Project 1. Buffer Manager
CS522, Fall 2004

Monday, October 18

Please upload all your files using the online turnin server. The uploaded files should include all the source code and any additional files needed to compile and run your project. Note that file uploading will be disabled automatically after 11:59PM of the due date, so please turn in your work on time.


In this assignment, you are going to use the Minibase database system, and implement a simple buffer management layer without support for concurrency control and recovery. The simplified buffer manager interface will allow a higher level program to allocate and deallocate pages on disk, to bring a disk page to the buffer pool and pin it, and to unpin a page in the buffer pool. In particular, the methods you have to implement are described below:
Allocate numbuf pages (frames) for the buffer pool in main memory.
Flush all dirty pages and de-allocate the buffer pool in main memory.
Check if this page is in buffer pool. If it is, increment  pin_count and return a pointer to this page. If pin_count was 0 before the call, the page was a replacement candidate, but is no longer a candidate. If the page is not in the pool, choose a frame to hold this page, read the page using proper DB class method, and pin it. Note that if the page in the chosen frame is dirty, you should write it out before reading in the new page. For this assignment, you may assume emptyPage is 0.
hate should be true if the page is "hated", and false otherwise.
dirty should be true if the client has modified the page, in which case, the call should set the dirty bit for this frame. Further, this call should decrement pin_count, and return error if pin_count is already 0 before this call.
This call allows a client of the buffer manager to allocate new pages on disk, and find a frame in the buffer pool for the first page allocated. In particular, if a frame is available, call DB object to allocate a run of new pages, read in the first page, and pin it. If the buffer is full, returns error.
This call allows a client of the buffer manager to delete a page on disk by calling proper function(s) in the DB class.
This call flushes a particular page of the buffer pool to disk, again, by calling proper function(s) in the DB class.
Flush all pages of the buffer pool to disk.

The files for this project can be downloaded as a zip file. Some important files for this assignment are:
[Design Overview and Implementation Details]

The buffer pool is a collection of frames (page-sized sequence of main memory bytes) that is managed by the Buffer Manager. It should be stored as an array bufPool[numbuf] of Page objects. In addition, you should maintain an array bufDescr[numbuf] of descriptors, one per frame. Each descriptor is a record with the following fields:

page number, pin_count, dirtybit

The pin_count field is an integer, page number is a PageId object, and dirtybit is a boolean. This describes the page that is stored in the corresponding frame. A page is identified by a page number that is generated by the DB class when the page is allocated, and is unique over all pages in the database. The PageId type is defined as an integer type in minirel.h.

A simple hash table should be used to figure out what frame a given disk page occupies.The hash table should be implemented (entirely in main memory) by using an array of pointers to lists of <page number, frame number> pairs. The array is called the directory and each list of pairs is called a bucket. Given a page number, you should apply a hash function to find the directory entry pointing to the bucket that contains the frame number for this page, if the page is in the buffer pool. If you search the bucket and don't find a pair containing this page number, the page is not in the pool. If you find such a pair, it will tell you the frame in which the page resides.

When a page is requested the buffer manager should do the following: Check the buffer pool (by using the hash table) to see if it contains the requested page. If the page is not in the pool, it should be brought in as follows: [Ths Love/Hate Replacement Policy]

Theoretically, the best candidate page for replacement is the page that will be last requested in the future. Since implementing such policy requires a future predicting oracle, all buffer replacement policies try to approximate it one way or another. The LRU policy, for example, uses the past access pattern as an indication for the future. However, sequential flooding can ruin this scheme and MRU becomes more appropriate in this particular situation. In this assignment you are supposed to implement the love/hate replacement policy. The policy tries to enhance prediction of the future by relying on a hint from the upper levels about the page. The upper level user hints the buffer manager that the page is loved if it is more likely that the page will be needed in the future, and hated if it is more likely that the page will not be needed. The policy is supposed to maintain an MRU list for the hated pages and an LRU list for the loved pages. If a page is needed for replacement, the buffer manager selects from the list of hated pages first and then from the loved pages if no hated ones exist.

A situation may arise when a page is both loved and hated at the same time. This can happen if the page was pinned by two different users and then was unpinned by the first one as a hated page and by the other as a loved page. In this case, assume that "love conquers hate", meaning that once a page is indicated as loved it should remain loved.