CS357: Database System Implementation
Homework Assignment 3 -- Disk and Memory Management
| Given: |
Wednesday, 6 February |
| Due Date: |
Wednesday, 13 February
|
The SimpleDB buffer manager is grossly inefficient in two ways:
- When looking for a buffer to replace, it uses the first unpinned
buffer it finds, instead of doing something intelligent like LRU.
- When checking to see if a block is already in a buffer, it does a
sequential scan of the buffers, instead of keeping a data structure
(such as a map) to more quickly locate the buffer.
I would like you to modify the buffer manager to fix these problems.
You are free to change (or rewrite) any of the files in the
package simpledb.buffer, in any way that you like. Think about what makes sense to do. My solution modifies the classes Buffer, BasicBufferMgr, and BufferMgr.
However, I want to point out that the number of lines of code did
not change much, which means that you don't need to do a lot of coding
to get this to work.
In order to get you started and to keep you from doing something weird, here are some guidelines to adhere to:
- Keep a list of unpinned buffers. Treat the list as a queue.
When a replacement buffer needs to be chosen, remove the buffer at
the head of the list and use it.. When a buffer becomes unpinned, add it to
the end of the list. This implements LRU replacement.
- Keep a Map
of allocated buffers, keyed on the block they contain. (A buffer
is allocated when its contents is not null, and may be pinned or
unpinned. A buffer starts out unallocated; it becomes allocated
when it is first assigned to a block, and stays allocated forever
after.) Use this map to determine if a block is currently in a
buffer. When a buffer is replaced, you must change the map --
The mapping for the old block must be removed, and the mapping for
the new block must be added.
- Write toString methods for Buffer, BufferMgr, and BasicBufferMgr. The purpose of these methods is to display the contents of the buffer for testing purposes. The method for Buffer
should show the buffer's id, the block it is allocated to, and whether
the buffer is pinned. The method for the other two classes should
show the information for each buffer. I found it useful to modify
the constructor of Buffer to take an integer argument denoting the buffer's id. (Otherwise, a buffer doesn't know which one it is.)
You also must write a test program. The program should demonstrate that the buffers
are really allocated using LRU, by doing judicious pinning and
unpinning. Note that the call to SimpleDB.init causes the buffers to get used, so your test program won't be able to start from a clean slate.
Hand in a printout of all files you wrote code for (including the test
program), as well as a printout of the output of the test program.
If you have any kind of Java-related problem, please see me early
or ask questions in class.