Hardware through the eyes of the OS

Why this matters

Almost every abstraction in this course rests on something concrete in the hardware, and without that support it simply would not exist.

Preemptive multitasking is possible because there is a timer that can interrupt a process. Process isolation is possible because there is an MMU. Virtual memory is possible because the hardware can report a missing mapping. And protection against writing to someone else’s memory is implemented not by a check in kernel code but by a single bit in the page table.

This module covers the minimum of hardware without which the rest of the course turns into memorizing definitions.

Two execution modes

The CPU has privilege levels. On x86 there are formally four of them, rings 0–3, but in practice two are used: kernel mode (ring 0) and user mode (ring 3).

In kernel mode everything is available: reprogram the MMU, disable interrupts, access a device port, halt the CPU. In user mode, an attempt to execute such an instruction raises an exception, and control passes to the kernel.

There are three ways to switch into kernel mode, and all three hand control to kernel code at a predefined address:

1. a system call, when a program deliberately asks for service;
2. an exception, when a program did something the hardware could not carry out;
3. an interrupt, an external event that has nothing to do with the program at all.

There is no instruction that says “switch to ring 0 and keep running my code”, and all of isolation rests on that.

Interrupts and exceptions

Both hand control to the kernel, but for different reasons.

An interrupt arrives asynchronously, from a device. The disk finished reading a block, a packet arrived, the timer fired. It has nothing to do with what the CPU is executing at that moment.

An exception, by contrast, is synchronous: it is caused by the very instruction that is executing right now. Division by zero, access to an invalid address, a privileged instruction in user mode, a page fault.

They are handled the same way. The CPU saves a minimal context, uses the event number to look up an address in the vector table and jumps there, now in kernel mode.

What differs is what happens afterward. After an interrupt, execution continues from the next instruction, while after a page fault the same instruction is executed again, because the mapping now exists.

The timer is the foundation of multitasking

The kernel programs the hardware timer, and after a set interval the timer raises an interrupt. This is the only way at all to give control back to the kernel if a program asks for nothing and is stuck in a loop.

Take away the timer and you are left with cooperative multitasking, where every program has to give up the CPU by itself. That is how Windows 3.x and classic Mac OS worked, which is why one hung program hung the whole system.

MMU

The memory management unit translates logical addresses into physical ones on every memory access. It also checks permissions: an attempt to write to a page marked read-only raises an exception, and the write does not happen.

The kernel needs the MMU for three things at once. For isolation, because a process physically cannot form an address pointing into someone else’s memory. For relocatability, because a process does not know where it actually lives. And for virtual memory, because a mapping may be missing, and the hardware will report it.

The details come in modules 10 and 11; here only one thing matters: this is hardware, and without it memory protection is impossible in principle. Microcontrollers without an MMU run all code in a shared space, which is why they have neither processes nor SIGSEGV.

The memory hierarchy

The right column shows the same series on a human scale. If an L1 access takes one second, a read from a spinning disk takes two months.

Fast memory is expensive, cheap memory is slow, and the compromise is always the same: several levels, each larger and slower than the one before.

This only works thanks to locality. Temporal locality: what was just accessed is likely to be accessed again. Spatial locality: if an address was accessed, the neighboring one will soon be needed. Both are empirical properties of real programs, so caches will not save a program that breaks locality.

That is why a cache works not in bytes but in 64-byte lines. Reading a single byte is physically impossible; the whole line arrives. This has many performance consequences: traversing an array by rows is faster than by columns, and a structure that fits in one line is processed faster than a scattered one.

The same two orders of magnitude that separate RAM from an SSD explain why a process is put into the “blocked” state instead of waiting: in 50 microseconds the CPU could execute hundreds of thousands of instructions.

DMA

If the CPU moved every byte from the disk by hand, copying a gigabyte would keep it fully busy. A direct memory access controller does this on its own: the CPU sets the address and size and then receives a single interrupt on completion.

You will see the consequence in module 13: copying a large file barely loads the CPU.

Many cores

A single CPU core runs one thread. As soon as there are several cores, problems appear that did not exist on one.

Let us start with caches. Each core has its own L1; usually only L3 stays shared. If two cores write to the same cache line, the hardware has to reconcile the copies, and this cache coherence has a cost. That is where false sharing comes from: two completely independent variables happen to land in one line and turn parallel code into sequential code.

Next comes the order of operations. The CPU executes instructions out of order and has write buffers, so writes become visible to other cores not in the order in which they were executed. That is why memory barriers exist (module 9).

And finally NUMA. With several sockets, memory is physically attached to a particular CPU, so an access to “someone else’s” memory goes over the inter-processor link and costs noticeably more. That is why the scheduler tries to keep a process where its memory lives (module 7).

How it actually works in Linux

lscpu | grep -E 'Model name|^CPU\(s\)|Thread|Core|Socket|NUMA|L1d|L2|L3'

Cores, threads per core, sockets, cache sizes and NUMA nodes: the whole topology the scheduler works with.

getconf LEVEL1_DCACHE_LINESIZE

The cache line size. This number determines the granularity at which memory travels between levels, and how many bytes apart two variables must be placed to avoid false sharing.

head -20 /proc/interrupts

How many interrupts from each source each core has handled. The columns are cores; an imbalance here means one core will become a bottleneck.

grep -E 'LOC|RES|CAL|TLB' /proc/interrupts

LOC is the local timer interrupt, the very one that makes preemption possible. Its count grows continuously while the system is running.

numactl --hardware 2>/dev/null || echo 'single NUMA node'

NUMA nodes and the relative cost of access between them. On a single socket the matrix is trivial; on a multi-socket server it is not.

perf stat -e cache-misses,cache-references,instructions,cycles -- \
  sh -c 'i=0; while [ $i -lt 300000 ]; do i=$((i+1)); done'

Cache misses, instructions and cycles. A ratio of instructions to cycles (IPC) below one usually means the CPU spends most of its time waiting for memory.

Common misconceptions

“The kernel constantly supervises program execution.” A process’s code is executed by the CPU itself, with no intermediaries. The kernel gets control only on a system call, an exception or an interrupt, and the rest of the time it does not take part at all.

“An interrupt and an exception are the same thing.” An interrupt comes from outside and asynchronously; an exception is caused by a specific instruction. After an interrupt, execution continues; after a page fault, the instruction is repeated.

“The cache reads bytes.” The cache works in 64-byte lines, and a single byte as a unit of exchange simply does not exist. That is why the order in which you traverse an array can change the speed several times over.

“Memory protection is implemented in the kernel.” It is implemented in hardware. The kernel only fills in the tables; the MMU checks them on every access.

“More cores simply means faster.” Along with speed come cache coherence, reordering of memory operations and NUMA. Naively parallelized code on 32 cores can easily turn out slower than on one.

Check yourself

1. What happens if you remove the hardware timer?

The system keeps working unchangedPreemptive multitasking disappears: the kernel cannot take the CPU away from a program that does not give it upThe MMU stops workingProcesses lose isolation

2. How does an interrupt differ from an exception?

An interrupt is handled fasterAn interrupt is asynchronous and comes from an external device; an exception is caused by the very instruction being executedAn exception is handled in user modeAn interrupt does not change the execution mode

3. How many bytes physically arrive in the cache if a program reads one byte from memory?

1864, a whole cache line4096, a whole page

4. If an L1 cache access took one second, how long would a read from a spinning disk take?

A minuteAn hourAbout two monthsA year

5. Where is the check that a process does not write into someone else's memory implemented?

In kernel code, on every system callIn hardware: the MMU checks permissions on every memory accessIn the compiler, when the program is builtIn the libc library

6. Two cores write to adjacent independent variables, and the parallel code runs slower than the sequential version. Why?

The scheduler did not spread the threads across coresThe variables ended up in one cache line, and the hardware keeps reconciling its copies between coresThere is not enough memoryThe threads compete for a mutex

Lab

B2 — mini-top. Reading /proc/stat and /proc/interrupts: see timer interrupts and how interrupts are spread across cores, and compute CPU load from the difference between counters.

Sources

• Silberschatz, Operating System Concepts, section 1.2
• Tanenbaum, Modern Operating Systems, section 1.3
• What Every Programmer Should Know About Memory — Ulrich Drepper
• Latency Numbers Every Programmer Should Know
• man 1 lscpu, man 8 numactl, man 1 perf-stat