7.3 Dynamic Storage Allocation Algorithms: First-Fit, Best-Fit & Worst-Fit

Back to Operating Systems Notes

📚Module 07: Main Memory ManagementTopic 7.3⏱️18 min read

🎯High-Yield For:Computer Science Foundations • Systems Engineering • Memory Allocators

💡 Core Intuition

🍳 The Everyday Analogy: The Warehouse Storage Bays

Imagine managing a freight warehouse where incoming pallets of cargo must be placed into varying empty storage bays:

Architecture Flow

Warehouse Pallet Allocation Strategies

Contrasting speed, precision fit, and residual space conservation

💡 Hover or click any card for deep-dive operational details

⚡Fastest Check

First Available Bay

First-Fit Policy

A forklift driver walks down aisle 1 and drops the cargo in the very first bay that fits.

→

Alternative Goal: Precision

🎯Tightest Fit

Smallest Capable Bay

Best-Fit Policy

The manager searches every single aisle in the entire warehouse to find the tightest match.

→

Alternative Goal: Reusable Leftovers

🏛️Largest Leftover

Largest Cavernous Bay

Worst-Fit Policy

Place the cargo inside the largest warehouse hangar currently empty.

• First-Fit: Prioritizes speed above all else. Scans from the start and grabs the first viable hole.
• Best-Fit: Prioritizes minimizing wasted partition space. Finds the smallest viable hole, but produces unusable micro-slivers.
• Worst-Fit: Prioritizes the utility of the leftover block. Chops into the largest hole so the remainder stays large and reusable.

---

💻 Bridging to Computer Science

In dynamic variable-size memory allocation, the operating system maintains a list of available free blocks of RAM known as the Free Hole List.

When a process of size $S$ enters the system:

1. The memory manager searches the hole list for an available contiguous block $H$ such that $\text{Size}(H) \ge S$.
2. The allocator carves out $S$ bytes for the process.
3. The remaining unallocated chunk $\text{Size}(H) - S$ (if greater than zero) is returned to the free list as a smaller hole.

The strategy chosen to select $H$ drastically influences both allocation latency (CPU time) and system fragmentation (RAM utilization).

Allocation Algorithm	Search Traversal Rule	Candidate Hole Evaluated	Leftover Remainder Hole	Latency vs Fragmentation Trade-Off
First-Fit	First hole $\ge 212\text{ KB}$	Hole 2 ($500\text{ KB}$)	$288\text{ KB}$	Fastest search ($\\mathcal{O}(1)$ avg); leaves moderate leftover hole.
Best-Fit	Smallest hole $\ge 212\text{ KB}$	Hole 4 ($300\text{ KB}$)	$88\text{ KB}$	Exhaustive search ($\\mathcal{O}(N)$); creates tiny unusable slivers.
Worst-Fit	Largest hole in memory	Hole 5 ($600\text{ KB}$)	$388\text{ KB}$	Exhaustive search ($\\mathcal{O}(N)$); leaves large reusable remnant hole.

---

📚 Core Deep-Dive & Concepts

1. The Four Allocation Algorithms

---

2. Time & Space Complexity Analysis

Algorithm	Search Complexity (Unsorted List)	Search Complexity (Optimized Data Structure)	Fragmentation Pattern	Memory Utilization Efficiency
First-Fit	$\mathcal{O}(N)$ worst-case, early exit average	$\mathcal{O}(N)$ linked list	Small holes cluster near base	High (Consistently superior in practice)
Next-Fit	$\mathcal{O}(N)$ worst-case	$\mathcal{O}(N)$ circular linked list	Holes dispersed across entire RAM	Moderate
Best-Fit	$\mathcal{O}(N)$ (must inspect all entries)	$\mathcal{O}(\log N)$ via Balanced BST (e.g., Red-Black Tree)	Leaves tiny unusable slivers	Moderate to Low (creates useless dead space)
Worst-Fit	$\mathcal{O}(N)$ (must inspect all entries)	$\mathcal{O}(1)$ via Max-Heap (search max)	Destroys large contiguous blocks	Lowest (Fails large allocations quickly)

Empirical Result (Knuth & Shore Experiments):
Exhaustive computer simulations show that First-Fit generally outperforms Best-Fit and Worst-Fit in both execution speed and storage utilization. First-Fit produces less severe fragmentation than Best-Fit, while Worst-Fit severely degrades system ability to satisfy large process requests.

---

3. Step-by-Step Allocation Trace: Comparative Walkthrough

Consider a physical memory configuration with $5$ free partitions/holes available in the following sequential order:

$\text{Holes: } [\,100\text{ KB},\; 500\text{ KB},\; 200\text{ KB},\; 300\text{ KB},\; 600\text{ KB}\,]$

Four processes arrive sequentially with the following memory requests:

1. $P_1 = 212\text{ KB}$
2. $P_2 = 417\text{ KB}$
3. $P_3 = 112\text{ KB}$
4. $P_4 = 426\text{ KB}$

Let us trace the exact allocation sequence for all three primary algorithms:

A. First-Fit Allocation Trace

1. $P_1$ ($212\text{ KB}$) arrives:
   • Check Hole 1 ($100\text{ KB}$): Too small.
   • Check Hole 2 ($500\text{ KB}$): Fits! Allocated to $P_1$.
   • Remaining Hole 2 $= 500 - 212 = \mathbf{288\text{ KB}}$.
   • State: $[100\text{ KB},\; \mathbf{288\text{ KB}},\; 200\text{ KB},\; 300\text{ KB},\; 600\text{ KB}]$.
2. $P_2$ ($417\text{ KB}$) arrives:
   • Check Hole 1 ($100\text{ KB}$): Too small.
   • Check Hole 2 ($288\text{ KB}$): Too small.
   • Check Hole 3 ($200\text{ KB}$): Too small.
   • Check Hole 4 ($300\text{ KB}$): Too small.
   • Check Hole 5 ($600\text{ KB}$): Fits! Allocated to $P_2$.
   • Remaining Hole 5 $= 600 - 417 = \mathbf{183\text{ KB}}$.
   • State: $[100\text{ KB},\; 288\text{ KB},\; 200\text{ KB},\; 300\text{ KB},\; \mathbf{183\text{ KB}}]$.
3. $P_3$ ($112\text{ KB}$) arrives:
   • Check Hole 1 ($100\text{ KB}$): Too small.
   • Check Hole 2 ($288\text{ KB}$): Fits! Allocated to $P_3$.
   • Remaining Hole 2 $= 288 - 112 = \mathbf{176\text{ KB}}$.
   • State: $[100\text{ KB},\; \mathbf{176\text{ KB}},\; 200\text{ KB},\; 300\text{ KB},\; 183\text{ KB}]$.
4. $P_4$ ($426\text{ KB}$) arrives:
   • Check Hole 1 ($100\text{ KB}$), Hole 2 ($176\text{ KB}$), Hole 3 ($200\text{ KB}$), Hole 4 ($300\text{ KB}$), Hole 5 ($183\text{ KB}$).
   • None of the holes are $\ge 426\text{ KB}$!
   • Result: $P_4$ cannot be allocated (must wait).

---

B. Best-Fit Allocation Trace

Initial State: $[100\text{ KB},\; 500\text{ KB},\; 200\text{ KB},\; 300\text{ KB},\; 600\text{ KB}]$.

1. $P_1$ ($212\text{ KB}$) arrives:
   • Capable holes: $500\text{ KB}, 300\text{ KB}, 600\text{ KB}$.
   • Smallest capable: Hole 4 ($300\text{ KB}$). Allocated to $P_1$.
   • Remaining Hole 4 $= 300 - 212 = \mathbf{88\text{ KB}}$.
   • State: $[100\text{ KB},\; 500\text{ KB},\; 200\text{ KB},\; \mathbf{88\text{ KB}},\; 600\text{ KB}]$.
2. $P_2$ ($417\text{ KB}$) arrives:
   • Capable holes: $500\text{ KB}, 600\text{ KB}$.
   • Smallest capable: Hole 2 ($500\text{ KB}$). Allocated to $P_2$.
   • Remaining Hole 2 $= 500 - 417 = \mathbf{83\text{ KB}}$.
   • State: $[100\text{ KB},\; \mathbf{83\text{ KB}},\; 200\text{ KB},\; 88\text{ KB},\; 600\text{ KB}]$.
3. $P_3$ ($112\text{ KB}$) arrives:
   • Capable holes: $200\text{ KB}, 600\text{ KB}$.
   • Smallest capable: Hole 3 ($200\text{ KB}$). Allocated to $P_3$.
   • Remaining Hole 3 $= 200 - 112 = \mathbf{88\text{ KB}}$.
   • State: $[100\text{ KB},\; 83\text{ KB},\; \mathbf{88\text{ KB}},\; 88\text{ KB},\; 600\text{ KB}]$.
4. $P_4$ ($426\text{ KB}$) arrives:
   • Capable holes: Hole 5 ($600\text{ KB}$).
   • Smallest capable: Hole 5 ($600\text{ KB}$). Allocated to $P_4$!
   • Remaining Hole 5 $= 600 - 426 = \mathbf{174\text{ KB}}$.
   • Result: All four processes ($P_1, P_2, P_3, P_4$) successfully allocated!

---

C. Worst-Fit Allocation Trace

Initial State: $[100\text{ KB},\; 500\text{ KB},\; 200\text{ KB},\; 300\text{ KB},\; 600\text{ KB}]$.

1. $P_1$ ($212\text{ KB}$) arrives:
   • Largest hole: Hole 5 ($600\text{ KB}$). Allocated to $P_1$.
   • Remaining Hole 5 $= 600 - 212 = \mathbf{388\text{ KB}}$.
   • State: $[100\text{ KB},\; 500\text{ KB},\; 200\text{ KB},\; 300\text{ KB},\; \mathbf{388\text{ KB}}]$.
2. $P_2$ ($417\text{ KB}$) arrives:
   • Largest hole: Hole 2 ($500\text{ KB}$). Allocated to $P_2$.
   • Remaining Hole 2 $= 500 - 417 = \mathbf{83\text{ KB}}$.
   • State: $[100\text{ KB},\; \mathbf{83\text{ KB}},\; 200\text{ KB},\; 300\text{ KB},\; 388\text{ KB}]$.
3. $P_3$ ($112\text{ KB}$) arrives:
   • Largest hole: Hole 5 ($388\text{ KB}$). Allocated to $P_3$.
   • Remaining Hole 5 $= 388 - 112 = \mathbf{276\text{ KB}}$.
   • State: $[100\text{ KB},\; 83\text{ KB},\; 200\text{ KB},\; 300\text{ KB},\; \mathbf{276\text{ KB}}]$.
4. $P_4$ ($426\text{ KB}$) arrives:
   • Available holes: $100\text{ KB}, 83\text{ KB}, 200\text{ KB}, 300\text{ KB}, 276\text{ KB}$.
   • Largest available hole is only $300\text{ KB} < 426\text{ KB}$.
   • Result: $P_4$ cannot be allocated (must wait).

Summary Comparison for this Workload

Algorithm	$P_1$ ($212\text{ KB}$)	$P_2$ ($417\text{ KB}$)	$P_3$ ($112\text{ KB}$)	$P_4$ ($426\text{ KB}$)	Total Completed
First-Fit	Hole 2 ($500\text{ KB}$)	Hole 5 ($600\text{ KB}$)	Hole 2 ($288\text{ KB}$)	❌ Rejected	3 / 4
Best-Fit	Hole 4 ($300\text{ KB}$)	Hole 2 ($500\text{ KB}$)	Hole 3 ($200\text{ KB}$)	✅ Hole 5 ($600\text{ KB}$)	4 / 4 (Winner)
Worst-Fit	Hole 5 ($600\text{ KB}$)	Hole 2 ($500\text{ KB}$)	Hole 5 ($388\text{ KB}$)	❌ Rejected	3 / 4

---

🏭 In The Real World: Production Case Study

High-Performance Heap Memory Allocators: malloc & ptmalloc

Modern user-space allocators implement modified hybrid forms of these algorithms to maximize thread concurrency and minimize heap fragmentation:

GNU C Library (glibc) ptmalloc Arena Architecture

Multi-tier bin hierarchy balancing allocation speed and fragmentation control

⚡

Fastbins

Singly-Linked (16B - 80B)

• Dedicated singly-linked LIFO caches for tiny allocation sizes.
• Zero hole scanning: allocations and deallocations complete in O(1) time via lockless pointer swaps.

Key Abstractions / Calls

malloc(32)

🎯

Smallbins

Exact-Fit (< 512B)

• Doubly-linked circular FIFO queues partitioned into 64 distinct exact size classes.
• Guarantees deterministic O(1) allocation without splitting large contiguous memory chunks.

Key Abstractions / Calls

malloc(128)

🔄

Unsorted Bin

First-Fit Staging

• Immediate cache staging area for all recently freed non-fastbin memory chunks.
• Evaluated via First-Fit: quickly recycles recently freed blocks without tree searches.

Key Abstractions / Calls

free(ptr)

🌲

Largebins

Best-Fit (> 512B)

• Sorted balanced search trees housing varied variable-sized large memory chunks.
• Searched via Best-Fit to strictly minimize wasted external fragmentation on large requests.

Key Abstractions / Calls

malloc(4096)

1. Why malloc Does Not Use Pure Worst-Fit:
   • In production microservices allocating millions of JSON strings, Worst-Fit quickly breaks apart large contiguous memory maps (mmap regions), causing heap expansion and out-of-memory (OOM) errors.
2. The Fastbin Optimization:
   • glibc bypasses dynamic hole searching entirely for small sizes by using dedicated Fastbins (analogous to fixed-size partitioning). Deallocations and allocations execute in $\mathcal{O}(1)$ time through pointer swaps without scanning any hole lists.

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

Question 1: In dynamic memory allocation, why is Worst-Fit named "Worst-Fit" if its design goal was to leave behind large, reusable fragments? Answer:

1. The name refers to the heuristic: it intentionally selects the worst possible size match (the largest discrepancy between request size and available hole size).
2. While the intention was to keep residual fragments large enough to be useful, in practice it rapidly consumes and splinters the largest contiguous blocks in the system.
3. When a subsequent process arrives with a genuinely large memory requirement, the system cannot fulfill the request because the large holes have already been degraded. Consequently, Worst-Fit exhibits the worst performance in overall storage utilization.

---

Question 2: Which algorithm is preferred when memory allocation requests arrive at an exceptionally high frequency and low CPU overhead is paramount? Answer: First-Fit is preferred.

• First-Fit does not require examining all free blocks; it terminates searching as soon as the first satisfactory hole is encountered.
• In contrast, Best-Fit and Worst-Fit must inspect every single block in an unsorted free list to determine the global minimum or maximum, incurring significant CPU scanning latency.

Common Interview Traps

• The "Best-Fit is Always Best" Trap: Do not assume Best-Fit is globally optimal because of its name. In variable-size partitioning, Best-Fit creates swarms of tiny unallocated fragments (e.g. 4-byte or 8-byte holes) that cannot satisfy any realistic process request, degrading performance over time.
• Failure to Update Hole Sizes in Multi-Step Questions: When tracing problems on exams, remember that after satisfying a process request, the hole size decreases immediately. The next process in the sequence sees the updated hole size, not the original size.

---

🗺️View Complete Operating Systems Roadmap & Syllabus

← Previous Topic7.2 Internal vs External FragmentationNext Topic →7.4 Compaction & Paging Architecture