The Art of the Necessary Lie

Research work by Merjen Kakajanova, student of the International University for the Humanities and Development. Instructor: Nurmyrat Allayarov.

Open a terminal on almost any computer and type ps aux. On an idle laptop you will see a few hundred processes; on a busy server, a few thousand. Each of them believes, in a fairly literal sense, that it owns a processor, that memory starts at a small address and stretches far beyond anything physically installed, and that the files it writes will still be there tomorrow. Every one of these beliefs is false. The machine has perhaps eight or sixteen cores, a fixed amount of RAM shared by everyone, and storage that can lose power halfway through a write.

The operating system is the program that keeps these beliefs intact. That is its central job, and nearly everything else it does follows from it. Textbooks have a dry name for the trick, virtualization, and it is worth taking the word seriously. The OS takes a physical resource that is scarce, shared and awkward to use, and presents in its place a virtual one that is plentiful, private and convenient. The CPU becomes a set of processes. Physical memory becomes a set of address spaces. A block device that understands only “read sector 81,920” becomes a tree of named files.

This essay follows that idea through the three problems every serious operating system has to solve: sharing the processor, sharing memory, and keeping data safe when the power goes out. Along the way it touches the less glamorous problem that makes all three harder than they look, which is that many things are now happening at once.

1. A program with a life

A program is a file. It sits on disk, inert, a list of instructions and some initial data. A process is what you get when the operating system gives that program a life: an address space to live in, a register set that records where it is in its work, a list of open files, an identity for permission checks, and a place in the queue for the processor.

The distinction sounds pedantic until you notice that one program can be many processes at once. Ten terminal windows may all be running the same shell binary, each with its own history, its own current directory, its own idea of what it is doing. The kernel tracks each one in a structure that Linux calls task_struct, a record that has grown over three decades to several kilobytes of state. When a process is not running, that record is the process. Everything needed to resume it later is either written there or reachable from there.

Unix made process creation famously strange. Instead of a single call that says “start this program,” it offers two. fork() makes an almost exact copy of the calling process. exec() then replaces the copy’s program with a different one. The idea predates Unix, but Thompson and Ritchie made it the foundation of their system, and it lives on in every shell:

pid_t pid = fork();
if (pid == 0) {
    /* child: rearrange stdin/stdout here, then become another program */
    execlp("sort", "sort", "-n", NULL);
    _exit(127);                 /* only reached if exec failed */
}
waitpid(pid, &status, 0);       /* parent: wait for the child to finish */

The gap between the two calls is where the design pays off. Between fork and exec, the child is still running the parent’s code, so it can close files, redirect output into a pipe or drop privileges using the same ordinary system calls any program uses. No special “spawn with these seventeen options” interface is needed. Pipelines like grep error log.txt | sort | uniq -c fall out of this almost for free. The cost, as later sections show, is that copying an entire process just to throw the copy away would be absurdly expensive, and it took clever memory management to make it cheap.

2. Slicing time

If processes outnumber cores a hundred to one, someone has to decide who runs next. That decision is the scheduler’s, and it is made thousands of times per second on every core.

The mechanism is simple to describe. A hardware timer interrupts the processor at regular intervals. The interrupt hands control to the kernel, whether or not the running program was willing to give it up. The kernel saves the program’s registers into its process record, picks another process, loads that one’s registers and returns. From the outside, the second program simply continues where it left off. This is a context switch, and on modern hardware the direct cost is a few microseconds. The indirect cost is often larger: the new process finds the caches full of someone else’s data and runs slowly until it has warmed them up again.

The policy is where it gets interesting, because the goals conflict. A batch job compiling a kernel wants long, uninterrupted stretches of CPU, since every switch wastes cache. A text editor wants almost no CPU at all, but it wants it immediately when a key is pressed. Optimize for throughput and the editor stutters. Optimize for responsiveness and the compiler crawls.

One of the most durable answers came from Fernando Corbató’s Compatible Time-Sharing System at MIT in the early 1960s, and it is still taught under the name multi-level feedback queue. The scheduler keeps several queues at different priorities. New processes start at the top. A process that uses up its whole time slice is probably doing heavy computation, so it is moved down a level. A process that gives up the CPU early, because it is waiting for input, stays near the top. The scheduler never needs to be told which programs are interactive; it infers it from their behavior. Variants of this idea shaped the schedulers of BSD, Solaris and Windows.

Linux took a different path. In 2007 it adopted the Completely Fair Scheduler, which dropped explicit priority queues in favor of an accounting trick. Each process accumulates “virtual runtime” as it executes, weighted by its priority, and the scheduler always runs whichever runnable process has accumulated the least.

Processes that sleep a lot fall behind on the ledger and get to run promptly when they wake up. In 2023, with version 6.6, the kernel replaced CFS with EEVDF (Earliest Eligible Virtual Deadline First), an algorithm from a 1995 research paper that keeps the fairness accounting but adds an explicit notion of latency, so that a process can ask to run sooner in exchange for running in shorter bursts.

No scheduler is right for every workload. Each one is a bet about what the people using the machine will notice first.

That bet changes with the hardware. On a phone, the scheduler also has to decide which kind of core to use, since a single chip may mix fast, power-hungry cores with slow, efficient ones. On a server, it has to weigh keeping a process on the core whose cache it has already warmed against moving it to an idle core on the other side of the chip. Scheduling stopped being a single queue long ago. It is now a running negotiation between fairness, latency, cache locality and the battery.

3. Everyone gets the whole address space

The processor lie is told in time. The memory lie is told in space, and it is the more ambitious of the two.

Every process on a 64-bit Linux system sees an address space of 128 terabytes, laid out in roughly the same way: program code near the bottom, a heap growing upward, shared libraries somewhere in the middle, a stack near the top growing down. Two processes can both store something at address 0x7ffd5a3c1e40 and never interfere with each other, because that number does not refer to a location in RAM. It is a virtual address, and on every memory access the hardware translates it into a physical one, using tables that the operating system has prepared for that particular process.

The idea is older than most people expect. The Atlas computer at the University of Manchester, in service from 1962, gave programmers what its designers called a “one-level store”: a single large address space, backed partly by fast core memory and partly by a slow magnetic drum, with hardware and software moving fixed-size pages between them automatically. Programmers no longer had to split their programs into overlays by hand. Sixty years later the vocabulary has barely changed.

How translation works

Memory is divided into pages, usually 4 KiB each. On x86-64, a virtual address is cut into pieces. The lowest 12 bits are an offset within the page and are not translated at all. The next 36 bits are split into four groups of nine, and each group is an index into one level of a tree of page tables. The hardware walks the tree from the root, whose location is held in a special register, down to an entry that names the physical page. Changing which process is running is, at bottom, a matter of pointing that register at a different tree.

Walking four tables on every memory access would make the computer several times slower, so processors cache recent translations in a small, very fast structure called the translation lookaside buffer. A TLB holds anywhere from a few dozen to a couple of thousand entries, and because programs tend to touch the same pages repeatedly, it answers the overwhelming majority of lookups. When a workload scatters its accesses across gigabytes, the TLB stops keeping up, and performance drops in ways that are baffling until you know to look. This is why databases and virtual machine hosts ask for “huge pages” of 2 MiB or 1 GiB: one TLB entry then covers 512 or 262,144 times as much memory.

The page fault as a feature

Each page table entry has a bit that says whether the page is actually present. If a program touches a page whose entry is marked absent, the processor stops and raises a page fault, handing control to the kernel along with the address that caused it. The name suggests an error. In practice, page faults are one of the most productive tools the kernel has, because they let it postpone work until the moment it is truly needed, and sometimes avoid it altogether.

When a program allocates a gigabyte, Linux typically hands out no physical memory at all. It records that the range is valid and waits. Only when the program first writes to a page does a fault occur, and only then does the kernel find a free physical page, fill it with zeros and map it. Executables work the same way: starting a 200 MB program does not read 200 MB from disk, only the pages that are actually executed.

The same trick rescues fork(). Rather than copying the parent’s memory, the kernel lets parent and child share every physical page and marks all of them read-only. As long as both only read, nothing is copied. The moment either one writes to a page, the processor faults, the kernel copies that single page, gives each process its own version and lets the write proceed. This is copy-on-write. A child that calls exec() right away ends up copying almost nothing.

Order-of-magnitude figures; exact values vary by hardware. A page fault that has to fetch from storage costs as much as tens of thousands of ordinary memory accesses, which is why the choice of which page to evict matters so much.

Choosing what to forget

When physical memory runs out, the kernel has to evict something, either by dropping a clean page that can be read back from its file or by writing a dirty one out to swap. The perfect policy is known and impossible: evict the page that will not be needed for the longest time. Since the kernel cannot see the future, it approximates it with the recent past, preferring to evict pages that have not been touched lately. Real kernels use cheap approximations of “least recently used,” such as the clock algorithm, because tracking exact access order for millions of pages would cost more than it saves.

The field learned early how badly this can go wrong. In 1969 László Bélády showed that under simple first-in, first-out eviction, giving a program more memory can sometimes cause more faults. Around the same time, systems began to thrash: with too many programs competing for too little memory, each one evicted pages the others were about to use, and the machine spent nearly all its time moving pages instead of computing. Peter Denning’s 1968 working-set model gave the problem its classic diagnosis. Each program needs a certain set of pages resident to make progress. If the sum of those sets exceeds physical memory, adding programs makes everything slower, and the right response is to run fewer of them. Modern systems still act on this: when Linux runs critically low on memory, it would rather kill a process outright than let the whole machine grind to a halt.

4. The price of sharing

So far, isolation has been the goal. Processes are kept apart so that one cannot damage another. But programs often want to share. Threads inside one process share an address space by design, and on a machine with many cores they genuinely run at the same instant. This is where the tidy abstractions start to strain.

Consider the most innocent line of code imaginable, counter = counter + 1, executed by two threads. The processor does this in three steps: load the value into a register, add one, store it back. If both threads load the value 41 before either stores, both compute 42, both store 42, and one increment simply vanishes. Run that loop a million times on each of two threads and the final count will usually be well short of two million, and different on every run. Such a bug may show up once a week in production and never on a developer’s machine.

The basic remedy is mutual exclusion: a lock that only one thread can hold at a time, wrapped around any code that touches shared state. Edsger Dijkstra formalized the semaphore in the mid-1960s, and later designers added mutexes, condition variables and monitors. Locks cannot be built from ordinary loads and stores alone, at least not efficiently. They depend on special atomic instructions, such as compare-and-swap, which read and modify memory in one step that no other core can interrupt. On top of those, the operating system adds the ability to put a waiting thread to sleep instead of letting it spin and burn a core.

Locks bring their own failure modes. Two threads that each hold one lock and wait for the other’s will wait forever; that is deadlock. A subtler problem nearly ended a famous mission. In July 1997, a few days after the Mars Pathfinder lander touched down, it began resetting itself. Engineers traced the problem to a classic priority inversion. A low-priority task held a lock on a shared data bus. A high-priority task needed that lock and waited. Meanwhile a medium-priority task, which needed no lock at all, kept preempting the low-priority one, so the lock was never released, the high-priority task missed its deadline, and a watchdog timer reset the system. The fix was to enable priority inheritance in the real-time operating system, so that a task holding a lock temporarily takes on the priority of the most important task waiting for it. The change was uploaded to a spacecraft on another planet.

Concurrency bugs are not bugs in any single line of code. They live in the gaps between lines, in orderings no one thought to imagine.

Kernels themselves are among the most heavily concurrent programs ever written. Early versions of Linux protected the whole kernel with one “big kernel lock,” which was safe but meant that only one core could execute kernel code at a time. Removing it took the better part of fifteen years and was completed in 2011. Today the kernel uses fine-grained locks, per-core data structures that avoid sharing entirely, and techniques such as read-copy-update, which lets readers proceed without taking any lock while writers publish new versions of data and reclaim old ones only once every reader is done with them.

5. Making things stay

Processes and address spaces vanish when the machine turns off. Files are meant to survive. The file system therefore tells the third great lie, that a disk is a tidy hierarchy of named, resizable documents, when it is actually a long array of numbered blocks that can be read or written only in fixed-size pieces.

The basic structures have changed less than one might think. A Unix file system keeps, for every file, an inode holding its size, owner, permissions, timestamps and the locations of its data blocks. A directory is just a special file that maps names to inode numbers. That is why a file in Unix can have two names (two directory entries pointing to the same inode) and why deleting a file is called unlink: you remove a name, and the data is freed only when the last name and the last open handle are gone.

The crash problem

The hard part is not storing data. It is storing it consistently when power can fail at any instant. Appending one block to a file requires at least three separate writes: the data block itself, the inode with its new size and block pointer, and the bitmap that marks the block as used. The disk performs them one at a time, and possi-

bly not in the order they were issued. A crash between any two leaves the file system contradicting itself: an inode pointing at garbage, or a block marked used that belongs to no file.

For years, the answer was to scan the entire disk on reboot with a tool like fsck and repair whatever looked inconsistent. As disks grew to terabytes, that scan stretched from seconds into hours. The fix that won was borrowed from databases: journaling. Before touching the real structures, the file system writes a description of everything it is about to do into a log, followed by a commit record. Only after the commit is safely on disk does it apply the changes in place. After a crash, recovery reads the log and replays every committed transaction, ignoring incomplete ones. Instead of scanning the whole disk, it reads a few megabytes. Ext3 brought journaling to mainstream Linux in 2001; NTFS, XFS, ext4 and APFS all rely on some form of it. Other designs, such as ZFS and Btrfs, take a different path called copy-on-write: they never overwrite live data and instead write new versions elsewhere, then atomically switch a single root pointer.

The fsync gap

There is one more layer of deception, and this one often catches application developers. For speed, a write() call usually returns as soon as the data has been copied into the kernel’s page cache in RAM. The data reaches the disk seconds later, when the kernel gets around to it. A program that needs a guarantee must call fsync(), which blocks until the data is durable. Even that is subtler than it looks. Safely replacing a configuration file, for instance, means writing a temporary file, calling fsync on it, renaming it over the original, and then calling fsync on the directory so that the rename itself is durable.

Plenty of real software gets this wrong. A 2014 study by Pillai and colleagues at the University of Wisconsin examined widely used applications, including databases and version control systems, and found crash-consistency bugs in all of them. Most of these bugs were invisible on some file systems and serious on others, because they depended on how a particular file system happened to order its writes. The file abstraction is excellent, but at its edges it leaks, and the leaks are exactly where data gets lost.

6. The wall between

None of this works unless programs are forced to respect it. A process that could edit its own page tables could read every other process’s memory; a process that could disable the timer interrupt could keep the processor forever. So the hardware enforces a boundary. The processor runs in at least two modes. In kernel mode it can do anything. In user mode, privileged instructions trigger a fault, and pages marked as kernel-only cannot be touched.

The only way across the boundary is a system call: a deliberate trap into the kernel at an entry point the kernel itself chose. When a program calls read(), its library places a call number and arguments in registers and executes a special instruction. The processor switches modes and jumps to the kernel, which checks every argument (Is this file descriptor valid? Does this buffer really belong to the caller?), does the work, and returns. Linux exposes a few hundred such calls, and together they define everything a program can ask the operating system for. Seen from user space, the system call table is the operating system.

For decades the wall was considered sound. Then, in January 2018, researchers disclosed Meltdown and Spectre, a family of attacks that used the processor’s own performance tricks against it. Modern CPUs execute instructions speculatively, guessing ahead before they know whether those instructions should run. On many

affected chips, a user program could cause the processor to speculatively read kernel memory; the permission check eventually canceled the result, but not before the forbidden value had left a measurable trace in the cache. The isolation that operating systems had relied on since the 1960s turned out to have a side door in the hardware.

The software response was costly. Kernels adopted page table isolation, which keeps the kernel almost entirely unmapped while user code runs and switches to a separate set of page tables on every system call. Workloads heavy in system calls slowed down noticeably until newer processors fixed the flaw in silicon. The episode was a sharp reminder that every abstraction in this essay rests on assumptions about the layer beneath it. The OS can only keep its promises as long as the hardware keeps its own.

7. Why the lie holds

A remark usually credited to the computer scientist David Wheeler says that any problem in computer science can be solved by adding another level of indirection. Operating systems are that principle carried to its limit. Virtual addresses stand between programs and RAM. File descriptors stand between programs and devices. The scheduler stands between programs and time itself. Each layer of indirection is a place where the kernel can intervene: to share, to protect, to postpone work or to avoid it.

The ideas are remarkably old. Paging dates from the Atlas in 1962, time-sharing schedulers from CTSS, processes and pipes from early Unix, the working set from 1968. What has changed is the scale at which they operate and the hardware they have to tame: dozens of cores instead of one, storage that is a thousand times faster, virtual machines and containers stacking new layers of illusion on top of the old ones. A container, for all the attention it gets, is mostly a process that the kernel has been told to lie to a little more thoroughly, with its own view of the file tree, the process list and the network.

The real measure of an operating system is how rarely anyone thinks about it. When it works, a programmer writes malloc, open and write and never pictures page tables, inodes or a timer firing in the dark a thousand times a second. That invisibility is the whole achievement. The lie is necessary because the truth, a single shared, finite and failure-prone machine, would make nearly every program impossible to write. The craft lies in telling it so consistently that the programs never find out.

Further reading

• Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau. Operating Systems: Three Easy Pieces. Arpaci-Dusseau Books. Freely available online; organized around the same three themes as this essay.
• Dennis M. Ritchie and Ken Thompson. “The UNIX Time-Sharing System.” Communications of the ACM, 17(7), 1974.
• Peter J. Denning. “The Working Set Model for Program Behavior.” Communications of the ACM, 11(5), 1968.
• T. Kilburn, D. B. G. Edwards, M. J. Lanigan and F. H. Sumner. “One-Level Storage System.” IRE Transactions on Electronic Computers, 1962.
• Thanumalayan Sankaranarayana Pillai et al. “All File Systems Are Not Created Equal: On the Complexity of Crafting Crash-Consistent Applications.” OSDI, 2014.
• Andrew S. Tanenbaum and Herbert Bos. Modern Operating Systems. Pearson.
• Moritz Lipp et al. “Meltdown: Reading Kernel Memory from User Space.” USENIX Security Symposium, 2018.

---

Research work by Merjen Kakajanova, student of the International University for the Humanities and Development. Instructor: Nurmyrat Allayarov.