The purpose of this assignment is to help you understand how dynamic memory management works in C. It also will give you more opportunity to use the GNU/Unix programming tools, especially
You may work with one partner on this assignment. You need not work with a partner, but we prefer that you do. Your preceptor will help you find a partner if you cannot find one yourself.
If you work with a partner, then only one of the partners should submit files. Your
readme file, your
makefile, and your source code files should contain your name and your partner's name.
If you are an undergraduate student, then your partner should be another undergraduate student. If you are a graduate student, then your partner should be another graduate student.
Your partner should be from your precept. You may work with a partner from another precept only in the case of extraordinary circumstances, and with the permission of the pertinent preceptors. If you wish to work with a partner from another precept, then you must obtain permission from the pertinent preceptors no later than Sunday 12/5.
"Checking invariants" (as described below) is the "on your own" part of this assignment. That is, when doing that part you may consult with your partner, but must not consult with the course instructors, lab TAs, listserv, etc., except perhaps to clarify requirements. That part is worth 15% of this assignment.
A standard C programming environment contains four functions that allow management of the runtime heap:
realloc. Those heap management functions are used heavily in many C programs.
Section 8.7 of the book The C Programming Language (Kernighan and Ritchie) shows an implementation of the
free functions. That book section is on electronic reserve at Princeton's library; you can access it through Princeton's Blackboard system (http://blackboard.princeton.edu) by selecting the COS 217 course and clicking on E-Reserves. The key data structure in that implementation is a circular singly-linked list; each free memory "chunk" is stored in that list. Each memory chunk contains a header which specifies its size and, if free, the address of the next chunk in the list. Although elegant in its simplicity, that implementation can be inefficient.
The web page http://gee.cs.oswego.edu/dl/html/malloc.html (Doug Lea) describes how one can enhance such an implementation so it is more efficient. The key data structure is an array of non-circular doubly-linked lists, that is, an array of "bins." Each bin contains all free chunks of a prescribed size. The use of multiple bins instead of a single linked list allows
malloc to be more efficient.
Moreover, each memory chunk contains both a header and a footer. The header contains three fields: the size of the chunk, an indication of whether the chunk is free, and, if free, a pointer to the next free chunk in its bin. The footer contains two fields: the size of the chunk, and, if free, a pointer to the previous free chunk in its bin. That chunk structure allows
free to be more efficient.
A more thorough description of the pertinent data structures and algorithms will be provided in lectures and precepts.
You are given the interface of a
HeapMgr (heap manager) module in a file named
heapmgr.h. It declares two functions:
void *HeapMgr_malloc(size_t uiSize); void HeapMgr_free(void *pv);
You also are given three implementations of the
heapmgrgnu.cis an implementation that simply calls the GNU
freefunctions provided with our hats development environment.
heapmgrkr.cis the Kernighan and Ritchie implementation, with small modifications for the sake of simplicity.
heapmgrbase.cis an implementation that you will find useful as a baseline for your implementations.
Your task is to create two additional implementations of the
HeapMgr module. Your first implementation,
heapmgr1.c, should enhance
heapmgrbase.c so it is reasonably efficient. To do that it should use a single doubly-linked list and chunks that contains headers and footers (as described above, in lectures, and in precepts).
If designed properly,
heapmgr1.c will be reasonably efficient in most cases. However,
heapmgr1.c is subject to poor worst-case behavior. Your second implementation,
heapmgr2.c, should enhance
heapmgr1.c so the worst-case behavior is not poor. To do that it should use multiple doubly-linked lists, alias bins (as described above, in lectures, and in precepts).
HeapMgr implementations should not call the standard
HeapMgr implementations should thoroughly validate function parameters by calling the standard
HeapMgr implementations should check invariants by:
assert(HeapMgr_isValid())at the leading and trailing edges of the
Develop on hats, using
emacs to create source code and
gdb to debug.
/u/cos217/Assignment6 contains files that you will find useful:
heapmgrbase.c: as described above.
Chunkmodule used by
Chunkmodule that you may use in both implementations of your
testheapmgr.c: a client program that tests the
HeapMgrmodule, and reports timing and memory usage statistics.
bashshell scripts that automate testing. The
testheapscript assumes the existence of executable files named
testheapmgr2(as described below).
testheapmgr program requires three command-line arguments. The first should be any one of seven strings, as shown in the following table, indicating which of seven tests the program should run:
||LIFO with fixed size chunks|
||FIFO with fixed size chunks|
||LIFO with random size chunks|
||FIFO with random size chunks|
||Random order with fixed size chunks|
||Random order with random size chunks|
||Worst case order for a heap manager implemented using a single linked list|
The second command-line argument is the number of calls of
HeapMgr_free that the program should execute. The third command-line argument is the (maximum) size, in bytes, of each memory chunk that the program should allocate and free.
Immediately before termination testheapmgr prints to stdout an indication of how much CPU time and heap memory it consumed. See the
testheapmgr.c file for more details.
To test your
HeapMgr implementations, you should build two programs using these
gcc217 testheapmgr.c heapmgr1.c chunk.c -o testheapmgr1 gcc217 testheapmgr.c heapmgr2.c chunk.c -o testheapmgr2
To collect timing statistics, you should build five programs using these
gcc217 -O3 -D NDEBUG testheapmgr.c heapmgrgnu.c -o testheapmgrgnu gcc217 -O3 -D NDEBUG testheapmgr.c heapmgrkr.c -o testheapmgrkr gcc217 -O3 -D NDEBUG testheapmgr.c heapmgrbase.c chunkbase.c -o testheapmgrbase gcc217 -O3 -D NDEBUG testheapmgr.c heapmgr1.c chunk.c -o testheapmgr1 gcc217 -O3 -D NDEBUG testheapmgr.c heapmgr2.c chunk.c -o testheapmgr2
-O3 (that's uppercase "oh", followed by the number "3") argument commands gcc to optimize the machine language code that it produces. When given the
gcc spends more time compiling your code so, subsequently, the computer spends less time executing your code. The
-D NDEBUG argument commands gcc to define the
NDEBUG macro, just as if the preprocessor directive
#define NDEBUG appeared in the specified .c file(s). Defining the
NDEBUG macro disables the calls of the
assert macro within the
HeapMgr implementations. Doing so also disables code within
testheapmgr.c that performs (very time consuming) checks of memory contents.
Create additional test programs as you deem necessary. You need not submit your additional test programs.
makefile. The first dependency rule of the
makefile should build five executable files:
testheapmgr2. That is, the first dependency rule of your
makefile should be:
all: testheapmgrgnu testheapmgrkr testheapmgrbase testheapmgr1 testheapmgr2
makefile that you submit should:
We recommend that you create your
makefile early in your development process. Doing so will allow you to use and test your
makefile during development.
readme text file that contains:
heapmgr2.c, with tests
Worst, with call count 100000, and with maximum chunk sizes 1000 and 10000. Note that if the CPU time consumed is more than 5 minutes,
testheapmgrwill abort execution. To report the time and memory consumption, it is sufficient to paste the output of the
testheapscript into your
Submit your work electronically on hats via the command:
submit 6 heapmgr1.c heapmgr2.c readme makefile
We will grade your work on quality from the user's point of view and from the programmer's point of view. To encourage good coding practices, we will deduct points if
gcc217 generates warning messages. We also will deduct points if
splint generates warning messages that are not explained in your
readme file. But see the next section of this document regarding
From the user's point of view, your module has quality if it behaves as it should. The correct behavior of the
HeapMgr module is defined by the previous sections of this assignment specification. From the programmer's point of view, your module has quality if it is well styled and thereby simple to maintain. See the specifications of previous assignments for guidelines concerning style. Specifically, function modularity will a prominent part of your grade.
splint generates these warnings when it analyzes the
testheapmgr.c: (in function main) testheapmgr.c:118:21: Unrecognized identifier: sbrk Identifier used in code has not been declared. (Use -unrecog to inhibit warning) testheapmgr.c: (in function setCpuLimit) testheapmgr.c:223:4: Variable sRlimit used before definition An rvalue is used that may not be initialized to a value on some execution path. (Use -usedef to inhibit warning) testheapmgr.c:225:4: Unrecognized identifier: setrlimit testheapmgr.c:225:14: Unrecognized identifier: RLIMIT_CPU
Don't be concerned about those warnings; you need not explain them in your
splint generates them because it ignores the
#include of the
unistd.h file (and all such Unix-specific header files). The
sbrk functions are declared in that file, and the
struct rlimit type and
RLIMIT_CPU constant are defined in that file.
splint may generate a warning for each call of
sbrk in your your
heapmgr2.c files. Don't be concerned about those messages. You need not explain them in your