Buffer pool is collection of a buffers arrange in series. The kernel caches data in the buffer pool according algorithm called least recently used, after that it allocates a buffer for a disk block, it cannot use the same buffer again for another disk block until all other buffers have been used more recently. The kernel maintains a free list of buffers that holds the least recently used order for future use.

The free list is a double linked circular list of buffers with a dummy buffer header that marks its beginning and end (Figure below). Every buffer is put on the free list when the system is booted (started). The kernel takes a buffer from the head of the free list when it wants any free buffer to use, but it can also take a buffer from the middle of the free list if it identifies a particular block in the buffer pool. In both cases, it removes the buffer from the free list.

When the kernel returns a buffer to the buffer pool, it usually attaches the buffer to the tail of the free list, sometimes to the head of the free list if error cases occurs, but never to the middle. As the kernel removes buffers from the free list, a buffer with valid data moves closer and closer to head of the free list (Figure below). Hence, the buffers that are closer to the head of the free list have not been used as recently as those that are further from the head of the free list.

When the kernel accesses a disk block, it searches for a buffer with the appropriate device-block number combination. Rather than search the entire buffer pool, it organises the some buffers into separate queues, which are hashed as a function of the device and block number. The kernel links the buffers on a hash queue into a circular, doubly linked list, similar to the structure of the free list.

The number of buffers on a hash queue varies during the lifetime of the system, as will be seen. The kernel must use a hashing function that distributes the buffers uniformly across the set of hash queues, yet the hash function must be simple so that performance does not suffer. System administrator creates the number of hash queues during generation the operating system.

Fig shows buffers on their hash queues. The headers of the hash queues are shown on the left side of the figure, and the squares on each row are buffers on a hash queue. Thus, squares marked 30, 06, and 66 represent buffers on the hash queue for "blkno 0 mod 4" (block number 0 modulo 4).

The dotted lines between the buffers denotes the forward and back pointers for the hash queue. Same way, the figure identifies blocks only by their block number, and it uses a hash function which is dependent only on a block number; however, implementations use the device number too.

Each buffer always be there on a hash queue, but there position on the queue is not specific. As stated above, no two buffers may simultaneously contain the contents of the same disk block; so, every disk block in the buffer pool exists on one and only one hash queue and only once on that queue.

However, a buffer may be on the free list as well if its status is free. Because a buffer may be at a time on a hash queue and may be on the free list too, the kernel has two ways to find its location: It searches the hash queue if it is looking for a particular buffer, and it removes a buffer from the free list if it is looking for any free buffer. To summarise, a buffer is always on a hash queue, but it may or may not be on the free list.