Background:
The standard C library routines malloc() and free()
are used to manage the heap for dynamic allocation of objects used by
C programs. They sit under the object model of C++ as well. Look
them up online using the command man malloc.
In the next machine problem, you will be implementing your own heap,
implementing mymalloc() and myfree(), with user
interfaces compatible with the predefined heap manager. For this problem,
implement these two routines as stubs, where each operates by calling the
corresponding built-in routines. Your allocate routine will occasionally
return NULL when there is insufficient memory in the heap to allocate
new memory.
To test a heap manager, it is useful to have a source of random numbers.
The standard C library contains a good random number generator. Look
it up online using the command man random.
The Assignment:
-
Write a program to test your heap manager (or, through the stub, the built-in
heap manager). This program should make a sequence of 10,000 random allocate
and deallocate calls. The deallocate calls should deallocate blocks of memory
already allocated. Block sizes should be random. Since it is illegal to
deallocate memory that has not previously been allocated, and since it is
illegal to deallocate a block twice, your program must maintain a data
structure to record what memory it has allocated. You are free to design
your own data structure for this.
-
You are testing a heap with a capacity of 10,000 bytes. Note that this is
not a power of two. Your test program should, in the steady state, have
an averate of 100 allocated blocks of memory. The average block size should
be 100 bytes, so that the average demand on the heap should attempt to fill
it.
-
Your program should keep statistics on the average block size actually
allocated and the average number of blocks actually allocated
(because your heap will be able to fail to allocate a block in the
event that the heap is full). It should also maintain statistics on the
average number of allocation requests that fail.
-
Submit your tested work using the
icon
submit mechanism.