Allocation Strategies - Learning Module

Loading content...

0/227

Priority-based Allocation

Not All Processes Are Created Equal

Equal allocation treats all processes identically. Proportional allocation differentiates by size. But neither captures a fundamental reality of computing systems: some processes are more important than others.

The database serving millions of customers in production is more critical than a developer's test script. The kernel's memory manager is more important than a user's background music player. The real-time control system monitoring factory equipment matters more than the logging daemon.

Priority-based allocation introduces explicit importance distinctions into frame distribution. Higher-priority processes receive preferential treatment—more frames, or frames reclaimed last during pressure, or guaranteed minimums that cannot be violated. This approach aligns memory resource allocation with organizational and operational priorities.

What You Will Learn

By the end of this page, you will master priority-based allocation: the models for defining and representing priority, methods for translating priority into allocation decisions, integration with size-based proportional allocation, handling of priority inversion scenarios, and critical analysis of when priority-based allocation excels versus creates problems. You will understand how modern systems implement priority hierarchies in memory management.

Conceptual Foundation

Priority-based allocation is philosophically distinct from equal and proportional allocation. Rather than asking "How do we divide resources fairly?" it asks "How do we divide resources according to importance?"

Defining Priority

Priority in memory allocation can derive from multiple sources:

System-Defined Priority:

Kernel processes (highest priority—system stability)
System services (high priority—core functionality)
Interactive user processes (medium-high priority—responsiveness)
Batch/background processes (lower priority—throughput-oriented)

User/Administrator-Defined Priority:

Critical production workloads
Important development/test environments
Nice-value adjusted processes
Resource class/quota group membership

Dynamic/Behavioral Priority:

Processes with high page fault rates (may need more frames)
Processes approaching deadlines (real-time consideration)
Recently interactive processes (responsiveness boost)

Priority Sources and Their Characteristics
Priority Source	Determination	Stability	Example
Process Type	Kernel classification	Very stable	Kernel threads vs. user processes
Nice Value	User/administrator set	Stable unless changed	nice -n -10 vs. nice -n 19
Resource Class	Group membership	Stable per-session	Production vs. development cgroups
Real-time Class	Scheduler classification	Stable	SCHED_FIFO vs. SCHED_OTHER
Dynamic Behavior	Runtime measurement	Fluctuates	Page fault rate, CPU usage pattern
User Identity	Authentication	Stable per-session	Root/admin vs. regular user

Priority Models

Several models exist for translating priority into allocation:

Model 1: Priority Classes

Group processes into discrete classes, each with different allocation rules:

Class A (Critical): Guaranteed minimum allocation, never reclaimed first
Class B (Normal): Standard proportional allocation
Class C (Background): Reduced allocation, first to be reclaimed

Model 2: Priority Weights

Assign numerical weights to processes; allocation is weighted-proportional:

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

Where pᵢ is the priority weight for process i.

Model 3: Priority Ordering

Under memory pressure, reclaim frames in priority order—lowest priority first. Allocation is implicit rather than explicit.

Priority vs. Size Interaction

Priority-based allocation raises a fundamental question: should a small high-priority process get more frames than a large low-priority process? The answer depends on your priority model:

• Multiplicative model: Priority amplifies size (high-priority large = most frames) • Additive model: Priority adds a bonus (high-priority small still less than low-priority large) • Override model: Priority trumps size (high-priority always beats low-priority)

Most systems use multiplicative or hybrid approaches.

Priority-Weighted Allocation

The most common approach to priority-based allocation extends proportional allocation with priority weights. This creates a unified framework that considers both size and importance.

Mathematical Formulation

For process i with:

sᵢ = size (pages)
pᵢ = priority weight (typically 1-1000, or normalized 0.0-1.0)
m = total available frames

The weighted allocation is:

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

This formula gives each process a share proportional to its priority-weighted size. A process with twice the priority weight receives twice the frames (for the same size), effectively treating high-priority processes as "larger" for allocation purposes.

priority_weighted_allocation.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
from dataclasses import dataclass
from typing import List, Dict
import math
 
@dataclass
class PriorityProcess:
    pid: int
    name: str
    size: int              # Virtual memory size in pages
    priority: float        # Priority weight (default 1.0)
    priority_class: str    # Classification for reporting
    allocation: int = 0    # Assigned frames
    
# Example priority weights by class
PRIORITY_WEIGHTS = {
    "kernel": 10.0,        # Critical kernel processes
    "system": 5.0,         # System services
    "interactive": 2.0,    # Interactive user applications
    "normal": 1.0,         # Standard processes
    "batch": 0.5,          # Background batch jobs
    "idle": 0.1,           # Idle-time only processes
}
 
def calculate_priority_weighted_allocation(
    processes: List[PriorityProcess],
    total_frames: int,
    min_frames: int = 3
) -> List[PriorityProcess]:
    """
    Calculate priority-weighted proportional allocation.
    
    Each process receives frames proportional to:
        (priority_weight × size) / sum(all priority_weight × size)
    """
    if not processes:
        return processes
    
    # Calculate total weighted size
    total_weighted_size = sum(
        p.priority * p.size for p in processes
    )
    
    if total_weighted_size == 0:
        # Edge case: all weighted sizes are zero
        per_process = total_frames // len(processes)
        for p in processes:
            p.allocation = max(per_process, min_frames)
        return processes
    
    # Calculate raw allocations
    total_allocated = 0
    for p in processes:
        weighted_size = p.priority * p.size
        raw_allocation = (weighted_size / total_weighted_size) * total_frames
        p.allocation = max(math.floor(raw_allocation), min_frames)
        total_allocated += p.allocation
    
    # Distribute remainder to highest-priority processes
    remainder = total_frames - total_allocated
    sorted_by_priority = sorted(processes, key=lambda x: x.priority, reverse=True)
    
    for i in range(remainder):
        sorted_by_priority[i % len(processes)].allocation += 1
    
    return processes
 
def demonstrate_priority_effect():
    """Show how priority affects allocation."""
    
    # Scenario: Same sizes, different priorities
    print("\n=== Scenario 1: Same Size, Different Priority ===")
    processes = [
        PriorityProcess(1, "DB Server", 100, 
                       PRIORITY_WEIGHTS["system"], "system"),
        PriorityProcess(2, "Web App", 100, 
                       PRIORITY_WEIGHTS["interactive"], "interactive"),
        PriorityProcess(3, "Batch Job", 100, 
                       PRIORITY_WEIGHTS["batch"], "batch"),
        PriorityProcess(4, "Idle Task", 100, 
                       PRIORITY_WEIGHTS["idle"], "idle"),
    ]
    
    calculate_priority_weighted_allocation(processes, 200)
    
    for p in processes:
        print(f"  {p.name:12s} (priority={p.priority:4.1f}): "
              f"{p.allocation:3d} frames")
    
    # Scenario: Different sizes, different priorities
    print("\n=== Scenario 2: Priority Can Override Size ===")
    processes = [
        PriorityProcess(1, "Small Critical", 50, 
                       PRIORITY_WEIGHTS["system"], "system"),
        PriorityProcess(2, "Large Normal", 200, 
                       PRIORITY_WEIGHTS["normal"], "normal"),
    ]
    
    calculate_priority_weighted_allocation(processes, 100)
    
    for p in processes:
        weighted = p.priority * p.size
        print(f"  {p.name:15s}: size={p.size:3d}, "
              f"priority={p.priority:.1f}, "
              f"weighted={weighted:5.0f} -> {p.allocation:3d} frames")
 
if __name__ == "__main__":
    demonstrate_priority_effect()

Worked Example: Priority Overriding Size

Consider 100 frames and two processes:

Process	Size	Priority	Weighted Size	Allocation
Small Critical	50	5.0	250	71 frames
Large Normal	200	1.0	200	29 frames

Analysis: Despite being 4× smaller, the critical process receives 2.5× more frames because its priority weight (5.0) more than compensates for its size deficit. This demonstrates how priority-based allocation can ensure critical processes receive adequate resources regardless of size.

Priority Weight Magnitude Matters

The ratio between priority weights determines the strength of priority effects:

• Narrow range (1-2): Priority gently influences allocation; size still dominates • Moderate range (1-10): Priority significantly affects allocation; can override moderate size differences • Wide range (1-100): Priority dominates; high-priority small processes beat low-priority large ones

Choose weight ranges carefully to match organizational policy.

Priority Class Systems

An alternative to continuous priority weights is discrete priority classes. Each class has different allocation rules, creating clear policy boundaries.

Defining Priority Classes

A typical class hierarchy might include:

Class 1: Real-Time Critical

Guaranteed minimum allocation: 75% of working set estimate
Never subject to reclamation unless class 1 processes compete
Examples: Industrial control, medical monitoring, financial trading

Class 2: System Essential

Guaranteed minimum: 50% of request
Reclaimed only after Class 3+ exhausted
Examples: Kernel threads, core system services, databases

Class 3: Interactive Standard

Proportional allocation among Class 3 processes
Reclaimed after Class 4+ exhausted
Examples: User applications, development tools

Class 4: Background Batch

Proportional allocation from remaining frames
First to be reclaimed under pressure
Examples: Backup jobs, index builders, log processors

Class 5: Best-Effort Idle

Only allocated from truly idle frames
Immediately reclaimed upon any pressure
Examples: Prefetching, speculative work, screen savers

Converting Mermaid diagram...

priority_classes.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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
 
typedef enum {
    PCLASS_REALTIME = 0,    // Highest priority
    PCLASS_SYSTEM = 1,
    PCLASS_INTERACTIVE = 2,
    PCLASS_BACKGROUND = 3,
    PCLASS_BESTEFFORT = 4,  // Lowest priority
    PCLASS_COUNT = 5
} PriorityClass;
 
// Per-class configuration
typedef struct {
    const char* name;
    float guaranteed_fraction;  // Fraction of request guaranteed
    float weight;               // Weight for proportional within class
    bool reclaim_protected;     // Resist reclamation
    int reclaim_order;          // Lower = reclaimed later
} ClassConfig;
 
ClassConfig CLASS_CONFIGS[PCLASS_COUNT] = {
    {"RealTime",    0.75, 10.0, true,  5},
    {"System",      0.50,  5.0, true,  4},
    {"Interactive", 0.25,  2.0, false, 3},
    {"Background",  0.10,  1.0, false, 2},
    {"BestEffort",  0.00,  0.5, false, 1},
};
 
typedef struct {
    int pid;
    PriorityClass pclass;
    size_t size;
    size_t requested;
    size_t guaranteed;
    size_t allocated;
} ClassedProcess;
 
// Calculate guaranteed minimums based on class
void calculate_class_guarantees(
    ClassedProcess* processes,
    int process_count
) {
    for (int i = 0; i < process_count; i++) {
        ClassedProcess* p = &processes[i];
        ClassConfig* cfg = &CLASS_CONFIGS[p->pclass];
        
        // Guaranteed = fraction of requested (or size if no explicit request)
        size_t base = p->requested > 0 ? p->requested : p->size;
        p->guaranteed = (size_t)(base * cfg->guaranteed_fraction);
    }
}
 
// Allocate frames respecting class priorities
void allocate_by_class(
    ClassedProcess* processes,
    int process_count,
    size_t total_frames
) {
    size_t available = total_frames;
    
    // Phase 1: Satisfy guarantees, highest class first
    for (int c = 0; c < PCLASS_COUNT; c++) {
        for (int i = 0; i < process_count; i++) {
            if (processes[i].pclass == c) {
                size_t to_grant = processes[i].guaranteed;
                if (to_grant > available) {
                    to_grant = available;  // Can't satisfy guarantee!
                    // Log critical warning for high-priority classes
                    if (c <= PCLASS_INTERACTIVE) {
                        log_warning("Cannot satisfy guarantee for PID %d",
                                   processes[i].pid);
                    }
                }
                processes[i].allocated = to_grant;
                available -= to_grant;
            }
        }
    }
    
    // Phase 2: Distribute remaining frames by weighted proportion
    if (available > 0) {
        // Calculate total weighted demand for unfulfilled requests
        float total_weighted_demand = 0;
        for (int i = 0; i < process_count; i++) {
            size_t unfulfilled = processes[i].size - processes[i].allocated;
            if (unfulfilled > 0) {
                ClassConfig* cfg = &CLASS_CONFIGS[processes[i].pclass];
                total_weighted_demand += unfulfilled * cfg->weight;
            }
        }
        
        // Distribute proportionally to weighted unfulfilled demand
        for (int i = 0; i < process_count; i++) {
            size_t unfulfilled = processes[i].size - processes[i].allocated;
            if (unfulfilled > 0 && total_weighted_demand > 0) {
                ClassConfig* cfg = &CLASS_CONFIGS[processes[i].pclass];
                float share = (unfulfilled * cfg->weight) / total_weighted_demand;
                size_t bonus = (size_t)(available * share);
                processes[i].allocated += bonus;
            }
        }
    }
}
 
// Select victim for reclamation based on class order
int select_reclaim_victim(
    ClassedProcess* processes,
    int process_count,
    size_t frames_needed
) {
    // Find lowest-priority process with reclaimable frames
    int victim = -1;
    int lowest_reclaim_order = 999;
    
    for (int i = 0; i < process_count; i++) {
        ClassConfig* cfg = &CLASS_CONFIGS[processes[i].pclass];
        
        // Check if this process can be reclaimed
        size_t reclaimable = 0;
        if (processes[i].allocated > processes[i].guaranteed) {
            reclaimable = processes[i].allocated - processes[i].guaranteed;
        }
        
        if (reclaimable >= frames_needed) {
            if (cfg->reclaim_order < lowest_reclaim_order) {
                lowest_reclaim_order = cfg->reclaim_order;
                victim = i;
            }
        }
    }
    
    return victim;
}

Priority Inversion and Priority Donation

Priority-based allocation, like priority-based scheduling, is susceptible to priority inversion—scenarios where priority ordering is violated due to indirect dependencies.

Memory Priority Inversion Scenario

Consider three processes:

P_high: Critical priority, waiting for data from shared memory
P_medium: Medium priority, running independently
P_low: Low priority, preparing data in shared memory for P_high

If memory pressure causes frames to be reclaimed from P_low (the lowest priority), P_low slows down, which delays P_high (even though P_high has highest priority). Meanwhile, P_medium continues running with full allocation.

Result: High-priority process blocked by low-priority preemption, while medium-priority runs freely—classic priority inversion.

Converting Mermaid diagram...

Priority Donation for Memory

Just as CPU scheduling uses priority inheritance/donation to address inversion, memory allocation can temporarily elevate the priority of processes blocking high-priority work.

When P_high blocks waiting for P_low:

Detect the dependency (shared memory segment, IPC channel, etc.)
Temporarily elevate P_low's memory priority to P_high's level
P_low receives protected allocation, accelerating its work
When P_low completes and unblocks P_high, restore P_low's original priority

Challenges:

Dependency detection is non-trivial (requires IPC/shared memory tracking)
Chain dependencies: A waiting for B waiting for C
Cycles: Potential for deadlock-like scenarios
Overhead: Tracking and updating priorities adds complexity

priority_donation_memory.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
#include <stdbool.h>
 
#define MAX_DONATION_CHAIN 10
 
typedef struct {
    int pid;
    int original_priority;
    int effective_priority;   // May be boosted by donation
    int donated_from;         // PID that donated priority (-1 if none)
    bool has_donation;
} PriorityState;
 
typedef struct {
    int blocker_pid;          // Process being waited on
    int waiter_pid;           // Process that is waiting
    int resource_id;          // Shared memory segment, lock, etc.
} WaitDependency;
 
// Priority donation for memory allocation
void apply_priority_donation(
    PriorityState* states,
    int state_count,
    WaitDependency* deps,
    int dep_count
) {
    // Reset effective priorities to originals
    for (int i = 0; i < state_count; i++) {
        if (!states[i].has_donation) {
            states[i].effective_priority = states[i].original_priority;
            states[i].donated_from = -1;
        }
    }
    
    // Apply donations iteratively (handle chains)
    bool changed;
    int iterations = 0;
    
    do {
        changed = false;
        iterations++;
        
        for (int d = 0; d < dep_count; d++) {
            WaitDependency* dep = &deps[d];
            
            // Find waiter and blocker states
            PriorityState* waiter = NULL;
            PriorityState* blocker = NULL;
            
            for (int i = 0; i < state_count; i++) {
                if (states[i].pid == dep->waiter_pid) waiter = &states[i];
                if (states[i].pid == dep->blocker_pid) blocker = &states[i];
            }
            
            if (!waiter || !blocker) continue;
            
            // If waiter has higher effective priority, donate to blocker
            if (waiter->effective_priority > blocker->effective_priority) {
                blocker->effective_priority = waiter->effective_priority;
                blocker->donated_from = waiter->pid;
                blocker->has_donation = true;
                changed = true;
                
                log_info("Priority donation: P%d (%d) -> P%d (now %d)",
                        waiter->pid, waiter->effective_priority,
                        blocker->pid, blocker->effective_priority);
            }
        }
        
    } while (changed && iterations < MAX_DONATION_CHAIN);
    
    if (iterations >= MAX_DONATION_CHAIN) {
        log_warning("Priority donation chain limit reached - possible cycle");
    }
}
 
// Release donation when blocking relationship ends
void release_priority_donation(
    PriorityState* states,
    int state_count,
    int released_pid
) {
    for (int i = 0; i < state_count; i++) {
        if (states[i].donated_from == released_pid) {
            // Find new highest donation or fall back to original
            states[i].effective_priority = states[i].original_priority;
            states[i].has_donation = false;
            states[i].donated_from = -1;
            
            log_info("Priority donation released for P%d, "
                    "priority restored to %d",
                    states[i].pid, states[i].original_priority);
        }
    }
}
 
// Integrate effective priority into memory allocation
int get_allocation_priority(PriorityState* states, int state_count, int pid) {
    for (int i = 0; i < state_count; i++) {
        if (states[i].pid == pid) {
            return states[i].effective_priority;  // Use donated if applicable
        }
    }
    return 0;  // Unknown process gets minimum priority
}

Practical Considerations

Full priority donation in memory management is rare in practice due to complexity. More common approaches include:

• Minimum floors for all processes: Even low-priority processes get enough frames to make reasonable progress • Gradual reclamation: Don't immediately starve low-priority processes; reclaim gradually • Dependency-aware grouping: Processes with shared resources are allocated as a group • Bounded inversion duration: Limit how long priority inversion can persist before intervention

Integration with Other Allocation Strategies

In practice, priority-based allocation rarely operates in isolation. It's typically integrated with proportional allocation and subject to minimum/maximum constraints. The result is a hybrid system that balances multiple concerns.

Common Integration Patterns

Pattern 1: Priority-Weighted Proportional

As shown earlier: aᵢ = (pᵢ × sᵢ) / Σ(pⱼ × sⱼ) × m

Priority acts as a multiplier on size, influencing proportional distribution.

Pattern 2: Priority-Tiered with Proportional Within Tiers

Divide total frames among priority tiers based on policy
- Tier 1 (Critical): 40% of frames
- Tier 2 (Normal): 50% of frames
- Tier 3 (Background): 10% of frames
Within each tier, allocate proportionally by size

Pattern 3: Minimum Guarantees + Proportional Remainder

Satisfy priority-based minimum guarantees first
Distribute remaining frames proportionally (ignoring priority)
Priority influences guarantees but not the proportional pool

Integration Pattern Comparison
Pattern	Priority Role	Size Role	Best For
Priority-Weighted Proportional	Multiplier on size	Base of allocation	Continuous priority spectrum
Priority-Tiered	Determines tier membership	Proportional within tier	Clear priority boundaries
Guarantees + Proportional	Sets minimum floors	Distributes remainder	Protecting critical processes
Priority Reclaim Order	Determines victim selection	Determines initial allocation	Managing pressure gracefully

hybrid_allocation.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
from dataclasses import dataclass
from typing import List, Tuple
from enum import IntEnum
 
class PriorityTier(IntEnum):
    CRITICAL = 0     # Tier 1: Critical processes
    NORMAL = 1       # Tier 2: Normal processes
    BACKGROUND = 2   # Tier 3: Background processes
 
# Policy: frame distribution among tiers
TIER_ALLOCATION = {
    PriorityTier.CRITICAL: 0.40,    # 40% of frames
    PriorityTier.NORMAL: 0.50,      # 50% of frames
    PriorityTier.BACKGROUND: 0.10,  # 10% of frames
}
 
@dataclass
class Process:
    pid: int
    name: str
    size: int
    tier: PriorityTier
    min_guarantee: int = 0    # Absolute minimum frames
    allocation: int = 0
 
def tiered_proportional_allocation(
    processes: List[Process],
    total_frames: int
) -> List[Process]:
    """
    Two-level allocation:
    1. Divide frames among priority tiers
    2. Proportionally allocate within each tier
    """
    
    # Group processes by tier
    tiers = {t: [] for t in PriorityTier}
    for p in processes:
        tiers[p.tier].append(p)
    
    # Calculate frames per tier
    tier_frames = {}
    for tier, fraction in TIER_ALLOCATION.items():
        tier_frames[tier] = int(total_frames * fraction)
    
    # Handle empty tiers: redistribute to non-empty tiers
    unused = 0
    for tier in PriorityTier:
        if not tiers[tier]:
            unused += tier_frames[tier]
            tier_frames[tier] = 0
    
    # Redistribute unused to highest non-empty tier
    for tier in PriorityTier:
        if tiers[tier]:
            tier_frames[tier] += unused
            break
    
    # Allocate proportionally within each tier
    for tier, procs in tiers.items():
        if not procs:
            continue
            
        available = tier_frames[tier]
        
        # First pass: satisfy minimum guarantees
        guaranteed_total = 0
        for p in procs:
            guaranteed_total += p.min_guarantee
        
        if guaranteed_total > available:
            # Cannot satisfy guarantees - critical error for high tiers
            print(f"WARNING: Cannot satisfy guarantees for tier {tier.name}")
            # Pro-rate guarantees
            for p in procs:
                p.allocation = int(p.min_guarantee * available / guaranteed_total)
            continue
        
        # Assign guarantees
        for p in procs:
            p.allocation = p.min_guarantee
        
        # Second pass: proportional distribution of remainder
        remainder = available - guaranteed_total
        total_unfulfilled = sum(max(0, p.size - p.allocation) for p in procs)
        
        if total_unfulfilled > 0 and remainder > 0:
            for p in procs:
                unfulfilled = max(0, p.size - p.allocation)
                if unfulfilled > 0:
                    share = unfulfilled / total_unfulfilled
                    bonus = int(remainder * share)
                    p.allocation += bonus
    
    return processes
 
def demonstrate_tiered_allocation():
    processes = [
        # Critical tier
        Process(1, "Database", 400, PriorityTier.CRITICAL, 100),
        Process(2, "API Server", 200, PriorityTier.CRITICAL, 50),
        
        # Normal tier  
        Process(3, "Web Frontend", 150, PriorityTier.NORMAL, 30),
        Process(4, "Worker", 100, PriorityTier.NORMAL, 20),
        Process(5, "Cache", 80, PriorityTier.NORMAL, 20),
        
        # Background tier
        Process(6, "Backup", 200, PriorityTier.BACKGROUND, 10),
        Process(7, "Logger", 50, PriorityTier.BACKGROUND, 5),
    ]
    
    result = tiered_proportional_allocation(processes, 500)
    
    print("\n=== Tiered Proportional Allocation ===")
    print(f"Total frames: 500\n")
    
    current_tier = None
    for p in sorted(result, key=lambda x: (x.tier, -x.allocation)):
        if p.tier != current_tier:
            current_tier = p.tier
            print(f"\n{current_tier.name} TIER:")
        pct = p.allocation / 500 * 100
        print(f"  {p.name:15s}: size={p.size:3d}, "
              f"min={p.min_guarantee:3d}, "
              f"alloc={p.allocation:3d} ({pct:4.1f}%)")
 
if __name__ == "__main__":
    demonstrate_tiered_allocation()

Advantages and Challenges

Priority-based allocation introduces explicit organizational control over memory distribution. This power comes with both significant benefits and notable challenges.

Advantages

•Service Differentiation — Critical workloads can be protected from resource competition with less important work
•Predictable Critical Performance — High-priority processes experience consistent memory availability
•Policy Enforcement — Organizational priorities translate directly into resource allocation
•Graceful Degradation — Under pressure, low-priority work suffers first, preserving critical function
•Multi-tenant Fairness — Premium customers can receive better resource treatment
•Real-time Support — Critical deadlines can be met by prioritizing memory allocation

Challenges

•Priority Assignment Complexity — Determining correct priorities requires deep system understanding
•Priority Inflation — Everyone wants 'critical' priority; discipline erodes over time
•Starvation Risk — Low-priority processes may never receive adequate allocation
•Priority Inversion — Indirect dependencies can violate priority intent
•Static vs. Dynamic Mismatch — Static priorities may not match dynamic importance
•Management Overhead — Priority schemes require ongoing administrative attention

The Priority Inflation Trap

Over time, priority systems suffer from inflation. Every service owner believes their service is critical. Gradually, most processes end up in high-priority tiers, negating the priority system entirely.

Mitigation strategies: • Quota on high-priority slots (only N processes can be critical) • Periodic priority audits with mandatory justification • Priority 'taxes' (high-priority costs more in resource accounting) • Automatic demotion if actual behavior doesn't match critical classification

Starvation Prevention

Pure priority-based allocation can completely starve low-priority processes under sustained pressure. This may be acceptable for truly "best-effort" work but is problematic for anything that must eventually complete.

Prevention Mechanisms:

Minimum Floors — Even lowest priority gets some allocation (e.g., architectural minimum + 10%)
Aging — Low-priority processes that haven't run gain priority over time
Burst Periods — Periodic intervals where low-priority receives temporary boost
Work Conservation — If high-priority doesn't need frames, they go to low-priority
Progress Requirements — Processes must make forward progress; if starved, force temporary priority boost

Real-World Implementations

Priority-based memory allocation manifests in various forms across modern operating systems and orchestration platforms.

Linux: OOM Killer Scoring

Linux doesn't use priority for proactive allocation, but uses it for reactive reclamation through the OOM (Out-Of-Memory) killer. Each process has an oom_score_adj value (-1000 to +1000) that influences its likelihood of being killed during OOM conditions.

oom_score_configuration.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
# Linux OOM score adjustment for priority-based protection
 
# Protect critical processes from OOM killer
# oom_score_adj: -1000 = never kill, +1000 = always kill first
 
# Critical: protect from OOM
echo "-1000" > /proc/$(pidof systemd)/oom_score_adj
echo "-900"  > /proc/$(pidof sshd)/oom_score_adj
echo "-500"  > /proc/$(pidof postgresql)/oom_score_adj
 
# Normal: default behavior
echo "0" > /proc/$(pidof nginx)/oom_score_adj
 
# Deprioritize: kill these first if needed
echo "500"  > /proc/$(pidof logrotate)/oom_score_adj
echo "750"  > /proc/$(pidof updatedb)/oom_score_adj
echo "1000" > /proc/$(pidof stress-test)/oom_score_adj
 
# View current OOM scores
echo "Process OOM Scores:"
for pid in $(pgrep -x "systemd|sshd|postgresql|nginx"); do
    name=$(cat /proc/$pid/comm 2>/dev/null)
    score=$(cat /proc/$pid/oom_score 2>/dev/null)
    adj=$(cat /proc/$pid/oom_score_adj 2>/dev/null)
    echo "  $name (PID $pid): score=$score, adj=$adj"
done

Linux: cgroups memory.high and memory.max

While not strictly priority-based, cgroups allow hierarchical resource control that achieves similar effects:

Process groups in different cgroups receive different memory limits
Under pressure, groups are throttled based on their configuration
Combined with process priorities, creates priority-tiered allocation

Windows: Memory Priority

Windows explicitly supports memory priority (0-7) for processes:

Priority affects page-out order during working set trimming
Higher memory priority = pages retained longer
Integrates with process priority but is separately configurable

WindowsMemoryPriority.ps1
PowerShell
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
# Windows Memory Priority Configuration
 
# Memory priority levels (0-7, higher = more important)
# 0: Very low - pages evicted first
# 3: Normal (default)
# 5: High
# 7: Critical - pages evicted last
 
# Set memory priority for a process
function Set-ProcessMemoryPriority {
    param(
        [Parameter(Mandatory=$true)]
        [int]$ProcessId,
        [Parameter(Mandatory=$true)]
        [ValidateRange(0,7)]
        [int]$Priority
    )
    
    $process = Get-Process -Id $ProcessId -ErrorAction Stop
    
    # Use Windows API via P/Invoke
    Add-Type -TypeDefinition @"
        using System;
        using System.Runtime.InteropServices;
        
        public class MemoryPriority {
            [DllImport("kernel32.dll", SetLastError = true)]
            public static extern bool SetProcessInformation(
                IntPtr hProcess,
                int ProcessInformationClass,
                ref int ProcessInformation,
                int ProcessInformationSize);
                
            public const int ProcessMemoryPriority = 0;
        }
"@
    
    $priorityValue = $Priority
    $result = [MemoryPriority]::SetProcessInformation(
        $process.Handle,
        0,  # ProcessMemoryPriority
        [ref]$priorityValue,
        4   # sizeof(int)
    )
    
    if ($result) {
        Write-Host "Set memory priority for $($process.Name) to $Priority"
    } else {
        Write-Error "Failed to set memory priority"
    }
}
 
# Example: Protect critical processes
$criticalProcesses = @("sqlservr", "w3wp", "lsass")
foreach ($procName in $criticalProcesses) {
    $procs = Get-Process -Name $procName -ErrorAction SilentlyContinue
    foreach ($proc in $procs) {
        Set-ProcessMemoryPriority -ProcessId $proc.Id -Priority 7
    }
}
 
# Deprioritize background processes
$backgroundProcesses = @("SearchIndexer", "TiWorker", "MsMpEng")
foreach ($procName in $backgroundProcesses) {
    $procs = Get-Process -Name $procName -ErrorAction SilentlyContinue
    foreach ($proc in $procs) {
        Set-ProcessMemoryPriority -ProcessId $proc.Id -Priority 1
    }
}

Cloud and Container Orchestration

Modern orchestration systems implement priority-based allocation at higher abstraction levels:

• Kubernetes Priority Classes: Pods have priority; during eviction, lower priority pods are removed first • Docker Compose: memory reservations act as priority floors • AWS ECS: Task priority affects placement and eviction decisions • Nomad: Job priorities influence scheduling and preemption

These systems don't control individual frames but achieve similar effects through container-level memory limits and eviction policies.

Summary and Key Takeaways

We have thoroughly explored priority-based allocation, extending our understanding beyond size-blind (equal) and size-aware (proportional) approaches to importance-aware allocation. Let's consolidate the essential concepts:

Core Concepts Mastered

•Priority Fundamentals — Priority can derive from process type, administrator configuration, resource class membership, or dynamic behavior. Different sources have different stability and appropriate use cases.
•Priority Models — Priority classes (discrete tiers), priority weights (continuous multipliers), and priority ordering (reclamation sequence) each offer different expressiveness and complexity tradeoffs.
•Priority-Weighted Allocation — Extending proportional allocation with priority weights: aᵢ = (pᵢ × sᵢ) / Σ(pⱼ × sⱼ) × m. Priority acts as a multiplier on size.
•Priority Class Systems — Discrete classes with different allocation rules provide clear policy boundaries: guaranteed minimums, reclamation ordering, and proportional pools within classes.
•Priority Inversion — Indirect dependencies can violate priority intent. Priority donation temporarily elevates blockers of high-priority waiters. Practical systems often use simpler mechanisms like minimum floors.
•Integration Patterns — Priority rarely operates alone; it combines with proportional allocation through weighted-proportional, tiered, or guarantee-plus-proportional patterns.
•Practical Challenges — Priority inflation, starvation risk, and management overhead require ongoing attention. Mitigation mechanisms include quotas, aging, and minimum floors.

Looking Ahead

We've now covered three fundamental allocation strategies: equal (fairness-focused), proportional (size-aware), and priority-based (importance-aware). Real systems rarely use any single approach exclusively.

In the next page, we examine combination approaches that blend these strategies, creating allocation policies that balance fairness, size-appropriateness, and priority considerations simultaneously. These hybrid approaches form the foundation of production memory management in modern operating systems.

Page Complete

You now understand priority-based allocation comprehensively: how to model and represent priority, translate priority into allocation decisions, handle priority inversion, integrate priority with proportional allocation, and implement priority schemes in practice. This knowledge enables you to design and analyze memory allocation policies that reflect organizational importance hierarchies.

Priority-based Allocation

Not All Processes Are Created Equal

What You Will Learn

Conceptual Foundation

Defining Priority

Priority in memory allocation can derive from multiple sources:

System-Defined Priority:

Kernel processes (highest priority—system stability)
System services (high priority—core functionality)
Interactive user processes (medium-high priority—responsiveness)
Batch/background processes (lower priority—throughput-oriented)

User/Administrator-Defined Priority:

Critical production workloads
Important development/test environments
Nice-value adjusted processes
Resource class/quota group membership

Dynamic/Behavioral Priority:

Processes with high page fault rates (may need more frames)
Processes approaching deadlines (real-time consideration)
Recently interactive processes (responsiveness boost)

Priority Sources and Their Characteristics
Priority Source	Determination	Stability	Example
Process Type	Kernel classification	Very stable	Kernel threads vs. user processes
Nice Value	User/administrator set	Stable unless changed	nice -n -10 vs. nice -n 19
Resource Class	Group membership	Stable per-session	Production vs. development cgroups
Real-time Class	Scheduler classification	Stable	SCHED_FIFO vs. SCHED_OTHER
Dynamic Behavior	Runtime measurement	Fluctuates	Page fault rate, CPU usage pattern
User Identity	Authentication	Stable per-session	Root/admin vs. regular user

Priority Models

Several models exist for translating priority into allocation:

Model 1: Priority Classes

Group processes into discrete classes, each with different allocation rules:

Class A (Critical): Guaranteed minimum allocation, never reclaimed first
Class B (Normal): Standard proportional allocation
Class C (Background): Reduced allocation, first to be reclaimed

Model 2: Priority Weights

Assign numerical weights to processes; allocation is weighted-proportional:

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

Where pᵢ is the priority weight for process i.

Model 3: Priority Ordering

Under memory pressure, reclaim frames in priority order—lowest priority first. Allocation is implicit rather than explicit.

Priority vs. Size Interaction

Priority-based allocation raises a fundamental question: should a small high-priority process get more frames than a large low-priority process? The answer depends on your priority model:

Most systems use multiplicative or hybrid approaches.

Priority-Weighted Allocation

The most common approach to priority-based allocation extends proportional allocation with priority weights. This creates a unified framework that considers both size and importance.

Mathematical Formulation

For process i with:

sᵢ = size (pages)
pᵢ = priority weight (typically 1-1000, or normalized 0.0-1.0)
m = total available frames

The weighted allocation is:

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

priority_weighted_allocation.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
from dataclasses import dataclass
from typing import List, Dict
import math
 
@dataclass
class PriorityProcess:
    pid: int
    name: str
    size: int              # Virtual memory size in pages
    priority: float        # Priority weight (default 1.0)
    priority_class: str    # Classification for reporting
    allocation: int = 0    # Assigned frames
    
# Example priority weights by class
PRIORITY_WEIGHTS = {
    "kernel": 10.0,        # Critical kernel processes
    "system": 5.0,         # System services
    "interactive": 2.0,    # Interactive user applications
    "normal": 1.0,         # Standard processes
    "batch": 0.5,          # Background batch jobs
    "idle": 0.1,           # Idle-time only processes
}
 
def calculate_priority_weighted_allocation(
    processes: List[PriorityProcess],
    total_frames: int,
    min_frames: int = 3
) -> List[PriorityProcess]:
    """
    Calculate priority-weighted proportional allocation.
    
    Each process receives frames proportional to:
        (priority_weight × size) / sum(all priority_weight × size)
    """
    if not processes:
        return processes
    
    # Calculate total weighted size
    total_weighted_size = sum(
        p.priority * p.size for p in processes
    )
    
    if total_weighted_size == 0:
        # Edge case: all weighted sizes are zero
        per_process = total_frames // len(processes)
        for p in processes:
            p.allocation = max(per_process, min_frames)
        return processes
    
    # Calculate raw allocations
    total_allocated = 0
    for p in processes:
        weighted_size = p.priority * p.size
        raw_allocation = (weighted_size / total_weighted_size) * total_frames
        p.allocation = max(math.floor(raw_allocation), min_frames)
        total_allocated += p.allocation
    
    # Distribute remainder to highest-priority processes
    remainder = total_frames - total_allocated
    sorted_by_priority = sorted(processes, key=lambda x: x.priority, reverse=True)
    
    for i in range(remainder):
        sorted_by_priority[i % len(processes)].allocation += 1
    
    return processes
 
def demonstrate_priority_effect():
    """Show how priority affects allocation."""
    
    # Scenario: Same sizes, different priorities
    print("\n=== Scenario 1: Same Size, Different Priority ===")
    processes = [
        PriorityProcess(1, "DB Server", 100, 
                       PRIORITY_WEIGHTS["system"], "system"),
        PriorityProcess(2, "Web App", 100, 
                       PRIORITY_WEIGHTS["interactive"], "interactive"),
        PriorityProcess(3, "Batch Job", 100, 
                       PRIORITY_WEIGHTS["batch"], "batch"),
        PriorityProcess(4, "Idle Task", 100, 
                       PRIORITY_WEIGHTS["idle"], "idle"),
    ]
    
    calculate_priority_weighted_allocation(processes, 200)
    
    for p in processes:
        print(f"  {p.name:12s} (priority={p.priority:4.1f}): "
              f"{p.allocation:3d} frames")
    
    # Scenario: Different sizes, different priorities
    print("\n=== Scenario 2: Priority Can Override Size ===")
    processes = [
        PriorityProcess(1, "Small Critical", 50, 
                       PRIORITY_WEIGHTS["system"], "system"),
        PriorityProcess(2, "Large Normal", 200, 
                       PRIORITY_WEIGHTS["normal"], "normal"),
    ]
    
    calculate_priority_weighted_allocation(processes, 100)
    
    for p in processes:
        weighted = p.priority * p.size
        print(f"  {p.name:15s}: size={p.size:3d}, "
              f"priority={p.priority:.1f}, "
              f"weighted={weighted:5.0f} -> {p.allocation:3d} frames")
 
if __name__ == "__main__":
    demonstrate_priority_effect()

Worked Example: Priority Overriding Size

Consider 100 frames and two processes:

Process	Size	Priority	Weighted Size	Allocation
Small Critical	50	5.0	250	71 frames
Large Normal	200	1.0	200	29 frames

Priority Weight Magnitude Matters

The ratio between priority weights determines the strength of priority effects:

Choose weight ranges carefully to match organizational policy.

Priority Class Systems

An alternative to continuous priority weights is discrete priority classes. Each class has different allocation rules, creating clear policy boundaries.

Defining Priority Classes

A typical class hierarchy might include:

Class 1: Real-Time Critical

Guaranteed minimum allocation: 75% of working set estimate
Never subject to reclamation unless class 1 processes compete
Examples: Industrial control, medical monitoring, financial trading

Class 2: System Essential

Guaranteed minimum: 50% of request
Reclaimed only after Class 3+ exhausted
Examples: Kernel threads, core system services, databases

Class 3: Interactive Standard

Proportional allocation among Class 3 processes
Reclaimed after Class 4+ exhausted
Examples: User applications, development tools

Class 4: Background Batch

Proportional allocation from remaining frames
First to be reclaimed under pressure
Examples: Backup jobs, index builders, log processors

Class 5: Best-Effort Idle

Only allocated from truly idle frames
Immediately reclaimed upon any pressure
Examples: Prefetching, speculative work, screen savers

Converting Mermaid diagram...

priority_classes.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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
 
typedef enum {
    PCLASS_REALTIME = 0,    // Highest priority
    PCLASS_SYSTEM = 1,
    PCLASS_INTERACTIVE = 2,
    PCLASS_BACKGROUND = 3,
    PCLASS_BESTEFFORT = 4,  // Lowest priority
    PCLASS_COUNT = 5
} PriorityClass;
 
// Per-class configuration
typedef struct {
    const char* name;
    float guaranteed_fraction;  // Fraction of request guaranteed
    float weight;               // Weight for proportional within class
    bool reclaim_protected;     // Resist reclamation
    int reclaim_order;          // Lower = reclaimed later
} ClassConfig;
 
ClassConfig CLASS_CONFIGS[PCLASS_COUNT] = {
    {"RealTime",    0.75, 10.0, true,  5},
    {"System",      0.50,  5.0, true,  4},
    {"Interactive", 0.25,  2.0, false, 3},
    {"Background",  0.10,  1.0, false, 2},
    {"BestEffort",  0.00,  0.5, false, 1},
};
 
typedef struct {
    int pid;
    PriorityClass pclass;
    size_t size;
    size_t requested;
    size_t guaranteed;
    size_t allocated;
} ClassedProcess;
 
// Calculate guaranteed minimums based on class
void calculate_class_guarantees(
    ClassedProcess* processes,
    int process_count
) {
    for (int i = 0; i < process_count; i++) {
        ClassedProcess* p = &processes[i];
        ClassConfig* cfg = &CLASS_CONFIGS[p->pclass];
        
        // Guaranteed = fraction of requested (or size if no explicit request)
        size_t base = p->requested > 0 ? p->requested : p->size;
        p->guaranteed = (size_t)(base * cfg->guaranteed_fraction);
    }
}
 
// Allocate frames respecting class priorities
void allocate_by_class(
    ClassedProcess* processes,
    int process_count,
    size_t total_frames
) {
    size_t available = total_frames;
    
    // Phase 1: Satisfy guarantees, highest class first
    for (int c = 0; c < PCLASS_COUNT; c++) {
        for (int i = 0; i < process_count; i++) {
            if (processes[i].pclass == c) {
                size_t to_grant = processes[i].guaranteed;
                if (to_grant > available) {
                    to_grant = available;  // Can't satisfy guarantee!
                    // Log critical warning for high-priority classes
                    if (c <= PCLASS_INTERACTIVE) {
                        log_warning("Cannot satisfy guarantee for PID %d",
                                   processes[i].pid);
                    }
                }
                processes[i].allocated = to_grant;
                available -= to_grant;
            }
        }
    }
    
    // Phase 2: Distribute remaining frames by weighted proportion
    if (available > 0) {
        // Calculate total weighted demand for unfulfilled requests
        float total_weighted_demand = 0;
        for (int i = 0; i < process_count; i++) {
            size_t unfulfilled = processes[i].size - processes[i].allocated;
            if (unfulfilled > 0) {
                ClassConfig* cfg = &CLASS_CONFIGS[processes[i].pclass];
                total_weighted_demand += unfulfilled * cfg->weight;
            }
        }
        
        // Distribute proportionally to weighted unfulfilled demand
        for (int i = 0; i < process_count; i++) {
            size_t unfulfilled = processes[i].size - processes[i].allocated;
            if (unfulfilled > 0 && total_weighted_demand > 0) {
                ClassConfig* cfg = &CLASS_CONFIGS[processes[i].pclass];
                float share = (unfulfilled * cfg->weight) / total_weighted_demand;
                size_t bonus = (size_t)(available * share);
                processes[i].allocated += bonus;
            }
        }
    }
}
 
// Select victim for reclamation based on class order
int select_reclaim_victim(
    ClassedProcess* processes,
    int process_count,
    size_t frames_needed
) {
    // Find lowest-priority process with reclaimable frames
    int victim = -1;
    int lowest_reclaim_order = 999;
    
    for (int i = 0; i < process_count; i++) {
        ClassConfig* cfg = &CLASS_CONFIGS[processes[i].pclass];
        
        // Check if this process can be reclaimed
        size_t reclaimable = 0;
        if (processes[i].allocated > processes[i].guaranteed) {
            reclaimable = processes[i].allocated - processes[i].guaranteed;
        }
        
        if (reclaimable >= frames_needed) {
            if (cfg->reclaim_order < lowest_reclaim_order) {
                lowest_reclaim_order = cfg->reclaim_order;
                victim = i;
            }
        }
    }
    
    return victim;
}

Priority Inversion and Priority Donation

Priority-based allocation, like priority-based scheduling, is susceptible to priority inversion—scenarios where priority ordering is violated due to indirect dependencies.

Memory Priority Inversion Scenario

Consider three processes:

P_high: Critical priority, waiting for data from shared memory
P_medium: Medium priority, running independently
P_low: Low priority, preparing data in shared memory for P_high

Result: High-priority process blocked by low-priority preemption, while medium-priority runs freely—classic priority inversion.

Converting Mermaid diagram...

Priority Donation for Memory

Just as CPU scheduling uses priority inheritance/donation to address inversion, memory allocation can temporarily elevate the priority of processes blocking high-priority work.

When P_high blocks waiting for P_low:

Detect the dependency (shared memory segment, IPC channel, etc.)
Temporarily elevate P_low's memory priority to P_high's level
P_low receives protected allocation, accelerating its work
When P_low completes and unblocks P_high, restore P_low's original priority

Challenges:

Dependency detection is non-trivial (requires IPC/shared memory tracking)
Chain dependencies: A waiting for B waiting for C
Cycles: Potential for deadlock-like scenarios
Overhead: Tracking and updating priorities adds complexity

priority_donation_memory.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
#include <stdbool.h>
 
#define MAX_DONATION_CHAIN 10
 
typedef struct {
    int pid;
    int original_priority;
    int effective_priority;   // May be boosted by donation
    int donated_from;         // PID that donated priority (-1 if none)
    bool has_donation;
} PriorityState;
 
typedef struct {
    int blocker_pid;          // Process being waited on
    int waiter_pid;           // Process that is waiting
    int resource_id;          // Shared memory segment, lock, etc.
} WaitDependency;
 
// Priority donation for memory allocation
void apply_priority_donation(
    PriorityState* states,
    int state_count,
    WaitDependency* deps,
    int dep_count
) {
    // Reset effective priorities to originals
    for (int i = 0; i < state_count; i++) {
        if (!states[i].has_donation) {
            states[i].effective_priority = states[i].original_priority;
            states[i].donated_from = -1;
        }
    }
    
    // Apply donations iteratively (handle chains)
    bool changed;
    int iterations = 0;
    
    do {
        changed = false;
        iterations++;
        
        for (int d = 0; d < dep_count; d++) {
            WaitDependency* dep = &deps[d];
            
            // Find waiter and blocker states
            PriorityState* waiter = NULL;
            PriorityState* blocker = NULL;
            
            for (int i = 0; i < state_count; i++) {
                if (states[i].pid == dep->waiter_pid) waiter = &states[i];
                if (states[i].pid == dep->blocker_pid) blocker = &states[i];
            }
            
            if (!waiter || !blocker) continue;
            
            // If waiter has higher effective priority, donate to blocker
            if (waiter->effective_priority > blocker->effective_priority) {
                blocker->effective_priority = waiter->effective_priority;
                blocker->donated_from = waiter->pid;
                blocker->has_donation = true;
                changed = true;
                
                log_info("Priority donation: P%d (%d) -> P%d (now %d)",
                        waiter->pid, waiter->effective_priority,
                        blocker->pid, blocker->effective_priority);
            }
        }
        
    } while (changed && iterations < MAX_DONATION_CHAIN);
    
    if (iterations >= MAX_DONATION_CHAIN) {
        log_warning("Priority donation chain limit reached - possible cycle");
    }
}
 
// Release donation when blocking relationship ends
void release_priority_donation(
    PriorityState* states,
    int state_count,
    int released_pid
) {
    for (int i = 0; i < state_count; i++) {
        if (states[i].donated_from == released_pid) {
            // Find new highest donation or fall back to original
            states[i].effective_priority = states[i].original_priority;
            states[i].has_donation = false;
            states[i].donated_from = -1;
            
            log_info("Priority donation released for P%d, "
                    "priority restored to %d",
                    states[i].pid, states[i].original_priority);
        }
    }
}
 
// Integrate effective priority into memory allocation
int get_allocation_priority(PriorityState* states, int state_count, int pid) {
    for (int i = 0; i < state_count; i++) {
        if (states[i].pid == pid) {
            return states[i].effective_priority;  // Use donated if applicable
        }
    }
    return 0;  // Unknown process gets minimum priority
}

Practical Considerations

Full priority donation in memory management is rare in practice due to complexity. More common approaches include:

Integration with Other Allocation Strategies

Common Integration Patterns

Pattern 1: Priority-Weighted Proportional

As shown earlier: aᵢ = (pᵢ × sᵢ) / Σ(pⱼ × sⱼ) × m

Priority acts as a multiplier on size, influencing proportional distribution.

Pattern 2: Priority-Tiered with Proportional Within Tiers

Divide total frames among priority tiers based on policy
- Tier 1 (Critical): 40% of frames
- Tier 2 (Normal): 50% of frames
- Tier 3 (Background): 10% of frames
Within each tier, allocate proportionally by size

Pattern 3: Minimum Guarantees + Proportional Remainder

Satisfy priority-based minimum guarantees first
Distribute remaining frames proportionally (ignoring priority)
Priority influences guarantees but not the proportional pool

Integration Pattern Comparison
Pattern	Priority Role	Size Role	Best For
Priority-Weighted Proportional	Multiplier on size	Base of allocation	Continuous priority spectrum
Priority-Tiered	Determines tier membership	Proportional within tier	Clear priority boundaries
Guarantees + Proportional	Sets minimum floors	Distributes remainder	Protecting critical processes
Priority Reclaim Order	Determines victim selection	Determines initial allocation	Managing pressure gracefully

hybrid_allocation.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
from dataclasses import dataclass
from typing import List, Tuple
from enum import IntEnum
 
class PriorityTier(IntEnum):
    CRITICAL = 0     # Tier 1: Critical processes
    NORMAL = 1       # Tier 2: Normal processes
    BACKGROUND = 2   # Tier 3: Background processes
 
# Policy: frame distribution among tiers
TIER_ALLOCATION = {
    PriorityTier.CRITICAL: 0.40,    # 40% of frames
    PriorityTier.NORMAL: 0.50,      # 50% of frames
    PriorityTier.BACKGROUND: 0.10,  # 10% of frames
}
 
@dataclass
class Process:
    pid: int
    name: str
    size: int
    tier: PriorityTier
    min_guarantee: int = 0    # Absolute minimum frames
    allocation: int = 0
 
def tiered_proportional_allocation(
    processes: List[Process],
    total_frames: int
) -> List[Process]:
    """
    Two-level allocation:
    1. Divide frames among priority tiers
    2. Proportionally allocate within each tier
    """
    
    # Group processes by tier
    tiers = {t: [] for t in PriorityTier}
    for p in processes:
        tiers[p.tier].append(p)
    
    # Calculate frames per tier
    tier_frames = {}
    for tier, fraction in TIER_ALLOCATION.items():
        tier_frames[tier] = int(total_frames * fraction)
    
    # Handle empty tiers: redistribute to non-empty tiers
    unused = 0
    for tier in PriorityTier:
        if not tiers[tier]:
            unused += tier_frames[tier]
            tier_frames[tier] = 0
    
    # Redistribute unused to highest non-empty tier
    for tier in PriorityTier:
        if tiers[tier]:
            tier_frames[tier] += unused
            break
    
    # Allocate proportionally within each tier
    for tier, procs in tiers.items():
        if not procs:
            continue
            
        available = tier_frames[tier]
        
        # First pass: satisfy minimum guarantees
        guaranteed_total = 0
        for p in procs:
            guaranteed_total += p.min_guarantee
        
        if guaranteed_total > available:
            # Cannot satisfy guarantees - critical error for high tiers
            print(f"WARNING: Cannot satisfy guarantees for tier {tier.name}")
            # Pro-rate guarantees
            for p in procs:
                p.allocation = int(p.min_guarantee * available / guaranteed_total)
            continue
        
        # Assign guarantees
        for p in procs:
            p.allocation = p.min_guarantee
        
        # Second pass: proportional distribution of remainder
        remainder = available - guaranteed_total
        total_unfulfilled = sum(max(0, p.size - p.allocation) for p in procs)
        
        if total_unfulfilled > 0 and remainder > 0:
            for p in procs:
                unfulfilled = max(0, p.size - p.allocation)
                if unfulfilled > 0:
                    share = unfulfilled / total_unfulfilled
                    bonus = int(remainder * share)
                    p.allocation += bonus
    
    return processes
 
def demonstrate_tiered_allocation():
    processes = [
        # Critical tier
        Process(1, "Database", 400, PriorityTier.CRITICAL, 100),
        Process(2, "API Server", 200, PriorityTier.CRITICAL, 50),
        
        # Normal tier  
        Process(3, "Web Frontend", 150, PriorityTier.NORMAL, 30),
        Process(4, "Worker", 100, PriorityTier.NORMAL, 20),
        Process(5, "Cache", 80, PriorityTier.NORMAL, 20),
        
        # Background tier
        Process(6, "Backup", 200, PriorityTier.BACKGROUND, 10),
        Process(7, "Logger", 50, PriorityTier.BACKGROUND, 5),
    ]
    
    result = tiered_proportional_allocation(processes, 500)
    
    print("\n=== Tiered Proportional Allocation ===")
    print(f"Total frames: 500\n")
    
    current_tier = None
    for p in sorted(result, key=lambda x: (x.tier, -x.allocation)):
        if p.tier != current_tier:
            current_tier = p.tier
            print(f"\n{current_tier.name} TIER:")
        pct = p.allocation / 500 * 100
        print(f"  {p.name:15s}: size={p.size:3d}, "
              f"min={p.min_guarantee:3d}, "
              f"alloc={p.allocation:3d} ({pct:4.1f}%)")
 
if __name__ == "__main__":
    demonstrate_tiered_allocation()

Advantages and Challenges

Priority-based allocation introduces explicit organizational control over memory distribution. This power comes with both significant benefits and notable challenges.

Advantages

•Service Differentiation — Critical workloads can be protected from resource competition with less important work
•Predictable Critical Performance — High-priority processes experience consistent memory availability
•Policy Enforcement — Organizational priorities translate directly into resource allocation
•Graceful Degradation — Under pressure, low-priority work suffers first, preserving critical function
•Multi-tenant Fairness — Premium customers can receive better resource treatment
•Real-time Support — Critical deadlines can be met by prioritizing memory allocation

Challenges

•Priority Assignment Complexity — Determining correct priorities requires deep system understanding
•Priority Inflation — Everyone wants 'critical' priority; discipline erodes over time
•Starvation Risk — Low-priority processes may never receive adequate allocation
•Priority Inversion — Indirect dependencies can violate priority intent
•Static vs. Dynamic Mismatch — Static priorities may not match dynamic importance
•Management Overhead — Priority schemes require ongoing administrative attention

The Priority Inflation Trap

Starvation Prevention

Prevention Mechanisms:

Minimum Floors — Even lowest priority gets some allocation (e.g., architectural minimum + 10%)
Aging — Low-priority processes that haven't run gain priority over time
Burst Periods — Periodic intervals where low-priority receives temporary boost
Work Conservation — If high-priority doesn't need frames, they go to low-priority
Progress Requirements — Processes must make forward progress; if starved, force temporary priority boost

Real-World Implementations

Priority-based memory allocation manifests in various forms across modern operating systems and orchestration platforms.

Linux: OOM Killer Scoring

oom_score_configuration.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
# Linux OOM score adjustment for priority-based protection
 
# Protect critical processes from OOM killer
# oom_score_adj: -1000 = never kill, +1000 = always kill first
 
# Critical: protect from OOM
echo "-1000" > /proc/$(pidof systemd)/oom_score_adj
echo "-900"  > /proc/$(pidof sshd)/oom_score_adj
echo "-500"  > /proc/$(pidof postgresql)/oom_score_adj
 
# Normal: default behavior
echo "0" > /proc/$(pidof nginx)/oom_score_adj
 
# Deprioritize: kill these first if needed
echo "500"  > /proc/$(pidof logrotate)/oom_score_adj
echo "750"  > /proc/$(pidof updatedb)/oom_score_adj
echo "1000" > /proc/$(pidof stress-test)/oom_score_adj
 
# View current OOM scores
echo "Process OOM Scores:"
for pid in $(pgrep -x "systemd|sshd|postgresql|nginx"); do
    name=$(cat /proc/$pid/comm 2>/dev/null)
    score=$(cat /proc/$pid/oom_score 2>/dev/null)
    adj=$(cat /proc/$pid/oom_score_adj 2>/dev/null)
    echo "  $name (PID $pid): score=$score, adj=$adj"
done

Linux: cgroups memory.high and memory.max

While not strictly priority-based, cgroups allow hierarchical resource control that achieves similar effects:

Process groups in different cgroups receive different memory limits
Under pressure, groups are throttled based on their configuration
Combined with process priorities, creates priority-tiered allocation

Windows: Memory Priority

Windows explicitly supports memory priority (0-7) for processes:

Priority affects page-out order during working set trimming
Higher memory priority = pages retained longer
Integrates with process priority but is separately configurable

WindowsMemoryPriority.ps1
PowerShell
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
# Windows Memory Priority Configuration
 
# Memory priority levels (0-7, higher = more important)
# 0: Very low - pages evicted first
# 3: Normal (default)
# 5: High
# 7: Critical - pages evicted last
 
# Set memory priority for a process
function Set-ProcessMemoryPriority {
    param(
        [Parameter(Mandatory=$true)]
        [int]$ProcessId,
        [Parameter(Mandatory=$true)]
        [ValidateRange(0,7)]
        [int]$Priority
    )
    
    $process = Get-Process -Id $ProcessId -ErrorAction Stop
    
    # Use Windows API via P/Invoke
    Add-Type -TypeDefinition @"
        using System;
        using System.Runtime.InteropServices;
        
        public class MemoryPriority {
            [DllImport("kernel32.dll", SetLastError = true)]
            public static extern bool SetProcessInformation(
                IntPtr hProcess,
                int ProcessInformationClass,
                ref int ProcessInformation,
                int ProcessInformationSize);
                
            public const int ProcessMemoryPriority = 0;
        }
"@
    
    $priorityValue = $Priority
    $result = [MemoryPriority]::SetProcessInformation(
        $process.Handle,
        0,  # ProcessMemoryPriority
        [ref]$priorityValue,
        4   # sizeof(int)
    )
    
    if ($result) {
        Write-Host "Set memory priority for $($process.Name) to $Priority"
    } else {
        Write-Error "Failed to set memory priority"
    }
}
 
# Example: Protect critical processes
$criticalProcesses = @("sqlservr", "w3wp", "lsass")
foreach ($procName in $criticalProcesses) {
    $procs = Get-Process -Name $procName -ErrorAction SilentlyContinue
    foreach ($proc in $procs) {
        Set-ProcessMemoryPriority -ProcessId $proc.Id -Priority 7
    }
}
 
# Deprioritize background processes
$backgroundProcesses = @("SearchIndexer", "TiWorker", "MsMpEng")
foreach ($procName in $backgroundProcesses) {
    $procs = Get-Process -Name $procName -ErrorAction SilentlyContinue
    foreach ($proc in $procs) {
        Set-ProcessMemoryPriority -ProcessId $proc.Id -Priority 1
    }
}

Cloud and Container Orchestration

Modern orchestration systems implement priority-based allocation at higher abstraction levels:

These systems don't control individual frames but achieve similar effects through container-level memory limits and eviction policies.

Summary and Key Takeaways

Core Concepts Mastered

•Priority Fundamentals — Priority can derive from process type, administrator configuration, resource class membership, or dynamic behavior. Different sources have different stability and appropriate use cases.
•Priority Models — Priority classes (discrete tiers), priority weights (continuous multipliers), and priority ordering (reclamation sequence) each offer different expressiveness and complexity tradeoffs.
•Priority-Weighted Allocation — Extending proportional allocation with priority weights: aᵢ = (pᵢ × sᵢ) / Σ(pⱼ × sⱼ) × m. Priority acts as a multiplier on size.
•Priority Class Systems — Discrete classes with different allocation rules provide clear policy boundaries: guaranteed minimums, reclamation ordering, and proportional pools within classes.
•Priority Inversion — Indirect dependencies can violate priority intent. Priority donation temporarily elevates blockers of high-priority waiters. Practical systems often use simpler mechanisms like minimum floors.
•Integration Patterns — Priority rarely operates alone; it combines with proportional allocation through weighted-proportional, tiered, or guarantee-plus-proportional patterns.
•Practical Challenges — Priority inflation, starvation risk, and management overhead require ongoing attention. Mitigation mechanisms include quotas, aging, and minimum floors.

Looking Ahead

Page Complete