When does the Scheduler Run?

CPU scheduling decisions occur whenever a process:

1. Switches from running to waiting (I/O, wait()).
2. Switches from running to ready (timer interrupt).
3. Switches from waiting to ready (I/O completion).
4. Terminates.

Cases 1 and 4 are non-preemptive; 2 and 3 require preemptive scheduling. Modern OS kernels (Linux included) use preemptive scheduling so high-priority processes can take the CPU immediately.

The Dispatcher

The dispatcher is the kernel module that actually performs the context switch — saves state, switches to user mode, and jumps to the next process's program counter. The time it takes is dispatch latency.

Scheduling Criteria

A scheduler is judged by several metrics:

Different workloads stress different criteria: batch jobs care about throughput and turnaround; interactive workloads care about response time.

CPU-Bound vs I/O-Bound Processes

• CPU-bound — long bursts of computation, few I/O operations.
• I/O-bound — many short CPU bursts interleaved with I/O.

A good scheduler maintains a healthy mix so the CPU and I/O devices stay busy simultaneously.

Burst Cycle

Process execution alternates between CPU bursts and I/O bursts. Histograms of CPU-burst length show that most bursts are short and a few are long — exponential distribution.

Preemptive vs Non-preemptive

Worked Mini-example

Suppose we have three processes:

• P1 burst 10, P2 burst 1, P3 burst 2.
• Arrival in order P1, P2, P3 at time 0.

Under FCFS, P1 runs to completion (0–10), then P2 (10–11), then P3 (11–13). Average waiting time = (0+10+11)/3 = 7.

Under SJF, order is P2 (0–1), P3 (1–3), P1 (3–13). Average waiting time = (3+0+1)/3 = 1.33.

Same workload, very different averages — choice of policy matters.

Summary

• Scheduling is invoked on state transitions; preemption requires interrupts.
• Six classic criteria — utilization, throughput, turnaround, waiting, response, fairness — sometimes conflict.
• The right policy depends on whether the workload is batch, interactive, or real-time.