1. Introduction to Operating Systems

This chapter establishes what an operating system actually is: the layer of software that stands between raw hardware and every program you run, turning a pile of transistors, wires, and spinning or flashing storage into a set of clean, safe, shareable abstractions. It traces how that layer evolved from punched-card batch monitors into the kernels running in phones and data centres, examines the hardware mechanisms (interrupts, dual-mode execution, DMA) that make the whole arrangement possible, and surveys the architectural styles used to organise kernels. Everything in later chapters — processes, scheduling, memory, files, security — is a specialisation of the ideas introduced here.

1.1 Role and Purpose

Before studying any mechanism, it helps to be precise about the job the operating system was invented to do, and about the two very different vantage points from which people describe it.

Definition of an Operating System

Theory

Start with the problem, not the definition. A bare computer is genuinely hostile to work. To read a byte from a disk you must know the controller's register layout, issue commands in the right order, and busy-wait for a status bit. To run two programs at once you must ensure neither overwrites the other's memory. To print, you must arbitrate a device that only one program can hold at a time. If every application had to solve these problems itself, every application would solve them differently, incompatibly, and mostly wrongly.

An operating system is the software layer that solves these problems once, on behalf of everyone. It has two complementary mandates:

Convenience — provide abstractions (files, processes, sockets, virtual memory) that are easier and safer to program against than the hardware underneath.
Control — arbitrate access to finite hardware among competing programs and users, enforcing protection and fairness.

The kernel is the part of the OS that is always resident in memory and runs with full hardware privilege. Around it sit system programs (shells, compilers, service daemons) that ship with the system but run as ordinary user processes. The word "operating system" is used loosely for both; when precision matters, say "kernel".

A useful analogy: the OS is the government of the machine. It provides infrastructure nobody wants to build privately (roads, water — files, memory), and it enforces rules so citizens do not trample each other (property law, courts — protection, scheduling). Like a government, it is overhead: it consumes resources and constrains you, and it is still vastly better than the alternative.

Example

        +-------------------------------------------------+
        |   Users                                         |
        +-------------------------------------------------+
        |   Application programs                          |
        |   (browser, compiler, database, games)          |
        +-------------------------------------------------+
        |   System programs / libraries                   |
        |   (shell, libc, systemd, window server)         |
        +-------------------------------------------------+
        |   O P E R A T I N G   S Y S T E M   K E R N E L |
        |   process mgmt | memory mgmt | file systems      |
        |   device drivers | networking | security         |
        +-------------------------------------------------+
        |   Hardware                                      |
        |   CPU | RAM | disks | NIC | GPU | timers         |
        +-------------------------------------------------+

The same program, written twice — once against the hardware, once against the OS:

/* Without an OS: talk to an (imaginary) disk controller directly. */
outb(DISK_CMD_PORT, CMD_READ);          /* issue a read command      */
outb(DISK_LBA_PORT, block_number);      /* select the block          */
while (!(inb(DISK_STATUS_PORT) & RDY))  /* busy-wait for the device  */
    ;
insw(DISK_DATA_PORT, buffer, 256);      /* pull 512 bytes, 16 bits at a time */

/* With an OS: the same intent, portable across every disk ever made. */
int fd = open("/data/report.txt", O_RDONLY);
read(fd, buffer, 512);
close(fd);

Key takeaways

An OS exists to provide abstraction (convenience) and arbitration (control) over hardware.
The kernel is the privileged, always-resident core; system programs are unprivileged software shipped alongside it.
Abstractions such as files and processes do not exist in hardware — the OS invents and maintains them.
The OS is deliberate overhead, paid in exchange for portability, safety, and sharing.

🧪 Practice

List five hardware resources on your own machine and, for each, name the abstraction the OS exposes to programs instead of the raw device.

Run ps aux (Linux/macOS) or Get-Process (Windows) and classify ten entries as kernel threads, system programs, or user applications. Which column told you?

Interview-style: "Is a device driver part of the operating system?" Argue both positions. Hint: consider where the code executes and whose privilege it borrows, not who wrote it.

Resource Management

Theory

The hardware offers a fixed budget: some number of CPU cores, some gigabytes of RAM, some bandwidth to disk and network. The demand is unbounded — every process would happily take everything. Resource management is the OS's job of dividing that fixed budget among competing claimants, and it is the single thread connecting most chapters of this book.

There are two ways to share a resource, and every OS mechanism is one of them:

Sharing style	Meaning	Examples
Time multiplexing	Claimants take turns using the whole resource	CPU scheduling, disk request queues, network transmission
Space multiplexing	The resource is divided; each claimant holds a piece simultaneously	RAM partitions and pages, disk blocks, port numbers

For each resource the OS must answer four questions: who is asking, how much do they get, when do they get it, and what happens when they conflict. Answering them requires policy (what is fair? what is efficient?) implemented by mechanism (queues, tables, locks). A recurring design principle is the separation of policy and mechanism: the mechanism that switches processes should not hard-code the rule that decides which process runs next, so the rule can change without rewriting the machinery.

Analogy: an airport. Runways are time-multiplexed (one aircraft at a time, scheduled); gates and parking stands are space-multiplexed (many aircraft simultaneously, each with its own slot). Air traffic control is pure policy; the radios and lights are mechanism.

Example

   Time multiplexing the CPU (one core, three processes)

   core: [ P1 ][ P2 ][ P3 ][ P1 ][ P2 ][ P3 ][ P1 ] ...
         |----|                                        one time slice
         switch points are enforced by a timer interrupt

   Space multiplexing RAM (one physical memory, three processes)

   RAM:  +--------+--------+--------+-----------------+
         |   P1   |   P2   |   P3   |   free          |
         +--------+--------+--------+-----------------+
         all three resident at once, each confined to its own region

# Ask the OS what it is currently managing.
nproc                 # CPUs available for time multiplexing
free -h               # RAM: used / free / cached (space multiplexing)
ulimit -a             # per-process resource caps this shell enforces
cat /proc/loadavg     # runnable processes competing for the CPU

Key takeaways

Resource management = dividing a fixed hardware budget among unbounded demand.
Every sharing scheme is time multiplexing (take turns) or space multiplexing (take a piece).
The OS must decide who, how much, when, and how to resolve conflicts.
Keep policy separate from mechanism so policies can evolve independently.

🧪 Practice

Classify each as time- or space-multiplexed: a printer, L3 cache, an SSD, TCP port numbers, a GPU running compute kernels.

Use ulimit -v 100000 in a throwaway shell, then run a memory-hungry program. Explain what the OS did and which side (policy or mechanism) ulimit represents.

Design a starvation-free policy for a single printer shared by ten users, then explain which parts of your design are policy and which are mechanism.

Abstraction of Hardware

Theory

Hardware is diverse, awkward, and unstable across generations. An SSD, a spinning disk, and a network file server share almost nothing at the electrical level. Abstraction is the OS's answer: expose one uniform, idealised interface, and hide every difference behind it.

The abstractions an OS provides are, without exception, useful lies:

Abstraction	The lie it tells	The reality underneath
Process	You have your own CPU, running continuously	One core shared by dozens of processes, switched thousands of times a second
Virtual memory	You have a large, private, contiguous address space	Scattered physical frames, some pages on disk, some shared
File	A named, arbitrarily long, growable byte stream	Fixed-size blocks scattered across a device, indexed by metadata
Socket	A reliable byte pipe to another machine	Lossy packets, retransmission, reordering, congestion control

Two properties make an abstraction good. Uniformity: the same read() call works on a file, a pipe, a terminal, and a socket — this is what "everything is a file" means in UNIX. Fidelity of cost: the abstraction should hide complexity without hiding cost so thoroughly that programmers cannot reason about performance. Memory-mapped files hide the difference between RAM and disk beautifully — right up until a page fault costs a hundred thousand times a memory access.

Analogy: a car's steering wheel and pedals. They are the same in every car, whether the engine is diesel, petrol, or electric. You learn once and drive anything. The abstraction leaks only where physics demands it — an electric car still brakes differently.

Example

                       read(fd, buf, n)
                              |
                +-------------+-------------+
                |     Virtual File System   |   one uniform interface
                +-------------+-------------+
        +---------+-----------+-----------+---------+
        |         |           |           |         |
     ext4 on    NFS over    tmpfs in    pipe     /dev/tty
       SSD      network       RAM      buffer    terminal

# One interface, four wildly different devices underneath.
def count_lines(source):
    """`source` may be a regular file, a pipe, a socket file, or a device."""
    total = 0
    with open(source, "r") as handle:   # the OS resolves what this really is
        for _ in handle:                # read() underneath in every case
            total += 1
    return total

count_lines("/etc/passwd")       # ext4 on an SSD: block reads plus caching
count_lines("/dev/stdin")        # a pipe from another process: kernel buffer
count_lines("/proc/cpuinfo")     # not a file at all: generated by the kernel

Key takeaways

Abstractions replace diverse, awkward hardware with a small number of uniform interfaces.
Every OS abstraction is a convenient fiction maintained by the kernel at runtime.
Uniformity ("everything is a file") lets one tool work across unrelated resources.
Abstractions hide complexity but should not hide cost; leaky performance behaviour is where they bite.

🧪 Practice

Run cat /proc/cpuinfo and cat /proc/self/status. No such files exist on disk — explain what the kernel is really doing and what abstraction it is exploiting.

Name three ways the "file" abstraction leaks (cases where you must know what is underneath to write correct or fast code).

Interview-style: "Why is /dev/null a file?" Hint: think about what you gain by making a discard sink obey the same interface as everything else.

User vs Kernel Perspective

Theory

The same system looks entirely different depending on where you stand, and confusing the two viewpoints is a common source of muddled reasoning.

From the user (or application) perspective, the OS is a service provider. It is defined by the API: what calls exist, what guarantees they make, what errors they return. A program asks for a file to be opened, memory to be allocated, a connection to be made. It does not know or care how many processes exist, where its pages physically live, or which core it runs on. Its mental model is sequential and private.

From the kernel perspective, the OS is a resource arbiter and event handler. There is no single flow of control. The kernel is mostly a large collection of handlers that run in response to events: a system call arrives, a timer fires, a disk finishes a transfer, a page fault traps. Between events, the kernel is not "running" at all — a CPU is executing some process's code, or sitting idle. The kernel's mental model is concurrent, global, and interrupt-driven.

Analogy: a restaurant. The diner's view is a menu and a waiter — order, wait, receive. The kitchen's view is a queue of tickets, contention for a limited number of pans, and constant interruptions. Both descriptions are true; neither is complete alone.

This split explains many otherwise puzzling behaviours. sleep(1) looks like a one-line pause to the application; to the kernel it is "remove from run queue, arm a timer, schedule someone else, and re-queue on expiry". A "slow" program may be perfectly fast in user terms and simply starved in kernel terms.

Example

  USER VIEW  (process P)                KERNEL VIEW (whole machine)

  n = read(fd, buf, 4096);              P: state RUNNING -> BLOCKED
  /* ...one line, program pauses... */  submit disk request, queue it
  /* ...then continues... */            pick next runnable process, switch
  use(buf);                             (Q runs for 8 ms)
                                        disk interrupt: transfer complete
                                        copy to P's buffer, P -> READY
                                        scheduler eventually resumes P

/* One user-level line; a great deal of kernel-level activity. */
#include <stdio.h>
int main(void) {
    printf("hello\n");   /* user: format string, buffer it in libc,
                            then write(1, "hello\n", 6);
                            kernel: validate fd 1, find the terminal or pipe,
                            copy from user memory, wake any blocked reader,
                            possibly block this process, return byte count */
    return 0;
}

Watch the two views side by side:

strace -c ./hello    # every kernel-visible event this "one line" program caused

Key takeaways

Users see a service interface: calls, guarantees, errors, and a private sequential world.
The kernel sees a global, concurrent, event-driven system with no single flow of control.
The kernel runs in response to events (system calls, interrupts, traps), not as a continuous program.
Most OS surprises come from reasoning about one view while the behaviour is explained by the other.

🧪 Practice

Write a program that calls getpid() in a loop one million times, then run it under strace -c. Explain the user view and the kernel view of the elapsed time.

For malloc(16), describe what the application believes happened and what the kernel may (or may not) have done. Why are the answers different for malloc(16) and malloc(16 * 1024 * 1024)?

Interview-style: "Is the kernel a process?" Defend your answer. Hint: ask what would schedule it, and in whose context system-call code executes.

1.2 Historical Evolution

Operating systems were not designed in one sitting; each generation added a mechanism to solve the dominant pain of its era, and every one of those mechanisms is still present in modern kernels.

Batch Processing Systems

Theory

In the 1950s a computer cost more than the building it stood in, and the scarce resource was unambiguously the machine, not the human. Yet early operation was catastrophically inefficient: a programmer signed up for an hour, walked in with a card deck, mounted tapes, ran the job, debugged at the console, and walked out. Between jobs the multi-million-dollar CPU sat idle while a human shuffled paper.

Batch processing removed the human from the inner loop. Jobs were collected onto a tape, and a small permanently resident program — the resident monitor, the direct ancestor of the kernel — read the next job, loaded it, ran it, collected its output, and immediately started the next one. This introduced ideas we still rely on:

A resident piece of software that outlives individual programs.
Automatic job sequencing without human intervention.
Job control language (JCL): cards that described the job rather than being part of it — the first system interface.
Rudimentary protection: if a job crashed or looped forever, the monitor had to survive and move on, which required a timer and a privileged mode.

The weakness is glaring in hindsight: batch systems ran one job at a time. When the job requested I/O, the CPU stalled entirely, doing nothing until the tape or card reader finished — often 99% of the elapsed time. Turnaround was measured in hours, and interactive debugging did not exist.

Example

   Memory layout of a batch system

   +----------------------------+  high address
   |                            |
   |     user job area          |   one job at a time
   |                            |
   +----------------------------+
   |   resident monitor         |   loader, sequencer, device drivers
   |   (ancestor of the kernel) |
   +----------------------------+  address 0

   Timeline of one job (CPU utilisation is terrible)

   CPU:  [compute]......idle......[compute]........idle........[compute]
   I/O:  ........[read tape].............[write tape]..................

//JOB   ACCT=1234,NAME=SMITH        <- job card: who is paying
//FORT  EXEC FORTRAN                <- run the compiler
        READ(5,10) X                   the actual program follows
        ...
//LOAD  EXEC LINKEDIT               <- link it
//RUN   EXEC PGM=*.LOAD             <- and execute it
//DATA  DD *                        <- input data follows
        3.14159
/*                                  <- end of job

Key takeaways

Batch systems automated job sequencing to eliminate idle time caused by human operators.
The resident monitor is the first recognisable kernel: permanent, privileged, in charge of loading and sequencing.
Job control language was the first explicit interface between users and the system.
Fatal limitation: one job at a time, so the CPU idled through every I/O operation.

🧪 Practice

A job computes for 2 seconds, then reads tape for 18 seconds, then computes for 2 more. Compute CPU utilisation on a batch system running it alone.

Name two mechanisms the resident monitor needed in order to survive a buggy job, and explain what hardware support each requires.

Modern batch queues (Slurm, LSF, cloud batch) reintroduce the same model deliberately. What has changed, and why is it a good design again?

Multiprogramming

Theory

The batch system's fatal flaw was that I/O left the CPU idle. Multiprogramming fixes it with one idea: keep several jobs resident in memory simultaneously, and when the running job blocks on I/O, switch the CPU to another job that is ready. The device and the processor then work in parallel instead of taking turns.

This single change forced most of the machinery that defines an operating system:

Memory management and protection — several jobs are in RAM at once, so each must be confined to its own region. Base and limit registers (later, paging) appear here.
CPU scheduling — when one job blocks, some policy must choose the next.
Job/process state — the system must record where a suspended job left off, giving rise to the process control block.
Interrupt handling — the CPU learns of I/O completion asynchronously, so it must be able to abandon what it is doing and resume it later.
Device management and spooling — devices become shared resources needing queues.

Crucially, multiprogramming optimises throughput (jobs completed per hour) and utilisation, not response time. A job that blocks may not be resumed for a long while; no one is watching interactively, so nobody cares yet.

Analogy: a chef cooking three dishes. Rather than standing over one pot waiting for water to boil (blocking on I/O), the chef starts the water, chops vegetables for the second dish, and seasons the third. Nothing is faster individually; the kitchen's total output rises sharply.

Example

   UNIPROGRAMMING (one job resident)
   CPU:  [J1]......wait......[J1]......wait......[J1]
   util: about 25%

   MULTIPROGRAMMING (three jobs resident)
   CPU:  [J1][J2][J3][J1][J2][J3][J1][J2]
   I/O1:     [J1 reads.....]      [J1 reads....]
   I/O2:         [J2 writes...]
   util: about 90%  -- the CPU always finds someone ready

   Memory now holds several jobs, each needing protection:

   +-------------------+
   |   job 3           |  <- base3 / limit3
   +-------------------+
   |   job 2           |  <- base2 / limit2
   +-------------------+
   |   job 1           |  <- base1 / limit1
   +-------------------+
   |   monitor/kernel  |
   +-------------------+

# Why utilisation rises: probability that all jobs are simultaneously blocked.
def cpu_utilisation(degree, io_fraction):
    """degree = jobs resident; io_fraction = share of time a job waits on I/O.
       Simple independence model: CPU idles only if every job is waiting."""
    return 1 - io_fraction ** degree

for n in range(1, 7):
    print(n, round(cpu_utilisation(n, 0.8), 3))
# 1 0.2   2 0.36   3 0.488   4 0.59   5 0.672   6 0.738
# Diminishing returns: each extra job helps less, and costs memory.

Key takeaways

Multiprogramming keeps several jobs in memory and switches the CPU to a ready job whenever the running one blocks.
It exists to raise CPU utilisation and throughput, not to improve response time.
It forced the invention of memory protection, scheduling, saved process state, and interrupt handling.
Returns diminish as the degree of multiprogramming rises, and memory is the binding constraint.

🧪 Practice

Using the model above, how many resident jobs are needed to exceed 90% utilisation when each job spends 70% of its time on I/O?

Explain why multiprogramming without memory protection is unsafe, and describe the minimum hardware that makes it safe.

Interview-style: "Does multiprogramming make an individual job finish sooner?" Hint: distinguish throughput from turnaround time for a single job.

Theory

Multiprogramming kept the machine busy but left humans waiting hours for results. Time-sharing (or multitasking) applies the same switching machinery with a different goal: give many interactive users the illusion that each has the whole machine.

The key change is why the CPU switches. Multiprogramming switches when a job blocks. Time-sharing switches preemptively, on a timer, after a short quantum (typically tens of milliseconds), whether or not the job is willing. The scheduler now optimises response time — the delay between a keystroke and a visible reaction — rather than raw throughput.

Time-sharing brought a cluster of now-standard requirements:

Preemptive scheduling driven by a hardware timer interrupt.
Virtual memory / swapping, because more users than fit in RAM want to be logged in.
On-line file systems, since users need to keep work between sessions instead of carrying card decks.
Concurrency control for files and devices shared by simultaneous users.
Protection and authentication, because users are now mutually distrusting strangers.

CTSS (MIT, 1961) demonstrated the idea; Multics attempted the grand version of it; UNIX (1969) distilled it into something small enough to survive, and every desktop, phone, and server OS today is a time-sharing system by this definition.

Human factors drive the design: a response under roughly 100 ms feels instantaneous, so a quantum must be short enough that all runnable users are served within that window — which in turn bounds how many users a machine can serve interactively.

Example

   Preemption by timer, three interactive users

   t=0ms   timer set to 20ms, user A runs
   t=20ms  TIMER INTERRUPT -> save A, run B
   t=32ms  B blocks reading the terminal -> run C
   t=52ms  TIMER INTERRUPT -> save C, run A
           ...
   Each user perceives a slow-but-continuous private machine.

   round-robin queue:  [A] -> [B] -> [C] -> back to [A]

/* The heart of time-sharing: a periodic timer forces the switch. */
void timer_interrupt_handler(void) {
    current->ticks_used++;                 /* charge CPU time to the running task */
    if (current->ticks_used >= QUANTUM) {  /* quantum exhausted? */
        current->state = READY;            /* it is willing or not, it yields */
        enqueue(ready_queue, current);
        schedule();                        /* pick and switch to another task */
    }
    acknowledge_timer();                   /* re-arm for the next tick */
}

Key takeaways

Time-sharing switches preemptively on a timer to optimise interactive response time.
It differs from multiprogramming in goal and trigger, not in underlying mechanism.
It requires a hardware timer, virtual memory or swapping, on-line file systems, and per-user protection.
Quantum length trades context-switch overhead against responsiveness.

🧪 Practice

With a 20 ms quantum and 200 microseconds per context switch, compute the overhead percentage. Repeat for a 2 ms quantum, and state the trade-off in one sentence.

Twenty users must each see a response within 100 ms. What is the maximum average quantum, ignoring I/O and switch cost?

Interview-style: "Why does a hardware timer interrupt have to be privileged?" Hint: imagine a process that could disable or reprogram it.

Personal and Mobile Systems

Theory

By the late 1970s hardware had inverted the original economics: the machine became cheap and the human expensive. If a computer serves one person, protecting users from each other looks like pure overhead — and early personal systems (CP/M, MS-DOS, classic Mac OS) duly discarded it. They were single-user, single-tasking, with no memory protection and no privilege separation; any program could scribble anywhere, and one bad pointer took down the machine.

That simplification was rolled back over two decades, for a reason worth remembering: protection is not primarily about users, it is about faults and malice. Even with one human present, the machine runs dozens of mutually distrusting programs, some downloaded minutes ago. Windows NT, Mac OS X, and Linux all reintroduced full multitasking, memory protection, and privilege levels on personal machines. Emphasis shifted from throughput to user experience: latency, responsiveness of the GUI, and rich device support.

Mobile systems then added a new dominant constraint: energy. On a phone, the scarcest resource is battery charge, and the second scarcest is thermal headroom. This inverts several classic assumptions:

Classic desktop assumption	Mobile reality
Idle CPU is wasted capacity	Idle CPU should be powered down aggressively
Background processes may run freely	Background execution is restricted and batched to allow deep sleep
Swap to disk when memory is short	Flash wear and latency discourage swap; kill or compress instead
App runs until it exits	The OS may suspend or terminate an app at any time; apps must checkpoint state

Android and iOS are UNIX-derived kernels (Linux and XNU respectively) wrapped in aggressive power management, a strict application lifecycle, and per-application sandboxing that is far stricter than traditional user-based protection.

Example

   Where the scarce resource moved

   1960s mainframe : CPU time      -> maximise utilisation
   1980s PC        : nothing much  -> maximise simplicity (and it showed)
   2000s desktop   : user attention-> maximise responsiveness
   2010s+ mobile   : battery/heat  -> maximise idle, minimise wakeups

   Mobile app lifecycle (the OS, not the app, is in charge)

   [not running] --launch--> [foreground] --user leaves--> [background]
        ^                         ^                              |
        |                         |                        (seconds later)
        |                    --resume--                          v
        +---------memory pressure: killed--------------- [suspended]

// Mobile apps must assume they can be suspended or killed at any moment.
override fun onPause() {
    super.onPause()
    saveDraftToDisk()      // the OS may never give us another chance to run
}

override fun onStop() {
    super.onStop()
    releaseCamera()        // holding a device awake or busy drains the battery
}

Key takeaways

Early personal systems dropped protection because there was one user; that reasoning was wrong, because protection guards against faults and hostile code, not just other people.
Modern desktop systems are time-sharing systems optimised for interactive latency rather than throughput.
Mobile systems treat energy and thermal budget as the primary scarce resources.
Mobile OSes own the application lifecycle: apps must save state defensively because they can be suspended or killed without warning.

🧪 Practice

List three OS features that make sense on a laptop but are actively harmful on a phone, and explain the energy reasoning for each.

MS-DOS had no memory protection. Describe two concrete failure modes this caused, and name the hardware feature that eliminates each.

Interview-style: "Why does a phone kill background apps instead of swapping them out?" Hint: consider flash write endurance, wake-ups, and latency together.

Distributed and Cloud Systems

Theory

Once machines are networked, the natural question is whether the OS abstraction should stop at the box. Two answers emerged.

A distributed operating system tries to make a cluster of machines look like one computer: a single process namespace, transparent remote execution, a shared file system. Research systems (Amoeba, Plan 9, Sprite) pursued this. The approach collides with hard realities — partial failure (one node dies while others continue), unbounded network latency, and the impossibility of a global instantaneous view — which is why the pure form never became mainstream.

The pragmatic answer, which won, is a network operating system: each machine keeps its own conventional OS, and distribution is provided by services and middleware above it — remote file systems (NFS), RPC frameworks, message brokers, distributed databases, orchestration layers. Transparency is partial and explicit, and failures are visible so applications can handle them.

Cloud computing reframes all of this as a resource market. The provider runs an enormous multiprogrammed system whose "jobs" are entire virtual machines or containers; the classic OS problems reappear one level up:

Classic OS problem	Cloud equivalent
CPU scheduling among processes	Placing and scheduling VMs/containers across a fleet
Memory allocation and protection	VM memory partitioning, ballooning, cgroup limits
File systems	Object storage and distributed file systems
Device drivers	Virtual devices and paravirtualised I/O
Process isolation	Hypervisor and namespace isolation between tenants

The result is a two-level structure: a hypervisor or container runtime multiplexes hardware among guests, and each guest OS multiplexes its slice among processes. Chapters 13 and 14 return to both layers in detail.

Example

   DISTRIBUTED OS (single system image)      NETWORK OS / CLOUD (explicit)

   +-----------------------------+           +--------+ +--------+ +--------+
   |   one logical system        |           | Linux  | | Linux  | | Linux  |
   |  proc A   proc B   proc C   |           | + apps | | + apps | | + apps |
   +-----------------------------+           +--------+ +--------+ +--------+
     node1     node2     node3                    \        |        /
     (the boundary is hidden)                      \    network    /
                                                    +-- services --+
                                                    NFS, RPC, queues,
                                                    orchestration

   Cloud stack (OS problems, one level up)

   +----------------------------------------+
   |  containers / processes per tenant     |
   +----------------------------------------+
   |  guest OS kernels                      |
   +----------------------------------------+
   |  hypervisor: schedules vCPUs, memory   |
   +----------------------------------------+
   |  physical host                         |
   +----------------------------------------+

# Local call vs remote call: the abstraction looks similar, the failure modes do not.
value = local_dict["k"]        # fails only if the key is missing

resp = requests.get(url,       # may hang, time out, partially succeed,
                    timeout=2) # or succeed while the reply is lost
resp.raise_for_status()        # remote work needs explicit failure handling,
                               # retries, idempotency, and timeouts

Key takeaways

Distributed OSes aimed for a single system image; partial failure and latency kept the pure model out of the mainstream.
Network OSes plus middleware won: each node keeps its own kernel, distribution is explicit.
Cloud platforms replay classic OS resource management at fleet scale, with VMs and containers as the scheduled units.
The defining difference from a single machine is partial failure — parts of the system fail while others keep running.

🧪 Practice

Name three guarantees a local OS gives you that a distributed system cannot give cheaply, and say what breaks each one.

Map four classic OS mechanisms onto their cloud counterparts, in your own words.

Interview-style: "Why is transparent remote memory access harder than transparent remote file access?" Hint: compare the latency and failure semantics each interface implicitly promises.

1.3 System Architecture

An operating system is only as capable as the hardware allows; this section covers the machine features — interrupts, the storage hierarchy, and I/O paths — that every kernel mechanism is built on.

Computer System Organization

Theory

A modern computer is not a CPU with peripherals attached; it is a set of independent processors sharing memory. The CPU is one of them. The disk controller, the network interface, the GPU, and the DMA engine are others, each with its own local buffers and its own execution, all contending for the same system bus and the same RAM.

The consequences shape the entire kernel:

Concurrency is physical, not simulated. While the CPU executes instructions, a disk controller can be writing into memory. The kernel must reason about memory being modified by something other than the CPU.
Devices need a way to report completion. Since they run independently, they signal the CPU asynchronously via interrupt request lines feeding an interrupt controller.
The bus is a shared, finite resource. Bandwidth contention between CPU and devices is real, which is why DMA and cache design matter.

The boot sequence reveals the structure. On power-up the CPU begins executing firmware (BIOS/UEFI) from a fixed address in ROM — the bootstrap program. It runs power-on self-test, initialises devices enough to read from them, locates a bootloader, and hands over; the bootloader loads the kernel image into memory and jumps to its entry point. The kernel then initialises its subsystems, mounts a root file system, and starts the first user process (init/systemd/launchd), after which the machine is event-driven forever: it does nothing until an interrupt, trap, or system call demands attention.

Example

   Structure of a modern machine

     +---------+   +---------+          +--------------------+
     |  CPU 0  |   |  CPU 1  |          |   Memory (RAM)     |
     | +-----+ |   | +-----+ |          |                    |
     | | L1  | |   | | L1  | |          +---------+----------+
     | +--+--+ |   | +--+--+ |                    |
     +----+----+   +----+----+                    |
          |             |                         |
     =====+=============+=========================+========= system bus
               |                |                |
        +------+-----+   +------+-----+   +------+-----+
        | disk ctrl  |   | NIC        |   | GPU        |
        | +buffer    |   | +buffer    |   | +VRAM      |
        +------+-----+   +------+-----+   +------------+
               |                |
          [ SSD ]          [ network ]

        every controller runs concurrently with the CPUs
        and raises interrupts through the interrupt controller

   Boot sequence

   power on -> firmware (ROM) -> POST -> bootloader (GRUB/UEFI app)
            -> kernel image loaded -> kernel init (memory, drivers, FS)
            -> mount root -> start PID 1 -> idle, waiting for events

dmesg | head -40            # the kernel's own account of initialising the machine
lspci                       # the independent controllers sharing your bus
cat /proc/interrupts        # per-device, per-CPU interrupt counts

Key takeaways

A computer is several independent processors (CPUs and device controllers) sharing memory and a bus.
Device concurrency is genuine hardware parallelism, not an OS illusion.
Bootstrapping proceeds from firmware in ROM through a bootloader to the kernel, ending at the first user process.
After boot, the system is purely event-driven: it reacts to interrupts, traps, and system calls.

🧪 Practice

Inspect /proc/interrupts and identify which devices interrupt most. Explain why those, and what it implies about kernel CPU cost.

Why must the bootstrap program live in non-volatile memory at a fixed address? What would break otherwise?

Interview-style: "What is the first user-mode process, and why does the kernel need one at all?" Hint: think about who starts everything else and what happens if it exits.

Interrupts and Traps

Theory

The kernel needs a way to regain control of the CPU: when a device finishes work, when a program misbehaves, when a program requests a service, and when a time slice expires. All four use the same underlying machinery — an interrupt, which diverts the CPU from its current instruction stream to a handler.

There are two families, distinguished by their source:

	Interrupt (asynchronous)	Trap / exception (synchronous)
Source	External hardware device	The currently executing instruction
Timing	Any time; unrelated to running code	Exactly at a known instruction
Examples	Disk complete, timer tick, key press, NIC packet	Divide by zero, page fault, invalid opcode, `syscall`
Reproducible	No	Yes, given the same state

Traps split further into faults (correctable — resume the offending instruction, as with a page fault), traps proper (deliberate — resume the next instruction, as with a system call), and aborts (unrecoverable hardware errors).

The mechanism is uniform. Each cause has a number; the number indexes an interrupt vector table (Linux/x86: the IDT) that the kernel populates at boot with handler addresses. On an event, the hardware saves minimal state (program counter, flags), switches to kernel mode and a kernel stack, and jumps through the vector. The handler saves the remaining registers, does its work, restores state, and executes a return-from-interrupt instruction that atomically restores mode and resumes the interrupted stream.

Two practical concerns dominate handler design. Latency: handlers run with some interrupts disabled, so a slow handler delays everything, which is why Linux splits work into a top half (fast, in interrupt context) and a bottom half (deferred, softirq/tasklet/workqueue). Priority and nesting: an interrupt controller assigns priorities so urgent events can preempt less urgent handlers.

Example

   Interrupt-driven control flow

   user process        |  hardware/kernel
   ------------------- + ---------------------------------------------
   ... executing ...   |
   MOV  R1, [X]        |
                       |  <-- device asserts IRQ line
   (instruction        |  CPU: finish current instruction,
    boundary)          |       push PC + FLAGS, switch to kernel mode,
                       |       look up vector N in the IDT, jump
                       |  handler: save registers
                       |           acknowledge the device
                       |           copy data / wake blocked process
                       |           restore registers
                       |  IRET: restore PC, FLAGS, and user mode
   ADD  R2, R1         |  <-- resumes as if nothing happened

/* A simplified vector table and dispatch, the shape every CPU uses. */
typedef void (*handler_t)(struct regs *);
handler_t idt[256];                  /* one entry per interrupt/trap number */

void init_interrupts(void) {
    idt[0]   = divide_by_zero_trap;  /* trap: fault, raised by the instruction */
    idt[14]  = page_fault_trap;      /* trap: fault, kernel may fix and retry  */
    idt[32]  = timer_interrupt;      /* interrupt: asynchronous, from the PIT  */
    idt[46]  = disk_interrupt;       /* interrupt: asynchronous, from the disk */
    idt[128] = system_call_trap;     /* trap: deliberate, requested by software*/
}

void dispatch(int vector, struct regs *r) {
    idt[vector](r);                  /* hardware supplies the vector number    */
}

Key takeaways

Interrupts are asynchronous and device-driven; traps are synchronous and instruction-driven.
Faults resume the offending instruction, traps resume the next one, aborts do not resume at all.
The vector table maps each cause to a handler; hardware switches mode and stack automatically.
Handlers must be short; long work is deferred to bottom halves to keep interrupt latency low.

🧪 Practice

Classify each: pressing a key, int 0x80, dereferencing a null pointer, a machine-check error, a page fault on a valid but swapped-out page.

Explain why the return-from-interrupt instruction must restore the privilege level and the program counter atomically. What attack becomes possible otherwise?

Interview-style: "Why can't an interrupt handler call a function that might block?" Hint: ask which process's context the handler is borrowing, and who would be put to sleep.

Storage Hierarchy

Theory

No single memory technology is simultaneously fast, large, cheap, and persistent — physics forbids it. Systems therefore stack several technologies into a hierarchy, each level larger, slower, and cheaper per byte than the one above.

Level	Typical size	Typical latency	Volatile	Managed by
Registers	< 1 KB	~0.3 ns	Yes	Compiler
L1 cache	32-64 KB	~1 ns	Yes	Hardware
L2/L3 cache	0.5-64 MB	4-40 ns	Yes	Hardware
Main memory	8-512 GB	~80 ns	Yes	OS (paging)
Flash/SSD	0.25-8 TB	20-100 microseconds	No	OS (file system)
Hard disk	1-20 TB	5-10 ms	No	OS (file system)
Tape/archive	petabytes	seconds to minutes	No	OS + operator

The hierarchy works only because of locality of reference. Temporal locality: a byte used now is likely to be used again soon. Spatial locality: a byte used now makes its neighbours likely next. Real programs exhibit both, so a small fast level can serve the great majority of accesses from a large slow one behind it.

Every level is a cache of the level below, and each raises the same three questions: what to keep, what to evict, and how to stay consistent when a copy is modified. The OS is directly responsible for two of these levels — RAM as a cache of disk (Chapter 8) and the buffer cache as a cache of file blocks (Chapter 10) — and must respect the hardware-managed ones through cache-friendly data structures.

The numbers are the point. If a memory access is one second in human terms, an SSD access is about a day and a disk seek about four months. Any design that turns a memory access into a disk access has changed its cost by five orders of magnitude, which is why page-fault behaviour dominates performance in Chapter 8.

Example

        smaller, faster, costlier per byte
              ^
              |   +-------------+
              |   |  registers  |  <1 KB      0.3 ns
              |   +-------------+
              |   |  L1 cache   |  64 KB      1 ns
              |   +-------------+
              |   |  L2/L3      |  32 MB      10-40 ns
              |   +-------------+
              |   | main memory |  32 GB      80 ns
              |   +-------------+
              |   |  SSD        |  1 TB       50 us     <- persistent below here
              |   +-------------+
              |   |  hard disk  |  8 TB       8 ms
              |   +-------------+
              |   |  tape       |  PB         minutes
              v   +-------------+
        larger, slower, cheaper per byte

# Locality is not theoretical: identical work, different access order.
N = 4096
matrix = [[1.0] * N for _ in range(N)]

total = 0.0
for i in range(N):            # row-major traversal: consecutive addresses
    for j in range(N):        # each cache line brings in the next values needed
        total += matrix[i][j] # high spatial locality -> mostly cache hits

total = 0.0
for j in range(N):            # column-major traversal over row-major storage
    for i in range(N):        # each access lands on a different cache line
        total += matrix[i][j] # poor locality -> often several times slower

Key takeaways

The hierarchy trades speed against capacity and cost; no level is optional.
It only works because programs exhibit temporal and spatial locality.
Every level is a cache of the one below, with placement, eviction, and coherence questions.
Latency gaps span orders of magnitude, so crossing a level is a performance event, not a detail.

🧪 Practice

Given a 90% cache hit rate, 1 ns hits and 80 ns misses, compute the average access time. Recompute at 99%. Comment on the sensitivity.

Run the two loops above with a large matrix in C or NumPy and measure both. Explain the ratio in terms of cache lines.

Interview-style: "Which levels of the hierarchy does the OS manage, and which does it only influence?" Hint: ask which transfers require a software decision and which happen without any instruction executing.

I/O Structure

Theory

I/O is where the CPU meets a world that is millions of times slower than it is, and the structure of I/O handling is essentially a set of strategies for not wasting the CPU while waiting.

A device is reached through its controller, which exposes registers: a data register, a status register (busy, ready, error), a command register, and often a control register. The CPU accesses them either through dedicated I/O instructions on separate port addresses (in/out on x86) or, more commonly today, through memory-mapped I/O, where the registers appear at physical addresses and ordinary loads and stores reach them.

Given that interface, there are three ways to run a transfer:

Strategy	How it works	CPU cost	Good for
Programmed I/O (polling)	CPU loops reading the status register until ready, then moves the data itself	Very high; CPU burns cycles waiting	Tiny transfers, very fast devices, early boot
Interrupt-driven I/O	CPU issues the request, blocks the process, and is interrupted on completion	One interrupt per transfer unit; CPU still copies bytes	Character devices, moderate rates
DMA	A DMA engine moves the data directly to or from memory; one interrupt for the whole block	Lowest; CPU is free during the transfer	Disks, networking, any bulk transfer

Polling is not always wrong: at very high device speeds (NVMe, 100 Gb networking) the cost of taking an interrupt can exceed the wait, which is why modern drivers use hybrid schemes (Linux NAPI switches from interrupts to polling under load).

The OS layers this into a device driver per device that hides the register-level protocol behind a uniform kernel interface, so the file system and network stack never touch a status register.

Example

   Three ways to read one block

   POLLING                INTERRUPT-DRIVEN            DMA
   -------                ----------------            ---
   issue cmd              issue cmd                   program DMA (addr,len)
   while(!ready);         block the process           block the process
   for each word:         (CPU runs other work)       (CPU runs other work;
     copy word            interrupt on ready           device writes RAM itself)
   done                   handler copies words        interrupt when block done
                          resume process              resume process
   CPU busy: 100%         CPU busy: per word/IRQ      CPU busy: 2 events total

/* Programmed I/O: correct, simple, and wasteful. */
int pio_read_block(uint8_t *dst, int nwords) {
    outb(CMD_REG, CMD_READ);                    /* tell the device what to do   */
    while ((inb(STATUS_REG) & STATUS_READY) == 0)
        ;                                       /* spin: the CPU does nothing   */
    for (int i = 0; i < nwords; i++)
        dst[i] = inw(DATA_REG);                 /* CPU personally moves each word */
    return nwords;
}

/* Memory-mapped I/O: the same registers reached as memory. */
volatile uint32_t *ctrl = (volatile uint32_t *)0xFED00000; /* volatile: never cache
                                                              or reorder these */
ctrl[CMD] = CMD_READ;                            /* a store that starts a device */

Key takeaways

Devices are driven through controller registers, accessed via port I/O or memory-mapped I/O.
Polling wastes CPU but has the lowest latency and no interrupt overhead; it wins for very fast devices.
Interrupt-driven I/O frees the CPU during the wait but costs one interrupt per unit of transfer.
Device drivers exist to hide all of this behind a uniform kernel-internal interface.

🧪 Practice

A device delivers a byte every 5 microseconds. Compare polling and interrupt-driven I/O for a 4 KB transfer, assuming 2 microseconds of interrupt overhead per event.

Explain why device register pointers must be declared volatile in C, and give a concrete bug caused by omitting it.

Interview-style: "When is polling faster than interrupts?" Hint: compare interrupt entry/exit cost with expected wait time on an NVMe device.

Direct Memory Access

Theory

Interrupt-driven I/O still leaves the CPU doing the actual copying: for a 4 KB block, that is a thousand loads and stores of data the CPU has no interest in. Direct Memory Access removes the CPU from the data path entirely. A DMA controller — today usually built into the device itself, as a bus-mastering peripheral — is told a memory address, a length, and a direction, and it performs the transfer over the bus while the CPU executes unrelated code. One interrupt is raised when the whole block is done.

The gain is dramatic: interrupts per 4 KB block fall from hundreds or thousands to one, and the CPU is available throughout. This is what makes gigabyte-per-second storage and 10+ Gb/s networking feasible at all.

DMA is not free of consequences, and each one shapes kernel code:

Cache coherence. The device writes RAM directly, so stale copies may sit in the CPU cache. Either the hardware snoops the bus (usual on x86) or the driver must explicitly flush/invalidate ranges (common on ARM embedded parts).
Physical addresses and pinning. The DMA engine typically works with physical addresses and knows nothing of page tables, so target pages must be pinned in memory and physically contiguous (or described by a scatter-gather list).
Protection. A device that can write anywhere in RAM is a security hole — the basis of DMA attacks over Thunderbolt/PCIe. An IOMMU solves this by giving devices their own address translation, so a device can only touch memory explicitly mapped for it.
Ordering. The completion interrupt must not be observed before the data lands; memory barriers and correctly ordered descriptor writes are essential.

Analogy: interrupt-driven I/O is carrying boxes yourself, one at a time, whenever the courier rings. DMA is giving the courier a key to the storeroom and asking to be told once when everything is delivered. Faster, and exactly as risky as it sounds — which is what the IOMMU is for.

Example

   WITHOUT DMA                          WITH DMA

   device --> CPU register --> RAM      device -----------------> RAM
              (every word)                        (bus master)
                                        CPU: free to run other processes
   CPU: consumed by copying             one completion interrupt at the end

   Transfer setup and completion

   1. driver allocates a pinned buffer, gets its physical address
   2. driver programs: src=device, dst=0x3F2A0000, len=4096, dir=to-memory
   3. driver starts the engine, blocks the process, returns to the scheduler
   4. DMA engine moves 4096 bytes across the bus (CPU runs other work)
   5. engine raises ONE interrupt: "transfer complete"
   6. handler invalidates caches if needed, marks the process READY

/* Typical driver-side DMA setup (Linux-flavoured, simplified). */
dma_addr_t dma_handle;
void *buf = dma_alloc_coherent(dev, 4096, &dma_handle, GFP_KERNEL);
/* dma_alloc_coherent gives a buffer that is:
     - physically contiguous
     - pinned (never swapped or moved)
     - coherent between CPU cache and device, or accompanied by sync calls
   dma_handle is the address the DEVICE uses; buf is the address the CPU uses.
   With an IOMMU they differ, and the device can reach nothing else. */

writel(dma_handle, dev->base + REG_DMA_ADDR);   /* where to put the data */
writel(4096,       dev->base + REG_DMA_LEN);    /* how much              */
wmb();                                          /* barrier: all of the above
                                                   must be visible before start */
writel(START_READ, dev->base + REG_CMD);        /* go; CPU is now free    */

Key takeaways

DMA lets a device transfer directly to or from memory, reducing the CPU to setup plus one completion interrupt.
It is what makes high-bandwidth storage and networking possible.
Its costs are cache coherence, buffer pinning with physical or scatter-gather addressing, and ordering barriers.
Unrestricted DMA is a serious security risk; an IOMMU confines each device to explicitly mapped memory.

🧪 Practice

A 1 MB transfer moves in 64-byte units. Compute the number of interrupts with interrupt-driven I/O versus DMA, and the CPU time saved at 2 microseconds per interrupt.

Explain why a DMA target buffer must be pinned. What would go wrong if the OS swapped that page out mid-transfer?

Interview-style: "How does an IOMMU differ from an MMU, and what attack does it stop?" Hint: one translates for the CPU, the other for devices; think about a malicious PCIe card.

1.4 Operating System Structures

Kernels must decide how much code runs with full privilege and how that code is decomposed; the answers form a spectrum from one large privileged blob to a minimal core surrounded by unprivileged servers.

Monolithic Kernels

Theory

In a monolithic kernel, the entire operating system — scheduler, memory manager, file systems, network stack, device drivers — is compiled into a single program that runs in kernel mode, in one address space. Any part can call any other part with an ordinary function call.

This is the oldest structure and, measured by deployed machines, overwhelmingly the winner: Linux, the BSDs, and traditional UNIX are all monolithic (Linux is more precisely a modular monolith, covered below).

The advantage is performance and simplicity of interaction. A file system read that needs a disk block calls the block layer directly: one function call, nanoseconds, no marshalling, shared data structures. There is no boundary to cross between subsystems.

The costs are equally structural:

No fault isolation. A bug in any driver can corrupt any kernel data structure. Drivers are the majority of kernel code and the least reviewed, and they run with full privilege over everything.
Weak enforced modularity. Nothing stops a subsystem from reaching into another's internals; discipline is by convention and review, not by hardware.
Large trusted computing base. Millions of lines run privileged, so the attack surface is enormous.
Maintenance friction. Changing a widely used internal interface means touching many subsystems at once.

Analogy: an open-plan workshop where every tool is within arm's reach. Work is fast because nothing is locked away, and one careless person with an angle grinder can ruin everyone's project.

Example

   MONOLITHIC KERNEL

   user mode   | applications                         |
   ------------+--------------------------------------+  system call boundary
   kernel mode | +----------------------------------+ |
               | | syscall interface                | |
               | | file systems | network stack     | |
               | | scheduler    | memory manager    | |
               | | device drivers (bulk of the code)| |
               | +----------------------------------+ |
               |   one address space, one privilege   |
   -------------------------------------------------+
                            hardware

   A file read never leaves kernel mode:
     sys_read() -> vfs_read() -> ext4_file_read() -> block layer -> driver
     all plain function calls

/* Inside a monolithic kernel: direct calls, shared structures, zero ceremony. */
ssize_t vfs_read(struct file *f, char __user *buf, size_t n, loff_t *pos) {
    if (!(f->f_mode & FMODE_READ))
        return -EBADF;
    return f->f_op->read(f, buf, n, pos);  /* straight into the file system,
                                              which calls the block layer,
                                              which calls the driver --
                                              all at full privilege, no IPC */
}

Key takeaways

All OS services run privileged in one address space and call each other directly.
Excellent performance: no boundary crossings between subsystems.
No fault isolation — a single driver bug can compromise the whole kernel.
The trusted computing base is very large, which is a security and maintenance liability.

🧪 Practice

Run wc -l over a kernel source tree's drivers/ directory versus the rest. What does the ratio imply about where kernel bugs come from?

Give two concrete failure scenarios that a monolithic design cannot contain but a microkernel could.

Interview-style: "If monolithic kernels have no fault isolation, why did they win?" Hint: weigh IPC cost per operation against the frequency of driver faults in mature code.

Layered Architecture

Theory

The layered approach imposes structure by decomposing the OS into N levels, where layer 0 is the hardware and layer N is the user interface. The defining rule: layer k may use only the services of layer k-1, and it exports a cleaner interface upward.

The appeal is intellectual control. Each layer can be designed, implemented, and debugged using only the layers beneath it, which are already correct — so verification proceeds bottom-up, and the dependency graph is acyclic by construction. Dijkstra's THE system (1968) demonstrated this with six layers, from processor allocation up through memory, console, I/O, and user programs.

Two problems keep pure layering rare in practice:

Layer definition is genuinely hard. Many services are mutually dependent. The memory manager may need to swap to disk, which needs the disk driver; but the disk driver needs memory for its buffers. Which layer is lower? Real systems break the cycle with pinned buffers and special cases — that is, by violating the model.
Performance. A request from the top must traverse every intermediate layer, each adding parameter checking and copying. A read might cross five layers and be copied at several of them.

The idea survives in weakened form nearly everywhere: the network stack is layered by protocol, the storage stack is layered (VFS, file system, block layer, driver), and hypervisors layer guests over hosts. The discipline is applied where the dependency structure genuinely permits it, and abandoned where it does not.

Example

   Layered OS (strict form)

   layer 5 | user programs                     |
   layer 4 | user interface / shell            |
   layer 3 | I/O management and buffering      |
   layer 2 | operator-console device driver    |
   layer 1 | memory management and swapping    |
   layer 0 | CPU allocation, multiprogramming  |
           +-----------------------------------+
             hardware

   Rule: each layer calls only downward, never sideways or upward.

   Cost of the discipline:

   read() -> layer4 checks args -> layer3 buffers -> layer2 driver call
          -> layer1 ensures pages -> layer0 blocks the process
   five interface crossings for one logical operation

   Layering that DID survive: the storage stack

   application            read("/data/f", buf, 4096)
       |
   VFS layer              uniform file operations, path resolution
       |
   file system (ext4)     inode -> logical block numbers
       |
   block layer            request queue, merging, I/O scheduling
       |
   device driver (NVMe)   submission/completion queues, registers
       |
   hardware

Key takeaways

Layering restricts each level to using only the level below, making the design acyclic and debuggable bottom-up.
Strict layering is rarely achievable because real OS services have circular dependencies.
Every layer crossing costs argument checking and often copying, which harms performance.
The idea persists in subsystem stacks (networking, storage) rather than as whole-kernel structure.

🧪 Practice

Sketch a five-layer OS and place: process scheduler, page swapper, disk driver, file system, shell. Justify each position.

Explain the memory-manager/disk-driver circular dependency concretely, and describe two ways real kernels break it.

Interview-style: "The TCP/IP stack is layered and fast. Why doesn't the layering argument hurt it as much?" Hint: consider where the copies happen and how much work each layer does per crossing.

Microkernels

Theory

The microkernel approach asks: what is the minimum that must run privileged? The answer is roughly address-space management, thread scheduling, and inter-process communication. Everything else — file systems, device drivers, network stacks, even paging policy — is moved into ordinary user-mode server processes, which communicate with each other and with applications by message passing through the kernel.

This inverts the monolithic trade-off:

Fault isolation is real and hardware-enforced. A crashing disk driver takes down one unprivileged process, which a supervisor can restart while the system keeps running.
The trusted computing base shrinks dramatically — seL4 is roughly 10,000 lines and has a machine-checked proof of functional correctness, which is inconceivable for a monolithic kernel.
Extensibility improves. Adding or replacing a file system means starting a different server, not rebuilding and rebooting the kernel.
Security policy becomes explicit, since every cross-component interaction is a message that can be mediated.

The historical cost is IPC overhead. What was one function call in a monolith becomes: user process → kernel → server → kernel → driver server → kernel → back, with context switches and data copying at each hop. First-generation microkernels (Mach) were slow enough that this became the standard objection. Second-generation designs (L4 and descendants) attacked it directly with tiny, register-based synchronous IPC, cutting the cost by more than an order of magnitude and making the argument much closer.

Microkernels dominate where assurance beats raw throughput: QNX in cars and medical devices, seL4 in security-critical systems, MINIX 3 running inside Intel's Management Engine, and the hypervisor-like cores of several phone secure worlds.

Example

   MICROKERNEL

   user mode | app | file | device | network | paging  |
             |     |server| driver | server  | server  |
   ----------+--+--+--+---+---+----+----+----+----+----+
                |     |       |         |         |
                +-----+---- messages ---+---------+
   kernel mode |  address spaces | threads | IPC          |
               |  (only these three things)               |
   ------------+------------------------------------------+
                            hardware

   A file read now crosses the boundary several times:

   app --msg--> [kernel] --> file server
   file server --msg--> [kernel] --> disk driver server
   disk driver talks to hardware, replies
   ... and back again

   Monolithic: 1 syscall, N function calls
   Microkernel: 1 syscall, 4-6 IPC round trips

/* Microkernel-style client: a "system call" is a message to a server. */
struct fs_request  req = { .op = FS_READ, .fd = fd, .len = 4096 };
struct fs_response resp;

ipc_call(FILE_SERVER, &req, sizeof req, &resp, sizeof resp);
/* The kernel: validates the sender, blocks this thread, copies (or maps)
   the message, and schedules the file server. The file server itself may
   ipc_call() the disk driver server. Every hop is a scheduling event --
   which is exactly why L4-family IPC is optimised so ferociously. */

Key takeaways

The kernel keeps only address spaces, threads, and IPC; all other services run as unprivileged servers.
Fault isolation and a tiny trusted computing base are the payoff — small enough for formal verification.
Message passing replaces function calls, so IPC performance determines whether the design is viable.
Microkernels dominate safety- and security-critical domains rather than general-purpose desktops.

🧪 Practice

Trace open("/etc/passwd") through a microkernel, listing every IPC hop and context switch. Compare with the monolithic path.

Explain how a microkernel can restart a crashed disk driver transparently. What state must be reconstructed, and who holds it?

Interview-style: "Why is seL4 formally verifiable when Linux is not?" Hint: think about lines of privileged code, and about what a proof must range over.

Modular Kernels

Theory

The modular (or loadable-module) approach is the pragmatic synthesis that most production systems actually use. The kernel remains monolithic — one address space, full privilege, direct calls — but is built from components that can be loaded and unloaded at runtime through well-defined internal interfaces.

This captures much of the microkernel's flexibility at none of its IPC cost:

Dynamic extensibility. A driver for hardware plugged in five minutes ago is loaded on demand; an unused subsystem never occupies memory.
Defined interfaces. Modules register through registration APIs (a file_system_type, a pci_driver struct) rather than by patching the kernel, so coupling is documented.
No performance penalty. Once loaded, a module is ordinary kernel code called directly. There is no boundary.
Faster development. Rebuild and reload one module rather than the whole kernel.

What it explicitly does not buy is isolation. A loaded module has full kernel privilege; a bug in it can panic the machine or corrupt anything. Modularity here is a software engineering property, not a protection property — a distinction worth being crisp about, because it is a common interview trap.

Linux is the canonical example, with thousands of modules; Solaris was built around the idea; FreeBSD's KLDs are the same concept. The recent trend is to add real safety to this model without a redesign — eBPF programs are verified before being allowed to run in kernel context, and Rust drivers use language-level guarantees, both aiming at "modules that cannot corrupt the kernel".

Example

   MODULAR MONOLITHIC KERNEL

   kernel mode | +-------------------------------------------+
               | | core: scheduler, memory, VFS, IPC, net    |
               | +----+------------+------------+------------+
               |      | registration interfaces              |
               |  +---+---+   +----+----+   +---+-----+
               |  | ext4  |   | nvme    |   | wifi    |  <- loadable modules,
               |  | module|   | driver  |   | driver  |     same privilege,
               |  +-------+   +---------+   +---------+     loaded on demand
               +-------------------------------------------+

   Loaded modules are NOT isolated. The dashed lines are interfaces,
   not protection boundaries.

lsmod | head                 # modules currently loaded
modinfo nvme                 # its declared interface, parameters, dependencies
sudo modprobe -r nvme        # unload (fails if in use -- reference counting)
sudo modprobe nvme           # load again on demand

/* A Linux module registers through a defined interface, then runs privileged. */
static struct file_system_type myfs_type = {
    .owner   = THIS_MODULE,
    .name    = "myfs",
    .mount   = myfs_mount,
    .kill_sb = kill_block_super,
};

static int __init myfs_init(void) {
    return register_filesystem(&myfs_type);  /* plug into the VFS at runtime */
}
static void __exit myfs_exit(void) {
    unregister_filesystem(&myfs_type);       /* clean removal, refcount permitting */
}
module_init(myfs_init);
module_exit(myfs_exit);

Key takeaways

Modular kernels keep the monolithic address space but load components dynamically through registration interfaces.
They gain extensibility and development speed with no IPC cost.
Modules run at full kernel privilege — this is modularity, not isolation.
eBPF verification and Rust drivers are attempts to add real safety to the module model.

🧪 Practice

Compare lsmod output on a laptop and a container host. Explain the differences in terms of hardware and workload.

Why can modprobe -r fail even when a module appears idle? Explain reference counting and give a scenario.

Interview-style: "Does loading a module as a .ko file make it safer than compiling it in?" Hint: separate deployment flexibility from privilege; ask what changes at run time.

Hybrid Designs

Theory

No shipping general-purpose OS is purely monolithic, purely layered, or purely microkernel. Hybrid designs deliberately mix structures, keeping performance-critical services in the kernel while pushing others out, and adopting microkernel-style message passing internally where the flexibility pays.

Three mainstream examples show the pattern:

Windows NT and successors. Structurally microkernel-influenced: a hardware abstraction layer, a small "kernel" layer handling scheduling and interrupts, and an Executive of subsystems above it. But the Executive, the graphics subsystem (moved into the kernel in NT 4.0 for performance), and drivers all run in kernel mode. Environment subsystems (Win32, and formerly POSIX/OS-2) run as user-mode processes, giving microkernel-style personalities on a monolithic core.
macOS/iOS (XNU — "X is Not UNIX"). Literally a hybrid: a Mach microkernel core providing IPC, virtual memory, and thread scheduling, with a full BSD kernel in the same address space providing the POSIX interface, file systems, and networking, plus the I/O Kit driver framework in C++. Mach's IPC and memory-object abstractions are used, but calls between Mach and BSD parts are function calls, not messages — the isolation is given up to reclaim the performance.
Linux with user-space components. Formally a modular monolith, but FUSE puts file systems in user space, DPDK and SPDK put network and storage drivers there for performance, and microVMs push isolation outward. The result is monolithic in structure and increasingly hybrid in deployment.

The honest reading: "hybrid" describes engineering compromise rather than a distinct theory. The recurring question is not which label applies but which components deserve the privilege and cost of living inside the kernel, and that answer changes as IPC cost, hardware features, and threat models change.

Example

   WINDOWS NT (simplified)

   user mode   | Win32 apps | subsystem processes (Win32, WSL) | services |
   ------------+-------------------------------------------------------+
   kernel mode | Executive: I/O mgr, object mgr, memory mgr, security  |
               | Kernel layer: scheduling, interrupts, synchronisation |
               | Drivers | Graphics (moved in for speed)               |
               | Hardware Abstraction Layer (HAL)                      |
   ------------+-------------------------------------------------------+

   XNU (macOS/iOS)

   kernel mode | BSD layer: POSIX API, VFS, sockets, signals           |
               | Mach layer: IPC, VM, threads, scheduling              |
               | I/O Kit: C++ driver framework                         |
               | (all three share ONE address space -- the "hybrid")   |

   Where does a component belong? The recurring trade-off

   in-kernel                         out-of-kernel (user space)
   ---------                         --------------------------
   + no boundary crossings           + faults are contained
   + direct access to structures     + restart without reboot
   + lowest latency                  + easier to develop and debug
   - a fault kills the system        - IPC and copy costs per operation
   - enlarges the trusted base       - harder to reach hardware directly

   Examples of the same component on both sides:
     file systems : ext4 (in kernel)      vs sshfs/FUSE (user space)
     network      : Linux stack (kernel)  vs DPDK (user space)
     graphics     : Win32k (kernel)       vs X server (user space)

Key takeaways

Every mainstream OS is a hybrid; pure structural models are teaching devices, not products.
Windows NT layers a microkernel-influenced Executive but runs subsystems and drivers in kernel mode.
XNU combines a Mach core and a BSD kernel in a single address space, trading isolation for speed.
The real design question is per-component: does this service earn kernel privilege, given current IPC and hardware costs?

🧪 Practice

NT 4.0 moved the graphics subsystem from user mode into the kernel. State the gain and the cost, and say whether you would make the same call today.

Compare an in-kernel file system with the same file system over FUSE: list the performance and reliability differences you would expect, and design a benchmark to measure them.

Interview-style: "Is XNU a microkernel?" Hint: separate the provenance of the code from the address-space boundaries that actually exist at run time.

Exokernels

Theory

Every structure so far assumes the kernel should provide abstractions. The exokernel (MIT, mid-1990s) challenges exactly that assumption, with a sharp argument: abstractions are policy, and policy in the kernel is imposed on everyone, including applications that would do better with a different one.

A database knows its own access patterns and would like to control disk layout and its own buffer replacement; the kernel's general-purpose page cache and file system get in the way. A garbage collector could avoid double paging if it knew about physical frames. A web server would like to lay out its own disk blocks.

The exokernel therefore does one thing: securely multiplex hardware resources — it tracks ownership of physical pages, disk blocks, and CPU time, and enforces protection — while providing no abstractions at all. Applications link against a library operating system (libOS) that implements files, virtual memory, and processes in user space, and may replace any of it.

Separation of protection from management. The kernel decides who may use a block; the libOS decides what it means.
Application-level flexibility. Different applications on one machine can use entirely different file systems or paging policies.
Performance from specialisation. Aegis/ExOS demonstrated order-of-magnitude improvements on operations where the general abstraction was a poor fit.
Costs: protection without abstraction is genuinely hard (tracking ownership of raw blocks securely is subtle), sharing between differently-abstracted applications becomes awkward, and application programmers must either use a libOS or handle hardware detail.

Exokernels never shipped commercially, but the idea is now everywhere in disguise: unikernels (MirageOS, IncludeOS) are libOS designs; user-space networking (DPDK) and storage (SPDK) bypass kernel abstractions for exactly the stated reason; io_uring reduces kernel mediation; and virtual machines are arguably exokernels that expose a hardware-shaped interface to guest libOSes.

Example

   TRADITIONAL                          EXOKERNEL

   app                                  app + libOS A   app + libOS B
    | files, VM, processes               | own FS,       | own FS,
   ---------------------                 | own paging    | log-structured
   kernel: abstractions                 -----------------------------------
   kernel: multiplexing                  exokernel: secure multiplexing only
   ---------------------                 (owns: which app holds which frame,
   hardware                               block, and time slice)
                                        -----------------------------------
                                         hardware

   The kernel enforces WHO may touch a resource.
   The libOS decides WHAT that resource means.

/* Exokernel-flavoured: the application manages physical resources itself. */
/* Ask for specific physical disk blocks, not a file. */
blockno_t blocks[64];
exo_disk_alloc(disk_id, 64, blocks);        /* kernel: ownership + protection */

/* The libOS -- not the kernel -- decides what these blocks mean. */
my_db_layout_index(blocks, 32);             /* application-specific layout    */
my_db_layout_heap(blocks + 32, 32);         /* tuned to this workload exactly */

/* Same idea, shipping today: user-space storage via SPDK. */
spdk_nvme_ns_cmd_read(ns, qpair, buf, lba, count, cb, arg, 0);
/* The kernel is out of the data path entirely; the application owns
   queueing, buffering, and scheduling policy. */

Key takeaways

Exokernels remove abstractions from the kernel, keeping only secure multiplexing of physical resources.
Applications link a library OS and can implement or replace file systems, paging, and process models.
The motivating insight is that kernel abstractions embed policy that suits average applications, not specific ones.
The design never went mainstream, but unikernels, DPDK/SPDK, io_uring, and VMs all reuse its core idea.

🧪 Practice

Name two applications that would clearly benefit from managing their own disk layout, and state the specific abstraction that hurts them today.

Explain how an exokernel enforces protection over raw disk blocks without understanding files. What must it track, and what attack must it prevent?

Interview-style: "In what sense is a hypervisor an exokernel?" Hint: compare what each multiplexes, and what plays the role of the library OS.

1.5 System Interfaces

This section examines the boundary itself: how a program crosses from its own world into the kernel's, what hardware makes the crossing safe, and which layers of software sit on top of it.

System Calls

Theory

A user program cannot touch hardware, allocate physical memory, or read a disk — it lacks the privilege. Yet programs plainly do all of these things. The bridge is the system call: a controlled, deliberate request for the kernel to perform a privileged operation on the caller's behalf.

The crucial property is that it is not a function call into a library. It is an interface between protection domains, with three defining characteristics:

Privilege transition. The CPU changes from user mode to kernel mode as part of the call, and back on return.
Controlled entry point. Control does not land wherever the caller says. The hardware jumps to one fixed kernel entry point, which dispatches on a call number. A program cannot enter the middle of a kernel routine, only the front door.
Distrust of arguments. Every argument comes from a potentially hostile program and must be validated: pointers checked against the caller's address space, lengths bounded, file descriptors verified as open and permitted.

System calls group into a small number of categories, and this list is essentially a table of contents for the rest of the book:

Category	Examples	Covered in
Process control	`fork`, `execve`, `exit`, `wait`, `kill`	Chapter 2
File management	`open`, `read`, `write`, `close`, `lseek`, `stat`	Chapter 10
Device management	`ioctl`, `read`, `write`, `mmap`	Chapter 11
Information	`getpid`, `time`, `uname`, `sysinfo`	this chapter
Communication	`pipe`, `socket`, `send`, `recv`, `shmget`	Chapter 2
Protection	`chmod`, `setuid`, `umask`, `capset`	Chapter 12

Linux has roughly 350 system calls; Windows has far more native calls but exposes them through documented APIs instead. The count matters less than the principle: the system call interface is the entire legitimate surface between applications and the kernel, and it is therefore both the compatibility contract and the security perimeter.

Example

   The system call boundary

   user mode   |  program                                     |
               |    write(1, "hi", 2)                         |
               |       |                                      |
               |    libc wrapper: put 1 in rax (call number), |
               |    args in rdi/rsi/rdx, execute SYSCALL      |
   ============|=======|======================================| privilege change
   kernel mode |    single entry point: entry_SYSCALL_64      |
               |    validate rax < NR_syscalls                |
               |    call sys_call_table[rax] -> sys_write()   |
               |    validate fd, validate user pointer+len    |
               |    do the work, put result in rax            |
               |    SYSRET                                    |
   ============|======================================================
   user mode   |    check return value, set errno if negative |

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

int main(void) {
    /* The ordinary way: a libc wrapper that hides the mechanism. */
    write(1, "via libc\n", 9);

    /* The same kernel service, invoked directly by call number. */
    syscall(SYS_write, 1, "via syscall()\n", 14);

    /* Error convention: kernel returns a negative errno; libc converts it. */
    int n = write(-1, "x", 1);            /* an invalid file descriptor */
    if (n < 0)
        perror("write");                  /* prints: write: Bad file descriptor */
    return 0;
}

gcc demo.c -o demo && strace -e trace=write ./demo
# Every crossing of the boundary is visible, and nothing else is.

Key takeaways

A system call is a protected request to the kernel, not a library function call.
It performs a privilege transition, enters at one fixed dispatch point, and validates every argument.
The system call set is the complete legitimate interface between user space and the kernel.
Return values follow a convention (negative errno in Linux) that the C library turns into -1 plus errno.

🧪 Practice

Run strace ls and count distinct system calls used. Group them into the six categories above.

Write a C program that calls getpid() via libc and via syscall(SYS_getpid), and time a million iterations of each. Explain the difference.

Interview-style: "Why must the kernel copy arguments from user memory rather than dereferencing user pointers directly?" Hint: consider a pointer to kernel memory, and a second thread modifying the buffer after validation.

System Call Implementation

Theory

Following one system call from instruction to instruction removes most of the mystery, and explains why the crossing is expensive.

The call number and the table. Since the kernel exposes one entry point, the caller must indicate which service it wants. It places an integer — the system call number — in a designated register (rax on x86-64, x8 on ARM64), and arguments in a fixed sequence of registers. The kernel uses that number to index the system call table, an array of function pointers. Bounds-checking that index is essential; an unchecked index is an immediate full-system compromise.

The instruction. Older x86 used a software interrupt (int 0x80) — correct but slow, since it goes through the full interrupt path. Modern CPUs provide dedicated fast instructions (syscall/sysret on x86-64, svc on ARM64) that switch mode with far less work by caching the kernel entry point and stack pointer in model-specific registers.

The crossing itself. The hardware switches to kernel mode, loads the kernel stack pointer for this thread, and jumps to the registered entry point. Kernel entry code then saves the user register set, switches to the kernel's view of memory, and dispatches. On return, the reverse happens.

Why it costs. Even a fast system call costs on the order of 100-300 ns — hundreds of times a function call. The costs are register save/restore, the mode switch, and, since Meltdown/Spectre, kernel page-table isolation (KPTI) which changes address space on every crossing, plus speculation barriers. This cost is why batching interfaces exist: readv/writev transfer multiple buffers per call, epoll reports many ready descriptors at once, io_uring uses shared submission and completion ring buffers to submit thousands of operations with no crossing at all, and vDSO maps a small kernel-provided page into every process so calls like gettimeofday() can be answered in user mode without any transition.

Example

   Anatomy of write(1, buf, 2) on x86-64

   USER                                  KERNEL
   ----                                  ------
   mov rax, 1        ; __NR_write
   mov rdi, 1        ; fd
   mov rsi, buf      ; buffer pointer
   mov rdx, 2        ; length
   syscall  ------------------------->   hardware: mode -> kernel,
                                         load kernel RSP, jump to entry
                                         entry_SYSCALL_64:
                                           save user registers
                                           swapgs; switch page tables (KPTI)
                                           cmp rax, __NR_syscall_max
                                           ja  bad_syscall        ; bounds check!
                                           call *sys_call_table[rax*8]
                                             sys_write():
                                               fdget(fd)          ; validate fd
                                               access_ok(buf,len) ; validate ptr
                                               vfs_write(...)     ; do the work
                                           restore registers
                                         sysret
   test rax, rax  <-------------------   result in rax (negative = -errno)
   js   error

/* The dispatch table, conceptually. */
typedef long (*syscall_fn)(long, long, long, long, long, long);

const syscall_fn sys_call_table[] = {
    [0]  = sys_read,
    [1]  = sys_write,
    [2]  = sys_open,
    [57] = sys_fork,
    /* ... roughly 350 entries ... */
};

long do_syscall(struct pt_regs *regs) {
    unsigned long nr = regs->rax;
    if (nr >= ARRAY_SIZE(sys_call_table))   /* MUST bounds check: an unchecked
                                               index is arbitrary kernel jump */
        return -ENOSYS;
    return sys_call_table[nr](regs->rdi, regs->rsi, regs->rdx,
                              regs->r10, regs->r8,  regs->r9);
}

# Why batching interfaces exist: the crossing, not the work, dominates.
# 1,000,000 single-byte writes  -> 1,000,000 crossings (~200 ns each = 0.2 s of pure overhead)
# 1,000 writes of 1000 bytes    ->     1,000 crossings (~0.0002 s)
# io_uring: submit 1,000,000 ops via a shared ring -> potentially 0 crossings

Key takeaways

The call number selects an entry in the system call table; bounds-checking it is a security requirement.
Modern CPUs provide dedicated fast entry instructions instead of software interrupts.
A crossing costs hundreds of nanoseconds — register save/restore, mode switch, KPTI page-table switch.
Batching (writev, epoll, io_uring) and the vDSO exist specifically to avoid or amortise crossings.

🧪 Practice

Measure the cost of a crossing: time 10 million getpid() calls, then 10 million calls to an empty local function. Explain the ratio.

gettimeofday() is often faster than getpid() despite doing more work. Explain why, in terms of the vDSO.

Interview-style: "What breaks if the kernel forgets to bounds-check the system call number?" Hint: the table is an array of function pointers, and the index came from the attacker.

API vs System Call

Theory

Application programmers almost never invoke system calls directly. They call an API — most often the C standard library, or a language runtime, or a framework — and the API calls the kernel. Understanding the distinction prevents a great deal of confusion about performance, portability, and errors.

	API (e.g. libc, Win32, java.io)	System call (e.g. `write`)
Runs in	User mode	Transitions to kernel mode
Defined by	A library specification (POSIX, Win32)	A specific kernel's ABI
Portability	Portable across systems implementing it	Tied to one kernel and architecture
Stability	Very stable, versioned	Stable on Linux, private on Windows/macOS
May do extra work	Yes: buffering, caching, retries, formatting	No: exactly the requested service

Three consequences matter in practice:

APIs may not call the kernel at all. printf() formats and buffers in user space and may issue no write until the buffer fills or is flushed — which is why output can appear out of order or be lost on a crash. malloc() usually satisfies requests from a user-space pool, calling brk/mmap only occasionally.
APIs may retry or adapt. A library read wrapper may loop over short reads or restart on EINTR; the raw call does not.
Portability lives in the API layer. Windows has no fork; macOS's raw call numbers are not stable and Apple explicitly requires going through libSystem. Writing against POSIX rather than a specific kernel ABI is what makes source portability possible at all.

Analogy: the system call is the factory loading dock; the API is the retail shop. The shop may keep stock on hand (buffering), split or combine your order (batching), and speak your language (portable naming), but the goods ultimately come from the same dock.

Example

   Layers between your code and the kernel

   application     printf("n = %d\n", n)
        |
   C library       format into a user-space buffer
        |          (may return here with NO kernel involvement)
        |          on flush: write(1, buf, len)
        |
   syscall stub    load rax=1, args in registers, SYSCALL
   ================================================== boundary
   kernel          sys_write -> vfs_write -> tty/pipe/file

#include <stdio.h>
#include <unistd.h>

int main(void) {
    /* API: buffered, formatted, portable. May issue zero system calls here. */
    printf("through the API\n");

    /* System call: unbuffered, exact, one crossing, right now. */
    write(1, "through the syscall\n", 20);

    /* Without a flush, the API line can appear AFTER the syscall line,
       because it is still sitting in a user-space buffer. */
    fflush(stdout);   /* forces the buffered data across the boundary */
    return 0;
}

strace -e trace=write ./demo          # to a terminal: line-buffered
strace -e trace=write ./demo > out    # to a file: fully buffered -- watch the
                                      # write() count collapse to one

Key takeaways

Applications call APIs; APIs call system calls. They are different layers with different guarantees.
An API call may perform no system call at all (buffering, caching, user-space allocation).
Portability is provided by the API layer, since kernel ABIs differ and some are unstable by policy.
Buffering explains many classic surprises: interleaved output, data lost on crash, and misleading write counts.

🧪 Practice

Run the demo above with output to a terminal and redirected to a file, under strace. Explain the different write counts.

Write a program that printfs then crashes via abort() without flushing. Explain what is lost and why.

Interview-style: "Why does Apple discourage direct system calls on macOS, while Linux guarantees its ABI forever?" Hint: ask what each vendor wants to be free to change, and where the compatibility contract is drawn.

Shells and Command Interpreters

Theory

The shell is the program that reads commands and asks the kernel to run them. It is worth studying not because command lines are important in themselves, but because the shell is the clearest small example of an OS interface built entirely out of system calls — and it demonstrates that the command interpreter is not part of the kernel.

A shell's main loop is short in principle: read a line, parse it, and either execute a builtin (a command the shell must implement itself) or run an external program. The distinction between the two is instructive. cd must be a builtin, because changing directory means calling chdir() in the shell's own process — a child process changing its own directory and exiting would accomplish nothing. ls is external, so the shell forks a child and replaces its image.

The classic UNIX pattern is fork() + execve() + wait():

fork() creates a near-identical child process; both continue from the same point, distinguished only by the return value.
execve() in the child replaces its memory image with a new program, keeping the process identity and open file descriptors.
wait() in the parent blocks until the child terminates and collects its exit status.

The apparent inefficiency of copying a process just to overwrite it is exactly what makes UNIX composable: between the fork and the exec, the child is an ordinary process that the shell can modify — redirect its file descriptors, change its working directory, drop privileges, join a process group. That window is how >, <, |, and job control are implemented, with no special support in the kernel or in the programs being run. Chapter 2 develops this in full.

Windows takes the alternative route: CreateProcess() does creation and program loading in one call with a large parameter block, which avoids the copy but folds all customisation into arguments.

Example

   Shell running `ls -l > out.txt`

   shell process
     |  fork()
     +-----------------> child process (a copy of the shell)
     |                     |  open("out.txt", O_WRONLY|O_CREAT|O_TRUNC)
     |                     |  dup2(fd, 1)      <- redirect stdout, the window
     |                     |  close(fd)           between fork and exec
     |                     |  execve("/bin/ls", ["ls","-l"], env)
     |                     |     (image replaced; fd 1 still points at out.txt)
     |  wait(&status) <----+  child exits
     |  print prompt

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

int main(void) {
    char line[256];
    while (printf("mysh$ "), fflush(stdout), fgets(line, sizeof line, stdin)) {
        line[strcspn(line, "\n")] = '\0';           /* strip the newline */
        if (line[0] == '\0') continue;

        if (strncmp(line, "cd ", 3) == 0) {         /* BUILTIN: must run in
                                                       this process to matter */
            if (chdir(line + 3) != 0) perror("cd");
            continue;
        }

        pid_t pid = fork();                          /* one call, two returns */
        if (pid == 0) {                              /* child: pid == 0 */
            char *argv[] = { line, NULL };
            execlp(argv[0], argv[0], (char *)NULL);  /* replaces this image */
            perror("exec");                          /* only reached on failure */
            _exit(127);
        } else if (pid > 0) {                        /* parent: pid == child */
            int status;
            waitpid(pid, &status, 0);                /* reap it; avoid zombies */
            if (WIFEXITED(status) && WEXITSTATUS(status))
                fprintf(stderr, "exit %d\n", WEXITSTATUS(status));
        } else {
            perror("fork");
        }
    }
    return 0;
}

Key takeaways

The shell is an ordinary user program, not part of the kernel; it can be replaced freely.
Builtins (cd, exit, export) must run in the shell's own process; everything else is fork + exec.
The gap between fork() and execve() is where redirection, pipes, and job control are implemented.
Windows CreateProcess() merges creation and loading, trading that customisation window for fewer copies.

🧪 Practice

Extend the shell above to support > redirection using open and dup2. Verify with strace -f.

Explain precisely why cd cannot be an external program. What would happen if you wrote /bin/cd and ran it?

Interview-style: "Why does UNIX separate fork from exec when almost every fork is followed immediately by an exec?" Hint: think about what the child can do in between, and how pipes would otherwise be implemented.

User Mode vs Kernel Mode

Theory

Everything in this chapter — protection, system calls, the kernel's authority — rests on one hardware feature: the CPU has at least two modes of execution, indicated by a mode bit (on x86, the current privilege level, rings 0 through 3; in practice ring 0 for the kernel and ring 3 for user code).

The mode determines what the running code is allowed to do:

	User mode (ring 3)	Kernel mode (ring 0)
Privileged instructions	Trap if attempted	Permitted
Memory reachable	Only pages mapped and marked user-accessible	All of physical memory
I/O access	Denied (no port I/O, no device registers)	Permitted
Interrupt control	Cannot disable interrupts	Can disable and mask
Page tables	Cannot modify	Owns them
Effect of a bug	One process dies	System panic or silent corruption

Privileged instructions are the enforcement point: loading the page-table base register, disabling interrupts, executing halt, writing device registers, changing the mode bit itself. Attempting any of them in user mode raises a trap, and the kernel typically terminates the offending process. This is what makes the protection non-negotiable — a program cannot choose to become privileged; it can only request a service through the controlled system call entry.

Two implications are worth internalising:

Mode is a property of the CPU right now, not of the process. When your process makes a system call, the CPU runs kernel code in your process's context, then returns to user mode. The same thread of execution spans both.
The transition is always through a hardware-defined path. System calls, interrupts, and traps are the only ways in; the return instruction is the only way out. There is no instruction "become privileged".

Some architectures add more rings: hypervisors run at a level below ring 0 (VMX root mode, EL2 on ARM), and secure worlds (TrustZone EL3, SMM) sit below that. Each is a further partition of the same idea, and Chapter 13 returns to it.

Example

   Mode transitions -- the only doors in and out

              +----------------------------------------+
   USER MODE  |  application code                      |
   (ring 3)   |  restricted instruction set            |
              +--+---------+---------+-----------+-----+
                 |         |         |           ^
        syscall  |  trap   | interrupt |         | IRET / SYSRET
        (voluntary) (fault)  (external)          | (the only way back)
                 v         v         v           |
              +--+---------+---------+-----------+-----+
   KERNEL     |  handlers, drivers, subsystems         |
   MODE       |  full instruction set, all memory      |
   (ring 0)   +----------------------------------------+

   Note: the SAME thread crosses the line. Kernel code usually runs
   in the context of whichever process happened to be executing.

#include <stdio.h>

int main(void) {
    /* A privileged instruction attempted from user mode.
       On x86-64, CLI (clear interrupt flag) is ring-0 only. */
    asm volatile ("cli");     /* general protection fault -> SIGSEGV
                                 The kernel is not asking politely; the
                                 hardware refused before any effect occurred. */
    printf("never printed\n");
    return 0;
}

# Observe where time is actually spent on each side of the boundary.
time ./cpu_bound_program
# real 0m2.10s   user 0m2.08s   sys 0m0.01s   <- almost all user mode

time ./io_bound_program
# real 0m3.40s   user 0m0.12s   sys 0m1.90s   <- much of it in kernel mode

Key takeaways

A hardware mode bit distinguishes user mode from kernel mode and gates privileged instructions, memory access, and I/O.
Attempting a privileged instruction in user mode traps; there is no instruction to elevate privilege voluntarily.
Mode belongs to the CPU at an instant: kernel code usually runs inside the calling process's context.
The only entries to kernel mode are system calls, traps, and interrupts; the only exit is the return-from-trap instruction.

🧪 Practice

Compile and run the cli example. Interpret the signal you receive, and identify which component (hardware or kernel) refused first.

Use time on a compute-heavy program and an I/O-heavy one. Explain the user versus sys split in terms of execution mode.

Interview-style: "Without a mode bit, could an OS still enforce protection?" Hint: consider software fault isolation, interpretation, and language-based safety — then ask what each costs and what it must trust.

← Operative Systems