Core · Operating systemsLesson 1 of 6Free to read

Processes and scheduling · Operating Systems

How does one CPU run dozens of programs "at once"?

Why you need it

Your laptop runs a browser, music and an editor on a few CPU cores. The operating system's scheduler switches between processes many times a second so each one makes progress. How it chooses explains why a busy machine feels slow, and what "CPU-bound" and "waiting on I/O" mean when you profile a server.

The intuition

A process is a running program with its own memory. At any moment it is in one state:

running on a CPU
ready: could run, waiting for a turn
blocked: waiting for something slow (disk, network, a key press)

Round-robin scheduling gives each ready process a short time slice (a quantum), then moves it to the back of the queue. Short jobs finish quickly and nobody starves. Switching costs a little time (a context switch), so slices can't be tiny.

Definition

Process

A running program: its code, its own memory, open files and a state (running, ready, blocked). Identified by a PID.

Context switch

Saving one process's CPU state and loading another's so it can continue. Necessary for sharing, but pure overhead.

Examples

Round-robin, step by step

Try it yourself

Three jobs need 5, 2 and 3 units of CPU. Each turn gets at most 2 units.

from collections import deque

ready = deque([("A", 5), ("B", 2), ("C", 3)])
quantum, clock = 2, 0
while ready:
    name, left = ready.popleft()
    run = min(quantum, left)
    clock += run
    if left - run > 0:
        ready.append((name, left - run))
    else:
        print(name, "done at", clock)

Step by step

L7Run for the slice, or less if the job finishes first.
L10Not finished: back of the line.
L12B finishes first at 4, then C at 9, A at 10.B done at 4

Common mistakes

More processes means more speed

With 4 cores, 400 CPU-busy processes don't run 100× faster; they take turns and the switching adds overhead.

Busy-waiting

A loop that keeps checking while not ready: pass burns a whole CPU doing nothing. Blocking calls let the OS run something else.

Quick quiz

1. A process is waiting for a file to be read from disk. What state is it in?

ABlocked
BRunning
CReady

Show the answer

Answer: A

It can't use the CPU until the data arrives, so the scheduler skips it.

2. What does this print?

jobs = [("A", 3), ("B", 1), ("C", 2)]
clock = 0
for name, need in sorted(jobs, key=lambda j: j[1]):
    clock += need
    print(name, clock)

A
```
B 1
C 3
A 6
```
B
```
A 3
B 4
C 6
```
C
```
B 1
C 2
A 3
```

Show the answer

Answer: A

Shortest job first: B (1), C (1 + 2 = 3), A (3 + 3 = 6).

Practice

3 exercises in three steps: predict what a program prints, change a program to meet a new requirement, then write one from scratch. Your code runs in the browser and is checked the moment you submit.

PredictTrace the scheduler
Type exactly what this program prints.
ModifyUse the quantum
finish_times(jobs, quantum) should simulate round-robin and return a dict of when each job finished. Right now it runs every job to completion in one go (first come, first served). Make each turn run at most quantum units and send unfinished jobs to the back.
WriteAverage waiting time
Jobs all arrive at time 0 and run one after another in the given order. A job's waiting time is how long it waited before starting. Write avg_wait(bursts) that returns the average waiting time as a float. Then try it in the editor with the same jobs in two orders and see why short-job-first helps.

Practise this lesson

Open the interactive lesson to edit and run these examples and solve the exercises with instant feedback. Free to start, no sign-up.

Open the interactive lesson Course map

Terms in this lesson

Term	Chinese	Definition
Process	进程	A running program with its own memory and state.
Scheduler	调度器	The part of the OS that decides which process runs next.
Time slice (quantum)	时间片	How long a process may run before the scheduler switches.