CS432/433

Assignment 2

Buffer Manager

Deadline : September 23, 1998 3:20 PM.

Please check this page frequently for any updates or clarification.

09/21/98 - Added Instruction to select replacement policy.

This page was last updated on 09/21/98.

Click Here for instruction on selecting replacement policy.

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 :

• class DB
• class Page
• type Status
• type PageID
• type Bool
• macro MINIBASE_DB
• macro MINIBASE_BM

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\A2. 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 and MRU replacement policy, which is described in the textbook.  (Hint : 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 such as the MRU policy that you will need to implement also.)
• 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:

For each of the replacement policy you implemented (MRU and Clock), you need to do the following:

       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.
 
In addition, you should then constrast the performance of the buffer manager when using these two replacement policies. 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.

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.
• Follow the coding convention in BufMgr class. If you create a new function, make sure the header contains the necessary comments. (PreCond, PostCond, etc).

Hints & Notes

• Keep in mind that the buffer contains a fixed number of frames which should be initialized and allocated at the start of the program. Any subsequent operations on the buffer should only involve modifying these frames without allocating any new ones.
• Since the buffer manager manages a set of frames in memory which are mapped to pages on disk, a lookup mechanism is necessary for fast access (i.e. Hash Table). Make sure you encapsulate this mechanism in a separate class instead of merging it into your replacement policy class. This will make your life a lot easier when you switch the buffer manager to the other replacement policy.

Submission Procedure

How to hand in:

• Create a  folder with your and your partner's NetID (i.e dsm&barr) 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 Assignment 2 Submissions network directory in   \\Goose\courses\Cs432\A2\Submissions.
• Set the permissions on your folder (on the network drive) so that only the TA's 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  September 23, 1998 3:20 PM. No late submissions 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 teams of two.

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 use cornell.class.cs432 for discussion for this assignment.