Worst Fit Memory Allocation

Worst Fit Memory Allocation is a classic greedy strategy from operating systems. When several free memory blocks could hold a process, Worst Fit deliberately picks the largest one — the opposite of being frugal — so that the leftover gap stays big enough to be useful later.

The slow way first

You could try to be clever: sort blocks, build a heap, or rebalance after every placement. But for a single placement the rule is simple — among all blocks that fit, take the biggest. A plain scan over every block finds that biggest-fitting block directly, no extra structure needed.

The question to ask: given this one process, which open hole leaves me in the best shape afterward? Worst Fit answers "the biggest hole," reasoning that a big leftover is more reusable than a tiny sliver.

The idea: pick the biggest hole

Walk the processes in order. For each process of size, scan every block and remember the index of the largest block whose free size is at least size. If you found one, subtract size from it (that block now has a smaller leftover) and record the index. If no block was big enough, record -1.

The key insight: choosing the largest block (not the first or the tightest) keeps the remaining gaps spread out and large, which tends to leave room for future processes.

Walk through it

Step through the animation. The top row holds free blocks 100, 500, 200; the bottom row holds processes 212, 417, 112. Process 212 takes the largest block (500 → 288). Process 417 finds the largest remaining hole is only 288, which is too small, so it is rejected. Process 112 again takes block 1 (288 → 176).

Pseudocode

placement = empty list
for each process size in procs:
    best = -1                              # index of best block so far
    for each block index j:
        if blocks[j] >= size and (best is -1 or blocks[j] > blocks[best]):
            best = j                       # a larger fitting block
    if best is not -1:
        blocks[best] = blocks[best] - size # shrink the chosen block
    append best to placement
return placement

The Python solution

def worst_fit(blocks, procs):
    placement = []
    for size in procs:
        best = -1
        for j in range(len(blocks)):
            if blocks[j] >= size and (best == -1 or blocks[j] > blocks[best]):
                best = j
        if best != -1:
            blocks[best] -= size
        placement.append(best)
    return placement

• placement collects the chosen block index for each process (-1 means rejected).
• For every process we reset best = -1, meaning "nothing chosen yet."
• The inner loop scans all blocks. A block is a candidate only if blocks[j] >= size (it can hold the process).
• Among candidates we keep the one with the largest free size: best == -1 or blocks[j] > blocks[best].
• If a block was chosen we shrink it with blocks[best] -= size; otherwise best stays -1.

Complexity

We use only a couple of variables beyond the inputs, so extra space is O(1). With a max-heap of block sizes you could speed the per-process pick to O(log b), but the plain scan is simplest and clear.

When this pattern shows up

Practice