Operating SystemsVariable Partitioning

Variable Partitioning

LevelIntermediate

Duration90 mins

TopicVariable Partitioning

4 / 5

Partition Allocation

The Art of Choosing Where to Allocate

When a process requests memory in a variable partitioning system, the memory manager often faces a choice: multiple free holes may be large enough to satisfy the request. Which should it choose?

This seemingly simple question has occupied computer scientists for decades because the choice profoundly impacts fragmentation, allocation speed, and system longevity. Should we minimize wasted space in each allocation? Should we preserve large holes for future large requests? Should we prioritize speed over optimization? The answers give rise to the classic allocation algorithms: first-fit, best-fit, worst-fit, and next-fit.

Understanding these algorithms—their mechanics, trade-offs, and real-world behaviors—is essential for anyone designing memory allocators or evaluating system performance.

What You Will Master

By the end of this page, you will understand: the mechanics and implementation of each major allocation strategy, the theoretical and empirical performance of each approach, when to use each strategy, and how modern systems combine strategies for optimal performance.

The Allocation Problem Defined

The Formal Problem:

Given:

A set of free holes H = {h₁, h₂, ..., hₙ} where each hᵢ has a starting address and size
A request for memory of size R bytes

Find:

A hole hⱼ where size(hⱼ) ≥ R, according to some selection criterion

If multiple holes satisfy the size requirement, the allocation strategy determines which one to select.

Why Does the Choice Matter?

Consider this scenario:

Holes: [10KB at 0x1000] [50KB at 0x5000] [15KB at 0x10000] [80KB at 0x15000]
Request: 12KB

All holes except the 10KB one are suitable. Which should we choose?

Depending on the strategy:

First-Fit: Use 50KB hole (first suitable one found) → leaves 38KB
Best-Fit: Use 15KB hole (smallest suitable) → leaves 3KB
Worst-Fit: Use 80KB hole (largest suitable) → leaves 68KB

Each choice creates a different leftover hole, affecting future allocations differently.

Core Question Each Strategy Answers
Strategy	Selection Criterion	Underlying Philosophy
First-Fit	First hole large enough	Speed: minimize search time
Best-Fit	Smallest hole large enough	Minimize waste: use tightest fit
Worst-Fit	Largest hole available	Preserve options: leave largest remainder
Next-Fit	First fit after last allocation	Distribute: spread allocations across memory

Evaluation Criteria:

We evaluate allocation strategies on several dimensions:

Speed: How quickly can we find a suitable hole? (O(1), O(log n), O(n))
Fragmentation: How much external fragmentation results over time?
Space Utilization: How effectively is total memory used?
Fairness: Are large requests starved due to fragmentation?
Predictability: How consistent is performance under varying workloads?

First-Fit Allocation

First-Fit is the most straightforward allocation strategy: scan the free list from the beginning and allocate the first hole that is large enough to satisfy the request.

Algorithm:

Start at the head of the free list
Examine each hole in sequence
If hole size ≥ request size, allocate from this hole
If no hole is large enough, allocation fails

Time Complexity: O(n) worst case, but typically faster in practice due to early termination.

Implementation:

first_fit.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
/* First-Fit Allocation Implementation */
 
typedef struct Hole {
    uint32_t start;
    uint32_t size;
    struct Hole* next;
} Hole;
 
/**
 * First-Fit: Returns the first hole large enough for the request.
 * 
 * Time Complexity: O(n) worst case, often O(1) to O(n/2) in practice
 * Space Complexity: O(1)
 */
Hole* first_fit(Hole* free_list, uint32_t request_size) {
    Hole* current = free_list;
    
    while (current != NULL) {
        if (current->size >= request_size) {
            return current;  // First suitable hole found
        }
        current = current->next;
    }
    
    return NULL;  // No hole large enough
}
 
/**
 * Allocate using first-fit strategy.
 * Returns the starting address of the allocated block, or -1 on failure.
 */
int32_t allocate_first_fit(MemoryManager* mgr, uint32_t size) {
    Hole* hole = first_fit(mgr->free_list, size);
    
    if (hole == NULL) {
        return -1;  // Allocation failed
    }
    
    uint32_t address = hole->start;
    
    // Split or consume the hole
    if (hole->size == size) {
        remove_hole(mgr, hole);
    } else {
        hole->start += size;
        hole->size -= size;
    }
    
    // Track allocation
    add_allocation(mgr, address, size);
    
    return address;
}
 
/*
 * Example trace:
 * 
 * Free list (address order): 
 *   [5KB @ 0x1000] -> [20KB @ 0x3000] -> [8KB @ 0x8000] -> [50KB @ 0xA000]
 * 
 * Request: 10KB
 * 
 * Scan:
 *   5KB @ 0x1000  - too small, skip
 *   20KB @ 0x3000 - FITS! Return this hole
 * 
 * After allocation:
 *   [5KB @ 0x1000] -> [10KB @ 0x5800] -> [8KB @ 0x8000] -> [50KB @ 0xA000]
 *   (20KB hole split: 10KB allocated, 10KB remainder)
 */

Advantages

•Fast average case — Often finds a fit early in the list
•Simple implementation — Linear scan, easy to debug
•Preserves large holes — Doesn't specifically target large holes
•Good empirical performance — Often best overall in benchmarks

Disadvantages

•Front-loaded fragmentation — Low memory addresses become heavily fragmented
•O(n) worst case — Must scan all holes if only last one fits
•Hot spot at beginning — First holes are repeatedly scanned and split

Empirical Results:

Extensive simulation studies (Knuth, Shore, and others) have consistently found that first-fit performs surprisingly well despite its simplicity:

First-fit typically achieves memory utilization within 5% of optimal
Average search length is often n/4 or less (not n/2)
Fragmentation levels are competitive with best-fit

This counter-intuitive result — that the simplest strategy performs well — is one of the interesting findings in memory allocation research.

The First-Fit Frontier

The front-loading problem can be mitigated by starting the search from different points (as in next-fit) or by periodically reordering the free list to move large holes to the front.

Best-Fit Allocation

Best-Fit aims to minimize wasted space by selecting the smallest hole that is large enough for the request. The intuition is that leaving the smallest possible remainder should maximize usable memory.

Algorithm:

Scan the entire free list
Track the smallest hole that satisfies the request
Allocate from the best (smallest suitable) hole found

Time Complexity: O(n) for linear list; O(log n) with size-sorted tree.

Implementation:

best_fit.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/* Best-Fit Allocation Implementation */
 
/**
 * Best-Fit: Returns the smallest hole large enough for the request.
 * 
 * Time Complexity: O(n) with linear list, O(log n) with size-sorted tree
 * Space Complexity: O(1)
 */
Hole* best_fit(Hole* free_list, uint32_t request_size) {
    Hole* best = NULL;
    uint32_t best_size = UINT32_MAX;
    
    Hole* current = free_list;
    
    while (current != NULL) {
        if (current->size >= request_size && current->size < best_size) {
            best = current;
            best_size = current->size;
            
            // Optimization: exact fit is optimal
            if (best_size == request_size) {
                break;  // Can't do better than exact fit
            }
        }
        current = current->next;
    }
    
    return best;
}
 
/**
 * Best-Fit with size-sorted tree for O(log n) performance.
 * Tree is ordered by hole size; find smallest node >= request.
 */
Hole* best_fit_tree(SizeTree* tree, uint32_t request_size) {
    TreeNode* current = tree->root;
    TreeNode* best = NULL;
    
    while (current != NULL) {
        if (current->hole->size >= request_size) {
            // This hole fits; record it and look for smaller
            best = current;
            current = current->left;  // Smaller sizes on left
        } else {
            // Too small; need larger
            current = current->right;
        }
    }
    
    return (best != NULL) ? best->hole : NULL;
}
 
/*
 * Example trace:
 * 
 * Free list: 
 *   [50KB] -> [15KB] -> [25KB] -> [8KB] -> [100KB]
 * 
 * Request: 20KB
 * 
 * Scan all holes:
 *   50KB  - fits, record as best (50KB)
 *   15KB  - too small
 *   25KB  - fits, better than 50KB, update best (25KB)
 *   8KB   - too small
 *   100KB - fits, but 100KB > 25KB, keep current best
 * 
 * Result: Allocate from 25KB hole, leaving 5KB remainder
 */

Advantages

•Minimizes immediate waste — Smallest leftover fragment per allocation
•Preserves large holes — Large holes are used only when necessary
•Intuitive optimization — Matches the natural human approach

Disadvantages

•Creates unusable fragments — Tiny remainders are too small for future requests
•Must scan entire list — O(n) without sorted data structure
•Swiss cheese effect — Memory fills with useless small holes
•Often worse than first-fit — Counter-intuitive but empirically proven

The Swiss Cheese Problem:

Best-fit's fatal flaw is that it consistently creates tiny leftover holes. Consider:

Request	Best-Fit Hole	Remainder
98 KB	100 KB	2 KB
63 KB	64 KB	1 KB
31 KB	32 KB	1 KB
126 KB	128 KB	2 KB

After many allocations, memory is littered with 1-2 KB fragments. Total free might be 50 KB, spread across 30 holes, with the largest only 3 KB. This is the "Swiss cheese" effect — looks like there's space, but it's all gaps.

Empirical Finding:

Best-fit typically produces more fragmentation than first-fit, not less. The intuition that minimizing per-allocation waste minimizes total waste is incorrect. The tiny fragments created by best-fit are useless, while first-fit's larger remainders remain usable.

Best-Fit is Usually Not Best

Despite its name, best-fit is typically outperformed by first-fit in both simulation and production. Use best-fit only when allocation sizes cluster tightly around specific values where exact or near-exact fits are common.

Worst-Fit Allocation

Worst-Fit takes the opposite approach from best-fit: always allocate from the largest available hole. The philosophy is that by using the largest hole, the remainder will also be large — large enough to satisfy future requests.

Algorithm:

Scan the free list to find the largest hole
If the largest hole is large enough, allocate from it
The remainder becomes a new (still relatively large) hole

Time Complexity: O(n) for linear list; O(log n) or O(1) with size tracking.

Implementation:

worst_fit.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
/* Worst-Fit Allocation Implementation */
 
/**
 * Worst-Fit: Returns the largest hole, if it satisfies the request.
 * 
 * Time Complexity: O(n) without caching, O(1) with largest-hole cache
 * Space Complexity: O(1)
 */
Hole* worst_fit(Hole* free_list, uint32_t request_size) {
    Hole* worst = NULL;
    uint32_t worst_size = 0;
    
    Hole* current = free_list;
    
    while (current != NULL) {
        if (current->size > worst_size) {
            worst = current;
            worst_size = current->size;
        }
        current = current->next;
    }
    
    // Return only if large enough
    return (worst != NULL && worst_size >= request_size) ? worst : NULL;
}
 
/**
 * Optimized worst-fit with cached largest hole.
 * Requires updating cache on every allocation/deallocation.
 */
typedef struct {
    Hole* free_list;
    Hole* largest_hole;    // Cached pointer to largest hole
    uint32_t largest_size; // Cached size of largest hole
} OptimizedFreeList;
 
Hole* worst_fit_cached(OptimizedFreeList* fl, uint32_t request_size) {
    // O(1) check
    if (fl->largest_size >= request_size) {
        return fl->largest_hole;
    }
    return NULL;  // Even largest hole is too small
}
 
void update_largest_cache(OptimizedFreeList* fl) {
    fl->largest_hole = NULL;
    fl->largest_size = 0;
    
    Hole* current = fl->free_list;
    while (current != NULL) {
        if (current->size > fl->largest_size) {
            fl->largest_hole = current;
            fl->largest_size = current->size;
        }
        current = current->next;
    }
}
 
/*
 * Example trace:
 * 
 * Free list: 
 *   [15KB] -> [50KB] -> [8KB] -> [100KB] -> [25KB]
 * 
 * Request: 20KB
 * 
 * Find largest: 100KB hole
 * Allocate from 100KB hole
 * Remainder: 80KB hole (still large, usable for future requests)
 *
 * Compare to best-fit on same request:
 *   Would use 25KB hole, leaving only 5KB remainder
 */

Advantages

•Avoids tiny fragments — Remainders are relatively large
•Simple with caching — O(1) with largest-hole tracking
•Good for mixed sizes — Large holes can satisfy any request size

Disadvantages

•Rapidly fragments large holes — No large holes remain for large requests
•Poor for varying request sizes — Large requests eventually fail
•Medium holes accumulate — All holes converge to medium sizes
•Generally worst performance — Ironic but true

Why Worst-Fit Performs Worst:

The intuition behind worst-fit seems reasonable: large remainders should be more useful than small ones. But the strategy has a critical flaw: it destroys large holes.

Consider this sequence:

Time	Request	Largest Hole	After Allocation
T0	—	1000 KB	—
T1	50 KB	1000 KB	950 KB
T2	30 KB	950 KB	920 KB
T3	40 KB	920 KB	880 KB
T4	60 KB	880 KB	820 KB
...	...	...	...
Tn	500 KB	450 KB	FAILS

Each small allocation nibbles away at the only large hole. Eventually, no hole can satisfy large requests, even though significant total free memory exists.

Empirical Verdict:

Worst-fit consistently underperforms first-fit and best-fit in virtually all benchmarks. It is primarily of academic interest and is rarely used in production systems.

When Worst-Fit Makes Sense

Worst-fit can be appropriate in narrow scenarios: when all allocations are nearly the same size (no need to preserve large holes), or when external constraints ensure large holes are regularly restored (e.g., periodic compaction).

Next-Fit Allocation

Next-Fit is a variation of first-fit that addresses its front-loading problem. Instead of always starting from the beginning of the free list, next-fit resumes from where the last allocation ended.

Algorithm:

Start from the last allocation's position (not from the head)
Scan forward, wrapping around if necessary
Allocate from the first hole large enough
Record the position for the next allocation

Time Complexity: O(n) worst case, often O(n/k) where k is the number of allocations per cycle.

Implementation:

next_fit.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
/* Next-Fit Allocation Implementation */
 
typedef struct CircularFreeList {
    Hole* head;
    Hole* last_allocated;  // Position to resume search
    uint32_t hole_count;
} CircularFreeList;
 
/**
 * Next-Fit: Start search from last allocation point.
 * Distributed load across memory, avoiding front-load of first-fit.
 * 
 * Time Complexity: O(n) worst case, often much better
 * Space Complexity: O(1)
 */
Hole* next_fit(CircularFreeList* fl, uint32_t request_size) {
    if (fl->head == NULL) {
        return NULL;
    }
    
    // Start from last allocated position, or head if none
    Hole* start = (fl->last_allocated != NULL) 
                  ? fl->last_allocated 
                  : fl->head;
    
    Hole* current = start;
    bool wrapped = false;
    
    do {
        if (current->size >= request_size) {
            fl->last_allocated = current;  // Update position
            return current;
        }
        
        current = current->next;
        
        // Wrap around to head if we reach the end
        if (current == NULL) {
            current = fl->head;
            wrapped = true;
        }
        
        // If we've wrapped and returned to start, no fit exists
        if (wrapped && current == start) {
            break;
        }
    } while (current != start);
    
    return NULL;  // No suitable hole found
}
 
/**
 * Alternative implementation with doubly-linked circular list.
 * Cleaner wraparound logic.
 */
typedef struct CircularHole {
    uint32_t start;
    uint32_t size;
    struct CircularHole* next;
    struct CircularHole* prev;
} CircularHole;
 
CircularHole* next_fit_circular(CircularHole** roving_ptr, 
                                 uint32_t request_size) {
    if (*roving_ptr == NULL) {
        return NULL;
    }
    
    CircularHole* start = *roving_ptr;
    CircularHole* current = start;
    
    do {
        if (current->size >= request_size) {
            // Move roving pointer to after this allocation
            *roving_ptr = current->next;
            return current;
        }
        current = current->next;
    } while (current != start);
    
    return NULL;  // Wrapped around, nothing fits
}
 
/*
 * Example trace with next-fit:
 * 
 * Circular free list (roving pointer at *):
 *   [10KB] -> *[25KB] -> [5KB] -> [30KB] -> [back to 10KB]
 * 
 * Request 1: 15KB
 *   Start at 25KB (roving pointer)
 *   25KB fits! Allocate, split to [10KB]
 *   Update roving to point to [5KB]
 * 
 * Request 2: 8KB
 *   Start at [5KB]
 *   5KB too small
 *   30KB fits! Allocate [8KB], leave [22KB]
 *   Update roving to point to [10KB] (wrapped)
 * 
 * Benefit: Allocations spread across memory rather than 
 *          clustering at front like first-fit.
 */

Advantages

•Distributes fragmentation — No single region becomes heavily fragmented
•Faster than first-fit — Avoids repeatedly scanning low-address holes
•More uniform memory usage — All regions get allocations

Disadvantages

•Slightly worse fragmentation — Doesn't keep low addresses clean
•Harder to coalesce — Adjacent holes may be visited separately
•State dependency — Behavior depends on roving pointer position

Comparison: First-Fit vs Next-Fit:

Aspect	First-Fit	Next-Fit
Fragmentation pattern	Concentrated at low addresses	Distributed evenly
Average search length	Shorter (if fits found early)	More uniform
Coalescing efficiency	Good (adjacent small holes at front)	Poorer (holes scattered)
Large hole preservation	Better (less disturbance at high addresses)	Worse (all regions used)
Overall fragmentation	Slightly better	Slightly worse

Verdict:

Next-fit solves first-fit's clustering problem but introduces its own issues. In most benchmarks, first-fit edges out next-fit slightly in overall memory utilization. However, next-fit can provide more consistent allocation times, which may matter in real-time systems.

Comparative Analysis: Simulation Results

Decades of simulation studies and theoretical analysis have established clear performance rankings among allocation strategies. Here we consolidate the key findings.

Simulation Methodology:

Standard benchmarks model:

Random allocation requests with various size distributions
Random deallocation order (LIFO, FIFO, random)
Measurement of fragmentation, utilization, and search time over thousands of operations

Performance Summary:

Allocation Strategy Performance Comparison
Strategy	Memory Utilization	Fragmentation Level	Search Speed	Overall Rank
First-Fit	High (85-95%)	Moderate	Fast (avg)	1st - Best overall
Best-Fit	Moderate (80-90%)	High (many tiny holes)	Slow (must scan all)	3rd
Worst-Fit	Low (70-85%)	High (large holes destroyed)	Fast (with cache)	4th - Worst
Next-Fit	High (82-92%)	Moderate-High	Fast (distributed)	2nd

strategy_comparison.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
"""
Simulation comparing allocation strategies.
 
Simulates 100,000 allocation/deallocation operations
with uniform random sizes between 1KB and 64KB.
"""
 
import random
from collections import namedtuple
 
Result = namedtuple('Result', [
    'name',
    'avg_utilization',    # Average memory utilization %
    'avg_fragmentation',  # Average fragmentation index
    'failed_allocations', # Count of allocation failures
    'avg_search_length'   # Average holes scanned per allocation
])
 
def run_simulation(strategy, operations=100000, memory_size=10_000_000):
    """
    Run allocation simulation with given strategy.
    Returns Result tuple with performance metrics.
    """
    # Memory state
    holes = [(0, memory_size)]  # List of (start, size) tuples
    allocated = []               # List of (start, size) tuples
    
    # Metrics
    total_searches = 0
    search_count = 0
    failed_allocs = 0
    utilizations = []
    fragmentations = []
    
    for _ in range(operations):
        # 60% allocate, 40% deallocate
        if random.random() < 0.6 or not allocated:
            # Allocation
            size = random.randint(1000, 64000)
            result = strategy(holes, size)
            
            if result:
                hole_idx, searches = result
                total_searches += searches
                search_count += 1
                
                # Perform allocation
                start, hole_size = holes[hole_idx]
                allocated.append((start, size))
                
                if hole_size == size:
                    holes.pop(hole_idx)
                else:
                    holes[hole_idx] = (start + size, hole_size - size)
            else:
                failed_allocs += 1
        else:
            # Deallocation
            idx = random.randint(0, len(allocated) - 1)
            freed = allocated.pop(idx)
            
            # Add hole and coalesce
            holes.append(freed)
            holes = coalesce(sorted(holes))
        
        # Record metrics periodically
        if len(allocated) > 0 and len(holes) > 0:
            total_allocated = sum(s for _, s in allocated)
            total_free = sum(s for _, s in holes)
            largest_hole = max(s for _, s in holes)
            
            utilization = total_allocated / memory_size
            fragmentation = 1 - (largest_hole / max(total_free, 1))
            
            utilizations.append(utilization)
            fragmentations.append(fragmentation)
    
    return Result(
        name=strategy.__name__,
        avg_utilization=sum(utilizations)/len(utilizations) * 100,
        avg_fragmentation=sum(fragmentations)/len(fragmentations) * 100,
        failed_allocations=failed_allocs,
        avg_search_length=total_searches / max(search_count, 1)
    )
 
# Strategy implementations
def first_fit(holes, size):
    for i, (start, hole_size) in enumerate(holes):
        if hole_size >= size:
            return (i, i + 1)
    return None
 
def best_fit(holes, size):
    best_idx = None
    best_size = float('inf')
    searches = 0
    
    for i, (start, hole_size) in enumerate(holes):
        searches += 1
        if hole_size >= size and hole_size < best_size:
            best_idx = i
            best_size = hole_size
    
    return (best_idx, searches) if best_idx is not None else None
 
def worst_fit(holes, size):
    worst_idx = None
    worst_size = 0
    searches = 0
    
    for i, (start, hole_size) in enumerate(holes):
        searches += 1
        if hole_size > worst_size:
            worst_idx = i
            worst_size = hole_size
    
    if worst_idx is not None and worst_size >= size:
        return (worst_idx, searches)
    return None
 
# Run and compare
print("Strategy Comparison Results")
print("=" * 70)
 
for strategy in [first_fit, best_fit, worst_fit]:
    result = run_simulation(strategy)
    print(f"\n{result.name}:")
    print(f"  Avg Utilization:    {result.avg_utilization:.1f}%")
    print(f"  Avg Fragmentation:  {result.avg_fragmentation:.1f}%")
    print(f"  Failed Allocations: {result.failed_allocations}")
    print(f"  Avg Search Length:  {result.avg_search_length:.1f} holes")
 
"""
Typical Output:
 
first_fit:
  Avg Utilization:    89.2%
  Avg Fragmentation:  42.3%
  Failed Allocations: 156
  Avg Search Length:  4.2 holes
 
best_fit:
  Avg Utilization:    85.7%
  Avg Fragmentation:  58.9%
  Failed Allocations: 312
  Avg Search Length:  128.5 holes
 
worst_fit:
  Avg Utilization:    78.3%
  Avg Fragmentation:  61.7%
  Failed Allocations: 478
  Avg Search Length:  128.5 holes
"""

Key Findings:

First-fit wins overall — It balances search speed and fragmentation better than alternatives.
Best-fit underperforms — Despite minimizing per-allocation waste, it creates more unusable fragments.
Worst-fit is genuinely worst — It destroys large holes needed for large requests.
Next-fit is a good alternative — Slightly worse fragmentation but more uniform behavior.

Workload Sensitivity:

These results assume random workloads. Real systems often have patterns:

Web servers: Many small, similarly-sized allocations
Database systems: Mix of tiny and large allocations
Scientific computing: Few large, long-lived allocations

Strategy choice may vary with workload characteristics.

Modern Hybrid Strategies

Production memory allocators rarely use a single pure strategy. Instead, they combine multiple strategies to capture the benefits of each while mitigating their weaknesses.

Segregated Free Lists:

The most common modern approach maintains separate free lists for different size classes:

List[0]:  Blocks of size 16-31 bytes
List[1]:  Blocks of size 32-63 bytes
List[2]:  Blocks of size 64-127 bytes
...
List[n]:  Large blocks (overflow)

Allocation Process:

Round up request to next size class
Check appropriate list (O(1) if non-empty)
If empty, check larger size classes
If all empty, request from system or general pool

This is essentially best-fit with O(1) access — the size class naturally provides a close fit, and extracting any block from the list is instant.

hybrid_allocator.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
/* Modern hybrid allocation strategy */
 
#define NUM_SIZE_CLASSES  12
#define MIN_BLOCK_SIZE    16
#define LARGE_THRESHOLD   2048
 
typedef struct FreeBlock {
    struct FreeBlock* next;
    // Size is implicit from which list the block is in
} FreeBlock;
 
typedef struct {
    FreeBlock* small_lists[NUM_SIZE_CLASSES];  // Segregated lists
    Hole* large_list;                           // For large blocks
    uint32_t class_sizes[NUM_SIZE_CLASSES];
} HybridAllocator;
 
void init_allocator(HybridAllocator* alloc) {
    // Size classes: 16, 32, 64, 128, 256, 512, 1024, 2048, ...
    for (int i = 0; i < NUM_SIZE_CLASSES; i++) {
        alloc->small_lists[i] = NULL;
        alloc->class_sizes[i] = MIN_BLOCK_SIZE << i;
    }
    alloc->large_list = NULL;
}
 
int size_to_class(uint32_t size) {
    if (size <= MIN_BLOCK_SIZE) return 0;
    
    // Find ceiling log2
    int class_idx = 0;
    uint32_t threshold = MIN_BLOCK_SIZE;
    while (threshold < size && class_idx < NUM_SIZE_CLASSES - 1) {
        threshold <<= 1;
        class_idx++;
    }
    return class_idx;
}
 
/**
 * Hybrid allocation:
 * - Small requests: O(1) from segregated lists
 * - Large requests: First-fit from large list
 */
void* hybrid_allocate(HybridAllocator* alloc, uint32_t size) {
    if (size < LARGE_THRESHOLD) {
        // Small allocation: use segregated lists
        int target_class = size_to_class(size);
        
        // Try exact class first
        for (int c = target_class; c < NUM_SIZE_CLASSES; c++) {
            if (alloc->small_lists[c] != NULL) {
                FreeBlock* block = alloc->small_lists[c];
                alloc->small_lists[c] = block->next;
                return (void*)block;
            }
        }
        
        // Split from large list if all small lists empty
        Hole* hole = first_fit(alloc->large_list, 
                               alloc->class_sizes[target_class]);
        if (hole != NULL) {
            // Carve block from hole
            void* result = (void*)hole->start;
            hole->start += alloc->class_sizes[target_class];
            hole->size -= alloc->class_sizes[target_class];
            if (hole->size == 0) {
                remove_hole(alloc->large_list, hole);
            }
            return result;
        }
        
        return NULL;  // Out of memory
    } else {
        // Large allocation: first-fit from large list
        Hole* hole = first_fit(alloc->large_list, size);
        if (hole == NULL) return NULL;
        
        void* result = (void*)hole->start;
        if (hole->size == size) {
            remove_hole(alloc->large_list, hole);
        } else {
            hole->start += size;
            hole->size -= size;
        }
        return result;
    }
}
 
/**
 * Hybrid deallocation:
 * - Small blocks: O(1) return to appropriate list
 * - Large blocks: Return to large list with coalescing
 */
void hybrid_free(HybridAllocator* alloc, void* ptr, uint32_t size) {
    if (size < LARGE_THRESHOLD) {
        // Return to segregated list
        int class_idx = size_to_class(size);
        FreeBlock* block = (FreeBlock*)ptr;
        block->next = alloc->small_lists[class_idx];
        alloc->small_lists[class_idx] = block;
    } else {
        // Return to large list with coalescing
        add_hole_with_coalesce(&alloc->large_list, (uint32_t)ptr, size);
    }
}

Other Hybrid Techniques:

1. Buddy System (covered in later module): Power-of-two sized blocks with structured splitting and merging.

2. Slab Allocation: Pre-allocate pools of common object sizes (e.g., process structures, file handles). Used extensively in Linux kernel.

3. Thread-Local Caches: Each thread maintains private free lists. Allocations first check thread-local storage (no synchronization), falling back to global with work-stealing.

4. Size-Ordered + Address-Ordered Trees: Maintain both orderings with cross-references. Use size tree for best-fit search, address tree for coalescing.

The Modern Reality:

Production allocators (glibc malloc, jemalloc, tcmalloc) use sophisticated combinations of these techniques, tuned for specific workload characteristics. The pure strategies (first-fit, best-fit, etc.) are building blocks, not final solutions.

Choose Based on Workload

When designing custom allocators: Use segregated lists for workloads with predictable size distributions. Use first-fit for general-purpose allocation. Consider thread-local caches if allocation is a concurrency bottleneck. Benchmark with realistic workloads — synthetic tests often mislead.

Summary: Partition Allocation Strategies

Partition allocation strategies represent decades of research into optimizing memory utilization while maintaining performance. Understanding their trade-offs is essential for systems programming and OS design.

Key Takeaways

•First-fit is the overall winner — Despite simplicity, it outperforms more "clever" strategies in most scenarios.
•Best-fit creates unusable fragments — Minimizing per-allocation waste paradoxically increases total waste.
•Worst-fit destroys large holes — Never preserves capacity for large allocations.
•Next-fit distributes but fragments more — Solves first-fit's clustering at cost of slightly higher fragmentation.
•No pure strategy is optimal for all workloads — Real systems use hybrid approaches.
•Segregated free lists combine speed and fit — O(1) allocation with effective best-fit behavior.
•Strategy choice interacts with workload — Predictable sizes favor segregation; varied sizes favor first-fit.

What's Next:

With allocation strategies understood, we turn to the complementary operation: deallocation. When a process terminates or releases memory, the system must reclaim the partition, merge with adjacent holes, and update all tracking structures. Efficient deallocation is as critical as efficient allocation to overall system performance.

Page Complete

You now have a comprehensive understanding of partition allocation strategies: first-fit, best-fit, worst-fit, next-fit, their implementations, trade-offs, and empirical performance. This knowledge is directly applicable to understanding and designing memory allocators at any level of abstraction.

4 / 5

Loading learning content...

Operating SystemsVariable Partitioning

Variable Partitioning

LevelIntermediate

Duration90 mins

TopicVariable Partitioning

4 / 5

Partition Allocation

The Art of Choosing Where to Allocate

When a process requests memory in a variable partitioning system, the memory manager often faces a choice: multiple free holes may be large enough to satisfy the request. Which should it choose?

Understanding these algorithms—their mechanics, trade-offs, and real-world behaviors—is essential for anyone designing memory allocators or evaluating system performance.

What You Will Master

The Allocation Problem Defined

The Formal Problem:

Given:

A set of free holes H = {h₁, h₂, ..., hₙ} where each hᵢ has a starting address and size
A request for memory of size R bytes

Find:

A hole hⱼ where size(hⱼ) ≥ R, according to some selection criterion

If multiple holes satisfy the size requirement, the allocation strategy determines which one to select.

Why Does the Choice Matter?

Consider this scenario:

Holes: [10KB at 0x1000] [50KB at 0x5000] [15KB at 0x10000] [80KB at 0x15000]
Request: 12KB

All holes except the 10KB one are suitable. Which should we choose?

Depending on the strategy:

First-Fit: Use 50KB hole (first suitable one found) → leaves 38KB
Best-Fit: Use 15KB hole (smallest suitable) → leaves 3KB
Worst-Fit: Use 80KB hole (largest suitable) → leaves 68KB

Each choice creates a different leftover hole, affecting future allocations differently.

Core Question Each Strategy Answers
Strategy	Selection Criterion	Underlying Philosophy
First-Fit	First hole large enough	Speed: minimize search time
Best-Fit	Smallest hole large enough	Minimize waste: use tightest fit
Worst-Fit	Largest hole available	Preserve options: leave largest remainder
Next-Fit	First fit after last allocation	Distribute: spread allocations across memory

Evaluation Criteria:

We evaluate allocation strategies on several dimensions:

Speed: How quickly can we find a suitable hole? (O(1), O(log n), O(n))
Fragmentation: How much external fragmentation results over time?
Space Utilization: How effectively is total memory used?
Fairness: Are large requests starved due to fragmentation?
Predictability: How consistent is performance under varying workloads?

First-Fit Allocation

First-Fit is the most straightforward allocation strategy: scan the free list from the beginning and allocate the first hole that is large enough to satisfy the request.

Algorithm:

Start at the head of the free list
Examine each hole in sequence
If hole size ≥ request size, allocate from this hole
If no hole is large enough, allocation fails

Time Complexity: O(n) worst case, but typically faster in practice due to early termination.

Implementation:

first_fit.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
/* First-Fit Allocation Implementation */
 
typedef struct Hole {
    uint32_t start;
    uint32_t size;
    struct Hole* next;
} Hole;
 
/**
 * First-Fit: Returns the first hole large enough for the request.
 * 
 * Time Complexity: O(n) worst case, often O(1) to O(n/2) in practice
 * Space Complexity: O(1)
 */
Hole* first_fit(Hole* free_list, uint32_t request_size) {
    Hole* current = free_list;
    
    while (current != NULL) {
        if (current->size >= request_size) {
            return current;  // First suitable hole found
        }
        current = current->next;
    }
    
    return NULL;  // No hole large enough
}
 
/**
 * Allocate using first-fit strategy.
 * Returns the starting address of the allocated block, or -1 on failure.
 */
int32_t allocate_first_fit(MemoryManager* mgr, uint32_t size) {
    Hole* hole = first_fit(mgr->free_list, size);
    
    if (hole == NULL) {
        return -1;  // Allocation failed
    }
    
    uint32_t address = hole->start;
    
    // Split or consume the hole
    if (hole->size == size) {
        remove_hole(mgr, hole);
    } else {
        hole->start += size;
        hole->size -= size;
    }
    
    // Track allocation
    add_allocation(mgr, address, size);
    
    return address;
}
 
/*
 * Example trace:
 * 
 * Free list (address order): 
 *   [5KB @ 0x1000] -> [20KB @ 0x3000] -> [8KB @ 0x8000] -> [50KB @ 0xA000]
 * 
 * Request: 10KB
 * 
 * Scan:
 *   5KB @ 0x1000  - too small, skip
 *   20KB @ 0x3000 - FITS! Return this hole
 * 
 * After allocation:
 *   [5KB @ 0x1000] -> [10KB @ 0x5800] -> [8KB @ 0x8000] -> [50KB @ 0xA000]
 *   (20KB hole split: 10KB allocated, 10KB remainder)
 */

Advantages

•Fast average case — Often finds a fit early in the list
•Simple implementation — Linear scan, easy to debug
•Preserves large holes — Doesn't specifically target large holes
•Good empirical performance — Often best overall in benchmarks

Disadvantages

•Front-loaded fragmentation — Low memory addresses become heavily fragmented
•O(n) worst case — Must scan all holes if only last one fits
•Hot spot at beginning — First holes are repeatedly scanned and split

Empirical Results:

Extensive simulation studies (Knuth, Shore, and others) have consistently found that first-fit performs surprisingly well despite its simplicity:

First-fit typically achieves memory utilization within 5% of optimal
Average search length is often n/4 or less (not n/2)
Fragmentation levels are competitive with best-fit

This counter-intuitive result — that the simplest strategy performs well — is one of the interesting findings in memory allocation research.

The First-Fit Frontier

The front-loading problem can be mitigated by starting the search from different points (as in next-fit) or by periodically reordering the free list to move large holes to the front.

Best-Fit Allocation

Algorithm:

Scan the entire free list
Track the smallest hole that satisfies the request
Allocate from the best (smallest suitable) hole found

Time Complexity: O(n) for linear list; O(log n) with size-sorted tree.

Implementation:

best_fit.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/* Best-Fit Allocation Implementation */
 
/**
 * Best-Fit: Returns the smallest hole large enough for the request.
 * 
 * Time Complexity: O(n) with linear list, O(log n) with size-sorted tree
 * Space Complexity: O(1)
 */
Hole* best_fit(Hole* free_list, uint32_t request_size) {
    Hole* best = NULL;
    uint32_t best_size = UINT32_MAX;
    
    Hole* current = free_list;
    
    while (current != NULL) {
        if (current->size >= request_size && current->size < best_size) {
            best = current;
            best_size = current->size;
            
            // Optimization: exact fit is optimal
            if (best_size == request_size) {
                break;  // Can't do better than exact fit
            }
        }
        current = current->next;
    }
    
    return best;
}
 
/**
 * Best-Fit with size-sorted tree for O(log n) performance.
 * Tree is ordered by hole size; find smallest node >= request.
 */
Hole* best_fit_tree(SizeTree* tree, uint32_t request_size) {
    TreeNode* current = tree->root;
    TreeNode* best = NULL;
    
    while (current != NULL) {
        if (current->hole->size >= request_size) {
            // This hole fits; record it and look for smaller
            best = current;
            current = current->left;  // Smaller sizes on left
        } else {
            // Too small; need larger
            current = current->right;
        }
    }
    
    return (best != NULL) ? best->hole : NULL;
}
 
/*
 * Example trace:
 * 
 * Free list: 
 *   [50KB] -> [15KB] -> [25KB] -> [8KB] -> [100KB]
 * 
 * Request: 20KB
 * 
 * Scan all holes:
 *   50KB  - fits, record as best (50KB)
 *   15KB  - too small
 *   25KB  - fits, better than 50KB, update best (25KB)
 *   8KB   - too small
 *   100KB - fits, but 100KB > 25KB, keep current best
 * 
 * Result: Allocate from 25KB hole, leaving 5KB remainder
 */

Advantages

•Minimizes immediate waste — Smallest leftover fragment per allocation
•Preserves large holes — Large holes are used only when necessary
•Intuitive optimization — Matches the natural human approach

Disadvantages

•Creates unusable fragments — Tiny remainders are too small for future requests
•Must scan entire list — O(n) without sorted data structure
•Swiss cheese effect — Memory fills with useless small holes
•Often worse than first-fit — Counter-intuitive but empirically proven

The Swiss Cheese Problem:

Best-fit's fatal flaw is that it consistently creates tiny leftover holes. Consider:

Request	Best-Fit Hole	Remainder
98 KB	100 KB	2 KB
63 KB	64 KB	1 KB
31 KB	32 KB	1 KB
126 KB	128 KB	2 KB

Empirical Finding:

Best-Fit is Usually Not Best

Worst-Fit Allocation

Algorithm:

Scan the free list to find the largest hole
If the largest hole is large enough, allocate from it
The remainder becomes a new (still relatively large) hole

Time Complexity: O(n) for linear list; O(log n) or O(1) with size tracking.

Implementation:

worst_fit.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
/* Worst-Fit Allocation Implementation */
 
/**
 * Worst-Fit: Returns the largest hole, if it satisfies the request.
 * 
 * Time Complexity: O(n) without caching, O(1) with largest-hole cache
 * Space Complexity: O(1)
 */
Hole* worst_fit(Hole* free_list, uint32_t request_size) {
    Hole* worst = NULL;
    uint32_t worst_size = 0;
    
    Hole* current = free_list;
    
    while (current != NULL) {
        if (current->size > worst_size) {
            worst = current;
            worst_size = current->size;
        }
        current = current->next;
    }
    
    // Return only if large enough
    return (worst != NULL && worst_size >= request_size) ? worst : NULL;
}
 
/**
 * Optimized worst-fit with cached largest hole.
 * Requires updating cache on every allocation/deallocation.
 */
typedef struct {
    Hole* free_list;
    Hole* largest_hole;    // Cached pointer to largest hole
    uint32_t largest_size; // Cached size of largest hole
} OptimizedFreeList;
 
Hole* worst_fit_cached(OptimizedFreeList* fl, uint32_t request_size) {
    // O(1) check
    if (fl->largest_size >= request_size) {
        return fl->largest_hole;
    }
    return NULL;  // Even largest hole is too small
}
 
void update_largest_cache(OptimizedFreeList* fl) {
    fl->largest_hole = NULL;
    fl->largest_size = 0;
    
    Hole* current = fl->free_list;
    while (current != NULL) {
        if (current->size > fl->largest_size) {
            fl->largest_hole = current;
            fl->largest_size = current->size;
        }
        current = current->next;
    }
}
 
/*
 * Example trace:
 * 
 * Free list: 
 *   [15KB] -> [50KB] -> [8KB] -> [100KB] -> [25KB]
 * 
 * Request: 20KB
 * 
 * Find largest: 100KB hole
 * Allocate from 100KB hole
 * Remainder: 80KB hole (still large, usable for future requests)
 *
 * Compare to best-fit on same request:
 *   Would use 25KB hole, leaving only 5KB remainder
 */

Advantages

•Avoids tiny fragments — Remainders are relatively large
•Simple with caching — O(1) with largest-hole tracking
•Good for mixed sizes — Large holes can satisfy any request size

Disadvantages

•Rapidly fragments large holes — No large holes remain for large requests
•Poor for varying request sizes — Large requests eventually fail
•Medium holes accumulate — All holes converge to medium sizes
•Generally worst performance — Ironic but true

Why Worst-Fit Performs Worst:

The intuition behind worst-fit seems reasonable: large remainders should be more useful than small ones. But the strategy has a critical flaw: it destroys large holes.

Consider this sequence:

Time	Request	Largest Hole	After Allocation
T0	—	1000 KB	—
T1	50 KB	1000 KB	950 KB
T2	30 KB	950 KB	920 KB
T3	40 KB	920 KB	880 KB
T4	60 KB	880 KB	820 KB
...	...	...	...
Tn	500 KB	450 KB	FAILS

Each small allocation nibbles away at the only large hole. Eventually, no hole can satisfy large requests, even though significant total free memory exists.

Empirical Verdict:

Worst-fit consistently underperforms first-fit and best-fit in virtually all benchmarks. It is primarily of academic interest and is rarely used in production systems.

When Worst-Fit Makes Sense

Next-Fit Allocation

Algorithm:

Start from the last allocation's position (not from the head)
Scan forward, wrapping around if necessary
Allocate from the first hole large enough
Record the position for the next allocation

Time Complexity: O(n) worst case, often O(n/k) where k is the number of allocations per cycle.

Implementation:

next_fit.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
/* Next-Fit Allocation Implementation */
 
typedef struct CircularFreeList {
    Hole* head;
    Hole* last_allocated;  // Position to resume search
    uint32_t hole_count;
} CircularFreeList;
 
/**
 * Next-Fit: Start search from last allocation point.
 * Distributed load across memory, avoiding front-load of first-fit.
 * 
 * Time Complexity: O(n) worst case, often much better
 * Space Complexity: O(1)
 */
Hole* next_fit(CircularFreeList* fl, uint32_t request_size) {
    if (fl->head == NULL) {
        return NULL;
    }
    
    // Start from last allocated position, or head if none
    Hole* start = (fl->last_allocated != NULL) 
                  ? fl->last_allocated 
                  : fl->head;
    
    Hole* current = start;
    bool wrapped = false;
    
    do {
        if (current->size >= request_size) {
            fl->last_allocated = current;  // Update position
            return current;
        }
        
        current = current->next;
        
        // Wrap around to head if we reach the end
        if (current == NULL) {
            current = fl->head;
            wrapped = true;
        }
        
        // If we've wrapped and returned to start, no fit exists
        if (wrapped && current == start) {
            break;
        }
    } while (current != start);
    
    return NULL;  // No suitable hole found
}
 
/**
 * Alternative implementation with doubly-linked circular list.
 * Cleaner wraparound logic.
 */
typedef struct CircularHole {
    uint32_t start;
    uint32_t size;
    struct CircularHole* next;
    struct CircularHole* prev;
} CircularHole;
 
CircularHole* next_fit_circular(CircularHole** roving_ptr, 
                                 uint32_t request_size) {
    if (*roving_ptr == NULL) {
        return NULL;
    }
    
    CircularHole* start = *roving_ptr;
    CircularHole* current = start;
    
    do {
        if (current->size >= request_size) {
            // Move roving pointer to after this allocation
            *roving_ptr = current->next;
            return current;
        }
        current = current->next;
    } while (current != start);
    
    return NULL;  // Wrapped around, nothing fits
}
 
/*
 * Example trace with next-fit:
 * 
 * Circular free list (roving pointer at *):
 *   [10KB] -> *[25KB] -> [5KB] -> [30KB] -> [back to 10KB]
 * 
 * Request 1: 15KB
 *   Start at 25KB (roving pointer)
 *   25KB fits! Allocate, split to [10KB]
 *   Update roving to point to [5KB]
 * 
 * Request 2: 8KB
 *   Start at [5KB]
 *   5KB too small
 *   30KB fits! Allocate [8KB], leave [22KB]
 *   Update roving to point to [10KB] (wrapped)
 * 
 * Benefit: Allocations spread across memory rather than 
 *          clustering at front like first-fit.
 */

Advantages

•Distributes fragmentation — No single region becomes heavily fragmented
•Faster than first-fit — Avoids repeatedly scanning low-address holes
•More uniform memory usage — All regions get allocations

Disadvantages

•Slightly worse fragmentation — Doesn't keep low addresses clean
•Harder to coalesce — Adjacent holes may be visited separately
•State dependency — Behavior depends on roving pointer position

Comparison: First-Fit vs Next-Fit:

Aspect	First-Fit	Next-Fit
Fragmentation pattern	Concentrated at low addresses	Distributed evenly
Average search length	Shorter (if fits found early)	More uniform
Coalescing efficiency	Good (adjacent small holes at front)	Poorer (holes scattered)
Large hole preservation	Better (less disturbance at high addresses)	Worse (all regions used)
Overall fragmentation	Slightly better	Slightly worse

Verdict:

Comparative Analysis: Simulation Results

Decades of simulation studies and theoretical analysis have established clear performance rankings among allocation strategies. Here we consolidate the key findings.

Simulation Methodology:

Standard benchmarks model:

Random allocation requests with various size distributions
Random deallocation order (LIFO, FIFO, random)
Measurement of fragmentation, utilization, and search time over thousands of operations

Performance Summary:

Allocation Strategy Performance Comparison
Strategy	Memory Utilization	Fragmentation Level	Search Speed	Overall Rank
First-Fit	High (85-95%)	Moderate	Fast (avg)	1st - Best overall
Best-Fit	Moderate (80-90%)	High (many tiny holes)	Slow (must scan all)	3rd
Worst-Fit	Low (70-85%)	High (large holes destroyed)	Fast (with cache)	4th - Worst
Next-Fit	High (82-92%)	Moderate-High	Fast (distributed)	2nd

strategy_comparison.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
"""
Simulation comparing allocation strategies.
 
Simulates 100,000 allocation/deallocation operations
with uniform random sizes between 1KB and 64KB.
"""
 
import random
from collections import namedtuple
 
Result = namedtuple('Result', [
    'name',
    'avg_utilization',    # Average memory utilization %
    'avg_fragmentation',  # Average fragmentation index
    'failed_allocations', # Count of allocation failures
    'avg_search_length'   # Average holes scanned per allocation
])
 
def run_simulation(strategy, operations=100000, memory_size=10_000_000):
    """
    Run allocation simulation with given strategy.
    Returns Result tuple with performance metrics.
    """
    # Memory state
    holes = [(0, memory_size)]  # List of (start, size) tuples
    allocated = []               # List of (start, size) tuples
    
    # Metrics
    total_searches = 0
    search_count = 0
    failed_allocs = 0
    utilizations = []
    fragmentations = []
    
    for _ in range(operations):
        # 60% allocate, 40% deallocate
        if random.random() < 0.6 or not allocated:
            # Allocation
            size = random.randint(1000, 64000)
            result = strategy(holes, size)
            
            if result:
                hole_idx, searches = result
                total_searches += searches
                search_count += 1
                
                # Perform allocation
                start, hole_size = holes[hole_idx]
                allocated.append((start, size))
                
                if hole_size == size:
                    holes.pop(hole_idx)
                else:
                    holes[hole_idx] = (start + size, hole_size - size)
            else:
                failed_allocs += 1
        else:
            # Deallocation
            idx = random.randint(0, len(allocated) - 1)
            freed = allocated.pop(idx)
            
            # Add hole and coalesce
            holes.append(freed)
            holes = coalesce(sorted(holes))
        
        # Record metrics periodically
        if len(allocated) > 0 and len(holes) > 0:
            total_allocated = sum(s for _, s in allocated)
            total_free = sum(s for _, s in holes)
            largest_hole = max(s for _, s in holes)
            
            utilization = total_allocated / memory_size
            fragmentation = 1 - (largest_hole / max(total_free, 1))
            
            utilizations.append(utilization)
            fragmentations.append(fragmentation)
    
    return Result(
        name=strategy.__name__,
        avg_utilization=sum(utilizations)/len(utilizations) * 100,
        avg_fragmentation=sum(fragmentations)/len(fragmentations) * 100,
        failed_allocations=failed_allocs,
        avg_search_length=total_searches / max(search_count, 1)
    )
 
# Strategy implementations
def first_fit(holes, size):
    for i, (start, hole_size) in enumerate(holes):
        if hole_size >= size:
            return (i, i + 1)
    return None
 
def best_fit(holes, size):
    best_idx = None
    best_size = float('inf')
    searches = 0
    
    for i, (start, hole_size) in enumerate(holes):
        searches += 1
        if hole_size >= size and hole_size < best_size:
            best_idx = i
            best_size = hole_size
    
    return (best_idx, searches) if best_idx is not None else None
 
def worst_fit(holes, size):
    worst_idx = None
    worst_size = 0
    searches = 0
    
    for i, (start, hole_size) in enumerate(holes):
        searches += 1
        if hole_size > worst_size:
            worst_idx = i
            worst_size = hole_size
    
    if worst_idx is not None and worst_size >= size:
        return (worst_idx, searches)
    return None
 
# Run and compare
print("Strategy Comparison Results")
print("=" * 70)
 
for strategy in [first_fit, best_fit, worst_fit]:
    result = run_simulation(strategy)
    print(f"\n{result.name}:")
    print(f"  Avg Utilization:    {result.avg_utilization:.1f}%")
    print(f"  Avg Fragmentation:  {result.avg_fragmentation:.1f}%")
    print(f"  Failed Allocations: {result.failed_allocations}")
    print(f"  Avg Search Length:  {result.avg_search_length:.1f} holes")
 
"""
Typical Output:
 
first_fit:
  Avg Utilization:    89.2%
  Avg Fragmentation:  42.3%
  Failed Allocations: 156
  Avg Search Length:  4.2 holes
 
best_fit:
  Avg Utilization:    85.7%
  Avg Fragmentation:  58.9%
  Failed Allocations: 312
  Avg Search Length:  128.5 holes
 
worst_fit:
  Avg Utilization:    78.3%
  Avg Fragmentation:  61.7%
  Failed Allocations: 478
  Avg Search Length:  128.5 holes
"""

Key Findings:

First-fit wins overall — It balances search speed and fragmentation better than alternatives.
Best-fit underperforms — Despite minimizing per-allocation waste, it creates more unusable fragments.
Worst-fit is genuinely worst — It destroys large holes needed for large requests.
Next-fit is a good alternative — Slightly worse fragmentation but more uniform behavior.

Workload Sensitivity:

These results assume random workloads. Real systems often have patterns:

Web servers: Many small, similarly-sized allocations
Database systems: Mix of tiny and large allocations
Scientific computing: Few large, long-lived allocations

Strategy choice may vary with workload characteristics.

Modern Hybrid Strategies

Production memory allocators rarely use a single pure strategy. Instead, they combine multiple strategies to capture the benefits of each while mitigating their weaknesses.

Segregated Free Lists:

The most common modern approach maintains separate free lists for different size classes:

List[0]:  Blocks of size 16-31 bytes
List[1]:  Blocks of size 32-63 bytes
List[2]:  Blocks of size 64-127 bytes
...
List[n]:  Large blocks (overflow)

Allocation Process:

Round up request to next size class
Check appropriate list (O(1) if non-empty)
If empty, check larger size classes
If all empty, request from system or general pool

This is essentially best-fit with O(1) access — the size class naturally provides a close fit, and extracting any block from the list is instant.

hybrid_allocator.c
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
/* Modern hybrid allocation strategy */
 
#define NUM_SIZE_CLASSES  12
#define MIN_BLOCK_SIZE    16
#define LARGE_THRESHOLD   2048
 
typedef struct FreeBlock {
    struct FreeBlock* next;
    // Size is implicit from which list the block is in
} FreeBlock;
 
typedef struct {
    FreeBlock* small_lists[NUM_SIZE_CLASSES];  // Segregated lists
    Hole* large_list;                           // For large blocks
    uint32_t class_sizes[NUM_SIZE_CLASSES];
} HybridAllocator;
 
void init_allocator(HybridAllocator* alloc) {
    // Size classes: 16, 32, 64, 128, 256, 512, 1024, 2048, ...
    for (int i = 0; i < NUM_SIZE_CLASSES; i++) {
        alloc->small_lists[i] = NULL;
        alloc->class_sizes[i] = MIN_BLOCK_SIZE << i;
    }
    alloc->large_list = NULL;
}
 
int size_to_class(uint32_t size) {
    if (size <= MIN_BLOCK_SIZE) return 0;
    
    // Find ceiling log2
    int class_idx = 0;
    uint32_t threshold = MIN_BLOCK_SIZE;
    while (threshold < size && class_idx < NUM_SIZE_CLASSES - 1) {
        threshold <<= 1;
        class_idx++;
    }
    return class_idx;
}
 
/**
 * Hybrid allocation:
 * - Small requests: O(1) from segregated lists
 * - Large requests: First-fit from large list
 */
void* hybrid_allocate(HybridAllocator* alloc, uint32_t size) {
    if (size < LARGE_THRESHOLD) {
        // Small allocation: use segregated lists
        int target_class = size_to_class(size);
        
        // Try exact class first
        for (int c = target_class; c < NUM_SIZE_CLASSES; c++) {
            if (alloc->small_lists[c] != NULL) {
                FreeBlock* block = alloc->small_lists[c];
                alloc->small_lists[c] = block->next;
                return (void*)block;
            }
        }
        
        // Split from large list if all small lists empty
        Hole* hole = first_fit(alloc->large_list, 
                               alloc->class_sizes[target_class]);
        if (hole != NULL) {
            // Carve block from hole
            void* result = (void*)hole->start;
            hole->start += alloc->class_sizes[target_class];
            hole->size -= alloc->class_sizes[target_class];
            if (hole->size == 0) {
                remove_hole(alloc->large_list, hole);
            }
            return result;
        }
        
        return NULL;  // Out of memory
    } else {
        // Large allocation: first-fit from large list
        Hole* hole = first_fit(alloc->large_list, size);
        if (hole == NULL) return NULL;
        
        void* result = (void*)hole->start;
        if (hole->size == size) {
            remove_hole(alloc->large_list, hole);
        } else {
            hole->start += size;
            hole->size -= size;
        }
        return result;
    }
}
 
/**
 * Hybrid deallocation:
 * - Small blocks: O(1) return to appropriate list
 * - Large blocks: Return to large list with coalescing
 */
void hybrid_free(HybridAllocator* alloc, void* ptr, uint32_t size) {
    if (size < LARGE_THRESHOLD) {
        // Return to segregated list
        int class_idx = size_to_class(size);
        FreeBlock* block = (FreeBlock*)ptr;
        block->next = alloc->small_lists[class_idx];
        alloc->small_lists[class_idx] = block;
    } else {
        // Return to large list with coalescing
        add_hole_with_coalesce(&alloc->large_list, (uint32_t)ptr, size);
    }
}

Other Hybrid Techniques:

1. Buddy System (covered in later module): Power-of-two sized blocks with structured splitting and merging.

2. Slab Allocation: Pre-allocate pools of common object sizes (e.g., process structures, file handles). Used extensively in Linux kernel.

3. Thread-Local Caches: Each thread maintains private free lists. Allocations first check thread-local storage (no synchronization), falling back to global with work-stealing.

4. Size-Ordered + Address-Ordered Trees: Maintain both orderings with cross-references. Use size tree for best-fit search, address tree for coalescing.

The Modern Reality:

Choose Based on Workload

Summary: Partition Allocation Strategies

Key Takeaways

•First-fit is the overall winner — Despite simplicity, it outperforms more "clever" strategies in most scenarios.
•Best-fit creates unusable fragments — Minimizing per-allocation waste paradoxically increases total waste.
•Worst-fit destroys large holes — Never preserves capacity for large allocations.
•Next-fit distributes but fragments more — Solves first-fit's clustering at cost of slightly higher fragmentation.
•No pure strategy is optimal for all workloads — Real systems use hybrid approaches.
•Segregated free lists combine speed and fit — O(1) allocation with effective best-fit behavior.
•Strategy choice interacts with workload — Predictable sizes favor segregation; varied sizes favor first-fit.

What's Next:

Page Complete

4 / 5