Scenarios 3 For Retrieval Of A Buffer In Unix

if (there are no buffers on free list) /* scenario 4 •/ [

sleep (event any buffer becomes free); continue; /* back to while loop */

remove buffer from free list;

if (buffer marked for delayed write) ( /* scenario 3 */ asynchronous write buffer to disk; continue; /* back to while loop */

/* scenario 2 — found a free buffer "/ remove buffer from old hash queue; put buffer onto new hash queue; return buffer;

Figure 3.4. Algorithm for Buffer Allocation

hash queue headers

(b) Remove Block 4 from Free List Figure 3.5. Scenario 1 in Finding a Buffer: Buffer on Hash Queue algorithm brelse input: locked buffer output: none (

wakeup all procs: event, waiting for any buffer to become free; wakeup all procs: event, waiting for this buffer to become free; raise processor execution level to block interrupts; if (buffer contents valid and buffer not old) enqueue buffer at end of free list else enqueue buffer at beginning of free list lower processor execution level to allow interrupts; unlock(buffer);

Figure 3.6. Algorithm for Releasing a Buffer

Before continuing to the other scenarios, let us consider what happens to a buffer after it is allocated. The kernel may read data from the disk to the buffer and manipulate it or write data to the buffer and possibly to the disk. The kernel leaves the buffer marked busy; no other process can access it and change its contents while it is busy, thus preserving the integrity of the data in the buffer. When the kernel finishes using the buffer, it releases the buffer according to algorithm brelse (Figure 3.6). It wakes up processes that had fallen asleep because the buffer was busy and processes that had fallen asleep because no buffers remained on the free list. In both cases, release of a buffer means that the buffer is available for use by the sleeping processes, although the first process that gets the buffer locks it and prevents the other processes from getting it (recall Section 2.2.2.4). The kernel places the buffer at the end of the free list, unless an I/O error occurred or unless it specifically marked the buffer "old," as will be seen later in this chapter; in the latter cases, it places the buffer at the beginning of the free list. The buffer is now free for another process to claim it.

Just as the kernel invokes algorithm brelse when a process has no more need for a buffer, it also invokes the algorithm when handling a disk interrupt to release buffers used for asynchronous I/O to and from the disk, as will be seen in Section 3.4. The kernel raises the processor execution level to prevent disk interrupts while manipulating the free list, thereby preventing corruption of the buffer pointers that could result from a nested call to brelse. Similar bad effects could happen if an interrupt handler invoked brelse while a process was executing getblk, so the kernel raises the processor execution level at strategic places in getblk, too. The exercises explore these cases in greater detail.

In the second scenario in algorithm getblk, the kernel searches the hash queue that should contain the block but fails to find it there. Since the block cannot be on another hash queue because it cannot "hash" elsewhere, it is not in the buffer blkno 3 mod 4

(a) Search for Block 18 - Not in Cache blkno 2 mod 4

freelist header hash queue headers blkno 0 mod 4

blkno 1 mod 4

blkno 1 mod 4

blkno 2 mod 4

hash queue headers blkno 0 mod 4

blkno 3 mod 4

freelist header

(a) Search for Block 18 - Not in Cache

blkno 3 mod 4

hash queue headers blkno 0 mod 4 •

(b) Remove First Block from Free List, Assign to 18 Figure 3.7. Second Scenario for Buffer Allocation blkno 1 mod 4

blkno 2 mod 4

blkno 3 mod 4

freelist header 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 marked for a delayed write (as will be described later), 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. A process searching for the old disk block will not find it in the pool and will have to allocate a new buffer for it from the free list, cxactly as outlined here. When the kernel finishes with the buffer, it releases it as described above. In Figure 3.7, for example, the kernel searches for block 18 but docs not find it on the hash queue marked "blkno 2 mod 4." It therefore removes the first buffer from the free list (block 3), assigns it to block 18, and places it on the appropriate hash queue.

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 kernel 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 traveled 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 3.8, 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.

In the fourth scenario (Figure 3.9), 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 arc 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. Figure 3.10 depicts the contention between two processes for a free buffer.

The final scenario (Figure 3.11) 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

writing

blkno 0 mod 4

blkno 1 mod 4

blkno 2 mod 4

blkno 3 mod 4

frcclist header writing

(b) Writing Blocks 3, 5, Reassign 4 to 18

Figure 3.8. Third Scenario for Buffer Allocation hash queue headers hash queue headers blkno 0 mod 4

blkno 1 mod 4

blkno 2 mod 4

blkno 3 mod 4

frcclist header

+1 0

Post a comment