Memory Allocation (First, Next, Best & Worst Fit)

The problem

When processes start and finish, the free memory gets chopped into holes of different sizes scattered around RAM. A new process needs one contiguous block. If several holes are big enough, which one should it get?

Think of parking cars of different lengths along a street with gaps of different sizes. Squeeze a small car into the smallest gap that fits, and the long gaps stay free for buses. Park it in the first gap you see, and you may block the only spot a bus could use.

The four strategies

Whatever hole is chosen, the process takes what it needs from the start of the hole, and the rest stays free as a smaller hole.

The textbook example

Holes: 100K, 500K, 200K, 300K, 600K (in memory order). Processes: P1 = 212K, P2 = 417K, P3 = 112K, P4 = 426K.

Only best fit places all four processes in this example. With first fit, 959K is still free when P4 arrives, more than twice what it needs, but the largest hole is only 300K.

Fragmentation

• External fragmentation: the free memory is enough in total, but it is split into pieces that are each too small. That is what blocks P4 above. A famous rule of thumb, the 50-percent rule, says first fit can lose about one third of memory this way.
• Internal fragmentation: memory is handed out in fixed-size units, so a process gets slightly more than it asked for and the extra is wasted inside its block.

Two cures for external fragmentation:

1. Compaction: move the processes together so the holes merge into one. It works, but copying memory is slow.
2. Paging: split every process into small fixed-size pages that can go into any free frame, so memory no longer has to be contiguous. This is what modern operating systems do. See paging and page replacement.

Which strategy is best?

Simulations show first fit and best fit both beat worst fit at using memory, and first fit is usually faster because it stops early. Best fit tends to leave many tiny, useless holes. Worst fit destroys the big holes that big processes need. There is no strategy that wins on every input. Try Random in the 3D model and see.

Code

def allocate(holes, procs, strategy):
    holes = holes[:]                          # free hole sizes, in memory order
    result, last = [], 0
    for p in procs:
        fits = [i for i, h in enumerate(holes) if h >= p]
        if not fits:
            result.append(None)               # must wait
            continue
        if strategy == "first":
            i = fits[0]
        elif strategy == "next":
            i = next((j for j in fits if j >= last), fits[0])
        elif strategy == "best":
            i = min(fits, key=lambda j: holes[j])
        else:                                 # worst
            i = max(fits, key=lambda j: holes[j])
        result.append(holes[i])
        holes[i] -= p                         # the rest of the hole stays free
        last = i
    return result

holes, procs = [100, 500, 200, 300, 600], [212, 417, 112, 426]
for s in ("first", "best", "worst"):
    print(s, allocate(holes, procs, s))
# first [500, 600, 288, None]
# best  [300, 500, 200, 600]
# worst [600, 500, 388, None]

Common mistakes

• Thinking the whole hole is used up. Only the process’s size is taken, and the leftover stays free.
• Forgetting that holes keep their memory order for first fit and next fit.
• Mixing up best and worst fit: best fit takes the smallest hole that fits, worst fit the largest.
• Calling P4’s problem “not enough memory”. The total is enough; it is external fragmentation.