First Fit Memory Allocation

First Fit Memory Allocation is a classic greedy problem from operating systems. Given a set of free memory blocks and a list of processes, you place each process into the first block that is large enough. It is the simplest of the memory-allocation strategies, and the greedy choice ("take the first thing that works") is the whole lesson.

The slow way first

There is not really a "slower" brute force here — First Fit is the simple approach. The naive instinct might be to first sort blocks, or to search for the best-sized block (that is a different strategy called Best Fit). First Fit deliberately skips all that cleverness: it just walks the blocks from the left and stops at the first one that fits.

The question to ask: for this one process, which block do I commit to? First Fit answers "the earliest one that has room" — a greedy choice made without looking ahead.

The idea: scan left, grab the first fit

For each process, scan the blocks left to right. The moment you hit a block whose remaining size is >= the process size, assign the process there and stop scanning for that process. Then subtract the process size from that block so the next process sees the reduced space. If you reach the end of the blocks with no fit, the process is unallocated (-1).

The key insight: we commit on the first fit and shrink that block immediately. Because earlier processes can shrink a block below a later process's need, First Fit can leave a process unallocated even when the total free memory across all blocks would have been enough.

Walk through it

Step through the animation. The bottom row is the processes; the top row is the free blocks. The scan pointer sweeps the blocks left to right for each process. P0 (212) skips block 0 (100) and lands in block 1 (500 → 288). P1 (417) fits nowhere — even block 1 has shrunk to 288 — so it stays -1. P2 (112) takes block 1 again (288 → 176).

Pseudocode

alloc = [-1, -1, ...]                 # one slot per process, default "no fit"
for each process p with size:
    for each block b from left to right:
        if blocks[b] >= size:         # first block large enough
            alloc[p] = b
            blocks[b] -= size         # shrink the block we used
            break                     # stop scanning for this process
return alloc

The Python solution

def first_fit(blocks, processes):
    alloc = [-1] * len(processes)
    for p, size in enumerate(processes):
        for b in range(len(blocks)):
            if blocks[b] >= size:
                alloc[p] = b
                blocks[b] -= size
                break
    return alloc

• alloc starts all -1, so any process that never finds a fit is already marked unallocated.
• The outer loop walks the processes in order — First Fit respects the given process order.
• The inner loop scans blocks left to right, which is what makes it "first" fit rather than "best" fit.
• if blocks[b] >= size is the greedy test: the first block with room wins.
• After assigning, blocks[b] -= size shrinks the block and break stops the inner scan so we never use a second block for the same process.

Complexity

With n processes and m blocks the scan is O(n·m). The extra space is O(n) for the allocation array. First Fit is prized for being fast and simple — no sorting, no global search — at the cost of sometimes wasting space (a problem called external fragmentation).

When this pattern shows up

Practice