Operating SystemsCPU Scheduling

Priority Scheduling

LevelIntermediate

Duration90 mins

TopicCPU Scheduling

3 / 5

The Starvation Problem

When Processes Wait Forever

In priority scheduling systems, a fundamental fairness problem emerges: starvation. A process starves when it remains indefinitely in the ready queue, perpetually denied CPU access because higher-priority processes continuously arrive. Unlike deadlock—where processes wait for each other—starvation involves waiting for a resource (CPU time) that is continuously given to others.

Starvation represents a failure of the scheduling system to provide basic fairness guarantees. While prioritization is necessary for system functionality, unchecked priority differences create pathological conditions where legitimate work never completes.

Learning Objectives

Understand the causes and manifestations of starvation, distinguish starvation from related problems like deadlock and livelock, analyze systems for starvation vulnerability, and prepare for the aging solution covered in the next page.

Defining Starvation

Starvation (also called indefinite blocking or indefinite postponement) occurs when a process is perpetually denied necessary resources to proceed. In CPU scheduling:

A process suffers starvation when it waits indefinitely in the ready queue while the scheduler continuously selects other processes for execution.

Formal Definition

A scheduling algorithm exhibits starvation if there exists a process P such that:

lim(t→∞) [waiting_time(P, t)] = ∞

while P remains runnable (not blocked, not terminated).

Distinguishing Starvation from Related Problems

Starvation vs Related Concurrency Problems
Problem	Definition	Detection	Resolution
Starvation	Process waits indefinitely for resource given to others	Waiting time analysis, priority monitoring	Aging, fair scheduling, priority ceiling
Deadlock	Circular wait where processes block each other	Wait-for graph cycle detection	Prevention, avoidance, detection+recovery
Livelock	Processes actively change state but make no progress	Progress monitoring, state repetition	Randomization, backoff strategies
Priority Inversion	High-priority waits for low-priority holding resource	Lock ownership analysis	Priority inheritance, priority ceiling

Starvation is Not Deadlock

In starvation, the system makes progress—other processes run and complete. Only specific processes are denied resources. In deadlock, no involved process can proceed. Starvation is a fairness failure; deadlock is a progress failure.

Causes of Starvation

Starvation arises from the interaction between scheduling policy and workload characteristics. Understanding these causes is essential for prevention:

Primary Causes of CPU Starvation

•Continuous high-priority arrivals — When higher-priority processes arrive faster than they complete, lower-priority processes never reach the front of the queue.
•Static priority without bounds — Fixed priorities with no mechanism to elevate starving processes guarantee eventual starvation under sustained load.
•Priority preemption without limits — Preemptive scheduling that always favors high priority, combined with sustained high-priority load, starves lower priorities.
•Resource-based priority boosts — Processes holding resources may receive boosts, creating feedforward loops that exclude others.
•Unfair tie-breaking — When equal-priority processes use LIFO instead of FIFO ordering, early arrivals may starve.

starvation_demo.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
"""
Demonstration of starvation in priority scheduling.
Low-priority process never runs due to continuous high-priority arrivals.
"""
import random
 
class Scheduler:
    def __init__(self):
        self.time = 0
        self.ready_queue = []  # (priority, arrival, name, remaining)
        self.waiting_times = {}
        
    def arrive(self, name, priority, burst):
        self.ready_queue.append((priority, self.time, name, burst))
        if name not in self.waiting_times:
            self.waiting_times[name] = 0
            
    def tick(self):
        if not self.ready_queue:
            self.time += 1
            return None
            
        # Sort by priority (highest first), then arrival
        self.ready_queue.sort(key=lambda x: (-x[0], x[1]))
        
        # Run highest priority for 1 unit
        pri, arr, name, remaining = self.ready_queue.pop(0)
        
        # Update waiting times for all OTHER processes
        for i, (p, a, n, r) in enumerate(self.ready_queue):
            self.waiting_times[n] = self.waiting_times.get(n, 0) + 1
            
        self.time += 1
        
        if remaining > 1:
            self.ready_queue.append((pri, arr, name, remaining - 1))
            
        return name
 
# Simulate: low-priority process vs continuous high-priority arrivals
sched = Scheduler()
 
# Low priority process arrives at t=0
sched.arrive("LowPriority", priority=1, burst=5)
 
# High priority processes arrive every 2 time units
for t in range(100):
    running = sched.tick()
    
    # New high-priority arrival every 2 ticks
    if t % 2 == 0 and t > 0:
        sched.arrive(f"High_{t}", priority=10, burst=2)
    
    if t % 20 == 0:
        print(f"t={t}: Running={running}, "
              f"LowPriority wait={sched.waiting_times.get('LowPriority', 0)}")
 
print(f"\nFinal: LowPriority waiting time = {sched.waiting_times.get('LowPriority', 0)}")
print("LowPriority is STARVING - it may never complete!")

Real-World Manifestations

Starvation manifests in various scenarios across modern computing environments:

Starvation in Real Systems
Scenario	Victim	Cause	Symptom
Busy web server	Background log rotation	Continuous request handling at higher priority	Logs grow unbounded, disk fills
Desktop system	System updates	User interactive apps always prioritized	Security patches never install
Database server	Index maintenance	Query processing prioritized over maintenance	Query performance degrades over time
Real-time system	Diagnostic tasks	Control loops consume all high-priority slots	System health unknown
Cloud scheduler	Low-bid batch jobs	Premium customers always served first	Batch jobs exceed SLA

The Mars Pathfinder Incident

The 1997 Mars Pathfinder mission experienced repeated system resets due to priority inversion—a related problem where a high-priority task waited for a low-priority task holding a mutex. While not pure starvation, it illustrates how priority-based scheduling failures can have severe real-world consequences.

Detecting Starvation

Unlike deadlock, starvation has no definitive detection algorithm—a process waiting a long time might run eventually. Detection relies on heuristics and monitoring:

Starvation Detection Strategies

•Waiting time thresholds — Alert when any process exceeds maximum expected wait time. Threshold must account for legitimate delays.
•Progress monitoring — Track CPU time granted to each process over intervals. Zero progress over extended periods indicates starvation.
•Priority distribution analysis — Monitor ready queue composition. Persistent presence of low-priority processes signals potential starvation.
•Scheduling decision logging — Record scheduler choices. Repeated skipping of specific processes reveals patterns.
•Statistical analysis — Compare expected vs actual wait times based on priority and load. Significant deviation indicates unfairness.

starvation_monitor.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
/* Simple starvation detection monitor */
#include <stdio.h>
#include <time.h>
 
#define MAX_PROCESSES 100
#define STARVATION_THRESHOLD_MS 30000  /* 30 seconds */
 
typedef struct {
    int pid;
    int priority;
    time_t last_scheduled;
    unsigned long wait_time_ms;
    int is_runnable;
} ProcessInfo;
 
ProcessInfo processes[MAX_PROCESSES];
int process_count = 0;
 
void check_starvation(void) {
    time_t now = time(NULL);
    
    for (int i = 0; i < process_count; i++) {
        if (!processes[i].is_runnable) continue;
        
        unsigned long wait = (now - processes[i].last_scheduled) * 1000;
        
        if (wait > STARVATION_THRESHOLD_MS) {
            printf("WARNING: PID %d (priority %d) potential starvation!\n"
                   "  Wait time: %lu ms (threshold: %d ms)\n",
                   processes[i].pid,
                   processes[i].priority,
                   wait,
                   STARVATION_THRESHOLD_MS);
            
            /* Could trigger: priority boost, alert, or logging */
        }
    }
}
 
void on_process_scheduled(int pid) {
    for (int i = 0; i < process_count; i++) {
        if (processes[i].pid == pid) {
            processes[i].last_scheduled = time(NULL);
            break;
        }
    }
}

Impact of Starvation

Starvation's effects extend beyond the starving process itself, creating cascading failures:

Cascading Effects of Starvation

•Resource accumulation — Starving processes hold memory, file handles, and locks while waiting, depleting system resources.
•Dependent task failures — Processes waiting for starving process's output also stall, propagating delays.
•Queue buildup — Work queued for starving services accumulates, potentially exhausting queue capacity.
•SLA violations — Background tasks with deadlines (backups, reports) miss delivery windows.
•System degradation — Deferred maintenance (garbage collection, log rotation) causes gradual performance decline.
•Unpredictable failures — Tasks that 'always worked before' suddenly fail when starvation threshold reached.

The Hidden Cost

Starvation often goes unnoticed until catastrophic failure. A batch job that 'can wait' accumulates for days until disk fills. A maintenance task deferred 'just this once' compounds until database corruption. Design systems assuming starvation WILL occur without explicit prevention.

Prevention Principles

Before examining specific solutions (aging, in the next page), consider the general principles for starvation prevention:

Starvation Prevention Principles

•Bounded waiting — Guarantee maximum wait time for any priority level. No process waits indefinitely.
•Progress guarantee — Ensure every runnable process makes progress within bounded time.
•Dynamic priority adjustment — Increase priority of waiting processes over time (aging).
•Reserved capacity — Allocate minimum CPU share to each priority class regardless of higher-priority load.
•Priority ceiling — Limit maximum effective priority to allow lower-priority execution windows.
•Fair share scheduling — Guarantee resource share based on policy, not just priority competition.

The most widely implemented solution is aging—gradually increasing the priority of waiting processes. The next page explores aging mechanisms in detail.

Summary

Key Takeaways

•Starvation is indefinite blocking where a process never receives CPU time despite being runnable.
•Starvation differs from deadlock — the system progresses, but specific processes are excluded.
•Primary cause is continuous high-priority arrivals overwhelming low-priority capacity.
•Detection relies on monitoring waiting times, progress, and scheduling patterns.
•Impact cascades — resource accumulation, dependent failures, and deferred maintenance compound.
•Prevention requires explicit mechanisms — aging, reserved capacity, or fair-share policies.

Next: The Aging Solution

The next page examines aging—the primary mechanism for preventing starvation by gradually elevating waiting process priorities, ensuring bounded waiting times.

3 / 5

Loading learning content...

Operating SystemsCPU Scheduling

Priority Scheduling

LevelIntermediate

Duration90 mins

TopicCPU Scheduling

3 / 5

The Starvation Problem

When Processes Wait Forever

Learning Objectives

Defining Starvation

Starvation (also called indefinite blocking or indefinite postponement) occurs when a process is perpetually denied necessary resources to proceed. In CPU scheduling:

A process suffers starvation when it waits indefinitely in the ready queue while the scheduler continuously selects other processes for execution.

Formal Definition

A scheduling algorithm exhibits starvation if there exists a process P such that:

lim(t→∞) [waiting_time(P, t)] = ∞

while P remains runnable (not blocked, not terminated).

Distinguishing Starvation from Related Problems

Starvation vs Related Concurrency Problems
Problem	Definition	Detection	Resolution
Starvation	Process waits indefinitely for resource given to others	Waiting time analysis, priority monitoring	Aging, fair scheduling, priority ceiling
Deadlock	Circular wait where processes block each other	Wait-for graph cycle detection	Prevention, avoidance, detection+recovery
Livelock	Processes actively change state but make no progress	Progress monitoring, state repetition	Randomization, backoff strategies
Priority Inversion	High-priority waits for low-priority holding resource	Lock ownership analysis	Priority inheritance, priority ceiling

Starvation is Not Deadlock

Causes of Starvation

Starvation arises from the interaction between scheduling policy and workload characteristics. Understanding these causes is essential for prevention:

Primary Causes of CPU Starvation

•Continuous high-priority arrivals — When higher-priority processes arrive faster than they complete, lower-priority processes never reach the front of the queue.
•Static priority without bounds — Fixed priorities with no mechanism to elevate starving processes guarantee eventual starvation under sustained load.
•Priority preemption without limits — Preemptive scheduling that always favors high priority, combined with sustained high-priority load, starves lower priorities.
•Resource-based priority boosts — Processes holding resources may receive boosts, creating feedforward loops that exclude others.
•Unfair tie-breaking — When equal-priority processes use LIFO instead of FIFO ordering, early arrivals may starve.

starvation_demo.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
"""
Demonstration of starvation in priority scheduling.
Low-priority process never runs due to continuous high-priority arrivals.
"""
import random
 
class Scheduler:
    def __init__(self):
        self.time = 0
        self.ready_queue = []  # (priority, arrival, name, remaining)
        self.waiting_times = {}
        
    def arrive(self, name, priority, burst):
        self.ready_queue.append((priority, self.time, name, burst))
        if name not in self.waiting_times:
            self.waiting_times[name] = 0
            
    def tick(self):
        if not self.ready_queue:
            self.time += 1
            return None
            
        # Sort by priority (highest first), then arrival
        self.ready_queue.sort(key=lambda x: (-x[0], x[1]))
        
        # Run highest priority for 1 unit
        pri, arr, name, remaining = self.ready_queue.pop(0)
        
        # Update waiting times for all OTHER processes
        for i, (p, a, n, r) in enumerate(self.ready_queue):
            self.waiting_times[n] = self.waiting_times.get(n, 0) + 1
            
        self.time += 1
        
        if remaining > 1:
            self.ready_queue.append((pri, arr, name, remaining - 1))
            
        return name
 
# Simulate: low-priority process vs continuous high-priority arrivals
sched = Scheduler()
 
# Low priority process arrives at t=0
sched.arrive("LowPriority", priority=1, burst=5)
 
# High priority processes arrive every 2 time units
for t in range(100):
    running = sched.tick()
    
    # New high-priority arrival every 2 ticks
    if t % 2 == 0 and t > 0:
        sched.arrive(f"High_{t}", priority=10, burst=2)
    
    if t % 20 == 0:
        print(f"t={t}: Running={running}, "
              f"LowPriority wait={sched.waiting_times.get('LowPriority', 0)}")
 
print(f"\nFinal: LowPriority waiting time = {sched.waiting_times.get('LowPriority', 0)}")
print("LowPriority is STARVING - it may never complete!")

Real-World Manifestations

Starvation manifests in various scenarios across modern computing environments:

Starvation in Real Systems
Scenario	Victim	Cause	Symptom
Busy web server	Background log rotation	Continuous request handling at higher priority	Logs grow unbounded, disk fills
Desktop system	System updates	User interactive apps always prioritized	Security patches never install
Database server	Index maintenance	Query processing prioritized over maintenance	Query performance degrades over time
Real-time system	Diagnostic tasks	Control loops consume all high-priority slots	System health unknown
Cloud scheduler	Low-bid batch jobs	Premium customers always served first	Batch jobs exceed SLA

The Mars Pathfinder Incident

Detecting Starvation

Unlike deadlock, starvation has no definitive detection algorithm—a process waiting a long time might run eventually. Detection relies on heuristics and monitoring:

Starvation Detection Strategies

•Waiting time thresholds — Alert when any process exceeds maximum expected wait time. Threshold must account for legitimate delays.
•Progress monitoring — Track CPU time granted to each process over intervals. Zero progress over extended periods indicates starvation.
•Priority distribution analysis — Monitor ready queue composition. Persistent presence of low-priority processes signals potential starvation.
•Scheduling decision logging — Record scheduler choices. Repeated skipping of specific processes reveals patterns.
•Statistical analysis — Compare expected vs actual wait times based on priority and load. Significant deviation indicates unfairness.

starvation_monitor.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
/* Simple starvation detection monitor */
#include <stdio.h>
#include <time.h>
 
#define MAX_PROCESSES 100
#define STARVATION_THRESHOLD_MS 30000  /* 30 seconds */
 
typedef struct {
    int pid;
    int priority;
    time_t last_scheduled;
    unsigned long wait_time_ms;
    int is_runnable;
} ProcessInfo;
 
ProcessInfo processes[MAX_PROCESSES];
int process_count = 0;
 
void check_starvation(void) {
    time_t now = time(NULL);
    
    for (int i = 0; i < process_count; i++) {
        if (!processes[i].is_runnable) continue;
        
        unsigned long wait = (now - processes[i].last_scheduled) * 1000;
        
        if (wait > STARVATION_THRESHOLD_MS) {
            printf("WARNING: PID %d (priority %d) potential starvation!\n"
                   "  Wait time: %lu ms (threshold: %d ms)\n",
                   processes[i].pid,
                   processes[i].priority,
                   wait,
                   STARVATION_THRESHOLD_MS);
            
            /* Could trigger: priority boost, alert, or logging */
        }
    }
}
 
void on_process_scheduled(int pid) {
    for (int i = 0; i < process_count; i++) {
        if (processes[i].pid == pid) {
            processes[i].last_scheduled = time(NULL);
            break;
        }
    }
}

Impact of Starvation

Starvation's effects extend beyond the starving process itself, creating cascading failures:

Cascading Effects of Starvation

•Resource accumulation — Starving processes hold memory, file handles, and locks while waiting, depleting system resources.
•Dependent task failures — Processes waiting for starving process's output also stall, propagating delays.
•Queue buildup — Work queued for starving services accumulates, potentially exhausting queue capacity.
•SLA violations — Background tasks with deadlines (backups, reports) miss delivery windows.
•System degradation — Deferred maintenance (garbage collection, log rotation) causes gradual performance decline.
•Unpredictable failures — Tasks that 'always worked before' suddenly fail when starvation threshold reached.

The Hidden Cost

Prevention Principles

Before examining specific solutions (aging, in the next page), consider the general principles for starvation prevention:

Starvation Prevention Principles

•Bounded waiting — Guarantee maximum wait time for any priority level. No process waits indefinitely.
•Progress guarantee — Ensure every runnable process makes progress within bounded time.
•Dynamic priority adjustment — Increase priority of waiting processes over time (aging).
•Reserved capacity — Allocate minimum CPU share to each priority class regardless of higher-priority load.
•Priority ceiling — Limit maximum effective priority to allow lower-priority execution windows.
•Fair share scheduling — Guarantee resource share based on policy, not just priority competition.

The most widely implemented solution is aging—gradually increasing the priority of waiting processes. The next page explores aging mechanisms in detail.

Summary

Key Takeaways

•Starvation is indefinite blocking where a process never receives CPU time despite being runnable.
•Starvation differs from deadlock — the system progresses, but specific processes are excluded.
•Primary cause is continuous high-priority arrivals overwhelming low-priority capacity.
•Detection relies on monitoring waiting times, progress, and scheduling patterns.
•Impact cascades — resource accumulation, dependent failures, and deferred maintenance compound.
•Prevention requires explicit mechanisms — aging, reserved capacity, or fair-share policies.

Next: The Aging Solution

The next page examines aging—the primary mechanism for preventing starvation by gradually elevating waiting process priorities, ensuring bounded waiting times.

3 / 5