CS 525: Advanced Database Organization
Programming Assignment #2: Implementing a buffer manager

Deadline:

Soft and Hard: March 22

You must implement a buffer manager for an abstract DBMS. For this assignment, you do not have to worry about many issues, e.g. recovery or indices. You will need to address some issues related to concurrency as explained below, but not the concurrency mechanisms (e.g. semaphores) used in real systems.

This particular buffer manager takes commands directly from the user. If the user needs a block of data, he/she asks the buffer manager for it. The buffer manager must return an indication that the block is in its buffer pool. If the block is not in the buffer pool, then the buffer manager asks the underlying storage manager for it.

The goal of the buffer manager is to minimize the number of disk accesses, so D <= R, where D is the number of disk accesses and R is the number of block reads. Hopefully, D is much less than R.

User interface:

Below are the functions you must expose to the user:

• init(A) : initialize the buffer pool to use the replacement policy A. If you call this after you have started using the buffer pool, then you must reinitialize all relevant data structures and parameters.
• fix(blockn, accessmode) : this function brings a block number blockn into memory for use in mode accessmode, where access mode is either 'read' or 'read/write.' Note that a block can be fixed by the user multiple times, but only in `read’ mode.
• unfix(blockn) : this function tells the buffer manager that one instance of the usage (one of the “fixes”) of the block number blockn is complete.
• showstat: show the statistics described below. Alternatively, you can constantly return the statistics after each function call. This is a diagnostic function.
• showbufstats: display the contents of the BCB table. This is a diagnostic function.
• exit: terminate the program

How it works:

The buffer manager handles block access for the user (in reality, access modules such as index or record manager). When the user wants to read a block, he/she asks the buffer manager to fix it in memory. If the block is already in memory and not fixed in ‘read/write’ mode, the buffer manager increments the fix count of that block. If the block is already in memory but fixed in `read/write’ mode, it returns an error. If the block is not in memory, the buffer manager reads the block from disk, via the storage manager, and sets the appropriate access mode.

The buffer manager can only supply the block if there is space in the buffer. When the user is finished using the block, he/she tells the buffer manager to unfix the block, which will decrement the fix count of that block. When the buffer manager is full, and wants to read a block, it must pick an unfixed block (i.e., block with a fix count of 0) to be replaced with the requested one. Dirty blocks must be written back to disk before being replaced.

Some suggestions:

As usual, you should write modular code. Separate buffer manager functions from storage manager functions. To the very least, the buffer manager's functionalities include:

• FixPage - put a page in the buffer pool with read or read/write permissions. Assume that the read/write permission will dirty the block. If the block is not already in the buffer pool, read it from the storage manager.
• UnfixPage - unfix the page from the buffer pool.

These functions may in turn have to use other ones, including:

• GetReplacementCandidate - get a buffer page for replacement, based on the replacement policy A.
• GetNextReplacementCandidate - get a buffer page that would be next in line after the one returned above.

A real buffer manager would have many more functions than we listed here, but to keep the project tractable (and to emphasis the concepts), we'll keep ours simpler.

Your implementation may need more or fewer than these functionalities. See the simplifying assumptions below.

The storage manager has the following functions:

• ReadBlock - given a disk block number, it returns the block.
• WriteBlock - writes a block of memory to a disk block. You have to write all dirty blocks to disk.

You will need some data structures:

• Buffer Pool - contains the buffer pages
• BCB table - contains statistics about each page in the buffer pool, such as:
• logical address of the page in the buffer pool
• fix count
• dirty bit
• info needed for page replacement algorithm
• and much more...

Some of the variables you need to keep in mind are:

Definition of the buffer manager: the following variables define the buffer manager:

• SP - page size - the size of a unit of data in the buffer pool. Should be equal to the size of a disk block.
• NP - number of pages in the buffer pool
• A - page replacement strategy (e.g., LRU, MRU)

Definition of the database: the following variables define the database:

• NB - number of blocks in the database
• SB - size of the database blocks

Statistics: you must keep the following statistics while running the database application.

• R - Number of pages read
• D - Number of disk accesses

To help you figure out what you need in the BCB table, see the simplifying assumptions below.

Simplifying assumptions:

The goal of this project is to get you to understand the basic implementation of a buffer manager, and how page replacement algorithms work. We don't care so much about writing blocks to disk. Therefore, your storage manager accesses imaginary blocks from disk. In other words, all calls to storagemanager::readblock(x) succeed.

Consequently, you don't have to worry about the variables SB, NB, SP. Assume that the number of pages in your buffer pool (NP) is 5. In fact, you don't even have to implement a buffer pool (since there is no data). However, you still must decide on which variables to include in the BCB table to implement "correct" functionality.

We want you to implement the buffer manager that will support basic functionality and correctly replace buffer pool pages when the buffer pool is full. The page replacement algorithms we want you to implement are:

• FIFO - first in first out
• LRU - least recently used
• MRU - most recently used
• LFU - least frequently used

Hints:

Figure out how these algorithms work on paper by considering their behaviors under certain reference patterns. This should indicate to you what the structure of your BCB table should be. Once you figure out the BCB table, you should try to implement your replacement algorithm to work as computationally simply as possible.

Testing your work:

We will give you a series of fix and unfix commands, and check the statistics and the bufferStats (see above). To speed up the debugging (for you), and the grading (for us) processes, you should define the interface intelligently.

Turn in:

On or before the due date, you should submit through CourseInfo the source code (as many files as you have), the executable code called assign2.exe, and a readme file describing how your program works.

More info:

Refer to the class notes and the text for information on the page replacement algorithms, and implementing the buffer manager

Good luck!

Last updated: Mar. 1st, 2004