Operating SystemsAllocation Strategies

Frame Allocation Strategies

LevelIntermediate

Duration60 mins

TopicAllocation Strategies

1 / 5

Equal Allocation

The Fairness Question in Memory Management

When multiple processes compete for a finite pool of physical memory frames, the operating system faces a fundamental question: How should these precious resources be divided? This question lies at the heart of memory management, and the answer profoundly impacts system performance, fairness, and stability.

The simplest answer—and our starting point in understanding allocation strategies—is equal allocation: give every process the same number of frames, regardless of their size, importance, or actual needs. While this approach may seem naive at first glance, understanding its mechanics, tradeoffs, and limitations provides the essential foundation for comprehending more sophisticated allocation schemes.

Equal allocation embodies a democratic principle: every process is equal in the eyes of the memory manager. But as we'll discover, this egalitarian approach, while elegant in its simplicity, often fails to match the complex reality of diverse workloads with vastly different memory requirements.

What You Will Learn

By the end of this page, you will deeply understand equal allocation: its mathematical formulation, implementation mechanisms, performance characteristics, and critical limitations. You will be able to analyze when equal allocation is appropriate, calculate frame distributions for any system configuration, and articulate precisely why more sophisticated strategies are often necessary.

The Fundamental Concept of Equal Allocation

Equal allocation is conceptually straightforward: if the system has m frames available for user processes and there are n active processes, each process receives ⌊m/n⌋ frames (the floor of m divided by n). Any remaining frames—typically fewer than n—are either kept in a free pool or distributed among processes using a secondary criterion.

This approach treats memory allocation like dividing a pie among diners: everyone gets an equal slice, regardless of appetite. The mathematical elegance of this formulation masks significant practical complexities that emerge when we consider real-world workloads.

Mathematical Foundation

For a system with m available frames and n processes:

Frames per process = ⌊m/n⌋ Leftover frames = m mod n

Example: With 93 frames and 5 processes, each process gets ⌊93/5⌋ = 18 frames, with 93 mod 5 = 3 frames remaining in the free pool.

The Implicit Assumptions

Equal allocation rests on several assumptions that are worth making explicit, as violations of these assumptions reveal the strategy's limitations:

Assumption 1: Homogeneous Memory Requirements — All processes need approximately the same amount of memory. In practice, this is almost never true. A small utility process might need 50KB while a database server needs 8GB.

Assumption 2: Equal Importance — All processes deserve equal treatment. In hierarchical systems with users, services, and critical infrastructure, this assumption often conflicts with organizational priorities.

Assumption 3: Static Process Count — The number of processes remains relatively stable. Frequent process creation and termination can cause allocation fluctuations that impact running processes.

Assumption 4: Adequate Total Memory — The total available memory is sufficient to give each process a viable allocation. When m/n falls below a process's minimum requirement, equal allocation fails entirely.

Equal Allocation Example: 100 Frames, Varying Process Counts
Processes (n)	Frames per Process	Leftover Frames	Notes
2	50	0	Generous allocation, likely wasteful
5	20	0	Reasonable for moderate-sized processes
10	10	0	Tight but workable for small processes
20	5	0	Marginal; may trigger thrashing
33	3	1	Below minimum for many processes
50	2	0	Critical: most processes will thrash
100	1	0	Failure: no process can function

The Minimum Frame Problem

A critical constraint on all allocation strategies—but one that equal allocation often violates—is the minimum frame requirement. Every process needs a certain minimum number of frames to execute even a single instruction. This minimum is architecturally determined and varies based on the instruction set architecture (ISA), addressing modes, and memory reference patterns.

Why Minimums Exist

Consider what happens when a single instruction executes. On many architectures, even a simple instruction like MOV [dest], [source] might require:

One frame for the instruction itself
One frame for the source operand (if in a different page)
One frame for the destination operand (if in yet another page)

If indirect addressing is involved, additional frames may be needed for pointer resolution. Some architectures with complex addressing modes (like the PDP-11's multiple levels of indirection) can require many frames for a single instruction.

Minimum Frame Analysis

Assembly (x86)

; Example: Instruction with multiple memory references
; Consider: MOV EAX, [EBX + ECX*4 + displacement]
;           MOV [EDI + ESI*2 + displacement], EAX
 
; Worst case memory references:
; 1. Instruction fetch (1-2 pages if instruction spans page boundary)
; 2. Source operand calculation and fetch (1-2 pages)
; 3. Destination operand calculation and store (1-2 pages)
; 
; Minimum frames needed: 3-6 frames depending on alignment
 
; For instructions with indirect addressing:
; MOV EAX, [[ptr]]  ; Double indirection
; 1. Instruction page
; 2. First pointer page
; 3. Second pointer page  
; 4. Final data page
; Minimum frames: 4
 
; x86-64 with RIP-relative addressing reduces some requirements
; but complex instructions still need multiple frames

Architectural Variation in Minimum Frames

Different architectures have different minimum frame requirements:

• IBM 370: 6 frames (MVC instruction can span 2 pages each for source, destination, and instruction) • PDP-11: Up to 7 frames (due to multi-level indirect addressing) • x86: 3-6 frames (depending on instruction complexity) • RISC architectures: Typically 2-3 frames (simpler addressing modes)

Equal allocation must never allocate fewer frames than the architectural minimum, or processes will fail immediately.

The Violation Scenario

Equal allocation can violate minimum frame requirements when:

Scenario 1: Too Many Processes — If n processes compete for m frames and m/n < minimum, equal allocation fails. With 50 frames, a minimum of 3, and 20 processes, equal allocation gives 2 frames per process—below the minimum.

Scenario 2: Dynamic Process Creation — A system running 10 processes with 100 frames (10 each) might seem healthy, but if 30 more processes start, allocation drops to 2.5 → 2 frames per process, potentially below the minimum.

Consequences of Violation:

Immediate page faults on every instruction
Complete inability to make forward progress
System appears hung or thrashing infinitely
Only solution: terminate processes to restore viable allocations

Minimum Frame Requirements by Architecture
Architecture	Minimum Frames	Determining Factor
IBM System/370	6	MVC instruction spans multiple pages
PDP-11	6-7	Multi-level indirect addressing
VAX	6	Complex memory-to-memory operations
Intel x86	3-6	Segment + page + data references
ARM	2-3	Load/store architecture, simpler addressing
MIPS	2	RISC design, fixed instruction format
RISC-V	2	Clean RISC design

Implementation Mechanics

Implementing equal allocation requires careful bookkeeping and efficient frame management. While the concept is simple, robust implementation must handle edge cases, maintain consistency, and integrate with the broader memory management subsystem.

Core Data Structures

Equal allocation typically relies on these data structures:

Process Frame Counter — Each process control block (PCB) contains a counter of currently allocated frames
Global Frame Pool — A list or bitmap of available frames
Process Count — Running count of active processes for allocation calculations
Minimum Frame Threshold — Architectural minimum, checked before allocation decisions

equal_allocation.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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
 
#define MAX_PROCESSES 256
#define TOTAL_FRAMES 1024
#define MIN_FRAMES_PER_PROCESS 3  // Architecture-dependent
 
// Frame pool management
typedef struct {
    int total_frames;           // Total physical frames available
    int free_frames;            // Currently unallocated frames
    int reserved_frames;        // Frames reserved for kernel/buffers
    int* frame_bitmap;          // 1 = allocated, 0 = free
} FramePool;
 
// Per-process allocation tracking
typedef struct {
    int pid;
    int allocated_frames;       // Current frame count
    int target_allocation;      // Equal allocation target
    bool active;
} ProcessAllocation;
 
// Global allocation state
typedef struct {
    FramePool frame_pool;
    ProcessAllocation processes[MAX_PROCESSES];
    int active_process_count;
    int frames_per_process;     // Current equal allocation quota
    int leftover_frames;        // Frames not evenly divisible
} AllocationState;
 
// Calculate equal allocation for all processes
void calculate_equal_allocation(AllocationState* state) {
    if (state->active_process_count == 0) {
        state->frames_per_process = 0;
        state->leftover_frames = 0;
        return;
    }
    
    int available = state->frame_pool.total_frames - 
                    state->frame_pool.reserved_frames;
    
    state->frames_per_process = available / state->active_process_count;
    state->leftover_frames = available % state->active_process_count;
    
    // Enforce minimum frame constraint
    if (state->frames_per_process < MIN_FRAMES_PER_PROCESS) {
        fprintf(stderr, 
            "WARNING: Equal allocation (%d frames) below minimum (%d)\n",
            state->frames_per_process, MIN_FRAMES_PER_PROCESS);
        
        // Calculate maximum processes supportable
        int max_processes = available / MIN_FRAMES_PER_PROCESS;
        fprintf(stderr, 
            "System can support at most %d processes with current memory\n",
            max_processes);
    }
}
 
// Allocate frames to a new process
int allocate_to_new_process(AllocationState* state, int pid) {
    // Find empty slot
    int slot = -1;
    for (int i = 0; i < MAX_PROCESSES; i++) {
        if (!state->processes[i].active) {
            slot = i;
            break;
        }
    }
    
    if (slot == -1) {
        return -1;  // No process slots available
    }
    
    // Register process
    state->processes[slot].pid = pid;
    state->processes[slot].active = true;
    state->processes[slot].allocated_frames = 0;
    state->active_process_count++;
    
    // Recalculate equal allocation for ALL processes
    calculate_equal_allocation(state);
    
    // Rebalance: may need to reclaim frames from other processes
    rebalance_allocations(state);
    
    return state->frames_per_process;
}
 
// Rebalance frames after process creation/termination
void rebalance_allocations(AllocationState* state) {
    int target = state->frames_per_process;
    
    // First pass: reclaim excess frames from over-allocated processes
    for (int i = 0; i < MAX_PROCESSES; i++) {
        if (!state->processes[i].active) continue;
        
        int excess = state->processes[i].allocated_frames - target;
        if (excess > 0) {
            // Reclaim excess frames (triggers page-out if needed)
            reclaim_frames(&state->processes[i], excess, &state->frame_pool);
        }
    }
    
    // Second pass: allocate to under-allocated processes
    for (int i = 0; i < MAX_PROCESSES; i++) {
        if (!state->processes[i].active) continue;
        
        int deficit = target - state->processes[i].allocated_frames;
        if (deficit > 0) {
            // Allocate additional frames
            grant_frames(&state->processes[i], deficit, &state->frame_pool);
        }
    }
    
    // Distribute leftover frames (optional: could use round-robin)
    distribute_leftovers(state);
}

Handling Leftover Frames

When m frames don't divide evenly among n processes, several strategies can distribute the remainder:

Strategy 1: Free Pool Reserve — Keep leftover frames in the free pool, available for demand paging spikes. Simple but wastes memory.

Strategy 2: Round-Robin Distribution — Distribute one extra frame to the first (m mod n) processes. Fair but requires tracking which processes received extras.

Strategy 3: Priority-Based Distribution — Give extras to higher-priority processes. Introduces priority considerations into an otherwise egalitarian scheme.

Strategy 4: First-Fault Allocation — Hold leftovers until page faults occur, then allocate to faulting processes. Adaptive but adds complexity.

Implementation Best Practice

Most production systems using equal allocation keep leftover frames in a free pool rather than distributing them. This provides a buffer for page fault handling and simplifies the implementation. The marginal efficiency loss (at most n-1 frames) is usually acceptable.

Dynamic Allocation Adjustments

In a real operating system, the process count changes continuously. Processes are created, terminate, get suspended, and resume. Each change potentially affects the equal allocation for all processes. Managing these transitions gracefully is crucial for system stability.

Process Creation Scenario

When a new process starts, equal allocation must:

Increment the active process count
Recalculate frames_per_process = ⌊m/n_new⌋
Determine how many frames must be reclaimed from existing processes
Select victim frames from each over-allocated process
Page out dirty victims to swap
Assign reclaimed frames to the new process
Initialize the new process's page table

Converting Mermaid diagram...

Process Termination Scenario

When a process terminates, equal allocation can distribute the freed frames:

Decrement the active process count
Reclaim all frames from the terminated process
Recalculate frames_per_process = ⌊m/n_remaining⌋
Distribute freed frames to under-allocated processes
Any remaining frames go to the free pool

The Thrashing Risk During Transitions

The period immediately after a new process starts is particularly dangerous. Existing processes have just lost frames and will immediately begin page faulting as they try to access pages that were evicted. The new process also starts with page faults as it loads its working set. This creates a page fault storm that can temporarily spike system load significantly.

Mitigation strategies include:

Gradual Rebalancing — Don't reclaim all excess frames immediately; spread the adjustment over time
Admission Control — Delay new process starts if the system is already under memory pressure
Burst Tolerance — Maintain a larger free pool to absorb transition spikes

gradual_rebalancing.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
#define REBALANCE_RATE 5  // Max frames to reclaim per interval
 
typedef struct {
    int pid;
    int current_allocation;
    int target_allocation;
    bool pending_adjustment;
} ProcessBalance;
 
// Gradual rebalancing to prevent page fault storms
void gradual_rebalance(AllocationState* state) {
    bool any_pending = false;
    
    for (int i = 0; i < MAX_PROCESSES; i++) {
        if (!state->processes[i].active) continue;
        
        ProcessBalance* pb = &state->processes[i].balance;
        int diff = pb->current_allocation - pb->target_allocation;
        
        if (diff > 0) {
            // Over-allocated: reclaim gradually
            int to_reclaim = (diff > REBALANCE_RATE) ? REBALANCE_RATE : diff;
            reclaim_frames(&state->processes[i], to_reclaim, &state->frame_pool);
            pb->current_allocation -= to_reclaim;
            pb->pending_adjustment = (diff > REBALANCE_RATE);
            any_pending |= pb->pending_adjustment;
            
        } else if (diff < 0) {
            // Under-allocated: grant if frames available
            int deficit = -diff;
            int to_grant = (deficit > REBALANCE_RATE) ? REBALANCE_RATE : deficit;
            int granted = grant_frames(&state->processes[i], to_grant, 
                                        &state->frame_pool);
            pb->current_allocation += granted;
            pb->pending_adjustment = (deficit > REBALANCE_RATE);
            any_pending |= pb->pending_adjustment;
        }
    }
    
    if (any_pending) {
        // Schedule another rebalance pass
        schedule_rebalance_timer(REBALANCE_INTERVAL_MS);
    }
}
 
// Admission control: check if new process can be accommodated
bool can_admit_process(AllocationState* state) {
    int available = state->frame_pool.total_frames - 
                    state->frame_pool.reserved_frames;
    int new_count = state->active_process_count + 1;
    int new_quota = available / new_count;
    
    // Check 1: Would violate minimum frame constraint?
    if (new_quota < MIN_FRAMES_PER_PROCESS) {
        return false;
    }
    
    // Check 2: Would cause excessive frame reclamation?
    int frames_to_reclaim = 0;
    for (int i = 0; i < MAX_PROCESSES; i++) {
        if (!state->processes[i].active) continue;
        int excess = state->processes[i].allocated_frames - new_quota;
        if (excess > 0) frames_to_reclaim += excess;
    }
    
    // Threshold: don't admit if reclaiming more than 20% of frames
    if (frames_to_reclaim > available * 0.2) {
        return false;  // System under memory pressure
    }
    
    return true;
}

Advantages and Appropriate Use Cases

Despite its limitations, equal allocation has genuine advantages that make it appropriate for certain scenarios. Understanding when to use equal allocation—and when to avoid it—is essential for system designers.

Key Advantages

Benefits of Equal Allocation

•Simplicity — Both conceptually and in implementation. The allocation decision is trivial: divide and distribute. No complex heuristics, no state tracking beyond frame counts.
•Fairness — Every process is treated identically, eliminating favoritism. This is particularly valuable in multi-user systems where perceived fairness matters.
•Predictability — Each process knows exactly how many frames it will receive. This aids performance analysis and capacity planning.
•Low Overhead — Minimal computation required. No need to analyze process behavior, track working sets, or adjust based on page fault rates.
•Easy Debugging — When problems occur, the allocation is transparent. No mysterious prioritization or dynamic adjustment to trace.
•Bounded Starvation — No process can monopolize memory at others' expense. Every process gets its fair share, preventing memory hogging.

Appropriate Use Cases

Equal allocation works well in specific scenarios:

Scenarios Favoring Equal Allocation
Scenario	Why Equal Allocation Works	Example
Homogeneous Workloads	All processes have similar memory needs	Batch processing of similar jobs
Educational/Teaching Systems	Simplicity aids understanding; fairness prevents grade disputes	University computer labs
Dedicated Single-Application Servers	All instances of same application have same requirements	Web server farm with identical worker processes
Resource-Constrained Embedded Systems	Predictable allocation simplifies real-time guarantees	Industrial controllers
Prototype/Development Systems	Quick implementation; behavior easy to analyze	Early-stage OS development

Historical Context

Early time-sharing systems like CTSS (Compatible Time-Sharing System) and Multics used variants of equal allocation. With limited memory and a focus on fair multi-user access, the simplicity and fairness of equal allocation outweighed its inefficiencies. As systems grew more sophisticated and workloads more diverse, proportional and dynamic allocation schemes became necessary.

Critical Limitations and Pathologies

Equal allocation's simplicity comes at a significant cost. In heterogeneous environments—which describe nearly all modern systems—equal allocation exhibits serious pathologies that can cripple system performance.

Fundamental Limitations

•Size Blindness — A 10MB process and a 1GB process receive identical allocations. The small process wastes frames while the large process thrashes.
•Priority Ignorance — Critical system services receive the same allocation as background tasks. A database server shares equally with a screen saver.
•Workload Insensitivity — A compute-bound process (minimal memory needs) gets the same allocation as a memory-intensive analytics job.
•Scaling Problems — As process count grows, per-process allocation shrinks until it falls below viable thresholds.
•Unfair Across Users — A user running one process gets the same total memory as a user running ten processes. The multi-process user's applications all suffer.
•Transition Disruption — Every process creation/termination affects all other processes, causing system-wide disturbance.

Quantifying the Waste: A Detailed Example

Consider a system with 1000 frames and these five processes:

Process	Virtual Size	Working Set	Equal Alloc (200 frames)
P1 (Editor)	50 pages	30 pages	200 frames (170 wasted)
P2 (Compiler)	800 pages	400 pages	200 frames (THRASHING)
P3 (DB Server)	2000 pages	600 pages	200 frames (SEVERE THRASHING)
P4 (Background)	20 pages	10 pages	200 frames (190 wasted)
P5 (Web Server)	300 pages	150 pages	200 frames (THRASHING)

With equal allocation:

360 frames wasted (P1 and P4 don't need their full allocation)
3 processes thrashing (P2, P3, P5 cannot fit their working sets)
System performance: catastrophic

With proportional allocation based on working set:

P1: 30 frames, P2: 400 frames, P3: 440 frames, P4: 10 frames, P5: 120 frames
Total: 1000 frames (fully utilized)
No process thrashing
System performance: optimal

The Equal Allocation Trap

Equal allocation creates a perverse incentive: running more processes makes every process slower, regardless of total memory demand. A user might have plenty of aggregate memory for their workload, but equal allocation prevents efficient distribution. This is particularly damaging in modern multi-process architectures (e.g., microservices, browser tabs, GUI applications with helper processes).

Comparison with Other Strategies

To fully appreciate equal allocation's tradeoffs, we must compare it against alternative strategies. This comparison also previews the more sophisticated approaches we'll explore in subsequent pages.

Frame Allocation Strategy Comparison
Criterion	Equal Allocation	Proportional	Priority-Based	Dynamic (Working Set)
Complexity	Very Low	Low	Medium	High
Fairness	Process-level equal	Size-proportional	Priority-weighted	Need-based
Adaptability	None	Static sizing only	Static priority only	Continuous adaptation
Overhead	Minimal	Low (process size tracking)	Low (priority tracking)	High (working set tracking)
Heterogeneous Workloads	Poor	Good	Good (if priorities set correctly)	Excellent
Thrashing Prevention	None	Limited	Limited	Strong
Implementation Effort	Trivial	Easy	Easy	Significant

When to Choose Equal Allocation

Choose equal allocation when:

Development/prototyping phase where simplicity trumps efficiency
Homogeneous workloads with similar memory requirements
Fairness guarantees are legally or contractually required
System complexity budget is exhausted
Real-time predictability is more important than optimal utilization

When to Avoid Equal Allocation

Avoid equal allocation when:

Processes have significantly different sizes (>10x variation)
Different priority levels exist among processes
System operates near memory capacity
Performance optimization is a priority
Workloads are dynamic and variable

Modern System Reality

No major production operating system uses pure equal allocation today. Linux uses a complex combination of proportional allocation, working set tracking, and priority-based adjustments. Windows uses working set management with trimming. Even embedded RTOSes typically use fixed per-process allocations (predetermined, not equal). Equal allocation remains valuable as a conceptual baseline and for understanding why more sophisticated approaches are necessary.

Summary and Key Takeaways

We have conducted an exhaustive examination of equal allocation, the foundational frame allocation strategy. Let's consolidate the critical insights:

Core Concepts Mastered

•Mathematical Foundation — Equal allocation gives each process ⌊m/n⌋ frames, where m is available frames and n is process count. Leftover frames (m mod n) typically remain in a free pool.
•Minimum Frame Constraint — Every architecture imposes a minimum frame requirement (typically 2-7 frames). Equal allocation can violate this constraint when process counts are high.
•Implementation Mechanics — Implementation requires process tracking, frame pool management, and rebalancing logic for process creation/termination events.
•Dynamic Adjustment Challenges — Process transitions cause system-wide disruption as frames are reclaimed and redistributed. Gradual rebalancing and admission control can mitigate impact.
•Appropriate Use Cases — Equal allocation suits homogeneous workloads, educational systems, and scenarios where simplicity and fairness outweigh efficiency.
•Critical Limitations — Size blindness, priority ignorance, and scaling problems make equal allocation unsuitable for heterogeneous production workloads.
•Comparison Context — Equal allocation is the simplest but least adaptive strategy. Proportional, priority-based, and dynamic strategies address its limitations at the cost of added complexity.

Looking Ahead

Equal allocation's fundamental insight—that frames must be explicitly distributed among processes—remains valid. Its limitation—treating all processes identically—motivates the strategies we'll explore next.

In the following page, we examine proportional allocation, which addresses equal allocation's size blindness by distributing frames in proportion to process sizes. This seemingly simple adjustment dramatically improves utilization in heterogeneous workloads while maintaining implementation simplicity.

Page Complete

You now possess a complete understanding of equal allocation: its mathematical formulation, implementation requirements, advantages, limitations, and appropriate use cases. This foundation enables you to appreciate why more sophisticated allocation strategies are necessary and how they improve upon equal allocation's baseline approach.

1 / 5

Loading learning content...

Operating SystemsAllocation Strategies

Frame Allocation Strategies

LevelIntermediate

Duration60 mins

TopicAllocation Strategies

1 / 5

Equal Allocation

The Fairness Question in Memory Management

What You Will Learn

The Fundamental Concept of Equal Allocation

Mathematical Foundation

For a system with m available frames and n processes:

Frames per process = ⌊m/n⌋ Leftover frames = m mod n

Example: With 93 frames and 5 processes, each process gets ⌊93/5⌋ = 18 frames, with 93 mod 5 = 3 frames remaining in the free pool.

The Implicit Assumptions

Equal allocation rests on several assumptions that are worth making explicit, as violations of these assumptions reveal the strategy's limitations:

Equal Allocation Example: 100 Frames, Varying Process Counts
Processes (n)	Frames per Process	Leftover Frames	Notes
2	50	0	Generous allocation, likely wasteful
5	20	0	Reasonable for moderate-sized processes
10	10	0	Tight but workable for small processes
20	5	0	Marginal; may trigger thrashing
33	3	1	Below minimum for many processes
50	2	0	Critical: most processes will thrash
100	1	0	Failure: no process can function

The Minimum Frame Problem

Why Minimums Exist

Consider what happens when a single instruction executes. On many architectures, even a simple instruction like MOV [dest], [source] might require:

One frame for the instruction itself
One frame for the source operand (if in a different page)
One frame for the destination operand (if in yet another page)

Minimum Frame Analysis

Assembly (x86)

; Example: Instruction with multiple memory references
; Consider: MOV EAX, [EBX + ECX*4 + displacement]
;           MOV [EDI + ESI*2 + displacement], EAX
 
; Worst case memory references:
; 1. Instruction fetch (1-2 pages if instruction spans page boundary)
; 2. Source operand calculation and fetch (1-2 pages)
; 3. Destination operand calculation and store (1-2 pages)
; 
; Minimum frames needed: 3-6 frames depending on alignment
 
; For instructions with indirect addressing:
; MOV EAX, [[ptr]]  ; Double indirection
; 1. Instruction page
; 2. First pointer page
; 3. Second pointer page  
; 4. Final data page
; Minimum frames: 4
 
; x86-64 with RIP-relative addressing reduces some requirements
; but complex instructions still need multiple frames

Architectural Variation in Minimum Frames

Different architectures have different minimum frame requirements:

Equal allocation must never allocate fewer frames than the architectural minimum, or processes will fail immediately.

The Violation Scenario

Equal allocation can violate minimum frame requirements when:

Consequences of Violation:

Immediate page faults on every instruction
Complete inability to make forward progress
System appears hung or thrashing infinitely
Only solution: terminate processes to restore viable allocations

Minimum Frame Requirements by Architecture
Architecture	Minimum Frames	Determining Factor
IBM System/370	6	MVC instruction spans multiple pages
PDP-11	6-7	Multi-level indirect addressing
VAX	6	Complex memory-to-memory operations
Intel x86	3-6	Segment + page + data references
ARM	2-3	Load/store architecture, simpler addressing
MIPS	2	RISC design, fixed instruction format
RISC-V	2	Clean RISC design

Implementation Mechanics

Core Data Structures

Equal allocation typically relies on these data structures:

Process Frame Counter — Each process control block (PCB) contains a counter of currently allocated frames
Global Frame Pool — A list or bitmap of available frames
Process Count — Running count of active processes for allocation calculations
Minimum Frame Threshold — Architectural minimum, checked before allocation decisions

equal_allocation.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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
 
#define MAX_PROCESSES 256
#define TOTAL_FRAMES 1024
#define MIN_FRAMES_PER_PROCESS 3  // Architecture-dependent
 
// Frame pool management
typedef struct {
    int total_frames;           // Total physical frames available
    int free_frames;            // Currently unallocated frames
    int reserved_frames;        // Frames reserved for kernel/buffers
    int* frame_bitmap;          // 1 = allocated, 0 = free
} FramePool;
 
// Per-process allocation tracking
typedef struct {
    int pid;
    int allocated_frames;       // Current frame count
    int target_allocation;      // Equal allocation target
    bool active;
} ProcessAllocation;
 
// Global allocation state
typedef struct {
    FramePool frame_pool;
    ProcessAllocation processes[MAX_PROCESSES];
    int active_process_count;
    int frames_per_process;     // Current equal allocation quota
    int leftover_frames;        // Frames not evenly divisible
} AllocationState;
 
// Calculate equal allocation for all processes
void calculate_equal_allocation(AllocationState* state) {
    if (state->active_process_count == 0) {
        state->frames_per_process = 0;
        state->leftover_frames = 0;
        return;
    }
    
    int available = state->frame_pool.total_frames - 
                    state->frame_pool.reserved_frames;
    
    state->frames_per_process = available / state->active_process_count;
    state->leftover_frames = available % state->active_process_count;
    
    // Enforce minimum frame constraint
    if (state->frames_per_process < MIN_FRAMES_PER_PROCESS) {
        fprintf(stderr, 
            "WARNING: Equal allocation (%d frames) below minimum (%d)\n",
            state->frames_per_process, MIN_FRAMES_PER_PROCESS);
        
        // Calculate maximum processes supportable
        int max_processes = available / MIN_FRAMES_PER_PROCESS;
        fprintf(stderr, 
            "System can support at most %d processes with current memory\n",
            max_processes);
    }
}
 
// Allocate frames to a new process
int allocate_to_new_process(AllocationState* state, int pid) {
    // Find empty slot
    int slot = -1;
    for (int i = 0; i < MAX_PROCESSES; i++) {
        if (!state->processes[i].active) {
            slot = i;
            break;
        }
    }
    
    if (slot == -1) {
        return -1;  // No process slots available
    }
    
    // Register process
    state->processes[slot].pid = pid;
    state->processes[slot].active = true;
    state->processes[slot].allocated_frames = 0;
    state->active_process_count++;
    
    // Recalculate equal allocation for ALL processes
    calculate_equal_allocation(state);
    
    // Rebalance: may need to reclaim frames from other processes
    rebalance_allocations(state);
    
    return state->frames_per_process;
}
 
// Rebalance frames after process creation/termination
void rebalance_allocations(AllocationState* state) {
    int target = state->frames_per_process;
    
    // First pass: reclaim excess frames from over-allocated processes
    for (int i = 0; i < MAX_PROCESSES; i++) {
        if (!state->processes[i].active) continue;
        
        int excess = state->processes[i].allocated_frames - target;
        if (excess > 0) {
            // Reclaim excess frames (triggers page-out if needed)
            reclaim_frames(&state->processes[i], excess, &state->frame_pool);
        }
    }
    
    // Second pass: allocate to under-allocated processes
    for (int i = 0; i < MAX_PROCESSES; i++) {
        if (!state->processes[i].active) continue;
        
        int deficit = target - state->processes[i].allocated_frames;
        if (deficit > 0) {
            // Allocate additional frames
            grant_frames(&state->processes[i], deficit, &state->frame_pool);
        }
    }
    
    // Distribute leftover frames (optional: could use round-robin)
    distribute_leftovers(state);
}

Handling Leftover Frames

When m frames don't divide evenly among n processes, several strategies can distribute the remainder:

Strategy 1: Free Pool Reserve — Keep leftover frames in the free pool, available for demand paging spikes. Simple but wastes memory.

Strategy 2: Round-Robin Distribution — Distribute one extra frame to the first (m mod n) processes. Fair but requires tracking which processes received extras.

Strategy 3: Priority-Based Distribution — Give extras to higher-priority processes. Introduces priority considerations into an otherwise egalitarian scheme.

Strategy 4: First-Fault Allocation — Hold leftovers until page faults occur, then allocate to faulting processes. Adaptive but adds complexity.

Implementation Best Practice

Dynamic Allocation Adjustments

Process Creation Scenario

When a new process starts, equal allocation must:

Increment the active process count
Recalculate frames_per_process = ⌊m/n_new⌋
Determine how many frames must be reclaimed from existing processes
Select victim frames from each over-allocated process
Page out dirty victims to swap
Assign reclaimed frames to the new process
Initialize the new process's page table

Converting Mermaid diagram...

Process Termination Scenario

When a process terminates, equal allocation can distribute the freed frames:

Decrement the active process count
Reclaim all frames from the terminated process
Recalculate frames_per_process = ⌊m/n_remaining⌋
Distribute freed frames to under-allocated processes
Any remaining frames go to the free pool

The Thrashing Risk During Transitions

Mitigation strategies include:

Gradual Rebalancing — Don't reclaim all excess frames immediately; spread the adjustment over time
Admission Control — Delay new process starts if the system is already under memory pressure
Burst Tolerance — Maintain a larger free pool to absorb transition spikes

gradual_rebalancing.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
#define REBALANCE_RATE 5  // Max frames to reclaim per interval
 
typedef struct {
    int pid;
    int current_allocation;
    int target_allocation;
    bool pending_adjustment;
} ProcessBalance;
 
// Gradual rebalancing to prevent page fault storms
void gradual_rebalance(AllocationState* state) {
    bool any_pending = false;
    
    for (int i = 0; i < MAX_PROCESSES; i++) {
        if (!state->processes[i].active) continue;
        
        ProcessBalance* pb = &state->processes[i].balance;
        int diff = pb->current_allocation - pb->target_allocation;
        
        if (diff > 0) {
            // Over-allocated: reclaim gradually
            int to_reclaim = (diff > REBALANCE_RATE) ? REBALANCE_RATE : diff;
            reclaim_frames(&state->processes[i], to_reclaim, &state->frame_pool);
            pb->current_allocation -= to_reclaim;
            pb->pending_adjustment = (diff > REBALANCE_RATE);
            any_pending |= pb->pending_adjustment;
            
        } else if (diff < 0) {
            // Under-allocated: grant if frames available
            int deficit = -diff;
            int to_grant = (deficit > REBALANCE_RATE) ? REBALANCE_RATE : deficit;
            int granted = grant_frames(&state->processes[i], to_grant, 
                                        &state->frame_pool);
            pb->current_allocation += granted;
            pb->pending_adjustment = (deficit > REBALANCE_RATE);
            any_pending |= pb->pending_adjustment;
        }
    }
    
    if (any_pending) {
        // Schedule another rebalance pass
        schedule_rebalance_timer(REBALANCE_INTERVAL_MS);
    }
}
 
// Admission control: check if new process can be accommodated
bool can_admit_process(AllocationState* state) {
    int available = state->frame_pool.total_frames - 
                    state->frame_pool.reserved_frames;
    int new_count = state->active_process_count + 1;
    int new_quota = available / new_count;
    
    // Check 1: Would violate minimum frame constraint?
    if (new_quota < MIN_FRAMES_PER_PROCESS) {
        return false;
    }
    
    // Check 2: Would cause excessive frame reclamation?
    int frames_to_reclaim = 0;
    for (int i = 0; i < MAX_PROCESSES; i++) {
        if (!state->processes[i].active) continue;
        int excess = state->processes[i].allocated_frames - new_quota;
        if (excess > 0) frames_to_reclaim += excess;
    }
    
    // Threshold: don't admit if reclaiming more than 20% of frames
    if (frames_to_reclaim > available * 0.2) {
        return false;  // System under memory pressure
    }
    
    return true;
}

Advantages and Appropriate Use Cases

Key Advantages

Benefits of Equal Allocation

•Simplicity — Both conceptually and in implementation. The allocation decision is trivial: divide and distribute. No complex heuristics, no state tracking beyond frame counts.
•Fairness — Every process is treated identically, eliminating favoritism. This is particularly valuable in multi-user systems where perceived fairness matters.
•Predictability — Each process knows exactly how many frames it will receive. This aids performance analysis and capacity planning.
•Low Overhead — Minimal computation required. No need to analyze process behavior, track working sets, or adjust based on page fault rates.
•Easy Debugging — When problems occur, the allocation is transparent. No mysterious prioritization or dynamic adjustment to trace.
•Bounded Starvation — No process can monopolize memory at others' expense. Every process gets its fair share, preventing memory hogging.

Appropriate Use Cases

Equal allocation works well in specific scenarios:

Scenarios Favoring Equal Allocation
Scenario	Why Equal Allocation Works	Example
Homogeneous Workloads	All processes have similar memory needs	Batch processing of similar jobs
Educational/Teaching Systems	Simplicity aids understanding; fairness prevents grade disputes	University computer labs
Dedicated Single-Application Servers	All instances of same application have same requirements	Web server farm with identical worker processes
Resource-Constrained Embedded Systems	Predictable allocation simplifies real-time guarantees	Industrial controllers
Prototype/Development Systems	Quick implementation; behavior easy to analyze	Early-stage OS development

Historical Context

Critical Limitations and Pathologies

Fundamental Limitations

•Size Blindness — A 10MB process and a 1GB process receive identical allocations. The small process wastes frames while the large process thrashes.
•Priority Ignorance — Critical system services receive the same allocation as background tasks. A database server shares equally with a screen saver.
•Workload Insensitivity — A compute-bound process (minimal memory needs) gets the same allocation as a memory-intensive analytics job.
•Scaling Problems — As process count grows, per-process allocation shrinks until it falls below viable thresholds.
•Unfair Across Users — A user running one process gets the same total memory as a user running ten processes. The multi-process user's applications all suffer.
•Transition Disruption — Every process creation/termination affects all other processes, causing system-wide disturbance.

Quantifying the Waste: A Detailed Example

Consider a system with 1000 frames and these five processes:

Process	Virtual Size	Working Set	Equal Alloc (200 frames)
P1 (Editor)	50 pages	30 pages	200 frames (170 wasted)
P2 (Compiler)	800 pages	400 pages	200 frames (THRASHING)
P3 (DB Server)	2000 pages	600 pages	200 frames (SEVERE THRASHING)
P4 (Background)	20 pages	10 pages	200 frames (190 wasted)
P5 (Web Server)	300 pages	150 pages	200 frames (THRASHING)

With equal allocation:

360 frames wasted (P1 and P4 don't need their full allocation)
3 processes thrashing (P2, P3, P5 cannot fit their working sets)
System performance: catastrophic

With proportional allocation based on working set:

P1: 30 frames, P2: 400 frames, P3: 440 frames, P4: 10 frames, P5: 120 frames
Total: 1000 frames (fully utilized)
No process thrashing
System performance: optimal

The Equal Allocation Trap

Comparison with Other Strategies

To fully appreciate equal allocation's tradeoffs, we must compare it against alternative strategies. This comparison also previews the more sophisticated approaches we'll explore in subsequent pages.

Frame Allocation Strategy Comparison
Criterion	Equal Allocation	Proportional	Priority-Based	Dynamic (Working Set)
Complexity	Very Low	Low	Medium	High
Fairness	Process-level equal	Size-proportional	Priority-weighted	Need-based
Adaptability	None	Static sizing only	Static priority only	Continuous adaptation
Overhead	Minimal	Low (process size tracking)	Low (priority tracking)	High (working set tracking)
Heterogeneous Workloads	Poor	Good	Good (if priorities set correctly)	Excellent
Thrashing Prevention	None	Limited	Limited	Strong
Implementation Effort	Trivial	Easy	Easy	Significant

When to Choose Equal Allocation

Choose equal allocation when:

Development/prototyping phase where simplicity trumps efficiency
Homogeneous workloads with similar memory requirements
Fairness guarantees are legally or contractually required
System complexity budget is exhausted
Real-time predictability is more important than optimal utilization

When to Avoid Equal Allocation

Avoid equal allocation when:

Processes have significantly different sizes (>10x variation)
Different priority levels exist among processes
System operates near memory capacity
Performance optimization is a priority
Workloads are dynamic and variable

Modern System Reality

Summary and Key Takeaways

We have conducted an exhaustive examination of equal allocation, the foundational frame allocation strategy. Let's consolidate the critical insights:

Core Concepts Mastered

•Mathematical Foundation — Equal allocation gives each process ⌊m/n⌋ frames, where m is available frames and n is process count. Leftover frames (m mod n) typically remain in a free pool.
•Minimum Frame Constraint — Every architecture imposes a minimum frame requirement (typically 2-7 frames). Equal allocation can violate this constraint when process counts are high.
•Implementation Mechanics — Implementation requires process tracking, frame pool management, and rebalancing logic for process creation/termination events.
•Dynamic Adjustment Challenges — Process transitions cause system-wide disruption as frames are reclaimed and redistributed. Gradual rebalancing and admission control can mitigate impact.
•Appropriate Use Cases — Equal allocation suits homogeneous workloads, educational systems, and scenarios where simplicity and fairness outweigh efficiency.
•Critical Limitations — Size blindness, priority ignorance, and scaling problems make equal allocation unsuitable for heterogeneous production workloads.
•Comparison Context — Equal allocation is the simplest but least adaptive strategy. Proportional, priority-based, and dynamic strategies address its limitations at the cost of added complexity.

Looking Ahead

Page Complete

1 / 5