Part VII · Chapter 20

Processes, Scheduling and System Calls

Your computer has a handful of processor cores, yet hundreds of programs seem to run at once. That's the kernel's greatest trick: it gives each program a few milliseconds at a time, switching between them so quickly that they all appear to run together. This chapter shows how it keeps track of every program, how it switches, and how it decides who goes next.

A program is a file on a disk: a list of instructions, like a recipe in a book. A process is a program that's running: the recipe being cooked, with its own kitchen, ingredients and progress so far. You can run the same program many times at once, for example two terminal windows, and each one is a separate process with its own memory and its own place in the recipe.

What is a process?

For every process, the kernel keeps a record, the process control block (Linux calls it a task_struct). It holds everything the kernel needs to know about the process:

A number that identifies it, the process ID or PID, and the PID of its parent, the process that started it.
Its own address space: its page tables (Chapter 10), so it sees its own memory and nobody else's.
A copy of its registers, saved whenever it isn't running, so it can carry on later exactly where it stopped.
Its open files, the user it runs as, its priority, how much CPU time it has used, and its state.

A process can also have several threads: separate paths through the same program, each with its own registers and stack, but all sharing one address space. A web browser uses threads to download, draw and run scripts at the same time. The kernel schedules each thread separately. On the computer this book was written on, at the moment we checked, there were 543 processes with 2,361 threads between them.

Running, ready or blocked

At any moment, each process is in one of a few states:

Running: its instructions are executing on a processor core right now.
Ready: it could run, but it's waiting for its turn on a core.
Blocked (Linux says "sleeping"): it's waiting for something else, like a key press, data from the disk or network, or a timer. Giving it the CPU would be pointless.

A process moves between these states all the time. A running process that asks to read the disk becomes blocked; when the disk's interrupt arrives (Chapter 12), the kernel marks it ready again. A running process whose time is up goes back to ready. Here's what the 543 processes were doing when we looked:

$ ps -e -o stat= | cut -c1 | sort | uniq -c
    134 I      ← idle kernel threads, waiting for work
      1 R      ← running: most likely ps itself
    405 S      ← sleeping (blocked), waiting for something
      2 Z      ← zombies: finished, see below

Almost everything is blocked, almost all the time. A typical program spends its life waiting for you, and that's what makes sharing the processor work so well.

The context switch

Switching the processor from one process to another is called a context switch. It happens when a process blocks, or when the timer interrupt (Chapter 12) tells the kernel that the current process has had its turn. The kernel saves the registers of the old process, loads the registers of the new one, and switches the page tables.

Step through a switch from the text editor to the music player. Watch the CPU's registers, and the two process control blocks.

On the computer this book was written on, the timer interrupts each busy core up to 1,000 times a second. We measured a switch by making two processes take turns on one core, passing a single byte back and forth: about 1.1 microseconds per switch, including the two system calls to send and receive the byte. That's a few thousand instructions' worth of time. There's also a hidden cost: the new process finds the caches and the TLB (Chapters 9 and 10) full of the old process's data, so it runs slowly for a while.

Who runs next?

The scheduler is the part of the kernel that picks the next process. It has to balance goals that pull in different directions:

Responsiveness: when you press a key, the text editor should react at once.
Throughput: big jobs, like compiling a program or encoding a video, should finish as soon as possible, without wasting time on switching.
Fairness: no process should be left waiting forever.

Processes come in two flavours. CPU-bound processes, like a video encoder, would happily use the processor all day. I/O-bound processes, like a text editor, run for a moment and then block again, waiting for the next key. A good scheduler lets the I/O-bound ones jump in quickly, because they'll give the CPU back almost at once.

Four processes share one core for 30 time slots. Try each policy, and compare how long the editor and the music player have to wait, and how long the big jobs take to finish.

Each policy wins something and loses something. Real schedulers combine these ideas. Since 2007, Linux's scheduler has followed the "fair share" idea: it tracks how much CPU time each process has had, and favours those that have had the least. Since 2023 it uses a version called EEVDF, which also takes into account how soon each process needs to run. You can adjust a process's share with its nice value, from −20 (greedy) to 19 (very polite); special real-time processes, like audio software, can be given strict priority over everything else.

A modern computer has many cores, so the scheduler keeps a separate queue of ready processes for each core, and moves processes between them to keep all the cores busy. The computer this book was written on has 20 logical cores, so up to 20 threads can really run at the same instant.

Starting a program: fork and exec

New processes don't appear out of nowhere: every process is started by another one. The very first, PID 1 (on Linux, usually systemd), is started by the kernel itself at the end of booting. All the others descend from it, forming a family tree.

Unix systems, including Linux and macOS, start a program in two surprising steps. First, fork() makes a copy of the process that calls it. Then the copy calls exec() to replace itself with a different program. The two-step design is a little strange, but simple and flexible: between the two steps, the child can rearrange its own open files, which is how the shell sends a program's output into a file or a pipe.

Follow the shell as it runs the ls command, one system call at a time.

Windows does it differently, with a single call, CreateProcess, that builds the new process and loads its program in one go.

When a process ends, it doesn't disappear completely at once. Its parent may want to know how it went, so the kernel keeps a tiny record holding its exit status until the parent collects it with wait(). Until then, the finished process is a zombie, like the two on our list above. If a parent dies first, its children are adopted by PID 1, which collects them.

Meanwhile, inside a real CPU

Here's the shell running a command for real, traced with strace, showing only the process system calls. (The clone call is how Linux's fork() works today.)

$ strace -f -e trace=clone,execve,wait4,exit_group bash -c 'ls -d /tmp; echo done'
                                                   (trimmed)
execve("/usr/bin/bash", ["bash", "-c", "ls -d /tmp; echo done"], …) = 0
clone(child_stack=NULL, flags=…|SIGCHLD, …) = 3337490      ← fork: child's PID
[pid 3337489] wait4(-1,  <unfinished ...>                    ← parent waits
[pid 3337490] execve("/usr/bin/ls", ["ls", "-d", "/tmp"], …) = 0
/tmp
[pid 3337490] exit_group(0)             = ?
[pid 3337490] +++ exited with 0 +++
<... wait4 resumed>[{WIFEXITED(s) && WEXITSTATUS(s) == 0}], 0, NULL) = 3337490
done

The same calls have different numbers on our two instruction sets. RISC-V doesn't even have a separate fork call, only the more general clone:

               x86-64 (rax)    RISC-V (a7)
clone               56             220
fork                57              —
execve              59             221
wait4               61             260
exit_group         231              94

We measured the costs with two small C programs:

context switch (two processes, one core):   about 1.1 µs
fork + exit + wait:                          about 0.1 ms
fork + exec("/bin/true") + wait:             about 0.45 ms

Finally, the kernel counts every switch. The desktop shell, which draws the windows on this computer, had been running for almost 12 days:

$ grep -E 'Name|State|Threads|ctxt' /proc/$(pgrep -x gnome-shell)/status
Name:	gnome-shell
State:	S (sleeping)
Threads:	27
voluntary_ctxt_switches:	46794671     ← it blocked by itself
nonvoluntary_ctxt_switches:	1304057  ← its time slice ran out

Over 97% of its switches were voluntary: it ran briefly and then blocked to wait for something, exactly like the I/O-bound processes in the scheduler demo.

Try it yourself

The timer interrupts 1,000 times a second, and a context switch takes about 1.1 µs. If the kernel switched process on every single tick, what fraction of the time would it spend switching?
Show answer
Ticks come every 1 ms = 1,000 µs, so 1.1 µs per tick is about 0.1% of the time. Switching is cheap; the hidden cost of cold caches is usually bigger.
In the scheduler demo, with "First come, first served", why does the text editor have to wait 16 time slots before it first runs?
Show answer
It's third in the queue. The video encoder runs for its whole 10 slots, then the compiler for its 6, and only then does the editor get the CPU: 10 + 6 = 16.
A program prints "hello" just after calling fork(). How many times does "hello" appear?
Show answer
Twice: once from the parent and once from the child, because both carry on from the same point after fork() returns.
Why is copy-on-write such a good idea for fork()?
Show answer
Usually the child calls exec() almost at once, which throws away all of its memory. Copying it first would be wasted work. With copy-on-write, only the few pages that get written before the exec() are actually copied.
What happens to a zombie if its parent never calls wait()?
Show answer
It stays a zombie as long as the parent lives, taking up a slot in the process table but no memory to speak of. When the parent finally exits, the zombie is adopted by PID 1, which collects its status, and it disappears.

What we learned

A process is a running program, with its own address space, saved registers, open files and a PID. Threads share one address space.
Each process is running, ready or blocked; most of them are blocked, most of the time.
A context switch saves one process's registers, switches page tables and restores another's: about a microsecond.
The scheduler balances responsiveness, throughput and fairness. Linux favours the processes that have had the least CPU time.
Unix starts programs with fork() (copy, with copy-on-write) and exec() (replace); the parent collects the exit status with wait().

We've now followed the whole machine, from transistors to an operating system running hundreds of programs at once. It's time to write those programs. Part VIII starts with the language the processor actually speaks: x86-64 assembly, side by side with RISC-V.