Memory allocation and deallocation is done through malloc and free in C language.
Section 8.7 of the C Programming Book [1] shows an implementation of the malloc and free functions. Memory is implemented using 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. The implementation is simple but extremely inefficient. The memory allocation algorithm used is the simple first fit algorithm.
Doug Lea describes more efficient implementation of malloc in his article [2]. Memory is implemented using 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. The memory allocation algorithm is the quick fit algorithm.
(a) Implement functions mod_malloc and mod_free by modifying K & R version by using Doug Lea's data structure and a simple best fit allocation algorithm. This implementation should not call malloc or delete functions internally. Implement test_storage_allocator.c
which outputs CPU time and memory heap size that the storage allocator uses; and compare performances of mod_malloc and mod_free with malloc and free. Use this sequence of instructions as test case where "M x" and "F y" imply "allocate x words" and "deallocate y"
words, respectively: M 10000, M 1000, M 500, M 1200, M 400, F 1000, M 200, F 500, F 1200,M 1100, M 100. A word is 4 bytes.