Operating SystemsCPU Scheduling

Priority Scheduling

LevelIntermediate

Duration90 mins

TopicCPU Scheduling

2 / 5

Preemptive vs Non-Preemptive Priority Scheduling

The Preemption Decision

When a higher-priority process becomes ready while a lower-priority process is running, the scheduler faces a critical decision: interrupt the running process immediately, or let it continue until it voluntarily yields? This decision defines the distinction between preemptive and non-preemptive scheduling.

The choice has profound implications for system responsiveness, throughput, complexity, and correctness. Understanding both approaches—and when to apply each—is essential for systems programming and real-time application development.

Learning Objectives

Understand the mechanics of preemptive and non-preemptive scheduling, analyze their tradeoffs, recognize appropriate use cases for each, and predict scheduling behavior given process arrival patterns.

Non-Preemptive Priority Scheduling

In non-preemptive (cooperative) priority scheduling, once a process starts executing, it retains the CPU until it:

Terminates — Process completes execution
Blocks — Process waits for I/O or synchronization
Yields — Process voluntarily relinquishes CPU

A higher-priority process arriving while a lower-priority process runs must wait. The scheduler only considers priorities at decision points—when the running process releases the CPU.

Characteristics

Non-Preemptive Scheduling Properties

•Simplicity — No mid-execution interrupts simplify synchronization. No race conditions from unexpected context switches.
•Predictable execution — Once started, a process runs without interruption until a natural yield point.
•Lower overhead — Fewer context switches mean less CPU time spent on scheduling mechanics.
•Poor responsiveness — High-priority arrivals wait for running process to yield, causing unpredictable latency.
•Starvation risk — CPU-bound process can monopolize processor indefinitely.

non_preemptive_simulation.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
"""
Non-Preemptive Priority Scheduling Simulation
Higher priority number = higher priority (runs first)
"""
from dataclasses import dataclass
from typing import List
import heapq
 
@dataclass
class Process:
    pid: str
    arrival: int
    burst: int
    priority: int
    start: int = -1
    finish: int = -1
 
def non_preemptive_priority(processes: List[Process]) -> List[Process]:
    """Simulate non-preemptive priority scheduling."""
    time = 0
    ready_queue = []  # Max-heap: (-priority, arrival, process)
    completed = []
    waiting = list(processes)
    
    while waiting or ready_queue:
        # Add newly arrived processes to ready queue
        for p in waiting[:]:
            if p.arrival <= time:
                heapq.heappush(ready_queue, (-p.priority, p.arrival, p))
                waiting.remove(p)
        
        if not ready_queue:
            time = min(p.arrival for p in waiting)  # Jump to next arrival
            continue
        
        # Select highest priority (lowest -priority value)
        _, _, current = heapq.heappop(ready_queue)
        current.start = time
        current.finish = time + current.burst
        time = current.finish  # Process runs to completion
        completed.append(current)
    
    return completed
 
# Example: P2 (high priority) arrives while P1 runs - must wait
processes = [
    Process("P1", arrival=0, burst=10, priority=1),  # Low priority
    Process("P2", arrival=2, burst=4, priority=3),   # High priority
    Process("P3", arrival=3, burst=2, priority=2),   # Medium priority
]
 
result = non_preemptive_priority(processes)
print("Non-Preemptive Priority Schedule:")
print(f"{'PID':<6}{'Arrival':<10}{'Start':<10}{'Finish':<10}{'Wait':<10}")
for p in result:
    wait = p.start - p.arrival
    print(f"{p.pid:<6}{p.arrival:<10}{p.start:<10}{p.finish:<10}{wait:<10}")
# P2 arrives at t=2 but waits until P1 finishes at t=10

Preemptive Priority Scheduling

In preemptive priority scheduling, the scheduler can interrupt a running process when a higher-priority process becomes ready. The interrupted process returns to the ready queue, and the higher-priority process begins execution immediately.

Preemption occurs when:

Higher-priority process arrives — New process or unblocked process has higher priority than running process
Priority changes — Dynamic priority adjustment elevates a waiting process above the running process
Timer interrupt — Periodic check allows scheduler to reevaluate (even without priority change)

Preemptive Scheduling Properties

•High responsiveness — High-priority tasks execute with minimal delay regardless of current workload.
•Real-time capable — Essential for meeting deadlines in time-critical systems.
•Complex synchronization — Preemption mid-critical-section requires careful lock design.
•Higher overhead — More context switches consume CPU cycles and cache resources.
•Priority inversion risk — Complex interactions between priorities and resource holding.

preemptive_simulation.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
"""
Preemptive Priority Scheduling Simulation
Demonstrates immediate preemption on higher-priority arrival
"""
from dataclasses import dataclass, field
from typing import List
import heapq
 
@dataclass
class Process:
    pid: str
    arrival: int
    burst: int
    priority: int
    remaining: int = field(init=False)
    timeline: List[tuple] = field(default_factory=list)
    
    def __post_init__(self):
        self.remaining = self.burst
 
def preemptive_priority(processes: List[Process]) -> List[Process]:
    """Simulate preemptive priority scheduling."""
    time = 0
    ready_queue = []
    completed = []
    waiting = sorted(processes, key=lambda p: p.arrival)
    current = None
    
    while waiting or ready_queue or current:
        # Add newly arrived processes
        while waiting and waiting[0].arrival <= time:
            p = waiting.pop(0)
            heapq.heappush(ready_queue, (-p.priority, p.arrival, p))
            
            # Check for preemption
            if current and p.priority > current.priority:
                heapq.heappush(ready_queue, (-current.priority, current.arrival, current))
                current.timeline.append((current.timeline[-1][1] if current.timeline else time, time))
                current = None
        
        # Select highest priority if no current process
        if not current and ready_queue:
            _, _, current = heapq.heappop(ready_queue)
            start = time
        
        if not current:
            time = waiting[0].arrival if waiting else time + 1
            continue
        
        # Find next event (arrival or completion)
        next_arrival = waiting[0].arrival if waiting else float('inf')
        completion = time + current.remaining
        
        if completion <= next_arrival:
            current.remaining = 0
            current.timeline.append((time, completion))
            time = completion
            completed.append(current)
            current = None
        else:
            current.remaining -= (next_arrival - time)
            if time < next_arrival:
                current.timeline.append((time, next_arrival))
            time = next_arrival
    
    return completed
 
# Same example: P2 (high priority) NOW preempts P1
processes = [
    Process("P1", arrival=0, burst=10, priority=1),
    Process("P2", arrival=2, burst=4, priority=3),
    Process("P3", arrival=3, burst=2, priority=2),
]
 
result = preemptive_priority(processes)
print("Preemptive Priority Schedule:")
for p in result:
    print(f"{p.pid}: {p.timeline}")
# P2 preempts P1 at t=2, runs t=2-6
# P3 runs t=6-8, P1 resumes t=8-16

Comparative Analysis

Preemptive vs Non-Preemptive Priority Scheduling
Criterion	Non-Preemptive	Preemptive
Response Time (high-priority)	Unpredictable, depends on running process	Minimal, bounded by interrupt latency
Throughput	Higher (fewer switches)	Lower (more switches)
Context Switch Overhead	Low	Higher
Implementation Complexity	Simple	Complex (requires interrupt handling)
Starvation of Low Priority	Less severe	More severe without aging
Critical Section Safety	Naturally safe	Requires explicit protection
Real-time Suitability	Soft real-time only	Hard real-time capable
Predictability	Process-level determinism	Priority-level determinism

Converting Mermaid diagram...

Practical Use Cases

Use Non-Preemptive When

•Cooperative multitasking environments (older Windows, classic Mac OS)
•Embedded systems with deterministic timing requirements
•Batch processing where throughput matters more than response
•Systems where critical sections cannot be interrupted
•Simple kernels where complexity must be minimized

Use Preemptive When

•Interactive systems requiring immediate user response
•Real-time systems with strict deadline guarantees
•Multi-user environments needing fairness
•Mixed workloads (I/O-bound and CPU-bound together)
•Modern general-purpose operating systems (Linux, Windows, macOS)

Hybrid Approaches

Many real systems use hybrid approaches: preemption between priority classes but non-preemptive (or round-robin) within a class. Linux SCHED_FIFO is preemptive across priorities but non-preemptive among equal-priority processes.

Implementation Considerations

Implementing preemptive scheduling requires careful attention to:

Context Saving

When preempting, the kernel must save the complete execution context: CPU registers, program counter, stack pointer, FPU state, and potentially SIMD registers. This context must be restored exactly when the process resumes.

Critical Section Protection

Code sequences that must not be interrupted require explicit protection. Options include:

Disabling interrupts (kernel mode only, shortest possible duration)
Spinlocks for multi-processor systems
Priority ceiling protocols to prevent inversion

Kernel Preemption

Modern kernels like Linux support kernel preemption—preempting even kernel code paths (with careful exclusions). This improves latency but adds complexity.

preemption_protection.c
C (Linux Kernel)
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
/* Linux kernel preemption control examples */
 
#include <linux/preempt.h>
#include <linux/spinlock.h>
 
/* Disable preemption for critical section */
void critical_operation(void)
{
    preempt_disable();  /* Increment preempt count */
    
    /* Critical code - cannot be preempted */
    do_critical_work();
    
    preempt_enable();   /* Decrement; may reschedule */
}
 
/* Spinlock implicitly disables preemption */
static DEFINE_SPINLOCK(my_lock);
 
void spinlock_protected(void)
{
    spin_lock(&my_lock);  /* Disables preemption + acquires lock */
    
    /* Protected code */
    modify_shared_data();
    
    spin_unlock(&my_lock);  /* Re-enables preemption */
}
 
/* Check if preemption is safe */
void conditional_yield(void)
{
    if (need_resched() && preemptible()) {
        /* Voluntary preemption point */
        cond_resched();
    }
}

Summary

Key Takeaways

•Non-preemptive scheduling waits for processes to yield voluntarily—simpler but less responsive.
•Preemptive scheduling interrupts running processes for higher-priority arrivals—responsive but complex.
•Preemption overhead includes context switch cost and synchronization complexity.
•Real-time systems require preemption to meet deadline guarantees.
•Critical sections need protection in preemptive environments.
•Modern systems are preemptive, often with kernel preemption for improved latency.

Next: The Starvation Problem

With priority-based preemption, low-priority processes may never run if higher-priority work constantly arrives. The next page examines this starvation problem and its manifestations.

2 / 5

Loading learning content...

Operating SystemsCPU Scheduling

Priority Scheduling

LevelIntermediate

Duration90 mins

TopicCPU Scheduling

2 / 5

Preemptive vs Non-Preemptive Priority Scheduling

The Preemption Decision

Learning Objectives

Non-Preemptive Priority Scheduling

In non-preemptive (cooperative) priority scheduling, once a process starts executing, it retains the CPU until it:

Terminates — Process completes execution
Blocks — Process waits for I/O or synchronization
Yields — Process voluntarily relinquishes CPU

A higher-priority process arriving while a lower-priority process runs must wait. The scheduler only considers priorities at decision points—when the running process releases the CPU.

Characteristics

Non-Preemptive Scheduling Properties

•Simplicity — No mid-execution interrupts simplify synchronization. No race conditions from unexpected context switches.
•Predictable execution — Once started, a process runs without interruption until a natural yield point.
•Lower overhead — Fewer context switches mean less CPU time spent on scheduling mechanics.
•Poor responsiveness — High-priority arrivals wait for running process to yield, causing unpredictable latency.
•Starvation risk — CPU-bound process can monopolize processor indefinitely.

non_preemptive_simulation.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
"""
Non-Preemptive Priority Scheduling Simulation
Higher priority number = higher priority (runs first)
"""
from dataclasses import dataclass
from typing import List
import heapq
 
@dataclass
class Process:
    pid: str
    arrival: int
    burst: int
    priority: int
    start: int = -1
    finish: int = -1
 
def non_preemptive_priority(processes: List[Process]) -> List[Process]:
    """Simulate non-preemptive priority scheduling."""
    time = 0
    ready_queue = []  # Max-heap: (-priority, arrival, process)
    completed = []
    waiting = list(processes)
    
    while waiting or ready_queue:
        # Add newly arrived processes to ready queue
        for p in waiting[:]:
            if p.arrival <= time:
                heapq.heappush(ready_queue, (-p.priority, p.arrival, p))
                waiting.remove(p)
        
        if not ready_queue:
            time = min(p.arrival for p in waiting)  # Jump to next arrival
            continue
        
        # Select highest priority (lowest -priority value)
        _, _, current = heapq.heappop(ready_queue)
        current.start = time
        current.finish = time + current.burst
        time = current.finish  # Process runs to completion
        completed.append(current)
    
    return completed
 
# Example: P2 (high priority) arrives while P1 runs - must wait
processes = [
    Process("P1", arrival=0, burst=10, priority=1),  # Low priority
    Process("P2", arrival=2, burst=4, priority=3),   # High priority
    Process("P3", arrival=3, burst=2, priority=2),   # Medium priority
]
 
result = non_preemptive_priority(processes)
print("Non-Preemptive Priority Schedule:")
print(f"{'PID':<6}{'Arrival':<10}{'Start':<10}{'Finish':<10}{'Wait':<10}")
for p in result:
    wait = p.start - p.arrival
    print(f"{p.pid:<6}{p.arrival:<10}{p.start:<10}{p.finish:<10}{wait:<10}")
# P2 arrives at t=2 but waits until P1 finishes at t=10

Preemptive Priority Scheduling

Preemption occurs when:

Higher-priority process arrives — New process or unblocked process has higher priority than running process
Priority changes — Dynamic priority adjustment elevates a waiting process above the running process
Timer interrupt — Periodic check allows scheduler to reevaluate (even without priority change)

Preemptive Scheduling Properties

•High responsiveness — High-priority tasks execute with minimal delay regardless of current workload.
•Real-time capable — Essential for meeting deadlines in time-critical systems.
•Complex synchronization — Preemption mid-critical-section requires careful lock design.
•Higher overhead — More context switches consume CPU cycles and cache resources.
•Priority inversion risk — Complex interactions between priorities and resource holding.

preemptive_simulation.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
"""
Preemptive Priority Scheduling Simulation
Demonstrates immediate preemption on higher-priority arrival
"""
from dataclasses import dataclass, field
from typing import List
import heapq
 
@dataclass
class Process:
    pid: str
    arrival: int
    burst: int
    priority: int
    remaining: int = field(init=False)
    timeline: List[tuple] = field(default_factory=list)
    
    def __post_init__(self):
        self.remaining = self.burst
 
def preemptive_priority(processes: List[Process]) -> List[Process]:
    """Simulate preemptive priority scheduling."""
    time = 0
    ready_queue = []
    completed = []
    waiting = sorted(processes, key=lambda p: p.arrival)
    current = None
    
    while waiting or ready_queue or current:
        # Add newly arrived processes
        while waiting and waiting[0].arrival <= time:
            p = waiting.pop(0)
            heapq.heappush(ready_queue, (-p.priority, p.arrival, p))
            
            # Check for preemption
            if current and p.priority > current.priority:
                heapq.heappush(ready_queue, (-current.priority, current.arrival, current))
                current.timeline.append((current.timeline[-1][1] if current.timeline else time, time))
                current = None
        
        # Select highest priority if no current process
        if not current and ready_queue:
            _, _, current = heapq.heappop(ready_queue)
            start = time
        
        if not current:
            time = waiting[0].arrival if waiting else time + 1
            continue
        
        # Find next event (arrival or completion)
        next_arrival = waiting[0].arrival if waiting else float('inf')
        completion = time + current.remaining
        
        if completion <= next_arrival:
            current.remaining = 0
            current.timeline.append((time, completion))
            time = completion
            completed.append(current)
            current = None
        else:
            current.remaining -= (next_arrival - time)
            if time < next_arrival:
                current.timeline.append((time, next_arrival))
            time = next_arrival
    
    return completed
 
# Same example: P2 (high priority) NOW preempts P1
processes = [
    Process("P1", arrival=0, burst=10, priority=1),
    Process("P2", arrival=2, burst=4, priority=3),
    Process("P3", arrival=3, burst=2, priority=2),
]
 
result = preemptive_priority(processes)
print("Preemptive Priority Schedule:")
for p in result:
    print(f"{p.pid}: {p.timeline}")
# P2 preempts P1 at t=2, runs t=2-6
# P3 runs t=6-8, P1 resumes t=8-16

Comparative Analysis

Preemptive vs Non-Preemptive Priority Scheduling
Criterion	Non-Preemptive	Preemptive
Response Time (high-priority)	Unpredictable, depends on running process	Minimal, bounded by interrupt latency
Throughput	Higher (fewer switches)	Lower (more switches)
Context Switch Overhead	Low	Higher
Implementation Complexity	Simple	Complex (requires interrupt handling)
Starvation of Low Priority	Less severe	More severe without aging
Critical Section Safety	Naturally safe	Requires explicit protection
Real-time Suitability	Soft real-time only	Hard real-time capable
Predictability	Process-level determinism	Priority-level determinism

Converting Mermaid diagram...

Practical Use Cases

Use Non-Preemptive When

•Cooperative multitasking environments (older Windows, classic Mac OS)
•Embedded systems with deterministic timing requirements
•Batch processing where throughput matters more than response
•Systems where critical sections cannot be interrupted
•Simple kernels where complexity must be minimized

Use Preemptive When

•Interactive systems requiring immediate user response
•Real-time systems with strict deadline guarantees
•Multi-user environments needing fairness
•Mixed workloads (I/O-bound and CPU-bound together)
•Modern general-purpose operating systems (Linux, Windows, macOS)

Hybrid Approaches

Implementation Considerations

Implementing preemptive scheduling requires careful attention to:

Context Saving

Critical Section Protection

Code sequences that must not be interrupted require explicit protection. Options include:

Disabling interrupts (kernel mode only, shortest possible duration)
Spinlocks for multi-processor systems
Priority ceiling protocols to prevent inversion

Kernel Preemption

Modern kernels like Linux support kernel preemption—preempting even kernel code paths (with careful exclusions). This improves latency but adds complexity.

preemption_protection.c
C (Linux Kernel)
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
/* Linux kernel preemption control examples */
 
#include <linux/preempt.h>
#include <linux/spinlock.h>
 
/* Disable preemption for critical section */
void critical_operation(void)
{
    preempt_disable();  /* Increment preempt count */
    
    /* Critical code - cannot be preempted */
    do_critical_work();
    
    preempt_enable();   /* Decrement; may reschedule */
}
 
/* Spinlock implicitly disables preemption */
static DEFINE_SPINLOCK(my_lock);
 
void spinlock_protected(void)
{
    spin_lock(&my_lock);  /* Disables preemption + acquires lock */
    
    /* Protected code */
    modify_shared_data();
    
    spin_unlock(&my_lock);  /* Re-enables preemption */
}
 
/* Check if preemption is safe */
void conditional_yield(void)
{
    if (need_resched() && preemptible()) {
        /* Voluntary preemption point */
        cond_resched();
    }
}

Summary

Key Takeaways

•Non-preemptive scheduling waits for processes to yield voluntarily—simpler but less responsive.
•Preemptive scheduling interrupts running processes for higher-priority arrivals—responsive but complex.
•Preemption overhead includes context switch cost and synchronization complexity.
•Real-time systems require preemption to meet deadline guarantees.
•Critical sections need protection in preemptive environments.
•Modern systems are preemptive, often with kernel preemption for improved latency.

Next: The Starvation Problem

With priority-based preemption, low-priority processes may never run if higher-priority work constantly arrives. The next page examines this starvation problem and its manifestations.

2 / 5