Assignment 10, due Apr 28
Part of
the homework for 22C:50, Spring 2003
|
Always, on every assignment, please write your name legibly as it appears on your University ID and on the class list!
Do problems 1 and 9 from the end of Chapter 13 (1 point each).
Do problems 6 and 9 from the end of Chapter 14 (1 point each).
In C and C++, you can allocate an instance of any data type (suppose the type name is mytype) as follows:
mytype * p; /* p is an uninitialized pointer */ p = (mytype *)malloc( sizeof( mytype ) );
Later, you can dispose of the allocated instance as follows:
free( p );
You can look these up in the on-line Unix manual (using the man command), or look in Kernighan and Ritchie.
Your assignment is to write equivalent code, but call your allocate routine myalloc and your deallocate routine myfree; additional details will be available soon. You may borrow ideas from the code in Kernighan and Ritchie, but you may not use their algorithm. Instead, use the Fibonacci Buddy System.
Because it's a buddy system, you've got to pass the size of the block to myfree just like you passed the size to myalloc! You can make a heap from an array of 10,000 bytes (char heap[10000]). You will most likely want to write a bit of code called heap_init(). Your allocate routine should return NULL when it can't satisfy an allocation request. Note that you can and should write simple test programs, but that a test program that exercises your heap fairly thoroughly is available at http://homepage.cs.uiowa.edu/~dwjones/syssoft/hw/alloctest.c
For Extra/Honors Credit: Instrument your heap with a routine called snapshot() that counts the free blocks of each available size and reports: a) The total number of free blocks, b) the total amount of memory allocated to users (the heap size minus the total of all free blocks), and c) the total amount of memory users have requested (the sum of allocation requests minus the sum of all deallocation requests). Also output the utilizaton of the allocated memory (c/b).