Project: Dynamic Storage Allocation - malloc
Anyone who has done even the slightest amount of C programming would be familiar with standard library functions malloc and free, and perhaps even realloc and calloc. In the introductory computer systems (15-213) class that I took during the fall of my sophomore year, one of the later lab assignments was to write a dynamic memory allocation package consisting of the four functions mentioned above. See the lab write-up, or assignment specification, here.
Instead of using the sbrk function to grow the heap space for our program, we had to use a provided wrapper function named mem_sbrk so that the amount of space that our program used could be measured and graded. Other than that change, however, my code was expected to perform exactly like the library standard functions.
This lab was graded with two criterion: utility and throughput. Utility (or as I like to call it, "fragmented-ness") represents how much overall heap space was used for a given set of memory allocation function calls (including free calls). The less fragmented your heap space was, the better utility score you would receive. The second criterion was speed (in our case measured in kilo-operations / second).
If you're unfamiliar with dynamic memory allocation, think of an storage allocator as a manager for space in your wardrobe; whenever you give him a large coat he can find space to put place it in your closet, but at the same time if you give him a tiny pair of socks he can find a small space (that doesn't waste too much) to put that in as well. In my memory allocation package, I used an explicit linked list (linked list containing only the pointers to free spaces) as my primary data structure.
