CPU Scheduling Concepts

Introduction

Think of the CPU as a single doctor in a busy clinic. Patients (processes) keep arriving, each needing different amounts of time. Some need just a quick consultation (I/O-bound processes), others need lengthy examinations (CPU-bound processes). The doctor cannot see everyone at once, so a receptionist (scheduler) must decide who goes next. The scheduling decision dramatically affects how long patients wait, how many patients are seen per day, and how satisfied they are.

CPU scheduling is one of the most fundamental functions of an operating system. Since the CPU is the most valuable resource in a computer system, how we allocate it among competing processes determines the overall system performance. A good scheduling algorithm maximizes CPU utilization, throughput, and fairness while minimizing waiting time and response time.

The CPU-I/O Burst Cycle

Every process alternates between two states: using the CPU (CPU burst) and waiting for I/O (I/O burst). This alternating pattern is called the CPU-I/O burst cycle.

I/O-bound processes: Many short CPU bursts with frequent I/O (text editor, web browser). They need the CPU briefly and then wait for user input or network data.

CPU-bound processes: Few long CPU bursts with rare I/O (video encoding, scientific simulation). They want to keep the CPU as long as possible.

A good scheduler should give I/O-bound processes quick access to the CPU (they will release it fast anyway) and let CPU-bound processes run in longer stretches (fewer context switches).

Scheduling Criteria

How do we measure whether a scheduling algorithm is good? There are several metrics:

These criteria often conflict. For example, maximizing throughput might mean running short jobs first (like SJF), but this could starve long processes. Minimizing response time requires frequent context switches (Round Robin), but too many switches reduce throughput.

Types of Schedulers

An operating system typically has three types of schedulers:

Long-Term Scheduler (Job Scheduler)

Decides which processes are admitted from the job pool to the ready queue. Controls the degree of multiprogramming (how many processes are in memory simultaneously). It runs infrequently (seconds to minutes) and carefully balances I/O-bound and CPU-bound processes.

Short-Term Scheduler (CPU Scheduler)

Selects which process in the ready queue gets the CPU next. This is what we usually mean by "CPU scheduling." It runs very frequently (every few milliseconds) and must be extremely fast — if it takes 10ms to decide and runs every 100ms, that is 10% overhead.

Medium-Term Scheduler (Swapper)

Temporarily removes processes from memory (swaps them to disk) to reduce the degree of multiprogramming. When memory pressure eases, swapped processes are brought back. This is called swapping.

Preemptive vs Non-Preemptive Scheduling

Non-Preemptive (Cooperative)

Once a process gets the CPU, it keeps it until it voluntarily releases — either by finishing, performing I/O, or calling a yield() function. The scheduler only makes decisions at these natural transition points.

Advantages: No race conditions on shared data, simpler implementation Disadvantages: One process can monopolize the CPU, poor response time

Preemptive

The OS can forcibly take the CPU from a running process (via timer interrupt) and give it to another. The scheduler can make decisions at any time.

Advantages: Better response time, fairness, handles misbehaving processes Disadvantages: Needs careful handling of shared data (synchronization), context switch overhead

Almost all modern operating systems use preemptive scheduling. The hardware timer generates interrupts at regular intervals, giving the scheduler an opportunity to make decisions.

The Dispatcher

The dispatcher is the module that gives control of the CPU to the process selected by the scheduler. Its functions include:

1. Context switching — Save the state of the old process, load state of new process
2. Switching to user mode — The scheduler runs in kernel mode; the process runs in user mode
3. Jumping to the proper location — Set the program counter to where the new process should resume

The time the dispatcher takes is called dispatch latency. It should be as small as possible since it is pure overhead — no useful work happens during dispatch.

When Does CPU Scheduling Occur?

Scheduling decisions happen in four situations:

1. A process switches from running to waiting (I/O request) — non-preemptive
2. A process switches from running to ready (interrupt/preemption) — preemptive
3. A process switches from waiting to ready (I/O completion) — preemptive
4. A process terminates — non-preemptive

In non-preemptive scheduling, only situations 1 and 4 require scheduling decisions. In preemptive scheduling, all four situations trigger the scheduler.

Real-World Analogy

The entire CPU scheduling system is like an airport gate agent managing boarding. The long-term scheduler is like the airline deciding how many tickets to sell (controlling how many passengers are at the gate). The short-term scheduler is the gate agent calling boarding groups (deciding who boards next). The dispatcher is the actual process of scanning the boarding pass and letting the passenger walk down the jetway (the mechanical work of switching). The medium-term scheduler is like asking passengers to wait in the lounge when the gate area is too crowded (swapping).

Key Takeaways

• CPU scheduling decides which process gets the CPU and for how long
• Processes alternate between CPU bursts and I/O bursts in a cycle
• Five key metrics measure scheduler quality: utilization, throughput, turnaround, waiting, and response time
• Three scheduler types operate at different time scales: long-term, short-term, and medium-term
• Preemptive scheduling (used in all modern OS) can interrupt running processes for better fairness
• The dispatcher handles the mechanical work of context switching with minimal latency
• Good scheduling balances conflicting goals — there is no single best algorithm for all situations