The idea: one free list, four ways to pick a hole

With contiguous allocation, every request gets one unbroken range of addresses. Memory is then a row of used blocks with free gaps between them, called holes. The allocator keeps the holes on a free list, sorted by address. A request for n KB needs one hole of at least n KB. When several holes are big enough, a placement strategy picks one:

  • First fit: walk the list from address 0 and take the first hole that is big enough.
  • Next fit: the same, but start where the last search stopped. A rover pointer remembers that place, and the search wraps around at the end of memory.
  • Best fit: check every hole and take the smallest one that is big enough.
  • Worst fit: check every hole and take the largest one.
Five holes of 100, 500, 200, 300 and 600 KB in address order and a 212 KB request. First fit and next fit (rover at 0) take the 500 KB hole, best fit takes the 300 KB hole, worst fit takes the 600 KB hole. The 100 and 200 KB holes are too small.
The same 212 KB request lands in a different hole under each rule.

Reading the canvas

The four rows hold four copies of the same 2400 KB memory, one per strategy. Every action runs in all four rows at once. Grey blocks were there at the start (the OS and processes P1–P4), coloured blocks are your requests A, B, C…, green boxes are holes. During a search the holes a row checks turn yellow and the one it picks turns orange. Under each bar you see the free list as start:size pairs, the free total, the largest hole, and how many holes the row has checked so far. The dark blue tick on the next fit row is its rover.

Splitting and coalescing

A hole is rarely the exact size. The block takes the front of the hole and the rest stays on the list as a smaller hole: that is splitting. When a block is freed, it may touch a hole on the left, on the right, or both. The allocator then coalesces them into one hole, so the list never holds two holes side by side.

In Demo: free merges with free neighbours, freeing P2 (100 KB at 1000) joins the 500 KB hole before it and the 200 KB hole after it into one 800 KB hole at 500. Freeing P1 then joins 100 + 100 + 800 into 1000 KB at 300. Now a 900 KB request fits in every row; before the frees the largest hole was 600 KB.

Top: a 500 KB hole at 500 receives A, 212 KB; A takes 500 to 712 and a 288 KB hole stays at 712. Bottom: P2 at 1000 to 1100 lies between a 500 KB hole and a 200 KB hole; after the free the three become one 800 KB hole from 500 to 1300.
Splitting makes holes smaller; coalescing puts neighbours back together.

External fragmentation

After many requests and frees, free memory is spread over many small holes. A request can then fail although the free total is larger than the request: no single hole is big enough. This is external fragmentation. In Demo: enough free memory, no hole big enough, three 600 KB blocks fill memory, B is freed, and a 700 KB request fails in every row: 900 KB are free, but as holes of 600 and 300 KB. The strategy does not matter here; the shape of the free memory does.

For first fit, Knuth's analysis and simulations give the 50-percent rule: with N blocks in use, about N/2 holes exist on average. So up to a third of memory can be lost to holes too small to use.

First fit after the textbook demo: holes of 100, 176, 200, 300 and 183 KB, 959 KB free in total, but the largest hole is 300 KB, so a 426 KB request fails.
959 KB are free, yet a 426 KB request fails: no hole is big enough.

Which one is best?

None of them wins every time. Demo: textbook holes, four strategies is the classic exercise from Silberschatz: holes of 100, 500, 200, 300 and 600 KB, then requests of 212, 417, 112 and 426 KB. Only best fit places all four; first fit, next fit and worst fit cannot place the 426 KB request although 959 KB are free. In Demo: best fit leaves a sliver the result turns around: with holes of 200 and 120 KB and requests of 110, 120 and 90 KB, best fit puts 110 KB into the 120 KB hole and leaves a useless 10 KB sliver, so the last request fails there and only there.

StrategyHoles checked per requestWhat it tends to leaveDemo numbers
First fituntil the first fitsmall slivers near low addresses, which every later search walks pasttextbook: 14 holes checked, 426 KB fails
Next fituntil the first fit, from the roverallocations spread over all of memory; often more fragmentation than first fittextbook: 12 checked, 426 KB fails
Best fitall of themvery small sliverstextbook: 20 checked, all placed; sliver demo: 90 KB fails
Worst fitall of themmedium holes, but the big holes are gone soontextbook: 20 checked, 426 KB fails

Simulations reported in the textbooks find first fit and best fit better than worst fit in both time and memory use. First fit and best fit use memory about equally well, and first fit is faster. Demo: next fit starts where it stopped shows the difference between the two "first that fits" rules: after A takes 450 KB of the 500 KB hole, first fit puts the 80 KB request back at address 300 and the 30 KB one into the 50 KB rest, leaving two 20 KB slivers. Next fit goes on from its rover and places them at 1100 and 1180.

Real allocators avoid the long walks. They keep segregated free lists, one list per size class, so a best-fit search only looks at holes of about the right size. glibc's malloc works like that, see glibc vs jemalloc vs tcmalloc. The Linux kernel uses power-of-two blocks instead, which makes coalescing cheap, see The Buddy Allocator.

What the page leaves out

Compaction, which slides blocks together to merge all holes (see Paging vs Segmentation); paging, which removes external fragmentation by using fixed-size frames; the block headers and boundary tags that a real allocator stores in memory to find neighbours in O(1); rounding requests up to an alignment, which adds internal fragmentation; keeping a hole at the end when the rest is too small to be worth listing; and size-class lists. Placement here is always at the start of the hole.

On the mind map

Open the Operating Systems mind mapOperatingSystemsBoot and program start: from power on to main()Boot and program startProcesses and the kernel: how user code talks to the kernelProcesses and the kernelInterrupts and devices: hardware interrupts the CPUInterrupts and devicesScheduling and deadlock: who runs next, who gets whatScheduling and deadlockVirtual memory: every address is translatedVirtual memoryPhysical memory: who gets which bytes of RAMPhysical memoryFiles and storage: from open() down to the diskFiles and storageDisks and RAID: blocks down to platter or flashDisks and RAIDIsolation and security: limit what a process can doIsolation and securityStack vs heap in CStack vs heap in Cframes pop on return, malloc needs freeC++ PointersC++ Pointersp holds an address; p + 1 adds sizeofStruct paddingStruct paddingLargest alignment first leaves no gapsEndiannessEndiannessx86 stores the low byte firstBuddy allocatorBuddy allocatorsplit in halves, find the buddy with XORFit Strategiesfirst, next, best, worst: none always winsReclaim and OOM killerReclaim and OOM killerkswapd reclaims, then the OOM killerSlab allocatorSlab allocatorkmalloc: per-CPU freelists of fixed sizesmalloc vs jemalloc vs tcmallocmalloc vs jemalloc vs tcmallocper-thread caches avoid arena lock fightsSwap out and swap inSwap out and swap inCold anon pages go to disk, fault backOpen the Operating Systems mind mapOperating Systemswho gets which bytes of RAMPhysical memoryStack vs heap in CStack vs heap in Cframes pop on return, malloc needs freeC++ PointersC++ Pointersp holds an address; p + 1 adds sizeofStruct paddingStruct paddingLargest alignment first leaves no gapsEndiannessEndiannessx86 stores the low byte firstBuddy allocatorBuddy allocatorsplit in halves, find the buddy with XORFit Strategiesfirst, next, best, worst: none always winsReclaim and OOM killerReclaim and OOM killerkswapd reclaims, then the OOM killerSlab allocatorSlab allocatorkmalloc: per-CPU freelists of fixed sizesmalloc vs jemalloc vs tcmallocmalloc vs jemalloc vs tcmallocper-thread caches avoid arena lock fightsSwap out and swap inSwap out and swap inCold anon pages go to disk, fault back
This page on the Operating Systems mind map · 64 pages in 9 branches · open it to see the whole map and test yourself in recall mode.