Finding room for a program

Before paging, a process needed one contiguous block of physical memory. Everything hard about allocation shows up clearly in that simple model, and the same problems reappear inside every allocator today.

Choosing a hole

Given a list of free blocks and a request:

First fit: the first hole large enough. Fast, and leaves small fragments near the start.

Best fit: the smallest hole that works. Sounds right, and produces many unusably small leftovers.

Worst fit: the largest hole, so the remainder stays useful. Consumes big holes quickly.

In practice first fit is as good as best fit and faster, which is a useful reminder that the intuitive optimisation is not always one.

Two kinds of fragmentation

External: enough total free memory, no single block big enough.

[used 100K][free 40K][used 200K][free 30K][used 50K][free 50K]
request 100K -> fails, though 120K is free

Internal: memory handed out in fixed units, so the tail of the last unit is wasted. Ask for 33 bytes from a 64 byte class and 31 bytes are unusable.

Paging eliminates external fragmentation by removing the need for contiguity, and accepts internal fragmentation of at most one page per allocation.

Compaction

Move everything to one end and merge the free space. It works, it requires all addresses to be relocatable, and it is expensive: every byte is copied while nothing else runs. Rarely used in operating systems, common in garbage collectors, which have the same problem.

Inside the kernel

The kernel still allocates physically contiguous memory, for device buffers among other things, so these problems are current rather than historical.

Buddy allocator: memory in power of two blocks. A request is rounded up and a block split in half repeatedly until it fits; freeing merges with its buddy if that is also free. Fast and simple, with up to 50 percent internal waste in the worst case.

Slab allocator: caches of pre-built objects of one size. Allocating a frequently used kernel structure becomes taking one off a list, with no search and no fragmentation, and the object is already initialised.

malloc in your own programs faces the same problem one level up, which is why a long running process can hold a lot of memory the allocator cannot return to the system.