Implementation of a Disk-based Buffer Pool
A buffer pool is an area of main memory that has been allocated for the purpose of caching data
blocks as they are read from disk. The main purpose of a buffer pool is to minimize disk I/O.
Tasks: Implement a disk-based buffer pool application based on the below three buffer pool
replacement schemes: FIFO (first in, first out), LRU (least recently used), and LFU (Least
frequently used) buffer pool replacement strategies.
FIFO (First In, First Out): the oldest data block in the buffer pool is replaced.
LRU (Least Recently Used): the least recently accessed data block in the buffer pool is replaced.
LFU (Least Frequently Used): the least frequently accessed data block in the buffer pool is
replaced.
Initially, the buffer pool is free. Disk blocks are numbered consecutively from the beginning of
the file with the first block numbered as 0. When I execute your program,
First, it asks the user to input the following parameters:
o ?: number of blocks in the buffer pool
o b: number of blocks on the disk, of course b >= a.
o c: the size of each block in bytes (i.e., 1024)
o ?: number of disk address accesses
o ???: the percentage of the l accesses that are writes, in the range of [0,1]. When 0,
all the accesses are reads; when 1, all the accesses are writes.
Then your program generates the
l
address requests, each is a random number in the range of
[0,
b * c – l], the entire address space of the disk. The disk and buffer pool accesses take place as
follows.
For each read access, it checks if the requested data block containing that address is already in
the buffer pool. If yes, there is no I/O; otherwise, the data block is brought into an empty data
block of the buffer pool from the disk, causing one I/O. However, if the buffer pool is full and
the requested data block is not in buffer block, then one of the three block replacement
algorithms (i.e., FIFO, LRU, and LFU) will be used to evict one of the existing data blocks in the
buffer pool, so the requested data block can be brought into the buffer pool from the disk.
For each write access, your program checks if the data block containing that address is in the
buffer pool. If yes, then there is no I/O, and the block is marked dirty (which means the block is
updated and needs to be written back to the disk). Otherwise, the data block is brought into an
empty data block of the buffer pool from the disk, causing one I/O, and the block is then marked
dirty. However, if the buffer pool is full and the newly requested data block is not in the buffer
pool, one of the three block replacement algorithms (i.e., FIFO, LRU, and LFU) will be used to
evict one of the existing data blocks in the buffer pool. If the to-be-evicted data block is dirty, it
needs to be written back to the disk, causing one I/O.
Then, after all the l disk accesses, it clears the buffer pool. That is, if its dirty bit is on, write it
back to the disk, causing one I/O.
Finally, it prints out the number of IOs for each of the three buffer pool replacement schemes.
Submission: Please submit a zip file named
LastNameFirstStudent_LastNameSecondStudent_541_proj3.zip. Only .zip format is allowed,
don’t include .rar file. It includes
• The source code of your program and a readme file as how to compile and run your
program.
• How to compile and execute your programs.
• Five screenshots showing your successful execution
• Contribution of each student if it is done by two students.
• Compare the total number of I/Os by varying
o a = 200, 400, 600, 800, 1000, while fixing b=10000, c =1024, l=1000, ??? =
50%.
o ??? = 10%, 30%, 50%, 70%, 90%, while fixing a = 500, while fixing b=10000,
c=1024, l=1000.
o Design a table and draw above two plots in Excel; each data in the plot is an average of 10 values,
with confidence interval of 95% (https://support.microsoft.com/enus/office/confidence-function-75ccc007-f77c-4343-bc14-673642091ad6)