CSE373—Data Structures and Algorithms
for Nonmajors
Programming Assignment #2
due: Friday,
2/1/08, 10:00 PM
Introduction:
The interface from the operating system to
memory or disk storage involves operations that get space (e.g. writing to disk,
allocating memory) and release space (removing from disk, freeing memory). Algorithms for managing these limited
resources balance between computing a management policy efficiently and for the
policy to provide in an efficient use of space.
After repeated gets and releases, one problem that arises is
fragmentation, where the free space is scattered widely. When fragmentation is present, a large
request may not be able to be met if the space must be continuous, or the large
request may have to be answered by storing the data in many pieces, which is
slow to access. In this project, we’ll
implement a simple allocation system (potentially for files) that is designed
to be fast, use limited space, and fragment files into freed holes.
One solution is to have a table where for each
byte or cluster, mark whether or not it is used. This can be inefficient spacewise
because a large file may require many marks.
Instead we will maintain collections of variable-sized free space, for
example that from address 1000, the next 5000 are free, from address 16000, the
next 2000 are free, and from address 50000, the next 10000 are free. Hence the amount of space needed to store the
allocation information is based on the number of freed holes, rather than the
number of available bytes/clusters/spots.
Our method will occupy the first available free holes, which is quick to
compute. This means that files may be
fragmented, but large parts of the space will remain unused.
A skeleton of the code is as follows (download
the full skeleton from the webpage):
public class
AllocationManager {
PriorityQueue<FreeSpaceNode> freeSpace;
class BlockNode {
String name;
int blockSize;
BlockNode next;
}
class FreeSpaceNode {
int blockStart;
int blockSize;
public int compareTo() { … }
}
…
BlockNode get(String name, int size) { … }
void release(BlockNode b) { … }
}
FreeSpaceNodes represent chunks of
free space that can be allocated via calls to get. When chunks are allocated, they are returned
as BlockNodes.
Because we’d like to use the first available chunks of free space, we’ll
be using a data structure called a priority queue (PriorityQueue
in Java 1.5). The PriorityQueue
has two basic operations: offer (add), which adds an item to the PriorityQueue, and poll, which removes the smallest element
from the PriorityQueue (as determined by the objects’
compareTo).
You may also find peek useful, which looks at the smallest element
without removing it.
The method
get returns one or more BlockNodes chained together as a singly linked list to add
up to the requested size. The blocks are
chosen smallest first.
For example, initially
there are no blocks, so the free space looks like
{ 0 – 999999999 }
get(“A”,1000) will take free
space from the beginning, leaving the free space as
{ 1000 – 999999999 }
The chunk contains way
more space than is necessary, so get just takes what it needs and adds the
reduced free chunk back to the priority queue.
get(“B”,1000) will take free
space from the beginning, leaving the free space as
{ 2000 – 999999999 }
Now a release of the blocknodes corresponding to A will return those blocks back
to the free space
{0 – 999},{ 2000 – 999999999 }
Now get(“C”,2000)
will take free space from the beginning, not have enough, and take more space,
leaving the remaining free space as
{3000 – 999999999}
The blocks for “C” are
[0 – 999], [2000 – 2999]
A more detailed example
is available in AllocationManagerDemo.java. I highly recommend walking through that
example by hand and trying to understand it before coding it up. This project is more about understanding the
underlying design and data structures than writing the code (I think my
implementation adds less than thirty lines of code to the skeleton). But to write the code, you need to really
understand what is going on.
Programming
(70 points):
You should
use good style, whitespace, naming conventions, etc., and comment your code.
You may
not add any other imports, add any instance variables, change the FreeSpaceNode or BlockNode nested
classes, or add any public methods. You
may add private helper methods.
Remember
that even though FreeSpaceNode and BlockNode have private parts, you can use them inside the AllocationManager file.
1) Implement compareTo for FreeSpaceNode so that it can be used with the PriorityQueue.
A FreeSpaceNode is before another if its blockStart is before the blockStart
of the other.
2) Implement get(String,int) such that it runs in O(m log n), where m is the number
of fragments needed, and n is the
total number of fragments. The return value
of get is a linked list of BlockNodes that store
fragments of the file. They must have
increasing start addresses, all have the string as their names, and their sizes
must add up to the original size. If the
size is nonpositive, then return null and do nothing.
For this implementation, the fragments chosen
for allocation from the freed holes must be the first such freed holes
available; they are removed from the priority queue. If a hole is only partially used, the
remainder of the hole remains in the priority queue.
Additionally, if you use any holes that are
adjacent to each other, you should recognize that as such and make them into a
unified block. Instead of trying to
clean up adjacent holes as they are released, we’ll be lazy and clean them up
as they are requested (via get) again.
Hint: you
will store freed holes in a priority queue
3) Implement release(BlockNode) such that it runs in O(m log n), where m is the number
of fragments needed, and n is the
total number of fragments. Release will
add the BlockNode and its chained BlockNode
fragments separately to the priority queue of freed holes. Do not worry about the case where someone
calls release on a BlockNode that has already been
released.
4) Implement numFiles() such that it is O(1)
Hint: you
will use the state variable numFiles in the AllocationModel class
5) Implement numFragments() such that it is O(1)
Hint: you
will use a state variable numFiles in the AllocationModel class
6) Track the amount of total free space. Determine if a get
is asking for too much space in O(1) time. If it’s asking for too much space, then have get return null without ever removing any FreeSpaceNodes
from the priority queue (even if you’d end up putting them back).
Hint: you
will use a state variable totalFreeSpace in the AllocationModel class
Turn in
your work electronically from the “assignments” link on the class webpage.