1. Introduction
CPU scheduling algorithms can be broadly classified into two major categories based on whether the operating system is allowed to interrupt a running process:
Non-Preemptive Scheduling
Preemptive Scheduling
This distinction is one of the most fundamental concepts in process scheduling because it determines how CPU control is shared among processes.
The key question is:
Once a process starts executing, can the operating system forcibly take the CPU away from it?
If the answer is No, the scheduling algorithm is non-preemptive.
If the answer is Yes, the scheduling algorithm is preemptive.
The choice between preemptive and non-preemptive scheduling significantly affects:
System responsiveness
CPU utilization
Fairness
Scheduling overhead
Context-switch frequency
Modern interactive operating systems generally favor preemptive scheduling because it provides better responsiveness, while simpler systems often use non-preemptive scheduling because of its lower overhead and simpler implementation.
2. Non-Preemptive Scheduling
2.1 Definition
In Non-Preemptive Scheduling, once a process is allocated the CPU, it continues execution until one of the following occurs:
The process completes execution.
The process voluntarily releases the CPU (usually for an I/O operation).
The process terminates.
The operating system cannot forcibly interrupt a running process simply because another process has arrived.
Therefore:
CPU ownership remains with the running process until it decides to give it up.
This approach gives processes uninterrupted CPU access during execution.
2.2 Working Mechanism
When the CPU becomes available:
Scheduler selects a process.
CPU is allocated.
Process executes continuously.
Process completes or blocks.
Scheduler selects another process.
Conceptual Flow
Ready Queue
[P1] [P2] [P3]
Execution:
P1 → P2 → P3
Once P1 starts:
P2 Cannot Interrupt
P3 Cannot Interrupt
The CPU remains with P1 until completion.
Key Behavior
P1 Starts
↓
Runs Completely
↓
P2 Starts
↓
Runs Completely
↓
P3 Starts
No forced interruption occurs.
2.3 Examples
Several well-known scheduling algorithms are non-preemptive.
First Come First Serve (FCFS)
Processes execute according to arrival order.
Non-Preemptive Shortest Job First (SJF)
Shortest available job executes completely.
Non-Preemptive Priority Scheduling
Highest-priority process executes until completion.
These algorithms only make scheduling decisions when the CPU becomes free.
2.4 Advantages
Simple Implementation
The scheduler performs fewer decisions.
No timer interrupts are required.
Implementation is straightforward.
Low Overhead
Because processes are rarely interrupted:
Fewer context switches occur.
Less CPU time is spent on scheduling.
This improves efficiency.
Predictable Execution
Once a process begins execution:
Start Time Known
↓
Completion Predictable
This can simplify system analysis.
Better Cache Utilization
Long uninterrupted execution often improves:
CPU cache performance
Memory locality
which may improve throughput.
2.5 Disadvantages
Poor Responsiveness
A newly arrived process must wait until the current process finishes.
Example:
Long Process Running
↓
User Process Arrives
↓
Must Wait
The user experiences delays.
Convoy Effect
A long process at the front of the queue delays all other processes.
Example:
P1 = 100 units
P2 = 2 units
P3 = 1 unit
Execution:
P1 → P2 → P3
Short jobs suffer excessive waiting.
Not Suitable for Interactive Systems
Interactive systems require:
Quick responses
Frequent CPU sharing
Non-preemptive scheduling cannot provide this efficiently.
CPU Monopolization
A CPU-bound process may occupy the processor for a very long period.
Other processes receive no CPU until it finishes.
3. Preemptive Scheduling
3.1 Definition
In Preemptive Scheduling, the operating system has the authority to interrupt a running process and allocate the CPU to another process.
This means:
CPU ownership belongs to the operating system, not the process.
Whenever scheduling conditions require it, the OS may suspend the running process and switch to another one.
The interrupted process is not terminated.
Its execution state is saved and it can resume later.
Preemptive scheduling is the foundation of modern:
Time-sharing systems
Interactive operating systems
Real-time systems
3.2 Working Mechanism
When a process is running:
OS monitors scheduling events.
A scheduling condition occurs.
Current process is interrupted.
Context switch is performed.
Another process receives the CPU.
Conceptual Flow
P1 Running
↓
Interrupt
↓
P2 Running
↓
Interrupt
↓
P3 Running
The scheduler may reassign CPU ownership many times before any process completes.
Key Behavior
P1 Running
↓
Preempted
↓
P2 Running
↓
Preempted
↓
P3 Running
CPU allocation becomes dynamic.
3.3 Examples
Many modern scheduling algorithms are preemptive.
Round Robin (RR)
Time quantum expiration triggers preemption.
Shortest Remaining Time First (SRTF)
Shorter jobs can preempt longer jobs.
Preemptive Priority Scheduling
Higher-priority processes can preempt lower-priority processes.
These algorithms continuously reevaluate scheduling decisions.
3.4 Advantages
Better Responsiveness
Interactive processes receive CPU quickly.
Example:
User Clicks Button
↓
Immediate CPU Access
The system feels responsive.
Suitable for Interactive Systems
Preemptive scheduling enables:
Time sharing
Multitasking
Multi-user operation
Prevents CPU Monopolization
No process can hold the CPU indefinitely.
Example:
Long Process Running
↓
Quantum Expires
↓
CPU Reallocated
This improves fairness.
Improved Resource Sharing
CPU time is distributed more evenly among competing processes.
3.5 Disadvantages
Higher Context-Switch Overhead
Every preemption requires:
Saving process state
Loading another process state
This consumes CPU resources.
Increased Complexity
The scheduler must:
Handle interrupts
Manage timers
Perform frequent decisions
Implementation becomes more complex.
Possible Starvation
Some preemptive algorithms may repeatedly favor certain processes.
Examples:
SRTF
Priority Scheduling
Long-running or low-priority processes may starve.
Cache Performance Impact
Frequent switching may:
Flush caches
Reduce locality
which can decrease efficiency.
4. Key Differences
| Feature | Non-Preemptive | Preemptive |
|---|---|---|
| CPU Control | Process holds CPU | OS controls CPU |
| Interrupt Running Process | No | Yes |
| Responsiveness | Low | High |
| Context Switching | Rare | Frequent |
| Overhead | Low | High |
| Complexity | Low | High |
| Fairness | Lower | Higher |
| Interactive Support | Poor | Excellent |
| CPU Sharing | Limited | Better |
5. When Does Preemption Occur?
In preemptive scheduling, CPU reassignment may occur because of several events.
Time Quantum Expiration
Used by Round Robin.
Quantum Ends
↓
Context Switch
Arrival of Higher-Priority Process
Used in Priority Scheduling.
Higher Priority Arrives
↓
Preemption
Arrival of Shorter Job
Used in SRTF.
Shorter Remaining Time
↓
Preemption
Hardware Interrupt
External events may require immediate OS intervention.
Interrupt
↓
Scheduler Activated
System Calls
Some system calls may trigger scheduling decisions.
6. Performance Trade-offs
The choice between preemptive and non-preemptive scheduling involves trade-offs.
| Aspect | Non-Preemptive | Preemptive |
|---|---|---|
| CPU Efficiency | High | Lower |
| Context-Switch Overhead | Low | High |
| Responsiveness | Poor | Good |
| Fairness | Lower | Higher |
| Implementation Simplicity | High | Lower |
| Resource Sharing | Limited | Better |
Fundamental Trade-off
Non-Preemptive
↓
Less Overhead
↓
Poor Responsiveness
Preemptive
↓
Better Responsiveness
↓
Higher Overhead
Operating systems must balance these competing objectives.
7. Practical Use Cases
Non-Preemptive Scheduling
Best suited for:
Batch Processing Systems
Examples:
Payroll processing
Report generation
Offline computations
Simple Embedded Systems
Systems with predictable workloads.
Educational Operating Systems
Used to simplify implementation and teaching.
Preemptive Scheduling
Best suited for:
Time-Sharing Systems
Multiple users share CPU resources.
Interactive Systems
Examples:
Desktop operating systems
Mobile operating systems
Real-Time Systems
Certain tasks require immediate CPU access.
Server Environments
Large numbers of concurrent requests require fair sharing.
8. Key Insight
The most important distinction is:
Non-preemptive scheduling prioritizes simplicity and low overhead, while preemptive scheduling prioritizes responsiveness and fairness.
In practice:
Responsiveness ↑
↓
Preemption Required
and
Overhead ↓
↓
Non-Preemptive Preferred
Thus scheduling design always involves balancing responsiveness against efficiency.
9. Relationship with Scheduling Algorithms
| Algorithm | Type |
|---|---|
| FCFS | Non-Preemptive |
| SJF | Non-Preemptive |
| SRTF | Preemptive |
| Priority Scheduling | Both |
| Round Robin | Preemptive |
| Multilevel Queue | Can Be Either |
| Multilevel Feedback Queue | Usually Preemptive |
Classification Summary
Non-Preemptive Algorithms
FCFS
SJF
Non-Preemptive Priority
Preemptive Algorithms
Round Robin
SRTF
Preemptive Priority
MLFQ
Both Variants Possible
Priority Scheduling
Multilevel Queue Scheduling