Free lesson · Operating Systems

Scheduling Criteria

Easy10 min readoperating-systemsosconcurrency

You Cannot Optimize Everything at Once

Before comparing scheduling algorithms, you need to know what "good" means. The problem is that "good" depends on what you care about - and different goals conflict with each other. A scheduler that maximizes throughput (total jobs completed per second) may provide terrible response times for individual requests. A scheduler that minimizes response time for interactive users may waste CPU cycles on rapid context switching.

This topic defines the five metrics that scheduling algorithms are evaluated against and explains the fundamental tradeoffs between them. Understanding these tradeoffs is essential for interviews because the interviewer does not just want you to recite how Round Robin works - they want you to explain when Round Robin is the right choice and why, which requires understanding what you are optimizing for.

The Five Scheduling Criteria

Every scheduling algorithm can be evaluated along five dimensions. Here they are, in order from system-level metrics (what the system administrator cares about) to user-level metrics (what the person sitting at the keyboard cares about).

1. CPU Utilization

What it measures: The percentage of time the CPU is doing useful work (not idle).

Goal: Keep the CPU as busy as possible. On a production server, you want CPU utilization between 40-70% under normal load and capable of bursting to 90%+ under peak load. A server running at 10% CPU utilization is wasting expensive hardware. A server running at 99% has no headroom for traffic spikes.

Why it matters: CPU time is the most expensive resource on a server. If the scheduler leaves the CPU idle while there are processes in the ready queue, it is wasting money. This happens when the scheduler takes too long to make decisions, or when it picks a process that immediately blocks on I/O rather than one that has CPU work to do.

2. Throughput

What it measures: The number of processes that complete execution per unit of time. If 100 requests arrive in one second and 95 complete within that second, the throughput is 95 requests per second.

Goal: Maximize throughput. More completed processes per second means the system is doing more useful work.

Why it matters: For batch processing systems (data pipelines, nightly reports, build systems), throughput is the most important metric. You want to finish as many jobs as possible in the available time. A scheduler that maximizes throughput will favor longer-running processes (to avoid the overhead of frequent context switches) and batch similar jobs together.

3. Turnaround Time

What it measures: The total time from when a process is submitted to when it completes. This includes time waiting in the ready queue, time running on the CPU, time waiting for I/O, and time being context-switched.

Formula: Turnaround Time = Completion Time − Arrival Time

Goal: Minimize average turnaround time across all processes.

Why it matters: Turnaround time measures the end-to-end experience. If you submit a compilation job and it takes 30 seconds even though the actual compilation only needs 5 seconds of CPU time, the other 25 seconds were spent waiting. Reducing turnaround time means reducing unnecessary waiting.

4. Waiting Time

What it measures: The total time a process spends in the ready queue - waiting for the CPU but not doing anything useful. Waiting time does not include time spent actually running on the CPU or waiting for I/O.

Formula: Waiting Time = Turnaround Time − Burst Time (where Burst Time is the total CPU time the process actually uses)

Goal: Minimize average waiting time. This is the metric most scheduling algorithm comparisons focus on because it isolates the scheduler's contribution to delay. The scheduler cannot reduce the time a process needs to compute or wait for I/O, but it can reduce the time the process spends sitting in the ready queue doing nothing.

Why it matters: Waiting time is the purest measure of scheduling quality. Two schedulers might produce the same turnaround time because the processes have the same CPU bursts and I/O waits, but one scheduler might have lower waiting time because it orders the processes more intelligently.

5. Response Time

What it measures: The time from when a request is submitted until the first response is produced - not the full completion time, just the time until the system starts responding.

Goal: Minimize response time, especially for interactive systems.

Why it matters: For interactive applications (web servers, desktop applications, mobile apps), response time is what the user perceives. A web page that starts rendering in 200 milliseconds and finishes loading in 2 seconds feels faster than a page that does nothing for 1.5 seconds and then appears all at once - even though the second approach has lower turnaround time. Response time is about perceived performance, and it is the metric that matters most for user-facing systems.

graph TD
    subgraph METRICS["The Five Scheduling Criteria"]
        CPU["CPU Utilization<br/>────<br/>% of time CPU is busy<br/>Goal: Keep high (40-70%)"]
        TP["Throughput<br/>────<br/>Jobs completed / second<br/>Goal: Maximize"]
        TT["Turnaround Time<br/>────<br/>Submit to complete<br/>Goal: Minimize"]
        WT["Waiting Time<br/>────<br/>Time in ready queue<br/>Goal: Minimize"]
        RT["Response Time<br/>────<br/>Submit to first response<br/>Goal: Minimize"]
    end
    
    subgraph SYSTEM["System-Level Metrics"]
        CPU
        TP
    end
    
    subgraph USER["User-Level Metrics"]
        TT
        WT
        RT
    end

This diagram organizes the five scheduling criteria into two groups. System-level metrics include CPU utilization (percentage of time the CPU is busy, goal is to keep it high) and throughput (jobs completed per second, goal is to maximize). User-level metrics include turnaround time (time from submission to completion, minimize), waiting time (time spent in the ready queue, minimize), and response time (time from submission to first response, minimize).

The Fundamental Tradeoffs

These five metrics cannot all be optimized simultaneously. Improving one often degrades another. Understanding these tradeoffs is the key to choosing the right scheduling algorithm for a given workload.

Throughput vs Response Time

This is the most important tradeoff in scheduling - and in system design generally.

To maximize throughput, the scheduler should minimize context switches. Every context switch wastes CPU time on saving and restoring state rather than doing useful work. The logical extreme is to let each process run to completion before starting the next one - no context switches, maximum throughput. But this means the second process waits until the first one finishes, which could be seconds or minutes. Response time is terrible.

To minimize response time, the scheduler should switch between processes frequently, giving each one a small time slice. This way, every process gets a little bit of CPU time quickly, and users see fast responses. But frequent switching means more context switch overhead, which reduces throughput.

Every scheduler navigates this tension. Round Robin (Topic 05) lets you control the balance directly through the quantum size - a larger quantum improves throughput but hurts response time, and a smaller quantum improves response time but hurts throughput.

Fairness vs Performance

A "fair" scheduler gives every process an equal share of CPU time. But equal is not always optimal. An I/O-bound process that needs 1 millisecond of CPU time between I/O waits should not get the same treatment as a CPU-bound process that needs 10 seconds of continuous computation. The I/O-bound process will waste most of its time slice returning to the Waiting state, while the CPU-bound process can use its entire slice productively.

Smart schedulers sacrifice strict fairness for performance - they give I/O-bound processes higher effective priority (because they use the CPU briefly and yield quickly) and let CPU-bound processes run when nothing else needs the CPU. This is one of the key insights behind the Multi-Level Feedback Queue (Topic 07).

Individual Process Optimization vs System Optimization

Optimizing for one process's turnaround time may hurt the average turnaround time across all processes. Shortest Job First (Topic 04) is provably optimal for average waiting time, but it can starve long-running processes - their individual turnaround time is terrible even though the system average is minimized.

This is a general principle: global optimization often requires sacrificing individual outcomes. The scheduler must balance the needs of the many against the needs of the few, and different algorithms make this tradeoff differently.

How Different Workloads Prioritize Different Criteria

The right set of priorities depends entirely on the type of system the scheduler is running on. Understanding this mapping is what allows you to justify scheduling choices in interviews.

Batch processing systems (Hadoop jobs, nightly ETL pipelines, CI/CD builds). These systems care most about throughput and CPU utilization. Nobody is sitting at a keyboard waiting for a response. The goal is to process as many jobs as possible in the available time. Turnaround time matters for individual job SLAs, but response time is irrelevant. Schedulers for batch systems minimize context switches and favor running jobs to completion.

Interactive desktop systems (Windows, macOS, Linux desktops). These systems care most about response time. When you click a button, you expect an immediate response. The scheduler must give interactive processes (the window manager, the text editor, the web browser) priority over background tasks (indexing, updates, backups). Throughput is secondary - users do not care how many total processes completed this second as long as their click gets a response in under 100 milliseconds.

Real-time systems (industrial control, avionics, medical devices). These systems care about meeting deadlines. A process that must complete within 10 milliseconds must complete within 10 milliseconds - not 11, not 12. Missing a deadline is a failure, even if the average response time is excellent. Real-time schedulers use algorithms specifically designed for deadline guarantees, like Earliest Deadline First (EDF) and Rate Monotonic Scheduling (RMS). These algorithms are not covered in depth in this course because they rarely appear in FAANG interviews, but knowing they exist shows breadth.

Web servers and microservices (Nginx, Tomcat, Go services). These systems care about response time (low latency per request) and throughput (high requests per second) simultaneously. This is the hardest workload to schedule because the two goals conflict. Production systems at FAANG companies typically use thread pools (bounding context switches for throughput) combined with priority mechanisms (ensuring that latency-sensitive requests get CPU time quickly).

Database systems (PostgreSQL, MySQL, Redis). These systems care about query response time (users expect fast queries) and throughput (the database serves many clients simultaneously). Additionally, internal background tasks (vacuuming, checkpointing, replication) must run regularly but should not interfere with user queries. Database schedulers (both at the OS level and within the database engine itself) must balance interactive query handling with background maintenance.

Interview: "What are the criteria for evaluating scheduling algorithms?"

"There are five main criteria. CPU utilization measures how busy the CPU is - the goal is to keep it high. Throughput measures how many processes complete per unit time - maximize this for batch systems. Turnaround time measures the total time from submission to completion - minimize for job processing. Waiting time measures time spent in the ready queue - this is the purest measure of scheduler quality. Response time measures how quickly the system starts responding - critical for interactive applications.

The key tradeoff is between throughput and response time. Maximizing throughput means fewer context switches, which means longer waits for individual processes. Minimizing response time means frequent context switches, which reduces throughput. Different algorithms balance this tradeoff differently - FCFS favors throughput, Round Robin favors response time, and MLFQ tries to balance both."

A Worked Example: Comparing Metrics

Let us make these metrics concrete with a small example. Suppose three processes arrive at time 0 with the following CPU burst times:

If the scheduler runs them in order P1 → P2 → P3 (FCFS):

If the scheduler runs them in order P2 → P3 → P1 (shortest first):

Same three processes, same total CPU time, but the average waiting time dropped from 17 milliseconds to 3 milliseconds - just by changing the order. The total time to complete all three processes is identical (30 ms), but the individual experience is dramatically different. P2 went from waiting 24 ms to waiting 0 ms. P1 went from waiting 0 ms to waiting 6 ms.

This simple example illustrates why scheduling order matters and why Shortest Job First has the optimal average waiting time. Topics 03 and 04 explore this in depth.

gantt
    title FCFS Order: P1 → P2 → P3
    dateFormat X
    axisFormat %s ms
    
    section Processes
    P1 (24ms)       :a1, 0, 24
    P2 (3ms)        :a2, 24, 27
    P3 (3ms)        :a3, 27, 30

    title SJF Order: P2 → P3 → P1
    section Processes
    P2 (3ms)        :b1, 0, 3
    P3 (3ms)        :b2, 3, 6
    P1 (24ms)       :b3, 6, 30

This Gantt chart compares two scheduling orders. In FCFS order, P1 runs from time 0 to 24, P2 from 24 to 27, and P3 from 27 to 30. P2 and P3 wait a long time for short jobs. In SJF order, P2 runs from 0 to 3, P3 from 3 to 6, and P1 from 6 to 30. The short jobs finish quickly, and the average waiting time drops from 17 ms to 3 ms.

Tip: For interviews: Being able to calculate turnaround time and waiting time for a small example is a common test. Practice with 3-4 processes under different scheduling algorithms until the calculations are automatic. The formulas are simple: Turnaround = Completion − Arrival, Waiting = Turnaround − Burst. What the interviewer really wants to see is that you understand why the numbers differ across algorithms.

Exercise: Starter: Given processes P1 (burst = 10), P2 (burst = 5), P3 (burst = 8), all arriving at time 0, calculate the average turnaround time and average waiting time if they are scheduled in the order P1 → P2 → P3.

Intermediate: For the same three processes, find the scheduling order that minimizes average waiting time. Calculate the metrics for that order. Compare the numbers to the P1 → P2 → P3 order. How much improvement did you get?

Advanced: Consider a system where throughput is the most important metric (a batch processing server) versus a system where response time is the most important metric (a web server handling user requests). For each system, which scheduling criteria would you prioritize? What algorithm properties would you want? Which metrics would you accept degrading?

Back to Operating Systems