Softpanorama

May the source be with you, but remember the KISS principle ;-)
Home Switchboard Unix Administration Red Hat TCP/IP Networks Neoliberalism Toxic Managers
(slightly skeptical) Educational society promoting "Back to basics" movement against IT overcomplexity and  bastardization of classic Unix

The Kernel Buffer Structures

The nature of physical disc drives is such that it is often only possible to transfer data in block size chunks. These are typically 512, 1024 or 2048 bytes. It is most unlikely that these units and the arbitrary boundaries they impose on the data will correspond to anything useful to the end-user application. To avoid multiple successive accesses to the same physical disc blocks the kernel maintains a set of block size in-core buffers and attempts to satisfy user requests from these blocks only initiating a physical disc read if necessary. Similarly when an end-user application writes to disc the kernel will, instead, modify the in-core buffer, only actually initiating a physical disc read if the user process so requests or if and when the buffer is required for some other purpose.

The performance advantages of in-core buffering or disc caching are fairly obvious and most operating systems provide this sort of facility. The number of such buffers is usually a "tunable" parameter. The size of buffers is not likely to be alterable and will impose constraints on the attachment of discs of very different characteristics. A multi-tasking operating system, such as Unix, imposes further constraints on the design of the kernel buffering system.

Associated with every buffer is a buffer header which contains the following information.

The kernel maintains a doubly linked list of free buffers known as the free list. Note that it is also possible for a buffer header not to be associated with a buffer, such headers are on the pfreelist. It also maintains a number of linked lists of used buffers known as hash queues. When a request is made for a disc block, the kernel hashes the device number and block number to decide which of the hash queues to explore looking for the block in question. The default number of hash queues is 64. If the required block is not found then a block is removed from the free list and a physical transfer is initiated. Of course it is very important to ensure consistency during these manipulations of the buffer structures and, to this end, the kernel will disable all interrupts while it manipulates certain key aspects of the buffer structures.

The operation of the kernel buffering system is described in terms of five algorithms, the names correspond to functions in the kernel source code.

  1. getblk()

    This associates a buffer number with device/block number. It may involve allocation of a new buffer via the geteblk() [get empty block] function. The buffer is locked and can be used for input or output. It is important to consider whether the buffer is "free" or not. In this context "free" means that there is currently no input/output activity in process for the buffer. The following possibilities may be encountered

    1. The block is found and is free. The block is marked busy and removed from the free list.
    2. The block is found and is busy. Under these circumstances there can be complex interactions between processes.
    3. The block cannot be found so new block is obtained from the free list. This involves marking the block as busy, transferring it to the new hash queue and removing it from the free list.
    4. The block cannot be found and a "delayed write" block is found on the free list. Asynchronous writing out of the "delayed write" block is initiated and an attempt is initiated to find another free block.
    5. The block cannot be found and the free list is empty. The process that, indirectly, initiated the search is slept waiting the execution of the brelse()

    The opreation of getblk can be described algorithmically thus.

    while(buffer not found)
    {
    	if(block in hash queue)
    	{
    		if(buffer busy/locked)
    		{
    			sleep(buffer becomes free)
    			continue
    		}
    		mark buffer busy/locked
    		remove buffer from free list
    		return buffer
    	}
    	else
    	{
    		if(no buffers on free list)
    		{
    			sleep(any buffer becomes free)
    			continue;
    		}
    		remove buffer from free list
    		if(delayed write buffer)
    		{
    			write buffer to disc (asynchronously)
    			continue
    		}
    		remove buffer from old hash queue
    		put buffer on new hash queue
    		return buffer
    	}
    }
    

    It should be noted that the algorithm returns (via continue) to re-examine the hash queues etc., whenever it wakes up after a sleep.

  2. brelse()

    This releases a used buffer back to the free list. The algorithm is

    {
    	wake up all processes waiting for this buffer
    	wake up all processes waiting for a free buffer
    	block interrupts
    	if(buffer contents valid AND buffer not "old")
    		put buffer at end of free list
    	else
    		put buffer at start of free list
    	unblock interrupts
    	mark buffer free
    }
    
  3. bread()

    This reads a disc block via the buffering system. The algorithm is.

    {
    	getblk()
    	if(buffer date valid) return buffer
    	initiate disc read
    	sleep (disc read complete)
    	return buffer
    }
    
  4. breada()

    This reads two disc blocks via the buffering system. The second block is read asynchronously which means that no process will be blocked awaiting completion of this speculative read ahead.

  5. bwrite()

    Writes data via the buffer system. This may be synchronous or asynchronous. The algorithm is

    {
    	initiate disc write
    	if(I/O synchronous)
    	{
    		sleep(disc write complete)
    		brelse(buffer)
    	}
    	else if(marked for delayed write)
    		mark buffer to put at head of free list
    }
    



Etc

Society

Groupthink : Two Party System as Polyarchy : Corruption of Regulators : Bureaucracies : Understanding Micromanagers and Control Freaks : Toxic Managers :   Harvard Mafia : Diplomatic Communication : Surviving a Bad Performance Review : Insufficient Retirement Funds as Immanent Problem of Neoliberal Regime : PseudoScience : Who Rules America : Neoliberalism  : The Iron Law of Oligarchy : Libertarian Philosophy

Quotes

War and Peace : Skeptical Finance : John Kenneth Galbraith :Talleyrand : Oscar Wilde : Otto Von Bismarck : Keynes : George Carlin : Skeptics : Propaganda  : SE quotes : Language Design and Programming Quotes : Random IT-related quotesSomerset Maugham : Marcus Aurelius : Kurt Vonnegut : Eric Hoffer : Winston Churchill : Napoleon Bonaparte : Ambrose BierceBernard Shaw : Mark Twain Quotes

Bulletin:

Vol 25, No.12 (December, 2013) Rational Fools vs. Efficient Crooks The efficient markets hypothesis : Political Skeptic Bulletin, 2013 : Unemployment Bulletin, 2010 :  Vol 23, No.10 (October, 2011) An observation about corporate security departments : Slightly Skeptical Euromaydan Chronicles, June 2014 : Greenspan legacy bulletin, 2008 : Vol 25, No.10 (October, 2013) Cryptolocker Trojan (Win32/Crilock.A) : Vol 25, No.08 (August, 2013) Cloud providers as intelligence collection hubs : Financial Humor Bulletin, 2010 : Inequality Bulletin, 2009 : Financial Humor Bulletin, 2008 : Copyleft Problems Bulletin, 2004 : Financial Humor Bulletin, 2011 : Energy Bulletin, 2010 : Malware Protection Bulletin, 2010 : Vol 26, No.1 (January, 2013) Object-Oriented Cult : Political Skeptic Bulletin, 2011 : Vol 23, No.11 (November, 2011) Softpanorama classification of sysadmin horror stories : Vol 25, No.05 (May, 2013) Corporate bullshit as a communication method  : Vol 25, No.06 (June, 2013) A Note on the Relationship of Brooks Law and Conway Law

History:

Fifty glorious years (1950-2000): the triumph of the US computer engineering : Donald Knuth : TAoCP and its Influence of Computer Science : Richard Stallman : Linus Torvalds  : Larry Wall  : John K. Ousterhout : CTSS : Multix OS Unix History : Unix shell history : VI editor : History of pipes concept : Solaris : MS DOSProgramming Languages History : PL/1 : Simula 67 : C : History of GCC developmentScripting Languages : Perl history   : OS History : Mail : DNS : SSH : CPU Instruction Sets : SPARC systems 1987-2006 : Norton Commander : Norton Utilities : Norton Ghost : Frontpage history : Malware Defense History : GNU Screen : OSS early history

Classic books:

The Peter Principle : Parkinson Law : 1984 : The Mythical Man-MonthHow to Solve It by George Polya : The Art of Computer Programming : The Elements of Programming Style : The Unix Haterís Handbook : The Jargon file : The True Believer : Programming Pearls : The Good Soldier Svejk : The Power Elite

Most popular humor pages:

Manifest of the Softpanorama IT Slacker Society : Ten Commandments of the IT Slackers Society : Computer Humor Collection : BSD Logo Story : The Cuckoo's Egg : IT Slang : C++ Humor : ARE YOU A BBS ADDICT? : The Perl Purity Test : Object oriented programmers of all nations : Financial Humor : Financial Humor Bulletin, 2008 : Financial Humor Bulletin, 2010 : The Most Comprehensive Collection of Editor-related Humor : Programming Language Humor : Goldman Sachs related humor : Greenspan humor : C Humor : Scripting Humor : Real Programmers Humor : Web Humor : GPL-related Humor : OFM Humor : Politically Incorrect Humor : IDS Humor : "Linux Sucks" Humor : Russian Musical Humor : Best Russian Programmer Humor : Microsoft plans to buy Catholic Church : Richard Stallman Related Humor : Admin Humor : Perl-related Humor : Linus Torvalds Related humor : PseudoScience Related Humor : Networking Humor : Shell Humor : Financial Humor Bulletin, 2011 : Financial Humor Bulletin, 2012 : Financial Humor Bulletin, 2013 : Java Humor : Software Engineering Humor : Sun Solaris Related Humor : Education Humor : IBM Humor : Assembler-related Humor : VIM Humor : Computer Viruses Humor : Bright tomorrow is rescheduled to a day after tomorrow : Classic Computer Humor

The Last but not Least Technology is dominated by two types of people: those who understand what they do not manage and those who manage what they do not understand ~Archibald Putt. Ph.D


Copyright © 1996-2021 by Softpanorama Society. www.softpanorama.org was initially created as a service to the (now defunct) UN Sustainable Development Networking Programme (SDNP) without any remuneration. This document is an industrial compilation designed and created exclusively for educational use and is distributed under the Softpanorama Content License. Original materials copyright belong to respective owners. Quotes are made for educational purposes only in compliance with the fair use doctrine.

FAIR USE NOTICE This site contains copyrighted material the use of which has not always been specifically authorized by the copyright owner. We are making such material available to advance understanding of computer science, IT technology, economic, scientific, and social issues. We believe this constitutes a 'fair use' of any such copyrighted material as provided by section 107 of the US Copyright Law according to which such material can be distributed without profit exclusively for research and educational purposes.

This is a Spartan WHYFF (We Help You For Free) site written by people for whom English is not a native language. Grammar and spelling errors should be expected. The site contain some broken links as it develops like a living tree...

You can use PayPal to to buy a cup of coffee for authors of this site

Disclaimer:

The statements, views and opinions presented on this web page are those of the author (or referenced source) and are not endorsed by, nor do they necessarily reflect, the opinions of the Softpanorama society. We do not warrant the correctness of the information provided or its fitness for any purpose. The site uses AdSense so you need to be aware of Google privacy policy. You you do not want to be tracked by Google please disable Javascript for this site. This site is perfectly usable without Javascript.

Last modified: March, 12, 2019