This program implements a simplified manager of a memory pool. The memory pool is a fixed number of blocks of memory which is modelled (for this assignment) as a 1D array of 32 byte objects. The index of each element of the array is treated as though it is the actual address of the memory block.
Memory (e.g., the heap) is divided into equal sized blocks. A user can request (alloc) one block or return (free) one block.
To request a block, the user would use the method: int alloc(int num);
The return value is the index of the block that has been allocated. The argument
is 1 (only a single block can be allocated or freed for this assignment --
for extra credit, see below).
When a user requests a block, the manager finds a free block, changes it to an allocated block, then returns the address of the block to the user.
When a user frees a block, the manager changes the block from allocated to free.
To free a block, the user calls the method free(int num); The method
returns no value, the argument is the address of the block being freed.
The linked list data structure is the primary data structure for keeping track of free and allocated memory blocks: there is a linked list of free blocks and a second linked list of used blocks.
free() and alloc() should throw exceptions.
free() throws invalid address exception when the user supplies an illegal address.
free() throw invalid action exception when user frees a block that is already free.
alloc() throws block not available exception when there are no (insufficient) free blocks.
| user | resulting free list | resulting used list | |
|---|---|---|---|
| Start state | 0, 1, 2, 3 | empty | |
| alloc(1) | 1, 2, 3 | 0 | |
| alloc(1) | 2, 3 | 0, 1 | |
| free(0) | 0, 2, 3 | 1 | |
| free(0) | 0, 2, 3 | 1 | throw Invalid Action |
| alloc(1) | 0, 3 | 1, 2 | |
| alloc(1) | 0 | 1, 2, 3 | |
| alloc(1) | empty | 0, 1, 2, 3 | |
| alloc(1) | empty | 0, 1, 2, 3 | throw Block Not Available |
| free(27) | empty | 0, 1, 2, 3 | throw Invalid Address |
alloc
is not important -- I tried to randomize. In your actual implementation, you will need to
write code that picks a reasonable free block (e.g., "first in the free list").
What you hand in for grading must demonstrate your program working correctly.
You must supply an argument at run-time (either run-time argument or query user) that sets the size of the memory pool.
Satisfying the functional specifications Coding style -- includes reasonable documentation Elegance of implementation
alloc() call. For example, alloc(3); will return the address
of the start of three consecutive blocks for the user.
alloc() will only allocate consecutive blocks. Therefore, only a single
address (the start of the first block is returned to the user). Obviously all three
blocks must have been moved from free list to the used list. Also obviously the
three blocks must be contiguous in memory -- they do not have to be contiguous in the
linked list of free objects.
free() works the same as before. Only one block at a time is freed.
So, the user code to allocate then free 3 blocks:
x = alloc(3); free(x); free(x+1); free(x+2);Now! in actuality, free() works in an intelligent way (see here). However, implementing this more user-friendly free() requires the memory manager to *also* keep track of the number of blocks allocated.
This is actually not that hard to do by storing the number of allocated blocks in the nodes in the used list.
I will draw you a picture if you are interested.
x = alloc(1); y =alloc(1); free(x); free(0); free(0); z[0] = alloc(1); z[1] = alloc(1); z[2] = alloc(1); z[3] = alloc(1); z[4] = alloc(1); free(0); free(27);