Operating SystemsCPU Scheduling

Priority Scheduling

LevelIntermediate

Duration90 mins

TopicCPU Scheduling

4 / 5

The Aging Solution

Aging: Preventing Starvation Through Time

Aging is the primary mechanism for preventing starvation in priority scheduling systems. The concept is elegantly simple: as a process waits in the ready queue, its priority gradually increases. Eventually, even the lowest-priority process will have waited long enough to become the highest priority—guaranteeing execution.

Aging transforms priority scheduling from a potentially unfair system into one with bounded waiting time guarantees. It preserves the benefits of prioritization while preventing its pathological failure mode.

Learning Objectives

Understand the mechanics of priority aging, implement aging algorithms, analyze aging parameters' effects on system behavior, and recognize aging mechanisms in real operating systems.

How Aging Works

Aging modifies the effective priority of a process based on its waiting time:

effective_priority(P) = base_priority(P) + aging_factor(wait_time(P))

The aging factor increases with waiting time, eventually dominating the base priority. Key parameters include:

Aging Rate

How quickly priority increases with waiting time. Faster aging prevents starvation more quickly but diminishes priority differentiation.

Aging Interval

How frequently the system updates priorities. Per-tick updates provide smoothness; periodic batch updates reduce overhead.

Priority Ceiling

Maximum effective priority after aging. May be unlimited (aging continues until selected) or capped (preserving some priority stratification).

Priority Reset

Whether priority resets to base after execution. Most systems reset, preventing permanent elevation.

Converting Mermaid diagram...

Aging Implementation

aging_scheduler.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
"""
Priority Scheduling with Aging Implementation
Demonstrates starvation prevention through progressive priority increase.
"""
from dataclasses import dataclass, field
from typing import List, Optional
import heapq
 
@dataclass
class Process:
    pid: str
    arrival: int
    burst: int
    base_priority: int
    remaining: int = field(init=False)
    current_priority: int = field(init=False)
    wait_time: int = 0
    history: List[str] = field(default_factory=list)
    
    def __post_init__(self):
        self.remaining = self.burst
        self.current_priority = self.base_priority
 
class AgingScheduler:
    def __init__(self, aging_rate: int = 1, aging_interval: int = 5, 
                 max_priority: int = 100):
        """
        aging_rate: Priority increase per aging interval
        aging_interval: Time units between priority updates
        max_priority: Ceiling for aged priority
        """
        self.aging_rate = aging_rate
        self.aging_interval = aging_interval
        self.max_priority = max_priority
        self.time = 0
        self.ready_queue: List[Process] = []
        self.completed: List[Process] = []
        
    def apply_aging(self):
        """Increase priority of all waiting processes."""
        for p in self.ready_queue:
            if p.current_priority < self.max_priority:
                old_pri = p.current_priority
                p.current_priority = min(
                    p.current_priority + self.aging_rate,
                    self.max_priority
                )
                if old_pri != p.current_priority:
                    p.history.append(
                        f"t={self.time}: Aged {old_pri} -> {p.current_priority}"
                    )
    
    def run(self, processes: List[Process]) -> List[Process]:
        waiting = sorted(processes, key=lambda p: p.arrival)
        current: Optional[Process] = None
        
        while waiting or self.ready_queue or current:
            # Arrivals
            while waiting and waiting[0].arrival <= self.time:
                p = waiting.pop(0)
                p.history.append(f"t={self.time}: Arrived")
                self.ready_queue.append(p)
            
            # Apply aging periodically
            if self.time > 0 and self.time % self.aging_interval == 0:
                self.apply_aging()
            
            # Select highest priority (preemptive)
            if self.ready_queue:
                self.ready_queue.sort(
                    key=lambda p: -p.current_priority  # Highest first
                )
                
                if current and self.ready_queue[0].current_priority > current.current_priority:
                    # Preempt
                    self.ready_queue.append(current)
                    current = self.ready_queue.pop(0)
                    current.history.append(f"t={self.time}: Preempted in")
                elif not current:
                    current = self.ready_queue.pop(0)
                    current.history.append(f"t={self.time}: Scheduled")
            
            if not current:
                self.time += 1
                continue
            
            # Execute one time unit
            current.remaining -= 1
            
            # Update wait times for ready queue
            for p in self.ready_queue:
                p.wait_time += 1
            
            self.time += 1
            
            if current.remaining == 0:
                current.history.append(f"t={self.time}: Completed")
                current.current_priority = current.base_priority  # Reset
                self.completed.append(current)
                current = None
        
        return self.completed
 
# Demonstration: Without aging, P_low would starve
processes = [
    Process("P_low", arrival=0, burst=5, base_priority=1),
    Process("P_high1", arrival=1, burst=3, base_priority=10),
    Process("P_high2", arrival=4, burst=3, base_priority=10),
    Process("P_high3", arrival=7, burst=3, base_priority=10),
]
 
scheduler = AgingScheduler(aging_rate=2, aging_interval=3, max_priority=15)
result = scheduler.run(processes)
 
print("Priority Scheduling with Aging:")
print("=" * 60)
for p in result:
    print(f"\n{p.pid} (base priority={p.base_priority}):")
    print(f"  Wait time: {p.wait_time}")
    for event in p.history:
        print(f"  {event}")

Aging Rate Tradeoffs

Fast aging (high rate, short interval) quickly elevates starving processes but dilutes priority differentiation. Slow aging maintains priority importance but may allow longer starvation periods. The optimal rate depends on workload characteristics and fairness requirements.

Mathematical Analysis

Bounded Waiting Time Guarantee

With aging, we can prove bounded waiting time. Consider:

P_low: base priority = 1
P_high: base priority = 10
Aging rate: +1 per interval
Aging interval: 5 time units

After waiting time t, P_low's effective priority becomes:

effective_priority(P_low, t) = 1 + floor(t / 5)

P_low will match P_high's priority when:

1 + floor(t / 5) ≥ 10
floor(t / 5) ≥ 9
t ≥ 45 time units

Thus, maximum wait time = 45 units regardless of high-priority arrivals.

General Formula

For aging with linear increase:

aging_analysis.txt

Mathematical Analysis

Maximum Wait Time Calculation
═══════════════════════════════════════════════════════════════════════
 
Given:
  • P_base:    Base priority of lowest-priority process
  • P_max:     Maximum priority in system (or ceiling)
  • R:         Aging rate (priority increase per interval)
  • I:         Aging interval (time units)
 
Maximum wait time until P_base reaches P_max:
 
    max_wait = ceiling((P_max - P_base) / R) × I
 
Example:
  P_base = 1, P_max = 100, R = 2, I = 10
  
  max_wait = ceiling((100 - 1) / 2) × 10
           = ceiling(49.5) × 10
           = 50 × 10
           = 500 time units
 
This is the WORST-CASE bound. Actual wait times are typically much lower
since high-priority processes complete, creating scheduling opportunities.

Aging in Real Operating Systems

Aging Mechanisms in Modern Operating Systems
System	Mechanism	Aging Behavior	Notes
Linux CFS	Virtual runtime	Lower vruntime = higher scheduling priority; processes accumulate vruntime slower when waiting	Not classic aging but achieves similar fairness
Windows	Priority decay/boost	Priority decays after running, implicitly boosting relative priority of waiters	Combined with I/O and foreground boosts
FreeBSD ULE	Interactivity score	Sleeping processes gain interactivity points, raising priority	Rewards I/O-bound behavior
Solaris	Dispatch tables	Priority adjusted based on time slice usage; CPU hogs demoted	Inverse aging—penalize CPU use rather than reward waiting
VxWorks	Optional aging	Configurable aging for time-sharing tasks	Disabled by default for real-time determinism

linux_cfs_aging.c
C (Linux Kernel Concepts)
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
/*
 * Linux CFS "Aging" Mechanism (Conceptual)
 * 
 * CFS doesn't use traditional aging. Instead, it tracks "virtual runtime"
 * (vruntime) - how much CPU time a process has received, weighted by nice.
 * 
 * Processes with LOWER vruntime are scheduled first.
 * A waiting process's vruntime doesn't increase, so it naturally becomes
 * the "most deserving" as running processes accumulate vruntime.
 */
 
struct sched_entity {
    u64 vruntime;           /* Virtual runtime consumed */
    u64 exec_start;         /* When current execution started */
    struct load_weight load; /* Weight based on nice value */
};
 
/* When a process runs, its vruntime increases */
static void update_curr(struct cfs_rq *cfs_rq) {
    struct sched_entity *curr = cfs_rq->curr;
    u64 now = rq_clock_task(rq_of(cfs_rq));
    u64 delta_exec = now - curr->exec_start;
    
    /* Weighted delta: high-nice processes accumulate vruntime faster */
    u64 delta_weighted = calc_delta_fair(delta_exec, curr);
    
    curr->vruntime += delta_weighted;
    curr->exec_start = now;
    
    /* Update min_vruntime for new arrivals */
    update_min_vruntime(cfs_rq);
}
 
/* Implicit aging: waiting process's vruntime stays constant
 * while running processes' vruntime increases.
 * Result: waiters become highest priority (lowest vruntime) over time.
 */
 
/* When a sleeping process wakes up, its vruntime is adjusted */
static void place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se) {
    u64 vruntime = cfs_rq->min_vruntime;
    
    /* Small penalty to prevent sleep/wake gaming */
    if (initial_task_util)
        vruntime -= sysctl_sched_latency;
    
    se->vruntime = max(se->vruntime, vruntime);
}

Tuning Aging Parameters

Selecting appropriate aging parameters requires balancing competing concerns:

Aging Parameter Effects
Parameter	High Value Effect	Low Value Effect	Guidance
Aging Rate	Quick starvation prevention, less priority differentiation	Strong priorities, longer possible starvation	Match to SLA requirements
Aging Interval	Coarse updates, lower overhead, step-like behavior	Smooth priority growth, higher overhead	Balance overhead vs smoothness
Priority Ceiling	Aged processes can fully override base priorities	Maintains stratification even for starving processes	Consider real-time vs batch trade-offs
Reset Policy	Full reset prevents priority inflation; harsh to long jobs	Partial reset smooths behavior for long-running processes	Full reset is most common

Workload-Dependent Tuning

There is no universal 'correct' aging configuration. Interactive workloads favor aggressive aging for responsiveness. Batch workloads may tolerate slower aging. Real-time systems may disable aging entirely to preserve priority guarantees. Profile your workload and measure fairness metrics.

Alternatives to Aging

Other Starvation Prevention Approaches

•Fair-share scheduling — Guarantee each user/group/priority-class a minimum CPU share regardless of other load. Linux cgroups provide this.
•Lottery scheduling — Probabilistic selection where each process holds 'tickets'. Low-priority processes have fewer tickets but non-zero probability of selection.
•Stride scheduling — Deterministic proportional-share scheduling. Each process advances by inverse of its share; lowest stride value runs next.
•Deadline-based scheduling — Replace priority with deadlines. EDF (Earliest Deadline First) guarantees execution if feasible.
•Time slice reservation — Reserve portion of each time window for low-priority execution, regardless of high-priority demand.

Summary

Key Takeaways

•Aging increases priority over waiting time, guaranteeing eventual execution for all processes.
•Key parameters are aging rate, interval, ceiling, and reset policy—each affects fairness and responsiveness.
•Bounded waiting is provable — maximum wait time is calculable from aging parameters.
•Modern systems use aging variants — Linux CFS uses virtual runtime; Windows uses priority decay/boost.
•Parameter tuning is workload-dependent — no universal configuration exists.
•Alternatives exist — fair-share, lottery, stride, and deadline scheduling also prevent starvation.

Next: Multiple Priority Levels

The final page examines multi-level priority queues—organizing processes into priority bands with different scheduling policies per level, combining the benefits of priority and other scheduling approaches.

4 / 5

Loading learning content...

Operating SystemsCPU Scheduling

Priority Scheduling

LevelIntermediate

Duration90 mins

TopicCPU Scheduling

4 / 5

The Aging Solution

Aging: Preventing Starvation Through Time

Learning Objectives

Understand the mechanics of priority aging, implement aging algorithms, analyze aging parameters' effects on system behavior, and recognize aging mechanisms in real operating systems.

How Aging Works

Aging modifies the effective priority of a process based on its waiting time:

effective_priority(P) = base_priority(P) + aging_factor(wait_time(P))

The aging factor increases with waiting time, eventually dominating the base priority. Key parameters include:

Aging Rate

How quickly priority increases with waiting time. Faster aging prevents starvation more quickly but diminishes priority differentiation.

Aging Interval

How frequently the system updates priorities. Per-tick updates provide smoothness; periodic batch updates reduce overhead.

Priority Ceiling

Maximum effective priority after aging. May be unlimited (aging continues until selected) or capped (preserving some priority stratification).

Priority Reset

Whether priority resets to base after execution. Most systems reset, preventing permanent elevation.

Converting Mermaid diagram...

Aging Implementation

aging_scheduler.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
"""
Priority Scheduling with Aging Implementation
Demonstrates starvation prevention through progressive priority increase.
"""
from dataclasses import dataclass, field
from typing import List, Optional
import heapq
 
@dataclass
class Process:
    pid: str
    arrival: int
    burst: int
    base_priority: int
    remaining: int = field(init=False)
    current_priority: int = field(init=False)
    wait_time: int = 0
    history: List[str] = field(default_factory=list)
    
    def __post_init__(self):
        self.remaining = self.burst
        self.current_priority = self.base_priority
 
class AgingScheduler:
    def __init__(self, aging_rate: int = 1, aging_interval: int = 5, 
                 max_priority: int = 100):
        """
        aging_rate: Priority increase per aging interval
        aging_interval: Time units between priority updates
        max_priority: Ceiling for aged priority
        """
        self.aging_rate = aging_rate
        self.aging_interval = aging_interval
        self.max_priority = max_priority
        self.time = 0
        self.ready_queue: List[Process] = []
        self.completed: List[Process] = []
        
    def apply_aging(self):
        """Increase priority of all waiting processes."""
        for p in self.ready_queue:
            if p.current_priority < self.max_priority:
                old_pri = p.current_priority
                p.current_priority = min(
                    p.current_priority + self.aging_rate,
                    self.max_priority
                )
                if old_pri != p.current_priority:
                    p.history.append(
                        f"t={self.time}: Aged {old_pri} -> {p.current_priority}"
                    )
    
    def run(self, processes: List[Process]) -> List[Process]:
        waiting = sorted(processes, key=lambda p: p.arrival)
        current: Optional[Process] = None
        
        while waiting or self.ready_queue or current:
            # Arrivals
            while waiting and waiting[0].arrival <= self.time:
                p = waiting.pop(0)
                p.history.append(f"t={self.time}: Arrived")
                self.ready_queue.append(p)
            
            # Apply aging periodically
            if self.time > 0 and self.time % self.aging_interval == 0:
                self.apply_aging()
            
            # Select highest priority (preemptive)
            if self.ready_queue:
                self.ready_queue.sort(
                    key=lambda p: -p.current_priority  # Highest first
                )
                
                if current and self.ready_queue[0].current_priority > current.current_priority:
                    # Preempt
                    self.ready_queue.append(current)
                    current = self.ready_queue.pop(0)
                    current.history.append(f"t={self.time}: Preempted in")
                elif not current:
                    current = self.ready_queue.pop(0)
                    current.history.append(f"t={self.time}: Scheduled")
            
            if not current:
                self.time += 1
                continue
            
            # Execute one time unit
            current.remaining -= 1
            
            # Update wait times for ready queue
            for p in self.ready_queue:
                p.wait_time += 1
            
            self.time += 1
            
            if current.remaining == 0:
                current.history.append(f"t={self.time}: Completed")
                current.current_priority = current.base_priority  # Reset
                self.completed.append(current)
                current = None
        
        return self.completed
 
# Demonstration: Without aging, P_low would starve
processes = [
    Process("P_low", arrival=0, burst=5, base_priority=1),
    Process("P_high1", arrival=1, burst=3, base_priority=10),
    Process("P_high2", arrival=4, burst=3, base_priority=10),
    Process("P_high3", arrival=7, burst=3, base_priority=10),
]
 
scheduler = AgingScheduler(aging_rate=2, aging_interval=3, max_priority=15)
result = scheduler.run(processes)
 
print("Priority Scheduling with Aging:")
print("=" * 60)
for p in result:
    print(f"\n{p.pid} (base priority={p.base_priority}):")
    print(f"  Wait time: {p.wait_time}")
    for event in p.history:
        print(f"  {event}")

Aging Rate Tradeoffs

Mathematical Analysis

Bounded Waiting Time Guarantee

With aging, we can prove bounded waiting time. Consider:

P_low: base priority = 1
P_high: base priority = 10
Aging rate: +1 per interval
Aging interval: 5 time units

After waiting time t, P_low's effective priority becomes:

effective_priority(P_low, t) = 1 + floor(t / 5)

P_low will match P_high's priority when:

1 + floor(t / 5) ≥ 10
floor(t / 5) ≥ 9
t ≥ 45 time units

Thus, maximum wait time = 45 units regardless of high-priority arrivals.

General Formula

For aging with linear increase:

aging_analysis.txt

Mathematical Analysis

Maximum Wait Time Calculation
═══════════════════════════════════════════════════════════════════════
 
Given:
  • P_base:    Base priority of lowest-priority process
  • P_max:     Maximum priority in system (or ceiling)
  • R:         Aging rate (priority increase per interval)
  • I:         Aging interval (time units)
 
Maximum wait time until P_base reaches P_max:
 
    max_wait = ceiling((P_max - P_base) / R) × I
 
Example:
  P_base = 1, P_max = 100, R = 2, I = 10
  
  max_wait = ceiling((100 - 1) / 2) × 10
           = ceiling(49.5) × 10
           = 50 × 10
           = 500 time units
 
This is the WORST-CASE bound. Actual wait times are typically much lower
since high-priority processes complete, creating scheduling opportunities.

Aging in Real Operating Systems

Aging Mechanisms in Modern Operating Systems
System	Mechanism	Aging Behavior	Notes
Linux CFS	Virtual runtime	Lower vruntime = higher scheduling priority; processes accumulate vruntime slower when waiting	Not classic aging but achieves similar fairness
Windows	Priority decay/boost	Priority decays after running, implicitly boosting relative priority of waiters	Combined with I/O and foreground boosts
FreeBSD ULE	Interactivity score	Sleeping processes gain interactivity points, raising priority	Rewards I/O-bound behavior
Solaris	Dispatch tables	Priority adjusted based on time slice usage; CPU hogs demoted	Inverse aging—penalize CPU use rather than reward waiting
VxWorks	Optional aging	Configurable aging for time-sharing tasks	Disabled by default for real-time determinism

linux_cfs_aging.c
C (Linux Kernel Concepts)
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
/*
 * Linux CFS "Aging" Mechanism (Conceptual)
 * 
 * CFS doesn't use traditional aging. Instead, it tracks "virtual runtime"
 * (vruntime) - how much CPU time a process has received, weighted by nice.
 * 
 * Processes with LOWER vruntime are scheduled first.
 * A waiting process's vruntime doesn't increase, so it naturally becomes
 * the "most deserving" as running processes accumulate vruntime.
 */
 
struct sched_entity {
    u64 vruntime;           /* Virtual runtime consumed */
    u64 exec_start;         /* When current execution started */
    struct load_weight load; /* Weight based on nice value */
};
 
/* When a process runs, its vruntime increases */
static void update_curr(struct cfs_rq *cfs_rq) {
    struct sched_entity *curr = cfs_rq->curr;
    u64 now = rq_clock_task(rq_of(cfs_rq));
    u64 delta_exec = now - curr->exec_start;
    
    /* Weighted delta: high-nice processes accumulate vruntime faster */
    u64 delta_weighted = calc_delta_fair(delta_exec, curr);
    
    curr->vruntime += delta_weighted;
    curr->exec_start = now;
    
    /* Update min_vruntime for new arrivals */
    update_min_vruntime(cfs_rq);
}
 
/* Implicit aging: waiting process's vruntime stays constant
 * while running processes' vruntime increases.
 * Result: waiters become highest priority (lowest vruntime) over time.
 */
 
/* When a sleeping process wakes up, its vruntime is adjusted */
static void place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se) {
    u64 vruntime = cfs_rq->min_vruntime;
    
    /* Small penalty to prevent sleep/wake gaming */
    if (initial_task_util)
        vruntime -= sysctl_sched_latency;
    
    se->vruntime = max(se->vruntime, vruntime);
}

Tuning Aging Parameters

Selecting appropriate aging parameters requires balancing competing concerns:

Aging Parameter Effects
Parameter	High Value Effect	Low Value Effect	Guidance
Aging Rate	Quick starvation prevention, less priority differentiation	Strong priorities, longer possible starvation	Match to SLA requirements
Aging Interval	Coarse updates, lower overhead, step-like behavior	Smooth priority growth, higher overhead	Balance overhead vs smoothness
Priority Ceiling	Aged processes can fully override base priorities	Maintains stratification even for starving processes	Consider real-time vs batch trade-offs
Reset Policy	Full reset prevents priority inflation; harsh to long jobs	Partial reset smooths behavior for long-running processes	Full reset is most common

Workload-Dependent Tuning

Alternatives to Aging

Other Starvation Prevention Approaches

•Fair-share scheduling — Guarantee each user/group/priority-class a minimum CPU share regardless of other load. Linux cgroups provide this.
•Lottery scheduling — Probabilistic selection where each process holds 'tickets'. Low-priority processes have fewer tickets but non-zero probability of selection.
•Stride scheduling — Deterministic proportional-share scheduling. Each process advances by inverse of its share; lowest stride value runs next.
•Deadline-based scheduling — Replace priority with deadlines. EDF (Earliest Deadline First) guarantees execution if feasible.
•Time slice reservation — Reserve portion of each time window for low-priority execution, regardless of high-priority demand.

Summary

Key Takeaways

•Aging increases priority over waiting time, guaranteeing eventual execution for all processes.
•Key parameters are aging rate, interval, ceiling, and reset policy—each affects fairness and responsiveness.
•Bounded waiting is provable — maximum wait time is calculable from aging parameters.
•Modern systems use aging variants — Linux CFS uses virtual runtime; Windows uses priority decay/boost.
•Parameter tuning is workload-dependent — no universal configuration exists.
•Alternatives exist — fair-share, lottery, stride, and deadline scheduling also prevent starvation.

Next: Multiple Priority Levels

4 / 5