代写CS201程序、代写c/c++编程

日期：2021-11-19 09:37

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.

4 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.

5 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).

6 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.

6