M.Sc Thesis

M.Sc StudentBendersky Anna
SubjectOn the Limits of Partial Compaction
DepartmentDepartment of Computer Science
Supervisor PROF. Erez Petrank
Full Thesis textFull thesis text - English Version


Dynamic memory allocation is ubiquitous in today's runtime environments. Allocation and de-allocation of objects during program execution may cause fragmentation and foil the program's ability to allocate objects. Robson has shown that a worst case scenario can create a space overhead within a factor of log n of the space that is actually required by the program, where n is the size of the largest possible object. Compaction can eliminate fragmentation, but is too costly to be run frequently. Therefore, some memory managers choose to run the compaction method seldom. Many runtime systems employ partial compaction, in which only a small fraction of the allocated objects are moved. Partial compaction reduces some of the existing fragmentation at an acceptable cost. In this work we limit the memory that can be compacted, and study the effects of the compaction use on the required heap size. We provide lower and upper bounds on the heap size requirement, for any program and any memory manager that employs compaction. In another part of our work, we show tighter bounds for a specific popular memory management method - the segregated free list. This work provides the first rigorous lower and upper bounds on the partial compaction effectiveness in reducing fragmentation at a low cost.