Dynamic Storage Allocation on a Multiprocessor

Many modern programming languages allocate storage from the heap. The dynamic storage allocator allocates and deallocates objects from the heap. Heap objects have indefinite lifetimes. Space occupied by a heap object is not reclaimed until the dynamic storage allocator is explicitly instructed to deallocate the object. The efficiency of the dynamic storage allocator constitutes a crucial component of system performance. A good dynamic storage allocator should utilize storage efficiently and satisfy requests in as few instructions as possible. A dynamic storage allocator on a parallel machine should have the ability to process several requests concurrently. This thesis studies algorithms for efficiently managing heap storage on high-performance computers. Heap management algorithms are evaluated based on execution speed, parallelism, and memory utilization. Quick fit generally outperformed all other previously published algorithms. Maximum memory utilization was achieved by a best fit algorithm. The best fit algorithm was significantly slower than quick fit, however. Quick fit achieves fast allocation by segregating small free blocks based on size. A single free list is used for large blocks. Quick fit is fastest when the vast majority of requests are for small blocks. Quick fit slows down as the percentage of requests for large blocks increases. We have developed three new algorithms which are faster than quick fit when the percentage of requests for large blocks is high. Multiple free list fit I (MFLF I) uses multiple free lists for large blocks. Modified quick fit uses a concurrent B-tree for large free blocks. Multiple free list fit II (MFLF II) uses multiple free lists and a concurrent B-tree for large free blocks. Dynamic storage allocators are compared using simulations and real implementations. Quick fit and MFLF I have been implemented on the Monsoon multiprocessor to support the execution of Id programs. This thesis also studies concurrent algorithms on both basic B-trees and $B\sp+$-trees. We obtained the best performance on basic B-trees using an optimistic, top-down restructuring algorithm. Maximum throughput on $B\sp+$-trees was obtained using B-link algorithms. However, B-link algorithms cannot easily be adapted to basic B-trees. (Copies available exclusively from MIT Libraries, Rm. 14-0551, Cambridge, MA 02139-4307. Ph. 617-253-5668; Fax 617-253-1690.)