Scheduling Criteria
Scenario
You are managing a popular coffee shop, but customers are constantly complaining. To fix the issue, you first need to define what 'good service' actually means.
Mental model
Scheduling criteria are the key performance indicators (KPIs) for evaluating a CPU scheduler.
Just like a restaurant might measure its success by how many tables it serves per hour (throughput), how long customers wait for their food (waiting time), or how quickly they get greeted (response time), an operating system uses specific criteria to judge how well its CPU scheduling algorithm is performing.
Explanation
Before we can design or compare CPU scheduling algorithms, we need a standard set of metrics to evaluate them. Without clear criteria, it is impossible to say whether one algorithm is objectively 'better' than another, because 'better' depends entirely on the system's goals. A personal laptop has very different goals than a batch-processing supercomputer.
To understand these metrics, imagine a process moving through the system. When a user launches a program, it arrives in the ready queue. The time it spends sitting there, doing absolutely nothing while waiting for the CPU, is its waiting time. If the process gets interrupted and put back in the queue later, all those waiting periods add up. Our goal is almost always to minimize this total waiting time.
Once the process finally gets the CPU for the first time and starts producing output, the time elapsed from its arrival to that very first response is its response time. This is critical in interactive systems; if you click a button, you expect a visual response immediately, even if the underlying computation takes longer to finish. Meanwhile, the turnaround time is the entire lifecycle: from the exact moment of arrival until the process completely finishes and exits the system. Turnaround time includes waiting time, execution time, and any I/O delays.
From the system's broader perspective, we also care about overall efficiency rather than just individual process times. CPU utilization measures how busy the processor is. Since the CPU is the most expensive component, we want to keep it running close to 100% of the time, rather than sitting idle. Similarly, throughput measures the total number of processes completed per unit of time. If a scheduling algorithm spends too much time context switching, throughput drops because the system is busy doing administrative work instead of real computation.
In reality, no single scheduling algorithm can optimize all these criteria simultaneously. Minimizing response time often requires frequent context switching, which hurts throughput and CPU utilization. Therefore, OS designers must prioritize certain metrics based on the environment. A desktop OS prioritizes response time for a snappy user experience, while a scientific computing cluster prioritizes throughput and CPU utilization to crunch maximum data.
Key points
- CPU Utilization: The percentage of time the CPU is actively executing user processes instead of sitting idle.
- Throughput: The number of processes that complete their execution per time unit.
- Turnaround Time: The total amount of time taken to execute a particular process, from submission to termination.
- Waiting Time: The total amount of time a process spends waiting in the ready queue.
- Response Time: The time from the submission of a request until the first response is produced.
Common mistakes
- Confusing waiting time with turnaround time: Waiting time ONLY counts the time spent in the ready queue. Turnaround time is the total time (Waiting Time + Execution Time + I/O Time).
- Thinking response time is when the process finishes: Response time is strictly the time until the system STARTS responding to the request, not when it finishes it. It's crucial for interactive applications.
Glossary
- CPU utilization
- A measure of how busy the computer's main processor is kept, with the goal being to keep it working as close to 100% of the time as possible.
- throughput
- The total number of complete programs or tasks the computer manages to finish from start to end within a given time period.
- turnaround time
- The total amount of time it takes from the moment you tell a program to run until the moment it completely finishes its job.
Recall questions
- Which scheduling criterion is most important for an interactive system like a desktop OS?
- What is the difference between turnaround time and waiting time?
- If a system performs excessive context switching, which metric suffers the most directly?
Questions & answers
A process arrives at time 0, waits for 5ms, executes for 10ms, and completes. What is its turnaround time?
15ms
Approach: Turnaround time = Completion time - Arrival time = 15 - 0 = 15ms. Alternatively, Turnaround time = Waiting time + Burst time = 5 + 10 = 15ms.
Why is it impossible to perfectly optimize both response time and throughput?
Optimizing response time requires frequent context switches to quickly give attention to new processes. Optimizing throughput requires minimizing context switches to spend more time on actual execution.
Approach: Highlight the tradeoff: frequent context switches (good for response time) introduce overhead that wastes CPU cycles, thereby lowering the total number of jobs completed per second (throughput).
Continue learning
Previous: Context Switching
Next: FCFS & the Convoy Effect
Next: SJF & SRTF
Next: Round Robin & Time Quantum