Chapter 10 of 38

CPU Scheduling Basics

Picture a single doctor in a busy clinic. Patients keep arriving: some need a two-minute check, some need a long examination, some step out for a blood test and come back later. The doctor can see only one patient at a time. Who should go next? The person who came first? The quickest case? The most urgent one? Every choice makes some patients happier and others wait longer.

A CPU core faces the same problem. At any moment there may be dozens of processes that are ready to run, but one core can run only one of them. The part of the operating system that decides which process gets the CPU next is the CPU scheduler.

CPU scheduling is the process of deciding which of the ready processes should be given the CPU next, and for how long, so that the system meets its goals such as high utilization, fast response and fairness.

This chapter covers the foundations that every scheduling algorithm builds on: why scheduling is needed, when it happens, preemptive vs non-preemptive scheduling, the dispatcher, the criteria used to judge a scheduler, and how to compute completion, turnaround, waiting and response times from a Gantt chart. The following chapters, starting with FCFS Scheduling, apply these ideas to specific algorithms.


Why Do We Need CPU Scheduling?

Almost every program alternates between two kinds of activity:

  • a CPU burst: running instructions on the CPU, and

  • an I/O burst: waiting for the disk, network, keyboard, etc.

load x, add, store          ← CPU burst
read from file              ← I/O burst (process waits)
compute, increment, compare ← CPU burst
write to network            ← I/O burst (process waits)
...

This pattern is called the CPU–I/O burst cycle. While a process waits for I/O, the CPU would sit idle if nobody else used it. In a multiprogrammed system, the OS keeps several processes in memory, and whenever the running process starts waiting, the scheduler gives the CPU to another one. That is how the CPU stays busy.

Measurements of real programs show that most CPU bursts are short, with a few long ones. This leads to two kinds of processes:

I/O-bound process

CPU-bound process

Many short CPU bursts, lots of waiting for I/O

Few, long CPU bursts

Examples: text editor, web server, shell

Examples: video encoding, compiling, scientific simulation

Wants the CPU quickly, for a short time

Wants the CPU for long stretches

A good scheduler gives I/O-bound processes the CPU promptly (so they can start their next I/O and keep devices busy, and so interactive programs feel responsive) while still letting CPU-bound processes make steady progress.


Where the Scheduler Fits

In Processes & Process States we saw the ready queue and the process states. The scheduler discussed in this chapter is the short-term scheduler (or CPU scheduler): it picks a process from the ready queue and allocates the CPU to it.

          admitted                         dispatch (scheduler picks)
  New ──────────────▶ [ Ready queue ] ──────────────────────────▶ Running ──▶ Terminated
                          ▲   ▲                                     │   │       exit
                          │   │       interrupt (preempted)         │   │
                          │   └─────────────────────────────────────┘   │
                          │                                             │ I/O or event wait
                          │   I/O or event completion                   ▼
                          └──────────────────────────────────────── Waiting

For completeness, textbooks mention two other schedulers:

Scheduler

Decides

How often it runs

Long-term (job scheduler)

Which new jobs are admitted into memory; controls the degree of multiprogramming

Rarely (seconds or minutes); mostly in batch systems

Short-term (CPU scheduler)

Which ready process runs next on the CPU

Very often (every few milliseconds), so it must be fast

Medium-term

Which processes to swap out of memory temporarily and swap back in later

Occasionally, under memory pressure

From here on, "the scheduler" means the short-term scheduler.


When Does the Scheduler Run?

A scheduling decision may be needed in four situations:

  1. A process switches from Running → Waiting (it requests I/O, calls wait() for a child, sleeps, etc.).

  2. A process switches from Running → Ready (an interrupt occurs, e.g. its time slice expires).

  3. A process switches from Waiting → Ready (its I/O completes).

  4. A process terminates.

In situations 1 and 4, the scheduler has no choice: the CPU is free, so a new process must be picked. In situations 2 and 3 there is a choice: the OS may let the current process continue or switch to another one. This difference defines the two big families of scheduling.


Preemptive vs Non-Preemptive Scheduling

Non-Preemptive (Cooperative) Scheduling

Scheduling happens only in situations 1 and 4. Once a process gets the CPU, it keeps it until it either blocks or terminates. The OS never forcibly takes the CPU away.

Preemptive Scheduling

Scheduling can also happen in situations 2 and 3. The OS can interrupt a running process (typically via the timer interrupt) and give the CPU to another process, for example because its time slice is over or because a more important process just became ready.

Aspect

Non-Preemptive

Preemptive

CPU taken away from a running process?

Never; it gives up the CPU itself

Yes, the OS can interrupt it

Responsiveness

Poor: one long process can hold everyone up

Good: short or urgent tasks get the CPU quickly

A buggy infinite loop

Can freeze the whole system

Only uses its share of CPU

Overhead

Fewer context switches

More context switches

Shared data

Simpler

Process can be interrupted mid-update, so shared data needs synchronization

Examples

FCFS, non-preemptive SJF, non-preemptive priority

Round Robin, SRTF, preemptive priority

Early personal-computer systems such as Windows 3.x and classic Mac OS (before Mac OS X) used cooperative scheduling: one misbehaving program could hang the machine. Virtually all modern general-purpose operating systems, including Windows, macOS, Linux, Android and iOS, use preemptive scheduling.


The Dispatcher

The scheduler decides which process should run. The dispatcher is the module that actually gives the CPU to that process. Its job is:

  1. switching context from the old process to the new one (as described in Process Control Block & Context Switching),

  2. switching to user mode,

  3. jumping to the right location in the new process to resume it.

Dispatch latency is the time the dispatcher takes to stop one process and start another.

Since the dispatcher runs on every context switch, it must be as fast as possible. In most numerical problems the dispatch latency is assumed to be zero unless the question says otherwise.


Scheduling Criteria

How do we decide whether one scheduling algorithm is better than another? We measure it against these criteria:

Criterion

Meaning

Goal

CPU utilization

Percentage of time the CPU is busy doing useful work

Maximize

Throughput

Number of processes completed per unit time

Maximize

Turnaround time

Total time from a process's arrival to its completion

Minimize

Waiting time

Total time a process spends in the ready queue

Minimize

Response time

Time from arrival until the process first gets the CPU (first response)

Minimize

These goals conflict. For example, giving very short time slices improves response time but adds context-switch overhead, which lowers throughput. Batch systems care most about throughput and turnaround time; interactive systems care most about response time; and fairness (no process waits forever) matters everywhere.

Note that the scheduler does not change how much CPU time a process needs, nor how long its I/O takes. What a scheduler mainly affects is the waiting time in the ready queue. That is why average waiting time is the most common way to compare algorithms.


The Vocabulary of Scheduling Problems

Exam and interview problems give a table of processes and ask you to compute times. These are the standard terms:

Term

Short form

Meaning

Arrival Time

AT

When the process enters the ready queue

Burst Time

BT

CPU time the process needs

Completion Time

CT

When the process finishes

Turnaround Time

TAT

CT − AT

Waiting Time

WT

TAT − BT (time in the ready queue, if the process does no I/O)

Response Time

RT

(time of first run) − AT

Turnaround Time  = Completion Time − Arrival Time
Waiting Time     = Turnaround Time − Burst Time
Response Time    = First time on CPU − Arrival Time

Why does WT = TAT − BT work? During its turnaround time, a CPU-only process is always either running (which adds up to its burst time) or waiting in the ready queue. Subtract the running part and what is left is the waiting part.

Gantt Charts

A Gantt chart is a timeline that shows which process runs on the CPU during each interval:

| P1 | P2 | P1 | P3 |
0    3    6    8    9

Read it as: P1 runs from 0 to 3, P2 from 3 to 6, P1 again from 6 to 8, and P3 from 8 to 9. The numbers under the bars are the times at which one process stops and another begins.


Worked Example 1: The Order Matters

Three processes arrive at time 0 (in the order P1, P2, P3) and do not do any I/O. Their burst times are:

Process

Burst Time (ms)

P1

20

P2

4

P3

2

Order A: P1, P2, P3

|          P1          |  P2  | P3 |
0                     20     24   26

Waiting times: P1 = 0, P2 = 20, P3 = 24. Average waiting time = (0 + 20 + 24) / 3 = 44 / 3 ≈ 14.67 ms.

Turnaround times: P1 = 20, P2 = 24, P3 = 26. Average = 70 / 3 ≈ 23.33 ms.

Order B: P3, P2, P1

| P3 |  P2  |          P1          |
0    2      6                     26

Waiting times: P3 = 0, P2 = 2, P1 = 6. Average waiting time = (0 + 2 + 6) / 3 = 8 / 3 ≈ 2.67 ms.

Turnaround times: P3 = 2, P2 = 6, P1 = 26. Average = 34 / 3 ≈ 11.33 ms.

Same processes, same total work, same finishing time for the last process (26 ms), but the average waiting time dropped from 14.67 ms to 2.67 ms just by changing the order. When a long process runs first, every short process stuck behind it waits; this is the convoy effect, discussed in FCFS Scheduling. Running short jobs first is the idea behind SJF & SRTF Scheduling.


Worked Example 2: Computing Every Metric

Now a realistic problem with different arrival times. Suppose some preemptive scheduler produced the Gantt chart below (we are not concerned with which algorithm here, only with reading the chart correctly).

Process

Arrival Time

Burst Time

P1

0

5

P2

2

3

P3

4

1

P4

12

2

| P1 | P2 | P1 | P3 | idle | P4 |
0    3    6    8    9      12   14

The CPU is idle from 9 to 12, because all of P1, P2 and P3 have finished and P4 has not yet arrived. Idle periods must always be shown in the chart.

Step 1: Completion Time

Look for the last time each process appears in the chart: P1 ends at 8 (its second piece), P2 at 6, P3 at 9, P4 at 14.

Step 2: Turnaround, Waiting and Response Times

Process

AT

BT

CT

TAT = CT − AT

WT = TAT − BT

First run

RT = first run − AT

P1

0

5

8

8

3

0

0

P2

2

3

6

4

1

3

1

P3

4

1

9

5

4

8

4

P4

12

2

14

2

0

12

0

  • Average turnaround time = (8 + 4 + 5 + 2) / 4 = 19 / 4 = 4.75

  • Average waiting time = (3 + 1 + 4 + 0) / 4 = 8 / 4 = 2

  • Average response time = (0 + 1 + 4 + 0) / 4 = 5 / 4 = 1.25

Step 3: Check the Waiting Time Directly

For P1, WT = 3 from the formula. Check it from the chart: P1 arrives at 0, runs 0–3, then waits from 3 to 6 while P2 runs, then runs 6–8. Total waiting = 6 − 3 = 3. ✔

Notice that P1's response time is 0 but its waiting time is 3. Response time counts only the wait before the first run; waiting time counts all time in the ready queue. For non-preemptive algorithms, a process runs in one piece, so RT = WT.

Step 4: CPU Utilization and Throughput

  • The schedule spans 0 to 14 = 14 time units. The CPU was busy for 5 + 3 + 1 + 2 = 11 units (idle 3 units).

  • CPU utilization = 11 / 14 ≈ 78.57%.

  • Throughput = 4 processes / 14 units ≈ 0.286 processes per unit time (that is, 2 processes every 7 units).


Conventions Used in Scheduling Problems

Unless a question says otherwise, the usual assumptions are:

  • Context-switch (dispatch) time is zero.

  • Processes are CPU-only (no I/O), so WT = TAT − BT.

  • Times are in the same unit (usually milliseconds) and are integers.

  • If two processes are equally good choices (a tie), pick the one that arrived earlier, and if they arrived together, the one with the lower process number.

  • If the CPU becomes free and no process has arrived, the CPU stays idle until the next arrival.

Some questions do include a context-switch time or I/O bursts. Then you must add switch intervals to the Gantt chart and remember that time spent doing I/O is not waiting time (the process is in the waiting state, not the ready queue).


A Preview of the Scheduling Algorithms

Algorithm

Picks next

Preemptive?

Can starve?

FCFS

The process that arrived first

No

No

SJF

The process with the shortest next CPU burst

No

Yes (long jobs)

SRTF

The process with the shortest remaining time

Yes

Yes (long jobs)

Priority

The highest-priority process

Either

Yes (low priority), fixed by aging

Round Robin

Next in a circular queue, for one time quantum

Yes

No

Multilevel (Feedback) Queue

From the highest non-empty queue

Usually yes

Possible, depends on design

Each of these gets its own chapter, starting with FCFS Scheduling.


Scheduling in Real Operating Systems

Real kernels combine several ideas rather than using one textbook algorithm. Linux, for example, has several scheduling policies. The chrt -m command lists them along with their priority ranges (output from Ubuntu on WSL2, kernel 6.18):

SCHED_OTHER min/max priority	: 0/0
SCHED_FIFO min/max priority	: 1/99
SCHED_RR min/max priority	: 1/99
SCHED_BATCH min/max priority	: 0/0
SCHED_IDLE min/max priority	: 0/0
SCHED_DEADLINE min/max priority	: 0/0
  • SCHED_OTHER (also called SCHED_NORMAL) is used by ordinary processes. Since Linux 6.6 it is implemented by the EEVDF (Earliest Eligible Virtual Deadline First) scheduler, which replaced the Completely Fair Scheduler (CFS) that had been the default since Linux 2.6.23. Both aim to share the CPU fairly according to each process's nice value, from −20 (highest priority) to 19 (lowest).

  • SCHED_FIFO and SCHED_RR are real-time policies with static priorities 1 to 99. A runnable real-time task always runs before any SCHED_OTHER task (apart from a small safety reserve, by default about 5% of each second, that the kernel keeps for normal tasks so a runaway real-time task cannot freeze the machine). SCHED_RR is the round-robin version.

  • SCHED_BATCH and SCHED_IDLE are for background work.

  • SCHED_DEADLINE schedules tasks by deadlines and takes runtime/period parameters instead of a priority.

You can try nice values yourself: nice -n 10 ./myprogram starts a program with lower priority, and ps -o pid,cls,ni,cmd shows each process's class (TS = time-sharing, i.e. SCHED_OTHER) and nice value. Windows uses a preemptive, priority-based scheduler with 32 priority levels, and gives threads temporary priority boosts (for example, when they wake up after waiting for input) to keep the interface responsive.

On multi-core machines, there is another layer: deciding which core a process runs on. Keeping a process on the same core helps it reuse its cached data (processor affinity), while moving work between cores keeps all of them busy (load balancing).


Common Mistakes

  • Using burst time instead of arrival time in TAT. TAT = CT − AT, not CT − BT.

  • Using the first appearance instead of the last for completion time in a preemptive Gantt chart.

  • Confusing response time with waiting time. They are equal only if the process runs in one piece.

  • Forgetting idle time. If no process has arrived, the CPU is idle; do not start the next process before its arrival time.

  • Counting I/O time as waiting time. Waiting time is time in the ready queue only.

  • Calling the scheduler and the dispatcher the same thing. The scheduler chooses; the dispatcher performs the switch.


Interview Questions

What is the difference between preemptive and non-preemptive scheduling?

In non-preemptive scheduling, a running process keeps the CPU until it blocks or terminates. In preemptive scheduling, the OS can take the CPU away, for example when a time slice expires or a higher-priority process becomes ready.

In which four situations can a scheduling decision occur, and which ones are non-preemptive?

Running → Waiting, Running → Ready, Waiting → Ready, and termination. Scheduling only at Running → Waiting and termination is non-preemptive; scheduling also at the other two is preemptive.

What is the dispatcher? What is dispatch latency?

The dispatcher gives control of the CPU to the process selected by the scheduler: it switches context, switches to user mode and jumps to the right place in the program. Dispatch latency is the time it takes to stop one process and start another.

Define turnaround time, waiting time and response time.

Turnaround = completion − arrival. Waiting = total time in the ready queue = turnaround − burst (for CPU-only processes). Response = time of first CPU allocation − arrival.

Which scheduling criteria should be maximized and which minimized?

Maximize CPU utilization and throughput. Minimize turnaround time, waiting time and response time.

What is the difference between an I/O-bound and a CPU-bound process?

An I/O-bound process has many short CPU bursts and spends most of its time waiting for I/O; a CPU-bound process has few, long CPU bursts. Schedulers usually favour I/O-bound processes so devices stay busy and interactive programs feel fast.

Which scheduler does Linux use for normal processes today?

EEVDF (Earliest Eligible Virtual Deadline First), merged in Linux 6.6 as the replacement for CFS. Normal processes use the SCHED_OTHER policy with nice values from −20 to 19.


Summary

  • Processes alternate between CPU bursts and I/O bursts; scheduling keeps the CPU busy while others wait for I/O.

  • The short-term scheduler picks the next process from the ready queue; the dispatcher performs the switch.

  • Scheduling decisions happen on Running → Waiting, Running → Ready, Waiting → Ready and termination. Using only the first and last gives non-preemptive scheduling; using all four gives preemptive scheduling.

  • Criteria: maximize CPU utilization and throughput; minimize turnaround, waiting and response times.

  • Formulas: TAT = CT − AT, WT = TAT − BT, RT = first run − AT.

  • The order in which processes run can change the average waiting time dramatically, even though the total work is the same.

  • Real systems mix policies: Linux uses EEVDF for normal tasks plus real-time FIFO/RR and deadline policies.

The scheduler cannot make work disappear; it can only decide who waits. A good scheduler makes sure the right processes wait the least.