Module 02 • COSC240

Dynamic Partitioning & Free Space Management

Explore how operating system kernels track, partition, and coalesce variable-sized blocks of contiguous physical memory using bitmaps, linked lists, fit algorithms, and the binary buddy system.

1. Memory Tracking: Bitmaps vs. Linked Lists

When an operating system supports dynamic partitioning, the kernel must maintain an accurate bookkeeping model of which regions of physical memory are actively allocated to processes and which regions are available as free holes.

Approach A: Memory Management with Bitmaps

Under a bitmap representation, memory is divided into fixed allocation units (typically 4 bytes to several kilobytes). Each allocation unit corresponds to a single bit in a contiguous kernel bitmap array:

Bit value 0: The corresponding unit is free.
Bit value 1: The corresponding unit is occupied by an allocated process.

Bitmap Memory Overhead:

Let $U$ be the allocation unit size in bytes. The fraction of physical memory dedicated entirely to the bitmap is: $$ \text{Overhead Fraction} = \frac{1 \text{ bit}}{U \times 8 \text{ bits}} = \frac{1}{8U} $$

If $U = 4\text{ bytes}$ (32 bits), the bitmap consumes $\frac{1}{32} \approx 3.125\%$ of total RAM. If $U = 4\text{ KB}$, the bitmap consumes only $\frac{1}{32768} \approx 0.003\%$.

Defect: When an application requests a contiguous block of $k$ units, the kernel must scan the bitmap for a contiguous run of $k$ consecutive zero bits. Searching a bitmap for arbitrary-length bit runs is computationally slow ($\mathcal{O}(N)$ sequential bit-testing operations).

Approach B: Memory Management with Linked Lists

A more responsive design maintains a sorted, doubly linked list of allocated memory segments and free holes. Each node contains a descriptor tuple: $$ (\text{Type}, \text{Start Address}, \text{Length}, \text{Next Pointer}, \text{Prev Pointer}) $$ where $\text{Type} \in \{\text{P (Process)}, \text{H (Hole)}\}$.

[ P | 0 | 100K ] ↔ [ H | 100K | 40K ] ↔ [ P | 140K | 80K ] ↔ [ H | 220K | 60K ]

Advantage: Free holes are explicit entities that can be traversed directly. When a process terminates, updating the list and coalescing adjacent holes is a constant-time $\mathcal{O}(1)$ pointer operation.

2. Contiguous Memory Allocation Policies

When a process requests $K$ bytes of contiguous memory, the kernel scans the free list to select an appropriate hole. Five classic search heuristics govern this decision:

1. First-Fit

Scans the free list from the beginning and allocates the very first hole that is $\ge K$. The hole is split: the process takes what it needs, and the remainder stays on the list as a smaller hole.

Fastest lookup; fragments low memory

2. Next-Fit (Knuth)

Functions like First-Fit, but maintains a roving pointer. It begins searching from the location of the previous successful allocation, wrapping around to the start if needed.

Spreads allocations; breaks large high-memory holes

3. Best-Fit

Searches the entire list from start to finish to find the smallest hole that is $\ge K$. It attempts to minimize the leftover residual space.

Slowest search; produces tiny unusable slivers

4. Worst-Fit

Always allocates the largest available hole in memory, with the intuition that splitting a large hole leaves behind a substantial remainder that remains useful.

Destroys large contiguous blocks prematurely

Interactive Walkthrough: First-Fit vs. Best-Fit Allocation

Trace step-by-step how incoming allocation requests search available holes, split memory partitions, and impact fragmentation.

Step 1: Initial Free State. Contiguous physical memory pool (128 KB) contains two occupied processes and two free holes (Hole A: 20 KB, Hole B: 50 KB).

Phase: 1/4

Request: Incoming: 16 KB

Selected: None

Fragment: Minimal

POLICY:

Synchronized Visual Canvas — Memory Pool Map (128 KB)

🔍 What Is Happening

Process P3 arrives requesting 16 KB of contiguous memory. The allocator initiates free list traversal.

⚙ Why The System Does This

The choice of fit heuristic dictates whether the allocator prioritizes search latency or storage packing efficiency.

3. Hole Coalescing & Boundary Tags

When an active process terminates and relinquishes its memory block, the kernel must merge adjacent free holes to counter external fragmentation. There are exactly four boundary conditions that can arise when block $X$ is freed:

Neither neighbor is a hole: Block $X$ simply converts from type $P$ to type $H$. The total number of nodes in the free list increases by 1.
Left neighbor is a hole ($H + X$): Block $X$ is merged into the left hole. The left hole's length is incremented by $\text{Length}(X)$. Node count decreases by 1.
Right neighbor is a hole ($X + H$): Block $X$ is merged into the right hole. The right hole's starting address shifts down to $\text{Address}(X)$. Node count decreases by 1.
Both neighbors are holes ($H + X + H$): All three segments coalesce into a single large hole. Node count decreases by 2.

Knuth's Boundary Tag Method

To determine whether the adjacent neighbor in physical memory is a hole without searching the entire linked list from the head, Donald Knuth introduced boundary tags. Every memory block contains a header and a footer storing its allocation status and size:

struct BlockHeader {
    unsigned int is_allocated : 1;
    unsigned int block_size    : 31;
};
struct BlockFooter {
    unsigned int is_allocated : 1;
    unsigned int block_size    : 31;
};

By examining the footer immediately preceding the block's start address, and the header immediately following the block's end address, the kernel performs neighbor inspection and hole coalescing in $\mathcal{O}(1)$ constant time.

4. The Binary Buddy Allocator

While linked lists offer flexibility, finding holes and splitting arbitrary sizes can cause memory fragmentation. The Binary Buddy System (developed by Harry Markowitz in 1963 and refined by Kenneth Knowlton) is an elegant compromise that provides fast allocation and rapid coalescing.

Buddy Mechanics

Memory is allocated strictly in units that are powers of two: $2^U, 2^{U+1}, \dots, 2^L$.

If a request of size $S$ arrives, the system rounds $S$ up to the nearest power of two: $2^k \ge S$.
The allocator checks the free list for size $2^k$.
If no hole of size $2^k$ is available, it finds a hole of size $2^{k+1}$ and splits it into two equal buddies of size $2^k$. One buddy is allocated; the other is placed on the $2^k$ free list.
This splitting recurses upward until an appropriately sized block is generated.

Bitwise Buddy Calculation:

For a block of size $2^k$ starting at physical address $B$, the physical address of its buddy is calculated instantly using a single bitwise XOR operation: $$ \text{BuddyAddress}(B, k) = B \oplus 2^k $$

When block $B$ is released, the allocator computes its buddy's address in one clock cycle. If the buddy is also marked free and has size $2^k$, the two buddies immediately merge back into a single block of size $2^{k+1}$. This coalescing cascades up the power-of-two hierarchy until an occupied buddy is reached.

Trade-off: The buddy system eliminates external fragmentation and coalesces in $\mathcal{O}(1)$ time, but suffers from moderate internal fragmentation because payloads are rounded up to powers of two.