CPU Scheduling

Need for Scheduling

In a multiprogramming OS, several processes compete for the CPU. The CPU scheduler decides which ready process runs next, aiming to keep the CPU busy and users responsive.

Scheduling Criteria

• CPU utilization — keep the CPU as busy as possible.
• Throughput — processes completed per unit time.
• Turnaround time — submission to completion.
• Waiting time — total time in the ready queue.
• Response time — submission to first response.
• Fairness — every process gets its turn.

Preemptive vs Non-Preemptive

Non-preemptive schedulers let a process run until it finishes or blocks. Preemptive schedulers can interrupt a running process to give the CPU to a higher-priority one.

First-Come, First-Served (FCFS)

Non-preemptive. Processes are served in arrival order. Simple but suffers from the convoy effect: a long process delays all shorter ones behind it.

Shortest Job First (SJF)

Pick the process with the smallest CPU burst. Optimal in average waiting time. Problem: burst time must be known or estimated. SRTF is the preemptive version.

Priority Scheduling

Each process has a priority; the highest priority runs first. Risk: starvation — low-priority processes may wait forever. Fix with aging: raise priority over time.

Round-Robin (RR)

Each ready process gets a fixed time quantum (5-100 ms). If it is not finished at the end, it goes to the back of the ready queue. Preemptive and fair. A small quantum gives responsiveness but raises context-switch overhead.

Example: Gantt Chart

Processes P1(24), P2(3), P3(3) arrive at t=0 in that order. FCFS:

| P1 (0-24) | P2 (24-27) | P3 (27-30) |
Waiting times: P1=0, P2=24, P3=27. Average = 17 ms.

With SJF (same data): P2, P3, P1. Average waiting = (6+3+0)/3 = 3 ms.

Multilevel Queue Scheduling

Multiple ready queues, each with its own algorithm. Example: foreground (RR) and background (FCFS). Processes are permanently assigned to a queue based on type.

Multilevel Feedback Queue

Allows processes to move between queues based on behavior. A CPU-bound process that uses its full quantum is demoted to a lower-priority queue; an I/O-bound process is promoted. This is how modern general-purpose OSes (Linux CFS, Windows) implement scheduling.

Multiprocessor Scheduling

With multiple CPUs, the scheduler decides which CPU runs which process. Issues:

• Load balancing — keep all CPUs busy.
• Processor affinity — keep processes on the same CPU to preserve cache.
• Symmetric multiprocessing (SMP) vs asymmetric.

Real-Time Scheduling

Real-time systems demand deadline guarantees. Common algorithms: Rate Monotonic (static priority inverse to period) and Earliest Deadline First (EDF).

Evaluation

Schedulers are evaluated using deterministic models (worked examples), queuing models, simulations, and actual implementation measurement.

Summary

Choose a scheduler that matches the workload: FCFS for batch, SJF when burst lengths are known, RR for time-sharing, multilevel feedback for general-purpose OS, EDF for real-time. All aim to balance throughput, responsiveness, and fairness.

Important Questions

1. List CPU scheduling criteria.
2. Differentiate preemptive and non-preemptive scheduling.
3. Explain FCFS with an example Gantt chart.
4. Compute average waiting time for SJF given burst times.
5. What is the convoy effect?
6. Explain round-robin. What is time quantum?
7. Describe multilevel feedback queue scheduling.
8. Compare rate monotonic and earliest deadline first.