You should print the free-list at the end in the increasing order of the addresses.
Assignment
In this assignment you will use binary search tree to create a memory allocation system that supports "allocate" and "free" primitives. Write a MemAlloc that implements the following interface:
interface MemAllocator {
int allocate(int size);
void free(int address, int size);
int allocatedSize();
}
The class implementing MemAllocator maintains the set of maximal blocks of free memory. Initially a single block
1 to ∞ is free. A block from address
a to b is maximal if addresses a-1 and b+1 are both allocated, i.e., not free.
allocate returns the address starting at which size free bytes are free. In order to reduce
fragmentation, the implementation must ensure that the smallest maximal block larger than the requested
size is always found. If no such block exists, 0 is returned (0 is not a valid address). If the
size of the block is less than twice the requested size, the entire block is allocated. Otherwise, only
the first size addresses are allocated; the block is split and the remaining block remains free.
allocatedSize returns the allocated size of the last most recently block (which may be larger than
the requested size).
free is permissive, meaning a non-allocated block may be "freed". The address specified in "free" need not
be one returned in a previous allocate either. After the method is complete,
all addresses from the given address to address+size-1 must be free. If a block contiguous
with the freed block is already free, the two are merged before the method returns.
You must implement a binary search tree class called BST to speed up allocate and free.
You will maintain one tree on the address key and another on the size key.
allocate employs size-BST to find the closest matching block and free employs address-BST to find
if any contiguous blocks are free. BST will require methods to find by keyword, delete a Position, insert a Position, as well as find the predecessar and successor Positions
Note that in your BST, all values less than or equal to a given node's must lie in its left subtree.
Implementation
Implement public class Assignment3, with a static main that takes on the command line, the name of a file containing a sequence of "alloc" and "free" calls. It reads the contents of the file, performing the requested actions. It produces the list of free blocks remaining at the end. The program should also take an optional argument "-l". When provided, it writes a log of operations to System.out (before producing the final list of free blocks).
Format
The input file has one command per line, one of
FREE <address> <size>
ALLOC <size>
FREE and ALLOC are keywords and the values in angled brackets are integers.
On output, the free list is written on a single line as a sequence:
FINAL <address1> <size1> <address2> <size2> ...
If the log option is enabled, at the end of the allocate method, the following line is printed:
ALLOC <address>
Also, for each size-BST node visited to find the closest matching node by allocate, the following line is printed:
VISIT <address> <size>
Examples
Input:
ALLOC 100
ALLOC 1000
ALLOC 10000
FREE 1101 100
FREE 1201 1000
FREE 1 100
ALLOC 50
Output:
VISIT 1 ∞
ALLOC 1
VISIT 101 ∞
ALLOC 101
VISIT 1101 ∞
ALLOC 1101
VISIT 11101 ∞
VISIT 1101 1100
VISIT 1 100
ALLOC 1
FINAL 51 50 1101 1100 11101 ∞
More To be added
Submission instructions
Submission will be at moodle.
Please ensure that you follow the following set of instructions meticulously while submitting the assignment on Moodle. Also, please note that in case of deviation from this procedure will render your submission faulty, and your assignment might not be evaluated at all by the script. Please follow these steps:
-
On eclipse, by default, all your source files (.java files) are saved into a directory called "src" inside your project. You have to compress this directory (to zip format) and rename the zip file in this format:
your-entry-number_assignment3.zip
Example: If your entry number is 2012CSZ8019, the zip file should be named 2012CSZ8019_assignment3.zip. It should expand to a directory called src, which contains all your .java files.
Please make sure that you follow exactly this naming format.
- Next, convert the zip file to base64 format. On any linux system, you can do this easily by issuing the following command on the terminal :
base64 entrynumber_assignment3.zip > entrynumber_assignment3.zip.b64
This will create a file with the same name with a b64 extension appended at the end.
- Upload this b64 file on moodle and submit it (in the "Submission" section). After Submission, there is an option of "Evaluate" in the "Edit" section.
Click on "Evaluate". On the right side of the window, you will get information about the submission status. On clicking the "Evaluate" link, you should see a script running and producing an output of your codes' performance against the standard set of test cases that we supply internally for the assessment. A dialog box will show you the messages on how your codes performed against the benchmarks that we provided.
Important notes