Scenarios of Retrieval of a Buffer

High level kernel algorithm in file subsystem invokes the algorithm of a buffer pool to manage the buffer cache. There are five typical scenarios the kernel may follow in getblk to allocate a buffer for a disk block. These are listed follow:

1. The kernel finds the disk block on its hash queue, and its buffer is free.
2. The kernel cannot find the block on the hash queue; therefore it allocates a buffer from the free list.
3. The kernel cannot find the block on the hash queue and, in attempting to allocate a buffer from the free list (as in scenario 2), finds a buffer on the free list that has been marked "delayed write." The kernel must write the "delayed write" buffer to disk and allocate another buffer.
4. The kernel cannot find the block on the hash queue, and the free list of buffers is empty.
5. The kernel finds the block on the hash queue, but its buffer is currently busy.

Let’s see all scenarios one by one-

1. The kernel finds the block on its hash queue, and its buffer is free.

When Kernel is searching for a block in the buffer pool by its device-block number combination, the kernel finds the hash queue that should contain the block. It searches the hash queue, following the linked list of buffers until (in the first scenario) it finds the buffer whose device and block number match those for which it is searching. The kernel checks that the buffer is free and, if it is, then marks the buffer "busy" so that other processes cannot access it. The kernel then removes the buffer from the free list, because a buffer cannot be live busy and on the free list. If other processes try to access the block while the buffer is busy, they sleep until the buffer is released. Figure above depicts the first scenario, in which the kernel searches for block 6 on the hash queue marked "blkno 0 mod 4." By finding the buffer, the kernel removes it from the free list, and attaches blocks 7 and 30 adjacent on the free list.

2. The kernel cannot find the block on the hash queue, therefore it allocates a buffer from the free list.

The second scenario in algorithm getblk, the kernel in search of hash queue that should contain the block but it was not there, since the block cannot be on another hash queue because it cannot "hash" elsewhere, it is not in the buffer cache. So the kernel removes the first buffer from the free list instead; that buffer had been allocated to another disk block and is also on a hash queue. If the buffer has not been ready for delayed write, the kernel marks the buffer busy, removes it from the hash queue where it currently resides, reassigns the buffer header's device and block number to that of the disk block for which the process is searching, and places the buffer on the correct hash queue. The kernel uses the buffer but has no record that the buffer formerly contained data for another disk block.

3. The kernel cannot find the block on the hash queue and, in attempting to allocate a buffer from the free list (as in scenario 2), finds a buffer on the free list that has been marked "delayed write." The kernel must write the "delayed write" buffer to disk and allocate another buffer.

In the third scenario in algorithm getblk, the kernel also has to allocate a buffer from the free list. However, it discovers that the buffer it removes from the free list has been marked for "delayed write," so it must write the contents of the buffer to disk before using the buffer. The kernel starts an asynchronous write to disk and tries to allocate another buffer from the free list. When the asynchronous write completes, the kornel releases the buffer and places it at the head of the free list. The buffer had started at the end of the free list and had travelled to the head of the free list. If, after the asynchronous write, the kernel were to place the buffer at the end of the free list, the buffer would get a free trip through the free list, working against the least recently used algorithm. For example, in Figure, the kernel cannot find block 18, but when it attempts to allocate the first two buffers (one at a time) on the free list, it finds them marked for delayed write. The kernel removes them from the free list, starts write operations to disk for the blocks, and allocates the third buffer on the free list, block 4. It reassigns the buffer's device and block number fields appropriately and places the buffer, now marked block 18, on its new hash queue.

4. The kernel cannot find the block on the hash queue, and the free list of buffers is empty.

In the fourth scenario (Figure below), the kernel, acting for process A, cannot find the disk block on its hash queue, so it attempts to allocate a new buffer from the free list, as in the second scenario. However, no buffers are available on the free list, so process A goes to sleep until another process executes algorithm brelse, freeing a buffer. When the kernel schedules process A, it must search the hash queue again for the block. It cannot allocate a buffer immediately from the free list, because it is possible that several processes were waiting for a free buffer and that one of them allocated a newly freed buffer for the target block sought by process A. Thus, searching for the block again insures that only one buffer contains the disk block.

5. The kernel finds the block on the hash queue, but its buffer is currently busy.

The final scenario (Figure above) is complicated, because it involves complex relationships between several processes. Suppose the kernel, acting for process A, searches for a disk block and allocates a buffer but goes to sleep before freeing the buffer. For example, if process A attempts to read a disk block and allocates a buffer as in scenario 2, then it will sleep white it waits for the I/O transmission from disk to complete. While process A sleeps, suppose the kernel schedules a second process, B, which tries to access the disk block whose buffer was just locked by process A. Process B (going through scenario 5) will find the locked block on the hash queue. Since it is illegal to use a locked buffer and it is illegal to allocate a second buffer for a disk block, process B marks the buffer "in demand" and then sleeps and waits for process A to release the buffer.

6. Reading and Writing Disk Blocks

Up til now the allocation of buffer algorithm has been covered; the procedures for reading and writing disk blocks should be easy to understand. To read a disk block, a process uses algorithm getblk to search for it first in the buffer cache. If it is available in the cache, the kernel can return it immediately instead of physically reading the block from the disk. If it is not present in the cache, the kernel calls the disk drive to "schedule" a read request and goes to sleep awaiting the event that the I/O completes. The disk driver informs the disk controller hardware that it wants to read data, and the disk controller then transmits the data to the buffer. Finally, the disk controller interrupts the processor when the I/O is complete, and the disk interrupt handler awakens the sleeping process; the contents of the disk block are now here in the buffer. The modules that requested the particular block now have the data; when they no longer need the buffer they release it so that other processes can access it.

Algorithm Bread // Reading the block //

Input : Block number of file system
Output : Buffer which contain data

{
    receive the buffer for block // by using getblk algorithm
    if (Buffer data is valid)
    {
        return buffer
    }
    initiate Diskread;
    sleep (Disk read event completed);
    return(Buffer);
}

The algorithm for writing the contents of a buffer to a disk block is similar (Figure 2.3.4(b)). The kernel informs the disk driver that it has a buffer whose contents should be output, and the disk driver schedules the block for I/O. 1f the write is synchronous, the calling process goes to sleep awaiting I/O completion and else the buffer when it awakens. If the write is asynchronous, the kernel starts the disk write but does not wait for the write to complete. The kernel will release the buffer when the I/O completes.

Algorithm bwrite //writing the block //

Input : Buffer
Output : Nothing

{
    initialize the disk write;
    if(I/O syncronous)
    {
        sleep (I/O event completed);
        release the buffer (algo brelse);
    }
    else if (mark the buffer for delay write) 
    {
        mark the buffer to put at the free list head;
    }
}

Advantages and disadvantages

Advantages

1. Uniform disk access-System design is simpler.
2. Data is copying from user buffer to system buffer so it eliminates the need for special alignment of user buffers.
3. Use of buffer cache can minimise the amount of disk traffic.
4. Only single copy of disk block contained in a cache. It helps to ensure file system integrity.

Disadvantages

1. Delayed write-Vulnerable to crashes the leave disk data in incorrect state.
2. An extra data copy when reading and writing to and from user processes-Slow down when transmitting large data.