Chap 3. The Buffer Cache

Chap 3.
THE BUFFER CACHE

SS 10144019
Buffering Exam
#include <stdio.h> FILE* test; int I, data = 0; Int main() { test = fopen(test, w); for(i == 0; i < 2000; i++) fwrite(&data, sizeof(data), 1, test) return 0; }
Buffer Cache
The kernel attempts to minimize the frequency of disk access Buffer cache == pool of buffers Buffer cache contains the data in recently used disk blocks Higher-level kernel algorithms instruct the buffer cache modules to pre-cache data or to delay-write data to maximize caching effect
Buffer Header
Buffer consists of two parts:
Buffer header: identifies the buffer Memory array: contains disk block data
A disk block can never map into more than one buffer at a time => why? Buffer status: combination of following
Locked(or busy) Unlocked(or free) Buffer is valid Write buffer contents before reassigning buffer Currently reading or Writing the contents to disk Currently waiting for the buffer to become free
Buffer Header
device num
block num status
prev buf on hash queue
data area
next buf on hash queue
prev buf on free list
next buf on Free list
Structure of the buffer pool

Hash queue headers
28 17 98 3
4 5 50 35
64 97 10 99
Blkno
0 1 2 3
Free list headers
mod 4
BUFFER POOL
Free
Scenarios for retrieval of a buffer

Five typical scenarios in getblk()
1. Block in the hash queue, and its buffer is free 2. Cannot find block on the hash queue => allocate a buffer from free list 3. Scenario 2, but buufer on the free list marked delayed write => flush delayed write buffer and allocate another buffer 4. Cannot find block on the hash queue and free list of buffer also empty 5. Block in the hash queue, but buffer is busy
Algorithm for buffer allocation

while(buffer not found) { if(block in hash queue) { if(buffer busy) /*scenario 5*/ { sleep(event buffer becomes free); continues; /*back to while*/ } mark buffer busy; /*scenario 1*/ remove buffer from free list; return buffer; }
/* Next Page */
Algorithm for buffer allocation

else { if(there are no buffer 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; }

The first scenario-1
Hash queue headers
28 blkno0 mod 4 blkno1 mod 4 17
64
97
blkno2 mod 4 blkno3 mod 4
98
50
10
35
99
freelist header
(a) Search for Block 4 on First Hash Queue Figure 3.5
3.3 Scenarios for retrieval of a buffer

The first scenario-2
Hash queue headers
64
97
98
50
10
35
99
freelist header
(b) Remove Block 4 from Free List Figure 3.5
Algorithm for Releasing a Buffer

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); }

The second scenario-1
Hash queue headers
64
97
98
50
10
35
99
freelist header
(a) Search for Block 18-Not in Cache Figure 3.7

The second scenario-2
Hash queue headers
64
97
98
50
10
18
35
99
freelist header
(b) Remove First Block from Free List, Assign to 18 Figure 3.7

The third scenario-1
Hash queue headers
64
5 delay
97
98
50
10
3 delay
35
99
freelist header
(a) Search for Block 18- Delayed Write Blocks on Free List Figure 3.8

The third scenario-2
Hash queue headers
28 blkno0 mod 4 blkno1 mod 4 17 5 writing blkno2 mod 4 blkno3 mod 4 98 50
64
97
10
18
3 writing
35
99
freelist header
(b) Writing Blocks 3, 5, Reassign 4 to 18 Figure 3.8

The fourth scenario
Hash queue headers
Process A
Cannot find block b on hash queue
Process B
blkno0 mod 4
28
64
No buffers on free list

blkno1 mod 4 17 5 97
Sleep
Cannot find block b on hash queue No buffers on free list
blkno2 mod 4
98
50
10
Sleep
blkno3 mod 4
35
99
Somebody frees a buffer: brelse
freelist header
Takes buffer from free list Assign to block b
Figure 3.9 Fourth Scenario for Allocating Buffer
Figure 3.10 Race for Free Buffer

The fifth scenario
Process A
Allocate buffer to block b Lock buffer Initiate I/O Sleep until I/O done
Process B
Process C
Find block b on hash queue Buffer locked, sleep
Sleep waiting for any free buffer (scenario 4)
I/O done, wake up

Brelse(): wake up others Get buffer previously assigned to block b Reassign buffer to block b Buffer does not contain block b Start search again
Time
Figure 3.12 Race for a Locked Buffer
Reading a disk block

algorithm bread /*block bread*/ input: file system block number output: buffer containing data { get buffer for block(algorithm getblk); if(buffer data valid) return buffer; initiate disk read; sleep(event disk read complete); return(buffer); }
Read Ahead
Algorithm breada { if(first block not in cache) { get buffer for first block(algorithm getblk); if(buffer data not valid) initiate disk read; } if(second block not in cache) { get buffer for second block(algorithm getblk); if(buffer data valid) release buffer(algorithm brelse); else initiate disk read; }
Read Ahead()
if(first block was originally in cache) { read first block(algorithm bread); return buffer; } sleep(event first buffer contains valid data); return buffer;
}
Writing a disk block

algorithm bwrite /*block write*/ input: buffer output: none { initiate disk write; if(I/O synchronous) { sleep(event I/O complete); release buffer(algorithm brelse); } else if(buffer marked for delayed write) mark buffer to put at head of free list; }
Advantages of the buffer cache

Uniform disk access => system design simpler Copying data from user buffers to system buffers => eliminates the need for special alignment of user buffers. Use of the buffer cache can reduce the amount of disk traffic. Single image of of disk blocks contained in the cache => helps insure file system integrity
Disadvantages of the buffer cache

Delayed write => vulnerable to crashes that leave disk data in incorrect state
An extra data copy when reading and writing to and from user processes => slow down when transmitting large data

Chap 3. The Buffer Cache

Uploaded by

Copyright:

Available Formats

Chap 3. The Buffer Cache

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Chap 3. The Buffer Cache

Uploaded by

Copyright:

Available Formats

Chap 3.

THE BUFFER CACHE

next buf on hash queue

prev buf on free list

next buf on Free list

Structure of the buffer pool

Scenarios for retrieval of a buffer

Algorithm for buffer allocation

Algorithm for buffer allocation

Scenarios for retrieval of a buffer

28 blkno0 mod 4 blkno1 mod 4 17

blkno2 mod 4 blkno3 mod 4

3.3 Scenarios for retrieval of a buffer

28 blkno0 mod 4 blkno1 mod 4 17

blkno2 mod 4 blkno3 mod 4

Algorithm for Releasing a Buffer

Scenarios for retrieval of a buffer

28 blkno0 mod 4 blkno1 mod 4 17

blkno2 mod 4 blkno3 mod 4

Scenarios for retrieval of a buffer

28 blkno0 mod 4 blkno1 mod 4 17

blkno2 mod 4 blkno3 mod 4

Scenarios for retrieval of a buffer

28 blkno0 mod 4 blkno1 mod 4 17

blkno2 mod 4 blkno3 mod 4

Scenarios for retrieval of a buffer

28 blkno0 mod 4 blkno1 mod 4 17 5 writing blkno2 mod 4 blkno3 mod 4 98 50

Scenarios for retrieval of a buffer

No buffers on free list

Cannot find block b on hash queue No buffers on free list

Somebody frees a buffer: brelse

Takes buffer from free list Assign to block b

Figure 3.9 Fourth Scenario for Allocating Buffer

Figure 3.10 Race for Free Buffer

Scenarios for retrieval of a buffer

Find block b on hash queue Buffer locked, sleep

Sleep waiting for any free buffer (scenario 4)

I/O done, wake up

Reading a disk block

Writing a disk block

Advantages of the buffer cache

Disadvantages of the buffer cache

You might also like