Operating systems

Free space management

Prashanth L.A.


Lecture 17

So far


A detour

Low-level mechanisms

A 30-byte heap

Free list

Splitting and coalescing

Splitting on a request for 1 byte

Free(10) ignoring the split leads to


Basic strategies for managing free space

Strategy Description
Best Fit Find free chunks that are bigger than the request and return the smallest
Worst Fit Find the largest free chunk, allocat and keep the remaining chunk on free list
First Fit Find the first chunk that is big enough, remaining free space goes to the list
Next Fit Find the first chunk that is big enough for the request; Searching from the point where one was looking last


Free list

Best-fit for size 15

Worst-fit for size 15

Tracking allocation size


Allocated region + header

Specific contents of the header

Heap allocation

Heap with one free chunk

Heap after an allocation for 100 bytes (+ 8 byte header)