Part 3 of 7 · 2 min read
External fragmentation
In plain words: The failure in the last example has a name. External fragmentation is the condition in which the total free memory is large enough for a request, but it is split among holes that are each too small. The memory is not full, yet the request fails.
How bad does it get? A simulation gives a feel for it. The memory has 10,000 units. Each request asks for a random size between 10 and 100 units. The simulation frees a random block when the memory is above a target load, and also with probability 0.3 at other times, so the load stays near the target. Each rule ran 200,000 steps with three random seeds, and the numbers below are averages over the second half of each run. The workload is made up, and other workloads give different numbers.
| Target load | Rule | Holes | Blocks | Share of free memory in holes under 100 units | Requests that failed |
|---|---|---|---|---|---|
| 80% | First fit | 68.5 | 145.3 | 65% | 0.0% |
| 80% | Best fit | 59.8 | 144.8 | 41% | 0.0% |
| 80% | Worst fit | 113.3 | 230.4 | 100% | 52.2% |
| 90% | First fit | 110.6 | 251.4 | 100% | 47.7% |
| 90% | Best fit | 68.1 | 169.7 | 87% | 5.7% |
| 90% | Worst fit | 121.3 | 247.9 | 100% | 56.9% |
The column "share of free memory in holes under 100 units" counts free space that is too small for the biggest requests (100 units). In these runs, best fit kept the memory usable the longest, and worst fit did badly. At 90% load, first fit failed nearly half of the requests, although about 1,000 units were free. The ranking depends on the workload, and a different mix of sizes can favour another rule. The common lesson is that a contiguous scheme degrades as load rises.
External fragmentation
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.
Example: at 90% load, first fit failed 47.7% of the requests in the simulation while about a tenth of the memory was free.
Check yourself: 1. Why can a request fail although the total free memory is larger than the request? 2. Which rule did best in the simulation at 90% load? 3. Why should these numbers not be trusted as a ranking for every system?