Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

On the Limits of Partial Compaction
event speaker icon
Anna Bendersky (M.Sc. Thesis Seminar)
event date icon
Wednesday, 30.12.2009, 14:00
event location icon
Taub 601
event speaker icon
Advisor: Prof. E. Petrank
Modern software employs dynamic memory allocation to support its memory needs. Allocation and de-allocation of memory create fragmentation: holes between the allocated objects in the memory may be too small to further satisfy future allocation. Fragmentation complicates memory allocation. Furthermore, fragmentation creates a space overhead sometimes making a program crash even though enough memory for allocation is available. Compaction defragments the memory by compacting all objects to the beginning of the memory. However, compaction is costly and practical systems prefer partial compaction when possible. In this work we investigate the effectiveness of partial compaction for reducing fragmentation. We show lower and upper bounds on the heap fragmentation, given a limit on the total space that exists simultaneously in the memory, a largest possible object size, and a fragmentation budget.