Operating SystemsAllocation Strategies

Frame Allocation Strategies

LevelIntermediate

Duration60 mins

TopicAllocation Strategies

2 / 5

Proportional Allocation

Size Matters: A More Intelligent Distribution

Equal allocation's fundamental flaw is size blindness—it ignores that processes have dramatically different memory requirements. A text editor with 50 pages of virtual memory and a database server with 2000 pages receive identical frame allocations, leading to massive waste for the small process and catastrophic thrashing for the large one.

Proportional allocation addresses this by distributing frames in proportion to process sizes. Larger processes receive more frames; smaller processes receive fewer. This intuitive approach aligns resource allocation with resource need, dramatically improving utilization in heterogeneous workloads.

The principle mirrors everyday fairness concepts: when dividing a resource, allocation should reflect need or entitlement, not arbitrary equality. A family of four reasonably expects more from a shared resource than a single individual. Similarly, a 1GB application reasonably needs more memory frames than a 10MB utility.

What You Will Learn

By the end of this page, you will master proportional allocation: its mathematical formulation, implementation strategies, variants based on different size metrics, handling of edge cases, and critical analysis of its strengths and weaknesses. You will be able to calculate proportional allocations for any system configuration and understand when proportional allocation excels versus when more sophisticated approaches are needed.

Mathematical Foundation

Proportional allocation uses a straightforward mathematical formula that scales elegantly regardless of process count or system size.

Core Formula

For a system with:

m = total available frames
n = number of processes
sᵢ = size of process i (in pages or bytes)
S = Σsᵢ = total size of all processes

The allocation for process i is:

aᵢ = (sᵢ / S) × m

Alternatively: aᵢ = sᵢ × (m / S)

This gives each process a fraction of total memory proportional to its fraction of total demand. If a process represents 30% of total memory demand, it receives approximately 30% of available frames.

Rounding Considerations

Since frame counts must be integers, the calculated allocation aᵢ must be rounded. Common approaches:

• Floor: aᵢ = ⌊(sᵢ / S) × m⌋ — Ensures we don't over-allocate; leftover frames go to free pool • Round: aᵢ = round((sᵢ / S) × m) — Minimizes total rounding error • Floor with redistribution: Floor all, then distribute remainder to largest processes

The choice affects edge cases but rarely matters significantly for large m.

Worked Example

Consider a system with 124 available frames and 5 processes:

Process	Size (pages)	Proportion	Raw Allocation	Rounded (floor)
P1	10	10/137 ≈ 7.3%	9.05	9
P2	25	25/137 ≈ 18.2%	22.63	22
P3	42	42/137 ≈ 30.7%	38.02	38
P4	35	35/137 ≈ 25.5%	31.68	31
P5	25	25/137 ≈ 18.2%	22.63	22
Total	137	100%	124	122

Total allocated: 122 frames. Remainder: 2 frames (kept in free pool or distributed).

Verification: Each process's allocation closely matches its proportion of total process size. P3, the largest process (30.7% of demand), receives 30.6% of frames (38/124).

proportional_calculation.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
from dataclasses import dataclass
from typing import List, Tuple
import math
 
@dataclass
class Process:
    pid: int
    size: int  # Virtual memory size in pages
    allocation: int = 0  # Assigned frames
 
def calculate_proportional_allocation(
    processes: List[Process],
    total_frames: int,
    min_frames: int = 3
) -> Tuple[List[Process], int]:
    """
    Calculate proportional frame allocation for all processes.
    
    Args:
        processes: List of processes with their sizes
        total_frames: Total available physical frames
        min_frames: Minimum frames per process (architectural constraint)
    
    Returns:
        Tuple of (updated process list, leftover frames)
    """
    if not processes:
        return processes, total_frames
    
    # Calculate total size demand
    total_size = sum(p.size for p in processes)
    
    if total_size == 0:
        # Edge case: all processes have zero size
        # Fall back to equal allocation
        per_process = total_frames // len(processes)
        for p in processes:
            p.allocation = max(per_process, min_frames)
        return processes, total_frames - sum(p.allocation for p in processes)
    
    # First pass: calculate raw proportional allocations
    allocations = []
    for p in processes:
        # Raw allocation (may be fractional)
        raw = (p.size / total_size) * total_frames
        # Floor to get integer
        floored = math.floor(raw)
        # Track fractional part for redistribution
        fractional = raw - floored
        allocations.append((p, floored, fractional))
    
    # Enforce minimum frame constraint
    for i, (p, alloc, frac) in enumerate(allocations):
        if alloc < min_frames:
            allocations[i] = (p, min_frames, 0)  # Bump to minimum, no fractional
    
    # Calculate total allocated and remaining
    total_allocated = sum(alloc for _, alloc, _ in allocations)
    remaining = total_frames - total_allocated
    
    # Check for over-allocation (can happen if many processes need minimum)
    if remaining < 0:
        raise ValueError(
            f"Cannot satisfy minimum frames ({min_frames}) for "
            f"{len(processes)} processes with {total_frames} frames. "
            f"Need at least {len(processes) * min_frames} frames."
        )
    
    # Redistribute remaining frames based on fractional parts
    # Sort by fractional part (descending) to distribute fairly
    sorted_by_fraction = sorted(
        enumerate(allocations), 
        key=lambda x: x[1][2], 
        reverse=True
    )
    
    for i in range(remaining):
        idx = sorted_by_fraction[i % len(sorted_by_fraction)][0]
        p, alloc, frac = allocations[idx]
        allocations[idx] = (p, alloc + 1, frac)
    
    # Apply allocations to processes
    for p, alloc, _ in allocations:
        p.allocation = alloc
    
    # Recalculate actual remaining
    final_remaining = total_frames - sum(p.allocation for p in processes)
    
    return processes, final_remaining
 
# Example usage
if __name__ == "__main__":
    processes = [
        Process(pid=1, size=10),
        Process(pid=2, size=25),
        Process(pid=3, size=42),
        Process(pid=4, size=35),
        Process(pid=5, size=25),
    ]
    
    updated, remaining = calculate_proportional_allocation(processes, 124)
    
    print("Proportional Allocation Results:")
    print("-" * 50)
    total_size = sum(p.size for p in processes)
    for p in updated:
        proportion = p.size / total_size * 100
        alloc_pct = p.allocation / 124 * 100
        print(f"P{p.pid}: size={p.size:3d} ({proportion:5.1f}%) -> "
              f"{p.allocation:3d} frames ({alloc_pct:5.1f}%)")
    print(f"\nTotal allocated: {124 - remaining}")
    print(f"Remaining in free pool: {remaining}")

What Constitutes 'Size'?

A critical design decision in proportional allocation is: What metric defines process 'size'? Different definitions lead to different allocation behaviors, each with distinct advantages and drawbacks.

Option 1: Virtual Memory Size

The simplest definition: sᵢ = total virtual pages allocated to process i.

Advantages:

Easy to determine (sum of virtual memory regions)
Static and stable (doesn't fluctuate during execution)
Reflects programmer/application intent

Disadvantages:

Virtual size ≠ actual usage (sparse address spaces common)
Process may allocate large virtual regions but use tiny fractions
Stack/heap reservations inflate size artificially

Size Metrics for Proportional Allocation
Metric	Definition	Pros	Cons
Virtual Memory Size	Total virtual pages	Simple, stable, deterministic	Doesn't reflect actual usage
Resident Set Size (RSS)	Pages currently in memory	Reflects current usage	Circular: allocation affects RSS
Working Set Size	Recently-accessed pages	Reflects actual need	Complex to track, dynamic
Maximum RSS	Peak memory usage	Captures burst needs	May over-allocate for steady state
Requested Size	Application-specified	Respects app knowledge	Apps may lie/exaggerate

Option 2: Resident Set Size (RSS)

Use the current number of pages actually resident in memory as the size metric.

Advantages:

Reflects actual current memory footprint
Automatically adapts as usage changes
Honest measure (can't be inflated by virtual reservations)

Disadvantages:

Circular dependency: RSS depends on allocation, but allocation depends on RSS
Startup processes have RSS=0, so receive minimal allocation
Fluctuates, causing allocation instability

Option 3: Working Set Size (WSS)

Use the estimated working set (pages accessed in recent window) as size.

Advantages:

Best reflects actual memory need
Automatically adapts to phase changes in program behavior
Minimizes wasted allocation

Disadvantages:

Computationally expensive to track
Requires reference bit manipulation or sampling
Still subject to fluctuation

Practical Recommendation

Most production systems use virtual memory size for initial/static allocation and RSS or working set for dynamic adjustment. This provides stable baseline allocation while remaining responsive to actual behavior. The combination—proportional static allocation plus dynamic adjustment—captures the benefits of multiple metrics.

size_metrics.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
#include <stdio.h>
#include <stdint.h>
 
typedef struct {
    int pid;
    
    // Different size metrics
    size_t virtual_size;      // Total virtual address space
    size_t rss;               // Current resident set
    size_t peak_rss;          // Maximum observed RSS
    size_t working_set;       // Estimated working set
    size_t requested_size;    // Application-requested quota
    
    // Derived allocation
    size_t allocated_frames;
} ProcessSizeMetrics;
 
typedef enum {
    SIZE_METRIC_VIRTUAL,
    SIZE_METRIC_RSS,
    SIZE_METRIC_PEAK_RSS,
    SIZE_METRIC_WORKING_SET,
    SIZE_METRIC_REQUESTED,
    SIZE_METRIC_HYBRID          // Weighted combination
} SizeMetricType;
 
// Get size value based on selected metric
size_t get_process_size(ProcessSizeMetrics* proc, SizeMetricType metric) {
    switch (metric) {
        case SIZE_METRIC_VIRTUAL:
            return proc->virtual_size;
            
        case SIZE_METRIC_RSS:
            return proc->rss;
            
        case SIZE_METRIC_PEAK_RSS:
            return proc->peak_rss;
            
        case SIZE_METRIC_WORKING_SET:
            return proc->working_set;
            
        case SIZE_METRIC_REQUESTED:
            return proc->requested_size;
            
        case SIZE_METRIC_HYBRID:
            // Weighted combination: 50% working set, 30% RSS, 20% virtual
            return (proc->working_set * 50 + 
                    proc->rss * 30 + 
                    proc->virtual_size * 20) / 100;
            
        default:
            return proc->virtual_size;
    }
}
 
// Calculate proportional allocation with configurable size metric
void calculate_proportional_with_metric(
    ProcessSizeMetrics* processes,
    int process_count,
    size_t total_frames,
    SizeMetricType metric
) {
    // Calculate total size using selected metric
    size_t total_size = 0;
    for (int i = 0; i < process_count; i++) {
        total_size += get_process_size(&processes[i], metric);
    }
    
    if (total_size == 0) {
        // Fallback to equal allocation
        size_t per_process = total_frames / process_count;
        for (int i = 0; i < process_count; i++) {
            processes[i].allocated_frames = per_process;
        }
        return;
    }
    
    // Proportional allocation
    size_t allocated = 0;
    for (int i = 0; i < process_count; i++) {
        size_t proc_size = get_process_size(&processes[i], metric);
        processes[i].allocated_frames = 
            (proc_size * total_frames) / total_size;
        allocated += processes[i].allocated_frames;
    }
    
    // Distribute remaining frames to largest processes
    size_t remaining = total_frames - allocated;
    while (remaining > 0) {
        // Find process with largest size that hasn't received bonus
        size_t max_size = 0;
        int max_idx = 0;
        for (int i = 0; i < process_count; i++) {
            size_t size = get_process_size(&processes[i], metric);
            if (size > max_size) {
                max_size = size;
                max_idx = i;
            }
        }
        processes[max_idx].allocated_frames++;
        remaining--;
    }
}

Implementation Strategies

Implementing proportional allocation efficiently requires careful consideration of when calculations occur, how frames are redistributed, and how the system handles dynamic changes.

Static vs. Dynamic Implementation

Static Proportional Allocation: Allocations are computed once at process creation based on initial size metrics and remain fixed throughout process lifetime.

When to use: Batch processing, predictable workloads, simplicity-critical systems
Advantage: Simple, deterministic, no runtime overhead
Disadvantage: Doesn't adapt to changing memory needs

Dynamic Proportional Allocation: Allocations are recomputed periodically or on specific triggers, adjusting to current size metrics.

When to use: Interactive systems, variable workloads, long-running processes
Advantage: Adapts to changing needs
Disadvantage: Overhead; can cause instability if too frequent

Converting Mermaid diagram...

Rebalancing Triggers

Dynamic proportional allocation must decide when to recalculate. Common triggers:

Process Creation/Termination — Essential; process pool changed
Significant Size Change — When a process's size changes by more than threshold (e.g., 20%)
Periodic Timer — Every N seconds, regardless of other events
Memory Pressure — When free pool depletes or page fault rate spikes
Explicit Request — Process or administrator requests rebalancing

Rebalancing Algorithm

The core rebalancing algorithm:

Snapshot current size metrics for all processes
Calculate new proportional allocations
Identify over-allocated processes (current > target)
Identify under-allocated processes (current < target)
Reclaim frames from over-allocated (page out if necessary)
Grant reclaimed frames to under-allocated
Update per-process allocation records

rebalancing_engine.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
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <stdbool.h>
#include <stdlib.h>
 
#define REBALANCE_THRESHOLD_PCT 20  // Trigger if allocation off by >20%
#define MIN_REBALANCE_INTERVAL_MS 1000  // Minimum time between rebalances
 
typedef struct {
    int pid;
    size_t current_size;
    size_t current_allocation;
    size_t target_allocation;
    int allocation_delta;  // target - current
} RebalanceEntry;
 
typedef struct {
    RebalanceEntry* entries;
    int entry_count;
    size_t total_frames;
    size_t free_pool;
    uint64_t last_rebalance_time;
} RebalanceState;
 
// Check if rebalancing is needed
bool needs_rebalancing(RebalanceState* state) {
    for (int i = 0; i < state->entry_count; i++) {
        RebalanceEntry* e = &state->entries[i];
        
        if (e->target_allocation == 0) continue;
        
        // Calculate percentage deviation
        int deviation_pct = abs(
            (int)e->current_allocation - (int)e->target_allocation
        ) * 100 / (int)e->target_allocation;
        
        if (deviation_pct > REBALANCE_THRESHOLD_PCT) {
            return true;
        }
    }
    return false;
}
 
// Perform proportional rebalancing
void rebalance_proportional(RebalanceState* state) {
    // Phase 1: Calculate total size and new proportions
    size_t total_size = 0;
    for (int i = 0; i < state->entry_count; i++) {
        total_size += state->entries[i].current_size;
    }
    
    if (total_size == 0) return;
    
    // Phase 2: Calculate target allocations
    size_t available = state->total_frames;
    for (int i = 0; i < state->entry_count; i++) {
        RebalanceEntry* e = &state->entries[i];
        e->target_allocation = 
            (e->current_size * available) / total_size;
        e->allocation_delta = 
            (int)e->target_allocation - (int)e->current_allocation;
    }
    
    // Phase 3: Reclaim from over-allocated processes
    // Sort by delta (most over-allocated first)
    qsort(state->entries, state->entry_count, 
          sizeof(RebalanceEntry), compare_by_delta_desc);
    
    for (int i = 0; i < state->entry_count; i++) {
        RebalanceEntry* e = &state->entries[i];
        
        if (e->allocation_delta >= 0) break;  // No more over-allocated
        
        int to_reclaim = -e->allocation_delta;
        
        // Reclaim frames (involves page-out for dirty pages)
        int reclaimed = reclaim_frames_from_process(e->pid, to_reclaim);
        
        e->current_allocation -= reclaimed;
        state->free_pool += reclaimed;
    }
    
    // Phase 4: Grant to under-allocated processes
    // Re-sort by delta (most under-allocated first)
    qsort(state->entries, state->entry_count,
          sizeof(RebalanceEntry), compare_by_delta_asc);
    
    for (int i = 0; i < state->entry_count; i++) {
        RebalanceEntry* e = &state->entries[i];
        
        if (e->allocation_delta <= 0) break;  // No more under-allocated
        
        int to_grant = e->allocation_delta;
        
        // Only grant what's available
        if (to_grant > (int)state->free_pool) {
            to_grant = (int)state->free_pool;
        }
        
        if (to_grant > 0) {
            grant_frames_to_process(e->pid, to_grant);
            e->current_allocation += to_grant;
            state->free_pool -= to_grant;
        }
    }
    
    state->last_rebalance_time = get_current_time_ms();
}
 
// Comparison functions for sorting
int compare_by_delta_desc(const void* a, const void* b) {
    const RebalanceEntry* ea = (const RebalanceEntry*)a;
    const RebalanceEntry* eb = (const RebalanceEntry*)b;
    return ea->allocation_delta - eb->allocation_delta;  // Negative first
}
 
int compare_by_delta_asc(const void* a, const void* b) {
    const RebalanceEntry* ea = (const RebalanceEntry*)a;
    const RebalanceEntry* eb = (const RebalanceEntry*)b;
    return eb->allocation_delta - ea->allocation_delta;  // Positive first
}

Handling Edge Cases

Proportional allocation introduces several edge cases that require careful handling to maintain system stability.

Edge Case 1: Very Small Processes

When a process has minimal size, proportional allocation may compute an allocation below the architectural minimum.

Minimum Frame Violation

If process i has size sᵢ such that (sᵢ/S) × m < minimum_frames, proportional allocation fails for that process.

Solution: Enforce a floor: aᵢ = max(proportional_allocation, minimum_frames)

Implication: This steals frames from the proportional pool, slightly reducing allocations for other processes. In extreme cases (many tiny processes), this can significantly distort proportionality.

Edge Case 2: Single Dominant Process

When one process is dramatically larger than all others, it receives almost all frames, potentially starving other processes.

Example: Processes with sizes [1000, 10, 10, 10] and 100 frames:

Proportional: [97, 1, 1, 1] — Small processes get only 1 frame each!

Solution Options:

Minimum floor enforcement — Ensures every process gets at least min_frames
Maximum cap enforcement — Limits any single process to max_fraction (e.g., 90%) of frames
Logarithmic scaling — Use log(size) instead of size, compressing the range

Edge Case 3: Zero-Size Processes

A process that just started or has been fully paged out has RSS=0, causing division issues.

Solution: Use virtual size as fallback, or assign minimum allocation for any active process.

Edge Case 4: Rapid Size Oscillation

If a process's size metric fluctuates rapidly (common with RSS-based sizing), allocations may oscillate, causing thrashing.

Solution:

Use exponential moving average: smoothed_size = α × current_size + (1-α) × smoothed_size
Implement hysteresis: only rebalance when change exceeds threshold
Use peak or maximum of recent sizes rather than instantaneous

edge_case_handling.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
#define MIN_FRAMES_PER_PROCESS 3
#define MAX_ALLOCATION_FRACTION 0.90  // No process gets > 90% of frames
#define SMOOTHING_ALPHA 0.3           // EMA smoothing factor
#define OSCILLATION_DAMPING_WINDOW 5  // Samples for oscillation detection
 
typedef struct {
    int pid;
    size_t raw_size;         // Current raw size metric
    size_t smoothed_size;    // Exponentially smoothed size
    size_t size_history[OSCILLATION_DAMPING_WINDOW];
    int history_index;
    size_t min_allocation;   // Process-specific minimum
    size_t max_allocation;   // Process-specific maximum
} ProcessAllocationState;
 
// Apply smoothing to prevent oscillation
void update_smoothed_size(ProcessAllocationState* state, size_t new_size) {
    // Store in history for oscillation detection
    state->size_history[state->history_index] = new_size;
    state->history_index = 
        (state->history_index + 1) % OSCILLATION_DAMPING_WINDOW;
    
    // Check for oscillation (high variance in recent sizes)
    size_t sum = 0, sum_sq = 0;
    for (int i = 0; i < OSCILLATION_DAMPING_WINDOW; i++) {
        sum += state->size_history[i];
        sum_sq += state->size_history[i] * state->size_history[i];
    }
    size_t mean = sum / OSCILLATION_DAMPING_WINDOW;
    size_t variance = sum_sq / OSCILLATION_DAMPING_WINDOW - mean * mean;
    
    // If high variance (oscillating), use more aggressive smoothing
    double effective_alpha = SMOOTHING_ALPHA;
    if (variance > mean * mean * 0.25) {  // Variance > 25% of mean squared
        effective_alpha = 0.1;  // Much slower response
    }
    
    // Apply exponential moving average
    state->raw_size = new_size;
    state->smoothed_size = (size_t)(
        effective_alpha * new_size + 
        (1.0 - effective_alpha) * state->smoothed_size
    );
}
 
// Calculate allocation with all edge case protections
size_t calculate_protected_allocation(
    ProcessAllocationState* processes,
    int process_count,
    int process_index,
    size_t total_frames
) {
    ProcessAllocationState* proc = &processes[process_index];
    
    // Calculate raw proportional allocation
    size_t total_size = 0;
    for (int i = 0; i < process_count; i++) {
        total_size += processes[i].smoothed_size;
    }
    
    size_t raw_allocation;
    if (total_size == 0) {
        // Edge case: all sizes zero, fall back to equal
        raw_allocation = total_frames / process_count;
    } else {
        raw_allocation = 
            (proc->smoothed_size * total_frames) / total_size;
    }
    
    // Apply minimum floor (architectural + process-specific)
    size_t floor_alloc = proc->min_allocation > MIN_FRAMES_PER_PROCESS 
                         ? proc->min_allocation 
                         : MIN_FRAMES_PER_PROCESS;
    
    if (raw_allocation < floor_alloc) {
        raw_allocation = floor_alloc;
    }
    
    // Apply maximum cap (prevents single process dominance)
    size_t max_allowed = (size_t)(total_frames * MAX_ALLOCATION_FRACTION);
    if (proc->max_allocation > 0 && proc->max_allocation < max_allowed) {
        max_allowed = proc->max_allocation;
    }
    
    if (raw_allocation > max_allowed) {
        raw_allocation = max_allowed;
    }
    
    return raw_allocation;
}

Proportional Allocation Variants

Pure proportional allocation admits several useful variants that address specific limitations while maintaining the core proportionality principle.

Variant 1: Weighted Proportional Allocation

Introduce a weight factor for each process, allowing administrative control over relative allocations:

aᵢ = (wᵢ × sᵢ) / Σ(wⱼ × sⱼ) × m

Where wᵢ is the weight for process i (higher weight = more frames).

Use cases:

Production processes get weight 2.0, development weight 1.0
Critical services get weight 3.0, background tasks weight 0.5
Interactive applications get weight 1.5, batch jobs weight 0.8

Weighted Proportional Example
Process	Size	Weight	Weighted Size	Allocation (100 frames)
Web Server	200	2.0	400	50
Database	150	2.0	300	37
Log Agent	50	0.5	25	3
Dev App	100	1.0	100	10
Total	500		825	100

Variant 2: Bounded Proportional Allocation

Enforce per-process bounds (minimum and maximum) that override proportional calculations:

aᵢ = clamp(proportional_aᵢ, minᵢ, maxᵢ)

Use cases:

Guarantee minimum allocation for critical processes
Prevent runaway processes from monopolizing memory
Implement resource limits/quotas

Variant 3: Hierarchical Proportional Allocation

First allocate among groups/users proportionally, then allocate within groups:

Divide total frames among groups based on group quotas
Within each group, divide proportionally among member processes

Use cases:

Multi-tenant systems (each tenant gets guaranteed fraction)
User-based fairness (each user gets equal share, regardless of process count)
Organizational hierarchies (departments → teams → applications)

Converting Mermaid diagram...

Variant 4: Elastic Proportional Allocation

Integrate proportional allocation with elasticity—processes can temporarily exceed their proportion when frames are available, but are throttled back under pressure:

Soft limit = proportional allocation (target)
Hard limit = maximum allowed (may exceed proportion)
Under memory pressure: reclaim down to soft limit
Under no pressure: allow growth to hard limit

This approach maximizes utilization during low-pressure periods while maintaining fairness during contention.

Modern Implementations

Linux cgroups implement a variant of hierarchical bounded proportional allocation. Each cgroup has a memory limit (hard bound) and can have a soft limit (elastic target). Within cgroups, the OOM killer uses heuristics that implicitly create priority-weighted proportionality. Docker and Kubernetes resource limits build on these mechanisms.

Comparison with Equal Allocation

Proportional allocation directly addresses equal allocation's primary weakness—size blindness—but introduces its own tradeoffs. A rigorous comparison illuminates when each approach is appropriate.

Equal vs. Proportional Allocation
Dimension	Equal Allocation	Proportional Allocation
Complexity	O(1) per decision	O(n) to compute proportions
Data Required	Process count only	Per-process size metrics
Size Sensitivity	None (size-blind)	Full (proportional to size)
Fairness Model	Per-process equality	Per-unit-of-size equality
Thrashing Risk (heterogeneous)	High (large processes starve)	Low (sizes matched to needs)
Thrashing Risk (homogeneous)	Low	Low
Wasted Frames	High (small processes over-allocated)	Low (allocation matches need)
Dynamic Overhead	Low (rebalance on count change)	Medium (rebalance on size change)
Implementation Effort	Trivial	Moderate
Predictability	High (allocation = m/n)	Medium (depends on other processes)

Quantitative Comparison Example

Recall our earlier example with 1000 frames and five processes:

Process	Size	Working Set	Equal (200 each)	Proportional
Editor	50	30	200 (170 waste)	32 (2 waste)
Compiler	800	400	200 (THRASH)	514 (114 buffer)
DB Server	2000	600	200 (THRASH)	257 (needs more)
Background	20	10	200 (190 waste)	13 (3 waste)
Web Server	300	150	200 (THRASH)	193 (43 buffer)
Total	3170	1190	1000	1009

Analysis:

Equal Allocation Issues:

360 frames wasted on over-allocation
3 processes actively thrashing
System performance severely degraded

Proportional Allocation Improvement:

Only 119 frames 'wasted' (buffer space, actually useful)
No process thrashing (though DB Server could use more)
System performance good overall

Note: Even proportional allocation doesn't perfectly match working sets. The DB Server gets 257 frames but needs 600 for its working set. This is where working set-based allocation or dynamic adjustment becomes necessary.

The Proportional-Size Disconnect

Proportional allocation assumes size correlates with need. This is often true but not always. A sparse virtual address space (common in 64-bit systems) may have huge virtual size but tiny actual need. A memory-mapped file may appear large but only small portions are actively accessed. This is why advanced systems combine proportional allocation with working set tracking.

Real-World Applications

Proportional allocation concepts appear throughout modern operating systems and resource management frameworks, though rarely in pure form. Understanding these applications connects theory to practice.

Linux Memory cgroups (Control Groups)

Linux cgroups v2 implements a sophisticated variant of proportional allocation through memory controller weights:

/sys/fs/cgroup/<group>/memory.weight  (default: 100)

When memory is contented, the kernel distributes reclaim pressure inversely proportional to weights. A process in a cgroup with weight 200 experiences half the reclaim pressure of weight 100.

cgroup_proportional_setup.sh
Bash
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
#!/bin/bash
# Setting up proportional memory allocation with cgroups v2
 
# Create cgroups for different service tiers
mkdir -p /sys/fs/cgroup/critical
mkdir -p /sys/fs/cgroup/normal
mkdir -p /sys/fs/cgroup/background
 
# Set memory weights (proportional allocation factor)
# Higher weight = more favorable allocation under pressure
echo "300" > /sys/fs/cgroup/critical/memory.weight    # 3x priority
echo "100" > /sys/fs/cgroup/normal/memory.weight      # baseline
echo "50"  > /sys/fs/cgroup/background/memory.weight  # 0.5x priority
 
# Optionally set hard limits (bounds for bounded proportional)
echo "8G" > /sys/fs/cgroup/critical/memory.max
echo "4G" > /sys/fs/cgroup/normal/memory.max
echo "1G" > /sys/fs/cgroup/background/memory.max
 
# Assign processes to cgroups
echo $CRITICAL_PID > /sys/fs/cgroup/critical/cgroup.procs
echo $NORMAL_PID > /sys/fs/cgroup/normal/cgroup.procs
echo $BACKGROUND_PID > /sys/fs/cgroup/background/cgroup.procs
 
# Effect: Under memory pressure, background processes are
# reclaimed ~6x more aggressively than critical processes
# (300/50 = 6)

Kubernetes Resource Management

Kubernetes implements proportional allocation at the container level through resource requests and limits:

Requests: Guaranteed allocation (like minimum bound)
Limits: Maximum allowed (like maximum bound)

The ratio of requests across containers in a node determines proportional sharing under contention.

kubernetes_memory.yaml
YAML
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
# Kubernetes pod specification with proportional resource allocation
apiVersion: v1
kind: Pod
metadata:
  name: multi-tier-app
spec:
  containers:
  # Database: largest allocation, critical service
  - name: database
    image: postgres:14
    resources:
      requests:
        memory: "4Gi"    # Proportional base: 4/7 = 57%
        cpu: "2000m"
      limits:
        memory: "8Gi"    # Can burst up to 8Gi if available
        cpu: "4000m"
        
  # Application server: medium allocation
  - name: app-server
    image: myapp:latest
    resources:
      requests:
        memory: "2Gi"    # Proportional base: 2/7 = 29%
        cpu: "1000m"
      limits:
        memory: "4Gi"
        cpu: "2000m"
        
  # Sidecar logging: small allocation
  - name: log-collector
    image: fluentd:latest
    resources:
      requests:
        memory: "512Mi"  # Proportional base: 0.5/7 = 7%
        cpu: "100m"
      limits:
        memory: "1Gi"
        cpu: "500m"
        
  # Monitoring sidecar: minimal allocation
  - name: metrics-agent
    image: prometheus-agent:latest
    resources:
      requests:
        memory: "512Mi"  # Proportional base: 0.5/7 = 7%
        cpu: "50m"
      limits:
        memory: "768Mi"
        cpu: "200m"
 
# Total requests: 7Gi memory
# Under memory pressure, containers are throttled proportionally
# based on their requests

Windows Working Set Management

Windows uses a variant of proportional allocation in its working set manager. Each process has:

Minimum Working Set: Guaranteed allocation (process-specific minimum bound)
Maximum Working Set: Allocation ceiling (automatic or configured)

Under memory pressure, the working set manager trims processes proportionally to their current working set sizes, larger processes contributing more pages to the trimmed pool.

Pure vs. Practical Proportional Allocation

No production system uses pure proportional allocation. All combine proportionality with: minimum/maximum bounds (cgroups limits), priority weights (cgroups weights), dynamic adjustment (working set trimming), and heuristics (OOM killer scores). However, proportional allocation provides the conceptual foundation that these systems build upon.

Summary and Key Takeaways

We have comprehensively explored proportional allocation, the strategy that addresses equal allocation's fundamental flaw by distributing frames based on process size. Let's consolidate the key insights:

Core Concepts Mastered

•Mathematical Foundation — Proportional allocation gives process i: aᵢ = (sᵢ/S) × m frames, where sᵢ is process size, S is total size, and m is available frames.
•Size Metric Selection — 'Size' can mean virtual memory size, RSS, working set, or a hybrid. Each metric has distinct characteristics; working set best reflects actual need but is expensive to track.
•Implementation Strategies — Static allocation computes once at creation; dynamic allocation recomputes periodically or on triggers. Dynamic implementations require smoothing to prevent oscillation.
•Edge Case Handling — Very small processes need minimum protection; dominant processes need maximum caps; zero-size and oscillating processes need special handling.
•Useful Variants — Weighted proportional, bounded proportional, hierarchical proportional, and elastic proportional address specific use cases while maintaining core proportionality.
•Comparison with Equal Allocation — Proportional dramatically reduces waste in heterogeneous workloads but adds complexity and data requirements.
•Real-World Applications — Linux cgroups, Kubernetes resources, and Windows working sets all implement proportional allocation variants.

Looking Ahead

Proportional allocation addresses size blindness but ignores another critical factor: priority. Not all processes are created equal in importance. A database serving production traffic matters more than a developer's test process, regardless of their relative sizes.

In the next page, we examine priority-based allocation, which introduces priority weights to ensure critical processes receive adequate resources even when competing against larger but less important workloads.

Page Complete

You now possess comprehensive understanding of proportional allocation: its mathematical formulation, implementation strategies, variants, and real-world applications. You can calculate proportional allocations, select appropriate size metrics, handle edge cases, and recognize proportional allocation patterns in production systems. This foundation prepares you for priority-based and combination allocation strategies.

2 / 5

Loading learning content...

Operating SystemsAllocation Strategies

Frame Allocation Strategies

LevelIntermediate

Duration60 mins

TopicAllocation Strategies

2 / 5

Proportional Allocation

Size Matters: A More Intelligent Distribution

What You Will Learn

Mathematical Foundation

Proportional allocation uses a straightforward mathematical formula that scales elegantly regardless of process count or system size.

Core Formula

For a system with:

m = total available frames
n = number of processes
sᵢ = size of process i (in pages or bytes)
S = Σsᵢ = total size of all processes

The allocation for process i is:

aᵢ = (sᵢ / S) × m

Alternatively: aᵢ = sᵢ × (m / S)

This gives each process a fraction of total memory proportional to its fraction of total demand. If a process represents 30% of total memory demand, it receives approximately 30% of available frames.

Rounding Considerations

Since frame counts must be integers, the calculated allocation aᵢ must be rounded. Common approaches:

The choice affects edge cases but rarely matters significantly for large m.

Worked Example

Consider a system with 124 available frames and 5 processes:

Process	Size (pages)	Proportion	Raw Allocation	Rounded (floor)
P1	10	10/137 ≈ 7.3%	9.05	9
P2	25	25/137 ≈ 18.2%	22.63	22
P3	42	42/137 ≈ 30.7%	38.02	38
P4	35	35/137 ≈ 25.5%	31.68	31
P5	25	25/137 ≈ 18.2%	22.63	22
Total	137	100%	124	122

Total allocated: 122 frames. Remainder: 2 frames (kept in free pool or distributed).

Verification: Each process's allocation closely matches its proportion of total process size. P3, the largest process (30.7% of demand), receives 30.6% of frames (38/124).

proportional_calculation.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
from dataclasses import dataclass
from typing import List, Tuple
import math
 
@dataclass
class Process:
    pid: int
    size: int  # Virtual memory size in pages
    allocation: int = 0  # Assigned frames
 
def calculate_proportional_allocation(
    processes: List[Process],
    total_frames: int,
    min_frames: int = 3
) -> Tuple[List[Process], int]:
    """
    Calculate proportional frame allocation for all processes.
    
    Args:
        processes: List of processes with their sizes
        total_frames: Total available physical frames
        min_frames: Minimum frames per process (architectural constraint)
    
    Returns:
        Tuple of (updated process list, leftover frames)
    """
    if not processes:
        return processes, total_frames
    
    # Calculate total size demand
    total_size = sum(p.size for p in processes)
    
    if total_size == 0:
        # Edge case: all processes have zero size
        # Fall back to equal allocation
        per_process = total_frames // len(processes)
        for p in processes:
            p.allocation = max(per_process, min_frames)
        return processes, total_frames - sum(p.allocation for p in processes)
    
    # First pass: calculate raw proportional allocations
    allocations = []
    for p in processes:
        # Raw allocation (may be fractional)
        raw = (p.size / total_size) * total_frames
        # Floor to get integer
        floored = math.floor(raw)
        # Track fractional part for redistribution
        fractional = raw - floored
        allocations.append((p, floored, fractional))
    
    # Enforce minimum frame constraint
    for i, (p, alloc, frac) in enumerate(allocations):
        if alloc < min_frames:
            allocations[i] = (p, min_frames, 0)  # Bump to minimum, no fractional
    
    # Calculate total allocated and remaining
    total_allocated = sum(alloc for _, alloc, _ in allocations)
    remaining = total_frames - total_allocated
    
    # Check for over-allocation (can happen if many processes need minimum)
    if remaining < 0:
        raise ValueError(
            f"Cannot satisfy minimum frames ({min_frames}) for "
            f"{len(processes)} processes with {total_frames} frames. "
            f"Need at least {len(processes) * min_frames} frames."
        )
    
    # Redistribute remaining frames based on fractional parts
    # Sort by fractional part (descending) to distribute fairly
    sorted_by_fraction = sorted(
        enumerate(allocations), 
        key=lambda x: x[1][2], 
        reverse=True
    )
    
    for i in range(remaining):
        idx = sorted_by_fraction[i % len(sorted_by_fraction)][0]
        p, alloc, frac = allocations[idx]
        allocations[idx] = (p, alloc + 1, frac)
    
    # Apply allocations to processes
    for p, alloc, _ in allocations:
        p.allocation = alloc
    
    # Recalculate actual remaining
    final_remaining = total_frames - sum(p.allocation for p in processes)
    
    return processes, final_remaining
 
# Example usage
if __name__ == "__main__":
    processes = [
        Process(pid=1, size=10),
        Process(pid=2, size=25),
        Process(pid=3, size=42),
        Process(pid=4, size=35),
        Process(pid=5, size=25),
    ]
    
    updated, remaining = calculate_proportional_allocation(processes, 124)
    
    print("Proportional Allocation Results:")
    print("-" * 50)
    total_size = sum(p.size for p in processes)
    for p in updated:
        proportion = p.size / total_size * 100
        alloc_pct = p.allocation / 124 * 100
        print(f"P{p.pid}: size={p.size:3d} ({proportion:5.1f}%) -> "
              f"{p.allocation:3d} frames ({alloc_pct:5.1f}%)")
    print(f"\nTotal allocated: {124 - remaining}")
    print(f"Remaining in free pool: {remaining}")

What Constitutes 'Size'?

Option 1: Virtual Memory Size

The simplest definition: sᵢ = total virtual pages allocated to process i.

Advantages:

Easy to determine (sum of virtual memory regions)
Static and stable (doesn't fluctuate during execution)
Reflects programmer/application intent

Disadvantages:

Virtual size ≠ actual usage (sparse address spaces common)
Process may allocate large virtual regions but use tiny fractions
Stack/heap reservations inflate size artificially

Size Metrics for Proportional Allocation
Metric	Definition	Pros	Cons
Virtual Memory Size	Total virtual pages	Simple, stable, deterministic	Doesn't reflect actual usage
Resident Set Size (RSS)	Pages currently in memory	Reflects current usage	Circular: allocation affects RSS
Working Set Size	Recently-accessed pages	Reflects actual need	Complex to track, dynamic
Maximum RSS	Peak memory usage	Captures burst needs	May over-allocate for steady state
Requested Size	Application-specified	Respects app knowledge	Apps may lie/exaggerate

Option 2: Resident Set Size (RSS)

Use the current number of pages actually resident in memory as the size metric.

Advantages:

Reflects actual current memory footprint
Automatically adapts as usage changes
Honest measure (can't be inflated by virtual reservations)

Disadvantages:

Circular dependency: RSS depends on allocation, but allocation depends on RSS
Startup processes have RSS=0, so receive minimal allocation
Fluctuates, causing allocation instability

Option 3: Working Set Size (WSS)

Use the estimated working set (pages accessed in recent window) as size.

Advantages:

Best reflects actual memory need
Automatically adapts to phase changes in program behavior
Minimizes wasted allocation

Disadvantages:

Computationally expensive to track
Requires reference bit manipulation or sampling
Still subject to fluctuation

Practical Recommendation

size_metrics.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
#include <stdio.h>
#include <stdint.h>
 
typedef struct {
    int pid;
    
    // Different size metrics
    size_t virtual_size;      // Total virtual address space
    size_t rss;               // Current resident set
    size_t peak_rss;          // Maximum observed RSS
    size_t working_set;       // Estimated working set
    size_t requested_size;    // Application-requested quota
    
    // Derived allocation
    size_t allocated_frames;
} ProcessSizeMetrics;
 
typedef enum {
    SIZE_METRIC_VIRTUAL,
    SIZE_METRIC_RSS,
    SIZE_METRIC_PEAK_RSS,
    SIZE_METRIC_WORKING_SET,
    SIZE_METRIC_REQUESTED,
    SIZE_METRIC_HYBRID          // Weighted combination
} SizeMetricType;
 
// Get size value based on selected metric
size_t get_process_size(ProcessSizeMetrics* proc, SizeMetricType metric) {
    switch (metric) {
        case SIZE_METRIC_VIRTUAL:
            return proc->virtual_size;
            
        case SIZE_METRIC_RSS:
            return proc->rss;
            
        case SIZE_METRIC_PEAK_RSS:
            return proc->peak_rss;
            
        case SIZE_METRIC_WORKING_SET:
            return proc->working_set;
            
        case SIZE_METRIC_REQUESTED:
            return proc->requested_size;
            
        case SIZE_METRIC_HYBRID:
            // Weighted combination: 50% working set, 30% RSS, 20% virtual
            return (proc->working_set * 50 + 
                    proc->rss * 30 + 
                    proc->virtual_size * 20) / 100;
            
        default:
            return proc->virtual_size;
    }
}
 
// Calculate proportional allocation with configurable size metric
void calculate_proportional_with_metric(
    ProcessSizeMetrics* processes,
    int process_count,
    size_t total_frames,
    SizeMetricType metric
) {
    // Calculate total size using selected metric
    size_t total_size = 0;
    for (int i = 0; i < process_count; i++) {
        total_size += get_process_size(&processes[i], metric);
    }
    
    if (total_size == 0) {
        // Fallback to equal allocation
        size_t per_process = total_frames / process_count;
        for (int i = 0; i < process_count; i++) {
            processes[i].allocated_frames = per_process;
        }
        return;
    }
    
    // Proportional allocation
    size_t allocated = 0;
    for (int i = 0; i < process_count; i++) {
        size_t proc_size = get_process_size(&processes[i], metric);
        processes[i].allocated_frames = 
            (proc_size * total_frames) / total_size;
        allocated += processes[i].allocated_frames;
    }
    
    // Distribute remaining frames to largest processes
    size_t remaining = total_frames - allocated;
    while (remaining > 0) {
        // Find process with largest size that hasn't received bonus
        size_t max_size = 0;
        int max_idx = 0;
        for (int i = 0; i < process_count; i++) {
            size_t size = get_process_size(&processes[i], metric);
            if (size > max_size) {
                max_size = size;
                max_idx = i;
            }
        }
        processes[max_idx].allocated_frames++;
        remaining--;
    }
}

Implementation Strategies

Implementing proportional allocation efficiently requires careful consideration of when calculations occur, how frames are redistributed, and how the system handles dynamic changes.

Static vs. Dynamic Implementation

Static Proportional Allocation: Allocations are computed once at process creation based on initial size metrics and remain fixed throughout process lifetime.

When to use: Batch processing, predictable workloads, simplicity-critical systems
Advantage: Simple, deterministic, no runtime overhead
Disadvantage: Doesn't adapt to changing memory needs

Dynamic Proportional Allocation: Allocations are recomputed periodically or on specific triggers, adjusting to current size metrics.

When to use: Interactive systems, variable workloads, long-running processes
Advantage: Adapts to changing needs
Disadvantage: Overhead; can cause instability if too frequent

Converting Mermaid diagram...

Rebalancing Triggers

Dynamic proportional allocation must decide when to recalculate. Common triggers:

Process Creation/Termination — Essential; process pool changed
Significant Size Change — When a process's size changes by more than threshold (e.g., 20%)
Periodic Timer — Every N seconds, regardless of other events
Memory Pressure — When free pool depletes or page fault rate spikes
Explicit Request — Process or administrator requests rebalancing

Rebalancing Algorithm

The core rebalancing algorithm:

Snapshot current size metrics for all processes
Calculate new proportional allocations
Identify over-allocated processes (current > target)
Identify under-allocated processes (current < target)
Reclaim frames from over-allocated (page out if necessary)
Grant reclaimed frames to under-allocated
Update per-process allocation records

rebalancing_engine.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
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <stdbool.h>
#include <stdlib.h>
 
#define REBALANCE_THRESHOLD_PCT 20  // Trigger if allocation off by >20%
#define MIN_REBALANCE_INTERVAL_MS 1000  // Minimum time between rebalances
 
typedef struct {
    int pid;
    size_t current_size;
    size_t current_allocation;
    size_t target_allocation;
    int allocation_delta;  // target - current
} RebalanceEntry;
 
typedef struct {
    RebalanceEntry* entries;
    int entry_count;
    size_t total_frames;
    size_t free_pool;
    uint64_t last_rebalance_time;
} RebalanceState;
 
// Check if rebalancing is needed
bool needs_rebalancing(RebalanceState* state) {
    for (int i = 0; i < state->entry_count; i++) {
        RebalanceEntry* e = &state->entries[i];
        
        if (e->target_allocation == 0) continue;
        
        // Calculate percentage deviation
        int deviation_pct = abs(
            (int)e->current_allocation - (int)e->target_allocation
        ) * 100 / (int)e->target_allocation;
        
        if (deviation_pct > REBALANCE_THRESHOLD_PCT) {
            return true;
        }
    }
    return false;
}
 
// Perform proportional rebalancing
void rebalance_proportional(RebalanceState* state) {
    // Phase 1: Calculate total size and new proportions
    size_t total_size = 0;
    for (int i = 0; i < state->entry_count; i++) {
        total_size += state->entries[i].current_size;
    }
    
    if (total_size == 0) return;
    
    // Phase 2: Calculate target allocations
    size_t available = state->total_frames;
    for (int i = 0; i < state->entry_count; i++) {
        RebalanceEntry* e = &state->entries[i];
        e->target_allocation = 
            (e->current_size * available) / total_size;
        e->allocation_delta = 
            (int)e->target_allocation - (int)e->current_allocation;
    }
    
    // Phase 3: Reclaim from over-allocated processes
    // Sort by delta (most over-allocated first)
    qsort(state->entries, state->entry_count, 
          sizeof(RebalanceEntry), compare_by_delta_desc);
    
    for (int i = 0; i < state->entry_count; i++) {
        RebalanceEntry* e = &state->entries[i];
        
        if (e->allocation_delta >= 0) break;  // No more over-allocated
        
        int to_reclaim = -e->allocation_delta;
        
        // Reclaim frames (involves page-out for dirty pages)
        int reclaimed = reclaim_frames_from_process(e->pid, to_reclaim);
        
        e->current_allocation -= reclaimed;
        state->free_pool += reclaimed;
    }
    
    // Phase 4: Grant to under-allocated processes
    // Re-sort by delta (most under-allocated first)
    qsort(state->entries, state->entry_count,
          sizeof(RebalanceEntry), compare_by_delta_asc);
    
    for (int i = 0; i < state->entry_count; i++) {
        RebalanceEntry* e = &state->entries[i];
        
        if (e->allocation_delta <= 0) break;  // No more under-allocated
        
        int to_grant = e->allocation_delta;
        
        // Only grant what's available
        if (to_grant > (int)state->free_pool) {
            to_grant = (int)state->free_pool;
        }
        
        if (to_grant > 0) {
            grant_frames_to_process(e->pid, to_grant);
            e->current_allocation += to_grant;
            state->free_pool -= to_grant;
        }
    }
    
    state->last_rebalance_time = get_current_time_ms();
}
 
// Comparison functions for sorting
int compare_by_delta_desc(const void* a, const void* b) {
    const RebalanceEntry* ea = (const RebalanceEntry*)a;
    const RebalanceEntry* eb = (const RebalanceEntry*)b;
    return ea->allocation_delta - eb->allocation_delta;  // Negative first
}
 
int compare_by_delta_asc(const void* a, const void* b) {
    const RebalanceEntry* ea = (const RebalanceEntry*)a;
    const RebalanceEntry* eb = (const RebalanceEntry*)b;
    return eb->allocation_delta - ea->allocation_delta;  // Positive first
}

Handling Edge Cases

Proportional allocation introduces several edge cases that require careful handling to maintain system stability.

Edge Case 1: Very Small Processes

When a process has minimal size, proportional allocation may compute an allocation below the architectural minimum.

Minimum Frame Violation

If process i has size sᵢ such that (sᵢ/S) × m < minimum_frames, proportional allocation fails for that process.

Solution: Enforce a floor: aᵢ = max(proportional_allocation, minimum_frames)

Edge Case 2: Single Dominant Process

When one process is dramatically larger than all others, it receives almost all frames, potentially starving other processes.

Example: Processes with sizes [1000, 10, 10, 10] and 100 frames:

Proportional: [97, 1, 1, 1] — Small processes get only 1 frame each!

Solution Options:

Minimum floor enforcement — Ensures every process gets at least min_frames
Maximum cap enforcement — Limits any single process to max_fraction (e.g., 90%) of frames
Logarithmic scaling — Use log(size) instead of size, compressing the range

Edge Case 3: Zero-Size Processes

A process that just started or has been fully paged out has RSS=0, causing division issues.

Solution: Use virtual size as fallback, or assign minimum allocation for any active process.

Edge Case 4: Rapid Size Oscillation

If a process's size metric fluctuates rapidly (common with RSS-based sizing), allocations may oscillate, causing thrashing.

Solution:

Use exponential moving average: smoothed_size = α × current_size + (1-α) × smoothed_size
Implement hysteresis: only rebalance when change exceeds threshold
Use peak or maximum of recent sizes rather than instantaneous

edge_case_handling.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
#define MIN_FRAMES_PER_PROCESS 3
#define MAX_ALLOCATION_FRACTION 0.90  // No process gets > 90% of frames
#define SMOOTHING_ALPHA 0.3           // EMA smoothing factor
#define OSCILLATION_DAMPING_WINDOW 5  // Samples for oscillation detection
 
typedef struct {
    int pid;
    size_t raw_size;         // Current raw size metric
    size_t smoothed_size;    // Exponentially smoothed size
    size_t size_history[OSCILLATION_DAMPING_WINDOW];
    int history_index;
    size_t min_allocation;   // Process-specific minimum
    size_t max_allocation;   // Process-specific maximum
} ProcessAllocationState;
 
// Apply smoothing to prevent oscillation
void update_smoothed_size(ProcessAllocationState* state, size_t new_size) {
    // Store in history for oscillation detection
    state->size_history[state->history_index] = new_size;
    state->history_index = 
        (state->history_index + 1) % OSCILLATION_DAMPING_WINDOW;
    
    // Check for oscillation (high variance in recent sizes)
    size_t sum = 0, sum_sq = 0;
    for (int i = 0; i < OSCILLATION_DAMPING_WINDOW; i++) {
        sum += state->size_history[i];
        sum_sq += state->size_history[i] * state->size_history[i];
    }
    size_t mean = sum / OSCILLATION_DAMPING_WINDOW;
    size_t variance = sum_sq / OSCILLATION_DAMPING_WINDOW - mean * mean;
    
    // If high variance (oscillating), use more aggressive smoothing
    double effective_alpha = SMOOTHING_ALPHA;
    if (variance > mean * mean * 0.25) {  // Variance > 25% of mean squared
        effective_alpha = 0.1;  // Much slower response
    }
    
    // Apply exponential moving average
    state->raw_size = new_size;
    state->smoothed_size = (size_t)(
        effective_alpha * new_size + 
        (1.0 - effective_alpha) * state->smoothed_size
    );
}
 
// Calculate allocation with all edge case protections
size_t calculate_protected_allocation(
    ProcessAllocationState* processes,
    int process_count,
    int process_index,
    size_t total_frames
) {
    ProcessAllocationState* proc = &processes[process_index];
    
    // Calculate raw proportional allocation
    size_t total_size = 0;
    for (int i = 0; i < process_count; i++) {
        total_size += processes[i].smoothed_size;
    }
    
    size_t raw_allocation;
    if (total_size == 0) {
        // Edge case: all sizes zero, fall back to equal
        raw_allocation = total_frames / process_count;
    } else {
        raw_allocation = 
            (proc->smoothed_size * total_frames) / total_size;
    }
    
    // Apply minimum floor (architectural + process-specific)
    size_t floor_alloc = proc->min_allocation > MIN_FRAMES_PER_PROCESS 
                         ? proc->min_allocation 
                         : MIN_FRAMES_PER_PROCESS;
    
    if (raw_allocation < floor_alloc) {
        raw_allocation = floor_alloc;
    }
    
    // Apply maximum cap (prevents single process dominance)
    size_t max_allowed = (size_t)(total_frames * MAX_ALLOCATION_FRACTION);
    if (proc->max_allocation > 0 && proc->max_allocation < max_allowed) {
        max_allowed = proc->max_allocation;
    }
    
    if (raw_allocation > max_allowed) {
        raw_allocation = max_allowed;
    }
    
    return raw_allocation;
}

Proportional Allocation Variants

Pure proportional allocation admits several useful variants that address specific limitations while maintaining the core proportionality principle.

Variant 1: Weighted Proportional Allocation

Introduce a weight factor for each process, allowing administrative control over relative allocations:

aᵢ = (wᵢ × sᵢ) / Σ(wⱼ × sⱼ) × m

Where wᵢ is the weight for process i (higher weight = more frames).

Use cases:

Production processes get weight 2.0, development weight 1.0
Critical services get weight 3.0, background tasks weight 0.5
Interactive applications get weight 1.5, batch jobs weight 0.8

Weighted Proportional Example
Process	Size	Weight	Weighted Size	Allocation (100 frames)
Web Server	200	2.0	400	50
Database	150	2.0	300	37
Log Agent	50	0.5	25	3
Dev App	100	1.0	100	10
Total	500		825	100

Variant 2: Bounded Proportional Allocation

Enforce per-process bounds (minimum and maximum) that override proportional calculations:

aᵢ = clamp(proportional_aᵢ, minᵢ, maxᵢ)

Use cases:

Guarantee minimum allocation for critical processes
Prevent runaway processes from monopolizing memory
Implement resource limits/quotas

Variant 3: Hierarchical Proportional Allocation

First allocate among groups/users proportionally, then allocate within groups:

Divide total frames among groups based on group quotas
Within each group, divide proportionally among member processes

Use cases:

Multi-tenant systems (each tenant gets guaranteed fraction)
User-based fairness (each user gets equal share, regardless of process count)
Organizational hierarchies (departments → teams → applications)

Converting Mermaid diagram...

Variant 4: Elastic Proportional Allocation

Integrate proportional allocation with elasticity—processes can temporarily exceed their proportion when frames are available, but are throttled back under pressure:

Soft limit = proportional allocation (target)
Hard limit = maximum allowed (may exceed proportion)
Under memory pressure: reclaim down to soft limit
Under no pressure: allow growth to hard limit

This approach maximizes utilization during low-pressure periods while maintaining fairness during contention.

Modern Implementations

Comparison with Equal Allocation

Equal vs. Proportional Allocation
Dimension	Equal Allocation	Proportional Allocation
Complexity	O(1) per decision	O(n) to compute proportions
Data Required	Process count only	Per-process size metrics
Size Sensitivity	None (size-blind)	Full (proportional to size)
Fairness Model	Per-process equality	Per-unit-of-size equality
Thrashing Risk (heterogeneous)	High (large processes starve)	Low (sizes matched to needs)
Thrashing Risk (homogeneous)	Low	Low
Wasted Frames	High (small processes over-allocated)	Low (allocation matches need)
Dynamic Overhead	Low (rebalance on count change)	Medium (rebalance on size change)
Implementation Effort	Trivial	Moderate
Predictability	High (allocation = m/n)	Medium (depends on other processes)

Quantitative Comparison Example

Recall our earlier example with 1000 frames and five processes:

Process	Size	Working Set	Equal (200 each)	Proportional
Editor	50	30	200 (170 waste)	32 (2 waste)
Compiler	800	400	200 (THRASH)	514 (114 buffer)
DB Server	2000	600	200 (THRASH)	257 (needs more)
Background	20	10	200 (190 waste)	13 (3 waste)
Web Server	300	150	200 (THRASH)	193 (43 buffer)
Total	3170	1190	1000	1009

Analysis:

Equal Allocation Issues:

360 frames wasted on over-allocation
3 processes actively thrashing
System performance severely degraded

Proportional Allocation Improvement:

Only 119 frames 'wasted' (buffer space, actually useful)
No process thrashing (though DB Server could use more)
System performance good overall

The Proportional-Size Disconnect

Real-World Applications

Linux Memory cgroups (Control Groups)

Linux cgroups v2 implements a sophisticated variant of proportional allocation through memory controller weights:

/sys/fs/cgroup/<group>/memory.weight  (default: 100)

When memory is contented, the kernel distributes reclaim pressure inversely proportional to weights. A process in a cgroup with weight 200 experiences half the reclaim pressure of weight 100.

cgroup_proportional_setup.sh
Bash
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
#!/bin/bash
# Setting up proportional memory allocation with cgroups v2
 
# Create cgroups for different service tiers
mkdir -p /sys/fs/cgroup/critical
mkdir -p /sys/fs/cgroup/normal
mkdir -p /sys/fs/cgroup/background
 
# Set memory weights (proportional allocation factor)
# Higher weight = more favorable allocation under pressure
echo "300" > /sys/fs/cgroup/critical/memory.weight    # 3x priority
echo "100" > /sys/fs/cgroup/normal/memory.weight      # baseline
echo "50"  > /sys/fs/cgroup/background/memory.weight  # 0.5x priority
 
# Optionally set hard limits (bounds for bounded proportional)
echo "8G" > /sys/fs/cgroup/critical/memory.max
echo "4G" > /sys/fs/cgroup/normal/memory.max
echo "1G" > /sys/fs/cgroup/background/memory.max
 
# Assign processes to cgroups
echo $CRITICAL_PID > /sys/fs/cgroup/critical/cgroup.procs
echo $NORMAL_PID > /sys/fs/cgroup/normal/cgroup.procs
echo $BACKGROUND_PID > /sys/fs/cgroup/background/cgroup.procs
 
# Effect: Under memory pressure, background processes are
# reclaimed ~6x more aggressively than critical processes
# (300/50 = 6)

Kubernetes Resource Management

Kubernetes implements proportional allocation at the container level through resource requests and limits:

Requests: Guaranteed allocation (like minimum bound)
Limits: Maximum allowed (like maximum bound)

The ratio of requests across containers in a node determines proportional sharing under contention.

kubernetes_memory.yaml
YAML
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
# Kubernetes pod specification with proportional resource allocation
apiVersion: v1
kind: Pod
metadata:
  name: multi-tier-app
spec:
  containers:
  # Database: largest allocation, critical service
  - name: database
    image: postgres:14
    resources:
      requests:
        memory: "4Gi"    # Proportional base: 4/7 = 57%
        cpu: "2000m"
      limits:
        memory: "8Gi"    # Can burst up to 8Gi if available
        cpu: "4000m"
        
  # Application server: medium allocation
  - name: app-server
    image: myapp:latest
    resources:
      requests:
        memory: "2Gi"    # Proportional base: 2/7 = 29%
        cpu: "1000m"
      limits:
        memory: "4Gi"
        cpu: "2000m"
        
  # Sidecar logging: small allocation
  - name: log-collector
    image: fluentd:latest
    resources:
      requests:
        memory: "512Mi"  # Proportional base: 0.5/7 = 7%
        cpu: "100m"
      limits:
        memory: "1Gi"
        cpu: "500m"
        
  # Monitoring sidecar: minimal allocation
  - name: metrics-agent
    image: prometheus-agent:latest
    resources:
      requests:
        memory: "512Mi"  # Proportional base: 0.5/7 = 7%
        cpu: "50m"
      limits:
        memory: "768Mi"
        cpu: "200m"
 
# Total requests: 7Gi memory
# Under memory pressure, containers are throttled proportionally
# based on their requests

Windows Working Set Management

Windows uses a variant of proportional allocation in its working set manager. Each process has:

Minimum Working Set: Guaranteed allocation (process-specific minimum bound)
Maximum Working Set: Allocation ceiling (automatic or configured)

Under memory pressure, the working set manager trims processes proportionally to their current working set sizes, larger processes contributing more pages to the trimmed pool.

Pure vs. Practical Proportional Allocation

Summary and Key Takeaways

Core Concepts Mastered

•Mathematical Foundation — Proportional allocation gives process i: aᵢ = (sᵢ/S) × m frames, where sᵢ is process size, S is total size, and m is available frames.
•Size Metric Selection — 'Size' can mean virtual memory size, RSS, working set, or a hybrid. Each metric has distinct characteristics; working set best reflects actual need but is expensive to track.
•Implementation Strategies — Static allocation computes once at creation; dynamic allocation recomputes periodically or on triggers. Dynamic implementations require smoothing to prevent oscillation.
•Edge Case Handling — Very small processes need minimum protection; dominant processes need maximum caps; zero-size and oscillating processes need special handling.
•Useful Variants — Weighted proportional, bounded proportional, hierarchical proportional, and elastic proportional address specific use cases while maintaining core proportionality.
•Comparison with Equal Allocation — Proportional dramatically reduces waste in heterogeneous workloads but adds complexity and data requirements.
•Real-World Applications — Linux cgroups, Kubernetes resources, and Windows working sets all implement proportional allocation variants.

Looking Ahead

Page Complete

2 / 5