CSE Roadmap

Core tier · about 5 hours · 7 parts

Part 6 of 7 · 3 min read

Compaction

Compaction, and the way out

In plain words: If external fragmentation is the problem, one cure is to gather the holes into one. Compaction moves all used blocks to one end of the memory, so that the free memory forms a single large hole. It is possible with base and limit registers (page 1): the kernel copies a process's memory to a new place, and sets a new base. The process does not notice, since its logical addresses stay the same. But the process must be stopped while it moves, because it must not run while its memory is being copied.

The cost is the cost of copying. On the test machine, copying 512 MiB inside memory took 0.064 s, or 7.8 GiB per second (the first copy took 0.379 s, since the pages were touched for the first time). At that speed, compacting 1 GiB of live data takes about 0.13 s, during which the moved processes cannot run. For a machine with 64 GiB of memory and a lot of live data, a full compaction can take seconds. That is too long to do often, and the kernel must also choose which blocks to move.

Other cures exist, and all have costs. Swapping (Level 7) writes processes to disk to make room. Segmentation (page 6) uses several smaller regions per process and reduces the problem. The cure that general-purpose operating systems chose is to remove the requirement of a contiguous region. If a process may be spread over many small, equal pieces anywhere in the memory, external fragmentation is gone, and internal fragmentation is under one piece per region. That is paging, and page 3 explains it.

Compaction

Compaction is the moving of used blocks of memory together, to join the scattered holes into one large free block; it needs relocation hardware such as a base register, and the moved processes must be paused during the copy.

Example: copying 1 GiB of live data at 7.8 GiB per second takes about 0.13 s, during which the owners of that data cannot run.

Interview angle

"What is the difference between internal and external fragmentation?" Internal waste is inside an allocated block, for example the unused end of a 4 KiB page. External waste is between blocks: free holes that are too small to use. Add that paging removes the external kind and limits the internal kind to less than a page per region.

Check yourself: 1. Why does compaction need relocation hardware? 2. Why can the process not run while it is being moved? 3. What property of paging removes external fragmentation?

Words you will meet

Word Meaning
Hole A contiguous block of free memory
First fit Take the first hole that is big enough
Best fit Take the smallest hole that is big enough
Worst fit Take the largest hole
External fragmentation Free memory split into holes too small to use
Internal fragmentation Unused space inside an allocated block
50-percent rule In steady state, holes are about half the number of blocks
Compaction Moving blocks together to merge the holes

Quick notes

  • A hole is a contiguous block of free memory between used blocks; a request can be placed only inside a single hole, never across two, even when they are neighbours with a used block in between.
  • External fragmentation is the waste of memory that lies outside the allocated blocks, in free holes that are individually too small to satisfy a request, although their total size would be enough.
  • Internal fragmentation is the waste of memory inside an allocated block: the part of a block, given to a process because the allocation unit is larger than the request, that the process does not use and nobody else can use.
  • The 50-percent rule states that, for a first-fit allocator in a steady state, the number of holes is about half the number of allocated blocks; if holes are as large.
  • Compaction is the moving of used blocks of memory together, to join the scattered holes into one large free block; it needs relocation hardware such as a base register, and the moved processes must be paused during the copy.