Memory Allocation Strategies
First Fit Allocation Strategy
Read aloud is unavailable in this browser.
The Allocation Decision
When a process requests memory from the operating system, the memory manager faces a deceptively simple question: Which free block should satisfy this request? In a system using variable partitioning, multiple holes (free memory blocks) of varying sizes typically exist throughout physical memory. The algorithm used to select among these holes profoundly impacts system performance, memory utilization, and fragmentation characteristics.
First Fit is the most intuitive and historically significant memory allocation strategy. It answers the selection question with elegant simplicity: allocate the first hole that is large enough to satisfy the request. This seemingly trivial decision has far-reaching implications that we will explore in comprehensive detail.
By the end of this page, you will understand the First Fit algorithm at a deep level—its implementation, time complexity, memory traversal patterns, fragmentation behavior, and why it remains the default choice in many real-world memory allocators. You will be able to trace its execution, analyze its performance characteristics, and understand its theoretical foundations.
Algorithm Definition and Core Mechanics
First Fit is elegantly defined: scan the list of free memory blocks from the beginning and allocate the first block that is large enough to satisfy the request. If the selected block is larger than needed, it is split—the requested portion is allocated to the process, and the remainder stays in the free list as a smaller hole.
Formal Algorithm Specification
Let us formalize the algorithm precisely:
- Input: A request for
nbytes of memory - Data Structure: A linked list (or array) of free blocks, where each block has a
start_addressandsize - Process:
- Traverse the free list from the beginning (lowest address or list head)
- For each block
Bwith sizeS:- If
S >= n: Select this block for allocation - If
S > n: Split the block—allocatenbytes, return remainder(S - n)to free list - If
S == n: Remove block entirely from free list
- If
- If no suitable block found: Return allocation failure (out of memory)
- Output: Starting address of allocated memory, or NULL/error on failure
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556
typedef struct FreeBlock { size_t start_address; size_t size; struct FreeBlock* next;} FreeBlock; FreeBlock* free_list_head = NULL; /** * First Fit Memory Allocation * * Searches the free list from the beginning and allocates * the first block that can satisfy the request. * * @param requested_size: Number of bytes to allocate * @return: Starting address of allocated block, or NULL on failure */void* first_fit_allocate(size_t requested_size) { if (requested_size == 0) { return NULL; } FreeBlock* current = free_list_head; FreeBlock* previous = NULL; // Traverse free list from the beginning while (current != NULL) { if (current->size >= requested_size) { // Found a suitable block - this is THE first fit void* allocated_address = (void*)current->start_address; if (current->size > requested_size) { // Split the block: allocate requested, keep remainder current->start_address += requested_size; current->size -= requested_size; } else { // Exact fit: remove block from free list entirely if (previous == NULL) { free_list_head = current->next; } else { previous->next = current->next; } // In practice: return current to block pool or free() } return allocated_address; } // Move to next block previous = current; current = current->next; } // No suitable block found - memory exhausted return NULL;}The behavior of First Fit depends critically on how the free list is ordered. If blocks are maintained in address order (lowest to highest), First Fit tends to allocate from lower memory addresses first, leaving larger blocks at higher addresses. If blocks are maintained in insertion order (most recently freed at head), behavior changes dramatically. Most implementations use address ordering for predictability and to facilitate coalescing of adjacent free blocks.
Time and Space Complexity Analysis
Understanding the computational complexity of First Fit is essential for predicting system behavior under various workloads.
Time Complexity
Worst Case: O(n) where n is the number of free blocks
In the worst case, First Fit must traverse the entire free list before finding a suitable block (or determining that none exists). This occurs when:
- The requested size is larger than most free blocks
- Suitable blocks are located near the end of the list
- Memory is highly fragmented with many small blocks
Best Case: O(1)
The best case occurs when the first block in the free list is large enough to satisfy the request. This is remarkably common in practice, especially with address-ordered free lists where:
- The first (lowest address) block tends to be large initially
- Memory patterns often create suitable blocks near the list head
Average Case: O(n/2) → O(n)
On average, First Fit must scan roughly half the free list. However, the constant factor is typically small because the early termination property means many allocations complete quickly.
| Scenario | Time Complexity | When It Occurs |
|---|---|---|
| Best Case | O(1) | First block satisfies request |
| Average Case | O(n) | Suitable block found mid-list |
| Worst Case | O(n) | Must scan entire list or no block found |
| Amortized (real workloads) | ~O(1) to O(log n) | Early termination common in practice |
Space Complexity
O(n) for the free list data structure, where n is the number of free blocks.
Each free block requires a small constant amount of metadata:
- Start address (pointer or size_t): 4-8 bytes
- Block size: 4-8 bytes
- Next pointer (for linked list): 4-8 bytes
Total overhead per block: typically 12-24 bytes on modern systems.
Fragmentation Impact on Complexity
A critical observation: as external fragmentation increases, the number of free blocks increases, and allocation time degrades. This creates a negative feedback loop:
- First Fit splits blocks, creating more (smaller) blocks
- More blocks means longer search times
- Longer searches mean slower allocation
- System performance degrades progressively
This phenomenon motivates the use of more sophisticated data structures (binary trees, segregated lists) in production allocators.
While O(n) might seem acceptable, consider a system with thousands of free blocks. Each allocation requiring a linear scan through thousands of entries creates substantial overhead. Real-time systems with strict latency requirements often cannot tolerate this variability—the worst-case allocation time may violate timing constraints even if average performance is acceptable.
Memory Traversal and Search Patterns
The search pattern of First Fit has profound implications for memory layout and fragmentation. Understanding these patterns is crucial for systems programmers.
Address-Ordered Traversal
When the free list is maintained in ascending address order (the most common implementation), First Fit exhibits a front-loading allocation pattern:
- Allocations preferentially consume blocks at lower memory addresses
- Higher memory addresses tend to accumulate larger, unused blocks
- The "front" of memory becomes increasingly fragmented over time
- The "back" of memory remains relatively pristine
This creates a characteristic fragmentation gradient across the address space.
The Front-End Fragmentation Problem
The front-loading pattern creates a well-known problem: the front of memory becomes increasingly fragmented with small, often unusable blocks, while the back retains larger blocks. This has several consequences:
Positive Effects:
- Large blocks are preserved for large allocation requests
- Memory near the top of the address space remains contiguous
- Coalescing opportunities exist in the back portion
Negative Effects:
- Small allocations must wade through fragmented front-end debris
- Search times steadily increase as fragmentation accumulates
- Cache locality suffers as allocations scatter across memory
- The free list grows longer, consuming more metadata space
Temporal Locality Considerations
First Fit's traversal pattern interacts with processor cache behavior:
- The free list itself must be traversed, causing cache misses
- Allocated blocks near the front of memory may have better cache locality due to address clustering
- However, fragmentation disrupts this as allocations interleave with free blocks
Some allocators use a LIFO (Last-In-First-Out) free list where recently freed blocks are placed at the head. This improves cache locality (recently freed memory is 'hot' in cache) but sacrifices address ordering, making coalescing more complex. The choice between address order and LIFO order represents a fundamental design trade-off.
Block Splitting Mechanics and Minimum Block Size
Block splitting is fundamental to how First Fit operates. When a free block larger than the request is selected, the allocator must decide how to handle the surplus.
The Splitting Decision
Given a free block of size B and a request for size R where B > R:
Option 1: Always Split
- Allocate exactly
Rbytes - Return
(B - R)bytes to the free list - Maximizes memory utilization
- May create tiny, unusable fragments
Option 2: Conditional Split with Minimum Block Size
- Define a
MIN_BLOCK_SIZE(e.g., 16 bytes) - Only split if
(B - R) >= MIN_BLOCK_SIZE - Otherwise, allocate the entire block
B - Trades some internal fragmentation for reduced external fragmentation
Option 3: Threshold-Based Allocation
- Define a waste threshold (e.g., 25% of request)
- Split only if
(B - R) > threshold - More sophisticated heuristic balancing both fragment types
1234567891011121314151617181920212223242526272829303132
#define MIN_BLOCK_SIZE 32 // Minimum viable free block size /** * Allocate from a free block with intelligent splitting * * Implements minimum block size constraint to prevent * creation of tiny, unusable fragments. */void* allocate_with_split(FreeBlock* block, FreeBlock* prev, size_t requested_size) { void* allocated_address = (void*)block->start_address; size_t remaining = block->size - requested_size; if (remaining >= MIN_BLOCK_SIZE) { // Worth splitting: remainder is large enough to be useful block->start_address += requested_size; block->size = remaining; // Block stays in free list at same position } else { // Not worth splitting: allocate entire block // This causes internal fragmentation but prevents tiny fragments if (prev == NULL) { free_list_head = block->next; } else { prev->next = block->next; } // Note: we allocate block->size bytes, not requested_size // Caller may receive more memory than requested } return allocated_address;}Minimum Block Size Selection
Choosing the appropriate MIN_BLOCK_SIZE is a nuanced engineering decision:
Factors to Consider:
-
Metadata Overhead: If block metadata requires 24 bytes, a free block smaller than 24 bytes cannot exist (the metadata would consume the entire block)
-
Alignment Requirements: Memory must often be aligned to word boundaries (4 bytes), cache lines (64 bytes), or page boundaries (4096 bytes).
MIN_BLOCK_SIZEshould be at least the alignment requirement -
Workload Characteristics: If the system frequently allocates small objects (8-16 bytes),
MIN_BLOCK_SIZEshould be low. If allocations are typically larger, higher thresholds are acceptable -
Fragmentation Trade-off: Lower
MIN_BLOCK_SIZE→ more external fragmentation, less internal fragmentation. HigherMIN_BLOCK_SIZE→ opposite trade-off
Typical Values in Practice:
- Simple allocators: 16-32 bytes
- Production allocators (glibc malloc): 16 bytes minimum, but complex binning
- Page-level allocators: 4096 bytes (one page)
Tiny leftover fragments (sometimes called 'slivers') are particularly insidious. They consume space in the free list, slow down searches, but are too small to satisfy any allocation request. Without minimum block size enforcement, slivers accumulate over time, degrading allocator performance even when substantial total free memory exists.
Fragmentation Behavior and Characteristics
Understanding how First Fit induces and manages fragmentation is essential for evaluating its suitability for different workloads.
External Fragmentation Analysis
First Fit tends to produce moderate external fragmentation—better than some strategies (like Worst Fit) and comparable to or slightly better than Best Fit in many workloads.
Why First Fit Handles External Fragmentation Reasonably Well:
-
Early Termination: By stopping at the first suitable block, First Fit avoids unnecessarily fragmenting larger blocks deeper in the list
-
Block Preservation: Large blocks at the end of the address space tend to survive longer, providing capacity for large future allocations
-
Natural Coalescing Opportunities: Adjacent allocations in the front of memory are likely freed together (temporal locality of deallocation), enabling efficient coalescing
The 50-Percent Rule Relevance:
Knuth's 50-percent rule states that under heavy allocation/deallocation workloads, free blocks approach 50% of the total blocks (free + allocated). First Fit, like other strategies, converges to this equilibrium, meaning approximately half of memory tracking overhead goes to free block management.
- •Preserves large blocks for large requests
- •Front-loaded fragmentation is predictable
- •Good locality of reference for allocated blocks
- •Simpler coalescing in address-ordered lists
- •Performance degrades gracefully, not catastrophically
- •Front of memory accumulates small fragments
- •Search times increase as fragmentation grows
- •May reject requests despite adequate total free memory
- •Not optimal for minimizing fragmentation
- •Sensitive to allocation/deallocation patterns
Empirical Fragmentation Studies
Extensive research since the 1970s has characterized First Fit's fragmentation behavior:
Knuth's Analysis (1973):
- First Fit produces approximately 27% unusable memory due to fragmentation under random workloads
- This is better than Worst Fit (~35%) and comparable to Best Fit (~25-27%)
Johnstone and Wilson (1998):
- Studied real application traces rather than synthetic workloads
- Found First Fit performs within 1% of Best Fit for most applications
- Real workloads show less fragmentation than random workloads due to structure in allocation patterns
Modern Observations:
- With sophisticated coalescing and minimum block sizes, First Fit achieves excellent memory utilization (typically >90% in well-tuned allocators)
- The simple algorithm enables aggressive optimization of the hot path (frequent small allocations)
Implementation Variations and Optimizations
Production allocators rarely use textbook First Fit directly. Instead, they employ various optimizations that preserve First Fit semantics while improving performance.
Roving Pointer (Next Fit Connection)
A simple optimization: maintain a 'rover' pointer to the last examined block. Start each search from the rover position rather than the list head. This distributes fragmentation more evenly and reduces average search time.
Note: This optimization transforms First Fit into Next Fit, which we cover in detail later.
Segregated Free Lists
Modern allocators like glibc malloc, jemalloc, and tcmalloc use size-segregated free lists:
- Maintain separate free lists for different size classes (e.g., 16 bytes, 32 bytes, 64 bytes, ...)
- Allocations are routed to the appropriate size class
- Within each class, First Fit (or exact fit) is used
- Dramatically reduces search time: O(1) to find the right list, O(1) or O(k) within the list
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849
#define NUM_SIZE_CLASSES 32#define SIZE_CLASS_SHIFT 4 // Minimum block = 16 bytes // Segregated free lists: one list per size classFreeBlock* segregated_lists[NUM_SIZE_CLASSES]; /** * Map allocation size to size class index * Size classes: 16, 32, 64, 128, ... bytes */int size_to_class(size_t size) { if (size <= 16) return 0; // Log2 calculation to find size class int class = 0; size_t s = size >> SIZE_CLASS_SHIFT; while (s > 1) { s >>= 1; class++; } return (class < NUM_SIZE_CLASSES) ? class : NUM_SIZE_CLASSES - 1;} /** * Segregated First Fit allocation * * Routes request to appropriate size class, then applies * First Fit within that class's free list. */void* segregated_first_fit(size_t requested_size) { int class = size_to_class(requested_size); // Search this class and larger classes for (int c = class; c < NUM_SIZE_CLASSES; c++) { FreeBlock* block = segregated_lists[c]; FreeBlock* prev = NULL; while (block != NULL) { if (block->size >= requested_size) { // Found first fit in this size class return allocate_and_maybe_split(block, prev, requested_size, c); } prev = block; block = block->next; } } return NULL; // No suitable block in any class}Binary Tree Organization
For systems with many free blocks, a balanced binary tree (AVL, red-black) ordered by address provides O(log n) First Fit:
- Use in-order traversal to maintain address ordering
- At each node, track the maximum free size in the subtree
- Navigate to find the first (lowest address) block meeting size requirement
- This is the approach used in some kernel allocators
Bitmap-Based First Fit
For fixed-size block systems (like page frame allocators), bitmaps provide extremely fast First Fit:
- Each bit represents one block (0 = free, 1 = allocated)
- Hardware instructions (find-first-zero) locate free blocks in O(1)
- Memory overhead is minimal (1 bit per block)
- Cache-efficient scanning of free block status
This approach is used extensively in:
- Page frame allocators in Linux, Windows, BSD kernels
- Ext4 file system block allocation
- Memory-mapped file region management
Real-world allocators combine multiple strategies. For example, glibc malloc uses: exact-fit bins for common sizes, First Fit within bins, Best Fit for large allocations, and mmap() for very large allocations. Understanding the pure algorithms enables appreciation of these hybrid designs.
Real-World Applications and Usage
First Fit's simplicity and acceptable performance make it the default choice in many contexts.
Operating System Kernel Allocators
Linux Kernel:
- The buddy system uses a form of First Fit within each order's free list
- SLUB (the default slab allocator) uses First Fit for per-CPU partial slabs
- The page allocator scans zone lists with First Fit semantics
Windows Kernel:
- The segment heap uses segregated First Fit for smaller allocations
- The NT heap manager historically used First Fit for coalesced blocks
User-Space Memory Allocators
glibc malloc (ptmalloc2):
- Uses First Fit within unsorted bins
- Employs Best Fit for large bins (sorted by size)
- Demonstrates that pure strategies are rarely used alone
jemalloc (used by Firefox, Facebook):
- Uses First Fit for selecting runs within arenas
- Emphasizes per-thread caching to reduce contention
tcmalloc (Google's allocator):
- Thread-caching with First Fit for span allocation
- Optimized for high allocation rates in multithreaded programs
| System/Allocator | Where First Fit Is Used | Why First Fit |
|---|---|---|
| Linux Buddy Allocator | Within each order's free list | Simplicity, O(1) common case |
| glibc malloc | Unsorted bin allocation | Speed for recent frees |
| FreeBSD UMA (slab) | Zone selection | Cache efficiency |
| Ext4 Block Allocator | Block group scanning | Locality of allocation |
| JVM G1 Garbage Collector | Region selection | Predictable latency |
Embedded and Real-Time Systems
First Fit is particularly popular in embedded systems due to:
- Predictable worst-case: O(n) is bounded and analyzable
- Low code complexity: Smaller code footprint for resource-constrained devices
- No dynamic data structures: Can be implemented with static arrays
- Deterministic: No randomization that could affect timing analysis
However, for hard real-time systems, even O(n) worst-case may be unacceptable, motivating specialized allocators like TLSF (Two-Level Segregated Fit) that achieve O(1) with First Fit semantics.
KEEP LEARNING
Keep learning for free.
Read the complete lesson, save your notes and pick up where you left off with a free account. No card needed.