|
CSE-4411M
Database Management Systems
York University
Winter 2013
|
Project #1
The Buffer Pool Manager
from Java Minibase
(University of Wisconsin)
|
|
|
|
For
this project,
you are to implement a simplified version
of the Buffer Manager
layer within Java Minibase,
without support for concurrency control or recovery,
with the LRU replacement strategy.
You will be given the code for the lower layer,
the Disk Space Manager.
Review the chapter on Disks and Files,
to get an overview of buffer management.
See the
Javadoc Minibase documentation
to understand how (java) Minibase is put together and its layers'
APIs.
Read the description of the DB class,
the diskmgr package,
in the javadoc,
which you will call extensively in this assignment.
You should also look over the code under diskmgr/
to learn how a package is declared and how
Exceptions are handled in Minibase.
|
|
You
may work in teams of size two.
Email the instructor with who composes your team.
|
|
|
|
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 are to implement are described below:
public class BufMgr {
/**
* Create the BufMgr object.
* Allocate pages (frames) for the buffer pool in main memory and
* make the buffer manage aware that the replacement policy is
* specified by replacerArg (i.e. Clock, LRU, MRU etc.).
*
* @param numbufs number of buffers in the buffer pool.
* @param replacerArg name of the buffer replacement policy.
*/
public BufMgr(int numbufs, String replacerArg) {};
/**
* Pin a page.
* First check if this page is already in the buffer pool.
* If it is, increment the pin_count and return a pointer to this
* page. If the 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 (from the
* set of replacement candidates) to hold this page, read the
* page (using the appropriate method from {\em diskmgr} package) and pin it.
* Also, must write out the old page in chosen frame if it is dirty
* before reading new page. (You can assume that emptyPage==false for
* this assignment.)
*
* @param Page_Id_in_a_DB page number in the minibase.
* @param page the pointer poit to the page.
* @param emptyPage true (empty page); false (non-empty page)
*/
public void pinPage(PageId pin_pgid, Page page, boolean emptyPage) {};
/**
* Unpin a page specified by a pageId.
* This method should be called with dirty==true if the client has
* modified the page. If so, this call should set the dirty bit
* for this frame. Further, if pin_count>0, this method should
* decrement it. If pin_count=0 before this call, throw an exception
* to report error. (For testing purposes, we ask you to throw
* an exception named PageUnpinnedException in case of error.)
*
* @param globalPageId_in_a_DB page number in the minibase.
* @param dirty the dirty bit of the frame
*/
public void unpinPage(PageId PageId_in_a_DB, boolean dirty) {};
/**
* Allocate new pages.
* Call DB object to allocate a run of new pages and
* find a frame in the buffer pool for the first page
* and pin it. (This call allows a client of the Buffer Manager
* to allocate pages on disk.) If buffer is full, i.e., you
* can't find a frame for the first page, ask DB to deallocate
* all these pages, and return null.
*
* @param firstpage the address of the first page.
* @param howmany total number of allocated new pages.
*
* @return the first page id of the new pages. null, if error.
*/
public PageId newPage(Page firstpage, int howmany) {};
/**
* This method should be called to delete a page that is on disk.
* This routine must call the method in diskmgr package to
* deallocate the page.
*
* @param globalPageId the page number in the data base.
*/
public void freePage(PageId globalPageId) {};
/**
* Used to flush a particular page of the buffer pool to disk.
* This method calls the write_page method of the diskmgr package.
*
* @param pageid the page number in the database.
*/
public void flushPage(PageId pageid) {};
/** Flushes all pages of the buffer pool to disk
*/
public void flushAllPages() {};
/** Gets the total number of buffers.
*
* @return total number of buffer frames.
*/
public int getNumBuffers() {};
/** Gets the total number of unpinned buffer frames.
*
* @return total number of unpinned buffer frames.
*/
public int getNumUnpinnedBuffers() {};
};
|
|
|
|
The
buffer pool is a collection of frames
(each frame is a page-sized sequence of main memory bytes)
that is managed by the Buffer Manager.
Conceptually,
it should be stored as an array
bufPool[numbuf] of Page objects.
However, due to the limitation of Java language,
it is not feasible to declare an array of Page objects,
and later on write string (or other primitive values)
to the defined Page directly.
To circumvent this problem,
Page is defined as an array of bytes.
We deal with buffer pool at the byte array level.
Therefore,
when one implements the constructor for the BufMgr class,
one should declare the buffer pool as
bufpool[numbuf][page_size].
Note that the size of minibase pages is defined in the interface
GlobalConst of the global package.
Before jumping into coding,
please be certain to understand how a Page object
is defined and manipulated within Java Minibase.
In addition,
one should maintain an array
bufDescr[numbuf]
of descriptors,
one per frame.
Each descriptor is a record with the following fields:
- page_number,
- pin_count,
and
- 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.
When a pin request is received,
the BP manager needs an efficient way to determine
whether the page is already in the buffer pool.
To handle this,
you should implement
a simple hash table, or map.
With an input of page_number,
the hash table should return
the frame_number that the page occupies
(or "nil" if the page is not present).
Of course, this hash table should be main-memory based.
Yes, you may use available Java classes (java.utils)
for this.
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:
- Choose a frame for replacement,
using the LRU replacement policy.
- 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).
- Read the requested page (again, by calling the DB class)
into the frame chosen for replacement;
the pin_count and dirtybit for the frame
should be initialized to 0 and FALSE, respectively.
- 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.
- 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.
Recall that the LRU replacement policy is as follows.
(It is the same as the textbook describes,
so follow that.)
Whenever a page is unpinned to a pin_count of zero,
its associated frame is placed into a priority queue.
(Really, a "plain" queue works for this.
There is nothing "priority" about it.)
When a frame is needed to bring in a page not already
in the buffer pool,
choose as follows:
first, a free frame (a frame than currently holds no page)
is chosen, if available;
else,
the frame at the front of the queue is selected,
which contains the page that has been least recently used.
Note that you must use a queue data-structure (class)
that allows you to remove efficiently a frame from it
when that frame's page becomes pinned again.
We need the buffer pool manager to be fast,
and candidate frame selection is a core operation.
So we need frame selection, and the management of the queue,
to be fast.
I shall be grading whether you implement this part reasonably.
|
|
|
|
Where to Find Makefiles, Code, etc.
|
|
Please
copy all the files from
/cse/dept/course/2012-13/W/4411/bufmgr/src/,
on red.cs.yorku.ca or any of the York PRISM machines,
into a local directory of your own.
You can do this easily, for instance, by saying
-
% cp -rp /cs/dept/course/2012-13/W/4411/bufmgr/src bufmgr
This makes a copy into a directory called bufmgr
within your current directory.
The contents are:
- bufmgr/
You should keep all your code for bufmgr package
in this directory.
A sample Makefile is provided for compiling your project.
You will have to set up any dependencies by editing this file.
You can also design your own Makefile.
Whatever you do, please make sure that the classpath
is set to the one provided in
the original Makefile.
Here is a template file to get you started:
BufMgr.java.
- diskmgr/
You should look over the code for the diskmgr
package before you implement
your bufmgr package.
Detailed descriptions of the files are not included,
but the javadoc (java documentation) of the packages
describes things well.
This directory is just for your convenience and reference.
The code in this directory is not linked
when you compile your code!
Rather the version (identical) in the JAR
that contains all the Minibase base code is linked
instead.
- tests/
You may find other useful information by reading the java documentation
on other packages, such as the global package and the
chainexception package.
|
|
|
|
Although
the Throwable class in Java contains a snapshot of the execution
stack of its thread at the time it was created and also a message
string that gives more information about the error (exception),
Minibase maintains a copy of its own stack,
in order to have more control over the error handling.
The chainexception package handles the Minibase
exception stack.
Every exception created in the bufmgr package
should extend the ChainException class.
The exceptions are thrown according to the following rule:
- Error caused by an exception caused by another layer:
For example: (when try to pin page from diskmgr layer)
try {
SystemDefs.JavabaseBM.pinPage(pageId, page, true);
}
catch (Exception e) {
throw new DiskMgrException(e, "DB.java: pinPage() failed");
}
- Error not caused by exceptions of others, but needs to be acknowledged.
For example: (when try to unpin a page that is not pinned)
if (pin\_count == 0) {
throw new PageUnpinnedException (null, "BUFMGR: PAGE_NOT_PINNED.");
}
Basically, the ChainException class keeps track of all the exceptions
thrown accross the different layers.
Any exceptions that you decide to throw
in your bufmgr package should extend the ChainException class.
For testing purposes, we ask you to throw the following exceptions
in case of error (use the exact same name, please):
- BufferPoolExceededException:
Throw a BufferPoolExceededException when try to pin
a page to the buffer pool with no unpinned frame left.
- PagePinnedException:
Throw a PagePinnedException when try to free a page that
is still pinned.
- HashEntryNotFoundException:
Throw a HashEntryNotFoundException when page specified by
PageId is not found in the buffer pool.
Feel free to throw other new exceptions as you see fit.
But make sure that you follow the error protocol
when you catch an exception.
Also, think carefully about what else you need to do in the
catch phase.
Sometimes you do need to undo certain previous operations
when a failure happens.
|
|
|
|
What to Turn In (and When)
|
|
You
will use submit to submit your code,
together with copies of the
output produced by running the tests provided.
Submit as
-
% submit 4411 bufmgr ...
where ... are your code files and output files,
as specified.
Or where ... is a directory (e.g., bmproj/)
in which you put your code.
For documentation,
you do not need to produce javadoc,
and you do not need to comment extensively, line-by-line.
You should comment your code though,
commenting the methods,
commenting the fields,
and placing relevant comments in the code
where things would not be clear otherwise.
Include a small text file named report.txt .
In it,
state the team members
—
just yourself, if you did not work with others
—
and what contributions each person made.
State any problems you encounterd with the project,
and briefly outline to approach of your solution.
I do not expect this to be long;
likely, half a page.
For coding style,
choose a reasonable indentation convention
and be consistent.
Name your variables with understandable names.
And follow general good coding practise.
I will not grade the style component with respect to specific
style guidelines,
but rather with respect to general good coding practise.
A portion of the project grade
will be based on coding style.
Namely,
your code should be readable.
|
|
|
|
See
the FAQ (Frequently Asked Questions)
for the buffer pool manager project
for more information.
Read over the FAQ to start.
There is already quite a bit covered in it.
Not everything in the FAQ will make sense to you in the beginning.
Don't worry about that.
Each of those issues will become clear as your project proceeds.
Refer back to the FAQ as needed.
Of course, send reasonable questions my way, as needed.
Pertinent questions sent my way regarding the project
will make their way into the FAQ.
So check the FAQ online periodically for updates.
You may discuss the project with others in the class.
The work you turn in has to be your own.
|
|
|
Parke Godfrey
|
|
With much thanks and credit to the many folks
at the University of Wisconsin
who built Minibase and designed these projects.
|
|