Evaluating Scheduling Metrics
In CPU scheduling, we have seen many different algorithms (FCFS, SJF, Round Robin, etc.). But how do we decide which one is actually "better" for a given set of processes?
We evaluate algorithms based on specific performance criteria. Two of the absolute most critical metrics you must master are Turnaround Time and Waiting Time.
Real-Life Example
Imagine ordering food at a fast-food restaurant. You arrive at 12:00 PM (Arrival Time) and place an order that takes exactly 5 minutes to cook (Burst Time).
If there are many people ahead of you, you might stand around doing absolutely nothing for 10 minutes (Waiting Time) before the chefs even start your order. Your food is finally handed to you at 12:15 PM (Completion Time).
Your Turnaround Time (total time from arrival to getting your food) is 15 minutes. Your Waiting Time (time spent doing nothing) is 10 minutes. If we use our formula: 15 (Turnaround) - 5 (Burst) = 10 (Wait). The math works perfectly!
Example 1: Calculating Metrics for Non-Preemptive Scheduling
Let's do a deep dive calculation using a non-preemptive algorithm like Shortest Job First (SJF). Remember, once a process starts, it doesn't stop.
| Process | Arrival Time (ms) | Burst Time (ms) |
|---|---|---|
| P1 | 0 | 6 |
| P2 | 2 | 2 |
| P3 | 4 | 1 |
| P4 | 5 | 3 |
Using SJF:
1. At 0, P1 starts and runs until time 6.
2. At 6, P2, P3, and P4 are all waiting. The shortest is P3 (Burst 1). P3 runs until 7.
3. At 7, P2 and P4 remain. The shortest is P2 (Burst 2). P2 runs until 9.
4. At 9, P4 runs until 12.
Here is the Gantt chart:
+---------+--+----+------+
| P1 |P3| P2 | P4 |
+---------+--+----+------+
0 6 7 9 12Now, let's strictly apply the formulas to find the Turnaround Time (Completion - Arrival):
- P1 Completion = 6. Turnaround = 6 - 0 = 6 ms.
- P2 Completion = 9. Turnaround = 9 - 2 = 7 ms.
- P3 Completion = 7. Turnaround = 7 - 4 = 3 ms.
- P4 Completion = 12. Turnaround = 12 - 5 = 7 ms.
Average Turnaround Time = (6 + 7 + 3 + 7) / 4 = 5.75 ms.
Next, we use those results to find the Waiting Time (Turnaround - Burst):
- P1 Wait = 6 - 6 = 0 ms.
- P2 Wait = 7 - 2 = 5 ms.
- P3 Wait = 3 - 1 = 2 ms.
- P4 Wait = 7 - 3 = 4 ms.
Average Waiting Time = (0 + 5 + 2 + 4) / 4 = 2.75 ms.
Example 2: The Complexity of Preemptive Scheduling
Calculating waiting time in a preemptive algorithm (like Round Robin) is notoriously tricky because a single process can start, get paused, wait, start again, get paused again, etc. Trying to add up all those little waiting gaps manually often leads to calculation errors.
This is why the formula Wait = Turnaround - Burst is a lifesaver! Let's see it in action using Round Robin (Time Quantum = 2).
| Process | Arrival Time (ms) | Burst Time (ms) |
|---|---|---|
| P1 | 0 | 5 |
| P2 | 1 | 4 |
Using Round Robin (TQ=2):
1. 0-2: P1 runs.
2. 2-4: P2 runs.
3. 4-6: P1 runs.
4. 6-8: P2 runs (and finishes its 4 ms total burst!).
5. 8-9: P1 runs its final 1 ms (and finishes).
Here is the fragmented Gantt chart:
+----+----+----+----+--+
| P1 | P2 | P1 | P2 |P1|
+----+----+----+----+--+
0 2 4 6 8 9Notice how P1 is spread across three different execution blocks! Instead of trying to add up the gaps, we just find the Completion Time by looking at the very right side of the Gantt chart.
Turnaround Time (Completion - Arrival):
- P1 completes at 9. Turnaround = 9 - 0 = 9 ms.
- P2 completes at 8. Turnaround = 8 - 1 = 7 ms.
Average Turnaround Time = (9 + 7) / 2 = 8 ms.
Waiting Time (Turnaround - Burst):
- P1 Wait = 9 - 5 = 4 ms.
- P2 Wait = 7 - 4 = 3 ms.
Average Waiting Time = (4 + 3) / 2 = 3.5 ms.
Using the formulas makes complex preemptive scheduling calculations incredibly simple!
Why Do We Care About These Metrics?
- Turnaround Time represents the total time it takes to execute a process from submission to completion. This directly represents the end-user's experience (how long they had to wait for a result).
- Waiting Time directly isolates and measures the efficiency of the scheduling algorithm itself. CPU execution time is fixed (a process takes what it takes to run), but Waiting Time is entirely dependent on how good the OS is at ordering tasks.
- Because of this, minimizing Average Waiting Time is the primary goal of almost all CPU scheduling algorithm optimizations.
Calculate the Metrics
Question 1 of 1Test your mastery of the Golden Formulas.