UNIVERSITY OF WASHINGTON

CSE 594: DATABASE MANAGEMENT SYSTEMS

Implementation Project, Phase 1: Buffer Manager
Due: July 29, 1998

Introduction

In this assignment, you will implement a simplified version of the Buffer Manager layer, without support for concurrency control or recovery. You will be given the code for the lower layer, the Disk Space Manager.

You should begin by reading the chapter on Disks and Files, to get an overview of buffer management. This material will also be covered in class. In addition, HTML documentation is available for Minibase, which you can read using Netscape. There is a link to the Minibase home page in the CSE594 home page. In particular, you should read the description of the DB class, which you will call extensively in this assignment. The header file for the DB class is in db.h, and there is a link to this file.

The Buffer Manager Interface

The simplified Buffer Manager interface that you will implement in this assignment allows a client (a higher level program that calls the Buffer Manager) to allocate/de-allocate pages on disk, to bring a disk page into the buffer pool and pin it, and to unpin a page in the buffer pool.

The methods that you have to implement are described in the buf.h file that you will have after you setup the software.

Internal Design

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[numBuffers] of Page objects.

In addition, you should maintain an array frmeTable[numBuffers] of descriptors, one per frame. Each descriptor is a record with the following fields:

The pin_cnt field is an integer, pageNo is a PageId, and dirty 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. This is illustrated in Figure 1.

The hash function must distribute values in the domain of the search field uniformly over the collection of buckets. If we have HTSIZE buckets, numbered 0 through M-1, a hash function h of the form h(value) = (a*value+b) mod HTSIZE works well in practice. HTSIZE should be chosen to be a prime number.

When a page is requested the buffer manager should do the following:

  1. 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:
    1. Choose a frame for replacement, using the Clock replacement policy.
    2. If the frame chosen for replacement is dirty, flush it (i.e., write out the page that it contains to disk, using the appropriate DB class method).
    3. Read the requested page (again, by calling the DB class) into the frame chosen for replacement; the pin_cnt and dirty for the frame should be initialized to 0 and FALSE, respectively.
    4. Delete the entry for the old page from the Buffer Manager's hash table and insert an entry for the new page. Also, update the entry for this frame in the bufDescr array to reflect these changes.
  2. Pin the requested page by incrementing the pin_count in the descriptor for this frame. and return a pointer to the page to the requestor.

Where to Find Makefiles, Code, etc.

Complete instructions for copying, compiling, and testing, can be found here. For a description of the error protocol to follow, go here . An example file illustrating the use of the error protocol is available in: ErrProc.sample, which you will have once you follow the setup procedures. It covers much of what you need to know about the protocol. You can look at new_error.h, which you have also copied, for more details.

What to Turn In

You should turn in hardcopies of your code together with hardcopies of the output produced by running the tests provided by me. A solution will be made public after I receive all the submissions.