Operating Systems Research · Memory Management Simulation

First Fit · Best Fit · Worst Fit

Doubly-Linked List · External Fragmentation Analysis · Heavy Load Benchmark
2048
Memory (bytes)
500
Operations
—
Lowest EF Algorithm
—
Best EF Achieved
Simulation Parameters
Total Memory2048 bytes
Operations500 ops
Max Request Size200 bytes
Alloc Probability65%
Live Memory Maps & Metrics
First FitEF: —
Alloc success—
Alloc failures—
Free blocks—
Free memory—
Best FitEF: —
Alloc success—
Alloc failures—
Free blocks—
Free memory—
Worst FitEF: —
Alloc success—
Alloc failures—
Free blocks—
Free memory—
External Fragmentation Over Time
Comparison Summary
AlgorithmTime ComplexityFinal EF %Free BlocksAlloc SuccessFailuresRank
Run simulation to see results
Research Framework
Formula

External Fragmentation

Silberschatz, Galvin & Gagne (OS Concepts, 10th ed.):

EF = 1 - (largest_free_hole / total_free_memory)

EF = 0.0 all free memory is contiguous ideal
EF = 1.0 all free is 1-byte fragments worst
Finding

Why Best Fit Underperforms

Best Fit minimises wasted space per allocation but creates many tiny leftover fragments too small for any future request. This causes higher long-term external fragmentation despite optimal per-allocation decisions. A classic example of a locally-optimal greedy strategy failing globally — a key OS exam insight.

Data Structure

Doubly-Linked List

Each block stores: start, size, free, pid, prev*, next*

  • Allocation: O(n) scan for suitable hole
  • Deallocation: O(n) scan + O(1) coalesce
  • Coalescing merges adjacent free blocks to prevent artificial fragmentation
  • Heap variant: Best Fit can use min-heap for O(log n)
OS Reality

Real OS Memory Managers

Linux uses the buddy system + slab allocator. glibc malloc() uses a variant of First Fit with size-class bins. The key insight: speed (O(1) amortised) matters more than minimal fragmentation in a real kernel. This simulator proves why the theoretical "best" algorithm — Best Fit — is almost never used in production operating systems.