Operating systems and the Linux kernel

A parameter sweep starts 100 000 runs of a small serial program, each run as a new process. On the machine used for this chapter, creating and ending one process that prints one line takes 0.46 to 0.70 ms when the program is linked dynamically and 0.31 to 0.42 ms when it is linked statically (five runs of the program in the section on launching). The sweep therefore spends 46 to 70 s, or 31 to 42 s, in process creation before any solver computes. The dynamic program makes 35 system calls. Entering and leaving the kernel 35 times costs at least 2.9 µs (35 × 84 ns, the smallest measured call), under 1 % of the launch time. The rest is work done inside the kernel: inside the calls fork, execve and mmap, which copy page tables, build the new address space and map the program and its libraries; in about 70 page faults that the program never requests; and in process exit. This chapter defines the objects that an operating system manages (processes, address spaces, privilege modes, system calls), follows one command, ./hello, from the shell to the first instruction of the program, and measures each step on a Linux kernel. Its structure follows the two lectures: the purpose of an operating system, the layers between a program and the hardware, and the subsystems of the Linux kernel.

Grounded in two recordings of the NPTEL course High Performance Scientific Computing (IIT Bombay): W1L1, Introduction to Operating System, and W1L2, Linux Kernel Explained. Lecture material: the definition of an operating system and the reasons for having one; eight components (kernel, process management, memory management, file-system management, device management, user interface, security and access control, networking); four types of operating system; the history of Unix, MINIX and Linux with milestones from 1991 to 2008; the role of Linux in high performance computing and its characteristics; the layers user, application, operating system and hardware, with the shell, the system libraries and the kernel inside the operating system; the kernel as a bridge between programs and hardware, its monolithic structure and its loadable modules; the kernel subcomponents (process scheduler, memory management, virtual file system, network subsystem, inter-process communication); the library files and the statement that in Linux most things are files. The slides carry the logos of NPTEL and C-DAC. Research extensions: Ritchie and Thompson on Unix (the definitions of image and process, fork, execute, pipes, special files, the shell as an ordinary program; the 1978 revision of the 1974 paper was read); Torvalds's 1992 account of the first posts and releases of Linux; the Tanenbaum–Torvalds exchange of January 1992 on monolithic kernels and microkernels; the Linux kernel documentation (virtual memory, virtual file system, the CFS and EEVDF schedulers, nice levels, the x86-64 entry code, page-table isolation, /proc); the Linux man-pages (syscall, fork, execve, sched, vdso); POSIX.1-2024 (fork); the KernelNewbies release notes of Linux 6.12. Original teaching constructions: the running case and the formal model of this chapter; the decomposition of the launch time; the amortization model of system calls; the fair-share prediction for nice levels; the scheduling example and its proof; the page-table arithmetic; the programs and measurements; the six exercises.

The objects of the chapter and the running case

The chapter studies one kind of system: a computer whose processors run programs in two privilege modes, under a kernel. The definitions below are used in every later section.

Processor and privilege mode. A processor executes the instructions of one thread at a time. At every instant it is in one of two privilege modes. In user mode it refuses privileged instructions (instructions that change the page tables, disable interrupts or halt the processor) and it reaches only the memory that the current page tables mark as accessible to user programs. In kernel mode it executes every instruction and reaches all memory. A privileged instruction in user mode does not execute: the processor raises an exception, which transfers control to the kernel. The program privileged.c in the next section observes this.

Kernel. The kernel is the code and the data that run in kernel mode. A program in user mode cannot read or write them. The section on the kernel shows that the kernel is not a process.

Entry to the kernel. Control passes from user mode to the kernel by one of three events. A system call is a request by the program: it executes a special instruction (syscall on x86-64) after placing a request number and arguments in registers. An exception is a fault caused by the instruction just executed, such as an access to an unmapped address or a privileged instruction in user mode. A page fault is the exception that an access to a virtual address raises when the page that holds it is not mapped, or is not mapped for the kind of access made; the kernel then maps a page or ends the process. An interrupt is a request from a device or a timer, unrelated to the instruction being executed. The kernel documentation of the x86-64 entry code lists these entry points: the syscall instruction, interrupts, and architecturally defined exceptions (Linux kernel documentation, x86 entry code). A signal goes the other way: it is a notification that the kernel delivers to a process. Signal 11, SIGSEGV, reports an invalid memory access or an instruction that the processor refused. On x86-64 this chapter assumes, without a source that it opened, that a privileged instruction in user mode raises a general-protection exception, which Linux reports to the process as SIGSEGV; the observed signal 11 in the next section agrees.

Process and thread. Ritchie and Thompson define an image as "a computer execution environment" that "includes a memory image, general register values, status of open files, current directory and the like", and a process as "the execution of an image" (Ritchie and Thompson, §V). This chapter writes a process as \(P=(A,O,\kappa,\mathcal T)\). \(A\) is its address space, the set of mappings from virtual pages (fixed-size blocks of addresses, 4096 bytes here) to physical page frames (blocks of physical memory of the same size), each with permissions. \(O\) is its table of open files: a map from small integers, the file descriptors, to open files. \(\kappa\) is its credentials, the user and group identity that the kernel checks on file access (chapter 3). \(\mathcal T\) is its set of threads. As in chapter 11, a thread is a sequence of instructions with its own program counter and call stack; every thread has its own register state and its own scheduling state, and the threads of one process share \(A\) and \(O\). The kernel schedules threads: the Linux scheduling manual speaks throughout of the scheduling of a thread (sched(7)). A process with one thread is the case studied until chapter 11.

System call interface. A system call has a number \(n\) and up to six integer arguments. On x86-64 Linux the number goes into register rax, the arguments into rdi, rsi, rdx, r10, r8 and r9, the instruction is syscall, and the result returns in rax (syscall(2), the tables of instruction, number register and argument registers). The C library wraps each call in a function that stores an error code in errno. The time that one call costs is \(t_{\mathrm{sys}}\); the section on the kernel measures it.

The running case. A user types ./hello in a shell. hello is a program that prints one line and ends. Six events lead from the keystroke to the end: (E1) the shell creates a child process; (E2) the child replaces its program by hello; (E3) the kernel builds the new address space and returns to user mode at the first instruction of the new image; (E4) for a dynamically linked program, the dynamic loader maps the C library; (E5) main runs and calls the kernel to write the line; (E6) the process ends and the shell learns the exit status. Four quantities describe the case: the number \(s\) of system calls, the cost \(t_{\mathrm{sys}}\) of one call, the number \(n_f\) of page faults, and the time \(t_{\mathrm{launch}}\) from E1 to E6. The lectures do not follow a command through these events; the chapter does, and it places each lecture topic at the event where it acts.

The machine. All programs of the chapter were built and run on the Intel Core i5-12450H laptop of this book, in a WSL 2 Ubuntu 24.04 guest with gcc 13.3 (8 cores and 12 logical processors by Intel's specification; the guest shows 6 cores of 2 threads, a synthetic view). WSL 2 runs the guest as a virtual machine with its own Linux kernel; uname -sr reports Linux 6.6.87.2-microsoft-standard-WSL2. Three consequences follow. Absolute times in this chapter hold for this guest and not for bare metal. The page size is 4096 bytes, and the kernel is configured with a timer frequency of 250 Hz (a tick every 4 ms) and dynamic preemption; the section with the session below shows the commands. The file /sys/devices/system/cpu/vulnerabilities/meltdown reports Not affected, so the page-table isolation mechanism that adds cost to system calls on some processors is not in use. Every timing is the minimum over several repetitions of the same run, and a timing listing is checked only by its return code: the output printed under it is one sample run on this machine, and the text gives the range over several runs. Other programs shared the machine during some runs. In one run under heavy load from other programs, the first-touch cost of a page rose to 3.0 µs and the fitted time per read call to 416 ns; the ranges in the text come from runs at lower load, and where a loaded run is quoted the text says so.

What an operating system does: multiplexing, protection and abstraction W1L1 0:48

The lecture defines an operating system as software that manages the hardware and software resources of a computer, the first thing loaded on a computer; the slide says that without one a computer "cannot function effectively". It gives eight reasons for having one: complex hardware, security, many concurrent tasks, memory and file storage, interaction with users, peripheral devices, error handling and networking. W1L1 4:37 lists eight components that do this work. The two lists of eight overlap. This section reduces them to three mechanisms, and Table 2.1 assigns each lecture component to the mechanisms it implements.

Multiplexing divides one resource among several users, over time or in space: processor time among threads, physical memory among address spaces, a network link among connections. Protection prevents one process from reading, writing or disabling the resources of another process or of the kernel. Abstraction presents one uniform interface over differing hardware, such as the file, the process and the socket.

Why protection needs two privilege modes. Suppose every program could execute every instruction. A program could disable interrupts and then loop. No timer interrupt would return control to the scheduler, so the processor could not be multiplexed against the will of that program. A program could also change the page-table base register and read any memory. Multiplexing and isolation therefore need a set of instructions that only the kernel can execute, and two privilege modes provide that set. This argument follows from the definitions of the mechanisms. It shows that hardware needs a privilege mode for the isolation to be enforceable, and it does not show that two modes are the only possible design.

The next program tests the argument on this machine. It creates three child processes with fork and reports how each ends; fork is defined in the section on launching, and here only its effect matters: the child runs the chosen function while the parent waits and reads the child's termination status. The first child makes an ordinary system call. The second executes hlt, a privileged instruction that halts the processor. The third stores to address 0, which no mapping covers. The program is specific to x86-64 because of hlt, and its output is the same on every run.

#include <signal.h>
#include <stdio.h>
#include <string.h>
#include <sys/wait.h>
#include <unistd.h>

static void halt_cpu(void)  { __asm__ volatile("hlt"); }              /* privileged instruction (x86-64) */
static void write_null(void) { *(volatile int *)0 = 1; }              /* store to an unmapped address */
static void harmless(void)  { (void)getpid(); }                       /* an ordinary system call */

static void run(const char *name, void (*body)(void))
{
    pid_t pid = fork();
    if (pid == 0) { body(); _exit(0); }
    int status = 0;
    waitpid(pid, &status, 0);
    if (WIFSIGNALED(status))
        printf("%-14s killed by signal %d (%s)\n", name, WTERMSIG(status), strsignal(WTERMSIG(status)));
    else
        printf("%-14s exited with status %d\n", name, WEXITSTATUS(status));
}

int main(void)
{
    run("getpid():", harmless);
    run("hlt:", halt_cpu);
    run("store to 0:", write_null);
    return 0;
}

getpid():      exited with status 0
hlt:           killed by signal 11 (Segmentation fault)
store to 0:    killed by signal 11 (Segmentation fault)

The system call succeeds. The privileged instruction and the store each end the child with signal 11, Segmentation fault. The processor does not execute hlt in user mode, and the kernel, which receives the exception, ends the child. The store to address 0 faults for a different reason: the page tables of the child have no mapping for that address, the kernel's page-fault handler finds no region that contains it, and the kernel delivers the same signal. In both cases the parent continues. A fault in one process does not stop the kernel or the other processes, which is the protection property the argument above requires.

Kinds of operating system, and why high performance computing uses Linux W1L1 9:04

The lecture names four types of operating system, "based on the type of computer they control and the sort of applications they support": single-user single-task (a first-generation mobile phone), real-time (industrial machinery, medical equipment), single-user multitasking (Windows, macOS, Android) and multi-user multitasking (Linux). W1L1 11:58 adds that on an HPC system many users are logged in at once and each has several jobs.

The four boxes do not lie on one axis. Three independent properties are mixed. The first is the number of users that the system serves at the same time. The second is the number of tasks that run concurrently. The third is whether the system guarantees a bound on the time to respond to an event. A real-time system differs from the others on the third property only: a real-time system can serve one task or many. The type "real-time" is therefore not a third value of the property that separates the other three. Linux is multi-user and multitasking by default. It also offers real-time scheduling policies, SCHED_FIFO and SCHED_RR, with static priorities from 1 to 99, which always preempt ordinary threads (sched(7)), and the KernelNewbies summary of Linux 6.12, released on 17 November 2024, reports that the real-time preemption patch set (PREEMPT_RT), developed for about 20 years, was merged into the mainline kernel in that release (KernelNewbies, Linux 6.12; a secondary source).

A multi-user system gives every process credentials \(\kappa\), checks every access to a file or device against them, and keeps the processes of different users apart by the protection mechanism of the previous section. A cluster needs this property because many people share the same nodes. Chapter 3 treats the permission rules.

History. The slide at W1L1 12:40 states that Linux has its roots in Unix, developed in 1969 at Bell Labs by Ken Thompson and Dennis Ritchie, and that Andrew Tanenbaum developed MINIX in the late 1980s, whose limitations led to Linux. Ritchie and Thompson date the earliest of four Unix versions to "circa 1969-70" and say that it ran on the PDP-7 and PDP-9 computers (§I). They add that the second version ran on "the unprotected PDP-11/20 computer" and that the third "incorporated multiprogramming" and ran on the PDP-11/34, /40, /45, /60 and /70. The paper does not link the two facts, but they agree with the argument of the previous section: multiprogramming appeared on the machines that offered memory protection. The same paper describes a system that runs on the PDP-11/70 and the Interdata 8/32, so by 1978 Unix had been ported to a second processor architecture.

Torvalds's own account of the start of Linux consists of newsgroup posts that he collected in 1992 (Torvalds, 1992). On 25 August 1991 he wrote to comp.os.minix that he was "doing a (free) operating system (just a hobby, won't be big and professional like gnu) for 386(486) AT clones". The same collection says that version 0.01 of the sources was made available "sometimes around this time", and that it contained no binaries. The lecture gives September 1991 for the first release. That is consistent with the posts; the exact day is not established by the sources that were opened. Torvalds also writes that the early licence was "much more restrictive than the GNU copyleft" because it allowed no money to change hands, and that this "changed with 0.12", which "was out January 5th" 1992. The lecture states that Linux adopted the GNU General Public License in 1992. The year agrees with Torvalds's account of version 0.12. The passage does not name the licence, so the identity of the licence rests on the lecture. The lecture dates kernel 1.0 to 1994, and the kernel.org archive lists linux-1.0.tar.gz with the date 13 March 1994 (kernel.org, v1.0).

The lecture says that Linus Torvalds joined hands with the GNU project to build a complete free system. Torvalds's post of 5 October 1991 reports that bash, gcc, GNU make and other GNU programs run under the new kernel. This supports the statement: the kernel came from one project, and the compilers, the shell and the utilities from another.

Four statements of the lecture were not checked against a source: the release of the first major distributions, Slackware and Debian, in 1993; the release years of Ubuntu (2004) and Android (2008); and the statement that in 2020 Linux had become the most popular operating system among its users. The chapter does not rely on them.

The Tanenbaum–Torvalds exchange. Twenty-four days after version 0.12, on 29 January 1992, Tanenbaum posted "LINUX is obsolete". He defined the two kernel designs that the next sections use. In a monolithic system "the whole operating system is a single a.out file that runs in 'kernel mode'" and "contains the process management, memory management, file system and the rest". In a microkernel-based system "most of the OS runs as separate processes, mostly outside the kernel", communicating "by message passing". Torvalds replied the same day: "True, linux is monolithic, and I agree that microkernels are nicer" (Open Sources, appendix A). The section on the kernel returns to this exchange with measurements.

Linux in high performance computing. The lecture states at W1L1 15:28 that Linux is "the heart of HPC systems" because many users run many jobs on the same machine. The first half of the reason is the multi-user, multitasking property described above. The TOP500 statistics page for the operating system family could not be read (the page loads its numbers with scripts that were not executed), so this chapter states no share of the TOP500 list for Linux. The lecture also lists the properties of Linux: open source, community support, a kernel base, multi-user multitasking, regular updates, many variants from mobile to server, customization, performance and stability, and several package managers (apt, yum, dnf). Chapter 1 and chapter 6 describe the systems themselves.

The layers between a program and the hardware W1L1 17:05

The lecture's diagram has four layers: the user, the application, the operating system, and the hardware. Inside the operating system it places three parts: the shell, the system libraries, and the kernel. It describes the shell as an interface to the kernel, the system libraries as "a bridge connecting applications and the kernel, offering a standardized and efficient method for applications to engage with the underlying system", and the kernel as the part that talks to the hardware. This section turns each part into an interface that a program can observe.

The shell is a program in user mode. Ritchie and Thompson describe it as a command-line interpreter that "reads lines typed by the user and interprets them as requests to execute other programs" (§VI). The system library, here the C library libc, is a collection of functions that run in user mode. A function such as puts formats data in user mode and, when it needs the kernel, executes a system call. The kernel offers the system call interface defined in the section on the model. The code of the shell, of the library and of the program all runs in user mode. Only the kernel runs in kernel mode.

The sessions of this chapter were run as one script in a fresh directory on the guest; the lines that start with a dollar sign show its commands, and tab characters in the outputs are shown as spaces. The session below builds the one-line program hello twice, once linked dynamically and once linked statically (with the C library copied into the executable). It prints the program interpreter that the dynamic executable requests, and the libraries that each executable needs.

$ cat hello.c
#include <stdio.h>
int main(void) { puts("hello"); return 0; }
$ gcc -O2 hello.c -o hello_dyn
$ gcc -O2 -static hello.c -o hello_static
$ ./hello_dyn
hello
$ readelf -l hello_dyn | grep Requesting
      [Requesting program interpreter: /lib64/ld-linux-x86-64.so.2]
$ ldd hello_dyn
    linux-vdso.so.1 (0x00007ffcc55d2000)
    libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x000075818de00000)
    /lib64/ld-linux-x86-64.so.2 (0x000075818e0b1000)
$ ldd hello_static
    not a dynamic executable

The dynamic executable carries the name of a program interpreter, /lib64/ld-linux-x86-64.so.2, which is the dynamic loader. The loader finds and maps the shared libraries when the program starts. ldd lists three objects for the dynamic executable: linux-vdso.so.1, which is not a file but a small object that the kernel maps into every process (vdso(7)); libc.so.6; and the loader itself. The static executable needs none of them. The tool strace records the system calls of a program. strace was unpacked from the Ubuntu package strace 6.8-0ubuntu2 (apt-get download strace, dpkg -x) without installation, and the sessions run it as ./strace. The first session counts the calls; the second records them in files and shows the ones that matter.

$ ./strace -c ./hello_dyn
hello
% time     seconds  usecs/call     calls    errors syscall
------ ----------- ----------- --------- --------- ----------------
  0.00    0.000000           0         1           read
  0.00    0.000000           0         1           write
  0.00    0.000000           0         2           close
  0.00    0.000000           0         3           fstat
  0.00    0.000000           0         8           mmap
  0.00    0.000000           0         3           mprotect
  0.00    0.000000           0         1           munmap
  0.00    0.000000           0         3           brk
  0.00    0.000000           0         2           pread64
  0.00    0.000000           0         1         1 access
  0.00    0.000000           0         1           execve
  0.00    0.000000           0         1           arch_prctl
  0.00    0.000000           0         1           set_tid_address
  0.00    0.000000           0         2           openat
  0.00    0.000000           0         1           set_robust_list
  0.00    0.000000           0         1           prlimit64
  0.00    0.000000           0         1           getrandom
  0.00    0.000000           0         1           rseq
------ ----------- ----------- --------- --------- ----------------
100.00    0.000000           0        34         1 total
$ ./strace -c ./hello_static 2>&1 | tail -3
  0.71    0.000005           5         1           set_robust_list
------ ----------- ----------- --------- --------- ----------------
100.00    0.000704          44        16           total

$ ./strace -o dyn.txt ./hello_dyn
hello
$ ./strace -o sta.txt ./hello_static
hello
$ grep -c '^[a-z_0-9]*(' dyn.txt sta.txt
dyn.txt:35
sta.txt:17
$ grep -E '^(execve|openat|write|exit_group)' dyn.txt | cut -c1-100
execve("./hello_dyn", ["./hello_dyn"], 0x7ffda73adac0 /* 22 vars */) = 0
openat(AT_FDCWD, "/etc/ld.so.cache", O_RDONLY|O_CLOEXEC) = 3
openat(AT_FDCWD, "/lib/x86_64-linux-gnu/libc.so.6", O_RDONLY|O_CLOEXEC) = 3
write(1, "hello\n", 6)                  = 6
exit_group(0)                           = ?

The dynamic program makes 35 system calls, including the final exit_group, which never returns; strace -c counts 34 completed calls. The static program makes 17, and strace -c counts 16. The 18 calls in the difference belong to the dynamic loader: it opens /etc/ld.so.cache and libc.so.6, reads the header of the library, and maps its segments with mmap (8 calls of mmap in the dynamic program). Exactly one call fails, access("/etc/ld.so.preload"), which returns ENOENT because the file does not exist. The single line that the program prints reaches the kernel as one call, write(1, "hello\n", 6). This is the boundary between the library and the kernel made visible: puts ran in user mode, and the kernel did the output.

The lecture says at W1L2 20:08 that shared libraries are shared by multiple applications and make memory use efficient. The next session tests this on a sleep process. It prints the mappings of the process, and the accounting of the executable part of the C library from /proc/PID/smaps.

$ sleep 5 &
$ awk '{print $1, $2, $6}' /proc/$!/maps | grep -E 'sleep|heap|libc.so|stack|vvar|vdso'
63fb35b82000-63fb35b84000 r--p /usr/bin/sleep
63fb35b84000-63fb35b88000 r-xp /usr/bin/sleep
63fb35b88000-63fb35b89000 r--p /usr/bin/sleep
63fb35b89000-63fb35b8a000 r--p /usr/bin/sleep
63fb35b8a000-63fb35b8b000 rw-p /usr/bin/sleep
63fb5b932000-63fb5b953000 rw-p [heap]
717bcf800000-717bcf828000 r--p /usr/lib/x86_64-linux-gnu/libc.so.6
717bcf828000-717bcf9b1000 r-xp /usr/lib/x86_64-linux-gnu/libc.so.6
717bcf9b1000-717bcfa00000 r--p /usr/lib/x86_64-linux-gnu/libc.so.6
717bcfa00000-717bcfa04000 r--p /usr/lib/x86_64-linux-gnu/libc.so.6
717bcfa04000-717bcfa06000 rw-p /usr/lib/x86_64-linux-gnu/libc.so.6
7ffe16778000-7ffe1679a000 rw-p [stack]
7ffe167c9000-7ffe167cd000 r--p [vvar]
7ffe167cd000-7ffe167cf000 r-xp [vdso]
$ awk '/ r-xp .*libc.so.6/ {f=1} f && /^(Size|Rss|Pss|Shared_Clean|Private_Clean):/ {print} f && /^VmFlags/ {exit}' /proc/$!/smaps
Size:               1572 kB
Rss:                 976 kB
Pss:                  36 kB
Shared_Clean:        976 kB
Private_Clean:         0 kB

The process maps its own program text /usr/bin/sleep, a heap, the C library in five mappings (the dynamic loader is also mapped, and the grep pattern leaves its lines out), a stack, and two kernel-provided regions, [vvar] and [vdso]. In the executable part of the C library (permissions r-xp), 976 kB are resident, and all 976 kB are shared clean pages. The proportional set size is the count of pages a process has in memory, "where each page is divided by the number of processes sharing it" (Linux kernel documentation, /proc). In four observations it was 16, 36, 43 and 45 kB, so on average (the harmonic mean over the pages) 22 to 61 processes shared each page at those moments (976 divided by 45, and 976 divided by 16). The lecture's statement holds: the code of the C library is stored once in physical memory and mapped into every process that uses it. The chapter returns to the [vdso] region in the section on the kernel.

The layering of the lecture is not strict. A program can call the kernel directly without the library, as the later measurement of syscall(SYS_getpid) does. The lecture says that an application goes to the shell first. This is true only at the moment of launching: after the shell has started the program, the shell waits, and the program's own system calls do not pass through it (Ritchie and Thompson §VI: "When the command is finished, the shell resumes its own execution").

From ./hello to the first instruction

The six events of the running case can now be named with the objects of the model. E1. The shell reads the line ./hello. The name contains a slash, so the shell takes it as a path and does not search for it (POSIX.1-2024, Shell and Utilities, §2.9.1.4, Command Search and Execution: the search applies only to a command name that contains no slash; Ritchie and Thompson §VI already allow a command that "may be a path name including the '/' character"). The shell calls fork. Ritchie and Thompson state that after fork "the process splits into two independently executing processes" that "have independent copies of the original memory image, and share all open files" (§5.1). POSIX.1-2024 states that the child "shall be an exact copy of the calling process" except for details such as a unique process identifier (POSIX.1-2024, fork). The Linux manual adds that the two processes "run in separate memory spaces", that at the time of fork both spaces have the same content, and that fork is implemented with copy-on-write pages (the two processes share the pages, read-only, until one of them writes to a page, and then the kernel gives the writer a private copy), so that its only penalty is "the time and memory required to duplicate the parent's page tables, and to create a unique task structure for the child" (fork(2), description and notes). The C library implements fork with the clone system call, as the trace below shows.

E2. The child calls execve. This call "causes the program that is currently being executed by the calling process to be replaced with a new program, with newly initialized stack, heap, and (initialized and uninitialized) data segments" (execve(2)). Ritchie and Thompson describe the same primitive: "All the code and data in the process invoking execute is replaced from the file" (§5.3). E3. ELF (Executable and Linkable Format) is the file format of Linux executables; its program headers list the segments to map, and the header of type PT_INTERP names the program interpreter. For an ELF executable, the kernel opens the file through the virtual file system, reads its headers, and creates the mappings for its loadable segments. For a dynamically linked ELF executable, "the interpreter named in the PT_INTERP segment is used to load the needed shared objects" (execve(2)). The kernel then returns to user mode at the entry point of the new image. In the full trace (dyn.txt, of which the previous section shows the filtered lines), the first calls after execve are brk, mmap, access("/etc/ld.so.preload") and the opening of /etc/ld.so.cache. The dynamic loader makes these calls, so the first user-mode instruction of the new image belongs to the loader. E4. The loader opens libc.so.6 and maps it. E5. The program's main calls puts, which calls write. E6. The program ends with exit_group, and the parent's wait4 returns the child's process number and status. Ritchie and Thompson describe the end: exit "terminates a process, destroys its image, closes its open files", and "the parent is notified through the wait primitive" (§5.5).

The next session traces the shell itself. The shell is started with two commands in sequence, ./hello_dyn; echo done, and strace -f follows the child. It shows only the calls that create, replace, wait for and end processes. The leading number in each line is the process number.

$ ./strace -f -o fork.txt -e trace=execve,clone,wait4,exit_group bash -c './hello_dyn; echo done'
hello
done
$ grep -v -E -e '--- SIG' -e ECHILD fork.txt | cut -c1-120
600   execve("/usr/bin/bash", ["bash", "-c", "./hello_dyn; echo done"], 0x7fffbc2aa428 /* 22 vars */) = 0
600   clone(child_stack=NULL, flags=CLONE_CHILD_CLEARTID|CLONE_CHILD_SETTID|SIGCHLD, child_tidptr=0x70821c038a10) = 601
600   wait4(-1,  <unfinished ...>
601   execve("./hello_dyn", ["./hello_dyn"], 0x636c1c1ec680 /* 22 vars */) = 0
601   exit_group(0)                     = ?
601   +++ exited with 0 +++
600   <... wait4 resumed>[{WIFEXITED(s) && WEXITSTATUS(s) == 0}], 0, NULL) = 601
600   exit_group(0)                     = ?
600   +++ exited with 0 +++

Process 600 is the shell. It calls clone with the flag SIGCHLD, which is how the C library implements fork, and the call returns 601 in the parent. The parent then blocks in wait4. Process 601 calls execve on ./hello_dyn, runs, and ends with exit_group. The wait4 of 600 resumes and returns 601. Process numbers differ from run to run, but the order of the events does not.

The next program performs E1, E2 and E6 itself. It takes no input and prints five lines. The parent calls fork. The child checks that its parent is the process that forked it, flushes its output buffer, and replaces its image by /bin/echo. The parent waits for the child with waitpid and checks three relations. The program prints relations between process numbers and not the numbers, so its output is the same on every run. The child's lines come first because the parent prints only after waitpid returns. The program assumes that /bin/echo exists.

#include <stdio.h>
#include <stdlib.h>
#include <sys/wait.h>
#include <unistd.h>

int main(void)
{
    pid_t parent = getpid();
    pid_t child = fork();                    /* one call, two returns */
    if (child < 0) { perror("fork"); return 1; }
    if (child == 0) {                        /* child: a copy of the parent's image */
        printf("child:  its parent is the process that forked it: %s\n",
               getppid() == parent ? "yes" : "no");
        fflush(stdout);                      /* empty the stdio buffer before the image is replaced */
        execl("/bin/echo", "echo", "child:  image replaced by /bin/echo", (char *)NULL);
        perror("execl");                     /* reached only if execl failed */
        _exit(127);
    }
    int status = 0;
    pid_t done = waitpid(child, &status, 0);
    printf("parent: wait returned the child's pid: %s\n", done == child ? "yes" : "no");
    printf("parent: child exited normally: %s, status %d\n",
           WIFEXITED(status) ? "yes" : "no", WEXITSTATUS(status));
    printf("parent: child pid differs from parent pid: %s\n", child != parent ? "yes" : "no");
    return 0;
}

child:  its parent is the process that forked it: yes
child:  image replaced by /bin/echo
parent: wait returned the child's pid: yes
parent: child exited normally: yes, status 0
parent: child pid differs from parent pid: yes

The first line is printed by the child's own code after fork. The second line is printed by /bin/echo: the child's code no longer exists after execl, which is the replacement of the whole image that the section above describes. The parent's lines confirm that waitpid returned the child's process number, that the child exited normally with status 0, and that the two processes have different numbers, so there are two processes where there was one.

The cost of a launch. Let \(t_{\mathrm{launch}}\) be the wall-clock time from the fork in the parent to the return of waitpid, and \(t_{\mathrm{run}}\) the time that the program then needs for its own work. The fraction of the time that the launch consumes is

The next program measures \(t_{\mathrm{launch}}\) for the one-line program in its two forms, built by the command in the listing. Its inputs are the two executables tiny_dyn and tiny_static. For each form it starts the program 1000 times with fork, execl and waitpid, with the output redirected to /dev/null, and it keeps the smallest time of 7 rounds in which the two forms alternate. It also reads the number of minor page faults of the children with getrusage(RUSAGE_CHILDREN) (a minor fault is a page fault that the kernel resolves without reading from a disk, for example by mapping a zero-filled page or a page already in memory), and it measures the cost of one minor fault as the time to write the first byte of each page of a fresh 64 MiB mapping. The product of the faults per launch and the cost of one fault estimates the time that faults take, under the assumption that a fault during a launch costs as much as a first write to a zero-filled page. That assumption is approximate: a fault on a page of an executable file does other work. The run is checked by its return code, and the output is one sample run.

#define _GNU_SOURCE
#include <fcntl.h>
#include <stdio.h>
#include <sys/mman.h>
#include <sys/resource.h>
#include <sys/wait.h>
#include <time.h>
#include <unistd.h>

#define LAUNCHES 1000

static double now(void)
{
    struct timespec ts;
    clock_gettime(CLOCK_MONOTONIC, &ts);
    return ts.tv_sec + ts.tv_nsec * 1e-9;
}

/* Seconds per minor fault: first write to each page of a fresh 64 MiB mapping. */
static double fault_cost(void)
{
    long page = sysconf(_SC_PAGESIZE), bytes = 64L << 20;
    char *p = mmap(NULL, bytes, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
    madvise(p, bytes, MADV_NOHUGEPAGE);
    double t0 = now();
    for (long off = 0; off < bytes; off += page) p[off] = 1;
    double t = now() - t0;
    munmap(p, bytes);
    return t / (bytes / page);
}

/* Run `path` LAUNCHES times with fork, exec and wait; report time and minor faults per launch. */
static double launch(const char *path, double *faults)
{
    struct rusage before, after;
    getrusage(RUSAGE_CHILDREN, &before);
    double t0 = now();
    for (int i = 0; i < LAUNCHES; i++) {
        pid_t pid = fork();
        if (pid == 0) {
            int null = open("/dev/null", O_WRONLY);
            dup2(null, 1);
            execl(path, path, (char *)NULL);
            _exit(127);
        }
        waitpid(pid, NULL, 0);
    }
    double t = (now() - t0) / LAUNCHES;
    getrusage(RUSAGE_CHILDREN, &after);
    *faults = (double)(after.ru_minflt - before.ru_minflt) / LAUNCHES;
    return t;
}

int main(void)
{
    double fc = fault_cost();
    printf("one minor fault (first touch of a page): %.2f us\n", fc * 1e6);
    const char *prog[] = {"/tmp/hpsc-launch-ch02/tiny_dyn", "/tmp/hpsc-launch-ch02/tiny_static"};
    double best[2] = {1e30, 1e30}, faults[2] = {0, 0};
    for (int r = 0; r < 7; r++)                      /* alternate the two programs in every round */
        for (int k = 0; k < 2; k++) {
            double t = launch(prog[k], &faults[k]);
            if (t < best[k]) best[k] = t;
        }
    for (int k = 0; k < 2; k++)
        printf("%-14s %6.1f us per launch, %5.1f minor faults per launch, faults alone: %4.1f us\n",
               prog[k], best[k] * 1e6, faults[k], faults[k] * fc * 1e6);
    return 0;
}

one minor fault (first touch of a page): 1.72 us
/tmp/hpsc-launch-ch02/tiny_dyn  510.7 us per launch,  69.9 minor faults per launch, faults alone: 120.0 us
/tmp/hpsc-launch-ch02/tiny_static  337.2 us per launch,  43.1 minor faults per launch, faults alone: 74.0 us

In five runs of this program, the dynamic form took 0.46 to 0.70 ms per launch and the static form 0.31 to 0.42 ms; in each run the static form was faster, by a factor of 1.4 to 1.7. The dynamic form took 69.8 to 70.9 minor faults per launch and the static form 43.0 to 44.0. One minor fault cost 1.7 to 2.5 µs in these five runs. The faults therefore account for 118 to 171 µs of a dynamic launch (23 to 30 %) and for 73 to 105 µs of a static launch (22 to 26 %). The share rises with the cost of a fault: in the run under heavy load, the fault cost 3.0 µs and the faults accounted for 211 µs of a 574 µs dynamic launch (37 %) and 130 µs of a 384 µs static launch (34 %). The entry and exit of the system calls account for less: 35 calls of at least 84 ns each (the smallest measured getpid) give at least 2.9 µs, 0.4 to 0.6 % of a dynamic launch, and 17 calls give at least 1.4 µs, 0.3 to 0.5 % of a static launch. These are lower bounds on the cost of entering and leaving the kernel only, because fork, execve, mmap and exit_group also do work inside the kernel. About 70 to 78 % of a launch remains unexplained by the two items, and most of it is time spent inside those calls: the duplication of the page tables in fork, the construction of the new address space and the mappings in execve and mmap, the teardown at exit, and the scheduling of the child and the parent. This measurement does not separate them. Exercise 6 measures the first one. The dynamic launch is 146 to 278 µs slower than the static launch. The 27 extra faults explain about 45 to 70 µs of that difference, and the 18 extra system calls at least 1.5 µs. The rest of the difference is not explained here.

Equation (2.1) turns these numbers into a rule. The launch consumes at most 1 % of the time when \(t_{\mathrm{run}}\ge 99\,t_{\mathrm{launch}}\), which is 45 to 69 ms for the dynamic program and 31 to 42 ms for the static one. For \(t_{\mathrm{run}}=10\) ms the fraction is \(\varphi=4.4\) to \(6.5\ \%\) (dynamic) and 3.0 to 4.0 % (static). For \(t_{\mathrm{run}}=1\) s it is 0.05 to 0.07 %. A sweep of runs that last seconds can start one process per run. A sweep of runs that last milliseconds should let one process compute several parameter sets; chapter 5 builds the sweep script.

The kernel: privileged code, system calls and loadable modules W1L2 2:27

The lecture defines the kernel as the platform on which programs and services run, a bridge between the software and the hardware that manages resources, handles hardware communication and keeps processes executing. At W1L2 3:28 it states that the Linux kernel is monolithic, which it explains as running "as a single large process in a privileged mode" (the slide at W1L2 4:45). It adds that the kernel supports loadable kernel modules, and that it creates for every process a "virtual machine" through which the process reaches the hardware.

What monolithic means. Tanenbaum's definition, quoted in the section on history, is that the whole operating system is one binary that runs in kernel mode and contains process management, memory management, the file system "and the rest". This definition does not call the kernel a process. A process, as defined in the model, is an execution of an image with its own address space and with state that the kernel keeps. The kernel is the code that keeps that state. When a process makes a system call, the kernel code runs on behalf of the calling thread, and strace attributes the call to the process that made it. The lecture's phrase "single large process" is therefore a description of one binary in one privileged mode and not of a process in the sense of the model.

What the "virtual machine" is. The slide at W1L2 9:45 draws a box labelled "Virtual Machine" between each process and the kernel. What the kernel gives each process is two things. The first is a virtual processor: the thread sees its own registers, and the kernel saves and restores them when it switches between threads. The second is virtual memory: the process sees its own address space \(A\), whatever the other processes do. Together they make each process behave as if it had a dedicated computer, which is what the lecture means. They are not a virtual machine in the sense of a hypervisor, where a guest runs its own kernel. The machine of this chapter contains both layers: the WSL 2 virtual machine runs the Linux kernel 6.6.87.2, and every process of the guest runs under that single kernel. The lecture also assigns the creation of these machines to the virtual file system. That assignment is not supported by the kernel documentation, which describes the virtual file system as an abstraction layer over file systems; the section on the virtual file system returns to it.

The cost of one system call. A request to the kernel costs more than a call to a function in the same program, because the processor changes mode, the kernel entry code runs, and the return restores the user state. The kernel documentation lists the entry point for the syscall instruction among the entry points of the x86-64 entry code (entry code). It also states that on processors that need page-table isolation, the kernel changes the page-table base register at every entry and exit, a move that costs "on the order of a hundred cycles" each (page-table isolation, section on overhead). The guest here reports Not affected, so that cost is absent from the numbers below. The next program measures three costs per call: an ordinary function call that the compiler cannot remove, the system call getpid through syscall(SYS_getpid), and clock_gettime, which the C library serves from the vDSO, a small shared object that the kernel maps into every process. The Linux manual states that the vDSO exists because some calls are used so often that "the context-switch overhead that results from exiting user space and entering the kernel" can dominate performance (vdso(7)), and it lists __vdso_clock_gettime among the exported symbols. The listing keeps the smallest time of 5 repetitions of 5 000 000 calls. It is checked by its return code.

#define _GNU_SOURCE
#include <stdio.h>
#include <sys/syscall.h>
#include <time.h>
#include <unistd.h>

#define N 5000000L
#define REPS 5

static double now(void)
{
    struct timespec ts;
    clock_gettime(CLOCK_MONOTONIC, &ts);
    return ts.tv_sec + ts.tv_nsec * 1e-9;
}

static long sink;
__attribute__((noinline)) static long plain_call(long x) { __asm__ volatile("" : "+r"(x)); return x + 1; }

int main(void)
{
    double best_plain = 1e30, best_sys = 1e30, best_vdso = 1e30;
    struct timespec ts;
    for (int r = 0; r < REPS; r++) {
        double t0 = now();
        for (long i = 0; i < N; i++) sink += plain_call(i);
        double t1 = now();
        for (long i = 0; i < N; i++) sink += syscall(SYS_getpid);
        double t2 = now();
        for (long i = 0; i < N; i++) { clock_gettime(CLOCK_MONOTONIC, &ts); sink += ts.tv_nsec; }
        double t3 = now();
        if (t1 - t0 < best_plain) best_plain = t1 - t0;
        if (t2 - t1 < best_sys)   best_sys = t2 - t1;
        if (t3 - t2 < best_vdso)  best_vdso = t3 - t2;
    }
    printf("ordinary function call      %7.2f ns\n", best_plain / N * 1e9);
    printf("syscall(SYS_getpid)         %7.2f ns\n", best_sys / N * 1e9);
    printf("clock_gettime (vDSO)        %7.2f ns\n", best_vdso / N * 1e9);
    printf("system call / function call %7.1f\n", best_sys / best_plain);
    return 0;
}

ordinary function call         0.49 ns
syscall(SYS_getpid)           87.28 ns
clock_gettime (vDSO)          16.57 ns
system call / function call   177.2

Over eight runs, the ordinary function call took 0.46 to 0.51 ns, syscall(SYS_getpid) took 83.6 to 96.5 ns, and clock_gettime through the vDSO took 15.6 to 17.8 ns. The run at 96.5 ns was made while other programs loaded the machine; the other seven runs lie between 83.6 and 91.4 ns. A minimal system call costs 176 to 194 times as much as the function call, and 5.0 to 5.5 times as much as the call that the vDSO serves. The vDSO call still reads the clock, so its cost is not the cost of a function call. The frequency of the processor was not measured, so the chapter does not convert the times into cycles.

Amortizing the cost. A program that moves \(S\) bytes with calls that each move \(b\) bytes makes \(S/b\) calls. Let \(a\) be the fixed time of one call, independent of \(b\), and \(B\) the rate at which the kernel copies data. The total time and the fraction of it that is fixed per-call cost are

The fixed cost equals the copy time when \(b^{*}=aB\). The model assumes that \(a\) and \(B\) are constant, which holds while the data stay in a cache that the copy can use. The next program tests it on a file read. It writes a 64 MiB file in /tmp, so that the data sit in the page cache (the memory in which the kernel keeps recently used file data), and it reads the file with read calls of 1 byte to 64 KiB. For each size it keeps the smallest time of three passes, with at most 2 000 000 calls per pass. It fits the line \(t=a+b/B\) through the seven points by least squares. The run is checked by its return code.

#define _GNU_SOURCE
#include <fcntl.h>
#include <stdio.h>
#include <time.h>
#include <unistd.h>

#define MAXCHUNK (64 * 1024)
#define FILE_BYTES (64L << 20)                   /* the file that every chunk size reads from the start */
#define CALLS 2000000L                           /* at most this many calls per measurement */

static double now(void)
{
    struct timespec ts;
    clock_gettime(CLOCK_MONOTONIC, &ts);
    return ts.tv_sec + ts.tv_nsec * 1e-9;
}

int main(void)
{
    static char buf[MAXCHUNK];
    int fd = open("/tmp/chunks.dat", O_RDWR | O_CREAT | O_TRUNC, 0600);
    unlink("/tmp/chunks.dat");                        /* the open descriptor keeps the file alive */
    for (long done = 0; done < FILE_BYTES; done += MAXCHUNK)
        if (write(fd, buf, MAXCHUNK) != MAXCHUNK) return 1;      /* the data now sit in the page cache */
    long size[] = {1, 8, 64, 512, 4096, 32768, 65536};
    int n = sizeof size / sizeof size[0];
    double x[8], y[8];
    printf("%8s %14s %14s\n", "bytes", "ns per call", "GB/s");
    for (int i = 0; i < n; i++) {
        long calls = FILE_BYTES / size[i];
        if (calls > CALLS) calls = CALLS;
        double best = 1e30;
        for (int r = 0; r < 3; r++) {
            lseek(fd, 0, SEEK_SET);
            double t0 = now();
            for (long k = 0; k < calls; k++)
                if (read(fd, buf, size[i]) != size[i]) return 1;
            double t = (now() - t0) / calls;
            if (t < best) best = t;
        }
        x[i] = size[i];
        y[i] = best * 1e9;
        printf("%8ld %14.1f %14.2f\n", size[i], y[i], size[i] / best / 1e9);
    }
    /* least-squares line  t = a + s / B  through the points (s, t) */
    double sx = 0, sy = 0, sxx = 0, sxy = 0;
    for (int i = 0; i < n; i++) { sx += x[i]; sy += y[i]; sxx += x[i] * x[i]; sxy += x[i] * y[i]; }
    double slope = (n * sxy - sx * sy) / (n * sxx - sx * sx);
    double a = (sy - slope * sx) / n;
    printf("fit: a = %.1f ns per call, 1/B = %.4f ns per byte (B = %.1f GB/s)\n", a, slope, 1.0 / slope);
    printf("chunk size at which call overhead equals copy time: %.0f bytes\n", a / slope);
    return 0;
}

   bytes    ns per call           GB/s
       1          182.7           0.01
       8          187.8           0.04
      64          185.4           0.35
     512          227.8           2.25
    4096          568.6           7.20
   32768         3764.8           8.70
   65536         6839.9           9.58
fit: a = 194.7 ns per call, 1/B = 0.1029 ns per byte (B = 9.7 GB/s)
chunk size at which call overhead equals copy time: 1893 bytes

In three runs at lower load, a read of 1 byte took 173 to 183 ns, a read of 4 KiB took 532 to 579 ns, and a read of 64 KiB took 6.4 to 6.8 µs, which is 9.6 to 10.3 GB/s. (In the run under heavy load, the read of 4 KiB took 845 ns and the fit gave \(a=416\) ns, so on a busy machine the fixed cost per call is larger and the crossover \(b^{*}\) moves up to 3.7 kB.) The fit gave \(a=180\) to 195 ns per call and \(B=9.7\) to 10.5 GB/s, and the crossover \(b^{*}=aB\) was 1.8 to 1.9 kB. The line agrees with every measured time to within 10 % in the sample run (the largest difference is 8.6 %). The 180 ns per call is about twice the 87 ns of getpid: a read also finds the open file from the descriptor and finds the data in the page cache, and the measurement does not separate these two parts. With \(a=180\) ns, reading 1 GiB takes \(2^{30}\times180\) ns \(=193\) s with 1-byte reads and \(0.003+0.107=0.11\) s with 64 KiB reads, by equation (2.2). The ratio is about 1700. A program that reads or writes in small pieces, one number or one line at a time, spends nearly all its time in the kernel. The remedy is to move more bytes per call. The stdio buffer of the C library helps: it turns many small fread or fprintf calls into one read or write of the buffer size, 4096 bytes for a file in /tmp on this guest (glibc 2.39; equal to the preferred I/O size of the file, st_blksize, which stat -c %o reports as 4096; a probe program that wrote 10 000 bytes with fputc made writes of 4096, 4096 and 1808 bytes). At 4096 bytes equation (2.2) puts the fixed cost at \(1800/(1800+4096)=31\) % of the call time. Reaching 5 % needs calls of about 34 kB (Exercise 2), which a program gets by reading into its own larger buffer or by setting the stdio buffer with setvbuf.

Monolithic or microkernel. In the exchange of January 1992, Tanenbaum argued that "the only real argument for monolithic systems was performance", and that microkernel systems "can be just as fast", citing published comparisons of Mach 3.0 with monolithic systems. Torvalds replied that Linux "wins heavily on points of being available now". Equation (2.2) shows where the performance question sits: in a microkernel, an operation that is one system call in a monolithic kernel becomes at least one message exchange with a server process. The program in the section on the scheduler measures a round trip of a one-byte message between two processes through a pipe: 2.8 to 3.3 µs on one processor, which is 29 to 40 times the cost of the minimal system call. That figure belongs to the generic pipe mechanism and not to the optimized message path of a microkernel, so it does not decide the question. It shows that the cost of the message path decides it.

Loadable modules. The kernel of this guest is built with module support (CONFIG_MODULES=y), and lsmod lists loaded modules such as intel_rapl_msr and kvm_intel (the session at the end of this section). A module is object code that is linked into the running kernel. It runs in kernel mode with the full privileges of the kernel, so a module is as trusted as the kernel, and a fault in a module is a fault in the kernel. The lecture says that this feature gives Linux its variety of flavors. The flavors of Linux that the lecture lists differ in their package managers, default software and kernel configuration. Modules are a mechanism for adding drivers and other kernel features to a running kernel without a restart, and the chapter does not find that they define a flavor.

$ uname -sr
Linux 6.6.87.2-microsoft-standard-WSL2
$ getconf PAGESIZE
4096
$ zcat /proc/config.gz | grep -E '^CONFIG_(MODULES|HZ|PREEMPT_DYNAMIC)='
CONFIG_PREEMPT_DYNAMIC=y
CONFIG_HZ=250
CONFIG_MODULES=y
$ lsmod | head -3
Module                  Size  Used by
intel_rapl_msr         16384  0
intel_rapl_common      32768  1 intel_rapl_msr
$ cat /sys/devices/system/cpu/vulnerabilities/meltdown
Not affected
$ cat /proc/sys/kernel/randomize_va_space
2

The session reports the page size, the timer frequency and the dynamic-preemption option of the kernel, the first loaded modules, the state of the Meltdown mitigation, and the setting of address-space layout randomization (randomize_va_space is 2, which means that the kernel places the stack, the heap and the libraries of each new process at random addresses, so the addresses in the maps session differ from run to run).

The scheduler: fair shares, preemption and the cost of switching W1L2 11:18

The lecture states that the process scheduler decides how processes are allocated to the processor, with the goal of maximizing processor utilization and sharing the time equally. Its slide lists the key elements: scheduling policies (round robin, first come first served, shortest job next, completely fair scheduler), process states (running, waiting, ready, blocked), preemptive and non-preemptive scheduling, context switching and load balancing. The lecture explains preemptive scheduling as taking the processor from a running process when a higher-priority process arrives.

Definitions. A thread is runnable when it needs a processor, and blocked when it waits for an event such as the completion of input. A burst \(\tau_j\) is the processor time that job \(j\) needs. The waiting time of a job is the time during which it is runnable and does not run. A scheduler is preemptive when it can remove a running thread from the processor before that thread blocks or ends. A quantum \(q\) is the longest time that a thread runs before the scheduler may switch. A context switch saves the state of one thread, restores the state of another and costs a time \(t_{\mathrm{cs}}\).

Policies on four jobs. Take four jobs that arrive together at time 0, with bursts \(\tau_A=8\), \(\tau_B=4\), \(\tau_C=9\), \(\tau_D=5\) ms, one processor, no switching cost, and jobs that run to completion in the chosen order. If the order is \(\sigma\) and \(\tau_{(i)}\) is the burst of the job in position \(i\), the job in position \(k\) waits \(\sum_{i\lt k}\tau_{(i)}\), so the sum of the waiting times and the mean waiting time are

The weights \(n-i\) fall as the position \(i\) rises. Suppose two neighbouring positions \(i\) and \(i+1\) hold bursts with \(\tau_{(i)}\gt \tau_{(i+1)}\). Swapping them changes the sum by \((n-i)\tau_{(i+1)}+(n-i-1)\tau_{(i)}-(n-i)\tau_{(i)}-(n-i-1)\tau_{(i+1)}=\tau_{(i+1)}-\tau_{(i)}\lt 0\). Every swap that removes an inversion lowers the sum, and an order with no inversion is the order of non-decreasing bursts. That order, shortest job first (SJF), therefore has the smallest mean waiting time. The proof assumes bursts that are known in advance, simultaneous arrival and no switching cost. With arrivals spread in time it does not hold as stated, and a long job can wait without bound while short jobs keep arriving. The program computes first come first served (FCFS), SJF and round robin (RR), in which each job in turn runs for at most \(q\) and then joins the end of the queue, for three quanta. It also checks the claim for all 24 orders. It is deterministic.

"""Mean waiting time of four jobs under first-come-first-served, shortest-job-first
and round-robin scheduling on one CPU; all jobs arrive at time 0."""
from itertools import permutations

bursts = {"A": 8, "B": 4, "C": 9, "D": 5}      # CPU time each job needs, in ms


def fcfs_waits(order):
    """Waiting time of each job when the jobs run to completion in the given order."""
    clock, waits = 0, {}
    for job in order:
        waits[job] = clock
        clock += bursts[job]
    return waits


def round_robin_waits(quantum):
    """Waiting time = completion time - burst, for a cyclic queue with the given quantum."""
    remaining = dict(bursts)
    queue, clock, done = list(bursts), 0, {}
    while queue:
        job = queue.pop(0)
        run = min(quantum, remaining[job])
        clock += run
        remaining[job] -= run
        if remaining[job]:
            queue.append(job)
        else:
            done[job] = clock
    return {job: done[job] - bursts[job] for job in bursts}


def mean(waits):
    return sum(waits.values()) / len(waits)


sjf = sorted(bursts, key=bursts.get)
print("FCFS  order A B C D :", fcfs_waits("ABCD"), f"mean {mean(fcfs_waits('ABCD')):.2f} ms")
print("SJF   order", " ".join(sjf), ":", fcfs_waits(sjf), f"mean {mean(fcfs_waits(sjf)):.2f} ms")
for q in (1, 4, 16):
    w = round_robin_waits(q)
    print(f"RR    quantum {q:2d} ms :", w, f"mean {mean(w):.2f} ms")

orders = list(permutations(bursts))
best = min(mean(fcfs_waits(o)) for o in orders)
print(f"minimum mean over all {len(orders)} orders: {best:.2f} ms;",
      "SJF reaches it:", mean(fcfs_waits(sjf)) == best)

FCFS  order A B C D : {'A': 0, 'B': 8, 'C': 12, 'D': 21} mean 10.25 ms
SJF   order B D A C : {'B': 0, 'D': 4, 'A': 9, 'C': 17} mean 7.50 ms
RR    quantum  1 ms : {'A': 16, 'B': 10, 'C': 17, 'D': 14} mean 14.25 ms
RR    quantum  4 ms : {'A': 12, 'B': 4, 'C': 17, 'D': 20} mean 13.25 ms
RR    quantum 16 ms : {'A': 0, 'B': 8, 'C': 12, 'D': 21} mean 10.25 ms
minimum mean over all 24 orders: 7.50 ms; SJF reaches it: True

FCFS in the order A, B, C, D gives a mean waiting time of 10.25 ms. SJF, in the order B, D, A, C, gives 7.50 ms, which equals the minimum over all 24 orders, as (2.3) predicts: \((3\cdot4+2\cdot5+1\cdot8+0\cdot9)/4=7.5\). Round robin gives 14.25, 13.25 and 10.25 ms for \(q=1,4,16\) ms. With \(q=16\) ms, which is longer than every burst, RR is FCFS. RR has the larger mean waiting time here, and its purpose is a different property: with \(n\) jobs in the queue, every job gets the processor within \((n-1)q\) of the moment it is ready. For \(n=4\) and \(q=1\) ms this is 3 ms, against 21 ms before job D first runs under FCFS. Shortest job next needs the burst length before the job runs, which a general-purpose kernel does not know, so Linux has no such policy.

What Linux does. The Linux manual names SCHED_OTHER as "the standard Linux time-sharing scheduler that is intended for all threads that do not require the special real-time mechanisms". The policies SCHED_FIFO and SCHED_RR are real-time policies with static priorities 1 to 99, and a runnable thread of a real-time policy always preempts a SCHED_OTHER thread. The manual states that "all scheduling is preemptive" (sched(7)). The lecture's round robin and first-come-first-served therefore exist in Linux as real-time policies, and the ordinary policy is the fair-share scheduler. The kernel documentation of the Completely Fair Scheduler (CFS) describes its model as an "ideal, precise multi-tasking CPU" on which \(n\) runnable tasks each run at \(1/n\) of the speed, and states that CFS tracks a virtual runtime per task (CFS scheduler). The documentation of the EEVDF scheduler states that the kernel began the transition to it in version 6.6 and that it also "aims to distribute CPU time equally among all runnable tasks with the same priority" (EEVDF scheduler). Linux 6.6 replaced the CFS selection rule by EEVDF (KernelNewbies, Linux 6.6), and Linux 6.12 completed the transition (KernelNewbies, Linux 6.12). The guest kernel, 6.6.87.2, therefore schedules SCHED_OTHER threads with EEVDF.

Fair share and nice levels. The nice value of a thread biases its share of the processor. In the fair-share model a thread \(i\) with weight \(\omega_i\) gets the share \(\omega_i/\sum_j \omega_j\) of a processor that runnable threads share. The kernel documentation on nice levels states that nice levels are multiplicative, so that two tasks whose nice levels differ by 1 split the processor 55 % to 45 % wherever the pair starts, and that a task at nice \(+19\) receives 1.5 % of the processor (nice-level design). If each step multiplies the weight by a constant factor \(r\), the share of the thread at nice \(k\) against a thread at nice 0 is

The two figures of the documentation give two values of \(r\): the 55/45 split gives \(r=0.55/0.45=1.222\), and the 1.5 % at \(k=19\) gives \(r=(1/0.015-1)^{1/19}=1.246\). Both figures are rounded. The kernel source settles the factor: the table sched_prio_to_weight in kernel/sched/core.c (Linux 6.6.87) is built with "a multiplier of 1.25" and gives the weights 1024, 335, 110 and 15 for nice 0, 5, 10 and 19 (kernel.org, stable tree, tag v6.6.87, lines 11550 to 11571). The table predicts shares of 24.7 % and 9.7 % for nice 5 and nice 10 against nice 0; the rounded 55/45 figure (\(r=1.222\)) predicts 26.8 % and 11.9 %. At nice \(+19\) the table gives \(15/1039=1.44\) %, which the documentation rounds to 1.5 %. The next program tests this. Two children are pinned to processor 0 with sched_setaffinity, so they must share it. Each child adds its nice value with nice, and counts blocks of 100 000 empty loop iterations until a common deadline 2 s away, and reports the count through a pipe. The share of a child is its count over the total. The loop makes no system call except the read of the clock, which the vDSO serves without entering the kernel. Any change of the running child therefore comes from the timer interrupt and not from a request of the child. The run takes 6 s and is checked by its return code.

#define _GNU_SOURCE
#include <errno.h>
#include <sched.h>
#include <stdio.h>
#include <sys/wait.h>
#include <time.h>
#include <unistd.h>

#define RUN_SECONDS 2.0

static double now(void)
{
    struct timespec ts;
    clock_gettime(CLOCK_MONOTONIC, &ts);
    return ts.tv_sec + ts.tv_nsec * 1e-9;
}

/* Fork a child that is pinned to CPU 0, adds `nice_value` to its nice value, and counts
   blocks of 100000 empty loop iterations until the wall-clock time `deadline`.
   The child reports its count through the pipe end `fd`. */
static pid_t spawn(int nice_value, double deadline, int fd)
{
    pid_t pid = fork();
    if (pid == 0) {
        cpu_set_t set;
        CPU_ZERO(&set);
        CPU_SET(0, &set);
        sched_setaffinity(0, sizeof set, &set);
        errno = 0;
        if (nice(nice_value) == -1 && errno) _exit(1);
        unsigned long count = 0;
        do {
            for (int k = 0; k < 100000; k++) __asm__ volatile("" ::: "memory");
            count++;
        } while (now() < deadline);
        (void)!write(fd, &count, sizeof count);
        _exit(0);
    }
    return pid;
}

static void experiment(int nice_a, int nice_b)
{
    int pa[2], pb[2];
    if (pipe(pa) || pipe(pb)) return;
    double deadline = now() + RUN_SECONDS;
    pid_t a = spawn(nice_a, deadline, pa[1]);
    pid_t b = spawn(nice_b, deadline, pb[1]);
    unsigned long ca = 0, cb = 0;
    (void)!read(pa[0], &ca, sizeof ca);
    (void)!read(pb[0], &cb, sizeof cb);
    waitpid(a, NULL, 0);
    waitpid(b, NULL, 0);
    printf("nice %2d against nice %2d: shares %.1f %% and %.1f %%\n", nice_a, nice_b,
           100.0 * ca / (ca + cb), 100.0 * cb / (ca + cb));
}

int main(void)
{
    experiment(0, 0);
    experiment(0, 5);
    experiment(0, 10);
    return 0;
}

nice  0 against nice  0: shares 49.8 % and 50.2 %
nice  0 against nice  5: shares 75.2 % and 24.8 %
nice  0 against nice 10: shares 90.4 % and 9.6 %

Two children of equal nice value got 49.7 to 50.3 % each. With nice 5 the niced child got 24.2 to 25.5 % across the runs of this section, and with nice 10 it got 9.0 to 10.0 %. These values agree with the shares of the kernel table (24.7 % and 9.7 %) and disagree with \(r=1.222\) (26.8 % and 11.9 %). The measurement cannot separate the table from \(r=1.246\) (25.0 % and 10.0 %): the two differ by 0.3 points, less than the spread of the runs. It also confirms preemption. Neither child ever blocks or yields, and the processor still divides in a fixed ratio between them, so the kernel removes the running thread from the processor by interrupt. The kernel is configured with a periodic timer tick of 250 Hz, which is 4 ms. The interval between the preemptions of this kernel was not measured.

The cost of a switch. Let \(t_{\mathrm{cs}}\) be the cost of one context switch. With a quantum \(q\), the fraction of the processor time that threads can use is

The next program estimates \(t_{\mathrm{cs}}\) from a ping-pong. Two processes are connected by two pipes. The parent writes one byte, the child reads it and writes one back, and the parent reads that byte; 50 000 rounds. When both processes are pinned to processor 0, each message wakes a process that cannot run until the other blocks, so a round trip contains two process switches, four pipe system calls and two wake-ups. The measured time of a round trip is therefore an upper bound on \(2t_{\mathrm{cs}}\), and half of it an upper bound on \(t_{\mathrm{cs}}\). The listing also runs the pair on processors 0 and 2, where no switch is needed. It keeps the smallest of three runs and is checked by its return code.

#define _GNU_SOURCE
#include <sched.h>
#include <stdio.h>
#include <sys/wait.h>
#include <time.h>
#include <unistd.h>

#define ROUNDS 50000
#define REPS 3

static double now(void)
{
    struct timespec ts;
    clock_gettime(CLOCK_MONOTONIC, &ts);
    return ts.tv_sec + ts.tv_nsec * 1e-9;
}

static void pin(int cpu)
{
    cpu_set_t set;
    CPU_ZERO(&set);
    CPU_SET(cpu, &set);
    sched_setaffinity(0, sizeof set, &set);
}

/* Two processes pass one byte back and forth through two pipes, ROUNDS times.
   One round trip is 2 writes and 2 reads. With both processes on one CPU each
   round trip also needs 2 process switches. Returns seconds per round trip. */
static double pingpong(int cpu_parent, int cpu_child)
{
    int up[2], down[2];
    char c = 'x';
    if (pipe(up) || pipe(down)) return -1.0;
    pid_t pid = fork();
    if (pid == 0) {
        pin(cpu_child);
        for (int i = 0; i < ROUNDS; i++) {
            (void)!read(up[0], &c, 1);
            (void)!write(down[1], &c, 1);
        }
        _exit(0);
    }
    pin(cpu_parent);
    double t0 = now();
    for (int i = 0; i < ROUNDS; i++) {
        (void)!write(up[1], &c, 1);
        (void)!read(down[0], &c, 1);
    }
    double t = now() - t0;
    waitpid(pid, NULL, 0);
    return t / ROUNDS;
}

int main(void)
{
    double same = 1e30, diff = 1e30;
    for (int r = 0; r < REPS; r++) {
        double a = pingpong(0, 0), b = pingpong(0, 2);
        if (a < same) same = a;
        if (b < diff) diff = b;
    }
    printf("both processes on CPU 0:       %.2f us per round trip\n", same * 1e6);
    printf("processes on CPU 0 and CPU 2:  %.2f us per round trip\n", diff * 1e6);
    return 0;
}

both processes on CPU 0:       3.12 us per round trip
processes on CPU 0 and CPU 2:  34.02 us per round trip

On one processor, a round trip took 2.8 to 3.3 µs in 11 runs, so \(t_{\mathrm{cs}}\lt1.7\) µs. For an assumed quantum of \(q=4\) ms, one timer tick, this gives, by (2.5), \(\eta\gt0.9995\). That is the direct cost of a switch. The cost of reloading caches and address translations after a switch is not in \(t_{\mathrm{cs}}\) and was not measured. On two processors a round trip took 31.7 to 40.2 µs, which is 10 to 14 times as long as the round trip on one processor (10.9 in the sample run), although no switch is involved. Waking a process on another processor requires an interrupt between processors, and the target processor may be idle. In a virtual machine, such interrupts and the halting of an idle processor involve the hypervisor. That is a hypothesis that this chapter did not test. The measured fact is that two processes on different processors of this guest take about 11 times as long to exchange a message as two processes that share one. Chapter 11 returns to this result for teams of threads that are larger than the number of processors, and chapter 14 for the placement of message-passing ranks.

Memory management: virtual addresses, page tables and page faults W1L2 13:27

The lecture assigns to the "memory management unit" the management of physical and virtual memory, the mapping between the two, the page tables, the translation lookaside buffer (TLB), memory protection and cache control, so that every process gets a fair share of memory. Two statements need a correction before the model is stated. The memory management unit (MMU) is a part of the processor, not a component of the kernel; the kernel builds the tables that the MMU reads. The lecture describes the TLB as a small memory that stores recent data. It stores recent address translations. The kernel documentation states that "CPUs maintain a cache of such translations called Translation Lookaside Buffer" because address translation "requires several memory accesses" (Linux kernel documentation, concepts overview, section on huge pages).

The model. The kernel documentation states that virtual memory "abstracts the details of physical memory from the application software, allows to keep only needed information in the physical memory (demand paging) and provides a mechanism for the protection and controlled sharing of data between processes". Every access uses a virtual address, and the processor translates it to a physical address. Physical memory is divided into page frames. Page tables describe the mappings, are organized hierarchically, and the pointer to the top-level table sits in a register; "the high bits of the virtual address are used to index an entry in the top level page table" and the lowest bits are the offset inside the page (concepts overview, section on the virtual memory primer). On x86-64, Linux supports 48-bit and 57-bit virtual addresses, with four-level and five-level page tables (Linux kernel documentation, x86-64 memory map). This chapter uses the 48-bit, four-level case with pages of 4096 bytes. An address then has 12 offset bits and four indices of 9 bits each. A table page of 4096 bytes holds 512 entries of 8 bytes, which is consistent with the 9-bit index. This chapter assumes, without a source that it opened, that an entry takes 8 bytes and that a table page holds 512 of them; the measurement below is consistent with that assumption and does not fix it.

The size of the tables. To map a contiguous region of \(S\) bytes, the kernel needs \(n_p=\lceil S/4096\rceil\) entries at the lowest level, which fill \(N_1=\lceil n_p/512\rceil\) table pages. The next level needs one entry per table page of the level below, so \(N_\ell=\lceil n_p/512^{\ell}\rceil\) for \(\ell=1,\dots,4\). The tables occupy

The next program splits one virtual address into its four indices and its offset, rebuilds the address from them, and evaluates (2.6) for three sizes. It assumes a start aligned to the span of one top-level entry, and its output is deterministic.

"""Split an x86-64 virtual address into page-table indices and count the table pages
needed to map a contiguous region. 4 KiB pages, 4 levels, 9 index bits per level."""

PAGE = 4096
ENTRY = 8                                       # bytes per page-table entry
PER_TABLE = PAGE // ENTRY                       # 512 entries per table page
SHIFTS = (39, 30, 21, 12)                       # top level first


def split(addr):
    offset = addr & (PAGE - 1)
    return [(addr >> s) & 0x1FF for s in SHIFTS], offset


def tables_for(size):
    """Pages used by the leaf tables and each higher level to map `size` contiguous bytes
    from a start aligned to the span of one top-level entry."""
    n = -(-size // PAGE)                        # number of data pages
    counts = []
    for _ in range(4):
        n = -(-n // PER_TABLE)
        counts.append(n)
    return counts                               # leaf level first, top level last


addr = 0x00007FFD12345678
idx, off = split(addr)
print(f"address {addr:#018x}: indices {idx} (top level first), offset {off:#x}")
rebuilt = sum(i << s for i, s in zip(idx, SHIFTS)) + off
print("indices and offset rebuild the address:", rebuilt == addr)

for label, size in (("1 MiB", 1 << 20), ("1 GiB", 1 << 30), ("16 GiB", 16 << 30)):
    counts = tables_for(size)
    total = sum(counts) * PAGE
    print(f"{label:>6}: {size // PAGE:>8} data pages; table pages, leaf level first: {counts}; "
          f"{total // 1024} KiB of tables = {100 * total / size:.2f} % of the region")

address 0x00007ffd12345678: indices [255, 500, 145, 325] (top level first), offset 0x678
indices and offset rebuild the address: True
 1 MiB:      256 data pages; table pages, leaf level first: [1, 1, 1, 1]; 16 KiB of tables = 1.56 % of the region
 1 GiB:   262144 data pages; table pages, leaf level first: [512, 1, 1, 1]; 2060 KiB of tables = 0.20 % of the region
16 GiB:  4194304 data pages; table pages, leaf level first: [8192, 16, 1, 1]; 32840 KiB of tables = 0.20 % of the region

The indices of the address 0x00007ffd12345678 are 255, 500, 145 and 325, and its offset is 0x678; the pieces rebuild the address. For 1 GiB the tables take 512 leaf pages and one page at each higher level, 515 pages or 2060 KiB, which is 0.20 % of the region. For 16 GiB the share is also 0.20 %. For 1 MiB it is 1.56 %, because the three upper levels cost three pages for a small region. The model assumes that the mapped region is dense. A sparse region needs more table memory per byte of data, and the next program measures how much. It reserves 512 MiB of address space and writes one byte in every 2 MiB region, 256 writes, so that each write needs its own table page at the lowest level. It reads the fields VmRSS (resident memory) and VmPTE (the size of the page-table memory; the /proc documentation defines it as the "size of page table entries") from /proc/self/status before and after.

#define _GNU_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/mman.h>

#define SPAN (512L << 20)                    /* 512 MiB of address space */
#define REGION (2L << 20)                    /* one page-table page maps 2 MiB */

static long status_kb(const char *key)
{
    FILE *f = fopen("/proc/self/status", "r");
    char line[256];
    long kb = -1;
    size_t n = strlen(key);
    while (f && fgets(line, sizeof line, f))
        if (strncmp(line, key, n) == 0) kb = atol(line + n);
    if (f) fclose(f);
    return kb;
}

int main(void)
{
    char *p = mmap(NULL, SPAN, PROT_READ | PROT_WRITE,
                   MAP_PRIVATE | MAP_ANONYMOUS | MAP_NORESERVE, -1, 0);
    if (p == MAP_FAILED) { perror("mmap"); return 1; }
    madvise(p, SPAN, MADV_NOHUGEPAGE);
    long rss0 = status_kb("VmRSS:"), pte0 = status_kb("VmPTE:");
    long touches = 0;
    for (long off = 0; off < SPAN; off += REGION) { p[off] = 1; touches++; }
    long rss1 = status_kb("VmRSS:"), pte1 = status_kb("VmPTE:");
    printf("touched one byte in each of %ld regions of 2 MiB\n", touches);
    printf("resident data grew by at least one 4 kB page per touch: %s\n",
           rss1 - rss0 >= 4 * touches ? "yes" : "no");
    printf("page-table memory grew by %.1f kB per touched region\n", (double)(pte1 - pte0) / touches);
    return 0;
}

touched one byte in each of 256 regions of 2 MiB
resident data grew by at least one 4 kB page per touch: yes
page-table memory grew by 4.0 kB per touched region

Each write adds 4.0 kB of page-table memory, and the resident data grow by at least one page per write. The growth of 4.0 kB per touched 2 MiB region is what one 4096-byte table page per 2 MiB predicts. It rules out a table page that covers more than 2 MiB, and it does not by itself fix the size of an entry. A sparse access pattern at a stride of 2 MiB therefore pays 4 kB of tables for each 4 kB page of data, a ratio of 1, against the ratio of 0.002 of the dense case in (2.6). The two cases differ by a factor of 512.

Translation cost. Reading the four entries of a walk takes up to four memory accesses. With a TLB hit time \(t_{\mathrm{TLB}}\), a TLB miss rate \(m_T\) and a memory access time \(t_{\mathrm{ref}}\), the mean time to translate one address is at most

The bound has the form of the average memory access time of chapter 7 with the miss penalty \(4t_{\mathrm{ref}}\). It is an upper bound because the entries of upper levels are often found in the processor's caches. This chapter did not measure the TLB. It uses (2.7) only to show why the lecture lists the TLB among the memory-management elements: a program with a large working set raises \(m_T\). The kernel documentation states that a huge page of 2 MiB or 1 GiB, mapped by an entry at a higher level, "significantly reduces pressure on TLB" (concepts overview, huge pages). The guest uses transparent huge pages only on request (/sys/kernel/mm/transparent_hugepage/enabled reads [madvise]), and every program of this chapter that counts page faults calls madvise with MADV_NOHUGEPAGE so that each fault maps one page of 4 KiB.

Demand paging and copy-on-write. The program below creates an anonymous 64 MiB mapping (memory that no file backs) with mmap and writes the first byte of each page twice, and counts the minor faults of the process with getrusage. A minor fault is a fault that the kernel resolves without disk input. The program then calls fork, and the child writes every page once more. The parent checks that its own pages are unchanged. Inputs: none. Outputs: faults per page and one check. The output is deterministic because the counts are the page counts.

#define _GNU_SOURCE
#include <stdio.h>
#include <sys/mman.h>
#include <sys/resource.h>
#include <sys/wait.h>
#include <unistd.h>

#define BYTES (64L << 20)                    /* 64 MiB */

static long minor_faults(void)
{
    struct rusage ru;
    getrusage(RUSAGE_SELF, &ru);
    return ru.ru_minflt;
}

static void touch(char *p, long bytes, long page, char value)
{
    for (long off = 0; off < bytes; off += page) p[off] = value;
}

int main(void)
{
    long page = sysconf(_SC_PAGESIZE);
    long pages = BYTES / page;
    char *p = mmap(NULL, BYTES, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
    if (p == MAP_FAILED) { perror("mmap"); return 1; }
    madvise(p, BYTES, MADV_NOHUGEPAGE);      /* one fault per ordinary page, whatever the system setting */

    long f0 = minor_faults();
    touch(p, BYTES, page, 1);                /* first write to each page */
    long f1 = minor_faults();
    touch(p, BYTES, page, 1);                /* second write: the pages are mapped now */
    long f2 = minor_faults();
    printf("page size %ld bytes, %ld pages\n", page, pages);
    printf("parent first pass : %.2f minor faults per page\n", (double)(f1 - f0) / pages);
    printf("parent second pass: %ld minor faults\n", f2 - f1);

    fflush(stdout);
    pid_t pid = fork();
    if (pid == 0) {                          /* the child shares every page with the parent until it writes */
        long g0 = minor_faults();
        touch(p, BYTES, page, 2);
        long g1 = minor_faults();
        printf("child write pass  : %.2f minor faults per page\n", (double)(g1 - g0) / pages);
        fflush(stdout);
        _exit(0);
    }
    waitpid(pid, NULL, 0);
    int unchanged = 1;
    for (long off = 0; off < BYTES; off += page) if (p[off] != 1) unchanged = 0;
    printf("parent: every page still holds the parent's own value: %s\n", unchanged ? "yes" : "no");
    return 0;
}

page size 4096 bytes, 16384 pages
parent first pass : 1.00 minor faults per page
parent second pass: 0 minor faults
child write pass  : 1.00 minor faults per page
parent: every page still holds the parent's own value: yes

The mapping has 16384 pages. The first write to each page costs one minor fault, 1.00 per page, and the second pass costs none: mmap reserved the addresses, and the kernel allocated a frame, filled it with zeros and mapped it when the page was first touched. The child's write pass again costs 1.00 fault per page. After fork the child shares every frame with the parent, and the first write by the child to a page makes the kernel copy that page into a new frame: this is copy-on-write, as the manual of fork states. The parent's pages still hold the parent's value, so the child's writes did not reach the parent. This is the isolation property of \(A\) that the model requires.

The cost of a minor fault is 1.7 to 2.5 µs in the launch measurement. A fault serves 4096 bytes, so the rate at which a fresh array is first written is 1.6 to 2.4 GB/s, against about 10 GB/s for copying data that are already in memory (the fit of the previous section). Initializing a large array that was just allocated is therefore slower than any later pass over it, a fact that chapter 7 meets again in the discussion of non-uniform memory and of first touch.

The virtual file system, inter-process communication and the claim that everything is a file W1L2 14:35

The lecture states that the virtual file system (VFS) is an abstraction layer that lets the kernel interface with different file systems in a uniform way. Its slide lists the key elements: the superblock (an entire mounted file system), the inode (metadata about a file or directory), the dentry (a directory entry), mount points, file-system operations and types, and the file descriptor table. The kernel documentation describes the VFS as "the software layer in the kernel that provides the filesystem interface to userspace programs" and as "an abstraction within the kernel which allows different filesystem implementations to coexist" (Linux kernel documentation, VFS, introduction). It adds that the system calls open, stat, read, write and chmod are called from a process context. The lecture says at W1L2 9:36 that the VFS is responsible for creating a virtual machine for each new process. The documentation does not assign to the VFS the creation of anything per process. The chapter takes the per-process objects to be the address space and the table of open files of the model, and the VFS to be the code that serves the calls on the open files. Chapter 3 treats the inode, the directory entry and the permission bits.

One interface, several kinds of object. The table \(O\) of the model maps a file descriptor to an open file. A call such as read(fd, buffer, n) names only the descriptor. The kernel finds the open file and runs the read operation of whatever the descriptor refers to: a file of a file system, a device driver, a pipe or a socket. The next program opens one object of each kind, writes 5 bytes with write, and reads them back with read when the object has a read end. It also reads from a directory. The output is deterministic.

#define _GNU_SOURCE
#include <errno.h>
#include <fcntl.h>
#include <stdio.h>
#include <string.h>
#include <sys/socket.h>
#include <sys/stat.h>
#include <unistd.h>

static const char *kind(int fd)
{
    struct stat st;
    fstat(fd, &st);
    if (S_ISREG(st.st_mode)) return "regular file";
    if (S_ISDIR(st.st_mode)) return "directory";
    if (S_ISCHR(st.st_mode)) return "character device";
    if (S_ISFIFO(st.st_mode)) return "pipe (FIFO)";
    if (S_ISSOCK(st.st_mode)) return "socket";
    return "other";
}

int main(void)
{
    int file = open("fdtypes.tmp", O_RDWR | O_CREAT | O_TRUNC, 0600);
    unlink("fdtypes.tmp");                   /* the open descriptor keeps the file alive */
    int dir = open(".", O_RDONLY);
    int dev = open("/dev/null", O_WRONLY);
    int pp[2], sp[2];
    if (pipe(pp) || socketpair(AF_UNIX, SOCK_STREAM, 0, sp)) return 1;

    struct { const char *name; int wfd, rfd; } t[] = {
        {"file",      file,  file},
        {"/dev/null", dev,   -1},
        {"pipe",      pp[1], pp[0]},
        {"socket",    sp[0], sp[1]},
    };
    char buf[16];
    for (int i = 0; i < 4; i++) {
        ssize_t w = write(t[i].wfd, "hello", 5);
        ssize_t r = -2;                      /* -2: this entry has no read end */
        if (t[i].rfd >= 0) {
            if (t[i].rfd == file) lseek(file, 0, SEEK_SET);
            r = read(t[i].rfd, buf, sizeof buf);
        }
        printf("%-10s %-17s write returned %zd, read returned %zd\n", t[i].name, kind(t[i].wfd), w, r);
    }
    ssize_t r = read(dir, buf, sizeof buf);
    printf("%-10s %-17s read returned %zd (%s)\n", "directory", kind(dir), r, strerror(errno));
    return 0;
}

file       regular file      write returned 5, read returned 5
/dev/null  character device  write returned 5, read returned -2
pipe       pipe (FIFO)       write returned 5, read returned 5
socket     socket            write returned 5, read returned 5
directory  directory         read returned -1 (Is a directory)

Four kinds of object accept the same write call and report 5 bytes written. The file, the pipe and the socket return the same 5 bytes through the same read call. /dev/null is a character device that accepts and discards the data, and it has no read end in this program. The directory is a file in the sense that it has a descriptor, but read fails with Is a directory: a uniform interface does not make every operation valid for every kind of object. Ritchie and Thompson describe the first version of the idea: "Special files are read and written just like ordinary disk files, but requests to read or write result in activation of the associated device" (§3.3), and the abstract of their paper lists "compatible file, device, and inter-process I/O" as a feature.

What "everything is a file" covers. The lecture states at W1L2 19:04 that most system resources and devices are represented as files, lists regular files, directories, devices in /dev, symbolic links and network interfaces, and says that processes, threads and memory are the exceptions. The slide says "mostly everything", which is the more careful statement. The next session tests three parts of the claim: the descriptors of a process, the information that the kernel gives about a process, and the network interface.

$ ls -l /proc/self/fd 3< hello.c > fd.txt 2>&1 < /dev/null; grep -v ptmx fd.txt | sed 's/ az9713 az9713//' | cut -c1-100
total 0
lr-x------ 1 64 Oct 26 18:46 0 -> /dev/null
l-wx------ 1 64 Oct 26 18:46 1 -> /tmp/hpsc-ch02-demo/fd.txt
l-wx------ 1 64 Oct 26 18:46 2 -> /tmp/hpsc-ch02-demo/fd.txt
lr-x------ 1 64 Oct 26 18:46 3 -> /tmp/hpsc-ch02-demo/hello.c
lr-x------ 1 64 Oct 26 18:46 4 -> /proc/609/fd
$ grep -E '^(Name|State|Pid|PPid|Threads|VmPTE)' /proc/self/status
Name:   grep
State:  R (running)
Pid:    613
PPid:   334
VmPTE:        48 kB
Threads:    1
$ ls /dev | grep -c -E '^(eth|wlan|en)'
0
$ ls /sys/class/net
eth0
lo

A process holds its open objects as descriptors: in the listing, descriptors 0, 1 and 2 refer to /dev/null and to the output file, as the redirections of the command line set them, descriptor 3 refers to the file hello.c, and descriptor 4 is the directory handle that ls itself opened. The kernel also exposes information about the process as files under /proc: the lines of /proc/self/status give the name, state, process number, parent number, thread count and page-table memory of the reading process. A process is therefore not a file, as the lecture says, but the kernel offers a file-shaped view of it. The lecture's claim about network interfaces does not hold in the sense of /dev: no node whose name starts with eth, wlan or en exists in /dev, and the interface eth0 appears under /sys/class/net as an entry of the sysfs file system. The kernel offers a socket, which is a descriptor, as the way to use the network, and the earlier program created one with socketpair.

The network subsystem and inter-process communication. At W1L2 16:09 the lecture describes the network subsystem as the code that processes, routes and manages network packets, with a socket interface between programs and the kernel and with layers from the link layer to the application layer. The socket in the program above is its simplest form, a pair of connected endpoints on one machine. Chapter 4 uses the network commands, and chapter 14 uses sockets and shared memory inside the message-passing library. At W1L2 17:16 the lecture lists the mechanisms for communication and synchronization between processes: message queues, shared memory, semaphores and signals. Ritchie and Thompson describe the earliest of them, the pipe, which processes use "with the same system read and write calls that are used for file-system I/O", and which must be set up by a common ancestor of the processes involved (§5.2). The ping-pong of the previous section measures a message through a pipe: 2.8 to 3.3 µs per round trip on one processor. Threads of one process need no such mechanism for data, because they share \(A\), and chapter 11 starts from this fact. Processes of different programs share data only through one of the mechanisms above, and the lecture states that these mechanisms are what the higher-level parallel programming models build on.

What the model establishes and what it does not

Table 2.2 lists the statements of the lectures that this chapter tested, with the status that the tests gave them.

The model of privilege modes, processes and system calls establishes four things. Multiplexing and isolation need instructions that only the kernel can execute, and an attempt to execute one in user mode ends the process, not the kernel. A process is an address space, a table of open files, credentials and threads, and the kernel runs on behalf of its threads. A system call costs 87 ns on this guest, 176 to 194 times an ordinary call, and a program must amortize it over at least a few kilobytes of data per call. The ordinary Linux scheduler divides a processor among runnable threads in the ratio of their weights, and a nice step multiplies the weight by 1.25 (the kernel table uses a multiplier of 1.25; the measured shares at nice 5 and 10 match it to within the 1-point spread of the runs).

The model leaves out most of what an operating system does. It treats the scheduler on one processor, and it omits the migration of threads between processors, the placement of memory on non-uniform machines, swapping, and the scheduling of disk and network input. It covers threads only as members of one process; the creation of threads with clone belongs to chapter 11. It does not describe containers, control groups or virtual machines beyond the one remark about the WSL 2 guest. Security appears only as the isolation between processes; permissions are in chapter 3.

The quantitative results have their own limits. All times belong to one WSL 2 guest on one hybrid processor, and a bare-metal Linux, or a guest that needs page-table isolation, would show other costs. The launch decomposition explains 22 to 30 % of the launch time at a fault cost of 1.7 to 2.5 µs (34 to 37 % in a loaded run), and the remaining 70 to 78 % (63 % in the loaded run) is not attributed. The estimate that faults account for a quarter of the launch assumes that a fault during a launch costs as much as the first write to a zero-filled page. The explanation offered for the slow exchange of messages between processors is a hypothesis that was not tested. The scheduler of the guest kernel is EEVDF according to the release notes of Linux 6.6; the scheduler's own source was not read. The share of Linux in the TOP500 list, the dates for Slackware and Debian, Ubuntu and Android, the 2020 popularity claim, and the exact day of the first Linux release were not established.

Exercises

Exercise 1 (derive). \(n\) jobs arrive together at time 0, and each needs the same burst \(\tau=mq\), where \(q\) is the quantum of a round-robin scheduler and \(m\) is a whole number. Switching is free. Derive the mean waiting time under round robin and under FCFS, and evaluate both for \(n=4\), \(\tau=8\) ms and \(q=1\) ms.

Exercise 2 (compute). A program reads a 4 GiB file that is in the page cache. Use \(a=180\) ns and \(B=10\) GB/s, round values from the fits of the chapter (180 to 195 ns, 9.7 to 10.5 GB/s). Compute the time for reads of \(b=1\), 512, 4096 and 65 536 bytes. Find the smallest \(b\) for which the per-call cost is at most 5 % of the total time. Compare the first and the last time.

Exercise 3 (counterexample). A student says: "A program that makes no system call never enters the kernel." Give a program from this chapter that disproves the claim, and count how many times it enters the kernel.

Exercise 4 (diagnose an assumption). A student reads the one-processor ping-pong, 2.8 to 3.3 µs per round trip, and concludes: "moving a thread to another processor costs at most one context switch, about 1.5 µs." Find the assumption that fails, and give a corrected bound for the cost of a switch.

Exercise 5 (design judgment). A sweep must run \(10^{5}\) cases of a solver that needs 20 ms each, on a node with 12 logical processors. Option A starts one process per case, linked dynamically. Option B is option A with static linking. Option C starts 12 worker processes that each loop over their share of the cases. Use the launch times of this chapter and choose an option, with numbers.

Exercise 6 (implementation and measurement). The manual says that fork costs "the time and memory required to duplicate the parent's page tables". Predict how the time of fork followed by waitpid depends on the amount of memory the parent has touched. Then measure it for parents that have touched 0, 16, 64, 256 and 512 MiB.

#define _GNU_SOURCE
#include <stdio.h>
#include <sys/mman.h>
#include <sys/wait.h>
#include <time.h>
#include <unistd.h>

#define REPS 200

static double now(void)
{
    struct timespec ts;
    clock_gettime(CLOCK_MONOTONIC, &ts);
    return ts.tv_sec + ts.tv_nsec * 1e-9;
}

int main(void)
{
    long page = sysconf(_SC_PAGESIZE);
    long mib[] = {0, 16, 64, 256, 512};
    printf("%10s %12s %14s %18s\n", "touched", "pages", "fork+wait us", "us per 1000 pages");
    double base = 0;
    for (int i = 0; i < 5; i++) {
        long bytes = mib[i] << 20;
        char *p = NULL;
        if (bytes) {
            p = mmap(NULL, bytes, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
            madvise(p, bytes, MADV_NOHUGEPAGE);
            for (long off = 0; off < bytes; off += page) p[off] = 1;
        }
        double best = 1e30;
        for (int r = 0; r < REPS; r++) {
            double t0 = now();
            pid_t pid = fork();
            if (pid == 0) _exit(0);
            waitpid(pid, NULL, 0);
            double t = now() - t0;
            if (t < best) best = t;
        }
        if (i == 0) base = best;
        printf("%7ld MiB %12ld %14.1f %18.1f\n", mib[i], bytes / page, best * 1e6,
               bytes ? (best - base) * 1e6 / (bytes / page / 1000.0) : 0.0);
    }
    return 0;
}

   touched        pages   fork+wait us  us per 1000 pages
      0 MiB            0           97.8                0.0
     16 MiB         4096          252.1               37.7
     64 MiB        16384          836.9               45.1
    256 MiB        65536         3299.2               48.9
    512 MiB       131072         8469.5               63.9

Primary sources

• Recordings: W1L1, Introduction to Operating System (slides: what an operating system is, its components, types, the history and milestones of Linux, the role of Linux in HPC, the layer structure); W1L2, Linux Kernel Explained (slides: the kernel, its subcomponents, library files, types of files), NPTEL High Performance Scientific Computing, IIT Bombay, 2025.
• D. M. Ritchie and K. Thompson, "The UNIX Time-Sharing System", electronic edition of the revision in The Bell System Technical Journal 57(6), 1978, which revises Communications of the ACM 17(7), 1974, pp. 365–375. The text of 1974 was not read. §I: versions of Unix, "circa 1969-70", the unprotected PDP-11/20 and multiprogramming on later models; §3.3: special files; §V: image and process; §5.1 to §5.3 and §5.5: fork, pipes, execute and exit; §VI: the shell as a command-line interpreter.
• L. Torvalds, "Linux's History", written 31 July 1992 (a mirror at Carnegie Mellon University). The posts of 3 July, 25 and 26 August, 5 October and 19 December 1991: the first announcement, version 0.01 "sometimes around this time", GNU programs running under the kernel, the early licence, and version 0.12 of 5 January 1992.
• kernel.org, archive of kernel version 1.0: linux-1.0.tar.gz with the date 13 March 1994 (the date of the file in the listing).
• A. S. Tanenbaum and L. Torvalds, "The Tanenbaum-Torvalds Debate", appendix A of Open Sources (O'Reilly, 1999). The posts of 29 January 1992: the definitions of the monolithic kernel and the microkernel, and Torvalds's reply.
• The Linux kernel community, Kernel Entry (x86 entry code: the entry points for syscall, interrupts and exceptions), Page Table Isolation (§23.3, overhead: control-register moves of about a hundred cycles at entry and exit), x86-64 memory map (48-bit and 57-bit virtual addresses, four-level and five-level tables), Concepts overview (virtual memory primer, huge pages, TLB), Overview of the Linux Virtual File System (introduction), The /proc filesystem (VmPTE, the definition of the proportional set size), CFS Scheduler (the ideal multi-tasking CPU, virtual runtime), EEVDF Scheduler (transition from version 6.6), Scheduler Nice Design (55 % to 45 % for a difference of one nice level, 1.5 % at nice +19). The pages are those of the documentation version 7.3.0 at the time of reading; they were read on 2026-10-26.
• The Linux man-pages project, syscall(2) (instruction, number register and argument registers for x86-64), fork(2) (separate memory spaces, copy-on-write, the penalty of duplicating page tables), execve(2) (replacement of the program, the PT_INTERP interpreter), sched(7) (policies, static priorities 1 to 99, preemption), vdso(7) (purpose of the vDSO, exported __vdso_clock_gettime).
• The Open Group, POSIX.1-2024 (IEEE Std 1003.1-2024), fork: the child is an exact copy of the parent except for a list of attributes, including a unique process identifier.
• The Open Group, POSIX.1-2024, Shell and Utilities, chapter 2, §2.9.1.4 Command Search and Execution: the search sequence applies only if the command name contains no slash.
• The Linux kernel source, tag v6.6.87 of the stable tree (kernel/sched/core.c, read through a mirror of the same tag): the comment "a multiplier of 1.25" and the table sched_prio_to_weight (weights 1024, 335, 110, 15 for nice 0, 5, 10, 19); mm/memory.c, copy_present_pte and page_try_dup_anon_rmap (the candidate mechanism of Exercise 6).
• KernelNewbies, Linux 6.6 (released 29 October 2023: the CFS process scheduler is replaced by EEVDF) and Linux 6.12 (release on 17 November 2024, merge of the real-time preemption patch set PREEMPT_RT, completion of the EEVDF transition); both are secondary sources.