Buffer Cache

UNIX Kernel Architecture
User programs
libraries
trap
User level
Kernel level
Sytem call interface
File subsytem
Buffer cache
Chracter
Process
control
sybsystem
Inter-process
communication
scheduler
Memory
management
block
Device drivers
Kernel level
Hardware level
Hardware control
hardware
System Calls
System call are similar to ordinary functions
Libraries map these function call to primitives
needed to enter OS
Assembly programs can directly invoke system
call
System calls can be categorized into :
File subsystem related calls
Process control system related calls
File subsystem related calls

Allocating file space
Free space management
File access control
open, close read, write, stat, chown, chmode etc
Process control system related calls
Process synchronization
Interprocess communication
Memory management
Process scheduling
Fork, exec, wait, exit etc.
File system layout

Boot block
Super block
Inode list
Data blocks
Boot block can contain the boot strap code

A file system may have an empty boot
block
describe state of file system
Size, number file it can store, location of free
space etc
Buffering
File subsystem accesses file data using
buffering mechanism
The mechanism regulates the flow between
buffer and secondary storage
The mechanism interacts with block i/o
device driver to initiate the data transfer
block I/O devices are random access
storage devices
Device drivers are kernel module that
controls the device operation
5
Buffer Cache
When a process wants to access data from a file,
the kernel brings the data into main memory,
alters it and then request to save in the file
system
Buffering increases the response time ,
throughput,
Buffering minimizes the frequency of disk
access by keeping a pool of internal data buffer
called buffer cache.
6
Buffer Cache
Buffer cache contains the data in recently used
disk blocks
When reading data from disk, the kernel
attempts to read from buffer cache.
If data is already in the buffer cache, the kernel
does not need to read from disk
If data is not in the buffer cache, the kernel
reads the data from disk and cache it
7
Buffer Headers
A buffer consists of two parts
a memory array
buffer header
disk block : buffer = 1 : 1

device num
block num
ptr to data area
status
ptr to previous buf on hash queue
ptr to next buf on hash queue
ptr to previous buf on free list
ptr to next buf on free list
Figure 3.1 Buffer Header
Buffer Headers
device num
logical file system number
block num
block number of the data on disk
status
The buffer is currently locked.

The buffer contains valid data.
delayed-write
The kernel is currently reading or writing the contents of buffer to disk.
A process is currently waiting for the buffer to become free.
kernel identifies the buffer content by examing device num and

block num.
Structures of the buffer pool

Buffer pool according to LRU
The kernel maintains a free list of buffer
doubly linked list
take a buffer from the head of the free list.
When returning a buffer, attaches the buffer to the
tail.
Forward ptrs
free list
head
buf 1
buf 2
buf n
Back ptrs
Figure 3.2 Free list of Buffers
10
Structures of the buffer pool

When the kernel accesses a disk block
separate queue (doublely linked circular list)
hashed as a function of the device and block num
Every disk block exists on one and only on hash
queue and only once on the queue
Hash queue headers
28
64
blkno1 mod 4
17
97
blkno2 mod 4
98
50
10
blkno3 mod 4
35
99
blkno0 mod 4
Figure 3.3 Buffers on the Hash Queues
11
Scenarios for retrieval of a buffer

Determine the logical device num and block num
The algorithms for reading and writing disk blocks use
the algorithm getblk
The kernel finds the block on its hash queue
The buffer is free.
The buffer is currently busy.
The kernel cannot find the block on the hash queue

The kernel allocates a buffer from the free list.
In attempting to allocate a buffer from the free list, finds a buffer on
the free list that has been marked delayed write.
The free list of buffers is empty.
12
Retrieval of a Buffer:1st Scenario (a)

The kernel finds the block on the hash queue and its buffer is
free
Hash queue headers
28
64
17
97
98
50
10
35
99
blkno0 mod 4
blkno1 mod 4
blkno2 mod 4
blkno3 mod 4
freelist header
Search for block 4
13
Retrieval of a Buffer:1st Scenario (b)

28
64
17
97
98
50
10
35
99
blkno0 mod 4
blkno1 mod 4
blkno2 mod 4
blkno3 mod 4
freelist header
Remove block 4 from free list
14
Retrieval of a Buffer: 2nd Scenario (a)

The kernel cannot find the block on the hash queue, so it
allocates a buffer from free list
Hash queue headers
28
64
17
97
98
50
10
35
99
blkno0 mod 4
blkno1 mod 4
blkno2 mod 4
blkno3 mod 4
freelist header
Search for block 18: Not in cache
15
Retrieval of a Buffer: 2nd Scenario (b)

Hash queue headers
28
64
17
97
98
50
10
35
99
blkno0 mod 4
blkno1 mod 4
blkno2 mod 4
blkno3 mod 4
18
freelist header
Remove 1st block from free list: Assign to 18

16
Retrieval of a Buffer: 3rd Scenario (a)

The kernel cannot find the block on the hash queue, and finds delayed write
buffers on hash queue
Hash queue headers
28
64
17
97
blkno0 mod 4
blkno1 mod 4
blkno2 mod 4
blkno3 mod 4
delay
98
50
10
35
99
delay
freelist header
Search for block 18, Delayed write blocks on free list

17
Retrieval of a Buffer: 3rd Scenario (b)

Hash queue headers
28
64
blkno0 mod 4
blkno1 mod 4
17
97
writing
blkno2 mod 4
blkno3 mod 4
98
50
10
35
99
18
writing
freelist header
(b) Writing Blocks 3, 5, Reassign 4 to 18
Figure 3.8
18
Retrieval of a Buffer: 4th Scenario

The kernel cannot find the buffer on the hash queue, and the free list is empty
Hash queue headers
28
64
17
97
blkno2 mod 4
98
50
10
blkno3 mod 4
35
99
blkno0 mod 4
blkno1 mod 4
freelist header
Search for block 18, free list empty
19
Retrieval of a Buffer: 5th Scenario

Kernel finds the buffer on hash queue, but it is currently busy
Hash queue headers
28
64
17
97
98
50
10
35
99
blkno0 mod 4
blkno1 mod 4
blkno2 mod 4
blkno3 mod 4
busy
freelist header
Search for block 99, block busy
20
File System Algorithms
namei
alloc free
iget
ialloc ifree
iput
buffer allocation algorithms
getblk
brelse
bread
bwrite
Lower Level File system Algorithms

21
Inode
contains the information necessary for a process to
access a file
exits in a static form on disk and the kernel reads
them into an in-core inode
22
Inodes
consists of
- file owner identifier
- file type
- file access permissions
- file access times
- number of links to the file
- table of contents for the disk address of data in a
file
- file size
23
Inodes
in-core copy of the inode contains
- status of the in-core inode indicating
- logical device number of file system
- inode number
- pointers to other in-core inodes
- reference count
24
inode contains the table of content to locate a file

data
Since each block on a disk is addressable by
number , the table of content consists of set of
disk block number
If file were stored in contiguous manner, start
block number and file size would have been
enough .
This strategy would not allow expansion/ contraction
25
File data may not be necessarily be stored in

contiguous manner
This would enable file to be of any size and can be
easily expanded or contracted
This would require basic unit of allocation unit to be a
block
The table of content would set of block number
The size of table of content will vary with size of file
26
Structure of a regular file

Inode
Data Blocks
direct0
direct1
direct2
direct3
direct4
direct5
direct6
direct7
direct8
direct9
single indirect
double indirect
triple indirect
27
Structure of a regular file

Assume that a logical block on the file system holds 1K bytes,
A block number is addressable by a 32 bit integer, then a block can hold up to 256
block numbers
10 direct blocks with 1K bytes each=10K bytes
1 indirect block with 256 direct blocks= 1K*256=256K bytes
1 double indirect block with 256 indirect blocks=256K*256=64M bytes
1 triple indirect block with 256 double indirect blocks=64M*256=16G bytes
28

Buffer Cache

Uploaded by

Copyright:

Available Formats

Buffer Cache

Uploaded by

Document Information

Original Description:

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

Buffer Cache

Uploaded by

Copyright:

Available Formats

UNIX Kernel Architecture

Sytem call interface

File subsystem related calls

File system layout

Boot block can contain the boot strap code

disk block : buffer = 1 : 1

ptr to data area

The buffer is currently locked.

kernel identifies the buffer content by examing device num and

Structures of the buffer pool

Figure 3.2 Free list of Buffers

Structures of the buffer pool

Figure 3.3 Buffers on the Hash Queues

Scenarios for retrieval of a buffer

The kernel cannot find the block on the hash queue

Retrieval of a Buffer:1st Scenario (a)

Search for block 4

Retrieval of a Buffer:1st Scenario (b)

Remove block 4 from free list

Retrieval of a Buffer: 2nd Scenario (a)

Search for block 18: Not in cache

Retrieval of a Buffer: 2nd Scenario (b)

Remove 1st block from free list: Assign to 18

Retrieval of a Buffer: 3rd Scenario (a)

Search for block 18, Delayed write blocks on free list

Retrieval of a Buffer: 3rd Scenario (b)

Retrieval of a Buffer: 4th Scenario

Search for block 18, free list empty

Retrieval of a Buffer: 5th Scenario

Search for block 99, block busy

File System Algorithms

Lower Level File system Algorithms

inode contains the table of content to locate a file

File data may not be necessarily be stored in

Structure of a regular file

Structure of a regular file

You might also like