Dynamic Allocation Strategies
You’ll do simulations of best- t, worst- t, and first- t dynamic-allocation strategies.
To accomplish this, you’ll do random allocation of groups of elements of a nite-capacity resource. This will model, for example, the allocation of pages from virtual memory or sectors from a hard-disk drive. You need to keep track only of the size and location of each allocation.
A straightforward way to think about this is as an array of fixed sizes 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.
Current Allocations and Holes
You’ll maintain two lists: the current allocations, and the current holes. Each list will consist of nodes having (size, location) 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: f(2, 3), (9, 2), (14, 1), (16, 4)g, and
the current-hole list would have these entries: f(0, 2), (5, 4), (11, 3), (15, 1)g.
Finding a region for an allocation of size x then requires us to look through the current-hole list for an entry having a size value of at least x. The specific allocation algorithm we’re using (first- t, best- t, worst- t) determines how the choice is made. Create an enum AllocType with three values to keep track of the current allocation strategy.
Put your lists and the value that represents the total capacity in data structure AllocInfo.
Data Structures
Here are data structures that you should use. Put these in a file dynalloc.netid.h:
typedef struct BlockListNodeStruct {
int size;
int start;
struct BlockListNodeStruct *next;
} BlockListNode;
typedef struct {
int capacity;
BlockListNode *allocations;
BlockListNode *holes;
} AllocInfo;
typedef enum AllocTypeEnum {
ALLOC_BEST_FIT,
ALLOC_WORST_FIT,
ALLOC_FIRST_FIT
} AllocType;
Functions
Here are the key functions you should write:
int allocateBlock(int size, AllocType allocType, AllocInfo *allocInfo)
Find and allocate a region of the speci ed size using the speci ed allocation type. Update the internal lists of blocks in use and holes. If the request can be made (i.e., a free region of at least the speci ed size is found), then return the start of the allocation. Otherwise, return -1.
int deallocateBlock(int location, AllocInfo *allocInfo)
Release the allocation speci ed by location. (The location value will be the rst block 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 return -1. Otherwise, update the internal lists of blocks in use and holes and return 0.
The above two functions represent the \public" interface to the allocation system. You’ll also need lower-level functions to manage the lists of allocations and holes. I suggest the following:
int addHole(int start, int size, AllocInfo *allocInfo)
int deleteHole(int start, AllocInfo *allocInfo)
int addAllocation(int start, int size, AllocInfo *allocInfo)
And you’ll also have a way to update the record for an existing hole (in order to make a new allocation in that hole). A function like this:
void updateHole(int requestSize, BlockListNode *holeNode, AllocInfo *info);
It’s also useful to have a function to validate that the allocation structure is self-consistent (to make sure that the holes and in-use blocks are compliments of each other and partition the whole space). I’ve put code for this function in GitLab, in the le validateAllocation.c, under Homework/dynalloc:
int validateAllocation(AllocInfo *info);
Simulations
Simulate the three allocation strategies ( rst- t, best- t, worst- t). 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 {
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 mean hole size:
Do the same for the fraction of elements in use (you should see a smaller value for the worst- t strategy). Graduate students, and undergraduates for extra credit: collect some other statistics from the simulation (e.g., mean number of allocations that fail; variance of hole size). You should see that rst- t and best- t behave approximately the same, but that worst- t is worse.
Deliverables
Submit your dynalloc.netid.c and dynalloc. netid.h les. Submit also a short report showing plots of a fraction of elements in use and also mean hole size across the allocation/deallocation cycles.