CPU Scheduling: Goals and Criteria

The Emergency Room Analogy

Walk into a busy emergency room. The hospital has competing goals that pull in different directions:

• Keep doctors busy: an idle doctor is a wasted resource
• Process many patients: high throughput means more people helped per hour
• Minimize total time in hospital: turnaround time for each patient
• Minimize wait before being seen: waiting time matters for satisfaction
• Respond quickly to new arrivals: response time for triage

These goals conflict. Routing all easy cases through quickly improves throughput but delays critical patients. Keeping every doctor busy might mean patients wait longer in triage. Every hospital management decision is a tradeoff.

The CPU scheduler faces the exact same tradeoffs. It must decide: which process runs next, for how long, and what happens when a higher-priority process arrives. The criteria for making these decisions are the foundation of scheduling theory.

What Is CPU Scheduling?

The CPU can only execute one process at a time (on a single core). Many processes compete for CPU time simultaneously. The CPU scheduler selects which process in the ready queue gets the CPU next, and for how long.

Scheduling decisions happen at specific moments:

1. A process switches from running to waiting (I/O request)
2. A process switches from running to ready (timer interrupt)
3. A process switches from waiting to ready (I/O completion)
4. A process terminates

CPU Burst vs I/O Burst

Processes alternate between two types of activity:

• CPU Burst: a period of pure computation (calculating, sorting, rendering)
• I/O Burst: a period of waiting for I/O (disk read, network response, keyboard input)

[CPU burst] → [I/O burst] → [CPU burst] → [I/O burst] → ... → [terminate]

CPU-Bound vs I/O-Bound Processes

I/O-bound processes spend most of their time waiting. While they wait, the CPU should be given to other processes. Scheduling I/O-bound processes first often improves overall system responsiveness.

Process Queues and State Transitions

NEW
 |
 v
READY QUEUE ──────────────────────────────────────────────────────┐
 |                                                                  |
 | scheduler dispatch                                               |
 v                                                                  |
RUNNING                                                             |
 |         |              |                                         |
 | exit     | I/O request  | timer interrupt (preemption)           |
 v         v              v                                         |
TERMINATED WAITING        READY ───────────────────────────────────┘
           QUEUE
            |
            | I/O complete
            |
            └──────────────────────────> READY QUEUE

The ready queue holds all processes that are in memory, ready to run, and waiting for the CPU.

The waiting queue (also called the device queue) holds processes blocked on I/O — they cannot use the CPU even if it's free.

The scheduler only picks from the ready queue. When I/O completes, the OS moves the process back to the ready queue so it can compete for CPU time again.

Scheduling Criteria

1. CPU Utilization

Definition: Percentage of time the CPU is doing useful work (not idle).

Goal: Maximize (target: 40–90% in a real system)

An idle CPU is wasted hardware. The scheduler should always have something for the CPU to do.

2. Throughput

Definition: Number of processes completed per unit of time.

Goal: Maximize

For long-running batch jobs, throughput might be 1 job/hour. For short interactive tasks, it might be 100 tasks/second.

3. Turnaround Time

Definition: Total time from process submission to process completion.

Turnaround Time = Completion Time − Arrival Time

Goal: Minimize

Includes time waiting in the ready queue, time executing, and time waiting for I/O.

4. Waiting Time

Definition: Total time a process spends in the ready queue waiting for the CPU.

Waiting Time = Turnaround Time − Burst Time

Goal: Minimize

Waiting time is the pure scheduling overhead — time lost to waiting rather than executing.

5. Response Time

Definition: Time from submitting a request to receiving the first response.

Goal: Minimize (especially for interactive systems)

Response time is not completion time — it is the time until the system first acknowledges the request. A user typing a command wants to see a cursor blink within milliseconds, not wait for the full task to complete.

Criteria Summary Table

Preemptive vs Non-Preemptive Scheduling

Non-preemptive schedulers are simpler but can lead to long waiting times if one process hogs the CPU. Preemptive schedulers add overhead but guarantee fairer access.

Why Interactive Systems Prioritize Response Time

A batch processing system (payroll, scientific simulation) cares about total throughput — complete as many jobs as possible per hour. No one is watching the terminal.

An interactive system (desktop, web server) must feel responsive. A user expects a keystroke to appear instantly. If response time exceeds 100ms, the system feels sluggish. If it exceeds 1 second, users perceive it as broken.

This is why modern desktop and server operating systems use preemptive schedulers with time-sharing: every process gets short, frequent turns at the CPU. No single process can monopolize the CPU and freeze the interface.

The Fundamental Tradeoff

Optimizing one criterion often hurts another:

• Maximize throughput → run long jobs without interruption → poor response time
• Minimize response time → frequently switch between processes → more overhead, lower throughput
• Minimize waiting time → run shortest jobs first → long jobs may wait forever (starvation)

Real schedulers balance these competing demands based on the system's purpose: batch systems favor throughput, interactive systems favor response time, and real-time systems have hard deadlines that override all other criteria.

Understanding these criteria is the prerequisite for evaluating any scheduling algorithm.