CSE Roadmap

Core tier · about 5 hours · 7 parts

Part 5 of 7 · 2 min read

The 50-percent rule

In plain words: A well-known result, from Knuth's study of first-fit allocation, says that in a steady state the number of holes is about half the number of allocated blocks. It is called the 50-percent rule. The reason is that a block next to a used block on one side and a hole on the other does not create a new hole when it is freed, while a block with used neighbours on both sides does. Only about half of the freed blocks find used blocks on both sides.

The simulation of section 2 gives a check. The ratio of holes to blocks in each row was:

Load First fit Best fit Worst fit
80% 0.47 0.41 0.49
90% 0.44 0.40 0.49

All values lie between 0.40 and 0.49, close to the rule of one half. For 1,000 blocks, expect about 500 holes (the simulation gave 400 to 490).

The rule also gives a rough size for the loss. If an average hole were as large as an average block, then N blocks would come with about 0.5 N blocks' worth of free holes, and the holes would make up 0.5 N out of 1.5 N, which is one third of the memory. OSC states it in this form. The simulation gave less loss, since its holes were on average smaller than its blocks. Use the rule as an estimate of the shape of the problem, and not as an exact number.

50-percent rule

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 as blocks, about one third of the memory is then lost to fragmentation.

Example: a memory with 600 allocated blocks is expected to have about 300 holes.

Check yourself: 1. How many holes does the rule predict for 400 allocated blocks? 2. What ratio of holes to blocks did best fit give at 90% load? 3. Why does a freed block not always create a new hole?