אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

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.