What an Operating System Does: Abstraction, Scheduling and Virtual Memory

0. Key points

• Boiled down, an operating system has two jobs: abstraction, which hides the awkward differences between pieces of hardware, and resource management, which hands out finite resources to several programs. Together they support the everyday fact that many programs run at once without destroying one another.
• Enforcing abstraction and management requires cooperation from the hardware. Privileged mode and interrupts are the substance of that cooperation, and the system call is the entrance from a program into the operating system.
• The allocation of the CPU — scheduling — can be treated mathematically. In a single-CPU, non-preemptive model in which all jobs arrive simultaneously, shortest job first (SJF) minimises the average waiting time (Theorem 4.1). There are, however, good reasons why real operating systems do not use SJF.
• Memory is allocated by paging: virtual addresses are mapped to physical frames in fixed-size units, and multi-level page tables together with the TLB bring this scheme within practical bounds of speed and capacity (Proposition 5.3, Proposition 5.5).
• The quality of a replacement algorithm is also a matter for theorems. FIFO can get worse when memory is enlarged (Example 5.7), whereas LRU never exhibits this anomaly (Theorem 5.8).
• The safety of concurrent execution reduces to avoiding deadlock. Four conditions are all necessary for a deadlock to occur (Theorem 6.4), and breaking any one of them prevents it.

1. Motivation: what goes wrong on bare hardware

As we saw in Computer Architecture and the Structure of the CPU, a CPU is nothing but a machine that repeats a simple loop: fetch an instruction from memory, decode it, execute it (Definition 6.1［Computer Architecture and the Structure of a CPU］, Example 7.1［Computer Architecture and the Structure of a CPU］). Now consider the situation with no operating system at all: you switch the machine on and your program alone owns the CPU. Most computers before the 1970s worked this way, and so do the smallest embedded devices today.

What is the trouble? Counting naively, there are at least four difficulties.

First, hardware differences leak into the program. To write a single byte to a disk you must know the register layout and the command protocol of that particular disk controller. Change the controller and the program has to be rewritten. It is plainly unreasonable that the same intention — “save this to a file” — should become different code on every model of machine.

Second, resources are fought over. Suppose we want two programs to run at once. There is only one CPU (or a few), and physical memory is finite. Somebody has to decide who uses the CPU and when, and which program may use which addresses.

Third, there is no isolation. When a bug in program A runs off the end of its addresses and corrupts program B’s data, or when a malicious program goes looking for someone else’s password, nothing stands in the way.

Fourth, runaway programs cannot be stopped. If a program enters an infinite loop, the CPU executes it forever, and no other program ever gets a chance to run.

The operating system is the software that answers all four at once. It answers the first with abstraction (providing hardware-independent notions such as files, sockets and processes), the second with resource management (scheduling and memory management), and the third and fourth with protection (enforcement by means of privileged mode and interrupts).

Note

The phrase “an operating system abstracts the hardware” is often misread as “it makes the hardware easier to use”. The essence, however, is not convenience but the insertion of one unbreakable boundary between programs and hardware. Precisely because the boundary cannot be broken, programs can share a machine without trusting their neighbours.

2. Preliminaries: privileged mode and interrupts

The operating system can enforce its boundary not because it is somehow superior, but because the CPU has two modes of execution.

Definition 2.1（Privileged mode and user mode）

A CPU has an execution mode represented by one bit (or more) of a status register.

• In kernel mode (privileged mode, supervisor mode) every instruction may be executed, and all of physical memory and all input/output devices are accessible.
• In user mode the privileged instructions — changing the configuration of the memory management unit, disabling interrupts, direct access to I/O ports, writing the mode bit itself, and so on — may not be executed; an attempt to execute one causes the hardware to raise an exception. Moreover the memory that can be accessed is limited to the range permitted by the address translation machinery described below.

A transition from user mode to kernel mode occurs only through the few entrances fixed by the hardware (traps, interrupts and exceptions), and the address at which execution resumes is determined by a vector that the kernel has set up in advance.

That last sentence is the crux of protection. A user program can cause the machine to enter kernel mode, but it cannot run code of its own choosing in kernel mode, because every transition lands at an address prepared by the operating system.

The second tool is the interrupt. A timer interrupt forcibly suspends execution at a fixed period (of the order of 1 to 10 milliseconds in most operating systems) and transfers control to the kernel. Thanks to it, the operating system can take the CPU back even from a program stuck in an infinite loop. This is the answer to the fourth difficulty.

Definition 2.2（System call）

The prescribed procedure by which a program in user mode requests a service of the operating system. Executing the dedicated instruction defined by the ISA (Definition 8.1［Computer Architecture and the Structure of a CPU］) — syscall on x86-64, ecall on RISC-V, svc on ARM — switches the CPU to kernel mode and resumes execution at the address of a trap handler configured beforehand. Arguments are passed in registers or through memory, and the kind of request is specified by a system call number. When it has finished, the kernel returns to user mode with a return-from-trap instruction (sret on RISC-V, for example).

flowchart LR
U["User mode: application"] -->|"ecall / syscall instruction"| T["Trap handling (address set by the kernel)"]
T --> K["Kernel mode: the OS performs the service"]
K -->|"sret / sysret instruction"| U
H["Timer, devices"] -.->|"interrupt"| T
E["Invalid address access, privileged instruction"] -.->|"exception"| T

The round trip between user mode and kernel mode. The entrances from a program into the operating system are few.

When you write read(fd, buf, n) in C, this round trip is what actually happens. The library function read packs the arguments into registers and executes the syscall instruction; the kernel resolves the file descriptor fd, asks the disk driver to perform the read, copies the result into buf and returns. The program knows nothing about the disk controller. This is the answer to the first difficulty.

3. Processes: the abstraction of a program in execution

Definition 3.1（Process）

A process is the operating system’s abstraction of a program in execution, realised as the following collection of information.

1. Address space: the whole of the virtual addresses the process sees, together with the contents of each of its regions (code, data, heap, stack).
2. CPU execution context: the values of the program counter, the general-purpose registers, the stack pointer and the status register.
3. Kernel-managed resources: the table of open file descriptors, signal settings, parent-child relationships, statistics of resource usage, and so on.
4. State: one of running, ready or blocked.

The kernel data structure that holds all of this together is called the process control block (PCB).

The abstraction of a process gives us two things. One is virtualisation of the CPU: a single CPU is in fact being time-shared, yet each process sees what looks like a CPU of its own. The other is virtualisation of memory, which we treat from Definition 5.1 onwards.

Definition 3.2（Context switch）

The operation of moving the CPU from a running process $P$ to another process $Q$. The kernel (a) saves $P$‘s registers into $P$‘s PCB, (b) switches the page table base register of the memory management unit to $Q$‘s, (c) restores $Q$‘s registers from $Q$‘s PCB, and (d) returns to $Q$‘s user mode.

A context switch has a direct cost (saving and restoring registers, well under a few microseconds) and an indirect cost (the loss of performance until the caches and the TLB have been refilled with the new process’s contents, often larger than the direct cost). Because of this cost, “make the time slice as fine as you like” is not a workable policy.

4. CPU scheduling

When several processes are ready to run, the scheduler decides which one runs next. Let us first fix the measures. Suppose process $i$ arrives at time $a_i$, needs the CPU for a total of $t_i$ (this $t_i$ is called its burst time), and completes at time $c_i$.

• Waiting time $w_i = (c_i - a_i) - t_i$: the total time during which it was ready but not running.
• Response time $r_i$: the time from arrival until it first obtains the CPU.
• Turnaround time $c_i - a_i$.

Interactive workloads care about response time; batch workloads care about average waiting time. The two cannot be optimised simultaneously. For the average waiting time there is a clean answer.

Theorem 4.1（Optimality of shortest job first）

Suppose $n$ processes all arrive at time $0$ and their burst times $t_1, \ldots, t_n > 0$ are known. Assume there is one CPU, that a process once started runs to completion without interruption (non-preemptive), and that the cost of a context switch is $0$. Then the order that runs the processes in increasing order of burst time (shortest job first, SJF) minimises the average waiting time.

Proof（Theorem 4.1）

Represent an execution order by a bijection $\pi : \{1,\ldots,n\} \to \{1,\ldots,n\}$, where $\pi(k)$ is the process run $k$-th. Since all processes arrive at time $0$ and there is no interruption, the waiting time of the process run $k$-th is the sum of the burst times of the processes run before it:

$$w_{\pi(k)} = \sum_{j=1}^{k-1} t_{\pi(j)} .$$

Let us rewrite the total waiting time $W(\pi) = \sum_{k=1}^{n} w_{\pi(k)}$ by exchanging the order of summation and collecting terms in $j$. The term $t_{\pi(j)}$ occurs for $k = j+1, j+2, \ldots, n$, that is in $n-j$ of the terms, so

$$W(\pi) = \sum_{k=1}^{n}\sum_{j=1}^{k-1} t_{\pi(j)} = \sum_{j=1}^{n} (n-j)\, t_{\pi(j)} .$$

Now suppose $\pi$ is not in increasing order. Then there are adjacent positions $j, j+1$ with $a := t_{\pi(j)} > t_{\pi(j+1)} =: b$ (for if $t_{\pi(j)} \le t_{\pi(j+1)}$ held for every adjacent pair, the whole sequence would be increasing). Let $\pi'$ be the order obtained by swapping these two. All terms other than $j$ and $j+1$ are unchanged, so

$$W(\pi') - W(\pi) = \bigl[(n-j)b + (n-j-1)a\bigr] - \bigl[(n-j)a + (n-j-1)b\bigr] = b - a < 0 .$$

The swap therefore strictly decreases the total waiting time. Since there are only finitely many orders ($n!$ of them), an order attaining the minimum exists, and by what we have just shown it must be increasing. Conversely the increasing order is unique (up to the arrangement of processes with equal burst times) and all such orders give the same value. The average waiting time is $W(\pi)/n$, so the same order minimises the average as well.

∎

Remark 4.2

Theorem 4.1 is elegant, but a real operating system cannot use it as it stands, for two reasons. First, the burst time $t_i$ is not known in advance (if it were, we would know whether a program halts; on the fundamental limits of predicting a program’s run-time behaviour without running it, see Theorem 5.6［Programming Language Theory］). Second, long jobs suffer starvation: as long as short jobs keep arriving, a long job never runs. Practical schedulers estimate $t_i$ by an exponential moving average of past burst lengths, and combine this with aging, which raises a process’s priority in proportion to how long it has been kept waiting.

To guarantee interactive response times we use a scheme that cuts execution short by force after a fixed time.

Proposition 4.3

Consider round-robin scheduling: the ready processes are placed in a circular queue, each is given the CPU for a fixed time quantum $q > 0$, and a process that uses up its quantum is returned to the end of the queue. Suppose there are at most $n$ ready processes at any time and that one context switch takes time $s \ge 0$. Then every process that becomes ready obtains its first slice of CPU time within $(n-1)(q+s)$. Moreover, if every process uses up its full quantum (never terminating or blocking part way through), the effective CPU utilisation is $q/(q+s)$.

Proof（Proposition 4.3）

Consider the moment at which a process $P$ joins the end of the queue. At most $n-1$ processes stand ahead of $P$. Under round robin each process occupies the CPU for at most $q$ per turn, followed by one context switch (time $s$), so the time spent on each process ahead of $P$ is at most $q + s$. If a process ahead of $P$ terminates or blocks without using up its quantum, less time is spent. Hence the time before $P$ obtains the CPU is at most $(n-1)(q+s)$.

As for utilisation, as long as the queue is non-empty the time axis is filled by the repetition “run for $q$, switch for $s$”. The fraction of the CPU spent on useful work is therefore $q/(q+s)$. Note that if some process terminates or blocks without using up its quantum, the number of switches is unchanged while the running portion is shortened, so this ratio can fall.

∎

These two statements give the design rule for the quantum $q$. Making $q$ smaller improves the response-time bound $(n-1)(q+s)$ but lowers the utilisation $q/(q+s)$. With $s = 5\ \mu\mathrm{s}$ and $q = 1\ \mathrm{ms}$ the utilisation is $1000/1005 \approx 99.5\%$; with $q = 50\ \mu\mathrm{s}$ it is $50/55 \approx 91\%$. Linux’s CFS does not use a fixed quantum but instead picks the process with the smallest accumulated execution time (virtual runtime); the idea is the same, and it imposes a minimum granularity to prevent excessive switching.

Example 4.4（Average waiting and response times under three policies）

Four processes arrive at time $0$ with burst times $t_1 = 24,\ t_2 = 3,\ t_3 = 3,\ t_4 = 6$ (in milliseconds). Take the switching cost to be $0$.

FCFS (in order of arrival, $P_1 \to P_2 \to P_3 \to P_4$): the waiting times are $0,\ 24,\ 27,\ 30$, so

$$\bar{w} = \frac{0+24+27+30}{4} = \frac{81}{4} = 20.25 .$$

The response times are the same $0, 24, 27, 30$, with average $20.25$.

SJF ($P_2 \to P_3 \to P_4 \to P_1$): the waiting times are $0,\ 3,\ 6,\ 12$, so

$$\bar{w} = \frac{0+3+6+12}{4} = \frac{21}{4} = 5.25 .$$

As Theorem 4.1 asserts, this is the minimum.

Round robin ($q = 4$): tracing the execution, $[0,4)$ runs $P_1$ (20 left), $[4,7)$ completes $P_2$, $[7,10)$ completes $P_3$, $[10,14)$ runs $P_4$ (2 left), $[14,18)$ runs $P_1$ (16 left), $[18,20)$ completes $P_4$, and $P_1$ finishes during $[20,36)$. The completion times are $c = (36, 7, 10, 20)$, so the waiting times, being $c_i - t_i$, are $12,\ 4,\ 7,\ 14$ with average

$$\bar{w} = \frac{12+4+7+14}{4} = \frac{37}{4} = 9.25 .$$

The response times are $0,\ 4,\ 7,\ 10$, average $5.25$. Round robin loses to SJF on average waiting time, but the average response time has shrunk from FCFS’s $20.25$ to $5.25$, roughly to a quarter. This is why interactive systems choose round-robin-like policies.

5. Memory management and virtual memory

After the CPU comes memory. When several processes are held in memory at once, the naive allocation “process A starts at physical address 0x1000, B at 0x9000” causes three problems. (i) If A runs off the end of its addresses it corrupts B. (ii) The placement must be known when A is compiled. (iii) A program larger than physical memory cannot be run.

Address translation solves all three at once.

Definition 5.1（Address translation by paging）

Divide the virtual and physical address spaces into pages and frames of the same size $2^{p}$ bytes (typically $2^{12} = 4$ KiB). Decompose a $b$-bit virtual address $v$ as

$$v = \underbrace{\lfloor v / 2^{p} \rfloor}_{\text{virtual page number } \mathrm{VPN}} \cdot 2^{p} + \underbrace{(v \bmod 2^{p})}_{\text{offset}}$$

and, using the page table $T$ maintained per process (a partial map from VPN to physical frame number PFN), define the physical address by

$$\mathrm{phys}(v) = T(\mathrm{VPN}) \cdot 2^{p} + (v \bmod 2^{p}) .$$

Besides the PFN, each page table entry (PTE) carries a valid bit, permission bits for read, write and execute, a bit saying whether user-mode access is allowed, a referenced bit and a modified bit. Touching an address at which $T$ is undefined (valid bit $0$) makes the CPU raise a page fault exception and transfer control to the kernel. This translation is performed in hardware by the memory management unit (MMU), and the physical address of the top of the page table is held in a privileged register (CR3 on x86-64, satp on RISC-V).

The point is that the offset is not translated. Contiguity within a page is preserved, and translation need only work at page granularity.

Address translation by a one-level page table. The offset passes straight through.

Example 5.2（Carrying an address translation through to the end）

Take 32-bit virtual addresses and a page size of 4 KiB ($p = 12$). We translate the virtual address $v = \mathtt{0x00403ABC}$.

The offset is the low 12 bits, that is the last three hexadecimal digits, so it is $\mathtt{0xABC} = 2748$. The virtual page number is

$$\mathrm{VPN} = \lfloor \mathtt{0x00403ABC} / 2^{12} \rfloor = \mathtt{0x00403} = 1027 .$$

Suppose that on looking up entry $1027$ of the page table we find the valid bit set to $1$, the PFN equal to $\mathtt{0x1F2} = 498$, and write permission granted. The physical address is then

$$\mathrm{phys}(v) = 498 \cdot 4096 + 2748 = 2039808 + 2748 = 2042556 = \mathtt{0x001F2ABC} .$$

In hexadecimal one sees that the top five digits have been replaced, $\mathtt{00403} \to \mathtt{001F2}$, while the last three digits $\mathtt{ABC}$ survive untouched.

This mechanism solves the three problems above. (i) A process physically cannot touch a frame that is not listed in its page table, so processes are isolated from one another. (ii) Every process may begin at the same virtual address, so a program can be compiled without knowing where it will be placed. (iii) If we clear the valid bit and evict a page’s contents to disk, then read them back on the page fault raised at the next access, a virtual address space larger than physical memory becomes usable. This is virtual memory.

5.1. The problem that page tables are too large

Implementing Definition 5.1 literally breaks down on capacity. With 32-bit addresses and 4 KiB pages the VPN is 20 bits, hence $2^{20}$ entries; at 4 bytes per entry that is $4$ MiB. This must be resident per process, so 100 processes cost 400 MiB. With 64-bit addresses it is simply impossible.

The remedy is to page the page table itself: split the VPN further and make a tree.

Proposition 5.3

Consider a two-level page table with 32-bit virtual addresses, a page size of 4 KiB and 4-byte PTEs, in which a virtual address is split into the high 10 bits (index into the first level), the next 10 bits (index into the second level) and the low 12 bits (offset). Let $S$ be the set of virtual pages a process actually uses, and let $I = \{\lfloor \mathrm{VPN}/2^{10}\rfloor : \mathrm{VPN} \in S\}$ be the set of first-level indices of the pages in $S$. Then the space occupied by that process’s page table is exactly $(1 + |I|) \times 4\ \mathrm{KiB}$.

Proof（Proposition 5.3）

The first-level table has $2^{10} = 1024$ entries of 4 bytes each, hence $1024 \times 4 = 4096$ bytes $= 4$ KiB. It fits exactly into one page, and exactly one of them is always needed.

A second-level table likewise occupies 1024 entries $\times$ 4 bytes $=$ 4 KiB. One second-level table is provided per first-level index, but if no virtual page with that index is in use, it suffices to clear the valid bit of the corresponding first-level entry and no table need be allocated at all. Conversely, if even one virtual page with that index is in use, one table is allocated. The number of second-level tables allocated is therefore exactly $|I|$, giving a total of $(1 + |I|) \times 4$ KiB.

∎

Example 5.4（Estimating the size for a real process）

Suppose a typical small process has its code and data around $\mathtt{0x00400000}$ and its stack around $\mathtt{0xBFFFF000}$. The first-level index of Proposition 5.3 is the virtual address divided by $2^{22} = 4$ MiB.

$$\left\lfloor \frac{\mathtt{0x00400000}}{4194304} \right\rfloor = \frac{4194304}{4194304} = 1, \qquad \left\lfloor \frac{\mathtt{0xBFFFF000}}{4194304} \right\rfloor = \left\lfloor \frac{3221221376}{4194304} \right\rfloor = 767 .$$

(The latter is confirmed by $767 \times 4194304 = 3217031168$ and $768 \times 4194304 = 3221225472 > 3221221376$.) Hence $I = \{1, 767\}$ and $|I| = 2$, and the page table occupies

$$(1 + 2) \times 4\ \mathrm{KiB} = 12\ \mathrm{KiB} .$$

This is about $1/341$ of the $4$ MiB required by the one-level scheme. x86-64 extends the same idea to four levels ($9+9+9+9+12 = 48$ bits), and RISC-V’s Sv39 uses three ($9+9+9+12 = 39$ bits).

5.2. The problem that translation is too slow

Adding levels reduces the space, but a single memory access now requires walking the table once per level. With four levels, one data access costs five memory accesses in total — a fivefold slowdown.

The remedy is to cache the results of translation, in what is called the TLB (translation lookaside buffer). The TLB is an associative memory inside the MMU holding a few tens to a few thousand recent VPN-to-PFN correspondences.

Proposition 5.5

Suppose a TLB lookup takes time $\varepsilon$ and one access to main memory takes time $m$. Assume the page table has one level, the TLB hit rate is $h$ (with $0 \le h \le 1$), and no page faults occur. Then the average time to read one word of data (the effective access time) is

$$\mathrm{EAT} = \varepsilon + m + (1-h)\, m .$$

Proof（Proposition 5.5）

In either case we consult the TLB first, which costs $\varepsilon$.

On a TLB hit (probability $h$) the PFN is obtained immediately, so all that remains is one main-memory access to fetch the data: $\varepsilon + m$ in total.

On a TLB miss (probability $1-h$) we need one main-memory access to read the page table ($m$) and one to read the data ($m$): $\varepsilon + 2m$ in total.

Taking the expectation,

$$\mathrm{EAT} = h(\varepsilon + m) + (1-h)(\varepsilon + 2m) = \varepsilon + m\bigl[h + 2(1-h)\bigr] = \varepsilon + m(2 - h) = \varepsilon + m + (1-h)m .$$∎

Example 5.6（Why the TLB matters, in numbers）

Take $\varepsilon = 1$ ns and $m = 100$ ns. Without a TLB, even a one-level table costs $2m = 200$ ns, that is twice as long on every access.

With a hit rate $h = 0.98$, Proposition 5.5 gives

$$\mathrm{EAT} = 1 + 100 + 0.02 \times 100 = 103\ \mathrm{ns},$$

so the extra cost of translation is a mere $3\%$. If $h$ drops to $0.90$ then $\mathrm{EAT} = 1 + 100 + 10 = 111$ ns, an increase of $11\%$. A change of a few percentage points in $h$ is perceptible, so keeping the TLB from overflowing is critically important for performance. Large pages (2 MiB huge pages) are used precisely to multiply by 512 the amount of memory covered by the same number of TLB entries.

Note also that a context switch (Definition 3.2) changes the page table, so naively the entire TLB must be invalidated. Modern CPUs attach an address space identifier (ASID or PCID) to TLB entries in order to avoid this wholesale invalidation.

5.3. Which page to evict

When physical memory runs short we must decide which page to evict to disk. The theoretical optimum is “evict the page whose next use lies farthest in the future” (Belady’s optimal algorithm), but it needs knowledge of the future and cannot be implemented. The practical candidates are FIFO (evict whichever was loaded longest ago) and LRU (evict whichever was least recently referenced).

Intuitively one expects that “more frames means fewer page faults”. For FIFO this is false.

Example 5.7（Belady's anomaly: FIFO can get slower when memory is enlarged）

Process the reference string $\sigma = 1,2,3,4,1,2,5,1,2,3,4,5$ with FIFO, starting from empty memory.

Three frames (in brackets, in order of loading, oldest on the left):

Reference	1	2	3	4	1	2	5	1	2	3	4	5
Outcome	F	F	F	F	F	F	F	H	H	F	F	H

At $4$ the oldest page $1$ is evicted, giving $[2,3,4]$; at the next $1$, $2$ is evicted, giving $[3,4,1]$; at the next $2$, $3$ is evicted, giving $[4,1,2]$; at $5$, $4$ is evicted, giving $[1,2,5]$. Here $1$ and $2$ hit consecutively. Then at $3$, $1$ is evicted, giving $[2,5,3]$; at $4$, $2$ is evicted, giving $[5,3,4]$; and the final $5$ hits. There are 9 faults.

Four frames:

Reference	1	2	3	4	1	2	5	1	2	3	4	5
Outcome	F	F	F	F	H	H	F	F	F	F	F	F

The first four references fill $[1,2,3,4]$ and $1, 2$ hit. But the moment $5$ evicts the oldest page $1$, the gears slip: from then on each reference asks for exactly what was just evicted, and every reference from the seventh onwards faults. There are 10 faults.

Adding one frame increased the number of faults from 9 to 10. This is Belady’s anomaly. The cause is that FIFO’s memory contents are not nested with respect to the number of frames.

Theorem 5.8（LRU is a stack algorithm and does not exhibit Belady's anomaly）

Use LRU under demand paging (only referenced pages are loaded, and memory is initially empty). For a reference string $\sigma = \sigma(1)\sigma(2)\cdots$, write $S_m(t)$ for the set of pages in memory immediately after the $t$-th reference has been processed with $m$ frames, and $F_m(t)$ for the number of page faults up to the $t$-th reference. Then for every $m \ge 1$ and every $t \ge 0$,

$$S_m(t) \subseteq S_{m+1}(t) ,$$

and consequently $F_{m+1}(t) \le F_m(t)$ for every $t$.

Proof（Theorem 5.8）

Step 1: characterisation of $S_m(t)$. List the distinct pages occurring in $\sigma(1),\ldots,\sigma(t)$ in decreasing order of their last reference time (most recent first) as $q_1(t), q_2(t), \ldots, q_{d_t}(t)$, where $d_t$ is the number of distinct pages. The claim is that

$$S_m(t) = \{ q_1(t), \ldots, q_{\min(m, d_t)}(t) \} .$$

We prove this by induction on $t$.

For $t = 0$ memory is empty and $d_0 = 0$, so both sides are the empty set.

Assume the claim for $t$ and reference $p := \sigma(t+1)$. In the new recency order $q_\bullet(t+1)$, the page $p$ moves to the front and the relative order of the other pages is unchanged. There are three cases.

(a) $p \in S_m(t)$. This is a hit, so the contents of memory are unchanged and $S_m(t+1) = S_m(t)$. On the other hand, by the induction hypothesis $p$ was among the top $\min(m,d_t)$ in the recency order, so moving it to the front does not change the set of the top $\min(m,d_t)$ pages. Also $d_{t+1} = d_t$. The claim is preserved.

(b) $p \notin S_m(t)$ and $|S_m(t)| < m$. By the induction hypothesis $|S_m(t)| = d_t < m$, that is, memory already contains every distinct page seen so far, so $p$ occurs for the first time. We fault and place $p$ in a free frame, so $S_m(t+1) = S_m(t) \cup \{p\}$. On the other side $d_{t+1} = d_t + 1 \le m$, and the top $\min(m, d_{t+1}) = d_{t+1}$ pages are all pages seen so far together with $p$. The two agree.

(c) $p \notin S_m(t)$ and $|S_m(t)| = m$. We fault, and LRU evicts the page whose last reference is oldest, which by the induction hypothesis is $q_m(t)$, and inserts $p$. Hence

$$S_m(t+1) = \bigl(\{q_1(t),\ldots,q_m(t)\} \setminus \{q_m(t)\}\bigr) \cup \{p\} = \{p, q_1(t), \ldots, q_{m-1}(t)\}.$$

In the new recency order $p$ is first and $q_1(t),\ldots,q_{m-1}(t)$ slide down to positions two through $m$, so the top $m$ pages are exactly this set. The two agree.

This completes Step 1.

Step 2: the inclusion. By Step 1, $S_m(t)$ consists of the top $\min(m,d_t)$ pages in recency order and $S_{m+1}(t)$ of the top $\min(m+1,d_t)$. Since $\min(m,d_t) \le \min(m+1,d_t)$ and both are prefixes of the same order $q_\bullet(t)$, we get $S_m(t) \subseteq S_{m+1}(t)$.

Step 3: monotonicity of the fault count. If the $(t+1)$-st reference $p = \sigma(t+1)$ hits with $m$ frames, that is $p \in S_m(t)$, then by Step 2 $p \in S_{m+1}(t)$, so it hits with $m+1$ frames as well. Contrapositively, if it faults with $m+1$ frames it also faults with $m$ frames. Hence at each time the indicator functions satisfy $\mathbf{1}[\text{fault with } m+1] \le \mathbf{1}[\text{fault with } m]$, and summing up to $t$ gives $F_{m+1}(t) \le F_m(t)$.

∎

Case (c) of Step 1 is exactly the part that fails for FIFO. Because FIFO chooses its victim by order of loading, its memory contents do not take the form “the top $m$ pages in order of recency”, which is nested in $m$, and the inclusion breaks. Example 5.7 is a concrete manifestation of this.

Tip

True LRU requires updating an order on every reference, which is expensive to realise in hardware. Real operating systems approximate LRU by the clock algorithm (second chance), which sweeps around the frames periodically clearing the referenced bits of PTEs. Being an approximation, it carries no guarantee that Belady’s anomaly disappears entirely, but in practice it is almost never a problem.

6. The safety of concurrent execution: mutual exclusion and deadlock

Once processes or threads begin touching shared data, a new kind of error appears.

Definition 6.1（Critical section and mutual exclusion）

A region of code that reads and writes state shared among several agents of execution is called a critical section. The property that at any instant at most one agent is executing the critical section is called mutual exclusion. An exclusion mechanism is said to be correct when, in addition to mutual exclusion, (i) if some agent wants to enter the critical section and nobody is inside, some agent enters within finite time (progress), and (ii) an agent wanting to enter is not made to wait indefinitely (bounded waiting).

For instance counter = counter + 1 becomes three machine instructions — read, add, write — in the code produced by a translator (Definition 3.1［Programming Language Theory］), and if two threads interleave, one update is lost. These three instructions must be protected as a critical section. The operating system provides mutexes and semaphores for this purpose, implemented using the CPU’s atomic instructions (compare-and-swap and the like) together with machinery for removing waiting processes from the scheduler.

Once an exclusion mechanism is introduced, a new state arises in which agents wait for each other and nothing progresses.

Definition 6.2（Deadlock）

A set of processes $D \ne \emptyset$ is deadlocked when every process in $D$ is waiting for the release of a resource held by another process in $D$, and that release cannot occur. Define the wait-for graph to be the directed graph whose vertices are processes and in which an edge $P \to Q$ means “the resource $P$ is requesting is held by $Q$”.

Lemma 6.3

If every vertex of a finite directed graph $G$ has out-degree at least $1$, then $G$ contains a directed cycle.

Proof（Lemma 6.3）

Pick a vertex and call it $v_0$. Since every vertex has out-degree at least $1$, we may choose an edge leaving $v_0$ and call its head $v_1$, then similarly go from $v_1$ to $v_2$, and so walk on forever. As $G$ has a finite number $N$ of vertices, the pigeonhole principle says that among the $N+1$ vertices $v_0, v_1, \ldots, v_N$ some vertex occurs twice; that is, there are $i < j$ with $v_i = v_j$. Then $v_i \to v_{i+1} \to \cdots \to v_j = v_i$ is a directed cycle.

∎

Theorem 6.4（The four necessary conditions for deadlock (Coffman conditions)）

If a deadlock (Definition 6.2) has occurred, then all four of the following conditions hold.

1. Mutual exclusion: at least one kind of resource can be held by only one process at a time.
2. Hold and wait: some process holds at least one resource while waiting for the release of another.
3. No preemption: a resource cannot be taken away from outside; it is released only voluntarily by the process holding it.
4. Circular wait: there is a sequence of processes $P_1, P_2, \ldots, P_k$ ($k \ge 2$) such that for each $i$, $P_i$ waits for a resource held by $P_{i+1}$ (indices modulo $k$, so that $P_k$ waits for $P_1$).

Proof（Theorem 6.4）

Let $D$ be the set of deadlocked processes.

On 1. If every resource could be held simultaneously by any number of processes, every request for a resource would be satisfied immediately and no process would ever be in a waiting state. This contradicts Definition 6.2, according to which every process in $D$ is waiting. Hence at least one kind of resource is exclusive.

On 2. By Definition 6.2, each process $P$ in $D$ is waiting for another process to release a resource. If $P$ held nothing, consider the process $Q \in D$ that $P$ is waiting for. $Q$ too is waiting for someone, and following the chain produces a cycle (as shown in item 4); every process on the cycle is waited for by another and therefore holds a resource. Hence $D$ certainly contains a process that holds a resource while waiting.

On 3. If resources could be preempted, the wait could be resolved by allocating the resource to the waiting process. But then the condition of Definition 6.2 that “the release cannot occur” would fail. Hence there is no preemption.

On 4. Consider the subgraph $G$ of the wait-for graph induced by the elements of $D$. By Definition 6.2, each process in $D$ waits for a resource held by another process in $D$; that is, every vertex of $G$ has out-degree at least $1$. Since $D$ is finite, Lemma 6.3 gives a directed cycle $P_1 \to P_2 \to \cdots \to P_k \to P_1$ in $G$. The definition of the edge $P_i \to P_{i+1}$ is precisely ”$P_i$ waits for a resource held by $P_{i+1}$”, which is circular wait. The length of the cycle is at least $2$ (waiting for a resource one holds oneself can be treated in the same way as a case of circular wait, for ordinary mutexes that do not permit recursive acquisition of the same resource).

∎

Theorem 6.4 says the four conditions are necessary, so by contraposition making any one of them fail prevents deadlock. Practical countermeasures can be classified by which of the four they break.

Condition broken	Technique	Price
Mutual exclusion	Read-only resources, lock-free data structures	Applicable only to a limited class of resources
Hold and wait	Acquire all needed resources at once, up front	Lower resource utilisation; all requests must be known in advance
No preemption	On a failed acquisition, release what is held and retry	Risk of livelock, cost of redoing work
Circular wait	Impose a total order on resources and always acquire in increasing order	Requires the discipline of fixing a total order at design time

The last row is the method most used in practice; the lock-ordering conventions of the Linux kernel are exactly this. Its correctness is left to be proved in Exercise 7.4.

7. Exercises

Exercise 7.1Easy

Consider a machine with a 32-bit virtual address space, a page size of 8 KiB and page table entries of 4 bytes. Using a one-level page table, compute the size of the page table per process. State also the factor by which this differs from the case of a 4 KiB page size.

Solution

Since $8\ \mathrm{KiB} = 2^{13}$, the offset is 13 bits and the virtual page number is $32 - 13 = 19$ bits. There are $2^{19} = 524288$ entries of 4 bytes each, so

$$2^{19} \times 4 = 2^{21} = 2097152\ \text{bytes} = 2\ \mathrm{MiB}.$$

With a 4 KiB page size the VPN was 20 bits and the table was $2^{20} \times 4 = 4$ MiB. Hence the factor is $2\ \mathrm{MiB} / 4\ \mathrm{MiB} = 1/2$: the table is halved.

Larger pages make the page table smaller, but in exchange the unused portion within a page (internal fragmentation) grows on average by half a page. This tug of war is why page sizes have settled around 4 KiB.

Exercise 7.2Standard

Four processes arrive at time $0$ with burst times $t_1 = 8,\ t_2 = 4,\ t_3 = 9,\ t_4 = 5$. Take the switching cost to be $0$. Compute the average waiting time for each of (a) FCFS (order of arrival), (b) SJF, and (c) round robin ($q = 4$, initial queue order $P_1, P_2, P_3, P_4$, a process that uses up its quantum returning to the end of the queue), and confirm that (c) can be worse than (a).

Solution

(a) FCFS: the execution order is $P_1, P_2, P_3, P_4$. The waiting times are $0,\ 8,\ 12,\ 21$, so

$$\bar{w} = \frac{0+8+12+21}{4} = \frac{41}{4} = 10.25 .$$

(b) SJF: increasing order of burst time is $P_2(4), P_4(5), P_1(8), P_3(9)$. The waiting times are $0,\ 4,\ 9,\ 17$, so

$$\bar{w} = \frac{0+4+9+17}{4} = \frac{30}{4} = 7.5 .$$

By Theorem 4.1 this is the minimum.

(c) Round robin with $q=4$: we trace the execution in order.

Interval	Running	Remaining	Queue afterwards
$[0,4)$	$P_1$	4	$P_2, P_3, P_4, P_1$
$[4,8)$	$P_2$	0 (done)	$P_3, P_4, P_1$
$[8,12)$	$P_3$	5	$P_4, P_1, P_3$
$[12,16)$	$P_4$	1	$P_1, P_3, P_4$
$[16,20)$	$P_1$	0 (done)	$P_3, P_4$
$[20,24)$	$P_3$	1	$P_4, P_3$
$[24,25)$	$P_4$	0 (done)	$P_3$
$[25,26)$	$P_3$	0 (done)	—

The completion times are $c = (20, 8, 26, 25)$. Since arrival is at $0$, the waiting times are $c_i - t_i$, that is $12,\ 4,\ 17,\ 20$, so

$$\bar{w} = \frac{12+4+17+20}{4} = \frac{53}{4} = 13.25 .$$

This is worse than FCFS’s $10.25$. When the burst times are all close in value, round robin merely pushes everybody’s completion uniformly backwards, which counts against the average waiting time. The response time, on the other hand, improves from FCFS’s $(0+8+12+21)/4 = 10.25$ to $(0+4+8+12)/4 = 6$, exactly in the spirit of Proposition 4.3.

Exercise 7.3Standard

Process the same reference string $\sigma = 1,2,3,4,1,2,5,1,2,3,4,5$ as in Example 5.7, this time with LRU. Compute the number of page faults with three frames and with four frames, and check that the results are consistent with Theorem 5.8.

Solution

Three frames (contents written in order of recency).

$1$: F, $[1]$. $2$: F, $[2,1]$. $3$: F, $[3,2,1]$. $4$: F, evict the least recent $1$, giving $[4,3,2]$. $1$: F, evict $2$, giving $[1,4,3]$. $2$: F, evict $3$, giving $[2,1,4]$. $5$: F, evict $4$, giving $[5,2,1]$. $1$: H, $[1,5,2]$. $2$: H, $[2,1,5]$. $3$: F, evict $5$, giving $[3,2,1]$. $4$: F, evict $1$, giving $[4,3,2]$. $5$: F, evict $2$, giving $[5,4,3]$.

There are 10 faults.

Four frames.

$1,2,3,4$: F on all four, $[4,3,2,1]$. $1$: H, $[1,4,3,2]$. $2$: H, $[2,1,4,3]$. $5$: F, evict the least recent $3$, giving $[5,2,1,4]$. $1$: H, $[1,5,2,4]$. $2$: H, $[2,1,5,4]$. $3$: F, evict $4$, giving $[3,2,1,5]$. $4$: F, evict $5$, giving $[4,3,2,1]$. $5$: F, evict $1$, giving $[5,4,3,2]$.

There are 8 faults.

Since $8 \le 10$, adding frames reduced the faults, consistently with $F_{m+1} \le F_m$ from Theorem 5.8. Comparing the memory contents at each moment confirms the inclusion as well: after the seventh reference (the reference to $5$), three frames hold $\{5,2,1\}$ and four frames hold $\{5,2,1,4\}$, so indeed $S_3 \subseteq S_4$.

Exercise 7.4Hard

Fix a total order $\prec$ on the set $R$ of all resources and suppose every process obeys the following discipline: whenever a process requests a resource $r$, every resource $r'$ it currently holds satisfies $r' \prec r$ (that is, resources are only ever acquired in increasing order of $\prec$). Prove that deadlock can never occur.

Solution

We argue by contradiction. Suppose a deadlock has occurred. By condition 4 of Theorem 6.4 there is a sequence of processes $P_1, P_2, \ldots, P_k$ ($k \ge 2$) such that for each $i$, $P_i$ waits for a resource held by $P_{i+1}$ (indices modulo $k$).

Write $r_{i+1}$ for the resource $P_i$ is waiting for (it is held by $P_{i+1}$). With this indexing, the following two statements hold simultaneously for each $i$.

• $P_i$ is requesting the resource $r_{i+1}$.
• $P_i$ holds the resource $r_i$ (this $r_i$ is the resource $P_{i-1}$ is waiting for, and it is held by $P_i$).

By the discipline, the resource requested is strictly greater in $\prec$ than the resource held, so

$$r_i \prec r_{i+1} \qquad (i = 1, 2, \ldots, k,\ \text{indices modulo } k).$$

Chaining these from $i = 1$ onwards gives

$$r_1 \prec r_2 \prec \cdots \prec r_k \prec r_1 ,$$

and transitivity of $\prec$ yields $r_1 \prec r_1$. But $\prec$ is a total order and hence irreflexive ($r \prec r$ never holds), a contradiction.

Therefore no deadlock occurs.

Remark: this argument sets the existence of a cycle, guaranteed by Lemma 6.3, against the existence of a quantity $\prec$ that can move in only one direction. The same structure appears in any argument that uses the absence of infinite descending chains in a finite partially ordered set. In practice one documents this $\prec$ as a convention on the order of lock acquisition, and detects violations at run time with verification machinery such as the Linux kernel’s lockdep.

References

• R. H. Arpaci-Dusseau, A. C. Arpaci-Dusseau, Operating Systems: Three Easy Pieces, Arpaci-Dusseau Books, 2018 — the chapters on virtualisation (processes, scheduling, paging) and on concurrency. The full text is available on the official site.
• A. Silberschatz, P. B. Galvin, G. Gagne, Operating System Concepts, 10th ed., Wiley, 2018 — the chapters on processes and threads, CPU scheduling, main memory and virtual memory, and deadlocks.
• A. S. Tanenbaum, H. Bos, Modern Operating Systems, 4th ed., Pearson, 2015 — the chapters on processes and threads and on memory management.
• L. A. Belady, R. A. Nelson, G. S. Shedler, “An anomaly in space-time characteristics of certain programs running in a paging machine”, Communications of the ACM 12 (1969), 349–353. doi:10.1145/363011.363155
• E. G. Coffman, M. J. Elphick, A. Shoshani, “System Deadlocks”, ACM Computing Surveys 3 (1971), 67–78. doi:10.1145/356586.356588
• A. Waterman, K. Asanović (eds.), The RISC-V Instruction Set Manual, Volume II: Privileged Architecture — the privilege modes (M/S/U), ecall and sret, the satp register and the Sv39 page table format. RISC-V specifications page

Appendix: Privileged mode in practice

On x86-64. For historical reasons there are four privilege levels (rings 0 to 3), but only two are actually used: ring 0 (kernel) and ring 3 (user). System calls use the syscall instruction and return with sysret. The base of the page table is held in the CR3 register, and four levels (PML4 → PDPT → PD → PT) are walked to translate a 48-bit virtual address. Since the introduction of virtualisation support (VT-x), a “root mode” has been added below ring 0, allowing a hypervisor to manage the kernels of guest operating systems.

On RISC-V. Being a newer design it is tidier, with three levels: machine mode (M), supervisor mode (S) and user mode (U). M mode is used by the boot process and the firmware, while the operating system kernel runs in S mode. System calls use the ecall instruction; executed from U mode it jumps to the S-mode trap handler (the address held in the stvec register). The return is sret. The satp register holds the base of the page table and the translation scheme together, and one may choose among Sv39 (three levels, 39-bit virtual addresses), Sv48 (four levels) and Sv57 (five levels). The specification is short enough to read through, so I think the RISC-V privileged specification is the best material available for checking how the mechanisms treated in this article are actually laid down in real hardware.

Why two or three levels suffice. Subdividing privilege further does not help, because in the end only one thing matters: that the boundary cannot be broken. Once a single boundary can be drawn, finer protection inside it is more simply obtained — and more easily verified — by applying the same mechanism recursively, building a virtual machine or a sandbox in user space. In the next chapter, Programming Language Theory, we shall see this idea of “drawing a boundary” appear in another guise, as the type system of a language (type soundness（Corollary 5.5）［Programming Language Theory］).