Operating Systems: How One Machine Safely Pretends to Be Many

Right now your phone is running dozens of programs on a handful of cores. A game, a music player, a browser with twenty tabs and the software that keeps your clock right all believe they have the machine to themselves. One of them crashes and the rest carry on. None of them can read the others' passwords out of memory. A file you save survives a battery dying a moment later.

None of this comes free from the hardware. It is the work of one special program, the operating system, whose central job is not to be clever but to be a referee: to share one machine among many programs that do not trust each other, safely and fairly. Nearly every idea in the subject is a way of keeping that promise cheaply.

An OS exists to share one machine safely

Picture a shared flat with one kitchen and no rules. Anyone can use the oven, move anyone's food, or lock the door and never leave. Programs are like that unless something enforces order. The enforcement is built into the hardware, which has (at least) two modes. In user mode a program can do arithmetic and touch its own memory, and nothing else. In kernel mode the code may do anything: talk to the disk, change the memory map, switch off interrupts. Only the operating system's core, the kernel, runs in kernel mode.

A user program that wants anything real, such as reading a file, opening a network connection or getting more memory, has to ask. It executes a special instruction, a system call, which makes the CPU jump to a fixed entry point inside the kernel and switch to kernel mode. The kernel checks the request, does the work, and returns to user mode. The program cannot choose where in the kernel it lands, which is the point: a door with one guarded entrance, not a wall with holes.

A second piece of hardware makes the rule enforceable. A timer interrupt forces the CPU back into the kernel many times a second, so no program can hog the machine by refusing to give it back. Together these give the OS its three duties: virtualise the machine so each program sees its own CPU and memory, manage concurrency so they can overlap without corrupting each other, and make data persist. Those are OSTEP's three "easy pieces" and the plan of what follows.

Processes and threads: programs in motion

A program on disk is just a file. A process is that program running: its code, its memory (the address space), its open files, and the CPU registers where it currently is. The OS keeps one record per process, and the process is the unit of protection: one process cannot touch another's memory. That is why a crashed browser tab, run as its own process, does not take the others with it. On Unix-like systems a new process is made by fork, which clones the caller, and exec, which swaps the clone's program for another.

A thread is a path of execution inside a process. Threads of the same process share its memory but each has its own registers and stack. That sharing is the attraction (cheap to create, easy to cooperate) and the danger, as the sections on races and deadlock show.

At any moment a process is in one of three states: running on a core, ready and waiting for a core, or blocked waiting for something slow like the disk. The OS moves processes between these states constantly. Swapping the running process for another is a context switch: save the old one's registers, load the new one's and switch to its address space. Nothing useful is computed while it happens, so it is pure overhead, and the next idea is about how often to pay it.

Scheduling: who runs next?

If three programs are ready and there is one core, the scheduler must choose. The choice is a trade-off between measurements. Turnaround time is finish time minus arrival time. Waiting time is the time spent ready but not running. Response time is how long until the job first gets the CPU. Interactive programs care about response, batch jobs about turnaround.

The simplest policy is first come, first served. Its flaw is the convoy effect: with three jobs needing 24, 3 and 3 time units arriving in that order, the short ones wait 24 and 27 units behind the long one, for an average wait of 17. Run the shortest job first and the average wait drops to 3, which is provably the best possible average, but it needs to know job lengths in advance and can starve long jobs. Round robin is the compromise: give each job a short time slice, the quantum, then send it to the back of the line. With a quantum of 4, the same three jobs wait 6, 4 and 7 units, about 5.7 on average, and nobody waits long for a first turn.

Set the policy to round robin on the mixed job set and drag the quantum down to 1. Response time becomes excellent, but with a switch cost of 1 the machine spends nearly half its time switching and the average turnaround is about 38 units, against about 15 for first come, first served. Raise the quantum and the policy turns back into first come, first served. Real schedulers sit in the middle: Linux used the Completely Fair Scheduler from 2007, and since version 6.6 (late 2023) uses a newer design called EEVDF, still built on the same trade-off.

Virtual memory: a private address space for everyone

If every program used real memory addresses, one program's bug could scribble on another's data, and no program could be placed in memory without knowing what was already there. So the OS gives each process virtual addresses that start at zero, as though it owned all of memory, and the hardware's memory-management unit translates every access into a real physical address.

Translation works on fixed-size blocks called pages, usually 4 KiB. A virtual address splits into a page number and an offset within the page. The page table, one per process, maps each page number to a physical frame; the offset is copied unchanged. If the page is not in memory, the access raises a page fault and the kernel steps in: it may fetch the page from disk, or stop a program that was never allowed to touch it.

The default address, 0x2A5C, is page 2, offset 0xA5C. Page 2 lives in frame 7, so the physical address is 0x7A5C. Drag into page 1 or page 5 and you get a page fault. On a modern 64-bit PC a virtual address has 48 usable bits: a 12-bit offset plus four levels of 9-bit page-table indexes (9 × 4 + 12 = 48), for 2⁴⁸ bytes, or 256 TiB, of address space per process. The tables are sparse, so only the parts in use cost memory. Because a translation would otherwise add several memory reads to every access, a small cache of recent translations, the TLB, sits in the CPU; this is the hardware from Computer Architecture doing the OS a favour.

The costly case is a page fault that goes to disk. Using the figures from the architecture piece (RAM about 100 ns, an SSD read about 150 µs), if just one access in a thousand faults, the average access time is 100 + 0.001 × 150,000 = 250 ns, 2.5 times slower than RAM alone. When there are too few frames, the system spends its time swapping pages in and out and gets nothing done, called thrashing. Choosing which page to evict is a policy question you can try:

On the first string, FIFO with 3 frames faults 9 times and with more memory (4 frames) faults 10 times. This is Belady's anomaly: for FIFO, extra memory can hurt. LRU never does that, and tracks Optimal better because programs show locality, as the cache section of the architecture piece described. Real systems approximate LRU cheaply.

Races and locks: when two threads touch one thing

Two threads each run counter = counter + 1. It looks like one step but is three: load the value into a register, add one, store it back. If the threads interleave, both can load 0, both compute 1, and both store 1. The counter is 1 instead of 2: one update is lost. This is a race condition: the result depends on the timing, and the timing is outside your control.

The cure is a lock (mutex). A thread must hold the lock to enter the critical section, and only one thread can at a time, so the three steps can no longer be torn apart. Locks themselves rest on a hardware atomic instruction, such as compare-and-swap, which reads and changes a value in one indivisible step.

Step thread 1 once (load), then thread 2 through all three steps, then thread 1 to the end: the final counter is 1. With the lock switched on, thread 2 is blocked until thread 1 lets go, and no ordering gives the wrong answer. If each step were given to either thread by a coin flip, an unlocked run would lose an update three times in four. Real threads run long stretches between switches, so the bug is far rarer and shows up only occasionally, under load, on someone else's machine. That is what makes races so hard to debug.

The worst version of this story is the Therac-25, a radiation-therapy machine. Between June 1985 and January 1987 it gave at least six patients massive overdoses. In their 1993 investigation, Nancy Leveson and Clark Turner traced one failure to a race: if an operator edited the treatment settings quickly enough, the machine could be left configured differently from what the screen showed. They also stressed that this was not the only cause: earlier models had hardware safety interlocks that the Therac-25 replaced with software, and the investigators blamed overconfidence in software and poor follow-up of accident reports as much as the bug.

Deadlock: waiting in a circle

Locks fix races and create a new problem. Suppose thread 1 locks A and then wants B, while thread 2 has locked B and now wants A. Each holds what the other needs, and neither will let go. Nothing crashes; the program simply stops. This is deadlock. It needs four conditions, listed in a 1971 survey by Coffman, Elphick and Shoshani: mutual exclusion (locks are exclusive), hold and wait (a thread holds one lock while asking for another), no preemption (locks can't be taken away) and circular wait (a loop of threads each waiting for the next). Break any one and deadlock cannot happen.

The cheapest fix is to break circular wait: always take locks in the same global order. Dijkstra posed the classic version in 1965 and Tony Hoare retold it as five philosophers sharing five forks, each needing two to eat; if all grab their left fork at once, all starve.

With opposite orders, step thread 1 once and thread 2 once: both are now stuck. With a coin-flip scheduler half of all runs end this way. With the same order, 0% do, however the steps interleave. The bug is again timing-dependent, which is why it can lie dormant for months.

File systems: names and blocks that survive a crash

A disk offers only numbered blocks. A file system turns that into files with names and directories. The key structure is the inode, a small record per file holding its size, permissions and the locations of its data blocks. A directory is just a file mapping names to inode numbers. To save space for small files while still allowing huge ones, an inode holds a few direct block pointers and then pointers to blocks of pointers, indirect blocks, nested up to three levels.

With 4 KiB blocks one block holds 1,024 pointers. The 12 direct pointers cover 48 KiB, one single-indirect block covers 4 MiB more, double indirect 4 GiB, triple indirect 4 TiB, for a layout limit of about 4 TiB. A small file needs one block read after the inode; the end of a huge file needs four. The shape is a tree that is shallow for the common case, a pattern you will meet again in databases.

The hard problem is the crash. Appending to a file changes several blocks: the data, the inode, the free-space map. If power fails after one is written and before the others, the disk contradicts itself. The first remedy was a slow repair scan on reboot. The modern one is journaling: first write a note of what you are about to do into a log, then do it, so after a crash the system replays or discards the log. It is the same idea as a bank writing a transaction ledger before moving the money.

What a graduate just sees

• The OS is a referee: the hardware's user/kernel split is what lets mutually distrustful programs share one machine.
• Every request for anything real, whether file, network or memory, is a system call through one guarded door.
• A process owns an address space; a thread only owns a path through someone else's.
• Scheduling is a trade-off between waiting, finishing and switching, and there is no best policy.
• Memory addresses are fiction: a table translates them, and a missing page costs a disk trip.
• A bug that depends on timing will hide in testing and appear in production.
• x = x + 1 is three steps, and any shared state needs a lock.
• Take locks in a fixed order, or two of them will eventually wait for each other forever.
• A file is an inode plus pointers, and crash safety means writing down your intentions first.

Where it shows up next

• Computer Networks (34/27): a network connection is a file-like handle from a system call, and the kernel's network stack and its interrupts deliver every packet.
• Computer Security (34/33): the user/kernel boundary, permissions and address-space isolation are the foundation of every defence, and race conditions between a check and a use are a classic attack.
• Databases (34/28): a database re-implements this subject: its buffer pool is paging, its transactions use locks and deadlock detection, and its write-ahead log is a journal.
• The cloud: containers are ordinary processes fenced off by kernel features, and virtual machines extend the virtual-memory trick to a whole computer.
• Software Engineering (34/31): every multithreaded program inherits the race and deadlock problems here, and most advice about concurrency exists to avoid them.

If you want to go deeper

• 📘 Free and the best first book: Remzi and Andrea Arpaci-Dusseau, Operating Systems: Three Easy Pieces (OSTEP), free online: virtualisation, concurrency and persistence, widely praised for its clear treatment of scheduling and paging.
• 📘 Textbook: Silberschatz, Galvin and Gagne, Operating System Concepts (10th ed.). The most widely assigned survey; strong on the tables of algorithms.
• 📘 Textbook: Andrew Tanenbaum and Herbert Bos, Modern Operating Systems (5th ed., 2022). A more narrative alternative with case studies of Linux, Windows and Android.
• ▶️ Gentler: Crash Course Computer Science, episode 18, "Operating Systems" (about 14 minutes), a first look at the same ideas.
• 🌐 Free course: MIT OpenCourseWare 6.1810 Operating System Engineering: you read and extend a small teaching kernel, xv6, whose free book is by Cox, Kaashoek and Morris.