CS432/433

Assignment 1

Buffer Manager

Deadline : Sept. 24 1997 (CS432)

Introduction

In this assignment you will need to implement a buffer manager. The buffer manager is responsible for bringing pages from the disk to the main memory as needed. The buffer manager:

Flushes a page to the disk, if required
Pins a page to the buffer, bringing a page from the disk, if necessary
Unpins a page in the buffer by reducing the pin counter for that page
Frees up space that is allocated to a given page on the disk.
Allocates one or more frames and brings the requested pages from the disk
Keeps track of statistics of operations on buffer pool

In addition, you will be required to run experiments studying the effect the size of the buffer pool has on performance and present your results.

Description and Specifications

You will be given the code that implements a database class (DB) and a page class (Page). The definition of public interface for the buffer manager class (BufMgr) is available, but is not implemented. You can find out more about the implemented classes and types here :

Also, you'll be given a visualization tool, "BufferSim", which simulates buffer manager operations.

The source code for the project is located in the directory \\goose\courses\Cs432\Proj1. The directory contains:

bufmgr.cpp -- the code skeleton for the Buffer Manager, where you will find the detailed specs of the methods that you need to implement as well as the necessary interfaces.
bufmgr.h - the definition for the class BufMgr.
globaldefs\*.[Ch] - files to make a static library (Win32, Debug) "globaldefs.lib" that defines the global variables in Minibase. You should link the library with your buffer manager project. Details here .
test.cpp, bmtest.cpp, test.h, bmtest.h-- the source codes for the test that the Buffer Manager needs to pass. RunTests runs the tests on the Buffer Manager.
main.cpp - the main routine that initializes the Minibase, including the buffer manager, and run the test.
db.cpp, db.h, page.cpp, page.h - files that implement the DB class and Page class. You should compile both page.cpp and db.cpp and link it with your programs.
da_types.h, new_error.h, minirel.h, system_defs.h - the header files for minibase which define various type, global variables, etc.
proj1.exe - a sample executable (Win32, Console Application) which demonstrates the working of a buffer manager.
BufferSim.exe - a visualization tool that simulates buffer manager operations.

You are required to modify and fill in the gaps in bufmgr.cpp and bufmgr.h, specifically :

You need to implement the methods listed in bufmgr.cpp based on specifications as described in bufmgr.cpp. You do not need to modify any other files. However if you do decide to look at them you will learn more about how the project works. You are free to add any private methods or members into BufMgr, or make a function inline if you want to.
Your buffer manager should implement the Clock replacement policy, which is described in the textbook. (Hints : A good way to make your buffer manager extensible is to define the interface for a base replacement policy class with virtual functions etc. Then derive the Clock replacement policy from it, and implement the virtual functions. This way minimum changes are required if the buffer manger switches to a different replacement policy.)
In order to work with BufferSim , you bufmgr must write out a file in the format described in the documentation of the BufferSim. Check the above link for details and examples.
Your buffer manager should collect the following statistics:
1) Number of PinPage requests made.
2) Number of PinPage requests that result in a miss (i.e. the page is not in the buffer when the pin request is made)
3) Number of "dirty" pages written to disk.
4) Total time taken to run the test. (This will be collected for you by the code that already exists in main.cpp)
Also you will need to write two functions: one to reset the statistics and one to report the statistics using standard input/output stream libraries.
You need to link your implementation with the rest of the files, and make sure that the tests run successfully. (i.e. it's output should looks like the output from proj1.exe).

Presenting Statistical Data:

       1) After your tests have run successfully, you will need to run some experiments while varying the buffer size, and describe the effects a larger buffer pool has on the statistics (including time) that you have collected. You should also explain these variations.
        2) Running the experiments is basically running the tests provided for you again with different buffer sizes. At this point you should also look at the test procedures and see why the buffer size increases will affect the performance. (note: we are only interested in statistics relating to the fourth and fifth tests.)
        3) In order to change the buffer size go to the file minirel.h and change the value of the constant NUMBUF. The buffer sizes recommended are 50,100,150,200, and 250. (Note: The project you submit should have buffer size 50 only. We don't want five copies of everybody's project)
        4) Remember to close all major applications on your computer before running the tests, since they will affect the time it takes to run the tests.

**CS 433 students only**
    CS433 students are required to implement the MRU replacement policy as well. This policy is described in the text. They are also required to present statistical data that describes its performance with varying buffer sizes. (in the same manner as that of the Clock replacement policy). You should then contrast these results with those received for the Clock replacement policy. Remember that if you define the replacement policy as a base class with virtual functions then all you have to do is derive the MRU class and implement the functions using the MRU algorithm. This will involve minimum change in your buffer manager code.
    This section of the assignment is due on October 1, 1997 5:00 pm. No late submissions will be accepted.

Coding Convention

You need to follow certain coding convention for all your assignments.

Names for all classes/method/type should start with a caps. Break multiple words with caps. For example AddFileEntry.
Names for all members/variables should start with small letters. Break multiple words with caps. For example numOfPages;
Names for all enum/macro should be all caps. Break multiple words with underscore. For example MINIBASE_DB.

Submission Procedure

How to hand in:

Create a folder with your NetID (or your partner) as its name in your local directory.
Into this folder, drop your project file, source code, executable, and documentation. Make sure that while the executable is ready to run, it can be recompiled as needed.
Insert this folder into the Project 1 Submissions network directory in \\Goose\courses\Cs432\Proj1\Submissions.
Set the permissions on your folder (on the network drive) so that only the TA's (cs432stf) and yourself have 'Full Control' access permission. And, nobody else should have any permission to access this directory.

You should remember to keep a copy of the project in your own account.

This assignment is due on Sept. 24 1997, 5:00 pm for CS432, and Oct. 1 1997, 5:00pm for CS433. No late submission will be accepted.

Marking Criteria

We will mark your programs based on the following criteria :

Correctness (65%): You will get full marks if your implementation is correct. Partial credit will be given to a partially correct submission.
Coding Style (15%): We expect you to write neat code. Code should be nicely indented and commented. We also expect you to follow the coding conventions.
Statistical Analysis (10%)
You should clearly describe what effects a larger buffer pool has on performance and why. You should use the statistics you collect to support your reasoning.
Documentation (10%): You should also submit the online copy of your documentation using any format you like. (WordPerfect, MS Word, HTML etc.), explaining the code that you have written. This should include assumptions that you made, description of any new class that you have added, and any other special feature we should take note of. As a guideline, the document should be 2-3 pages long (with normal fonts and spacing), or more if you feel necessary.

Collaboration

Project will be done in team of two (you must stick with the same team for the rest of the semester). Both or none of the team members should be in cs433.

Both team members will receive the same grade. Also, collaboration across teams is not allowed, beyond discussing broad logical ideas (eg. how does the clock algorithm work?) and C++ doubts (e.g.. how does one initialize static variables?). Looking at the code from another team is also not allowed. In any situation where a team feels that it may have compromised one of these guidelines, the right thing to do is to state the details along with the project submission.

Miscellaneous

Please let us know if there is any ambiguity in the assignment and please report any possible bugs as soon as possible by mailing a TA .

There are now two newsgroups for the class : cornell.class.cs432 and cornell.class.cs433, for general discussions. Please used cornell.class.cs432 for discussion for this assignment.

Please check this page frequently for any updates or clarification.