Part 4 of 7 · 2 min read
Internal fragmentation
In plain words: The second kind of waste lies inside the blocks. Suppose the memory is divided into fixed units of 4 KiB (4,096 bytes), and a request is rounded up to a whole number of units. A request for 4,097 bytes gets two units, 8,192 bytes, and 4,095 bytes of the second unit are wasted. That waste is internal fragmentation: it is inside an allocated block, and nobody else can use it.
On average, how large is it? If request sizes are spread evenly, the last unit is on average half full, so the waste is about half a unit per block. A test with 1,000,000 random sizes between 1 and 100,000 bytes gave an average waste of 2,067 bytes per request with 4 KiB units. Half of 4,096 is 2,048, and the measured value is close to it.
The two kinds of waste pull in opposite directions:
| Small units | Large units | |
|---|---|---|
| Internal fragmentation | Small (about half a unit per block) | Large |
| External fragmentation | Small, since units fit anywhere | Large |
| Bookkeeping | More units to track | Fewer |
With variable-sized blocks, there is no internal waste, but external waste grows. With fixed-sized units, the external waste disappears, since any free unit fits any request, and the internal waste is limited to less than one unit per block. This is the idea behind paging (page 3), where the unit is the page, usually 4 KiB.
Internal fragmentation
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.
Example: a request for 4,097 bytes served in 4 KiB units takes 8,192 bytes and wastes 4,095.
Check yourself: 1. How many bytes are wasted if a request of 10,000 bytes is served in units of 4,096 bytes? 2. What is the average waste per block, if sizes are spread evenly and the unit is 4,096 bytes? 3. Which kind of fragmentation disappears when all units have one size?