Assignment #4: Dynamic Allocation
CS201 Fall 2021
Part One: 20 points, due Thursday, Nov. 11th, 11:59 pm
second chance for 18 points due TBD
Part Two: 20 points, due Saturday, Nov. 20th, 11:59 pm
1 Dynamic Allocation
You may work with a partner on this assignment. Graduate students must work individually.
For Part Two, you’ll implement best-fit, worst-fit, and first-fit dynamic-allocation strategies.
To accomplish this, you’ll do random allocation of contiguous groups of elements of a finite-capacity resource.
You need to keep track only of the size and location of each allocation.
A straightforward way to think about this is as array of fixed size in which groups of contiguous elements
are allocated. As groups of elements are allocated and deallocated, holes will appear, and the free space will
become more and more fragmented.
For Part One, you’ll write the utility functions that will allow you to do the allocations in Part Two.
2 Details
You’ll maintain two lists: the current allocations, and the current holes. Each list will consist of nodes having
(location, size) pairs.
Suppose the array from which we are allocating has a length of 20, and the following allocations have been
made:
Then the current-allocation list would consist of these entries: {(2, 3), (9, 2), (14, 1), (16, 4)}, and
the current-hole list would have these entries: {(0, 2), (5, 4), (11, 3), (15, 1)}. So in other words,
there is an allocation of length 3 that starts at position 2; an allocation of length 2 that starts at position 9;
etc. And there is a hole of length 2 that starts at position 0; a hole of length 4 that starts at position 5; etc.
Together, the union of the holes and the allocations should be the full array. And the holes and allocations
should be disjoint.
It’s OK for allocations to abut each other, but holes must not abut. If there were abutting holes, then we
would not be able to make an accurate determination of whether an allocation fits inside an available hole.
You don’t have to check for this in Part One, but your functions in Part Two will have to be aware of this
rule.
For example, this shows a valid allocation:
1
Here, I’ve shown the adjoining allocations with different letters. The lists corresponding to this allocation
would be {(3, 3), (6, 4), (13, 5)} for the allocations, and {(0, 3), (10, 3), (18, 2)} for the holes.
I’ve written a function (validateAllocation(), described below) that you can use to check whether the
state of the holes and allocations list is valid and self-consistent.
Finding a region for an allocation of size n then requires us to look through the current-hole list for an entry
having a size value of at least n. The specific allocation algorithm we’re using (first-fit, best-fit, worst-fit)
determines how the choice is made. Create an enum AllocType with three values to keep track of the current
allocation strategy.
Important note: you don’t have to keep your lists in sorted order, unless you are graduate student or unless
you are doing the extra credit.
2.1 Data Structures
Here are data structures that you should use. Put these in a file dynalloc.netid.h:
// this represents a single record — either an allocation or
// a hole — in the allocations list or the holes list
typedef struct BlockListNodeStruct {
int size;
int start;
struct BlockListNodeStruct *next;
} BlockListNode;
// here are the two lists, along with the size of the “memory”
typedef struct {
int capacity;
BlockListNode *allocations;
BlockListNode *holes;
} AllocInfo;
// and this determines how a hole for an allocation is selected,
// in Part Two
typedef enum AllocTypeEnum {
ALLOC_BEST_FIT,
ALLOC_WORST_FIT,
ALLOC_FIRST_FIT
} AllocType;
2.2 Functions – Part One
2.2.1 Initialization
Write the following function to initialize your data structures:
void initializeAllocation(int capacity, AllocInfo *allocInfo)
In your instance of the AllocInfo structure, this will set the allocations list to NULL, set the capacity value
to the specified value, and create a single hole at location zero of size equal to capacity.
2
2.2.2 Creation, deletion, update
Write the following functions to create and delete allocations and holes. In all cases, you should assert if the
allocInfo parameter is NULL.
int addAllocation(int start, int size, AllocInfo *allocInfo)
This function will put a new entry in the allocations list, with the specified start and size. Return zero.
int deleteAllocation(int start, AllocInfo *allocInfo)
This will delete the allocation record starting at the specified start value from the holes list. Assert if
there is no allocation record starting at the specified start parameter value. Return zero.
int addHole(int start, int size, AllocInfo *allocInfo)
This will add a new record to the holes list. Return zero.
int deleteHole(int start, AllocInfo *allocInfo)
This will delete the hole record starting at the specified start value from the allocations list. Assert if
there is no hole record starting at the specified start parameter value. Return zero.
int shrinkHole(int requestSize, BlockListNode holeNode, AllocInfo allocInfo)
This will update the record for an existing hole (in order to make a subsequent allocation in that hole). The
function shrinks the specified hole from its start position, changing it so that the size is decremented by
the value of requestSize and the start is incremented by the value of requestSize. So for example, if the
hole in holeNode is (15, 8) and I call updateHole(4, holeNode, &info), then the size of the hole will be
reduced by 4, and the start of the hole will be set to 19, with the result that the updated hole will be (19, 4).
If the request parameter is either negative or is larger than the current size of the hole, you should assert:
this should never happen; and if it does happen, then there is something seriously wrong in your Part Two
code.
If the request parameter is exactly equal to the size of the hole, then you must delete the hole entirely.
Return zero from this function.
You should also assert if holeNode is NULL.
int expandHole(int newSize, BlockListNode holeNode, AllocInfo allocInfo)
This will update the record for an existing hole by enlarging it. The function expands the specified hole from
its start position, by setting the hole’s size to the newSize value. The start position remains unchanged.
Assert if the value of newSize is less than the current size of the hole. Assert it holeNode is HULL.
3 Testing Your Code
Get the file utilities.c from gitlab. This contains the following functions:
int validateAllocation(AllocInfo *allocInfo, int sorted)
During your initial development, call this function after every call to addHole() or deleteHole() or
3
updateHole(). This will make sure that your lists of allocations and holes are correct. The sorted parameter
should be 0. (If you are a graduate student, you will be maintaining sorted lists, and you should set the
sorted parameter to a nonzero value.)
void printAllocation(AllocInfo *info)
If the capacity is not too large (≤ 40), then this also prints out a ASCII depiction of the state of the
allocations and holes, like this:
numUsed = 19; numHoles = 3
fraction in use = 0.63; mean hole size = 3.67
A: (0, 3) (6, 6) (14, 5) (19, 4) (23, 1)
H: (3, 3) (12, 2) (24, 6)
x x x – – – x x x x x x – – x x x x x y y y y x – – – – – –
-
-
- h h h – – – – – – h h – – – – – – – – – – h h h h h h
Neighboring allocations are printed using different letters. This also prints some stats about the state of the
allocations and holes, which will be useful for Part Two.
And then get testBase.c. This contains three test functions that create various patterns of allocations and
holes and then call validateAllocation(). All of your tests should pass.
- h h h – – – – – – h h – – – – – – – – – – h h h h h h
-
- Part Two
Implement the two high-level allocation and deallocation functions that will use your base functions from
Part One.
4.1 Allocation
int allocateBlock(int size, AllocType allocType, AllocInfo *allocInfo)
Find and allocate a region of the specified size using the specified allocation type. Update the internal lists
of allocations and holes. If the request can be made (i.e., a free region of at least the specified size is found),
then return the start of the allocation. Otherwise, return -1.
If your list is not sorted by location, and you are using first fit, then just pick the first hole in your list,
starting at the beginning, that is sufficiently large for the desired allocation.
4.2 Deallocation
int deallocateBlock(int location, AllocInfo *allocInfo)
Release the allocation specified by location. The location value will be the starting index of the allocation
and will be the value that was returned by allocateBlock(). If the location value does not actually
represent a current allocation, then assert. Otherwise, update the internal lists of allocations and holes and
return 0.
This function must check the list of holes and take one of four actions
• if there is no hole to the left or to the right of the allocation you are deleting, then delete the allocation
and add a new hole of the same size and at the same starting index as the allocation you are deleting
4
• if there is a hole to the left but no hole to the right, then delete the allocation and expand the hole on
the left to cover the space that the allocation was using
• if there is not a hole to the left but is a hole to the right, then delete the allocation and replace the
hole on the right with a new hole that covers the full space of the allocation you are deleting and the
hole on the right
• if there is a hole on the left and on the right, then delete the allocation, delete the hole on the right,
and expand the hole on the left to cover the space that the deleted allocation and the hole on the right
were using
The above two functions represent the“public”interface to the allocation system.
4.3 Part Two – Testing
I’ve created two tests in testFulll.c: testFirstFit() and testBestFit(). You should also test your code
by making and releasing allocations and verifying the state of your lists. - What to Submit
For Part One, put your functions in dynalloc-one.netid.c. Put your structures in dynalloc.netid.h.
Submit just these two files. Do not put a main() in the dynalloc-one.netid.c file that you submit.
For Part Two, put your functions in dyanlloc-two.netid.c. You’ll use the same dynalloc.netid.h from
Part One, so you don’t need to submit it again (unless you’ve changed it). - Graduate Students
Students taking the course for graduate credit, and undergrads who would like a little extra credit: do the
following.
6.1 Sorted lists
Maintain your lists in sorted order (sorted by start value). This will make searching through the lists more
efficient.
6.2 Simulations
Simulate the three allocation strategies (first-fit, best-fit, worst-fit). Here is pseudocode describing how to
do this:
// initialize the elements; use for example CAPACITY = 2000 elements
// pick a mean request size; for example M = 25
// do some initial allocations; for example CAPACITY / M
// pick N, the number of allocation/deallocation cycles; for example, N = 1000
failureCount = 0
for i = 1 to N {
5
randomly pick one of the allocations and deallocate it
pick r, a uniformly distributed random number in the range [1, 2*M]
allocate a block of size r
validate the allocation structures by calling validateAllocation()
if the allocation succeeds
keep track of it
else
increment failureCount
print stats, for example fraction of elements in use and mean hole size
}
Do these simulations. Plot the results across the cycles. Here’s an example of my results for fraction of
memory in use:
Do the same for mean hole size. Plot also #cycles vs. #allocation failures. In each case, you should see that
worst fit is worse than the other two strategies.