๐ค Process Scheduling Algorithms: A Deep Dive into Preemptive vs. Non-Preemptive
Summary
Master the core of operating systems: process scheduling. Understand the principles of preemptive (SRT, Round Robin) and non-preemptive (FIFO, SJF, HRN) algorithms, and sharpen your skills with practice problems on calculating average waiting and turnaround times.
๐ฆ Why Do We Need Process Scheduling?
A computer needs to handle multiple processes simultaneously. The rule that decides which process gets assigned the CPU is called process scheduling. The goal of scheduling is to use the CPU efficiently, give fair opportunities to all processes, and minimize user waiting time.
Scheduling methods are broadly divided into two types: Non-preemptive and Preemptive.
- Non-preemptive Scheduling: Once a process is allocated the CPU, no other process can take it away until the process finishes or voluntarily releases the CPU for an I/O operation.
- Preemptive Scheduling: The operating system can forcibly interrupt the currently running process and allocate the CPU to another process if deemed necessary. This is suitable for time-sharing systems.
๐ก Try calculating the average waiting time and average turnaround time yourself using the example problems provided with each algorithm description below!
๐ซ Non-preemptive Scheduling
Once allocated, no one can stop it until it's done.
1. FIFO (First-In, First-Out) or FCFS (First-Come, First-Served)
The simplest method, allocating the CPU in the order that processes arrive in the Ready Queue.
- Pros: Easy to implement and fair.
- Cons: If a long process arrives first, subsequent short processes have to wait indefinitely, causing the Convoy Effect.
2. SJF (Shortest Job First)
Allocates the CPU to the process with the shortest execution time.
- Pros: The optimal algorithm for minimizing average waiting time.
- Cons: Long processes can be indefinitely postponed by new short processes, leading to Starvation. It's also difficult to predict the exact execution time of each process in advance.
3. HRN (Highest Response-ratio Next)
Developed to compensate for the starvation problem of SJF. It dynamically determines priority by considering both waiting time and execution time.
- Priority Calculation:
(Waiting Time + Burst Time) / Burst Time
- Characteristic: The CPU is allocated to the process with the highest value. As waiting time increases, so does the priority, thus preventing starvation.
4. Deadline
Used in real-time systems where a process must be completed within a given deadline. Processes with the nearest deadline are given higher priority.
5. Priority
The CPU is allocated based on a static priority assigned to each process. The process with the highest priority runs first. Like SJF, it can cause starvation.
๐ Preemptive Scheduling
A flexible approach that can stop a running process at any time to hand the CPU over to another process.
1. SRT (Shortest Remaining Time)
A preemptive version of the SJF algorithm. If a new process arrives with a shorter execution time than the remaining time of the current process, the CPU is immediately taken away and given to the new process.
- Pros: Can further reduce average waiting time.
- Cons: Frequent context switching can cause overhead, and starvation can still occur.
2. Round Robin (RR)
An approach that adds a time quantum (or time slice) to FIFO. Each process uses the CPU for a fixed amount of time, and if the time is up, it moves to the back of the ready queue.
- Pros: Suitable for interactive systems as all processes are guaranteed fair CPU time.
- Cons: If the time quantum is too large, it becomes like FIFO. If it's too small, context switching becomes too frequent, increasing overhead. Setting an appropriate time quantum is crucial.
๐ Practice Problems
Problem | When the following processes arrive at the ready queue in order, calculate the average waiting time and average turnaround time using SJF (Non-preemptive) scheduling. | Process | Arrival Time | Burst Time | | :--- | :---: | :---: | | P1 | 0 | 6 | | P2 | 1 | 3 | | P3 | 2 | 4 | | P4 | 3 | 2 | |
Your Answer | |
Correct Answer | Reveal Answer |
Solution (SJF)
-
Determine Execution Order:
- Time 0: P1 arrives. Executes (Burst time 6).
- Since it's non-preemptive, P1 runs to completion (Finish time 6).
- At time 6: P2, P3, P4 have all arrived. Compare their burst times (P2:3, P3:4, P4:2).
- P4 executes (Burst time 2, Finish time 8).
- P2 executes (Burst time 3, Finish time 11).
- P3 executes (Burst time 4, Finish time 15).
- Execution Order: P1 -> P4 -> P2 -> P3
-
Calculate Waiting/Turnaround Time:
- Turnaround Time = Finish Time - Arrival Time
- Waiting Time = Turnaround Time - Burst Time
Process | Arrival | Burst | Finish | Turnaround | Waiting |
---|---|---|---|---|---|
P1 | 0 | 6 | 6 | 6 | 0 |
P2 | 1 | 3 | 11 | 10 | 7 |
P3 | 2 | 4 | 15 | 13 | 9 |
P4 | 3 | 2 | 8 | 5 | 3 |
Total | 34 | 19 |
- Calculate Average:
- Average Waiting Time: 19 / 4 = 4.75
- Average Turnaround Time: 34 / 4 = 8.5
Problem | Under the same conditions, calculate the average waiting time and average turnaround time using SRT (Preemptive) scheduling. |
Your Answer | |
Correct Answer | Reveal Answer |
Solution (SRT)
-
Determine Execution Order (Timeline):
- 0: P1 arrives. P1 runs (Remaining time 6).
- 1: P2 arrives (Burst 3). Shorter than P1's remaining time (5), so preempt P1. P2 runs.
- 2: P3 arrives (Burst 4). Longer than P2's remaining time (2), so P2 continues.
- 3: P4 arrives (Burst 2). Longer than P2's remaining time (1), so P2 continues.
- 4: P2 finishes. Remaining processes: P1(5), P3(4), P4(2). P4 runs.
- 6: P4 finishes. Remaining processes: P1(5), P3(4). P3 runs.
- 10: P3 finishes. Remaining process: P1(5). P1 runs.
- 15: P1 finishes.
- Execution Trace: P1(1) -> P2(3) -> P4(2) -> P3(4) -> P1(5)
-
Calculate Waiting/Turnaround Time:
- P1: Finish 15, Arrival 0, Burst 6 -> Turnaround 15, Waiting 9
- P2: Finish 4, Arrival 1, Burst 3 -> Turnaround 3, Waiting 0
- P3: Finish 10, Arrival 2, Burst 4 -> Turnaround 8, Waiting 4
- P4: Finish 6, Arrival 3, Burst 2 -> Turnaround 3, Waiting 1
Process | Arrival | Burst | Finish | Turnaround | Waiting |
---|---|---|---|---|---|
P1 | 0 | 6 | 15 | 15 | 9 |
P2 | 1 | 3 | 4 | 3 | 0 |
P3 | 2 | 4 | 10 | 8 | 4 |
P4 | 3 | 2 | 6 | 3 | 1 |
Total | 29 | 14 |
- Calculate Average:
- Average Waiting Time: 14 / 4 = 3.5
- Average Turnaround Time: 29 / 4 = 7.25
Problem | Under the same conditions, calculate the average waiting time and average turnaround time using Round Robin (RR, Time Quantum=2) scheduling. |
Your Answer | |
Correct Answer | Reveal Answer |
Solution (Round Robin, Quantum=2)
-
Determine Execution Order (Queue Changes):
- 0: [P1] -> P1 runs (2)
- 2: [P2, P3, P1] -> P2 runs (2)
- 4: [P4, P1, P2] -> P4 runs (2) -> P4 finishes
- 6: [P1, P2, P3] -> P1 runs (2)
- 8: [P2, P3, P1] -> P2 runs (1) -> P2 finishes
- 9: [P3, P1] -> P3 runs (2)
- 11: [P1, P3] -> P1 runs (2) -> P1 finishes
- 13: [P3] -> P3 runs (2) -> P3 finishes
- Finish Order: P4(6) -> P2(9) -> P1(13) -> P3(15)
-
Calculate Waiting/Turnaround Time:
Process | Arrival | Burst | Finish | Turnaround | Waiting |
---|---|---|---|---|---|
P1 | 0 | 6 | 13 | 13 | 7 |
P2 | 1 | 3 | 9 | 8 | 5 |
P3 | 2 | 4 | 15 | 13 | 9 |
P4 | 3 | 2 | 6 | 3 | 1 |
Total | 37 | 22 |
- Calculate Average:
- Average Waiting Time: 22 / 4 = 5.5
- Average Turnaround Time: 37 / 4 = 9.25