Pointer Walk

Memory Allocation

First-fit, best-fit, worst-fit and next-fit place the same blocks into one strip of memory. One leaves the most unusable slivers.

Operating SystemsIntermediate9 min read

Handing out memory

Programs ask for memory all the time: "I need room for 200 bytes", "now 4,000", "I am done with the first one". Each request must be given a stretch of memory that is in one piece, and each freed block becomes available again.

The component that manages this is the allocator. Its job sounds like bookkeeping. The difficulty appears after a while, when blocks have been freed in a different order from the one they were handed out in, and the free space is no longer one big region. It is a scatter of gaps between blocks still in use.

A new request has to go into one of those gaps. Which one?

Four ways to choose a gap

Pick an allocator and watch the same sequence of requests.

First fitInteractive
Allocator

Coloured: in use. Grey: free. Red: a free gap too small to be much use.

Start. Scan from the start and take the first gap that is big enough. An empty strip of memory, 32 units long. Programs will ask for blocks of different sizes and give some back.

Free in total
32
Largest gap
32
Slivers (gaps of 1 or 2)
0
Requests failed
0

First fit

Scan from the beginning and take the first gap that is big enough.

First fitInteractive

Coloured: in use. Grey: free. Red: a free gap too small to be much use.

Start. Scan from the start and take the first gap that is big enough. An empty strip of memory, 32 units long. Programs will ask for blocks of different sizes and give some back.

Free in total
32
Largest gap
32
Slivers (gaps of 1 or 2)
0
Requests failed
0

It is quick, because it stops at the first match. It tends to pack small blocks near the start of memory and leave larger gaps further along.

Next fit

Like first fit, but continue searching from where the last search ended and wrap around at the end.

It spreads allocations around the whole of memory, and avoids re-scanning the crowded start every time. The cost is that it chops into the big gaps at the far end sooner.

Best fit

Look at every gap and take the smallest one that is big enough.

It sounds like the obvious winner: waste as little as possible each time.

Best fitInteractive

Coloured: in use. Grey: free. Red: a free gap too small to be much use.

Start. Check every gap and take the smallest one that is big enough. An empty strip of memory, 32 units long. Programs will ask for blocks of different sizes and give some back.

Free in total
32
Largest gap
32
Slivers (gaps of 1 or 2)
0
Requests failed
0

Watch the red cells. A tight fit is almost never an exact fit. Each time, a tiny leftover remains: one or two units, too small for nearly any request. Best fit is very good at producing these slivers.

Worst fit

Look at every gap and take the largest one.

The reasoning: after a big gap is cut, what remains is still a useful size. No slivers.

Worst fitInteractive

Coloured: in use. Grey: free. Red: a free gap too small to be much use.

Start. Check every gap and take the largest one. An empty strip of memory, 32 units long. Programs will ask for blocks of different sizes and give some back.

Free in total
32
Largest gap
32
Slivers (gaps of 1 or 2)
0
Requests failed
0

The flaw shows up at the end. By always cutting into the largest gap, it destroys the large gaps. When a big request arrives, there is plenty of free memory in total, and no single gap big enough to hold it.

Fragmentation

Both failures have the same name.

External fragmentation is free memory that cannot be used because it is in pieces. In the worst-fit run, the last request needed 5 units, 9 were free, and it failed, because those 9 were split into gaps of 4, 4 and 1.

Example

Free, and still not available

Think of a car park with ten empty spaces, each between two parked cars. There is room for ten cars. There is no room for one bus.

Memory cannot simply be shuffled together to close the gaps, at least not in languages like C: programs hold the addresses of their blocks, and moving a block would leave those addresses pointing at the wrong place.

There is no winner

In this sequence, first fit comes out best, and it usually does well in practice. But the sequence was chosen to show each strategy's typical weakness, and a different sequence ranks them differently.

AllocatorSpeedTypical weakness
First fitFast: stops at the first matchClutter builds up at the start
Next fitFastBreaks up large gaps early
Best fitSlow: checks every gapLeaves many tiny, useless slivers
Worst fitSlow: checks every gapUses up the large gaps

What real allocators do

Real ones avoid the search altogether with a different idea: keep separate pools for different sizes.

  1. Round each request up to a standard size

    For example 16, 32, 64, 128 bytes, and so on.

  2. Keep a list of free blocks for each size

    A request for 50 bytes takes a block from the 64-byte list. No searching.

  3. When a block is freed, put it back on its list

    The next request of that size reuses it exactly.

Because every block in a pool is the same size, a freed one always fits the next request perfectly. The gaps problem disappears. The price is internal fragmentation: a 50-byte request sitting in a 64-byte block wastes 14 bytes inside it. That waste is small and predictable, which is a good trade.

Languages with garbage collection can go further. Since the runtime knows where every reference is, it can move the live blocks together and fix up the references, leaving all free memory in one piece. This is called compaction.

Key takeaways

  • An allocator hands out contiguous blocks of memory and takes them back.
  • As blocks are freed, free memory breaks into gaps, and each request must choose one.
  • First fit takes the first gap that fits. Best fit takes the tightest. Worst fit takes the largest.
  • Best fit leaves tiny slivers. Worst fit destroys large gaps. Both are forms of fragmentation.
  • Real allocators mostly use pools of fixed sizes, trading a little wasted space for no searching.

Your progress

Check your progress

0%

  1. Read the page50% of this page

    When you have gone through the page and its animations, tick it off.

  2. Take the quiz50% of this page

    7 questions, from easy to hard. Take it as often as you like: the questions change, and only your best score counts.

Saved on this device only. See all your progress