Operating Systems
There Is No Perfect Fit
The trade-offs of variable-sized memory allocation.
Operating SystemsMemory ManagementMemory AllocationFirst FitBest FitWorst FitFragmentation
1. The Quest for Perfect Memory
At the end of our previous exploration, we were left with a challenging question:
Can any memory-management strategy avoid both external and internal fragmentation?
The answer is brief: no universally perfect strategy exists.
Memory allocation is a balance of trade-offs. Paging uses fixed-size pages, so a process may not use every byte of its final allocated page, creating internal fragmentation. Because pages can occupy any available physical frame, paging generally avoids external fragmentation.
Segmentation uses variable-sized logical segments, but those segments require suitable contiguous regions, so allocation and deallocation over time can create external fragmentation.
When we must place variable-sized segments into physical memory, how does the system choose where to put them?
2. Classical Allocation Strategies
Let us consider a memory layout with several scattered free regions of different sizes. When a new segment request arrives, three classical algorithms can determine its placement:
* First Fit: The allocator scans memory from the beginning and places the segment in the first free block that is large enough. This strategy is fast because it stops scanning immediately upon finding a fit, but it tends to crowd the beginning of memory with small fragments.
* Best Fit: The allocator scans the entire memory space and places the segment in the smallest free block that is large enough. This preserves larger blocks for future allocations, but it often leaves behind tiny, unusable slivers of free space—"memory shrapnel"—that are too small to satisfy any future request.
* Worst Fit: The allocator scans the entire memory space and places the segment in the largest free block available. The logic is that the remaining leftover space will still be large enough to be useful. In practice, however, this strategy quickly breaks down large blocks, making it impossible to allocate large segments later.
These strategies are not merely textbook definitions; they represent different philosophies of managing resource scarcity.
3. EdgeCase: Allocation Strategies in Action
In this interactive scenario, we have a memory layout with three free blocks of varying sizes: 12 KB, 6 KB, and 20 KB, separated by blocks already in use by other processes.
We will attempt to allocate a sequence of three segment requests:
1. Request 1 (R1): 5 KB
2. Request 2 (R2): 10 KB
3. Request 3 (R3): 15 KB
Switch between the strategies below to see how the exact same sequence of requests succeeds or fails depending on the placement algorithm.
4. Modern Memory Management Systems
While First Fit, Best Fit, and Worst Fit are valuable mental models for variable-sized allocation, modern operating systems do not rely on a single algorithm to manage their memory. Real systems are far more complex, combining virtual memory hardware with specialized allocation layers:
* Linux: Uses the Buddy Allocator to manage physical page frames (mitigating external fragmentation by grouping pages into power-of-two blocks), and layers the SLAB/SLUB Allocator on top to manage small kernel objects (eliminating internal fragmentation by caching objects of specific sizes).
* Android / Mobile Platforms: Operates under tight hardware constraints. Rather than swapping to disk, Android utilizes zram (compressed memory swap) to compress unused pages in RAM, and coordinates memory pressure using the Low Memory Killer Daemon (LMKD) to reclaim space under severe load.
* Windows & Apple macOS/iOS: Employ advanced virtual memory managers that dynamically manage page tables, compress memory pages, and page out inactive memory to persistent storage when memory pressure rises.
Modern memory management is not a single universal algorithm, but a coordinated hierarchy of physical managers, virtual translation layers, and reclaim daemons working together.
5. The Next Horizon
We have followed the journey of memory from physical registers to virtual pages, through paging tables, page replacement algorithms, and variable-sized segment allocators.
But RAM—whether paged, segmented, or compressed—possesses a fundamental physical constraint: it is temporary. When a system loses power, everything inside its memory fades away. Programs need a way to keep their code, documents, images, databases, and configurations safe across reboots.
This transition from volatile memory to persistent storage leads us to our next major architectural question:
If memory is where information lives while it is being used, where does information live when it isn't?
To answer this, we must cross the boundary from memory allocation to File Management.
Current Exploration
There Is No Perfect Fit
