Operating SystemsCPU Scheduling

Scheduling Concepts

LevelIntermediate

Duration60 mins

TopicCPU Scheduling

3 / 5

Preemptive vs Non-preemptive

Who Controls the CPU?

At the heart of every CPU scheduling system lies a fundamental question: When can the operating system take the CPU away from a running process?

The answer to this question divides all scheduling approaches into two categories with profoundly different characteristics:

Non-preemptive (Cooperative) scheduling: Once a process has the CPU, it keeps it until it voluntarily gives it up—by blocking on I/O, waiting for a resource, or terminating.
Preemptive scheduling: The operating system can forcibly take the CPU from a running process, typically via timer interrupts, to give it to another process.

This distinction isn't merely academic—it shapes user experience, system security, fairness guarantees, and the complexity of kernel design. Understanding this choice is essential for grasping why modern operating systems work the way they do.

What You Will Learn

By the end of this page, you will understand: (1) The precise definitions and mechanics of both scheduling types, (2) When scheduling decisions occur in each model, (3) The tradeoffs between responsiveness, throughput, and complexity, (4) Historical context and why preemption became dominant, and (5) Where non-preemptive scheduling is still used today.

Non-preemptive (Cooperative) Scheduling

In non-preemptive scheduling (also called cooperative scheduling), a process retains the CPU until it explicitly relinquishes control. The operating system cannot forcibly remove a running process; it must wait for the process to cooperate.

Formal definition:

In a non-preemptive system, scheduling decisions occur only at these points:

Process termination: The running process exits (voluntarily or due to error)
Process blocks: The running process makes a blocking system call (I/O, wait for lock, etc.)
Voluntary yield: The process explicitly calls a yield function (if available)

Crucially, scheduling does NOT occur:

When a higher-priority process becomes ready
When a timer expires (no timer-based preemption)
When the current process has been running "too long"

Converting Mermaid diagram...

non_preemptive_behavior.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
// In a non-preemptive system, this loop runs forever
// No timer interrupt will stop it
// No higher-priority process can preempt it
// Only way to stop: I/O, yield(), or termination
 
#include <stdbool.h>
 
void malicious_or_buggy_process() {
    // This would freeze the entire system on single-CPU non-preemptive OS
    while (true) {
        // Pure computation - no I/O, no yielding
        volatile int x = 0;
        x++;
    }
    // Never reaches here
    // Other processes never run
    // User cannot interact with system
}
 
// In a well-behaved non-preemptive system, processes must cooperate:
void cooperative_process() {
    while (true) {
        // Do some work
        perform_computation();
        
        // Explicitly yield to let others run
        yield();  // "I'm done for now, let someone else have a turn"
        
        // This requires TRUST that all processes yield regularly
        // One misbehaving process breaks the entire system
    }
}

Characteristics of non-preemptive scheduling:

•Simple kernel design: No need to handle interrupting an arbitrary instruction; process state is well-defined at yield points
•No race conditions from preemption: Critical sections complete atomically (within user space)
•Lower overhead: No timer interrupt handling, fewer context switches
•No fairness guarantees: A single process can monopolize the CPU indefinitely
•Poor responsiveness: High-priority events must wait for current process to yield
•Vulnerability to bugs/malice: One infinite loop freezes the entire system

The Trust Problem

Non-preemptive scheduling only works when all processes are trusted to yield regularly. In a general-purpose OS with arbitrary user programs, this trust is impossible to guarantee. A buggy program (e.g., infinite loop) or malicious software can freeze the entire system. This is why non-preemptive scheduling is no longer used for general-purpose operating systems.

Preemptive Scheduling

In preemptive scheduling, the operating system can forcibly remove the CPU from a running process, even if the process hasn't completed or voluntarily yielded. This is typically accomplished through hardware timer interrupts.

Formal definition:

In a preemptive system, scheduling decisions can occur at:

All non-preemptive points (termination, blocking, voluntary yield)
Timer interrupt expiration (time quantum exhausted)
Higher-priority process becoming ready (in priority-based systems)
Any interrupt completion that affects the ready queue

The key mechanism: A hardware timer is programmed to generate an interrupt at regular intervals (typically 1-10 milliseconds). When the interrupt fires, the kernel's interrupt handler saves the current process's state and invokes the scheduler to decide what to run next.

Converting Mermaid diagram...

preemption_mechanism.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
// Conceptual illustration of how preemption works
 
// === Hardware Timer Interrupt Flow ===
 
// The hardware timer generates an interrupt every N milliseconds
// This causes the CPU to:
// 1. Save current instruction pointer to stack
// 2. Switch to kernel mode
// 3. Jump to interrupt handler address
 
void timer_interrupt_handler(struct cpu_state *regs) {
    // STEP 1: Save complete process state
    // The current process was executing arbitrary user code
    // We must save EVERYTHING: registers, flags, FPU state
    save_process_state(current_process, regs);
    
    // STEP 2: Acknowledge the interrupt
    acknowledge_timer_interrupt();
    
    // STEP 3: Update accounting
    current_process->time_used += TIMER_QUANTUM;
    current_process->remaining_quantum--;
    
    // STEP 4: Check if preemption is needed
    if (current_process->remaining_quantum <= 0 ||
        higher_priority_process_ready()) {
        
        // STEP 5: Invoke scheduler to pick next process
        struct process *next = schedule();
        
        // STEP 6: Switch to new process
        if (next != current_process) {
            context_switch(current_process, next);
            // This function never returns in the normal sense
            // CPU is now running 'next' process
        }
    }
    
    // STEP 7: Return from interrupt
    // Restores user-mode and resumes execution
    return_from_interrupt();
}
 
// Key insight: The running process has NO CONTROL over this
// It cannot prevent or delay the timer interrupt
// The OS is in charge, not the process

Characteristics of preemptive scheduling:

•Guarantees fairness: No process can monopolize the CPU; all get time slices
•Ensures responsiveness: High-priority events (user input) get handled promptly
•Robust against misbehavior: Infinite loops don't freeze the system; process just loses its quantum
•More complex kernel: Must handle interruption at arbitrary points; requires careful synchronization
•Higher overhead: Timer interrupts, more context switches, cache invalidation
•Race condition complexity: Kernel code must be reentrant and use proper locking

The Time Quantum (Time Slice)

The time quantum (or time slice) is the maximum amount of time a process can run before preemption. Typical values range from 1ms to 100ms. Shorter quanta improve responsiveness but increase context switch overhead. Longer quanta improve throughput but hurt interactive response. Most modern systems use adaptive quanta that vary based on process behavior.

Scheduling Decision Points Compared

To precisely understand the difference between preemptive and non-preemptive scheduling, let's enumerate all possible scheduling decision points and which type responds to each.

Scheduling Decision Points
Event	Non-preemptive	Preemptive	Description
Process terminates	✓ Yes	✓ Yes	Running process exits; must schedule next
Process blocks (I/O)	✓ Yes	✓ Yes	Running process can't continue; must schedule
Process yields voluntarily	✓ Yes (if API exists)	✓ Yes	Process explicitly releases CPU
Timer quantum expires	✗ No	✓ Yes	OS forcibly reclaims CPU
Higher-priority ready	✗ No	✓ Yes (if priority-based)	Preempt for urgent work
I/O completion (wakeup)	✗ No (waits for yield)	✓ Yes (can preempt)	Awakened process may preempt current
New process created	✗ No	✓ Optionally	New process may preempt if higher priority

The critical difference illustrated:

Consider a scenario with Process A (CPU-bound, running) and Process B (I/O-bound, just completed I/O and now ready):

Non-preemptive system:

Time 0ms:   A running, B waiting for I/O
Time 5ms:   B's I/O completes, B moves to ready queue
Time 5ms:   A continues running (B must wait)
Time 10ms:  A continues running (B still waiting)
...
Time 500ms: A finally blocks on I/O
Time 500ms: NOW the scheduler runs, B gets CPU

B waited 495ms even though it was ready and A was just doing computation that could have been interrupted.

Preemptive system:

Time 0ms:   A running, B waiting for I/O
Time 5ms:   B's I/O completes, B moves to ready queue
Time 5ms:   If B has higher priority, A is preempted immediately
              OR waits until A's quantum expires
Time 15ms:  Timer expires, scheduler runs
Time 15ms:  B gets CPU (even if A wanted to continue)

B gets CPU within milliseconds, not seconds.

Immediate vs Deferred Preemption

Some preemptive systems preempt immediately when a higher-priority process becomes ready (immediate preemption), while others wait until the next timer interrupt (deferred preemption). Immediate preemption provides better worst-case latency but requires more complex kernel code. Linux supports both modes depending on configuration.

The Tradeoff Analysis

Neither approach is universally superior—each represents a different balance of competing concerns. Understanding these tradeoffs informs system design decisions.

Non-preemptive Advantages

•Simpler synchronization: No kernel preemption means simpler critical sections
•Lower overhead: Fewer context switches, no timer interrupt handling
•Predictable execution: Process runs to completion without interruption
•Cache efficiency: Longer runs mean better cache utilization
•Determinism: Easier to reason about timing behavior

Non-preemptive Disadvantages

•No fairness guarantees: CPU hogs can starve other processes
•Poor responsiveness: User input delayed by running process
•Vulnerability: One bad actor freezes entire system
•Requires trusted code: Only works with cooperative software
•Real-time unsuitable: Cannot guarantee deadline responsiveness

Preemptive Advantages

•Guaranteed fairness: All processes get CPU time
•Responsive interaction: User input handled promptly
•Robustness: System survives misbehaving processes
•Real-time capable: Can bound response latency
•Multi-user suitable: Fair sharing among users

Preemptive Disadvantages

•Complex kernel: Must handle arbitrary interruption
•Synchronization overhead: Locks needed everywhere
•Context switch cost: Timer interrupts consume cycles
•Cache pollution: Frequent switches reduce cache effectiveness
•Non-deterministic timing: Harder to analyze timing behavior

The overhead quantified:

Context switch overhead on modern systems:

Register save/restore: ~0.5-1 microseconds
Cache/TLB pollution: 10-100 microseconds of degraded performance
Timer interrupt handling: ~1-5 microseconds per interrupt

With 1000 timer interrupts per second (1ms quantum) and 100 context switches per second:

Direct overhead: ~150 microseconds/second = 0.015%
Cache effects: ~10 milliseconds/second = 1%
Total practical overhead: 1-2% of CPU time

For most workloads, this overhead is overwhelmingly justified by the benefits of fairness and responsiveness.

The Historical Verdict

By the 1990s, preemptive scheduling won decisively for general-purpose operating systems. The 1-2% overhead is negligible compared to the benefits of a system that doesn't freeze when one program misbehaves. Every mainstream OS today (Windows, Linux, macOS, iOS, Android) uses preemptive scheduling.

Historical Context and Evolution

The evolution from non-preemptive to preemptive scheduling mirrors the evolution of computing itself—from single-user batch systems to multi-user interactive systems.

Era 1: Early batch systems (1950s-1960s)

The first operating systems were non-preemptive by necessity:

Single-user systems running one job at a time
No concept of "interactive response"
Jobs ran to completion; next job started when previous finished
Simple, but horrific resource utilization during I/O waits

Era 2: Multiprogramming (1960s-1970s)

To improve CPU utilization, multiprogramming was introduced:

Multiple jobs loaded in memory simultaneously
When one job blocked on I/O, another could run
Still non-preemptive: running job kept CPU until it blocked
Example: IBM OS/360 MFT (Multiprogramming with Fixed Tasks)

Era 3: Time-sharing (1960s-1980s)

Interactive computing demanded preemption:

Multiple users sharing a single computer via terminals
Each user needed responsive interaction (sub-second response)
Preemptive scheduling essential: couldn't wait for batch job to finish
Examples: CTSS, Multics, Unix

Historical Operating Systems: Scheduling Type
System	Era	Type	Notes
IBM OS/360 (batch)	1960s	Non-preemptive	Jobs ran to completion or block
CTSS	1961	Preemptive	First time-sharing system
Multics	1960s-70s	Preemptive	Influenced Unix design
Classic Mac OS (1-9)	1984-2001	Cooperative	Last major cooperative consumer OS
Windows 3.x	1990-1994	Cooperative	16-bit Windows applications
Windows 95/NT	1993-1995	Preemptive	Transition to preemptive
Mac OS X	2001	Preemptive	Replaced cooperative Classic Mac OS
Linux	1991-present	Preemptive	Always preemptive

The Classic Mac OS story:

Classic Mac OS (versions 1-9, 1984-2001) is notable as the last major consumer operating system to use cooperative scheduling. This choice had significant consequences:

Advantage: Simpler programming model, lower overhead
Consequence: One misbehaving application froze the entire system
User experience: The infamous "spinning beach ball" with no way to recover except restart
Ultimate fate: Replaced by Mac OS X (based on preemptive Unix/Mach)

Windows had a similar journey—Windows 3.x was cooperative for 16-bit programs, but Windows NT (1993) and Windows 95 (1995) introduced preemptive scheduling.

Why Cooperative Lasted So Long

Cooperative scheduling persisted on personal computers longer than on servers because personal computers were initially single-user, single-task systems. When multitasking became standard, the transition to preemptive scheduling became essential. The stability improvement was dramatic enough that users happily accepted the slightly higher overhead.

Modern Applications of Non-preemptive Scheduling

While preemptive scheduling dominates general-purpose OSes, non-preemptive (cooperative) scheduling remains valuable in specific contexts where its advantages outweigh its risks.

User-space cooperative threading (green threads/fibers):

Many modern languages and runtimes implement cooperative scheduling within a preemptively scheduled process:

cooperative_examples.py
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
# Python asyncio: Cooperative scheduling of coroutines
# Within the async runtime, tasks yield cooperatively at 'await' points
# But the OS can still preempt the entire Python process
 
import asyncio
 
async def task_a():
    print("Task A starting")
    await asyncio.sleep(1)  # Cooperative yield point
    print("Task A resuming")
    await asyncio.sleep(1)  # Another yield point
    print("Task A done")
 
async def task_b():
    print("Task B starting")
    await asyncio.sleep(0.5)  # Yields to other tasks
    print("Task B done")
 
async def main():
    # Both tasks run "concurrently" via cooperative scheduling
    await asyncio.gather(task_a(), task_b())
 
# This is cooperative scheduling:
# - Tasks voluntarily yield at 'await'
# - No timer-based preemption within the event loop
# - A task that never awaits blocks all others
 
# BUT the entire Python process is preemptively scheduled by the OS
# So a misbehaving asyncio program doesn't freeze the system
 
asyncio.run(main())

Modern Cooperative Scheduling Examples

•Go goroutines: Cooperatively scheduled by Go runtime; OS preempts the runtime itself
•Python asyncio: Coroutines yield at await points; used for I/O-bound concurrency
•JavaScript event loop: Single-threaded cooperative scheduling; async/await for yielding
•Rust async/await: Futures polled cooperatively by async runtimes like tokio
•Game engines: Game loop often uses cooperative task scheduling for AI, physics, etc.

Embedded and real-time systems:

Simple embedded systems often use cooperative scheduling:

Microcontrollers: Resource-constrained devices where timer interrupts add unacceptable overhead
Super loops: Main loop polls each subsystem in sequence; each "yields" by returning
Cooperative RTOS: Some lightweight RTOSes (e.g., FreeRTOS in cooperative mode) support optional non-preemptive operation

Why it works in these contexts:

All code is trusted: Embedded developer controls all software
Predictable execution: Easier to analyze timing for real-time guarantees
Minimal overhead: Critical when CPU cycles are precious
Simple debugging: No race conditions from unexpected preemption

The Hybrid Pattern

Modern systems often combine both approaches: the OS kernel uses preemptive scheduling to manage processes, while user-space runtimes (like Go, Node.js, or asyncio) use cooperative scheduling to manage lightweight tasks within a process. This gives the best of both worlds: system stability from OS preemption, plus efficiency from user-space cooperation.

Kernel Preemption: A Deeper Layer

Our discussion so far has focused on user-space preemption—can the OS preempt user processes? But there's another level: kernel preemption—can the OS preempt code running in kernel mode?

The distinction:

User preemption: Always enabled in preemptive systems—OS can interrupt user code anytime
Kernel preemption: Whether the kernel can be interrupted while executing kernel code (system calls, interrupt handlers)

Why kernel preemption is harder:

Kernel code manipulates shared data structures (process tables, file systems, device state). If preempted mid-operation, another process might see inconsistent state:

kernel_preemption_problem.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
// Problem: Kernel preemption during critical operation
 
// Process A is in kernel mode, allocating a page
void allocate_page_frame() {
    struct page *page = get_free_page();  // Gets page 0x1000
    
    // PREEMPTION HAPPENS HERE
    // Process B runs, also allocates a page
    // B gets the SAME page 0x1000 (still marked free!)
    
    page->owner = current_process;  // A marks it as owned
    page->flags = PAGE_PRESENT;
    add_to_page_table(current_process, page);
    
    // Both A and B now think they own page 0x1000
    // Data corruption guaranteed
}
 
// Solution 1: Non-preemptive kernel
// System calls run to completion; no preemption during kernel mode
// Simple but hurts latency
 
// Solution 2: Preemptive kernel with locks
void allocate_page_frame_safe() {
    spin_lock(&page_allocator_lock);  // Disable preemption in critical section
    
    struct page *page = get_free_page();
    page->owner = current_process;
    page->flags = PAGE_PRESENT;
    add_to_page_table(current_process, page);
    
    spin_unlock(&page_allocator_lock);  // Re-enable preemption
}

Kernel preemption in major operating systems:

OS	Kernel Preemptibility	Notes
Linux (default)	Preemptible	Can preempt kernel code except in critical sections
Linux PREEMPT_RT	Fully preemptible	Even spinlocks are preemptible for real-time
Windows NT	Preemptible	Kernel-mode APCs can preempt kernel code
macOS/XNU	Partly preemptible	Mach microkernel portions preemptible
FreeBSD	Optional	PREEMPTION kernel option

Linux preemption models:

PREEMPT_NONE: No kernel preemption (server workloads—maximum throughput)
PREEMPT_VOLUNTARY: Explicit preemption points (traditional desktop)
PREEMPT: Full preemption except spinlock-held regions (low-latency desktop)
PREEMPT_RT: Real-time patches—spinlocks become mutex, almost fully preemptible

Latency Implications

Kernel preemption primarily affects worst-case latency for high-priority tasks. Without kernel preemption, a high-priority process might wait for a long-running system call in another process to complete. With kernel preemption, the scheduler can intervene. This matters for audio/video processing, gaming, and real-time control systems.

Summary: Preemptive vs Non-preemptive

The choice between preemptive and non-preemptive scheduling is foundational to operating system design. Let's consolidate the key insights:

Key Takeaways

•Non-preemptive scheduling relies on processes voluntarily yielding; simple but vulnerable to misbehavior.
•Preemptive scheduling uses timer interrupts to forcibly reclaim the CPU; complex but robust.
•Scheduling decision points differ: non-preemptive only on block/yield/exit; preemptive adds timer expiry and priority changes.
•Preemption won for general-purpose OSes due to fairness, responsiveness, and robustness benefits outweighing 1-2% overhead.
•Cooperative scheduling survives in user-space runtimes (asyncio, goroutines) and simple embedded systems where trust is guaranteed.
•Kernel preemption adds another layer—whether kernel code itself can be interrupted—affecting system latency.

What's next:

With the preemption question settled (modern systems are preemptive), we can now explore scheduling criteria—the metrics by which we evaluate scheduling algorithms. CPU utilization, throughput, turnaround time, waiting time, response time—each represents a different stakeholder's priorities, and no algorithm can optimize all simultaneously.

Page Complete

You now understand the fundamental distinction between preemptive and non-preemptive scheduling—why preemption exists, how it works mechanically (timer interrupts), what tradeoffs it involves, and where cooperative scheduling still has a role. This understanding is essential for appreciating why scheduling algorithms take the forms they do.

3 / 5

Loading learning content...

Operating SystemsCPU Scheduling

Scheduling Concepts

LevelIntermediate

Duration60 mins

TopicCPU Scheduling

3 / 5

Preemptive vs Non-preemptive

Who Controls the CPU?

At the heart of every CPU scheduling system lies a fundamental question: When can the operating system take the CPU away from a running process?

The answer to this question divides all scheduling approaches into two categories with profoundly different characteristics:

Non-preemptive (Cooperative) scheduling: Once a process has the CPU, it keeps it until it voluntarily gives it up—by blocking on I/O, waiting for a resource, or terminating.
Preemptive scheduling: The operating system can forcibly take the CPU from a running process, typically via timer interrupts, to give it to another process.

What You Will Learn

Non-preemptive (Cooperative) Scheduling

Formal definition:

In a non-preemptive system, scheduling decisions occur only at these points:

Process termination: The running process exits (voluntarily or due to error)
Process blocks: The running process makes a blocking system call (I/O, wait for lock, etc.)
Voluntary yield: The process explicitly calls a yield function (if available)

Crucially, scheduling does NOT occur:

When a higher-priority process becomes ready
When a timer expires (no timer-based preemption)
When the current process has been running "too long"

Converting Mermaid diagram...

non_preemptive_behavior.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
// In a non-preemptive system, this loop runs forever
// No timer interrupt will stop it
// No higher-priority process can preempt it
// Only way to stop: I/O, yield(), or termination
 
#include <stdbool.h>
 
void malicious_or_buggy_process() {
    // This would freeze the entire system on single-CPU non-preemptive OS
    while (true) {
        // Pure computation - no I/O, no yielding
        volatile int x = 0;
        x++;
    }
    // Never reaches here
    // Other processes never run
    // User cannot interact with system
}
 
// In a well-behaved non-preemptive system, processes must cooperate:
void cooperative_process() {
    while (true) {
        // Do some work
        perform_computation();
        
        // Explicitly yield to let others run
        yield();  // "I'm done for now, let someone else have a turn"
        
        // This requires TRUST that all processes yield regularly
        // One misbehaving process breaks the entire system
    }
}

Characteristics of non-preemptive scheduling:

•Simple kernel design: No need to handle interrupting an arbitrary instruction; process state is well-defined at yield points
•No race conditions from preemption: Critical sections complete atomically (within user space)
•Lower overhead: No timer interrupt handling, fewer context switches
•No fairness guarantees: A single process can monopolize the CPU indefinitely
•Poor responsiveness: High-priority events must wait for current process to yield
•Vulnerability to bugs/malice: One infinite loop freezes the entire system

The Trust Problem

Preemptive Scheduling

Formal definition:

In a preemptive system, scheduling decisions can occur at:

All non-preemptive points (termination, blocking, voluntary yield)
Timer interrupt expiration (time quantum exhausted)
Higher-priority process becoming ready (in priority-based systems)
Any interrupt completion that affects the ready queue

Converting Mermaid diagram...

preemption_mechanism.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
// Conceptual illustration of how preemption works
 
// === Hardware Timer Interrupt Flow ===
 
// The hardware timer generates an interrupt every N milliseconds
// This causes the CPU to:
// 1. Save current instruction pointer to stack
// 2. Switch to kernel mode
// 3. Jump to interrupt handler address
 
void timer_interrupt_handler(struct cpu_state *regs) {
    // STEP 1: Save complete process state
    // The current process was executing arbitrary user code
    // We must save EVERYTHING: registers, flags, FPU state
    save_process_state(current_process, regs);
    
    // STEP 2: Acknowledge the interrupt
    acknowledge_timer_interrupt();
    
    // STEP 3: Update accounting
    current_process->time_used += TIMER_QUANTUM;
    current_process->remaining_quantum--;
    
    // STEP 4: Check if preemption is needed
    if (current_process->remaining_quantum <= 0 ||
        higher_priority_process_ready()) {
        
        // STEP 5: Invoke scheduler to pick next process
        struct process *next = schedule();
        
        // STEP 6: Switch to new process
        if (next != current_process) {
            context_switch(current_process, next);
            // This function never returns in the normal sense
            // CPU is now running 'next' process
        }
    }
    
    // STEP 7: Return from interrupt
    // Restores user-mode and resumes execution
    return_from_interrupt();
}
 
// Key insight: The running process has NO CONTROL over this
// It cannot prevent or delay the timer interrupt
// The OS is in charge, not the process

Characteristics of preemptive scheduling:

•Guarantees fairness: No process can monopolize the CPU; all get time slices
•Ensures responsiveness: High-priority events (user input) get handled promptly
•Robust against misbehavior: Infinite loops don't freeze the system; process just loses its quantum
•More complex kernel: Must handle interruption at arbitrary points; requires careful synchronization
•Higher overhead: Timer interrupts, more context switches, cache invalidation
•Race condition complexity: Kernel code must be reentrant and use proper locking

The Time Quantum (Time Slice)

Scheduling Decision Points Compared

To precisely understand the difference between preemptive and non-preemptive scheduling, let's enumerate all possible scheduling decision points and which type responds to each.

Scheduling Decision Points
Event	Non-preemptive	Preemptive	Description
Process terminates	✓ Yes	✓ Yes	Running process exits; must schedule next
Process blocks (I/O)	✓ Yes	✓ Yes	Running process can't continue; must schedule
Process yields voluntarily	✓ Yes (if API exists)	✓ Yes	Process explicitly releases CPU
Timer quantum expires	✗ No	✓ Yes	OS forcibly reclaims CPU
Higher-priority ready	✗ No	✓ Yes (if priority-based)	Preempt for urgent work
I/O completion (wakeup)	✗ No (waits for yield)	✓ Yes (can preempt)	Awakened process may preempt current
New process created	✗ No	✓ Optionally	New process may preempt if higher priority

The critical difference illustrated:

Consider a scenario with Process A (CPU-bound, running) and Process B (I/O-bound, just completed I/O and now ready):

Non-preemptive system:

Time 0ms:   A running, B waiting for I/O
Time 5ms:   B's I/O completes, B moves to ready queue
Time 5ms:   A continues running (B must wait)
Time 10ms:  A continues running (B still waiting)
...
Time 500ms: A finally blocks on I/O
Time 500ms: NOW the scheduler runs, B gets CPU

B waited 495ms even though it was ready and A was just doing computation that could have been interrupted.

Preemptive system:

Time 0ms:   A running, B waiting for I/O
Time 5ms:   B's I/O completes, B moves to ready queue
Time 5ms:   If B has higher priority, A is preempted immediately
              OR waits until A's quantum expires
Time 15ms:  Timer expires, scheduler runs
Time 15ms:  B gets CPU (even if A wanted to continue)

B gets CPU within milliseconds, not seconds.

Immediate vs Deferred Preemption

The Tradeoff Analysis

Neither approach is universally superior—each represents a different balance of competing concerns. Understanding these tradeoffs informs system design decisions.

Non-preemptive Advantages

•Simpler synchronization: No kernel preemption means simpler critical sections
•Lower overhead: Fewer context switches, no timer interrupt handling
•Predictable execution: Process runs to completion without interruption
•Cache efficiency: Longer runs mean better cache utilization
•Determinism: Easier to reason about timing behavior

Non-preemptive Disadvantages

•No fairness guarantees: CPU hogs can starve other processes
•Poor responsiveness: User input delayed by running process
•Vulnerability: One bad actor freezes entire system
•Requires trusted code: Only works with cooperative software
•Real-time unsuitable: Cannot guarantee deadline responsiveness

Preemptive Advantages

•Guaranteed fairness: All processes get CPU time
•Responsive interaction: User input handled promptly
•Robustness: System survives misbehaving processes
•Real-time capable: Can bound response latency
•Multi-user suitable: Fair sharing among users

Preemptive Disadvantages

•Complex kernel: Must handle arbitrary interruption
•Synchronization overhead: Locks needed everywhere
•Context switch cost: Timer interrupts consume cycles
•Cache pollution: Frequent switches reduce cache effectiveness
•Non-deterministic timing: Harder to analyze timing behavior

The overhead quantified:

Context switch overhead on modern systems:

Register save/restore: ~0.5-1 microseconds
Cache/TLB pollution: 10-100 microseconds of degraded performance
Timer interrupt handling: ~1-5 microseconds per interrupt

With 1000 timer interrupts per second (1ms quantum) and 100 context switches per second:

Direct overhead: ~150 microseconds/second = 0.015%
Cache effects: ~10 milliseconds/second = 1%
Total practical overhead: 1-2% of CPU time

For most workloads, this overhead is overwhelmingly justified by the benefits of fairness and responsiveness.

The Historical Verdict

Historical Context and Evolution

The evolution from non-preemptive to preemptive scheduling mirrors the evolution of computing itself—from single-user batch systems to multi-user interactive systems.

Era 1: Early batch systems (1950s-1960s)

The first operating systems were non-preemptive by necessity:

Single-user systems running one job at a time
No concept of "interactive response"
Jobs ran to completion; next job started when previous finished
Simple, but horrific resource utilization during I/O waits

Era 2: Multiprogramming (1960s-1970s)

To improve CPU utilization, multiprogramming was introduced:

Multiple jobs loaded in memory simultaneously
When one job blocked on I/O, another could run
Still non-preemptive: running job kept CPU until it blocked
Example: IBM OS/360 MFT (Multiprogramming with Fixed Tasks)

Era 3: Time-sharing (1960s-1980s)

Interactive computing demanded preemption:

Multiple users sharing a single computer via terminals
Each user needed responsive interaction (sub-second response)
Preemptive scheduling essential: couldn't wait for batch job to finish
Examples: CTSS, Multics, Unix

Historical Operating Systems: Scheduling Type
System	Era	Type	Notes
IBM OS/360 (batch)	1960s	Non-preemptive	Jobs ran to completion or block
CTSS	1961	Preemptive	First time-sharing system
Multics	1960s-70s	Preemptive	Influenced Unix design
Classic Mac OS (1-9)	1984-2001	Cooperative	Last major cooperative consumer OS
Windows 3.x	1990-1994	Cooperative	16-bit Windows applications
Windows 95/NT	1993-1995	Preemptive	Transition to preemptive
Mac OS X	2001	Preemptive	Replaced cooperative Classic Mac OS
Linux	1991-present	Preemptive	Always preemptive

The Classic Mac OS story:

Classic Mac OS (versions 1-9, 1984-2001) is notable as the last major consumer operating system to use cooperative scheduling. This choice had significant consequences:

Advantage: Simpler programming model, lower overhead
Consequence: One misbehaving application froze the entire system
User experience: The infamous "spinning beach ball" with no way to recover except restart
Ultimate fate: Replaced by Mac OS X (based on preemptive Unix/Mach)

Windows had a similar journey—Windows 3.x was cooperative for 16-bit programs, but Windows NT (1993) and Windows 95 (1995) introduced preemptive scheduling.

Why Cooperative Lasted So Long

Modern Applications of Non-preemptive Scheduling

While preemptive scheduling dominates general-purpose OSes, non-preemptive (cooperative) scheduling remains valuable in specific contexts where its advantages outweigh its risks.

User-space cooperative threading (green threads/fibers):

Many modern languages and runtimes implement cooperative scheduling within a preemptively scheduled process:

cooperative_examples.py
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
# Python asyncio: Cooperative scheduling of coroutines
# Within the async runtime, tasks yield cooperatively at 'await' points
# But the OS can still preempt the entire Python process
 
import asyncio
 
async def task_a():
    print("Task A starting")
    await asyncio.sleep(1)  # Cooperative yield point
    print("Task A resuming")
    await asyncio.sleep(1)  # Another yield point
    print("Task A done")
 
async def task_b():
    print("Task B starting")
    await asyncio.sleep(0.5)  # Yields to other tasks
    print("Task B done")
 
async def main():
    # Both tasks run "concurrently" via cooperative scheduling
    await asyncio.gather(task_a(), task_b())
 
# This is cooperative scheduling:
# - Tasks voluntarily yield at 'await'
# - No timer-based preemption within the event loop
# - A task that never awaits blocks all others
 
# BUT the entire Python process is preemptively scheduled by the OS
# So a misbehaving asyncio program doesn't freeze the system
 
asyncio.run(main())

Modern Cooperative Scheduling Examples

•Go goroutines: Cooperatively scheduled by Go runtime; OS preempts the runtime itself
•Python asyncio: Coroutines yield at await points; used for I/O-bound concurrency
•JavaScript event loop: Single-threaded cooperative scheduling; async/await for yielding
•Rust async/await: Futures polled cooperatively by async runtimes like tokio
•Game engines: Game loop often uses cooperative task scheduling for AI, physics, etc.

Embedded and real-time systems:

Simple embedded systems often use cooperative scheduling:

Microcontrollers: Resource-constrained devices where timer interrupts add unacceptable overhead
Super loops: Main loop polls each subsystem in sequence; each "yields" by returning
Cooperative RTOS: Some lightweight RTOSes (e.g., FreeRTOS in cooperative mode) support optional non-preemptive operation

Why it works in these contexts:

All code is trusted: Embedded developer controls all software
Predictable execution: Easier to analyze timing for real-time guarantees
Minimal overhead: Critical when CPU cycles are precious
Simple debugging: No race conditions from unexpected preemption

The Hybrid Pattern

Kernel Preemption: A Deeper Layer

Our discussion so far has focused on user-space preemption—can the OS preempt user processes? But there's another level: kernel preemption—can the OS preempt code running in kernel mode?

The distinction:

User preemption: Always enabled in preemptive systems—OS can interrupt user code anytime
Kernel preemption: Whether the kernel can be interrupted while executing kernel code (system calls, interrupt handlers)

Why kernel preemption is harder:

Kernel code manipulates shared data structures (process tables, file systems, device state). If preempted mid-operation, another process might see inconsistent state:

kernel_preemption_problem.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
// Problem: Kernel preemption during critical operation
 
// Process A is in kernel mode, allocating a page
void allocate_page_frame() {
    struct page *page = get_free_page();  // Gets page 0x1000
    
    // PREEMPTION HAPPENS HERE
    // Process B runs, also allocates a page
    // B gets the SAME page 0x1000 (still marked free!)
    
    page->owner = current_process;  // A marks it as owned
    page->flags = PAGE_PRESENT;
    add_to_page_table(current_process, page);
    
    // Both A and B now think they own page 0x1000
    // Data corruption guaranteed
}
 
// Solution 1: Non-preemptive kernel
// System calls run to completion; no preemption during kernel mode
// Simple but hurts latency
 
// Solution 2: Preemptive kernel with locks
void allocate_page_frame_safe() {
    spin_lock(&page_allocator_lock);  // Disable preemption in critical section
    
    struct page *page = get_free_page();
    page->owner = current_process;
    page->flags = PAGE_PRESENT;
    add_to_page_table(current_process, page);
    
    spin_unlock(&page_allocator_lock);  // Re-enable preemption
}

Kernel preemption in major operating systems:

OS	Kernel Preemptibility	Notes
Linux (default)	Preemptible	Can preempt kernel code except in critical sections
Linux PREEMPT_RT	Fully preemptible	Even spinlocks are preemptible for real-time
Windows NT	Preemptible	Kernel-mode APCs can preempt kernel code
macOS/XNU	Partly preemptible	Mach microkernel portions preemptible
FreeBSD	Optional	PREEMPTION kernel option

Linux preemption models:

PREEMPT_NONE: No kernel preemption (server workloads—maximum throughput)
PREEMPT_VOLUNTARY: Explicit preemption points (traditional desktop)
PREEMPT: Full preemption except spinlock-held regions (low-latency desktop)
PREEMPT_RT: Real-time patches—spinlocks become mutex, almost fully preemptible

Latency Implications

Summary: Preemptive vs Non-preemptive

The choice between preemptive and non-preemptive scheduling is foundational to operating system design. Let's consolidate the key insights:

Key Takeaways

•Non-preemptive scheduling relies on processes voluntarily yielding; simple but vulnerable to misbehavior.
•Preemptive scheduling uses timer interrupts to forcibly reclaim the CPU; complex but robust.
•Scheduling decision points differ: non-preemptive only on block/yield/exit; preemptive adds timer expiry and priority changes.
•Preemption won for general-purpose OSes due to fairness, responsiveness, and robustness benefits outweighing 1-2% overhead.
•Cooperative scheduling survives in user-space runtimes (asyncio, goroutines) and simple embedded systems where trust is guaranteed.
•Kernel preemption adds another layer—whether kernel code itself can be interrupted—affecting system latency.

What's next:

Page Complete

3 / 5