LARA

Memory Fragmentation

Suppose we have only 320 words of memory

x1 = alloc(32)
x2 = alloc(32)
...
x10 = alloc(32)
free(x1, 32)
free(x3, 32)
free(x5, 32)
free(x7, 32)
free(x9, 32)
// now have 160 bytes of free memory
z = alloc(50) // fails!

Some steps to address this:

  • always merge adjecent blocks (e.g. suppose there was free(x4,32) )
  • not sufficient in general
  • in general must do compaction (move blocks to put them together)