How the Machine Works¶

~12 min

In short¶

A program is a list of instructions. The processor runs them, keeps the data it needs close by in a hierarchy of memory, and asks the operating system for anything outside its own reach, such as a file or a network connection. This page gives you that outline with numbers you can check.

From switches to logic gates¶

A transistor is a switch that a voltage controls. In a MOSFET, the voltage on the gate decides whether current can flow between the source and the drain [1]. Digital circuits treat one voltage range as 1 and another as 0. A modern chip contains a very large number of these switches.

A logic gate is a small circuit built from transistors. The NAND gate is special: any logic gate can be built from NAND gates alone. A Princeton problem set asks you to show this by building NOT, AND, and OR from NAND [2]. The construction looks like this:

NOT(a)     = NAND(a, a)
AND(a, b)  = NOT(NAND(a, b))
OR(a, b)   = NAND(NOT(a), NOT(b))

Gates combine into an arithmetic logic unit (ALU), which adds, subtracts, and compares binary numbers. The Nand2Tetris course builds this whole stack from NAND, up to a working computer [3].

You will sometimes see chip names such as "3 nm". These are marketing labels. Wikipedia notes that the name has no direct relation to gate length, metal pitch, or gate pitch [4]. Do not read a name as a measurement.

The processor loop¶

The textbook model of a CPU is a loop of five steps: fetch the instruction, decode it, execute it in the ALU, access memory if needed, and write the result back to a register [5]. This model explains what one instruction does. Real processors overlap these steps across several instructions at once (pipelining), so the stages are a model, not a strict timeline.

A register is a storage cell inside the CPU core. At 3 GHz, one clock cycle lasts about 0.33 ns. Some x86-64 registers you will meet early:

Register	Role	Source
`RSP`	Stack pointer	[6]
`RIP`	Address of the next instruction	[6]
`RAX`	Return value of a function	[6]
`RDI`, `RSI`, `RDX`	First, second, and third integer arguments	[7]

The system call convention in the next section is almost the same, except that it passes the fourth argument in r10 instead of rcx. The table above is for ordinary function calls.

Memory is layered, and distance costs time¶

Light travels 0.2998 meters in one nanosecond, because the speed of light is exactly 299 792 458 m/s [8]. Signals in hardware cannot beat that limit, so the farther data has to travel, the longer the access takes.

The table below shows approximate latencies from a widely used interactive page that updates Peter Norvig's numbers [9]. Exact values depend on the hardware.

Level	Approximate latency
L1 cache	1 ns
L2 cache	4 ns
Main memory (RAM)	100 ns
SSD, random read	16 microseconds

To feel the gaps, pretend one L1 access takes 1 second. Then main memory takes about 100 seconds, and a random SSD read takes about 4.4 hours. The arithmetic is from the table, not from a measurement.

The cache sizes differ from machine to machine. On the Intel Mac used to check this page, sysctl -n hw.l1dcachesize printed 32768 bytes (32 KB) and hw.l2cachesize printed 262144 bytes (256 KB). Your numbers will differ.

Programs run faster when they reuse data that is already close. Two patterns matter here: temporal locality (a location you used recently is likely to be used again) and spatial locality (a location near one you just used is likely to be used soon) [10]. Reading an array in order is a good example of spatial locality.

Virtual memory¶

Each process sees its own virtual address space. The kernel keeps page tables that map virtual pages to physical memory, and the memory management unit (MMU) in the CPU applies those mappings on every access [11]. The MMU caches recent translations in the translation lookaside buffer (TLB), which is a cache of the page table [12].

On 64-bit Linux with four-level paging, user space spans about 128 TB of virtual addresses [13]. That is a range, not a promise of RAM. Only pages that have been mapped use physical memory.

If a process touches a page that has no valid mapping, the MMU raises a page fault. The kernel then either makes the page available, for example by loading it from disk, or denies the access [14]. This is why a program can use more virtual memory than the RAM installed in the machine, and why it can be slow when pages keep moving between RAM and disk.

Stack and heap¶

A typical Linux process has these regions, from low addresses to high:

high addresses
  +------------------------------+
  | stack   (grows DOWN)         |  local variables, return addresses
  +------------------------------+
  | (unused gap)                 |
  +------------------------------+
  | heap    (grows UP)           |  dynamic memory: malloc, new
  +------------------------------+
  | bss     zeroed globals       |
  | data    initialized globals  |
  | text    machine code         |
  +------------------------------+
low addresses

On x86-64 the stack grows toward lower addresses [7]. The heap grows upward as the program break moves up. brk raises that break to give the process more memory [15].

For large requests, glibc malloc does not grow the heap. Its default M_MMAP_THRESHOLD is 128 KiB, and allocations at or above that size that cannot be met from free memory are served with mmap [16]. So malloc(1024 * 1024) (1 MiB) is handled by mmap, not by growing the heap.

System calls: asking the kernel¶

User code cannot touch the disk or the network directly. To write a file, it calls a system call. On x86-64 Linux, the C library places the system call number in eax, places the arguments in rdi, rsi, rdx, r10, r8, and r9, and then executes the syscall instruction [17]. That instruction runs the kernel's handler at privilege level 0 by loading RIP from the IA32_LSTAR model-specific register [18].

write(2) sends up to count bytes from a buffer to the file that fd refers to. It returns the number of bytes written. That number can be smaller than count, so a careful program checks it [19].

Python exposes this directly. os.write is a low-level call that writes bytes to a file descriptor and returns the number of bytes written [21]. File descriptor 1 is standard output:

$ python3 -c "import os; n = os.write(1, b'hi from os.write\n'); print('bytes written:', n)"
hi from os.write
bytes written: 17

The bytes are written first, then Python prints the return value, 17, which is the length of the byte string.

Try this¶

Run getconf PAGESIZE. On the Intel Mac used to check this page it prints 4096, the common page size on x86-64 Linux. Run it on your own machine and compare.
Read the runnable block below. It builds the three gates from NAND and checks every truth table row, then checks the page arithmetic.

def nand(a, b):
    return 1 - (a & b)

def not_(a):
    return nand(a, a)

def and_(a, b):
    return not_(nand(a, b))

def or_(a, b):
    return nand(not_(a), not_(b))

for a in (0, 1):
    for b in (0, 1):
        assert and_(a, b) == (a & b)
        assert or_(a, b) == (a | b)
    assert not_(a) == 1 - a

PAGE = 4096
assert 0x1234 // PAGE == 1
assert 0x1234 % PAGE == 0x234

If the error messages in this section look unfamiliar, read Reading error messages in the Python course.
Redis is a good real example of a program that cares about these costs. Its documentation describes a mostly single-threaded server that serves many clients with multiplexing [20]. Skim the Redis section when you want to see how this affects design.

Summary¶

Idea	What to remember
Gates	NAND is enough to build every other gate.
Registers	The fastest storage, inside the core.
Memory levels	Each step away from the core costs more time.
Virtual memory	Each process sees its own addresses; the kernel maps them to RAM.
System calls	Files and sockets go through the kernel.

Sources¶

[1] MOSFET, Wikipedia. https://en.wikipedia.org/wiki/MOSFET
[2] Princeton COS 111, problem set 2 (NAND is universal). https://www.cs.princeton.edu/courses/archive/spr05/cos111/probs/2
[3] Nand2Tetris, "From Nand to Tetris". https://www.nand2tetris.org/
[4] 3 nm process, Wikipedia. https://en.wikipedia.org/wiki/3_nm_process
[5] Bryant and O'Hallaron, Computer Systems: A Programmer's Perspective, 3rd ed. https://csapp.cs.cmu.edu/
[6] Stanford CS107, "Guide to x86-64" (register roles). https://web.stanford.edu/class/archive/cs/cs107/cs107.1272/guide/x86-64.html
[7] System V AMD64 calling convention, argument registers (secondary summary). https://c9x.me/articles/gthreads/mach.html
[8] NIST, speed of light in vacuum. https://physics.nist.gov/cgi-bin/cuu/Value?c
[9] Colin Scott, "Interactive latency numbers". https://colin-scott.github.io/personal_website/research/interactive_latency.html
[10] Locality of reference, Wikipedia. https://en.wikipedia.org/wiki/Locality_of_reference
[11] Linux kernel documentation, "Concepts overview" (virtual memory, page tables). https://docs.kernel.org/admin-guide/mm/concepts.html
[12] Translation lookaside buffer, Wikipedia. https://en.wikipedia.org/wiki/Translation_lookaside_buffer
[13] Linux kernel documentation, "x86-64 memory map". https://docs.kernel.org/arch/x86/x86_64/mm.html
[14] Page fault, Wikipedia. https://en.wikipedia.org/wiki/Page_fault
[15] brk(2), Linux man-pages. https://man7.org/linux/man-pages/man2/brk.2.html
[16] mallopt(3), M_MMAP_THRESHOLD, Linux man-pages. https://man7.org/linux/man-pages/man3/mallopt.3.html
[17] syscall(2), Linux man-pages (x86-64 conventions). https://man7.org/linux/man-pages/man2/syscall.2.html
[18] Intel SDM, SYSCALL instruction (mirror). https://www.felixcloutier.com/x86/syscall.html
[19] write(2), Linux man-pages. https://man7.org/linux/man-pages/man2/write.2.html
[20] Redis documentation, "Diagnosing latency issues". https://redis.io/docs/latest/operate/oss_and_stack/management/optimization/latency/
[21] Python 3.12 standard library, os.write and file descriptors. https://docs.python.org/3.12/library/os.html