Introduction
Process scheduling in an operating system determines how CPU time is allocated among different processes. There are two primary types of CPU scheduling:
- Preemptive Scheduling – The CPU can be taken away from a running process before it completes.
- Non-Preemptive Scheduling – A running process keeps the CPU until it voluntarily releases it.
Understanding these two types is crucial for designing an efficient and fair scheduling system.
1. What is Preemptive Scheduling?
Definition
Preemptive scheduling allows the operating system to interrupt a running process and assign the CPU to another process before the current process finishes execution.
How it Works
- The OS preempts (forces) the running process to move to the Ready queue.
- A higher-priority or more urgent process gets the CPU.
- The preempted process waits until the CPU is available again.
Example of Preemptive Scheduling
Suppose three processes are in the system:
| Process | Arrival Time | Burst Time | Priority |
|---|---|---|---|
| P1 | 0 ms | 10 ms | 2 |
| P2 | 2 ms | 5 ms | 1 (higher) |
| P3 | 4 ms | 8 ms | 3 |
- P1 starts executing at 0 ms.
- At 2 ms, P2 arrives and has a higher priority than P1.
- The OS preempts P1 and assigns the CPU to P2.
- After P2 finishes, P1 resumes execution.
This ensures high-priority tasks get CPU time immediately.
Advantages of Preemptive Scheduling
✔ Better CPU Utilization – Ensures no process keeps the CPU idle for too long.
✔ Faster Response Time – Important for real-time systems and multitasking environments.
✔ Fairness – High-priority and short jobs do not get stuck waiting behind long processes.
Disadvantages of Preemptive Scheduling
✖ More Overhead – Frequent switching causes context switching overhead.
✖ Complex Implementation – The OS must track process states efficiently.
✖ Starvation – Low-priority processes may get delayed indefinitely.
2. What is Non-Preemptive Scheduling?
Definition
In non-preemptive scheduling, a process that starts execution keeps the CPU until it voluntarily releases it (i.e., it completes execution or enters an I/O wait).
How it Works
- The OS does not interrupt a running process.
- A process runs until it terminates or moves to the waiting state (e.g., waiting for I/O).
- Once a process is finished or blocked, the CPU is assigned to the next ready process.
Example of Non-Preemptive Scheduling
Using the same example:
| Process | Arrival Time | Burst Time |
|---|---|---|
| P1 | 0 ms | 10 ms |
| P2 | 2 ms | 5 ms |
| P3 | 4 ms | 8 ms |
- P1 starts at 0 ms and runs for 10 ms.
- Even though P2 and P3 arrive earlier, they must wait until P1 finishes.
- Only after P1 completes, P2 gets CPU time.
Advantages of Non-Preemptive Scheduling
✔ Less Overhead – No need for context switching.
✔ Simple Implementation – Easier to design and manage.
✔ No Starvation – Once a process starts, it will complete without interruption.
Disadvantages of Non-Preemptive Scheduling
✖ Poor CPU Utilization – Long processes can block shorter or urgent ones.
✖ High Response Time – Important jobs may have to wait for long-running processes.
✖ Less Fair – A single process can dominate CPU time, delaying others.
3. Key Differences Between Preemptive and Non-Preemptive Scheduling
| Feature | Preemptive Scheduling | Non-Preemptive Scheduling |
|---|---|---|
| Process Control | The OS can interrupt a process before completion. | The process runs until it finishes or enters I/O. |
| CPU Utilization | More efficient, as short and high-priority tasks get CPU sooner. | Less efficient, as long tasks can block others. |
| Context Switching | Frequent switching leads to higher overhead. | No switching during execution, reducing overhead. |
| Fairness | Ensures fair execution for all processes. | Some processes may suffer long waiting times. |
| Complexity | More complex to implement. | Simpler and easier to manage. |
| Starvation | Possible if low-priority processes keep getting preempted. | No starvation, but long processes can slow the system. |
| Best For | Multitasking, real-time OS, time-sharing. | Batch processing, simple OS, low-overhead systems. |
4. Examples of Scheduling Algorithms
Preemptive Scheduling Algorithms
- Round Robin (RR) – Each process gets a fixed time slice before switching.
- Priority Scheduling (Preemptive Version) – High-priority processes preempt low-priority ones.
- Shortest Remaining Time First (SRTF) – Process with the smallest remaining execution time runs first.
Non-Preemptive Scheduling Algorithms
- First Come First Serve (FCFS) – Processes execute in order of arrival.
- Shortest Job Next (SJN) – The shortest job executes first, but no preemption.
- Priority Scheduling (Non-Preemptive Version) – High-priority processes execute first but cannot preempt running processes.
5. When to Use Each Scheduling Type
Use Preemptive Scheduling When:
✔ Real-time processing is needed (e.g., medical devices, financial transactions).
✔ Short tasks should be executed quickly (e.g., user applications in OS).
✔ Time-sharing and multitasking are required (e.g., Windows, Linux).
Use Non-Preemptive Scheduling When:
✔ Simplicity and low overhead are more important than responsiveness.
✔ Processes need to finish in the same order they arrive (e.g., batch processing).
✔ Starvation must be avoided (e.g., embedded systems with limited resources).
6. Conclusion
- Preemptive Scheduling is best for multitasking and real-time systems but requires more overhead.
- Non-Preemptive Scheduling is simpler and ensures process completion but can lead to inefficiencies.
- The choice of scheduling type depends on system requirements and workload characteristics.