Computer Organization & Systems

Pull a file off a disk and look at what is physically stored, and you will not find letters, pixels, or sound. You will find a long row of two-state switches. The difference between a love letter and a photograph of a cat is nothing but which switches are on. Learning to read those switches as numbers is the first real skill in computer architecture, and every later topic in this course is built on it.

The big picture

Everything inside a computer, every photo, song, message, and program, is stored as a pattern of bits. This lesson teaches you to read those patterns like a number. Once you can turn a row of ones and zeros into a value in your head, the rest of the machine stops looking like magic. The skill is small but it compounds. The memory addresses, the arithmetic circuits, the cache index calculations, and the instruction encodings you meet in later modules are all the same place-value idea wearing different hats.

What a bit is

A bit (short for binary digit) is the smallest piece of information a computer can hold: a single value that is either 0 or 1. Think of a bit as a light switch that is either off or on. Computers use two values instead of ten because it is easy and reliable to build hardware with two clearly different states, such as a low or high voltage on a wire. A part only has to tell "off" from "on," not ten shades in between, so the circuits stay cheap, fast, and hard to confuse by electrical noise.

Key idea: a bit is one on/off choice, and binary is used because two-state hardware is simple and dependable.

Why two states and not ten

It is worth pushing on that answer, because "binary is simpler" sounds complete and is not. Inside a chip a signal is a voltage on a wire, and voltages are analog: they sag under load, wobble when a neighboring wire switches, and arrive slightly late. A digital circuit survives all of that by refusing to look at the exact voltage. With a 1.0 volt supply, anything below roughly 0.3 volts is declared a 0 and anything above roughly 0.7 volts is declared a 1, and the band between is a no-man's-land a healthy signal crosses in a fraction of a nanosecond. That band is the noise margin, and it is the whole trick: a signal can be corrupted by tenths of a volt and still read back as exactly the value it started as.

Now imagine base 10 on the same wire. You would carve that same swing into ten bands about 0.1 volts wide, and any disturbance over 0.05 volts would flip a digit. Non-binary machines exist - the Soviet Setun ran on balanced ternary in 1958 - but none survived mass manufacturing, because every extra state costs noise margin, switching speed, and yield. Two states is not the elegant choice. It is the robust one.

A second reason is about logic rather than electricity. In the 1930s Claude Shannon noticed that the algebra George Boole had invented for reasoning about true and false described relay switching circuits exactly. Two-valued hardware and two-valued logic are the same mathematics, so a designer can prove a circuit correct with algebra instead of a voltmeter. Module 2 is that observation cashed in.

Positional notation, the idea behind every base

The decimal system you grew up with is a positional system in base 10, where each place is worth ten times the place to its right. The number 3725 means 3 thousands, 7 hundreds, 2 tens, and 5 ones, because the places are powers of ten: 10³, 10², 10¹, 10⁰.

A car odometer is the useful analogy. The rightmost wheel counts ones, and when it rolls past 9 it forces the next wheel to tick up. Binary works the same way, except each wheel counts only 0 and 1, so every place is worth two times the one to its right.

In base 2, the place values from the right are 1, 2, 4, 8, 16, 32, 64, 128, and so on. To read a binary number, add up the place values wherever there is a 1.

Worked example: reading a byte

Consider the 8-bit pattern 10110100. Line each bit up under its place value:

Place value	128	64	32	16	8	4	2	1
Bit	1	0	1	1	0	1	0	0

Now add the place values that sit above a 1: 128 + 32 + 16 + 4. Check the arithmetic step by step: 128 + 32 = 160, then 160 + 16 = 176, then 176 + 4 = 180. So 10110100 represents the decimal number 180.

Key idea: to read binary, sum the place values wherever a 1 appears.

Worked example: writing a value in binary

Reading is half the skill. Go the other way and write 77 in 8 bits by taking the largest place value that still fits at each step. This greedy method is the one you can do in your head.

Target 77   places: 128 64 32 16 8 4 2 1

128 > 77    -> 0, remainder 77
 64 fits    -> 1, remainder 77 - 64 = 13
 32 > 13    -> 0, remainder 13
 16 > 13    -> 0, remainder 13
  8 fits    -> 1, remainder 13 - 8 = 5
  4 fits    -> 1, remainder 5 - 4 = 1
  2 > 1     -> 0, remainder 1
  1 fits    -> 1, remainder 0

Result: 01001101

Check by reading it back: 64 + 8 + 4 + 1 = 77. The remainder hitting exactly zero proves nothing was dropped. Finish with a remainder left over and you skipped a place value.

Powers of two worth knowing cold

Architecture is full of quantities that are exact powers of two, and datasheets go down much easier when you recognize them on sight.

Power	2^4	2^8	2^10	2^16	2^20	2^30	2^32
Value	16	256	1024	65,536	1,048,576	1,073,741,824	4,294,967,296

The handy approximation is that 2^10 = 1024, a bit over one thousand, so every ten powers of two multiply by roughly a thousand: 2^20 is about a million, 2^30 about a billion, 2^40 about a trillion. The approximation drifts 2.4 percent high per step, which is why a drive sold as one terabyte reports as roughly 931 gibibytes.

These are not trivia. A 32-bit address is a 32-bit unsigned number, so it names 2^32 = 4,294,967,296 byte addresses, which is 4 gibibytes. That one fact is why 32-bit machines hit a hard wall at 4 GB and why the industry moved to 64-bit addressing, where 2^64 is about 18.4 quintillion bytes.

Key idea: the width of an address in bits sets the size of the address space, because n bits name exactly 2^n locations.

Bytes and the range they cover

Bits are grouped into bytes of 8 bits each, the standard unit of storage. One byte holds 2⁸ = 256 patterns, from 00000000 to 11111111, which read as an unsigned number run 0 to 255. Notice that is 0 through 255, 256 values counting the zero, a spot where people often miscount.

The leftmost bit is the most significant bit because it carries the largest place value; the rightmost is the least significant bit. In 10000001 the two are worth 128 and 1, so the value is 129.

Size prefixes

Larger amounts of memory use prefixes. In the binary sense used for memory addressing, a kilobyte is 2¹⁰ = 1024 bytes, a megabyte is 1024 kilobytes, and a gigabyte is 1024 megabytes. Disk makers and networks often use the decimal meaning instead, where a kilobyte is exactly 1000 bytes, which is why a "500 GB" drive shows up in the operating system as a little less. Both meanings are correct in their own context; you just have to know which one is in play.

Because the ambiguity caused real confusion, standards bodies added separate names for the powers of 1024: the kibibyte (KiB) is 1024 bytes, the mebibyte (MiB) is 1024 KiB, and the gibibyte (GiB) is 1024 MiB. Adoption has been uneven, so you still read the context, but knowing both vocabularies keeps you out of arguments that are really about naming.

Key idea: a byte is 8 bits and holds 256 patterns, and memory prefixes usually step up in powers of 1024.

Words, and why memory is addressed in bytes

Bits rarely travel alone. Above the byte, hardware works in a chunk called a word, the width the processor prefers for registers and arithmetic. Word size is a property of the machine, not the number: a 64-bit processor has 64-bit registers, adds 64 bits at a time, and generates 64-bit addresses.

Name	Bits	Distinct patterns	Typical use
Nibble	4	16	one hexadecimal digit
Byte	8	256	the unit of addressing
Halfword	16	65,536	short integers, UTF-16 units
Word	32	about 4.3 billion	a typical integer, one RISC-V instruction
Doubleword	64	about 1.8 x 10^19	pointers on modern machines

Now a question that trips people up: if the machine likes 64-bit chunks, why does memory hand out one address per byte? Because text and other small data would waste enormous space otherwise, and touching a single character would demand extra shifting and masking on every access. Byte addressing costs a few extra address bits and buys a far simpler programming model, so nearly every general-purpose machine since the IBM System/360 in 1964 has used it. The cost returns later as alignment rules, since hardware prefers a 4-byte value at an address divisible by 4.

The same bits mean different things

Here is the idea that most changes how you read a memory dump. A bit pattern carries no intrinsic meaning. The byte 01000001 is 65 if an instruction treats it as an unsigned integer, the letter A if a text routine renders it, a fragment of a float if it sits inside one, and an opcode if the program counter points at it. Nothing in the bits says which.

That is not a philosophical aside. It is why the von Neumann model in Module 4 can keep instructions and data in one memory, why a language's type system is a promise rather than a physical property, and why a program that misreads a buffer can be tricked into executing data. Bits are inert; interpretation is everything.

Key idea: a bit pattern has no meaning by itself; the operation that reads it supplies the interpretation.

Where people get stuck

• "Binary is used because it saves space." No. Binary numbers are actually longer to write than decimal. It is used because two-state hardware is reliable, not because it is compact.
• "A byte holds 255 values." It holds 256, because the all-zeros pattern counts too. The largest unsigned value is 255.
• "The leftmost bit is always the biggest number by itself." The leftmost bit carries the largest place value in that group, but its contribution is that place value only if the bit is a 1.
• "A kilobyte is always 1000 bytes." For memory it is 1024; only in disk and network marketing is it 1000. The unambiguous name for 1024 bytes is the kibibyte.
• "A bit pattern has one true meaning." The same eight bits can be an integer, a character, or an instruction. The reading operation decides, not the bits.
• "2^32 is a strangely arbitrary number." It is the count of distinct 32-bit addresses, 4,294,967,296, and it is exactly the 4 GB ceiling that ended the 32-bit era.

Recap

• A bit is a single 0 or 1; binary is used because two-state hardware keeps a wide noise margin and matches Boolean logic exactly.
• Positional notation gives each place a value; in base 2 the places are powers of two: 1, 2, 4, 8, 16, and so on.
• To read a binary number, add the place values where a 1 appears; to write one, subtract the largest place value that fits until the remainder is zero.
• A byte is 8 bits, holds 256 patterns, and covers 0 to 255 as an unsigned number.
• An n-bit address names 2^n locations, so 32 bits reaches 4 GiB and 64 bits reaches far more than any real machine.
• The most significant bit is on the left; memory prefixes step up by 1024, with KiB, MiB, and GiB as the unambiguous names.
• Bits are inert. Meaning comes from the operation that reads them.

Everything after this lesson is elaboration on one habit: when you see a row of bits, ask what place values are in play and who is doing the interpreting. Get those two questions right and the machine becomes readable.

Sources

1. Patterson, D. A., & Hennessy, J. L. (2020). Instructions: Language of the computer. In Computer organization and design RISC-V edition: The hardware software interface (2nd ed., ch. 2). Morgan Kaufmann. find source ↗
2. Harris, S. L., & Harris, D. M. (2021). From zero to one. In Digital design and computer architecture: RISC-V edition (ch. 1). Morgan Kaufmann. find source ↗
3. Terman, C., & Ward, S. (2017). 6.004 Computation structures (Chapter 1: Basics of information). MIT OpenCourseWare. ocw.mit.edu
4. National Institute of Standards and Technology. (n.d.). Definitions of the SI units: The binary prefixes. NIST Physical Measurement Laboratory. physics.nist.gov
5. Shannon, C. E. (1940). A symbolic analysis of relay and switching circuits [Master's thesis, Massachusetts Institute of Technology]. DSpace@MIT. dspace.mit.edu
6. Nisan, N., & Schocken, S. (n.d.). Boolean logic (Project 1). Nand to Tetris. nand2tetris.org
7. Computer History Museum. (n.d.). Digital logic. CHM Revolution exhibit. computerhistory.org

Open a debugger, a network packet dump, a colour picker, or a crash report and you will be reading hexadecimal within seconds. Nobody warns you about this in advance. The good news is that base conversion is a small set of mechanical procedures that never fail, and once they are in your fingers you stop treating 0x7FFF as a foreign language and start reading it as a number with a size you can estimate.

The big picture

Programmers constantly switch between three ways of writing the same number: decimal for everyday reading, binary for what the hardware actually holds, and hexadecimal as a compact shorthand for binary. This lesson gives you reliable, repeatable methods to convert among all three so you never have to guess. The emphasis is on procedures with a built-in check, because a conversion you cannot verify is a conversion you cannot trust.

The three bases at a glance

Decimal is base 10 (digits 0 to 9). Binary is base 2 (digits 0 and 1). Hexadecimal, or hex, is base 16 (digits 0 to 9 then A, B, C, D, E, F for the values 10 through 15). Hex exists mainly as a friendlier costume for binary: because 16 is 2⁴, one hex digit stands in for exactly four bits, so long binary strings become short and readable.

Decimal	Binary (4-bit)	Hex
0	0000	0
5	0101	5
10	1010	A
15	1111	F

Key idea: hex is base 16, and one hex digit maps to exactly four bits because 16 equals 2 to the 4th power.

The nibble table, which is the only table you need

Every binary-to-hex conversion in your career is sixteen lookups repeated. Learn this table and the rest is bookkeeping.

0000 = 0    0100 = 4    1000 = 8    1100 = C (12)
0001 = 1    0101 = 5    1001 = 9    1101 = D (13)
0010 = 2    0110 = 6    1010 = A (10)  1110 = E (14)
0011 = 3    0111 = 7    1011 = B (11)  1111 = F (15)

Two shortcuts help while you are still learning it. A nibble beginning with 1 is worth 8 or more, so it lands in the 8-to-F half; and the letters run A, B, C, D, E, F for 10, 11, 12, 13, 14, 15, which you can recover by counting on your fingers from A = 10 whenever you blank.

Why hex, and how the prefixes work

Hex is not the only compact option. Early machines with word sizes divisible by three, such as the 36-bit PDP-10, favoured octal (base 8), where one digit covers three bits. When the byte settled at 8 bits, octal stopped dividing evenly into a word and hex took over, because two hex digits describe exactly one byte and eight describe exactly one 32-bit word. You still meet octal in one place: Unix file permissions, where chmod 755 is three octal digits, each holding the read, write, and execute bits for one group of users.

Because the same digits can be read in several bases, a written number needs a marker. The near-universal conventions are 0x for hex, 0b for binary, and 0o (or a bare leading zero in older C) for octal. So 0x10 is sixteen, 0b10 is two, 0o10 is eight, and plain 10 is ten - four different values, one written form. Assembly listings sometimes use a trailing h instead, as in 1Ah. Always find the marker before you read the value.

Binary to decimal: add the place values

You already know this from the last lesson. Write the place values (1, 2, 4, 8, 16, ...) under the bits and add wherever there is a 1. For 11010: the 1 bits are in the 16, 8, and 2 places, so 16 + 8 + 2 = 26.

Decimal to binary: repeated division by 2

To convert a decimal number to binary, divide by 2 over and over, writing down each remainder. The remainders, read from the bottom up, are the binary digits. It is like making change: you keep splitting the amount in half and note whether anything is left over. Convert 45:

Division	Quotient	Remainder
45 / 2	22	1
22 / 2	11	0
11 / 2	5	1
5 / 2	2	1
2 / 2	1	0
1 / 2	0	1

Reading the remainders bottom to top gives 101101. Check it by converting back: 32 + 8 + 4 + 1 = 45. It matches, so the answer is correct.

Why bottom up? Because each division peels off the least significant bit first. Dividing by 2 is a right shift, and the remainder is whatever fell off the right end. The first remainder you write is therefore the ones place, the second is the twos place, and so on. Reading the column downward would give you the number backwards, which is the single most common error in this procedure.

The same machinery works for any base: divide repeatedly by the base and read the remainders bottom up. Converting 429 to hex, divide by 16 instead of 2. 429 / 16 = 26 remainder 13 (D); 26 / 16 = 1 remainder 10 (A); 1 / 16 = 0 remainder 1. Bottom up, that is 1AD, which we will confirm from the other direction later in the lesson.

Key idea: divide by 2 repeatedly and read the remainders bottom up to get binary; always check by converting back.

Binary to hex: group into nibbles of four

A group of four bits is called a nibble (half a byte). To convert binary to hex, split the bits into groups of four starting from the right, pad the leftmost group with leading zeros if needed, then translate each nibble using the table above. Convert 110101101:

1. Group from the right: 1 1010 1101.
2. Pad the left group to four bits: 0001 1010 1101.
3. Translate each nibble: 0001 = 1, 1010 = A, 1101 = D.

So 110101101 in binary is 1AD in hex. To go from hex back to binary, just expand each digit into its four bits.

Hex to decimal: multiply by powers of 16

Each hex place is worth 16 times the one to its right: the places are 1, 16, 256, and so on. For 1AD: the digits are 1, A (=10), and D (=13). Multiply and add: (1 x 256) + (10 x 16) + (13 x 1) = 256 + 160 + 13 = 429. As a sanity check, the binary 110101101 also sums to 256 + 128 + 32 + 8 + 4 + 1 = 429, so all three forms agree.

Key idea: convert binary and hex through their groups of four bits, and confirm any conversion by translating it back.

Worked example: a full round trip

Take the byte 0xB7 and push it through every representation, checking at each step.

0xB7  ->  B = 1011, 7 = 0111  ->  10110111        (hex to binary)
10110111  ->  128 + 32 + 16 + 4 + 2 + 1 = 183       (binary to decimal)
183 / 16 = 11 remainder 7                            (decimal back to hex)
 11 / 16 =  0 remainder 11 = B
read bottom up ->  B7                                 matches, so 0xB7 = 183

Notice the shortcut hiding in the second line: two hex digits always come out as (first digit x 16) + second digit. Here that is (11 x 16) + 7 = 176 + 7 = 183, no binary needed. Because a byte is exactly two hex digits, this is the fastest way to read any byte value, and it is worth practising until it is automatic.

Hex arithmetic and address math

You will rarely multiply in hex, but you will constantly add small offsets to addresses, and doing it directly beats converting to decimal and back. The rule is ordinary column addition, except that you carry when a column reaches 16 rather than 10.

  0x2F4C
+ 0x00B8
---------
  C + 8 = 20 decimal = 16 + 4  -> write 4, carry 1
  4 + B + 1 = 4 + 11 + 1 = 16  -> write 0, carry 1
  F + 0 + 1 = 16               -> write 0, carry 1
  2 + 0 + 1 = 3                -> write 3
  0x3004

Two facts make address arithmetic easier than it looks. Adding 0x10 moves 16 bytes; adding 0x100 moves 256 bytes; adding 0x1000 moves 4096 bytes, which is exactly one page in Module 6. And because each hex digit is four bits, dropping the last digit of an address divides it by 16, while dropping the last three digits divides it by 4096. Page and cache calculations later in the course lean on precisely these shifts.

Where hex actually turns up

Hex is not an academic exercise. Memory addresses in a debugger print as hex because the digit boundaries line up with the bit fields the hardware uses. Web colours such as #FF8800 are three bytes, one each for red, green, and blue. A MAC address is six bytes written as twelve hex digits. Unicode code points are written as U+1F600. And when a crash dump shows 0xDEADBEEF or 0xCAFEBABE, you are looking at a deliberately recognizable filler value that a programmer chose because it spells something in hex digits.

A preview: bits after the point

Place values do not stop at the ones column. Just as decimal continues 0.1, 0.01, 0.001 to the right of the point, binary continues 1/2, 1/4, 1/8. So 101.101 in binary is 4 + 1 + 0.5 + 0.125 = 5.625. That single observation is the seed of floating point in the next lesson, and it also explains a problem waiting there: 1/10 is a clean decimal but never terminates in binary, because 10 has a prime factor of 5 that no power of 2 can supply.

Key idea: binary place values continue to the right of the point as halves, quarters, and eighths, so any fraction whose denominator is not a power of two cannot be written exactly.

Where people get stuck

• "You read the division remainders top to bottom." No, read them bottom to top. Reading them the wrong way reverses the number.
• "Group bits from the left when making hex." Group from the right, so the least significant bits stay together. Only the leftmost group may need padding.
• "Hex A is a letter, not a number." In hex, A through F are digits with the values 10 through 15; they are numbers written with letters.
• "Hex is a different amount of information than binary." Hex is just a shorter way to write the same bits; the underlying value is identical.
• "10 always means ten." In any base, the string 10 means one times that base. It is 2 in binary, 8 in octal, 16 in hex. Read the prefix first.
• "Padding with leading zeros changes the value." It does not. 0x0B7 and 0xB7 are the same number; the padding only fixes how many bits you are drawing.

Recap

• Decimal is base 10, binary is base 2, hex is base 16; prefixes 0b, 0o, and 0x say which is meant.
• Binary to decimal: add place values over each 1.
• Decimal to binary: divide by 2 repeatedly, read remainders bottom up, because each division peels off the least significant bit.
• The same repeated-division method converts to any base, including straight to hex by dividing by 16.
• Binary to hex: group into nibbles of four from the right and translate each.
• Hex to decimal: multiply each digit by its power of 16 and add; for a single byte that is just (first digit x 16) + second digit.
• Hex addition carries at 16, and adding 0x1000 steps one 4096-byte page.
• Always verify a conversion by converting back the other way.

Practise until conversion stops feeling like arithmetic and starts feeling like reading. Every later module - instruction encodings, cache index bits, page offsets - assumes you can move between these three notations without stopping to think.

Sources

1. Patterson, D. A., & Hennessy, J. L. (2020). Instructions: Language of the computer. In Computer organization and design RISC-V edition: The hardware software interface (2nd ed., ch. 2). Morgan Kaufmann. find source ↗
2. Harris, S. L., & Harris, D. M. (2021). From zero to one. In Digital design and computer architecture: RISC-V edition (ch. 1). Morgan Kaufmann. find source ↗
3. Terman, C., & Ward, S. (2017). 6.004 Computation structures (Chapter 1: Basics of information). MIT OpenCourseWare. ocw.mit.edu
4. University of California, Berkeley. (n.d.). CS 61C: Great ideas in computer architecture (machine structures). EECS Instructional Support. inst.eecs.berkeley.edu
5. RISC-V International. (n.d.). Ratified specifications (see the unprivileged ISA instruction encodings). riscv.org
6. Computer History Museum. (n.d.). The first mainframes: IBM System/360. CHM Revolution exhibit. computerhistory.org
7. Nisan, N., & Schocken, S. (n.d.). Boolean arithmetic (Project 2). Nand to Tetris. nand2tetris.org

On 4 June 1996 the first Ariane 5 rocket destroyed itself 37 seconds after launch. The cause was a 64-bit floating-point value for horizontal velocity being converted into a 16-bit signed integer that could not hold it. The overflow raised an exception, the guidance computer shut down, the backup ran identical code and shut down too, and roughly 370 million dollars became a fireball. Signed integer representation is not a formality. It is a contract about which values exist, and violating it silently is what makes it dangerous.

The big picture

Bits alone have no sign, so we need a rule for storing negative numbers. Almost every computer uses one clever scheme called two's complement. This lesson shows what it is, why it makes subtraction free for the hardware, and how to read and write negative values by hand. It also shows what happens at the edges, because the edges are where the bugs live.

The problem: where does the minus sign go?

An 8-bit pattern like 10000001 could mean 129 if we treat all bits as positive (unsigned), or it could mean a negative number if we agree to reserve part of the pattern for a sign. A signed number is one that can be negative or positive. The challenge is picking a rule that lets ordinary addition circuits handle negatives without extra machinery.

Two schemes that lost, and why

The obvious first idea is sign-magnitude: use the top bit as a plus-or-minus flag and read the rest as an ordinary magnitude, so 00000101 is +5 and 10000101 is -5. It is easy for a human to read and it fails immediately in hardware. Adding +5 and -5 with a plain adder gives 10001010, which reads as -10 rather than 0. The adder would have to inspect sign bits, compare magnitudes, decide whether this is really a subtraction, and possibly swap the operands - a pile of extra logic in the most performance-critical circuit on the chip. Worse, there are two zeros, since 00000000 and 10000000 both mean zero.

The second idea is one's complement: negate by flipping every bit, so -5 is 11111010. Addition almost works, but any carry out of the top must be added back into the bottom, an extra step called end-around carry, and the duplicate zero survives. Real machines used both schemes - the CDC 6600 was a one's complement machine - and both were abandoned for the same reasons.

Key idea: the winning representation is the one that lets a plain binary adder produce the right answer with no inspection of signs and no duplicate zero.

Two's complement: the winning rule

In two's complement, the most significant bit is the sign bit, but with a twist: instead of just flagging the sign, it carries a negative place value. For an 8-bit number the leftmost place is worth -128 instead of +128; all the other places stay positive. To read a two's complement number, add the place values as usual but treat the top bit as negative.

Read 11111111 in 8-bit two's complement: -128 + 64 + 32 + 16 + 8 + 4 + 2 + 1. The positive part sums to 127, so the total is -128 + 127 = -1. That is the elegance of the scheme: all ones means negative one.

Key idea: in two's complement the top bit carries a negative place value, so a leading 1 always means the number is negative.

Negating a number: flip the bits and add one

To find the representation of a negative number, take the positive version, flip every bit (change 0 to 1 and 1 to 0), then add 1. Think of it as "mirror, then nudge." Find -5 in 8 bits:

1. Start with +5: 00000101.
2. Flip every bit: 11111010.
3. Add 1: 11111011.

Check by reading it back: -128 + 64 + 32 + 16 + 8 + 2 + 1 = -128 + 123 = -5. Correct. The same flip-and-add-one trick also turns a negative back into its positive, so the operation is its own inverse. Verify that too: flip 11111011 to get 00000100, add 1, and you are back at 00000101 = +5.

Here is a small table you can use to sanity-check yourself, and it also exposes the structure of the encoding.

Value	+127	+1	0	-1	-2	-127	-128
8-bit pattern	01111111	00000001	00000000	11111111	11111110	10000001	10000000
Hex	0x7F	0x01	0x00	0xFF	0xFE	0x81	0x80

Notice that counting down from 0 wraps to all ones and keeps going, which is exactly counting down from 256 in unsigned terms. That is the deepest way to see two's complement, and it deserves its own name.

The clean way to think about it: arithmetic modulo 2^n

An 8-bit register holds only 256 distinct values, so everything it computes is arithmetic modulo 256. Two's complement is just the decision to cut the number line in the middle rather than at the end. The patterns are identical either way; unsigned reads them as 0 to 255, and signed reads the upper half as -128 to -1 by subtracting 256.

pattern   11111011
unsigned  251
signed    251 - 256 = -5      the whole rule, in one subtraction

This also explains why "invert and add one" works, without any hand-waving. Inverting every bit of x gives 255 - x, because the all-ones pattern is 255 and flipping is subtraction from it. Add 1 and you have 256 - x, which is congruent to -x modulo 256. The trick is not a trick; it is the definition, computed with hardware that only knows how to invert and add.

Key idea: a fixed-width register does arithmetic modulo 2^n, and two's complement simply reinterprets the top half of that range as negative.

Why hardware loves it: subtraction becomes addition

The whole point is that A - B can be computed as A + (-B) using the very same adder that does addition. There is no separate subtraction circuit and no special case for the sign. For example, 5 - 5 is 5 + (-5): 00000101 + 11111011 = 1 00000000. The carry out of the top falls off the 8-bit register and we are left with 00000000, which is 0, exactly right.

Key idea: two's complement lets one adder do both addition and subtraction, because subtracting is just adding the negative.

Range and overflow

An n-bit two's complement number ranges from -2^n-1 up to 2^n-1 - 1. For 8 bits that is -128 to +127. Notice the range is lopsided: there is one more negative value than positive, because zero uses up a slot on the positive side. Overflow happens when a result does not fit this range, for instance adding 127 + 1 gives 10000000, which reads as -128 rather than 128. The number silently wraps around, which is a classic source of bugs.

How hardware detects overflow

The processor cannot check whether the answer "looks wrong". It uses a rule costing one XOR gate: signed overflow has occurred when the carry into the sign bit differs from the carry out of it. An easier statement for hand work is that adding two numbers of the same sign and getting the opposite sign is always overflow, while opposite signs can never overflow. Work three cases in 8 bits.

Case 1: 100 + 50   (both positive, result should be 150)
  01100100 + 00110010 = 10010110
  carry into sign bit = 1, carry out = 0   -> differ -> OVERFLOW
  the register reads 10010110 = -106, not 150

Case 2: -100 + -50  (both negative, result should be -150)
  10011100 + 11001110 = 1 01101010, keep 8 bits -> 01101010
  carry into sign bit = 0, carry out = 1   -> differ -> OVERFLOW
  the register reads 01101010 = +106, not -150

Case 3: 100 + (-50)  (opposite signs, result should be 50)
  01100100 + 11001110 = 1 00110010, keep 8 bits -> 00110010 = 50
  carry into sign bit = 1, carry out = 1   -> same -> no overflow, answer correct

Case 3 makes a point that confuses nearly everyone: the carry out of the top bit was 1, and the answer is still perfectly correct. A carry out is not signed overflow. Carry is the unsigned indicator; the XOR of the two carries is the signed one. Processors keep both as separate flags because the same addition can overflow under one interpretation and not the other, and only the program knows which it meant.

Key idea: carry out means unsigned overflow, and disagreement between the carry into and out of the sign bit means signed overflow. They are different flags for different questions.

Widening a value: sign extension

Copy an 8-bit -5 into a 32-bit register and you cannot simply pad with zeros: 00000000 00000000 00000000 11111011 is 251, not -5. The correct move is sign extension, replicating the sign bit into every new position to give 11111111 11111111 11111111 11111011, which reads as -5. Padding with zeros is zero extension, which is what an unsigned value needs. Instruction sets provide both, which is why RISC-V has lb (load byte, sign-extended) alongside lbu (load byte unsigned). This is a live source of bugs in C, where a plain char may be signed: read a byte of 0xFF into a char, compare it to 255, and the comparison fails because the char sign-extends to -1.

The one value with no positive twin

The lopsided range has a sharp edge. In 8 bits there is no +128, so negating -128 is impossible. Try it: flip 10000000 to get 01111111, add 1, and you land back on 10000000. The absolute value of the most negative number is itself, and it is negative. The same holds at every width, so in 32 bits -(-2147483648) evaluates to -2147483648. Sorting routines and absolute-value helpers have been broken by exactly this. In C and C++ signed overflow is undefined behaviour, so the compiler may assume it never happens, which turns wrong arithmetic into unpredictable program behaviour.

Wraparound is not only a textbook worry. A 32-bit signed counter overflows after 2,147,483,647 events, and the Unix time_t counting seconds since 1970 in a signed 32-bit field overflows on 19 January 2038. Same arithmetic, different width.

Key idea: the most negative value has no positive counterpart, so negation and absolute value have one input they cannot handle correctly.

Where people get stuck

• "The sign bit is just a plus or minus flag." In two's complement it is a real place value worth -2 to the (n-1), not a separate flag you tack on.
• "To negate, you only flip the bits." Flipping alone is one's complement. Two's complement also adds 1, which is why it has a single representation of zero.
• "The positive and negative ranges are equal." There is one extra negative value because zero occupies a positive-side slot; 8-bit runs -128 to +127.
• "Overflow throws an error." Fixed-width arithmetic wraps around silently; the hardware sets a flag but the value just rolls over. In C, signed overflow is undefined behaviour, so the compiler may assume it cannot happen.
• "A carry out of the top bit means the answer is wrong." Case 3 above had a carry out and a correct answer. Carry is the unsigned indicator; signed overflow is the disagreement between the two carries around the sign bit.
• "Widening a negative number just adds zeros on the left." That is zero extension and it turns -5 into 251. Signed values must be sign-extended by copying the sign bit.
• "Absolute value always returns a positive number." Not for the most negative value, whose absolute value is itself.

Recap

• Unsigned bits are all positive; signed numbers can be negative.
• Sign-magnitude and one's complement both waste a pattern on a second zero and complicate the adder, which is why they lost.
• In two's complement the top bit carries a negative place value, so a leading 1 means negative.
• Negate by flipping all bits and adding 1; the trick is its own inverse, and it is really the computation of 2^n - x.
• A fixed-width register does arithmetic modulo 2^n; signed reading just relabels the top half as negative.
• Subtraction reuses the adder because A - B equals A + (-B).
• Signed overflow is detected by comparing the carry into and out of the sign bit; unsigned overflow is the carry out alone.
• Widening needs sign extension for signed values and zero extension for unsigned ones.
• An n-bit range is -2^(n-1) to 2^(n-1)-1; results outside it overflow and wrap, and the most negative value cannot be negated.

Two's complement rewards a habit: whenever you write code that mixes widths, mixes signedness, or negates a value that came from outside your program, stop and ask what happens at the extremes of the range. That one question would have prevented most of the famous failures in this lesson.

Sources

1. Patterson, D. A., & Hennessy, J. L. (2020). Signed and unsigned numbers. In Computer organization and design RISC-V edition: The hardware software interface (2nd ed., ch. 2). Morgan Kaufmann. find source ↗
2. Bryant, R. E., & O'Hallaron, D. R. (2016). Representing and manipulating information. In Computer systems: A programmer's perspective (3rd ed., ch. 2). Pearson. find source ↗
3. Harris, S. L., & Harris, D. M. (2021). Number systems. In Digital design and computer architecture: RISC-V edition (ch. 1). Morgan Kaufmann. find source ↗
4. Terman, C., & Ward, S. (2017). 6.004 Computation structures (Chapter 1: Basics of information). MIT OpenCourseWare. ocw.mit.edu
5. European Space Agency. (1996). Ariane 501: Presentation of Inquiry Board report. ESA Newsroom. esa.int
6. MITRE Corporation. (n.d.). CWE-190: Integer overflow or wraparound. Common Weakness Enumeration. cwe.mitre.org
7. Lattner, C. (2011). What every C programmer should know about undefined behavior. The LLVM Project Blog. blog.llvm.org

Type 0.1 + 0.2 into almost any programming language and you get 0.30000000000000004. This is not a bug in the language, the processor, or your machine. It is the honest consequence of storing an infinite decimal in a finite number of bits, and by the end of this lesson you will be able to derive that trailing 4 from first principles. The same lesson explains why a text file from one system shows up as mojibake on another.

The big picture

Numbers are not the only thing computers store. Letters, emoji, and fractional values like 3.14 all have to become bits too. This lesson explains the codes that turn text into numbers and the floating-point format that squeezes real numbers into a fixed number of bits. Both are agreements rather than laws of nature, and knowing exactly what each one promises is what keeps you out of trouble.

Text: characters are just numbers in disguise

A character encoding is an agreed table that assigns a number to each symbol. The oldest common one is ASCII, which uses 7 bits to cover 128 symbols: the English letters, digits, punctuation, and some control codes. For example the capital letter A is 65, and the digit character "0" is 48. Because the letters are numbered in order, you can find any capital letter by counting up from A: the letter C is 65 + 2 = 67.

A subtle but important point: the character "5" (code 53) is not the number 5. One is a symbol you print, the other is a value you compute with. Converting between them is a deliberate step, not automatic.

Key idea: an encoding is a lookup table mapping symbols to numbers, and the digit character "5" is not the same as the numeric value 5.

ASCII is not an arbitrary table

The 1963 committee that laid out ASCII chose the numbers so that useful operations become simple arithmetic, and those choices still shape code you write today.

• Codes 0 to 31 are control codes rather than printable symbols: newline is 10, carriage return is 13, tab is 9. Code 32 is the space, the first printable character.
• The digits sit at 48 to 57 (0x30 to 0x39) in order, so converting a digit character to its value is a subtraction: '7' - '0' is 55 - 48 = 7. Every parser you have ever used starts here.
• Uppercase runs 65 to 90 (0x41) and lowercase 97 to 122 (0x61), exactly 32 apart. In binary that is a single bit: A is 1000001 and a is 1100001. Changing case is therefore one bitwise operation, which is precisely why old code toggles case with an OR or AND against 32.

The bit trick is elegant and it is also a trap, because it works only for unaccented English letters. Case conversion in Turkish, Greek, or German needs real tables, and the fact that one language's rules leak into another's data is the oldest source of text bugs there is.

Beyond English: Unicode and UTF-8

ASCII cannot represent the world's scripts, so Unicode gives a number, called a code point, to well over a hundred thousand characters from every writing system plus emoji. UTF-8 is the most common way to store those code points as bytes. It is clever: the original ASCII characters still take a single byte, while other characters use two, three, or four bytes as needed. This means old ASCII text is already valid UTF-8, which is why UTF-8 took over the web.

Worked example: encoding a character in UTF-8

The scheme is a set of templates. A byte starting with 0 is a lone ASCII byte. A byte starting with 110 begins a two-byte sequence, 1110 a three-byte sequence, and 11110 a four-byte sequence. Every continuation byte starts with 10. The code point's bits are then poured into the x slots.

1 byte : 0xxxxxxx                            up to U+007F
2 bytes: 110xxxxx 10xxxxxx                   up to U+07FF
3 bytes: 1110xxxx 10xxxxxx 10xxxxxx          up to U+FFFF
4 bytes: 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx up to U+10FFFF

Encode the euro sign, U+20AC:
  0x20AC in binary is        0010 0000 1010 1100    (16 bits)
  split 16 bits as 4/6/6:    0010  000010  101100
  fill the 3-byte template:  11100010 10000010 10101100
  in hex:                    E2 82 AC

The leading bits are not decoration. Because a continuation byte always starts with 10 and a starting byte never does, a program that lands in the middle of a string can walk backwards to the nearest byte that is not a continuation and know it has found a character boundary. That property is called self-synchronization, and it is why a corrupted byte damages one character rather than every character after it. It is also why UTF-8 beat the alternatives.

Key idea: UTF-8 packs a code point into templated bytes whose high bits announce their role, which keeps ASCII intact and makes the stream self-synchronizing.

Real numbers: fixed point versus floating point

To store a value like 5.75 we could imagine a binary point in a fixed spot, giving fixed point. But fixed point wastes bits when numbers vary wildly in size. Instead computers use floating point, which is binary scientific notation. Just as decimal scientific notation writes 6.022 x 10²³, floating point writes a number as a sign, a mantissa (the significant digits), and an exponent (how far to shift the binary point). The point "floats" to wherever the exponent puts it, which is where the name comes from.

The IEEE 754 single-precision layout

The standard 32-bit float, defined by IEEE 754, splits its bits like this:

Field	Bits	Role
Sign	1	0 for positive, 1 for negative
Exponent	8	Scales the value, stored with a bias of 127
Mantissa	23	The significant bits after an assumed leading 1

The exponent is stored biased, meaning you subtract 127 from the stored value to get the true exponent. This lets one unsigned field represent both large and tiny scales. The value works out to sign x 1.mantissa x 2^{(exponent - 127)}.

Key idea: floating point stores a sign, mantissa, and biased exponent, so the same 32 bits can hold both huge and minuscule numbers.

Worked example: building a float bit by bit

Encode -6.25 as a 32-bit float. Work in four steps and nothing is mysterious.

1. Convert to binary:      6.25 = 110.01
2. Normalize to 1.xxx:     110.01 = 1.1001 x 2^2      so true exponent = 2
3. Bias the exponent:      2 + 127 = 129 = 10000001
4. Take the bits after the point as the mantissa,
   padded to 23 bits:      10010000000000000000000
   sign is negative:       1

   1 10000001 10010000000000000000000
   = 1100 0000 1100 1000 0000 0000 0000 0000
   = 0xC0C80000

Now run it backwards to check your understanding. Decode 0x41C80000: the bits are 0 10000011 10010000000000000000000. The sign is 0, so positive. The stored exponent is 10000011 = 131, and 131 - 127 = 4. The mantissa gives a significand of 1.1001. So the value is 1.1001 x 2^4 = 11001.0 in binary = 25.0.

Notice what step 2 bought us. Every normalized number starts with a 1 before the point, so there is no reason to store that bit. It is assumed, which is why it is called the implicit leading one, and it gives 24 bits of precision from 23 bits of storage - a free bit, and the reason step 4 says "the bits after the point".

The special exponents

Two exponent patterns are reserved, which is where the odd values in floating point come from.

Stored exponent	Mantissa	Meaning
all zeros	zero	zero (and negative zero, if the sign bit is 1)
all zeros	non-zero	subnormal: no implicit 1, fills the gap around zero
all ones	zero	infinity, positive or negative
all ones	non-zero	NaN, "not a number"

These are not error states to be avoided; they are values the arithmetic produces and propagates, so a long computation can keep running and report a problem at the end rather than trapping in the middle. NaN has one famous property worth memorizing: it compares unequal to everything, including itself. If x != x is true, x is NaN.

How much precision, exactly

A 32-bit float has 24 bits of significand, and 2^24 = 16,777,216. Above that, consecutive whole numbers can no longer all be represented: 16,777,217 rounds to 16,777,216. Converting 24 bits to decimal digits gives 24 x log10(2), about 7.2, so a float carries roughly seven reliable decimal digits and no more. A 64-bit double has 53 bits of significand, about 15.9 decimal digits, which is why doubles are the default in most languages.

The structural point is that the gaps are not uniform. Because the exponent scales everything, the spacing between neighbouring floats doubles each time the exponent increases by one: near 1.0 the gap is about 1.2 x 10^-7, near 10 million it is about 1. That is usually what you want, since measurements carry relative rather than absolute error, but it means adding a small number to a large one can change nothing at all.

Key idea: floating point has constant relative precision, so the absolute spacing between representable values grows with magnitude.

The catch: floats are approximations

Only a finite set of values fits in 32 bits, so most real numbers are rounded to the nearest representable one. This is why 0.1 + 0.2 does not come out to exactly 0.3 in most languages: 0.1 has no exact binary form, just as 1/3 has no exact decimal form. Floats are fast and cover an enormous range, but you should never compare them for exact equality; compare whether they are close enough instead.

Derive it rather than taking it on faith. Multiply 0.1 by 2 repeatedly and record each whole part: 0.2 -> 0, 0.4 -> 0, 0.8 -> 0, 1.6 -> 1, 1.2 -> 1, 0.4 -> 0, and 0.4 has now recurred, so the pattern 0011 repeats forever. In binary, 0.1 is 0.0001100110011... A fraction terminates in base 2 only when its denominator is a power of 2, and 10 = 2 x 5 carries a factor of 5 that no power of two can cancel. So the stored double sits very slightly above one tenth, 0.2 carries its own small error, and their sum lands on the representable value that prints as 0.30000000000000004.

The practical rule follows. Compare with a tolerance, preferably relative: treat a and b as equal when abs(a - b) <= tol * max(abs(a), abs(b)), falling back to a small absolute tolerance near zero. And for money, do not use binary floating point at all - store integer cents or use a decimal type, because currency rounding rules are defined in base 10.

Where people get stuck

• "The character 7 and the number 7 are the same bits." No. The character "7" is ASCII code 55; the numeric value 7 is the binary 00000111.
• "UTF-8 makes every character one byte." Only the ASCII range is one byte; other characters take two to four bytes.
• "Floating point stores exact values." It stores the nearest representable approximation, so tiny rounding errors are normal.
• "A bigger exponent field means more precision." The exponent sets the range; the mantissa sets the precision. They are separate.
• "Floating-point error is random noise." It is deterministic rounding. The same inputs always give the same result, which is why the 0.1 + 0.2 answer is always the same digits.
• "Using doubles fixes the problem." Doubles push the error out to the sixteenth digit; they do not make 0.1 exact. Only a decimal or rational representation does that.
• "NaN equals NaN." It does not, and that is the standard's defined behaviour, not a quirk of your language.

Recap

• Character encodings map symbols to numbers; ASCII covers 128 symbols in 7 bits, with digits at 48 and a single bit separating upper from lower case.
• Unicode assigns code points to all scripts, and UTF-8 stores them in one to four templated, self-synchronizing bytes.
• Floating point is binary scientific notation: sign, mantissa, and exponent.
• IEEE 754 single precision uses 1 sign bit, 8 biased exponent bits, and 23 mantissa bits, plus an implicit leading 1 that gives 24 bits of precision.
• Encode by normalizing to 1.xxx, biasing the exponent by 127, and storing the bits after the point.
• All-zero and all-one exponents are reserved for zero, subnormals, infinity, and NaN.
• Precision is about 7 decimal digits for a float and 16 for a double, and the gaps between values grow with magnitude.
• Floats are approximations, so compare for closeness, not exact equality, and never store money in binary floating point.

Both halves of this lesson teach the same discipline. A byte sequence is text only relative to a declared encoding, and a float is a number only to within a stated tolerance. Say which encoding and which tolerance out loud, and most of the bugs in this area never happen.

Sources

1. Patterson, D. A., & Hennessy, J. L. (2020). Arithmetic for computers. In Computer organization and design RISC-V edition: The hardware software interface (2nd ed., ch. 3). Morgan Kaufmann. find source ↗
2. Bryant, R. E., & O'Hallaron, D. R. (2016). Floating point. In Computer systems: A programmer's perspective (3rd ed., ch. 2.4). Pearson. find source ↗
3. IEEE. (2019). IEEE Standard for Floating-Point Arithmetic (IEEE 754-2019). IEEE Standards Association. standards.ieee.org
4. Goldberg, D. (1991). What every computer scientist should know about floating-point arithmetic. ACM Computing Surveys, 23(1), 5-48. docs.oracle.com
5. Yergeau, F. (2003). RFC 3629: UTF-8, a transformation format of ISO 10646. RFC Editor. rfc-editor.org
6. Unicode Consortium. (n.d.). What is Unicode? unicode.org
7. Cerf, V. (1969). RFC 20: ASCII format for network interchange. RFC Editor. rfc-editor.org

George Boole published his algebra of true and false in 1854, aiming at the laws of human reasoning and expecting no machinery at all. Seventy years later it turned out to be the exact description of a switch. That accident is the reason a computer can be designed on paper: you can write down what a circuit should do, transform the expression with algebra, and know that the cheaper circuit you end up with behaves identically. This lesson is that toolkit.

The big picture

Underneath every calculation a computer makes is a tiny algebra with only two values, true and false. This lesson introduces that algebra, the three basic operations, and the truth table, the simple grid that lets you describe or check any logic exactly. It then does the thing that makes the algebra pay: turning a table into an expression, and an expression into fewer gates.

Two values, three operations

Boolean algebra is arithmetic where every value is either true (1) or false (0). It was invented by George Boole in the 1800s, long before computers, but it turned out to be the perfect match for circuits that are either on or off. There are three fundamental operations:

• AND is true only when both inputs are true. Think of two switches in a row: the light turns on only if you flip both. Written A AND B, or A . B.
• OR is true when at least one input is true. Think of two switches side by side wired in parallel: either one lights the bulb. Written A OR B, or A + B.
• NOT flips a single value: true becomes false and false becomes true. Written NOT A, or A with a bar over it.

Key idea: Boolean algebra has two values and three core operations: AND (both), OR (at least one), and NOT (flip).

Truth tables: the complete picture

A truth table lists every possible combination of inputs and the output for each. It is like a full answer key: because there are only two values, a small table can capture a function exactly with no ambiguity. For two inputs there are 2 x 2 = 4 rows; for three inputs there are 8 rows. Here are the three basic operations side by side:

A	B	A AND B	A OR B	NOT A
0	0	0	0	1
0	1	0	1	1
1	0	0	1	0
1	1	1	1	0

Notice AND has a single 1 (only the last row), OR has a single 0 (only the first row), and NOT ignores B entirely.

Useful laws you can verify with a table

Boolean algebra has laws that let you simplify expressions, and you can prove any of them by checking that two expressions have identical truth tables. A few important ones:

• Identity: A AND 1 = A, and A OR 0 = A. Combining with the neutral value changes nothing.
• Annihilator: A AND 0 = 0, and A OR 1 = 1. One dominant input forces the result.
• Double negation: NOT (NOT A) = A. Flipping twice returns the original.
• Complement: A AND (NOT A) = 0, and A OR (NOT A) = 1. A thing and its opposite cannot both hold, and one of them must.
• Distributive: A AND (B OR C) = (A AND B) OR (A AND C), which matches ordinary algebra. But Boolean algebra also has the reverse, which ordinary algebra does not: A OR (B AND C) = (A OR B) AND (A OR C).
• Absorption: A OR (A AND B) = A, and A AND (A OR B) = A. If A alone already decides the outcome, the extra term is redundant.
• De Morgan's laws: NOT (A AND B) = (NOT A) OR (NOT B), and NOT (A OR B) = (NOT A) AND (NOT B). Negation turns AND into OR and vice versa.

De Morgan's laws matter enormously in practice because they let designers swap between AND and OR forms to fit whatever gates are cheapest to build.

Look again at that list and you will notice a symmetry. Every law comes in a pair, and each member of the pair becomes the other if you swap AND with OR and swap 0 with 1. That is the principle of duality, and it is not a coincidence: it halves the number of laws you have to remember, and it is why hardware built from NAND gates and hardware built from NOR gates are mirror images of each other.

Key idea: a truth table proves any Boolean law, De Morgan's laws swap AND and OR when you push a NOT inside, and every law has a dual obtained by exchanging AND with OR and 0 with 1.

Worked example: verifying De Morgan

Check NOT (A OR B) = (NOT A) AND (NOT B) by building both sides:

A	B	A OR B	NOT (A OR B)	(NOT A) AND (NOT B)
0	0	0	1	1
0	1	1	0	0
1	0	1	0	0
1	1	1	0	0

The last two columns are identical in every row, so the law holds.

From a table to an expression: sum of products

Here is the step that turns Boolean algebra from a curiosity into a design method. Given any truth table, you can mechanically write an expression that produces it. Take each row whose output is 1, write an AND of all the inputs (using the input directly where it is 1 and its complement where it is 0), and then OR those terms together. Each such term is a minterm, and the result is called sum-of-products form, borrowing the arithmetic names because OR is written + and AND is written as a dot. A complement is written with an apostrophe, so A' means NOT A.

Work the majority function of three inputs, which outputs 1 whenever at least two inputs are 1. It is a genuinely useful circuit: fault-tolerant systems run three copies of a computation and take the majority vote.

A	B	C	Output	Minterm
0	0	0	0	-
0	0	1	0	-
0	1	0	0	-
0	1	1	1	A'.B.C
1	0	0	0	-
1	0	1	1	A.B'.C
1	1	0	1	A.B.C'
1	1	1	1	A.B.C

OR the four minterms and you have a correct circuit: F = A'.B.C + A.B'.C + A.B.C' + A.B.C. Correct, and wasteful. It needs three inverters, four three-input AND gates, and one four-input OR gate.

Worked example: simplifying the majority function

The algebra now earns its keep. The key move is a law that has no arithmetic counterpart: idempotence, X + X = X, which lets you duplicate a term as often as you like. Duplicate A.B.C twice more so each of the other three terms has a partner.

F = A'.B.C + A.B'.C + A.B.C' + A.B.C
  = (A'.B.C + A.B.C) + (A.B'.C + A.B.C) + (A.B.C' + A.B.C)   duplicate A.B.C
  = B.C.(A' + A)      + A.C.(B' + B)    + A.B.(C' + C)        factor each pair
  = B.C.1             + A.C.1           + A.B.1               complement law
  = A.B + A.C + B.C

Read the result back in English and it is obviously right: the output is 1 when any two of the three inputs agree on 1. The circuit is now three two-input ANDs and one three-input OR - four gates instead of eight, with no inverters at all. On a chip that is roughly half the transistors, half the switching power, and one less gate delay on the critical path. Multiply that saving across the millions of small logic blocks in a processor and simplification stops being an exercise and becomes the job.

For expressions of three or four variables, engineers often use a Karnaugh map instead of algebra: a grid whose rows and columns are ordered so that neighbouring cells differ in exactly one input, which makes the groupings you just did by hand visible as rectangles of adjacent 1s. Beyond about six variables, both methods give way to software, and every synthesis tool in the industry is doing a scaled-up version of the same search.

Key idea: any truth table becomes a sum-of-products expression mechanically, and simplifying that expression directly buys fewer gates, less power, and shorter delay.

Where people get stuck

• "OR means exactly one, like a restaurant menu." Boolean OR is inclusive: it is true when one or both inputs are true. The exclusive version is a separate operation, XOR.
• "AND is like addition and OR is like multiplication." It is the reverse in the common notation: OR uses the + symbol and AND uses the . symbol, and neither is ordinary arithmetic.
• "A truth table only samples some inputs." A correct truth table lists every combination, so it fully defines the function.
• "De Morgan just moves the NOT." It also swaps AND for OR; moving the NOT without swapping the operation is wrong.
• "X + X should be 2X." There is no 2 in this algebra. X + X = X, and that idempotence is exactly what licenses the duplication trick used in the simplification above.
• "A simpler expression is only prettier." Each removed gate is real transistors, real switching power, and often a shorter critical path, which raises the achievable clock speed.

Recap

• Boolean algebra uses two values (0 and 1) and three operations: AND, OR, NOT.
• AND is true only when both inputs are true; OR is true when at least one is; NOT flips.
• A truth table lists all input combinations and defines a function completely.
• Laws like identity, annihilator, complement, distribution, absorption, and double negation simplify expressions, and every law has a dual.
• De Morgan's laws swap AND and OR when a NOT is pushed inside.
• Any truth table converts mechanically to sum-of-products form by ORing the minterms of its 1 rows.
• Algebraic simplification, or a Karnaugh map for small functions, turns that correct-but-bloated expression into a cheaper circuit.

The habit to build is to treat a specification, a truth table, an expression, and a circuit as four views of one object. Once you can move freely among them, designing hardware becomes rewriting, and rewriting is something algebra is very good at.

Sources

1. Harris, S. L., & Harris, D. M. (2021). Combinational logic design. In Digital design and computer architecture: RISC-V edition (ch. 2). Morgan Kaufmann. find source ↗
2. Patterson, D. A., & Hennessy, J. L. (2020). The basics of logic design. In Computer organization and design RISC-V edition: The hardware software interface (2nd ed., appendix A). Morgan Kaufmann. find source ↗
3. Shannon, C. E. (1940). A symbolic analysis of relay and switching circuits [Master's thesis, Massachusetts Institute of Technology]. DSpace@MIT. dspace.mit.edu
4. Terman, C., & Ward, S. (2017). 6.004 Computation structures (Chapter 4: Combinational logic). MIT OpenCourseWare. ocw.mit.edu
5. Nisan, N., & Schocken, S. (n.d.). Boolean logic (Project 1). Nand to Tetris. nand2tetris.org
6. Computer History Museum. (n.d.). How do digital computers "think"? CHM Revolution exhibit. computerhistory.org
7. University of California, Berkeley. (n.d.). CS 61C: Great ideas in computer architecture (machine structures). EECS Instructional Support. inst.eecs.berkeley.edu

A modern processor contains tens of billions of transistors, and almost none of them are wired individually. They are grouped into a few dozen repeating patterns, and every one of those patterns is a gate. If you understand what a gate costs in transistors and in time, you can predict most of the design decisions in the rest of this course - including the surprising one that a computer prefers gates that invert their output.

The big picture

Boolean operations are ideas; logic gates are the physical parts that carry them out. This lesson connects the two, introduces the full family of gates, and reveals a surprising fact: a single gate type, NAND, can build every other gate and therefore every computer.

From operation to gate

A logic gate is a tiny circuit that takes one or more input signals (each a 0 or 1 voltage) and produces an output signal according to a Boolean rule. Each basic operation has a matching gate: an AND gate, an OR gate, and an inverter (NOT gate). Gates are drawn with standard shapes so engineers can read a schematic like a sentence.

Think of a gate as a very simple decision-maker wired from transistors. It does one Boolean job, instantly and continuously, as long as power flows.

Key idea: a logic gate is the hardware that performs one Boolean operation on 0/1 voltage signals.

What a gate is made of, and why inverting gates are cheaper

Nearly all digital chips are built in CMOS, which uses two complementary kinds of transistor. An NMOS transistor conducts when its gate input is high, and it is good at pulling an output down to 0. A PMOS transistor conducts when its input is low, and it is good at pulling an output up to 1. Every CMOS gate is therefore two networks: a pull-up network of PMOS above the output and a pull-down network of NMOS below it, arranged so that exactly one of them conducts for any input.

That construction has a consequence people find backwards at first. The pull-down network sees the inputs directly, so the natural output is the inverted function. Count transistors and the picture is stark.

Gate	Transistors	Construction
NOT	2	one PMOS up, one NMOS down
NAND	4	two PMOS in parallel, two NMOS in series
NOR	4	two PMOS in series, two NMOS in parallel
AND	6	a NAND plus an inverter
OR	6	a NOR plus an inverter

Read that table again: AND costs half as much again as NAND, because the only way to build it is to build a NAND and then undo it. In CMOS the inverting gates are the primitives and the friendly-sounding ones are the derived, expensive versions. This is why real schematics are full of bubbles, why designers apply De Morgan's laws to push inversions around until the cheap gates fall out, and why NAND universality is a manufacturing fact rather than a party trick.

Gates take time: propagation delay

A gate is not instantaneous. Its output changes some time after its inputs do, because the transistors must charge or discharge the capacitance of the wire and of every input they drive. That interval is the propagation delay, on the order of tens of picoseconds in a modern process. Two practical rules follow.

First, delays add along a path. If a signal passes through twenty gates at 20 picoseconds each, the result is not ready for 400 picoseconds, which caps the clock frequency of any circuit containing that path. Lesson 8 turns this into an equation. Second, driving more inputs makes a gate slower, because each input adds capacitance. The number of inputs a gate drives is its fan-out, and the number of inputs it has is its fan-in. A gate with high fan-out is usually followed by a chain of progressively larger inverters called a buffer, which is why chips contain many gates whose only job is to repeat a signal harder.

Key idea: gate cost is measured in transistors and in delay, and both are what a designer is actually minimizing when simplifying logic.

The gate family

Beyond the three basics, a few combined gates appear so often they get their own names and symbols:

Gate	Meaning	Output is 1 when...
AND	A AND B	both inputs are 1
OR	A OR B	at least one input is 1
NOT	invert A	the input is 0
NAND	NOT (A AND B)	the inputs are not both 1
NOR	NOT (A OR B)	both inputs are 0
XOR	exclusive OR	the inputs differ
XNOR	equality	the inputs are the same

XOR (exclusive OR) is especially handy: it outputs 1 only when its inputs disagree, which makes it the heart of binary addition and of parity checks.

XOR truth table

A	B	A XOR B
0	0	0
0	1	1
1	0	1
1	1	0

The middle two rows (inputs differ) give 1; the outer rows (inputs match) give 0.

Universal gates: one gate to rule them all

A gate is called universal if you can build every other gate using only copies of it. Both NAND and NOR are universal. This is not just a curiosity: chip factories can optimize for making a sea of identical NAND gates, knowing that pattern can express any logic at all. It is like discovering that a single Lego brick shape, snapped together cleverly, can build any structure.

Here is how NAND builds the three basics:

• NOT from NAND: tie both inputs together. NAND(A, A) = NOT (A AND A) = NOT A.
• AND from NAND: NAND gives NOT (A AND B), so feed that into a NAND-inverter. AND(A, B) = NOT (NAND(A, B)).
• OR from NAND: by De Morgan, A OR B = NOT ((NOT A) AND (NOT B)). Invert each input with a NAND, then NAND the results. So OR(A, B) = NAND(NOT A, NOT B).

Key idea: NAND (and NOR) are universal, so an entire processor can be built from one repeated gate type.

Worked example: NAND as NOT

Feed A into both inputs of a NAND. When A is 0, NOT (0 AND 0) = NOT 0 = 1. When A is 1, NOT (1 AND 1) = NOT 1 = 0. The output is the opposite of A in both cases, so the NAND behaves exactly like an inverter. From that single inverter plus more NANDs, everything else follows.

Worked example: XOR from four NANDs

XOR is the interesting case, because it is not obviously reachable from NAND and it is the gate the adder in the next lesson needs most. Four NANDs suffice. Write N(x, y) for a NAND.

X   = N(A, B)
Y   = N(A, X)
Z   = N(B, X)
Out = N(Y, Z)          claim: Out = A XOR B

Do not take the claim on trust; trace all four input combinations, which is the whole point of having truth tables.

A	B	X = N(A,B)	Y = N(A,X)	Z = N(B,X)	Out = N(Y,Z)
0	0	1	1	1	0
0	1	1	1	0	1
1	0	1	0	1	1
1	1	0	1	1	0

The output column is 0, 1, 1, 0 - exactly XOR. Notice also that the longest path runs through three gates in series (X, then Y or Z, then Out), so this XOR costs three gate delays. A purpose-built CMOS XOR does the same job in about eight to twelve transistors and one gate delay, which is why real chips include XOR as a standard cell instead of assembling it from NANDs. Universality tells you what is possible; the cell library tells you what is fast.

NOR is universal too, by the mirror-image argument. NOR with its inputs tied together is an inverter, OR is a NOR followed by that inverter, and De Morgan gives AND as NOR applied to the inverted inputs. This is the duality principle from the previous lesson showing up in silicon: every NAND-based construction has a NOR-based twin.

Where people get stuck

• "XOR is the same as OR." OR is true when at least one input is 1, including both; XOR is true only when the inputs differ, so 1 XOR 1 is 0.
• "You need many different gate types to build a CPU." A single universal gate such as NAND suffices, though real chips mix gates for speed and area.
• "NAND is a rare exotic gate." NAND is one of the cheapest and most common gates in real silicon, which is why universality matters.
• "A gate stores its result." A basic gate has no memory; its output simply follows its current inputs. Storage needs the sequential circuits covered later.
• "AND must be simpler than NAND, since NAND is AND plus NOT." In CMOS the opposite holds: NAND is 4 transistors and AND is 6, because AND is built by inverting a NAND.
• "Gates respond instantly." Every gate has a propagation delay, and delays add along a path. The longest such path is what limits clock speed.

Recap

• A logic gate is the hardware that performs one Boolean operation.
• CMOS builds every gate from a PMOS pull-up network and an NMOS pull-down network, which makes inverting gates the cheap primitives.
• The family includes AND, OR, NOT, NAND, NOR, XOR, and XNOR.
• XOR outputs 1 only when its inputs differ, which drives addition and parity, and it can be built from four NANDs at a cost of three gate delays.
• NAND and NOR are universal: they can build any other gate, and each construction has a dual in the other.
• Tying a NAND's inputs together makes an inverter, the starting point for building the rest.
• Gates cost transistors and time; fan-out and long gate chains are what turn a logic design into a speed limit.

Keep two numbers in mind from here on: a gate is a handful of transistors, and a gate is a few tens of picoseconds. Every architectural trick in the rest of this course is an attempt to buy more useful work per transistor or per picosecond.

Sources

1. Harris, S. L., & Harris, D. M. (2021). Logic gates and CMOS transistors. In Digital design and computer architecture: RISC-V edition (ch. 1.5-1.7). Morgan Kaufmann. find source ↗
2. Patterson, D. A., & Hennessy, J. L. (2020). The basics of logic design. In Computer organization and design RISC-V edition: The hardware software interface (2nd ed., appendix A). Morgan Kaufmann. find source ↗
3. Terman, C., & Ward, S. (2017). 6.004 Computation structures (Chapter 3: CMOS technology). MIT OpenCourseWare. ocw.mit.edu
4. Nisan, N., & Schocken, S. (n.d.). Boolean logic (Project 1: building all gates from Nand). Nand to Tetris. nand2tetris.org
5. Computer History Museum. (n.d.). Digital logic. CHM Revolution exhibit. computerhistory.org
6. Sedgewick, R., et al. (n.d.). Dictionary of algorithms and data structures. National Institute of Standards and Technology. xlinux.nist.gov
7. University of California, Berkeley. (n.d.). CS 61C: Great ideas in computer architecture (machine structures). EECS Instructional Support. inst.eecs.berkeley.edu

Nobody designs a processor by placing gates one at a time, any more than a novelist assembles sentences letter by letter. Engineers work with a vocabulary of a few standard blocks that appear over and over, and three of them account for a startling fraction of any datapath. Once you can see adders, multiplexers, and decoders inside a block diagram, a CPU stops being a mystery box and becomes a legible arrangement of familiar parts.

The big picture

Individual gates are like single words; to do useful work we combine them into standard building blocks. This lesson covers three of the most important: the adder that does binary arithmetic, the multiplexer that chooses among inputs, and the decoder that activates one output out of many. It also does the arithmetic that explains why simple adders are too slow for a modern machine.

Combinational versus sequential

A combinational circuit is one whose output depends only on its current inputs, with no memory of the past. Give it the same inputs and you always get the same outputs, right away. The blocks in this lesson are all combinational. Circuits that remember, such as registers, are sequential and come next.

Key idea: combinational circuits compute a fresh answer from their inputs every moment, with no stored state.

The half adder and full adder

Adding two bits produces a sum bit and possibly a carry into the next column, exactly like adding decimal digits. A half adder adds two bits: the sum is A XOR B and the carry is A AND B. Check it: 1 + 1 in binary is 10, so the sum bit is 0 (1 XOR 1) and the carry is 1 (1 AND 1). Correct.

A half adder cannot accept a carry coming in from the previous column, so real addition uses a full adder, which has three inputs: A, B, and a carry-in. Its outputs are the sum of the three bits and a carry-out. Chaining full adders, each carry-out feeding the next carry-in, builds a ripple-carry adder that adds whole multi-bit numbers, one column at a time like grade-school addition.

A	B	Carry-in	Sum	Carry-out
0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	1	0
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

The last row shows 1 + 1 + 1 = 3, which in binary is 11: sum bit 1, carry-out 1. Read the table as a whole and two clean rules appear. The sum bit is 1 whenever an odd number of the three inputs is 1, which is exactly A XOR B XOR carry-in. The carry-out is 1 whenever at least two inputs are 1, which is the majority function you simplified in Lesson 5: (A AND B) OR (A AND Cin) OR (B AND Cin). Nothing here was invented for adders; it is the same logic, met again.

Key idea: a full adder adds three bits (two operands plus a carry-in), and chaining them adds full numbers.

Worked example: tracing a 4-bit ripple-carry addition

Add 1011 (11) and 0110 (6) in a 4-bit ripple-carry adder, with the incoming carry set to 0. Work right to left, exactly as you would on paper, and record what each full adder sees.

stage  A  B  Cin | Sum  Cout    running result
  0    1  0   0  |  1     0     ....1
  1    1  1   0  |  0     1     ...01
  2    0  1   1  |  0     1     ..001
  3    1  0   1  |  0     1     .0001

  sum bits = 0001, carry out = 1  ->  10001 = 17     and 11 + 6 = 17

Look at stage 2. Its inputs A and B are 0 and 1, which alone would produce a sum of 1 and no carry. The 1 arriving from stage 1 changes both outputs. That dependency is the entire problem with this design: stage 3 cannot settle until stage 2 has, which cannot settle until stage 1 has. The carry ripples, which is where the name comes from.

Why ripple-carry does not scale

Put numbers on it. Each full adder needs roughly two gate delays to produce its carry-out once its carry-in is stable. A 4-bit adder therefore takes about 8 gate delays, which is fine. A 64-bit adder takes about 128 gate delays, and at 20 picoseconds per gate that is 2.56 nanoseconds - a hard ceiling of under 400 MHz for any clock that must contain one addition. Modern processors run ten times faster than that and still perform several additions per cycle, so plainly they do not use ripple-carry.

The fix is carry-lookahead, and the idea is worth knowing even if the algebra stays in a later course. For each bit position, compute two signals directly from A and B without waiting for anything: the position generates a carry when A AND B (it will emit a carry no matter what arrives), and it propagates a carry when A XOR B (it will pass along whatever arrives). Those signals are available immediately, in parallel, for all 64 positions. Combining them in a tree lets the carry into every position be computed in a number of gate delays proportional to log(n) rather than n. A 64-bit lookahead adder settles in roughly a dozen gate delays instead of 128. The cost is far more gates, which is exactly the trade this course keeps returning to: area and power bought in exchange for time.

Key idea: ripple-carry delay grows linearly with word width, so real adders compute generate and propagate signals in parallel and combine them in a tree of logarithmic depth.

From adder to ALU

An arithmetic logic unit is mostly an adder with company. Put the adder next to a bank of bitwise units (AND, OR, XOR), run all of them at once on the same operands, and use a multiplexer to select which result leaves the unit. Computing every operation and discarding all but one sounds wasteful, and it is - in energy. It is also faster than deciding first and computing second, and speed is what the ALU is for.

Subtraction needs no separate hardware at all, which is the payoff from Lesson 3. To compute A - B, feed B through a row of XOR gates controlled by a single "subtract" signal. When that signal is 0 the XORs pass B through unchanged; when it is 1 they invert every bit. Wire the same signal into the adder's carry-in, and the adder computes A + NOT(B) + 1, which is A + (-B) in two's complement. One control wire, one row of XORs, and subtraction is free.

The multiplexer: a data selector

A multiplexer, or mux, picks one of several data inputs and passes it to a single output, based on select lines. It is exactly like a railroad switch or a TV channel selector: many possible sources come in, the select control decides which one gets through. A 2-to-1 mux has two data inputs, one select bit, and one output: when select is 0 it passes input 0, when select is 1 it passes input 1.

In general, a mux with n select lines can choose among 2ⁿ inputs. A 4-to-1 mux needs 2 select bits (2² = 4). Muxes are everywhere inside a CPU, for example choosing whether the next number comes from memory or from a register.

There is a deeper fact about multiplexers that is easy to miss. A mux with n select lines can implement any Boolean function of n variables: wire the function's truth-table output column into the 2^n data inputs and drive the select lines with the variables. The mux then simply looks up the answer. That is why multiplexers are the workhorse of programmable hardware, and it is essentially how a field-programmable gate array stores logic in lookup tables.

The decoder: one hot output

A decoder does the opposite job of selecting: it takes an n-bit input and activates exactly one of its 2ⁿ outputs, the one whose number matches the input. It is like a mailroom that reads a room number and lights up only that one mailbox. A 3-to-8 decoder reads a 3-bit code and raises one of 8 output lines. Decoders are how a memory chip turns an address into a signal that selects the correct storage cell.

That pattern - exactly one line high and all others low - is called one-hot encoding, and it appears everywhere once you notice it. A register file uses a decoder on the register number to enable one register's write port. An instruction decoder raises one line per opcode, and those lines become the control signals of Lesson 9. A RAM chip's row decoder turns the upper address bits into a single selected row. Each output of a decoder is a minterm of its inputs, which connects it straight back to sum-of-products form: a decoder plus an OR gate is a general-purpose way to build any function, just as a mux is.

Key idea: a multiplexer funnels many inputs down to one chosen output, while a decoder lights up one of many outputs from a coded input, and both are general enough to implement arbitrary logic.

Where people get stuck

• "A half adder can add binary numbers of any size." A half adder handles only two single bits with no carry-in; multi-bit addition needs full adders chained together.
• "A multiplexer combines its inputs into one value." It selects exactly one input to pass through; it does not add or mix them.
• "A decoder and a multiplexer are the same." They are opposites: a mux chooses one input for one output, a decoder activates one output from a coded input.
• "These blocks store their results." They are combinational, so the output changes the instant the inputs do.
• "A wider adder is just as fast as a narrow one." In ripple-carry it is not: delay grows with the number of bits, which is the whole reason carry-lookahead exists.
• "The ALU decides which operation to run and then runs it." It usually runs all of them at once and a multiplexer picks the answer, because selecting is faster than deciding first.

Recap

• Combinational circuits depend only on present inputs, with no memory.
• A half adder adds two bits (sum = XOR, carry = AND); a full adder adds three bits, with sum = XOR of all three and carry-out = majority of all three.
• Chaining full adders makes a ripple-carry adder for whole numbers, whose delay grows linearly with width.
• Carry-lookahead computes generate and propagate signals in parallel and combines them in a tree, cutting the delay to logarithmic depth.
• An ALU is an adder beside bitwise units with a mux on the output, and subtraction comes free by inverting one operand and setting carry-in to 1.
• A multiplexer uses select lines to pass one of 2^n inputs to a single output, and can implement any function of its select variables.
• A decoder activates one of 2^n outputs matching an n-bit input, producing the one-hot signals that drive register files, memories, and instruction decode.

These three blocks are the alphabet of the datapath in Module 4. When you see a CPU diagram, look for the adder that computes the next instruction address, the mux that chooses between a register value and a constant, and the decoder that turns an opcode into control lines. They are always there.

Sources

1. Harris, S. L., & Harris, D. M. (2021). Digital building blocks. In Digital design and computer architecture: RISC-V edition (ch. 5). Morgan Kaufmann. find source ↗
2. Patterson, D. A., & Hennessy, J. L. (2020). Arithmetic for computers. In Computer organization and design RISC-V edition: The hardware software interface (2nd ed., ch. 3). Morgan Kaufmann. find source ↗
3. Terman, C., & Ward, S. (2017). 6.004 Computation structures (Chapter 4: Combinational logic). MIT OpenCourseWare. ocw.mit.edu
4. Nisan, N., & Schocken, S. (n.d.). Boolean arithmetic and the ALU (Project 2). Nand to Tetris. nand2tetris.org
5. Cornell University. (2019). CS 3410: Computer system organization and programming. Cornell Computer Science. cs.cornell.edu
6. University of California, Berkeley. (n.d.). CS 61C: Great ideas in computer architecture (machine structures). EECS Instructional Support. inst.eecs.berkeley.edu
7. Computer History Museum. (n.d.). The silicon engine: A timeline of semiconductors in computers. computerhistory.org

In November 2004 Intel shipped a Pentium 4 running at 3.8 GHz. Two decades and roughly a thousandfold increase in transistor count later, the fastest desktop chips boost to about 6 GHz. Clock speed, which had multiplied by hundreds in the preceding twenty years, essentially stopped. This lesson explains what sets a clock period in the first place, and then explains exactly what stopped.

The big picture

Combinational circuits can compute, but they forget everything the instant inputs change. To store a value, a program counter, or the contents of a register, a circuit must remember. This lesson shows how feedback creates memory, how a clock keeps that memory orderly, and how flip-flops become the storage cells of a computer.

Memory from feedback

A sequential circuit has outputs that depend on both the current inputs and its stored past, its state. The trick that creates memory is feedback: wiring a gate's output back to its own input so the circuit can hold a value in place. The simplest example is the SR latch built from two cross-coupled NOR gates, which can be Set to 1 or Reset to 0 and then holds that value on its own, like a seesaw that stays wherever you last pushed it.

Key idea: feedback lets a circuit hold a value, turning gates into memory.

Tracing an SR latch

The claim that feedback creates memory deserves to be checked rather than asserted. Take two NOR gates. The output of the first, call it Q, feeds an input of the second, whose output Q' feeds back into the first. The remaining inputs are S (set) and R (reset). Recall that a NOR outputs 1 only when both its inputs are 0.

S=0 R=0, currently Q=1, Q'=0
    Q  = NOR(R, Q') = NOR(0, 0) = 1     unchanged
    Q' = NOR(S, Q)  = NOR(0, 1) = 0     unchanged   -> the state HOLDS

S=1 R=0
    Q' = NOR(1, Q) = 0
    Q  = NOR(0, 0) = 1                  -> forced to 1, the latch is SET

S=0 R=1
    Q  = NOR(1, Q') = 0
    Q' = NOR(0, 0)  = 1                 -> forced to 0, the latch is RESET

S=1 R=1
    Q = 0 and Q' = 0 at the same time    -> illegal: the outputs are supposed
                                            to be complements, and whichever
                                            input drops first decides the
                                            result, which is a race

The first case is the whole point: with both inputs quiet, the circuit reproduces whatever it was already doing. That self-consistency is the stored bit. The last case is the reason nobody exposes a raw SR latch to a designer; higher-level storage elements are built so that the forbidden combination cannot be requested.

The clock: keeping time

If storage elements updated whenever their inputs wiggled, a big circuit would be chaos. The clock is a signal that ticks steadily between 0 and 1, like a metronome that everyone marches to. Its speed is the clock frequency, measured in hertz. A 3 GHz clock ticks 3 billion times per second, so one clock cycle lasts 1 / 3,000,000,000 second, about 0.33 nanoseconds. The clock gives every part of the chip a shared heartbeat so changes happen in a coordinated rhythm.

The clock period is simply 1 divided by the frequency. For a 2 GHz clock the period is 1 / (2 x 10⁹) = 0.5 nanoseconds. The period must be long enough for the slowest signal to settle before the next tick, which is what ultimately limits how fast a chip can run.

Latches versus flip-flops

A latch is level-sensitive: it follows its input the whole time the clock is at one level, like a door propped open. A flip-flop is edge-triggered: it captures its input only at the instant the clock changes, usually the rising edge, like a camera that snaps exactly at the tick. Edge triggering is preferred in modern designs because it makes timing predictable: every flip-flop updates once per cycle, at the same moment.

The workhorse is the D flip-flop (D for data). At each clock edge it copies whatever is on its D input to its output Q and then holds it steady until the next edge. In effect it remembers one bit for one clock cycle at a time.

How does an edge-triggered device get built from level-sensitive parts? With two latches in series, called master-slave. The master latch is transparent while the clock is low and the slave while the clock is high, and because they are never open at the same time, data can advance through only one of them per half cycle. A value entering while the clock is low waits in the master, and the instant the clock rises the master closes and the slave opens, passing that captured value through. The visible behaviour is a single sample taken at the rising edge, assembled out of two things that individually just follow their inputs.

Key idea: a latch follows its input while the clock level is active, while an edge-triggered flip-flop samples its input once per clock tick.

Setup, hold, and the real clock equation

A flip-flop cannot capture a value that is still moving. It demands that its input be stable for a short window before the edge, called the setup time, and remain stable for a short window after it, called the hold time. It also takes a little while after the edge to present the new value on its output, the clock-to-Q delay. Those three numbers, plus the delay of the logic between flip-flops, are what actually set the clock period.

T_clock  >=  t_clock-to-Q  +  t_logic  +  t_setup  +  t_skew

Worked budget for one pipeline stage:
    clock-to-Q delay        30 ps
    longest logic path     250 ps
    setup time              20 ps
    clock skew              20 ps
    -------------------------------
    minimum period         320 ps   ->  f_max = 1 / 320 ps = 3.125 GHz

Two lessons fall out of that arithmetic. First, only 250 of the 320 picoseconds do any computing; the rest is overhead paid every single cycle. That is why cutting a long logic path into two shorter stages does not double the clock speed - each new stage pays the overhead again. Second, clock skew, the difference in arrival time of the clock edge at two different flip-flops, is pure loss. Distributing one edge across a chip a couple of centimetres wide is such a hard problem that the clock distribution network can consume a substantial share of a processor's power.

There is also a failure mode with no clean fix. If an input changes right inside the setup window - which is unavoidable for a signal arriving from a button, a network, or another clock domain - the flip-flop can enter metastability, hovering between 0 and 1 for an unpredictable time before falling one way. The standard treatment is a synchronizer: two flip-flops in series, giving any metastable state a full extra cycle to resolve before the rest of the circuit sees it. This does not eliminate the risk, it makes it astronomically improbable, and that distinction is honest engineering rather than a weakness.

From one bit to a register

Line up several D flip-flops sharing the same clock and you get a register, a small group of bits that update together. A 32-bit register is just 32 D flip-flops in a row. Registers hold the values the CPU is actively working with, and the program counter is a special register that holds the address of the next instruction. Every piece of state in a processor, from status flags to the entire register file, is ultimately built from flip-flops clocked in unison.

Worked example: clock period

Suppose the longest combinational path between two flip-flops takes 0.4 nanoseconds to settle. The clock period must be at least that long, so the fastest safe frequency is 1 / 0.4 ns = 1 / (0.4 x 10^-9 s) = 2.5 x 10⁹ Hz = 2.5 GHz. Trying to clock faster would tick before the signal is ready, storing a wrong value. This is exactly why reducing the slowest path lets designers raise the clock speed.

Why clock speed stopped rising

If shorter paths raise the clock, and transistors kept getting smaller and faster, why did frequency plateau around 2005? The answer is power, and it has a formula. The dynamic power a CMOS chip burns is roughly

P = alpha * C * V^2 * f

    alpha = fraction of transistors switching each cycle
    C     = capacitance being charged and discharged
    V     = supply voltage
    f     = clock frequency

For about thirty years this equation was survivable because of Dennard scaling, an observation from 1974 that as transistors shrink, you can lower the supply voltage in proportion. Capacitance per transistor falls, V falls, and the V^2 term falls quadratically - so you could double the transistor count and raise the frequency while power per square millimetre stayed roughly constant. Free performance, generation after generation.

Dennard scaling broke in the mid-2000s. Supply voltage could no longer fall, because a transistor's threshold voltage cannot be lowered indefinitely without the device leaking current even when it is supposed to be off, and that static leakage began to dominate. With V pinned, power now rises linearly with frequency and there is no quadratic saving to pay for it. Push the clock up 30 percent and the chip gets 30 percent hotter for the same work, plus more because faster switching often demands a higher voltage anyway. Chips ran into a thermal wall of roughly 100 to 150 watts that air cooling can remove from a few square centimetres, and the wall has not moved much since.

The industry's response was to stop selling frequency and start selling cores. If you cannot make one core twice as fast, put two on the die and run both at the old clock. That decision is why Lesson 18 exists, why Amdahl's law suddenly became everyone's problem, and why Herb Sutter titled his 2005 essay on the shift "The Free Lunch Is Over".

Key idea: the clock stopped rising because dynamic power scales with V^2 x f and voltage stopped falling, so the industry spent extra transistors on more cores instead of a faster one.

Where people get stuck

• "Combinational circuits can store data if you wait." Without feedback there is no memory; storage requires a latch or flip-flop.
• "A latch and a flip-flop are the same thing." A latch is level-sensitive (transparent while the clock is high), a flip-flop is edge-triggered (captures only at the clock edge).
• "A faster clock is always better." The period must exceed the slowest signal path; clocking too fast stores wrong values.
• "The clock does computation." The clock only sets timing; the gates do the computing. The clock decides when results are captured.
• "A higher clock always means a faster computer." Work done per second is frequency times work per cycle. A 3 GHz chip that finishes two instructions per cycle beats a 4 GHz chip that finishes one.
• "Clock speed stalled because transistors stopped shrinking." They kept shrinking. What stopped was voltage scaling, which is what had been keeping power density flat.

Recap

• Sequential circuits have state; feedback is what gives a circuit memory, as the SR latch trace shows directly.
• The clock is a steady tick that coordinates when storage updates.
• Clock period equals 1 divided by frequency, and must cover clock-to-Q delay, the slowest logic path, setup time, and clock skew.
• A latch is level-sensitive; a flip-flop is edge-triggered and samples once per cycle, built as a master-slave pair of latches.
• Setup and hold windows must be respected, and asynchronous inputs need a synchronizer to make metastability vanishingly unlikely.
• A D flip-flop stores one bit; grouping them makes registers and the program counter.
• Dynamic power scales as C x V^2 x f, and the end of Dennard voltage scaling capped frequency and pushed the industry to multicore.

From here on, treat the clock period as a budget you are spending. Every architectural idea in the remaining modules - pipelining, caching, speculation - is a way to get more finished work out of the same 300-odd picoseconds.

Sources

1. Harris, S. L., & Harris, D. M. (2021). Sequential logic design and timing. In Digital design and computer architecture: RISC-V edition (ch. 3). Morgan Kaufmann. find source ↗
2. Patterson, D. A., & Hennessy, J. L. (2020). The basics of logic design; Performance. In Computer organization and design RISC-V edition: The hardware software interface (2nd ed., appendix A and ch. 1.6-1.10). Morgan Kaufmann. find source ↗
3. Terman, C., & Ward, S. (2017). 6.004 Computation structures (Chapter 6: Sequential logic). MIT OpenCourseWare. ocw.mit.edu
4. Nisan, N., & Schocken, S. (n.d.). Sequential logic (Project 3). Nand to Tetris. nand2tetris.org
5. Sutter, H. (2005). The free lunch is over: A fundamental turn toward concurrency in software. Dr. Dobb's Journal, 30(3). gotw.ca
6. Hennessy, J. L., & Patterson, D. A. (2019). A new golden age for computer architecture. Communications of the ACM, 62(2), 48-60. cacm.acm.org
7. Fog, A. (n.d.). The microarchitecture of Intel, AMD and VIA CPUs. Technical University of Denmark. agner.org

Open a die photograph of a modern processor and the largest regions are memory: caches, buffers, tables. The part that actually computes is a surprisingly small rectangle. That rectangle is the datapath, and beside it sits an even smaller block whose only job is to tell the datapath what to do this cycle. Everything a program does passes through those two, so it is worth knowing precisely where the boundary between them lies.

The big picture

A CPU is not one blob of logic; it is a small set of cooperating parts. This lesson names those parts, splits the CPU into the datapath that moves and crunches numbers and the control that directs traffic, and shows how they work together to run one instruction. It then introduces the equation that decides whether one processor is genuinely faster than another.

The main parts of a CPU

Inside a processor you will find a handful of key components:

• The register file: a small, very fast set of storage slots (registers) that hold the values being worked on right now. Think of it as the workbench directly in front of you.
• The arithmetic logic unit (ALU): the calculator that performs operations like add, subtract, AND, OR, and comparisons.
• The program counter (PC): a register holding the address of the next instruction to fetch.
• The control unit: the manager that reads each instruction and tells every other part what to do.

Key idea: a CPU is a register file, an ALU, a program counter, and a control unit working together.

Why so few registers

A typical machine offers 16 or 32 general-purpose registers, which seems miserly next to gigabytes of RAM. There are three reasons, and each one is a design pressure you will meet again. First, small is fast: a 32-entry array can be read in a fraction of a clock cycle, while a larger one needs longer wires and more decoding, and would become the slowest path in the machine. Second, registers are expensive in a way memory is not, because the register file must serve several accesses at once - a typical instruction reads two operands and writes one result, so the file needs two read ports and a write port, and port count drives area up sharply. Third, register numbers live inside the instruction word: with 32 registers each operand field costs 5 bits, and three operand fields already consume 15 of a 32-bit instruction. Doubling the register count would cost three more bits of every instruction that uses them.

Datapath: where the numbers flow

The datapath is all the hardware that actually holds and transforms data: the registers, the ALU, and the wires and multiplexers that connect them. Picture it as a road network with the ALU as a factory in the middle. Values leave the register file, travel to the ALU, get processed, and the result travels back to be stored. The datapath does not decide what to do; it simply provides the roads and the machinery.

The ALU deserves a closer look. It takes two input numbers and a small code that selects the operation, and it produces a result plus status flags such as zero (was the result 0?) and carry (did the addition overflow the width?). Those flags let the machine make decisions, for example whether to take a branch.

Control: the traffic director

The control unit is the part that reads the current instruction and generates the control signals that steer the datapath. Control signals are the settings on all those multiplexers and the ALU: which registers to read, which operation the ALU should perform, whether to write a result back, and where the next instruction comes from. If the datapath is the roads and factory, control is the set of traffic lights and switch settings that route each job correctly.

A helpful way to see the split: the datapath can do many things, and control decides which of them happens this cycle. The same adder in the datapath might compute a sum for one instruction and a memory address for another; control makes the difference.

Key idea: the datapath holds and transforms data, while control generates the signals that decide what the datapath does each cycle.

How they cooperate on one instruction

Consider an instruction that adds two registers and stores the result in a third. The steps interleave datapath and control:

1. Control decodes the instruction and sees it is an add.
2. Control tells the register file to read the two source registers; their values flow out on the datapath.
3. Control sets the ALU operation code to "add"; the ALU computes the sum.
4. Control asserts the write-enable signal, so the sum is written into the destination register.
5. Control updates the program counter to point at the next instruction.

Every arrow of data is datapath; every decision and signal is control. Neither is useful without the other.

What the control signals actually look like

Control is less abstract than it sounds. For a simple single-cycle machine it is a handful of wires whose values are a direct function of the opcode. Here is the pattern for four representative instructions, using names drawn from the classic RISC-V teaching datapath.

Instruction	RegWrite	ALUSrc	MemRead	MemWrite	MemToReg	Branch
add (register)	1	0 = register	0	0	0 = ALU	0
lw (load word)	1	1 = immediate	1	0	1 = memory	0
sw (store word)	0	1 = immediate	0	1	-	0
beq (branch if equal)	0	0 = register	0	0	-	1

That table is the control unit. Feed the opcode into a decoder, OR together the right outputs, and you have generated every line. Two entries repay a second look. The dashes mean "do not care", because when RegWrite is 0 nothing is written back and it does not matter what the MemToReg mux selects - and do-not-cares are exactly the freedom a logic minimizer exploits to shrink the circuit. And notice that lw and sw both set ALUSrc to the immediate: the ALU is computing an address, base register plus offset, not doing arithmetic the programmer asked for. Same hardware, different purpose, chosen by one control wire.

Hardwired control, microcode, and the RISC argument

There are two ways to build that decoder. Hardwired control implements it as combinational logic, which is fast and inflexible. Microcoded control stores, in a small internal ROM, a sequence of micro-instructions for each machine instruction, and steps through them. Microcode was how 1970s machines afforded complex instructions: a single opcode could expand into dozens of internal steps, so the instruction set could include string copies and polynomial evaluation without any of that logic being built directly.

In 1980 David Patterson and David Ditzel argued in "The Case for the Reduced Instruction Set Computer" that this was the wrong trade. Compilers, they observed, rarely emitted the exotic instructions; the microcode ROM was large, slow, and buggy; and a simpler instruction set of fixed-width, register-to-register operations could be hardwired, pipelined, and clocked much faster. Simple instructions executed quickly would beat complex instructions executed slowly, even if you needed more of them.

What actually happened is more interesting than either side predicted, and worth stating plainly because the textbook debate is often left in 1990. Both approaches converged. Since the Pentium Pro in 1995, x86 processors decode their complex instructions into simple internal micro-operations and then execute those on a pipelined, register-renaming core that is RISC-like in every respect that matters; the complex instruction set survives as an interface, not as an implementation. Meanwhile the RISC families grew: ARM and RISC-V now have vector extensions, cryptography instructions, and hundreds of opcodes. The genuinely durable RISC insight was not "few instructions" but "a decodable, regular encoding that a pipeline can chew through at one instruction per cycle", and today essentially everyone builds that way.

Key idea: the instruction set is an interface and the datapath is an implementation, which is why a CISC interface can sit on top of a RISC-style engine.

Measuring a processor: the performance equation

Now the equation that keeps arguments about speed honest. The time a program takes is

CPU time = (instructions executed) x (cycles per instruction) x (clock period)

Three factors, three different owners: the compiler and instruction set mostly determine the first, the microarchitecture the second, and the circuit design and process technology the third. Improving one at the expense of another can easily lose. Compare two machines running the same billion-instruction program.

Machine A: 1.5 GHz, CPI 1.2
    period = 1 / 1.5 GHz = 0.667 ns
    time   = 1e9 x 1.2 x 0.667 ns = 0.80 s

Machine B: 3.0 GHz, CPI 3.0
    period = 1 / 3.0 GHz = 0.333 ns
    time   = 1e9 x 3.0 x 0.333 ns = 1.00 s

Machine A wins by 1.00 / 0.80 = 1.25x, at half the clock speed.

This is exactly how a lower-clocked design can outrun a higher-clocked one, and why "gigahertz" alone stopped being a useful number to compare. It is also the frame for the rest of the course: pipelining attacks CPI, caches attack the stalls that inflate CPI, and Lesson 8 explained why the third factor stopped improving.

Where people get stuck

• "The control unit does the arithmetic." The ALU in the datapath does the math; control only tells it which operation to run.
• "Registers are part of main memory." Registers are inside the CPU and far faster than main memory; the register file is a separate, tiny store.
• "The datapath decides what the program does." The datapath provides capability; control selects which action happens each cycle.
• "The ALU only adds and subtracts." A typical ALU also does AND, OR, comparisons, and sets status flags like zero and carry.
• "RISC won and CISC lost." The RISC execution model won; the x86 instruction set is still everywhere, decoded into RISC-like micro-operations inside the chip.
• "The instruction set is the processor." It is the contract. Two chips implementing the same instruction set can differ by an order of magnitude in speed and power.

Recap

• A CPU contains a register file, an ALU, a program counter, and a control unit.
• Registers are few because small arrays are fast, ports are expensive, and register numbers occupy bits in every instruction.
• The datapath is the registers, ALU, and wiring that hold and transform data.
• The ALU produces a result plus status flags such as zero and carry.
• The control unit reads each instruction and emits the control signals that steer the datapath; those signals are a small table indexed by opcode.
• Control can be hardwired or microcoded, and the RISC argument was that hardwired simplicity clocks faster than microcoded complexity.
• The approaches converged: complex instruction sets survive as interfaces decoded into simple micro-operations.
• CPU time = instructions x CPI x clock period, so clock speed alone never settles which machine is faster.

Hold on to the interface-versus-implementation distinction. It is the reason the same program runs on a phone and a server, the reason architects can redesign a chip completely without breaking software, and, as Lesson 10 will show, the reason a processor can quietly do things out of order that the interface never promised.

Sources

1. Patterson, D. A., & Hennessy, J. L. (2020). The processor. In Computer organization and design RISC-V edition: The hardware software interface (2nd ed., ch. 4). Morgan Kaufmann. find source ↗
2. Harris, S. L., & Harris, D. M. (2021). Microarchitecture. In Digital design and computer architecture: RISC-V edition (ch. 7). Morgan Kaufmann. find source ↗
3. Patterson, D. A., & Ditzel, D. R. (1980). The case for the reduced instruction set computer. ACM SIGARCH Computer Architecture News, 8(6), 25-33. doi.org ↗
4. Hennessy, J. L., & Patterson, D. A. (2019). A new golden age for computer architecture. Communications of the ACM, 62(2), 48-60. cacm.acm.org
5. Terman, C., & Ward, S. (2017). 6.004 Computation structures (Chapter 7: Designing an instruction set). MIT OpenCourseWare. ocw.mit.edu
6. RISC-V International. (n.d.). Ratified specifications. riscv.org
7. Intel Corporation. (n.d.). Intel 64 and IA-32 architectures software developer's manual. cdrdv2.intel.com

Every program you have ever run, on any machine, reduces to one loop repeated a few billion times a second. The loop itself is almost embarrassingly simple. What is not simple is what modern processors do to run several turns of it at once - and the last part of this lesson shows how that cleverness leaked secrets out of nearly every processor on earth.

The big picture

A running program is just the CPU repeating the same small loop billions of times: grab the next instruction, figure out what it means, do it, then move on. This lesson walks through that loop, called the fetch-decode-execute cycle, shows how it turns stored bytes into action, and then shows how real processors overlap many cycles at once through pipelining and speculation.

The stored-program idea

Modern computers follow the von Neumann model: both the program's instructions and its data live in the same memory, as numbers. That is a powerful idea. It means the CPU can treat instructions like any other data to fetch, and it means one machine can run any program simply by loading different bytes. The cost is that instructions and data share the same path to memory, a limit later lessons will revisit.

Key idea: in the von Neumann model, instructions and data are stored together as numbers in the same memory.

The three phases

Every instruction goes through the same stages, driven by the clock:

1. Fetch: the CPU reads the instruction stored at the address in the program counter (PC), and copies it into an instruction register. Then it advances the PC to point at the following instruction.
2. Decode: the control unit examines the instruction's bits to work out what operation it is and which registers or memory it involves.
3. Execute: the datapath carries out the operation, for instance the ALU computes a sum, a value is read from memory, or the PC is changed to jump elsewhere.

An everyday analogy is a cook following a recipe card by card: read the next card (fetch), understand what it asks (decode), perform that step (execute), then reach for the next card. The cook does not memorize the whole recipe; the card in hand is enough, just as the PC always points at the current spot.

Key idea: the CPU repeatedly fetches an instruction, decodes it, and executes it, one after another.

Following a tiny example

Imagine memory holds a short program, one instruction per address starting at address 100:

Address	Instruction
100	load R1 from memory[200]
101	add R2 = R1 + R1
102	store R2 into memory[201]

Starting with PC = 100, the machine fetches the load, decodes it as a memory read, executes it by bringing memory[200] into R1, and advances PC to 101. It then fetches the add, decodes it, executes R2 = R1 + R1, and advances PC to 102. Finally it fetches the store, decodes it, and writes R2 out to memory[201]. Three trips around the loop ran the whole program.

Trace the machine state, step by step

Descriptions of the cycle are easy to nod along to and hard to actually hold. So run the same program again and write down every piece of state after every phase. Assume memory[200] contains 21 and everything else starts undefined.

                                  PC    IR              R1    R2   m[200]  m[201]
start                             100   -               ?     ?    21      ?
1. fetch     read m[100], PC+1    101   load R1,[200]   ?     ?    21      ?
2. decode    "memory read into R1" 101  load R1,[200]   ?     ?    21      ?
3. execute   R1 <- m[200]         101   load R1,[200]   21    ?    21      ?
4. fetch     read m[101], PC+1    102   add R2,R1,R1    21    ?    21      ?
5. decode    "ALU add, srcs R1,R1" 102  add R2,R1,R1    21    ?    21      ?
6. execute   R2 <- 21 + 21        102   add R2,R1,R1    21    42   21      ?
7. fetch     read m[102], PC+1    103   store R2,[201]  21    42   21      ?
8. decode    "memory write from R2" 103 store R2,[201]  21    42   21      ?
9. execute   m[201] <- R2         103   store R2,[201]  21    42   21      42

Three details there are worth pausing on. The program counter is incremented during fetch, not at the end of the instruction, which is why it already reads 101 while the load is still being decoded - and why a branch must overwrite a PC that has already moved on. The instruction register holds the fetched bits for the whole instruction, giving decode and execute something stable to read. And the decode rows change no data at all; they only produce control signals, which is the datapath-versus-control split made visible.

Changing the flow: branches and jumps

Normally the PC just increments, so instructions run in order. A branch or jump instruction breaks that pattern by writing a new value into the PC during execute, sending the machine to a different address. This is how loops and if-statements work at the hardware level: a conditional branch checks a status flag, and if the condition holds it loads the PC with the target address instead of the next one. Without branches a program could only run straight through once.

Key idea: branches and jumps change flow by overwriting the program counter, which is how loops and decisions are built.

Pipelining: overlapping the loop with itself

Running one instruction fully before starting the next wastes almost the whole machine: while the ALU works the fetch logic sits idle, and while memory is accessed the ALU sits idle. The fix is the one a laundromat uses - start the next load washing while the first is in the dryer. Split the cycle into stages and let a different instruction occupy each. The classic split has five: IF (instruction fetch), ID (decode and read registers), EX (execute), MEM (access data memory), and WB (write back).

cycle:      1     2     3     4     5     6     7
i1:        IF    ID    EX    MEM   WB
i2:              IF    ID    EX    MEM   WB
i3:                    IF    ID    EX    MEM   WB

3 instructions, unpipelined: 3 x 5 = 15 stage-times
3 instructions, pipelined:   5 + (3 - 1) = 7 cycles
n instructions, pipelined:   5 + (n - 1) cycles  ->  about 1 per cycle for large n

The pipeline does not make any single instruction faster - an instruction still takes five stages from entry to exit. It raises throughput, the number finished per unit time. In the performance equation of the last lesson, pipelining attacks CPI, driving it toward 1.

The speedup is never the full 5x, and the reason is Lesson 8's timing budget. Suppose an unpipelined design needs 800 ps per instruction. Split into five equal 160 ps stages, each stage still pays about 30 ps of clock-to-Q, setup, and skew, so the clock period is 190 ps, not 160, and the speedup is 800 / 190 = 4.2x. Split into ten stages and that overhead is paid ten times, which is why deeper is not automatically better.

Three ways a pipeline goes wrong

Overlapping instructions creates conflicts that sequential execution never had. These are the hazards, and every real processor spends serious hardware on them.

A structural hazard is two instructions wanting the same hardware in the same cycle. With a single memory port, the IF of one instruction would collide with the MEM of another - which is why essentially every machine has separate first-level instruction and data caches.

A data hazard is an instruction needing a result that is still in flight.

add  x1, x2, x3      writes x1 during WB, in cycle 5
sub  x4, x1, x5      needs x1 during EX, in cycle 4    <- one cycle too early

Waiting would cost two stall cycles. Instead the hardware uses forwarding: the ALU result exists at the end of EX in cycle 3, long before write-back, so a multiplexer routes it directly from the pipeline register into the next instruction's ALU input, with no stall at all. Forwarding cannot rescue every case. A load produces its value at the end of MEM and the next instruction needs it in EX one cycle earlier, so a load-use hazard costs one unavoidable stall. Compilers try to slot an unrelated instruction into that gap, which is one concrete reason optimized code is reordered.

A control hazard is the pipeline not knowing which instruction comes next. A branch's outcome is not settled until EX, by which time IF and ID have already pulled in instructions that may be wrong, and branches are roughly one instruction in five. So processors predict: they guess the direction from that branch's history, keep fetching down the predicted path, and discard the work if the guess was wrong. Modern predictors exceed 95 percent accuracy on ordinary code. Put numbers on the residual cost - 20 percent branches, 5 percent of those mispredicted, 15 cycles to refill the pipeline - and the added CPI is 0.20 x 0.05 x 15 = 0.15, which is real but survivable. Now imagine the 31-stage pipeline of the later Pentium 4 designs, where a mispredict cost far more, and you can see why extreme depth went out of fashion along with the clock race.

Key idea: pipelining raises throughput rather than reducing latency, and its cost is the hazard-handling hardware - forwarding, stalls, and branch prediction - needed to preserve the illusion of one instruction at a time.

Speculation, and the security bill that came due

Branch prediction is one case of a general strategy: rather than waiting to find out, do the work now and undo it if the guess was wrong. Modern processors take this far. They execute instructions out of order as inputs become ready, run ahead down predicted paths, and keep a buffer that retires results in program order so the visible state always looks sequential. When speculation is wrong, the speculative results are discarded and the machine continues as if nothing happened.

Except that something did happen. Discarding the architectural state - registers and memory - does not undo the microarchitectural state, and any memory the speculative instructions touched has been pulled into the cache, where it stays. In January 2018 two groups published attacks built on exactly that gap. In Meltdown, a user program loads from kernel memory; on affected processors the permission check resolved late enough that the fetched value was already feeding dependent speculative instructions, which used it to index an array. The fault then cancelled everything except the cache line that had been brought in. The attacker times each element of that array, finds the suspiciously fast one, and has recovered a byte of kernel memory. Repeat, and read the kernel a byte at a time. Spectre is subtler: the attacker trains a branch predictor so a victim process speculatively runs past its own bounds check with an attacker-chosen index, leaking through the same timing channel.

The conceptual lesson matters more than the mechanics. For decades, "the processor may do anything internally as long as the architectural result is correct" was treated as a complete specification. These attacks showed that timing is an output too, and an optimization invisible to correctness can be perfectly visible to an attacker with a stopwatch. The mitigations that followed cost measurable performance, which is the plainest possible statement that some of the speed gained since the 1990s had been borrowed against security.

Key idea: speculation rolls back architectural state but not microarchitectural traces, and cache timing turns those traces into a channel that leaks data across privilege boundaries.

Where people get stuck

• "Instructions and data are stored in separate memories." In the von Neumann model they share the same memory as numbers; the CPU tells them apart by context.
• "The whole program is loaded into the CPU at once." The CPU fetches one instruction at a time using the program counter; it does not hold the entire program internally.
• "The program counter only ever increments." Branches and jumps overwrite it, which is exactly how loops and conditionals redirect execution.
• "Decode and execute are the same step." Decode interprets the bits; execute performs the action. They are distinct phases of the cycle.
• "A pipeline makes each instruction faster." It does not. Each instruction still takes all the stages; the pipeline raises how many finish per second.
• "A deeper pipeline is always better." Each stage pays flip-flop overhead, and a deeper pipeline makes every branch mispredict more expensive.
• "Speculative work that is thrown away leaves no trace." It leaves the cache warmed, and Meltdown and Spectre are what that trace is worth to an attacker.

Recap

• The von Neumann model stores instructions and data together as numbers.
• The CPU loops through fetch, decode, and execute for every instruction.
• Fetch reads the instruction at the PC and advances the PC, which is why a branch must overwrite an already-updated PC.
• Decode interprets the bits and emits control signals but changes no data; execute carries out the operation.
• Branches and jumps overwrite the PC to create loops and decisions.
• Pipelining overlaps stages of consecutive instructions, driving CPI toward 1 and raising throughput by a factor a little below the stage count.
• Structural, data, and control hazards are handled by duplicated resources, forwarding and stalls, and branch prediction respectively.
• Speculation and out-of-order execution hide latency, but the microarchitectural traces they leave behind are a real security channel.

The simple loop at the top of this lesson is still an accurate description of what a program means. Everything after it - overlap, reordering, guessing - exists to make that meaning arrive faster while pretending nothing changed. Most of modern architecture is the maintenance of that pretence.

Sources

1. Patterson, D. A., & Hennessy, J. L. (2020). The processor: Pipelining and hazards. In Computer organization and design RISC-V edition: The hardware software interface (2nd ed., ch. 4.5-4.9). Morgan Kaufmann. find source ↗
2. Terman, C., & Ward, S. (2017). 6.004 Computation structures (Chapter 12: Pipelining the processor). MIT OpenCourseWare. ocw.mit.edu
3. Kocher, P., Horn, J., Fogh, A., Genkin, D., Gruss, D., Haas, W., Hamburg, M., Lipp, M., Mangard, S., Prescher, T., Schwarz, M., & Yarom, Y. (2019). Spectre attacks: Exploiting speculative execution. 2019 IEEE Symposium on Security and Privacy. spectreattack.com
4. Lipp, M., Schwarz, M., Gruss, D., Prescher, T., Haas, W., Fogh, A., Horn, J., Mangard, S., Kocher, P., Genkin, D., Yarom, Y., & Hamburg, M. (2018). Meltdown: Reading kernel memory from user space. 27th USENIX Security Symposium. usenix.org
5. Linux kernel contributors. (n.d.). Spectre side channels. The Linux Kernel documentation. docs.kernel.org
6. Slotin, S. (n.d.). Pipeline hazards. Algorithms for Modern Hardware. en.algorithmica.org
7. Fog, A. (n.d.). The microarchitecture of Intel, AMD and VIA CPUs. Technical University of Denmark. agner.org

A program that has been compiled is a file full of 32-bit numbers. Nothing marks them as instructions; the only thing that makes them instructions is that the program counter eventually points at them. In this lesson you will take one of those numbers apart field by field, and see precisely how a line of readable text becomes a pattern of bits the decoder can pull back into control signals.

The big picture

The CPU only understands numbers, but humans cannot comfortably write raw numeric instructions. Assembly language is the thin, readable layer that names each machine instruction. This lesson shows how assembly maps one-to-one onto machine code, how the bits of a real instruction are laid out, and how a high-level line of code becomes several machine instructions.

Two forms of the same instruction

Machine code is the actual binary an instruction is stored as: an opcode (a code for the operation) plus operands (which registers or values it uses), all packed into a fixed number of bits. Assembly language is a human-readable text version of exactly those instructions, using short names called mnemonics like ADD, LOAD, and BEQ. Each assembly line usually corresponds to a single machine instruction, so assembly is essentially machine code with the numbers spelled as words.

The tool that translates assembly into machine code is an assembler. Think of assembly as the sheet music and machine code as the exact finger positions: the same performance, one written for people and one for the instrument.

Key idea: assembly is a readable, near one-to-one text form of the binary machine code the CPU runs.

Anatomy of an instruction

A simple instruction like "add register 1 and register 2, put the result in register 3" is encoded as fields inside one machine word:

Field	Meaning	Example
Opcode	which operation	ADD
Destination	where the result goes	R3
Source 1	first operand register	R1
Source 2	second operand register	R2

In assembly this reads as ADD R3, R1, R2. The assembler replaces ADD with its numeric opcode and each register name with its number, then packs the fields into bits. The decode phase you saw earlier is simply the CPU pulling those fields back apart.

Worked example: encoding a real instruction

Abstract fields become much more convincing with a real instruction set. RISC-V is a good one to learn on because its encodings are regular and published openly. A register-to-register operation uses the R-type format, which divides the 32 bits like this.

bits:   31-25     24-20   19-15   14-12   11-7    6-0
field:  funct7    rs2     rs1     funct3  rd      opcode
        7 bits    5       5       3       5       7

Now encode add x5, x6, x7, meaning "put the sum of registers 6 and 7 into register 5". For an add, the opcode is 0110011, funct3 is 000, and funct7 is 0000000. The register numbers 5, 6, and 7 become 5-bit binary values.

funct7  = 0000000
rs2     = 00111   (x7)
rs1     = 00110   (x6)
funct3  = 000
rd      = 00101   (x5)
opcode  = 0110011

concatenate: 0000000 00111 00110 000 00101 0110011
as 32 bits:  0000 0000 0111 0011 0000 0010 1011 0011
in hex:      0x007302B3

That hexadecimal number is what sits in the file. Disassembly is the same operation run backwards: take the low seven bits to get the opcode, look up which format that opcode uses, slice out the other fields, and print the mnemonic.

Two design choices in that layout are worth noticing, because they are the difference between an instruction set that pipelines well and one that does not. First, every instruction is exactly 32 bits, so the fetch stage always knows where the next instruction begins and can fetch several at once - x86, whose instructions run from 1 to 15 bytes, must partially decode an instruction before it knows where the following one starts, which is a genuine cost paid on every fetch. Second, rs1, rs2, and rd sit at fixed bit positions across all formats that use them. That lets the processor start reading registers before it has finished working out what the instruction is, since the register numbers are in the same place regardless. Regularity is not tidiness; it is speed.

Why there are several formats

Not every instruction needs three registers. A load needs one register, one destination, and a constant offset; a branch needs two registers and a target. RISC-V therefore defines a small family of formats - R for register-register, I for immediates and loads, S for stores, B for branches, U and J for large constants and jumps - all 32 bits wide, differing in how the bits not used for registers are spent. Constants embedded in an instruction are called immediates, and their size is a hard limit: an I-type immediate is 12 bits, so it covers -2048 to +2047, and any larger constant must be built in two instructions. This is why compiled code sometimes contains a pair of instructions where you expected one.

Addressing modes: how an instruction names its data

An operand can be reached in several ways, and the set a machine offers is its addressing modes. Four cover most of what you will see.

• Register: the value is in a register, named by a 5-bit field. Fastest, and the only mode arithmetic uses on a load-store machine.
• Immediate: the value is a constant inside the instruction itself, as in addi x5, x6, 100.
• Base plus offset: the address is a register plus a constant, as in lw x5, 8(x6). This is how structure fields and array elements are reached, and it is the reason the ALU computes addresses as well as arithmetic.
• PC-relative: the target is the current PC plus a constant, used by branches. Because the offset is relative, the same machine code works wherever the operating system loads it, which is what makes position-independent code possible.

Key idea: an instruction encoding is a negotiated budget of 32 bits, and the format zoo exists because different instructions need to spend those bits on different things.

Instruction types

Most instruction sets have a few families:

• Arithmetic and logic, such as ADD, SUB, AND, OR, which operate on registers.
• Data transfer, such as LOAD and STORE, which move values between registers and memory.
• Control flow, such as BEQ (branch if equal) and JMP (jump), which change the program counter.

These three families are enough to express any program, which is why real instruction sets, though larger, are built around them.

Key idea: instructions fall into arithmetic/logic, data transfer, and control flow families.

From high-level code to assembly

A single line in a language like C or Python expands into several machine instructions, because each machine instruction does only one tiny thing. Take the statement c = a + b where a, b, and c live in memory. A compiler might turn it into:

1. LOAD R1, a (bring a from memory into R1)
2. LOAD R2, b (bring b into R2)
3. ADD R3, R1, R2 (add them in the ALU)
4. STORE R3, c (write the result back to memory)

One friendly line became four instructions: two loads, an add, and a store. This is the general pattern. High-level code is compact because each statement hides a sequence of small hardware steps, and the compiler is what unfolds it.

Compiled versus interpreted, briefly

A compiler translates an entire high-level program into machine code ahead of time, producing a file the CPU runs directly. An interpreter instead reads the high-level program and carries out its meaning step by step at run time, without producing a standalone machine-code file. Compiled programs usually run faster; interpreted ones are often easier to develop and move between machines. Either way, what ultimately executes on the hardware is machine instructions.

Key idea: one high-level statement becomes several machine instructions, produced by a compiler ahead of time or driven by an interpreter at run time.

The instruction set as a contract

The instruction set architecture is the promise a processor family makes to software: these instructions exist, these registers exist, memory behaves this way. It is deliberately separate from how any particular chip implements it. That separation is why a program compiled in 2005 still runs on a processor designed in 2025, why AMD and Intel chips run the same binaries despite sharing no circuitry, and why Apple could switch its Macs to a different instruction set and translate old binaries to keep them working.

Above the instruction set sits a second agreement, the application binary interface, which fixes the conventions the hardware does not: which registers carry arguments, which a called function may destroy, how the stack is laid out. Nothing in the silicon enforces it. It is a treaty among compilers, and it is why code from two different compilers can call into each other at all. Lesson 14 works through the stack side of that treaty in detail.

If you want to see all of this rather than take it on faith, compile a small function with optimizations on and read the assembly - modern tools will show you source and generated instructions side by side. It is usually a surprise. Loops get unrolled, multiplications by constants turn into shifts and adds, and whole variables vanish because the compiler proved nothing observable depended on them. Reading that output once teaches more about what your machine actually does than a chapter of description.

Where people get stuck

• "Assembly is a high-level language." Assembly is low level and maps almost one-to-one to machine code; it is not abstract like C or Python.
• "One line of C equals one machine instruction." A single high-level statement typically compiles into several machine instructions.
• "The CPU runs assembly directly." The CPU runs binary machine code; an assembler must first translate the assembly text.
• "Interpreted code never becomes machine instructions." The interpreter itself is machine code, and it drives the hardware to carry out each step.
• "Any constant can go inside an instruction." Immediates have a fixed bit width. A 12-bit RISC-V immediate holds -2048 to +2047; anything bigger takes two instructions to build.
• "Optimized assembly should look like my source code." It usually does not. The compiler is required to preserve observable behaviour, not structure.

Recap

• Machine code is binary: an opcode plus operands packed into bits.
• Assembly is a readable, near one-to-one text form of machine code, using mnemonics.
• An assembler translates assembly into machine code, and disassembly runs the same field slicing backwards.
• A RISC-V R-type instruction spends its 32 bits on funct7, rs2, rs1, funct3, rd, and opcode, so add x5, x6, x7 is 0x007302B3.
• Fixed width and fixed field positions let a pipeline fetch and read registers before decoding finishes.
• Several formats exist because different instructions need to spend their bits differently, and immediates are limited by their field width.
• Addressing modes - register, immediate, base plus offset, and PC-relative - are the ways an instruction names its data.
• Instructions come in arithmetic/logic, data transfer, and control flow families.
• One high-level statement expands into several machine instructions; compilers translate ahead of time and interpreters at run time.
• The instruction set is a contract between hardware and software, and the ABI is a second contract among compilers on top of it.

The single most useful habit from this lesson is to stop treating compiled output as opaque. When performance or behaviour surprises you, look at the instructions. They are only fields in a 32-bit word, and you now know how to read them.

Sources

1. Patterson, D. A., & Hennessy, J. L. (2020). Instructions: Language of the computer. In Computer organization and design RISC-V edition: The hardware software interface (2nd ed., ch. 2). Morgan Kaufmann. find source ↗
2. Bryant, R. E., & O'Hallaron, D. R. (2016). Machine-level representation of programs. In Computer systems: A programmer's perspective (3rd ed., ch. 3). Pearson. find source ↗
3. RISC-V International. (n.d.). Ratified specifications (RISC-V unprivileged ISA, instruction formats). riscv.org
4. RISC-V International. (n.d.). RISC-V instruction set manual [Source repository]. GitHub. github.com
5. Intel Corporation. (n.d.). Intel 64 and IA-32 architectures software developer's manual. cdrdv2.intel.com
6. Cloutier, F. (n.d.). x86 and amd64 instruction reference. felixcloutier.com
7. Godbolt, M. (n.d.). Compiler Explorer. godbolt.org

For most programs written today, the processor is not the bottleneck. It spends a large share of its time waiting for memory, and the fraction has been growing for thirty years. Two loops that perform identical arithmetic can differ in runtime by a factor of ten purely because of the order in which they touch memory. This lesson is about why that gap exists and what to do about it, and it is probably the single most practically useful lesson in the course.

The big picture

Fast memory is expensive and small; big memory is cheap and slow. Computers get the best of both by stacking several kinds of memory into a hierarchy and keeping the data you are likely to need close by. This lesson explains that hierarchy, the pattern called locality that makes it work, and the concrete numbers that turn locality from a slogan into an engineering tool.

The speed-versus-size tradeoff

No single memory technology is both huge and instant. Registers are lightning fast but there are only a few dozen. Main memory (RAM) holds gigabytes but takes far longer to reach. Disks and solid-state drives store terabytes yet are slower still. The memory hierarchy arranges these levels from small-and-fast at the top to large-and-slow at the bottom, so the CPU usually finds what it needs near the top.

Level	Rough size	Rough speed
Registers	a few hundred bytes	fastest
L1 cache	tens of kilobytes	very fast
L2 / L3 cache	hundreds of KB to tens of MB	fast
Main memory (RAM)	gigabytes	moderate
Disk / SSD	terabytes	slow

A good analogy is your desk. The papers in your hand are registers; the few on the desktop are cache; the filing cabinet across the room is RAM; the archive in the basement is disk. You keep what you are using within arm's reach and fetch the rest only when needed.

Key idea: the memory hierarchy stacks small-fast memory over large-slow memory so most accesses hit the fast levels.

The numbers, and why they are shocking

"Slower" is easy to nod at and easy to underestimate. Here are representative latencies for a desktop processor running around 3 GHz, where one clock cycle is about a third of a nanosecond. The right-hand column rescales everything so that an L1 hit takes one second, which is the only way most people manage to feel the difference.

Level	Typical latency	In cycles	If L1 took 1 second
Register	immediate	0	instant
L1 cache	about 1.3 ns	4	1 second
L2 cache	about 4 ns	12	3 seconds
L3 cache	about 13 ns	40	10 seconds
Main memory (DRAM)	about 80 ns	250	1 minute
NVMe SSD	about 100 us	300,000	21 hours
Hard disk seek	about 10 ms	30,000,000	3 months

Read the last column again. Going to main memory is not "a bit slower" than a cache hit; on human timescales it is the difference between answering from memory and going to look something up. And that is why the hierarchy is not a nicety - it is the only reason a fast processor is worth building.

The gap also grew on purpose, or at least inevitably. Between roughly 1985 and 2005, processor speed improved by something like 50 percent per year while DRAM latency improved by around 7 percent per year. Memory bandwidth improved far more than latency did, because it is easy to widen a bus and hard to make a capacitor discharge faster. Architects have been compensating for that divergence ever since, and the name for the problem is the memory wall.

Key idea: the cost of a memory access spans seven orders of magnitude, and processor speed outran DRAM latency for two decades, which is why so much of a modern chip is cache.

Why it works: locality

The hierarchy would be useless if programs accessed memory randomly. Luckily they do not; real programs show locality of reference, meaning their accesses cluster in predictable ways. There are two flavors:

• Temporal locality: if you use a piece of data now, you are likely to use it again soon. A loop counter is touched every iteration. The rule of thumb is "recently used, soon reused."
• Spatial locality: if you use one location, you are likely to use nearby locations soon. Walking through an array touches address after address in order. The rule of thumb is "near what you used, used next."

Because of locality, keeping recently and nearby data in fast memory pays off almost all the time.

Key idea: programs reuse recent data (temporal) and neighboring data (spatial), which is why caching works.

Blocks: moving data in chunks

To exploit spatial locality, memory does not move one byte at a time between levels; it moves fixed-size blocks (also called lines), often 64 bytes. When the CPU asks for one byte that is not in cache, the whole surrounding block is pulled up, on the bet that the neighbors will be wanted soon. It is like grabbing a whole folder from the cabinet instead of a single sheet, because you will probably read the pages around it too.

There is a hardware reason as well as a statistical one, and it explains why the line size is 64 bytes rather than 4. A DRAM read is not one operation but two: the chip must first activate a whole row of thousands of bits into a set of sense amplifiers, which is the slow part, and only then read columns out of that open row, which is fast. Having paid tens of nanoseconds to open the row, taking a single word and closing it again would waste almost all of the cost. Transferring 64 bytes instead of 8 barely lengthens the operation, so the marginal bytes are nearly free. The cache line size is essentially the point where "free extra bytes" stops being true, balanced against the waste of loading neighbours you never use. A larger line captures more spatial locality but pollutes the cache when access is scattered.

Worked example: the same loop, two orders

Locality is not just hardware trivia; it changes how fast your code runs. Sum a 1024 by 1024 array of 4-byte integers, which is 4 MB in total, laid out row by row in memory. A 64-byte line holds 16 integers.

Row-major traversal (following the layout):
    first access to a row brings in a line of 16 ints
    the next 15 accesses hit
    misses = 1,048,576 / 16 = 65,536
    at ~80 ns per miss  ->  about 5 ms of memory stall

Column-major traversal (against the layout):
    consecutive accesses are 1024 ints = 4096 bytes apart
    every access lands on a different line, and by the time the
    loop returns to that line it has been evicted
    misses = 1,048,576
    at ~80 ns per miss  ->  about 84 ms of memory stall

Identical arithmetic. About 16x the memory traffic.

In practice the gap is often worse than 16x, because the strided version also misses in the translation lookaside buffer you will meet in Lesson 17, and because the hardware prefetcher can recognize a sequential pattern and fetch ahead of a row-major loop but not a scattered one. The lesson generalizes: iterate over data in the order it is stored.

Writing for the hierarchy

Three techniques follow directly from everything above, and they are worth knowing by name.

• Blocking, or tiling. If a computation touches more data than fits in cache, break it into tiles small enough to fit and finish each tile completely before moving on. Matrix multiplication is the standard example, where blocking can improve performance several-fold with no change to the arithmetic performed.
• Layout choice. An array of structures puts unrelated fields on the same line; a structure of arrays keeps each field contiguous. If a loop reads one field of every element, the second layout can cut memory traffic by the ratio of the structure size to the field size.
• Predictable access. Hardware prefetchers detect sequential and fixed-stride patterns and start fetching before you ask. Pointer chasing through a linked list defeats them completely, which is why an array of values often beats a linked structure even when the algorithm looks worse on paper.

Key idea: arranging your data accesses to follow locality can make identical computations run much faster, and the wins come from layout and traversal order rather than from cleverer arithmetic.

Where people get stuck

• "More RAM automatically makes a program faster." Speed depends on where data sits in the hierarchy and on locality, not just total capacity.
• "Cache moves single bytes." Data moves in blocks (often 64 bytes) to exploit spatial locality.
• "Temporal and spatial locality are the same." Temporal is reusing the same location soon; spatial is using nearby locations soon.
• "Access order does not affect performance." Traversing data against its memory layout wastes cached blocks and can be several times slower.
• "The algorithm with fewer operations is faster." Not if it touches memory unpredictably. A linear scan of an array often beats an asymptotically better structure that chases pointers.
• "DRAM got faster along with processors." Bandwidth did; latency barely moved. That divergence is the memory wall.

Recap

• Faster memory is smaller and pricier, so computers stack levels into a hierarchy.
• The levels run registers, caches, RAM, then disk, from fast-small to slow-large, spanning about seven orders of magnitude in latency.
• Locality of reference makes the hierarchy effective.
• Temporal locality reuses recent data; spatial locality uses nearby data.
• Memory moves in 64-byte lines rather than words because opening a DRAM row is the expensive part and the extra bytes come almost free.
• Traversing a 2D array along its layout costs roughly one sixteenth the misses of traversing across it, for identical arithmetic.
• Blocking, layout choice, and predictable strides are the practical levers, and they matter more than micro-optimizing arithmetic.

When a program is slower than it should be, the first question worth asking is no longer "how many operations does this do" but "how many cache lines does this touch, and in what order". That reframing is what the rest of this module equips you to answer.

Sources

1. Patterson, D. A., & Hennessy, J. L. (2020). Large and fast: Exploiting memory hierarchy. In Computer organization and design RISC-V edition: The hardware software interface (2nd ed., ch. 5). Morgan Kaufmann. find source ↗
2. Bryant, R. E., & O'Hallaron, D. R. (2016). The memory hierarchy. In Computer systems: A programmer's perspective (3rd ed., ch. 6). Pearson. find source ↗
3. Hennessy, J. L., & Patterson, D. A. (2019). Memory hierarchy design. In Computer architecture: A quantitative approach (6th ed., ch. 2). Morgan Kaufmann. find source ↗
4. Drepper, U. (2007). What every programmer should know about memory. Red Hat. akkadia.org
5. Drepper, U. (2007). What every programmer should know about memory, part 1. LWN.net ↗. lwn.net
6. Slotin, S. (n.d.). RAM and CPU caches. Algorithms for Modern Hardware. en.algorithmica.org
7. Terman, C., & Ward, S. (2017). 6.004 Computation structures (Chapter 13: Caches). MIT OpenCourseWare. ocw.mit.edu

A cache has to answer one question in a fraction of a nanosecond: do I already have the bytes at this address? It cannot search. There is no time to compare an address against thousands of stored addresses. The entire design of a cache follows from that constraint, and once you see how an address is chopped into three fields, everything else - associativity, conflict misses, why a 2048-byte stride can destroy your performance - falls out as consequences.

The big picture

A cache is a small, fast memory that sits between the CPU and main memory and keeps copies of data the processor is likely to reuse. This lesson explains how a cache decides where to put a block, how we measure whether it is helping, and how to compute the average time a memory access really takes.

What a cache is

A cache holds recently and nearby used data close to the CPU so most requests can be answered quickly, without the long trip to main memory. When the CPU asks for an address, one of two things happens: a cache hit means the data is already in the cache and is returned fast; a cache miss means it is not, so the CPU must fetch the block from slower memory and place it in the cache for next time. The analogy from the last lesson holds: the cache is the small stack of papers on your desk, saving you trips to the filing cabinet.

Key idea: a hit is found-in-cache and fast; a miss means a slow trip to memory to fetch the block.

Measuring a cache: hit rate and miss rate

The hit rate is the fraction of accesses that are hits; the miss rate is the fraction that are misses. They always add to 1. If a program makes 1000 memory accesses and 950 are hits, the hit rate is 950 / 1000 = 0.95 (95%) and the miss rate is 50 / 1000 = 0.05 (5%). A small change in miss rate matters a lot because misses are so expensive.

Average memory access time

The single most useful cache formula is average memory access time (AMAT):

AMAT = hit time + (miss rate x miss penalty)

Here the hit time is how long a hit takes, and the miss penalty is the extra time a miss costs to fetch the block from the next level. Worked example: suppose the hit time is 1 nanosecond, the miss penalty is 100 nanoseconds, and the miss rate is 5% (0.05). Then:

AMAT = 1 + (0.05 x 100) = 1 + 5 = 6 nanoseconds.

Even though a miss costs 100 ns, because only 1 in 20 accesses misses, the average is just 6 ns. Now watch how sensitive this is: if the miss rate doubles to 10% (0.10), AMAT = 1 + (0.10 x 100) = 1 + 10 = 11 nanoseconds, nearly double. That is why shaving the miss rate is so valuable.

Key idea: AMAT equals hit time plus miss rate times miss penalty, so lowering the miss rate has an outsized effect.

How an address is split

The trick that makes a lookup fast is to let the address itself decide where a block may live. Split it into three fields, from the bottom up.

• The block offset, the low bits, says which byte inside the line you want. A 64-byte line needs 6 bits, because 2^6 = 64.
• The index, the next bits up, selects which cache set to look in. It is just the block number modulo the number of sets, which in binary costs nothing at all - you take the bits.
• The tag, everything left over, is stored alongside the data and compared against the address to confirm this really is the block you wanted.

Work a concrete case: a 32 KB direct-mapped cache with 64-byte lines, on a 32-bit machine. The cache holds 32768 / 64 = 512 lines, and direct-mapped means one line per set, so there are 512 sets.

offset bits = log2(64)  = 6
index bits  = log2(512) = 9
tag bits    = 32 - 9 - 6 = 17

Look up address 0x0000ABCD = 0000 0000 0000 0000 1010 1011 1100 1101

  block number = 0xABCD / 64 = 43981 / 64 = 687, remainder 13
  offset = 13                 (bits 5-0  = 001101)
  index  = 687 mod 512 = 175  (bits 14-6 = 010101111)
  tag    = 687 / 512  = 1     (bits 31-15)

The cache reads set 175, compares the stored tag with 1, and if they
match, returns byte 13 of that line. One index, one comparison.

That is the whole mechanism. No searching, one tag comparison, done in parallel with reading the data out so the answer is ready the moment the comparison resolves.

Where blocks go: cache mapping

A cache must decide where in its limited slots each memory block may live. Three schemes are common:

• Direct-mapped: each block can go in exactly one slot, chosen by part of its address. Simple and fast, but two hot blocks that map to the same slot keep evicting each other.
• Fully associative: a block may go in any slot. Flexible and fewer conflicts, but checking every slot is costly.
• Set-associative: a compromise where the cache is divided into small sets, and a block may go in any slot within its set. An "N-way" cache has N slots per set. This captures most of the benefit of full flexibility at reasonable cost, so it is what real CPUs use.

Replacement and writes

When a set is full and a new block arrives, the cache must evict one. A common replacement policy is least recently used (LRU), which throws out the block untouched for the longest time, betting on temporal locality. For writes, the cache either updates memory immediately (write-through) or marks the block dirty and writes it back only when evicted (write-back). Write-back reduces memory traffic, which is why it is common, at the cost of extra bookkeeping.

Key idea: set-associative caches with LRU balance conflict misses against cost, and write-back defers memory writes to cut traffic.

Worked example: tracing an access sequence

Take a deliberately tiny cache so the whole thing fits on a page: 4 lines of 16 bytes, direct-mapped. That gives 4 bits of offset and 2 bits of index, so the block number is the address divided by 16 and the set is that block number modulo 4. Run this sequence of byte addresses through it: 0, 4, 16, 32, 0, 64, 0, 16.

addr  block  set  tag   result                       set contents after
   0      0    0    0   MISS (compulsory), load       s0=b0
   4      0    0    0   HIT                           s0=b0
  16      1    1    0   MISS (compulsory), load       s0=b0 s1=b1
  32      2    2    0   MISS (compulsory), load       s0=b0 s1=b1 s2=b2
   0      0    0    0   HIT                           unchanged
  64      4    0    1   MISS (conflict), evicts b0    s0=b4 s1=b1 s2=b2
   0      0    0    0   MISS (conflict), evicts b4    s0=b0 s1=b1 s2=b2
  16      1    1    0   HIT                           unchanged

3 hits, 5 misses  ->  hit rate 3/8 = 37.5%

The last three lines are the interesting part. Blocks 0 and 4 are 64 bytes apart, and in a 4-set cache they land in the same set, so they evict each other repeatedly even though two other sets sit empty. This is thrashing, and it is entirely an artefact of the mapping.

Now rebuild the same 4 lines as a 2-way set-associative cache: 2 sets of 2 lines, so the set is the block number modulo 2. Blocks 0 and 4 both map to set 0 but can now coexist there.

addr  block  set  result                        set 0 (LRU order)
   0      0    0   MISS, load                     [b0]
   4      0    0   HIT                            [b0]
  16      1    1   MISS, load                     set 1: [b1]
  32      2    0   MISS, load                     [b0, b2]
   0      0    0   HIT                            [b2, b0]  (b0 most recent)
  64      4    0   MISS, LRU evicts b2            [b0, b4]
   0      0    0   HIT                            [b4, b0]
  16      1    1   HIT                            set 1: [b1]

4 hits, 4 misses  ->  hit rate 50%, with exactly the same capacity

Same number of bytes, same line size, better result - purely from giving each block two possible homes. That is the argument for associativity in one table, and it is why real first-level caches are typically 4-way or 8-way.

Naming the misses: the three Cs

The trace above showed two different reasons for a miss, and there are three in total. Learning the names is worth it because each has a different cure.

• Compulsory misses happen the first time a block is ever touched. Nothing in the cache design prevents them; longer lines and prefetching reduce their cost.
• Capacity misses happen because the working set is larger than the cache. Only a bigger cache, or restructuring the program to work on smaller tiles, will help.
• Conflict misses happen because too many active blocks map to the same set, as blocks 0 and 4 did. More associativity is the cure, and so is changing the stride - which is why padding an array's row length by one element sometimes produces a startling speedup, by shifting hot data off a shared set.

Two levels, one formula

Real machines have several cache levels, and AMAT nests neatly to describe them. If a miss in L1 is served by L2, the L1 miss penalty is simply L2's average access time.

AMAT = L1 hit + L1 miss rate x (L2 hit + L2 miss rate x memory penalty)

With L1 hit 1 cycle, L1 miss rate 5%, L2 hit 12 cycles,
L2 miss rate 40%, memory penalty 250 cycles:

    AMAT = 1 + 0.05 x (12 + 0.40 x 250)
         = 1 + 0.05 x (12 + 100)
         = 1 + 5.6 = 6.6 cycles

Without the L2 at all:
    AMAT = 1 + 0.05 x 250 = 13.5 cycles

The second-level cache halved the average access time while catching only 60 percent of what reached it. That asymmetry is the reason the hierarchy keeps getting deeper: each level only has to be better than the level below to earn its area.

One caution on the numbers. The 40 percent above is a local miss rate, measured against accesses that reach L2, not against all accesses. The corresponding global miss rate is 0.05 x 0.40 = 2 percent. Mixing the two is the most common arithmetic error in this topic, so always say which one you mean.

Where people get stuck

• "A bigger cache always means a higher hit rate." Size helps up to a point, but locality, block size, and associativity matter too; past a point returns shrink.
• "Hit rate and miss rate can both be high." They must sum to 1, so a 95% hit rate means a 5% miss rate.
• "A single miss barely matters." A miss can cost 100 times a hit, so even a small miss rate dominates the average access time.
• "Direct-mapped caches never conflict." Because each block has only one slot, two active blocks mapping to it repeatedly evict each other, a conflict miss.
• "The cache searches for my address." It cannot afford to. The index bits pick one set, and only the tags in that set are compared.
• "A local miss rate and a global miss rate are the same thing." A 40 percent L2 local miss rate behind a 5 percent L1 miss rate is a 2 percent global rate.

Recap

• A cache keeps likely-reused data near the CPU; a hit is fast, a miss fetches from slower memory.
• An address splits into tag, index, and block offset, so a lookup is one index followed by one tag comparison.
• Hit rate and miss rate sum to 1.
• AMAT = hit time + miss rate x miss penalty, it is very sensitive to miss rate, and it nests across cache levels.
• Mapping can be direct, fully associative, or set-associative; real CPUs use set-associative, and the worked trace shows why associativity beats the same capacity direct-mapped.
• Misses are compulsory, capacity, or conflict, and each has a different remedy.
• LRU replacement and write-back policies exploit locality and cut memory traffic.

Everything here is a consequence of one constraint: a cache must answer in a couple of cycles, so it indexes rather than searches. Keep that in mind and you can predict cache behaviour for a new access pattern without simulating it.

Sources

1. Patterson, D. A., & Hennessy, J. L. (2020). The basics of caches. In Computer organization and design RISC-V edition: The hardware software interface (2nd ed., ch. 5.3-5.4). Morgan Kaufmann. find source ↗
2. Bryant, R. E., & O'Hallaron, D. R. (2016). Cache memories. In Computer systems: A programmer's perspective (3rd ed., ch. 6.4). Pearson. find source ↗
3. Hennessy, J. L., & Patterson, D. A. (2019). Review of memory hierarchy. In Computer architecture: A quantitative approach (6th ed., appendix B). Morgan Kaufmann. find source ↗
4. Terman, C., & Ward, S. (2017). 6.004 Computation structures (Chapter 13: Caches). MIT OpenCourseWare. ocw.mit.edu
5. Slotin, S. (n.d.). Cache associativity. Algorithms for Modern Hardware. en.algorithmica.org
6. Drepper, U. (2007). What every programmer should know about memory. Red Hat. akkadia.org
7. University of California, Berkeley. (n.d.). CS 61C: Great ideas in computer architecture (machine structures). EECS Instructional Support. inst.eecs.berkeley.edu

Nothing in a processor knows what a function is. There is no call instruction that creates a scope, no hardware notion of a local variable, no built-in idea that one routine is nested inside another. All of that is a convention, agreed between compilers and implemented with one register and some arithmetic. This lesson takes that convention apart, and then shows what happens when a program violates it.

The big picture

Programs are built from functions that call other functions, which call still others. The CPU keeps track of all these nested calls using a simple structure in memory called the stack. This lesson shows how the stack works, what a stack frame holds, how a function knows where to return, and why this arrangement is both extremely fast and a favourite target for attackers.

The stack: last in, first out

The stack is a region of memory used in a last in, first out (LIFO) way: the most recently added item is the first one removed. The everyday image is a stack of plates. You add a plate on top (push) and take one off the top (pop); you never pull from the middle. A special register called the stack pointer always marks the current top of the stack, so the CPU knows where to push and pop.

By convention on most machines the stack grows toward lower addresses, so pushing subtracts from the stack pointer and popping adds to it. The exact direction matters less than the LIFO discipline, which perfectly matches how function calls nest.

Key idea: the stack is last-in-first-out memory, and the stack pointer marks its current top.

Why calls need a stack

When function A calls function B, the CPU must remember where to come back to in A once B finishes. That memory is the return address. If B then calls C, another return address must be saved, and so on. Because calls nest and unwind in LIFO order (the most recently called function returns first), a stack is exactly the right tool. Each call pushes its bookkeeping on top; each return pops it off.

The stack frame

Every active function call gets its own stack frame (also called an activation record): a block on the stack holding everything that call needs. A frame typically stores:

• the return address, so control can jump back to the caller;
• the function's local variables;
• saved copies of registers the function must not clobber;
• space for arguments passed to functions it calls in turn.

When the function returns, its whole frame is popped in one motion by restoring the stack pointer, which instantly frees all its locals. This is why local variables vanish when a function ends: their storage is simply reclaimed off the stack.

Key idea: each call pushes a stack frame holding its return address and locals, and returning pops the frame to reclaim that space.

Walking through nested calls

Suppose main calls A, and A calls B. The stack builds up and unwinds like this:

1. main is running; its frame is on the stack.
2. main calls A: push A's frame (including the address in main to return to). The stack now holds main, then A on top.
3. A calls B: push B's frame (including the address in A to return to). Stack holds main, A, B.
4. B finishes: pop B's frame and jump to the saved return address back in A. Stack holds main, A.
5. A finishes: pop A's frame and return into main. Stack holds main again.

The frames appear and disappear in perfect LIFO order, which is why the single stack pointer is enough to manage arbitrarily deep nesting.

Watching the stack pointer move

Put addresses on that walkthrough and the mechanism stops being abstract. Suppose the stack pointer holds 0x7FFFF000 when main begins, main needs 32 bytes of frame, A needs 48, and B needs 16. Remember that the stack grows downward.

event                       stack pointer      live frames
main begins                 0x7FFFF000         -
main prologue: sp -= 0x20   0x7FFFEFE0         main
main calls A
A prologue:    sp -= 0x30   0x7FFFEFB0         main, A
A calls B
B prologue:    sp -= 0x10   0x7FFFEFA0         main, A, B
B epilogue:    sp += 0x10   0x7FFFEFB0         main, A
A epilogue:    sp += 0x30   0x7FFFEFE0         main
main epilogue: sp += 0x20   0x7FFFF000         -

Notice that freeing B's 16 bytes of locals is a single addition. There is no free list, no bookkeeping, no search for a block of the right size. That is why stack allocation is effectively free and heap allocation is not, and it is also why the top of the stack is almost always sitting in the first-level cache: the same few hundred bytes are reused by every call the program makes.

The prologue and epilogue, in instructions

Those sp adjustments are real instructions the compiler emits at the top and bottom of every non-trivial function. In RISC-V they look like this.

funcA:
    addi sp, sp, -32       # open a 32-byte frame
    sd   ra, 24(sp)        # save the return address
    sd   s0, 16(sp)        # save a callee-saved register we intend to use
    ...                    # body: locals live at 0(sp) and 8(sp)
    ld   s0, 16(sp)        # restore what we promised to preserve
    ld   ra, 24(sp)
    addi sp, sp, 32        # close the frame
    ret                    # jump to the address in ra

The ra register holds the return address, written automatically by the call instruction. A leaf function - one that calls nothing - can skip saving it entirely, which is a small but real reason short helper functions are cheap.

The calling convention

For two separately compiled functions to call each other, they must agree on more than the stack pointer. That agreement is the calling convention, part of the application binary interface, and it answers questions the hardware leaves open.

• Where arguments go. The first several arguments travel in designated registers - a0 through a7 in RISC-V - because registers are far faster than memory. Anything beyond that spills onto the stack.
• Where the result goes. Back in a0.
• Who preserves what. Callee-saved registers must hold the same value when a function returns as when it was entered, so a function that wants to use one must save and restore it. Caller-saved registers may be destroyed by any call, so a caller that still needs their contents must stash them first. Splitting the registers between the two categories lets each side avoid saving things nobody cares about.

None of this is enforced by hardware. A hand-written assembly routine that ignores the convention will link and run, and will corrupt its caller in ways that are extremely unpleasant to debug. The convention is a treaty, and the compiler keeps it on your behalf.

When the stack runs out

The stack has a limited size. If functions nest too deeply, most often through recursion that never stops, the stack keeps growing until it overruns its bounds. This is a stack overflow, and it typically crashes the program. It is the hardware's way of saying there were too many unfinished calls piled up at once. Correct recursion avoids this by always making progress toward a base case, so frames get popped as fast as they are pushed.

The limit is smaller than people expect. A typical Linux process gets 8 megabytes of stack by default, and a thread often gets less. A recursive function with a 64-byte frame therefore reaches roughly 130,000 levels deep before it dies, which sounds like plenty until you recurse over a list of a million items. Some languages avoid the problem for the special case where the recursive call is the very last thing a function does: a tail call can reuse the current frame instead of pushing a new one, turning recursion into a loop. Whether you get that optimization depends on your language and compiler, not on the hardware.

Key idea: the stack is finite, so unbounded call nesting such as runaway recursion causes a stack overflow.

Why attackers love the stack

Look again at the frame layout: a function's local buffer sits in the same frame as the saved return address. If the code writes past the end of that buffer - reading, say, 200 bytes of input into an 80-byte array - the extra bytes run straight over the saved return address. When the function executes its ret, the processor jumps wherever those bytes now say. This is the stack buffer overflow, the technique behind the Morris worm in 1988 and an enormous share of remote code execution vulnerabilities since.

The response has been layered, and every layer is worth recognizing because you will see all of them mentioned in build flags and security advisories.

• A stack canary is a random value placed between the locals and the saved return address at function entry and checked before returning. An overflow that reaches the return address must pass through the canary first, so the check fails and the program aborts instead of jumping.
• A non-executable stack marks stack pages as data-only, so injected instructions cannot run there. Attackers answered with return-oriented programming, stitching together fragments of code already present in the program.
• Address space layout randomization shifts the stack, heap, and libraries to different addresses on each run, so an attacker cannot know what address to jump to.
• Memory-safe languages remove the class of bug entirely by checking bounds or by proving at compile time that no write can leave its buffer.

The reason this belongs in an architecture course rather than only a security one is that the vulnerability is not a bug in any particular program. It is a direct consequence of a design that stores control information and user data in the same downward-growing region, chosen because it is fast and simple. That is the trade the machine made, and defences have been paying interest on it ever since.

Where people get stuck

• "You can access any item in the stack directly, like an array." The stack discipline is LIFO: you push and pop from the top, though frames do let a function reach its own locals.
• "Local variables live somewhere permanent." Locals live in the call's stack frame and are reclaimed the moment the function returns.
• "The return address is stored in the function being called." The return address is pushed onto the stack as part of the call, not baked into the callee.
• "Stack overflow means the computer is out of RAM." It means the stack region's limit was exceeded, usually by too-deep nesting, even if plenty of other memory is free.
• "Stack allocation and heap allocation cost about the same." Stack allocation is one addition to a register. Heap allocation searches a data structure and must be freed explicitly.
• "The calling convention is enforced by the CPU." It is a compiler agreement. Breaking it produces silent corruption, not a hardware fault.

Recap

• The stack is last-in-first-out memory managed by the stack pointer, which moves by simple addition and subtraction.
• Calls nest and unwind in LIFO order, which is why a stack fits function calls.
• Each call gets a stack frame holding its return address, locals, and saved registers, opened by a prologue and closed by an epilogue.
• The calling convention fixes which registers carry arguments and results and which side is responsible for preserving each register.
• Returning pops the frame, reclaiming the call's local storage at essentially zero cost, and keeping the hot region of the stack in L1.
• The stack is finite - often 8 MB - so runaway recursion causes a stack overflow, and tail calls avoid the growth in the cases where a language supports them.
• Because return addresses share a frame with local buffers, overflowing a buffer can hijack control flow, which is why canaries, non-executable stacks, and address randomization exist.

The stack is the clearest example in this course of a convention that feels like a law of nature. It is fast because it is simple, it is exploitable for the same reason, and every defence built on top of it is an attempt to keep the simplicity while removing the consequence.

Sources

1. Patterson, D. A., & Hennessy, J. L. (2020). Supporting procedures in computer hardware. In Computer organization and design RISC-V edition: The hardware software interface (2nd ed., ch. 2.8). Morgan Kaufmann. find source ↗
2. Bryant, R. E., & O'Hallaron, D. R. (2016). Procedures; Out-of-bounds memory references and buffer overflow. In Computer systems: A programmer's perspective (3rd ed., ch. 3.7 and 3.10). Pearson. find source ↗
3. Terman, C., & Ward, S. (2017). 6.004 Computation structures (Chapter 8: Procedures and stacks). MIT OpenCourseWare. ocw.mit.edu
4. RISC-V International. (n.d.). RISC-V ELF psABI specification (register convention and stack frame layout). GitHub. github.com
5. MITRE Corporation. (n.d.). CWE-121: Stack-based buffer overflow. Common Weakness Enumeration. cwe.mitre.org
6. Carnegie Mellon University. (n.d.). 15-213: Introduction to computer systems. CMU School of Computer Science. cs.cmu.edu
7. Godbolt, M. (n.d.). Compiler Explorer (for viewing generated prologues and epilogues). godbolt.org

A processor running at 3 GHz completes an instruction in a third of a nanosecond. A key press takes about a tenth of a second. In the time between two keystrokes the CPU could execute several hundred million instructions. Almost every design decision in input and output follows from that mismatch: the machine must never stand still waiting, and it must be interruptible the instant something finally happens.

The big picture

A CPU that could only compute would be useless; it has to talk to keyboards, disks, networks, and screens. This lesson explains how the processor communicates with those devices and, crucially, how interrupts let a device grab the CPU's attention without the CPU wasting time constantly checking.

Talking to devices

Input and output (I/O) devices connect to the CPU through controllers, small circuits that manage a specific device and expose a set of registers the CPU can read and write. To send a character to a printer, for example, the CPU writes it into the controller's data register; to check if a key was pressed, it reads a status register.

The most common way to reach these registers is memory-mapped I/O, where device registers are assigned ordinary memory addresses, so the same load and store instructions that touch RAM also talk to devices. The CPU does not need special hardware for each gadget; it just reads and writes the right addresses.

Key idea: devices expose control and data registers, often at memory addresses, so ordinary loads and stores can drive them.

Those addresses need one property ordinary memory does not have: they must not be cached, and the compiler must not optimize accesses to them away. Reading a status register twice is not a redundant load - the value may have changed because the device changed it. This is what the volatile keyword exists for in C, and why the page tables of Lesson 17 mark device regions as uncacheable.

The bus, and how devices connect

The wires linking components are collectively the bus, traditionally three groups: address lines saying which location, data lines carrying the value, and control lines saying read or write and signalling completion. A single shared bus is easy to understand and was how early machines worked, but every device on it adds capacitance and every transfer excludes all others, so shared buses became the bottleneck.

Modern systems use point-to-point serial links instead. PCI Express gives each device its own set of lanes to a switch, so devices transfer in parallel and each link can be clocked far faster than a shared parallel bus ever could. The idea that "wider and parallel is faster" stopped being true once signal skew between parallel wires became the limiting factor, which is the same reason storage and displays moved to serial links too.

How slow is slow

The reason I/O needs special mechanisms is worth quantifying. Assume a 3 GHz processor, so one cycle is about 0.33 nanoseconds.

Event	Typical time	CPU cycles that fit inside it
L1 cache hit	1.3 ns	4
Main memory access	80 ns	about 250
NVMe SSD read	100 us	about 300,000
Network round trip in a datacentre	500 us	about 1,500,000
Hard disk seek	10 ms	about 30,000,000
Key press	100 ms	about 300,000,000

Spinning in a polling loop through 30 million cycles waiting for a disk is not a small inefficiency. It is throwing away the entire machine for the duration.

Polling: the busy way to wait

The simplest way for the CPU to know a device is ready is polling: repeatedly reading the device's status register in a loop until it shows "ready." Polling is easy to write, but it wastes the processor. Imagine repeatedly opening the mailbox every few seconds to see if mail arrived; you get nothing else done while you check. If a device is slow, like a disk, the CPU could spin through millions of pointless checks.

Interrupts: let the device call you

The better approach is the interrupt. Instead of the CPU asking over and over, the device signals the CPU only when it actually needs attention, for example when data has arrived. On receiving an interrupt, the CPU pauses whatever it is doing, saves its place, and jumps to a special routine called an interrupt handler (or interrupt service routine) that deals with the device. When the handler finishes, the CPU restores its saved state and resumes exactly where it left off. This is like leaving your mailbox alone and letting the doorbell ring when the mail actually arrives, so you can work until then.

The sequence for handling an interrupt is:

1. A device raises an interrupt signal.
2. The CPU finishes the current instruction, then saves its current state (such as the program counter and registers).
3. The CPU jumps to the handler for that interrupt.
4. The handler services the device, for instance copying in the arrived data.
5. The CPU restores the saved state and resumes the interrupted program.

Key idea: an interrupt lets a device notify the CPU on demand, so the processor does useful work instead of polling.

Finding the handler, and the wider family of exceptions

Step 3 above glosses over something: how does the CPU know which handler? Through an interrupt vector table, an array in memory - or a base register plus an offset - holding the address of a handler for each interrupt number. The device supplies its number, the processor indexes the table, and the jump is a single memory read away. This is a decoder and a table, exactly the pattern from Lesson 7.

The same machinery serves several kinds of event, and distinguishing them clears up a lot of confusion.

• An interrupt is asynchronous: it comes from outside, unrelated to whichever instruction happens to be executing. A network packet arriving, or the timer tick that lets the operating system regain control.
• An exception or fault is synchronous: a specific instruction caused it. Dividing by zero, or the page fault of Lesson 17. Because a particular instruction is responsible, the handler can fix the problem and re-run that instruction.
• A trap is a deliberate exception, raised by an instruction whose whole purpose is to enter the operating system. That is what a system call is, and it is why Lesson 16 can talk about crossing into kernel mode safely.

All three save state, consult a table, run privileged code, and return. One mechanism, three reasons to use it.

Handlers operate under real constraints. Interrupts are usually disabled or masked by priority while one is running, so a slow handler delays every other device, and time spent in a handler is time the interrupted program is not running. Operating systems therefore split the work: a short top half acknowledges the device and copies the minimum needed, and queues the real processing to run later with interrupts enabled. If you have ever seen advice that an interrupt handler must never block, this is why.

Moving big data efficiently: DMA

Even with interrupts, having the CPU copy every byte between a device and memory is wasteful for large transfers like reading a file. Direct memory access (DMA) solves this: a DMA controller moves a whole block of data between the device and memory on its own, then raises a single interrupt when the entire transfer is done. The CPU sets up the transfer and is then free to compute while the block moves in the background. It is the difference between carrying every grocery bag yourself and having them delivered, with one knock at the door when everything has arrived.

DMA introduces a problem worth naming, because it is the same problem multicore systems have. The controller writes straight into main memory, but the processor may still hold a stale copy of those addresses in its cache, or may hold modified data in cache that memory has not seen yet. Systems solve this either with hardware that snoops DMA traffic and invalidates the affected cache lines, or by requiring the driver to flush and invalidate explicitly around every transfer. That is exactly the coherence question Lesson 18 revisits between cores.

Key idea: DMA lets a controller transfer whole blocks without the CPU, interrupting only once when finished, at the cost of needing cache coherence with the transferred region.

When polling came back

The tidy story - polling is naive, interrupts are correct - was true for decades and is no longer the whole truth. An interrupt is not free: entering and leaving a handler costs on the order of a microsecond once you count saving state, the pipeline flush, and the damage done to caches and branch predictors by running unrelated code. When a hard disk took 10 milliseconds, that overhead was noise. An NVMe drive can complete a read in 10 microseconds and a fast network card can deliver millions of packets per second, and now the interrupt costs a serious fraction of the operation - and at high rates the machine can spend nearly all its time entering and leaving handlers, a failure mode with its own name, receive livelock.

So the pendulum swung partway back. Modern high-performance drivers use hybrid schemes: take one interrupt, then disable further interrupts and poll the device while work keeps arriving, re-enabling them only when the queue empties. Linux's networking stack has worked this way since the NAPI design, and storage interfaces offer polled completion modes for the same reason. The principle is not "interrupts good, polling bad" but "compare the cost of the notification with the cost of the operation", and that comparison changed when devices got fast.

Where people get stuck

• "Polling is more efficient than interrupts." Polling burns CPU time repeatedly checking; interrupts free the CPU until a device actually needs it.
• "An interrupt discards the running program." The CPU saves its state, runs the handler, then resumes the interrupted program right where it stopped.
• "Every byte of I/O must pass through the CPU." DMA moves whole blocks directly between device and memory, bypassing the CPU during the transfer.
• "Devices need special CPU instructions to talk to." With memory-mapped I/O, ordinary load and store instructions to device addresses suffice.
• "An interrupt is free." Entry, exit, and the cache and predictor damage cost around a microsecond, which is why very fast devices are often polled instead.
• "Interrupts and exceptions are different mechanisms." They share the save-state, vector, handle, return machinery. The difference is whether the cause was external or was a specific instruction.

Recap

• Devices connect through controllers exposing registers the CPU reads and writes, over buses that are now mostly point-to-point serial links.
• Memory-mapped I/O gives device registers addresses, so loads and stores drive them, provided those addresses are uncached and not optimized away.
• Device latencies span from microseconds to hundreds of milliseconds, which is millions of wasted cycles if the CPU waits.
• Polling checks a device in a loop and wastes CPU time.
• Interrupts let a device signal the CPU on demand; the CPU saves state, indexes a vector table, runs a handler, and resumes.
• Interrupts, exceptions, and traps share one mechanism and differ only in what triggered them.
• DMA transfers whole blocks without the CPU, interrupting once when complete, and requires cache coherence with the transferred buffer.
• For very fast devices, hybrid interrupt-then-poll schemes beat pure interrupts because notification overhead is no longer negligible.

The through-line is that I/O design is arithmetic about time. Compare how long the device takes with how long the notification costs, and the right mechanism picks itself - which is why the answer changed as devices got faster, and will change again.

Sources

1. Patterson, D. A., & Hennessy, J. L. (2020). Parallelism and I/O; storage and other topics. In Computer organization and design RISC-V edition: The hardware software interface (2nd ed., ch. 5.11 and appendix). Morgan Kaufmann. find source ↗
2. Bryant, R. E., & O'Hallaron, D. R. (2016). Exceptional control flow. In Computer systems: A programmer's perspective (3rd ed., ch. 8). Pearson. find source ↗
3. Tanenbaum, A. S., & Bos, H. (2015). Input/output. In Modern operating systems (4th ed., ch. 5). Pearson. find source ↗
4. Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. (n.d.). I/O devices. In Operating systems: Three easy pieces. University of Wisconsin-Madison. pages.cs.wisc.edu
5. Linux kernel contributors. (n.d.). Dynamic DMA mapping using the generic device. The Linux Kernel documentation. docs.kernel.org
6. Linux kernel contributors. (n.d.). How to write Linux PCI drivers. The Linux Kernel documentation. docs.kernel.org
7. Kerrisk, M. (n.d.). ioctl(2) - Linux manual page. man7.org

Right now your machine is probably running several hundred processes on a handful of cores. None of them was written to cooperate with the others, none was told when it would be paused, and any one of them could contain an infinite loop without freezing the system. That combination of illusions - unlimited CPUs, complete isolation, guaranteed interruptibility - is what an operating system sells, and this lesson is about how it delivers.

The big picture

One computer runs dozens of programs that all seem to go at once, even on a chip that can truly execute only a few instructions at a time. The operating system creates that illusion. This lesson explains what a process is, how a program crosses safely into the kernel, and how the operating system shares the CPU among many processes through scheduling.

What the operating system does

The operating system (OS) is the master program that manages the hardware and shares it safely among all the other programs. It decides which program runs, hands out memory, controls access to devices, and stops one program from trampling another. Think of the OS as the manager of a shared workshop: it owns the tools, schedules who uses them and when, and keeps everyone from colliding.

To do this the OS needs authority that ordinary programs lack, so hardware provides two privilege levels. In kernel mode the OS can do anything, including touching hardware directly. In user mode ordinary programs run with restrictions and must ask the OS for privileged services through a system call. This split protects the machine: a buggy application cannot directly seize a device or another program's memory.

Key idea: the OS manages and protects shared hardware, running privileged in kernel mode while applications run restricted in user mode.

How a system call actually works

The privilege split raises an obvious question: if user code cannot enter kernel mode, how does it ever ask for anything? Not by calling a kernel function - a plain jump would run kernel code at user privilege, which would be useless, or would let a program jump into the middle of a kernel routine, which would be catastrophic. The answer is the trap from the previous lesson.

1. The program puts a system call number in a designated register - "read", "write", "open" - along with its arguments.
2. It executes a special instruction (ecall on RISC-V, syscall on x86-64) whose only effect is to raise a trap.
3. The hardware switches to kernel mode and jumps to one fixed entry point chosen by the kernel, not by the caller. That single controlled door is the whole security argument.
4. The kernel switches to a per-process kernel stack, saves user state, checks that the call number is valid, validates every pointer argument, and dispatches through a table.
5. When the work is done, the kernel restores user state and executes a return-from-trap instruction that drops privilege and resumes the user program at the instruction after the call.

Notice how much of that is checking. The kernel cannot trust a single value the caller supplied: a pointer might address kernel memory, a length might overflow, a file descriptor might not belong to this process. Every one of those checks exists because somebody once found the vulnerability that came from omitting it.

Processes: a program in action

A process is a program that is actually running, together with all its state: its code, its data, its stack, and the current values in the CPU registers. The program on disk is a passive recipe; the process is the live cooking in progress. The OS keeps a record for each process, often called a process control block, storing everything needed to pause and later resume it, such as the saved program counter and registers.

At any moment a process is in a state such as running (currently using the CPU), ready (able to run, waiting its turn), or blocked (waiting for something like disk data). Processes move among these states as the OS manages them and as events occur. The transitions matter as much as the states, because each one is caused by something specific.

  ready  --- scheduler picks it --->  running
  running --- quantum expires,
              or a higher-priority
              process becomes ready --->  ready        (preemption)
  running --- issues a slow request --->  blocked      (voluntary)
  blocked --- the awaited event
              occurs (interrupt)   --->  ready
  running --- exits or is killed   --->  terminated

Two of those arrows deserve attention. A process never goes from blocked straight to running; it becomes ready and waits its turn, because the scheduler decides who runs, not the device that woke it. And the preemption arrow is only possible because a timer interrupt exists - without it, a process that never makes a system call could keep the CPU forever.

Sharing one CPU: the context switch

Because a single CPU core runs one process at a time, the OS creates the appearance of many at once by switching rapidly between them. Saving one process's state and loading another's is a context switch. The steps are: save the running process's registers and program counter into its control block, choose the next process, then load that process's saved state and let it run. Switches happen many times per second, far faster than you can notice, so several programs feel simultaneous. This time-sharing is why your music keeps playing while you type.

Context switches are not free; saving and restoring state takes time, so switching too often wastes effort. The OS balances responsiveness against this overhead.

How expensive, exactly? The direct cost - saving registers, swapping page tables, updating bookkeeping - is on the order of one to three microseconds. The indirect cost is usually larger and is invisible in that measurement: the incoming process finds the caches full of the outgoing process's data, the TLB entries wrong, and the branch predictors trained on somebody else's code. It then runs slowly for a while as it rebuilds that state, an effect sometimes called cache pollution. This is why scheduling quanta are measured in milliseconds rather than microseconds: at a few milliseconds, a couple of microseconds of switching overhead is well under one percent, and shorter quanta would spend a visible fraction of the machine on switching alone.

Key idea: a context switch saves one process and loads another, and doing this rapidly makes many programs appear to run at once - at a cost dominated by the cold caches the incoming process inherits.

Scheduling: who runs next

The part of the OS that decides which ready process runs next is the scheduler, and its policy is the scheduling algorithm. Different goals lead to different policies:

• First come, first served: run processes in arrival order. Simple, but a long job can make short ones wait a long time.
• Round robin: give each ready process a small slice of time called a time quantum, then move to the next, cycling around. This keeps the system responsive and shares the CPU fairly.
• Priority scheduling: run higher-priority processes first, useful when some tasks are more urgent than others.

A key distinction is preemptive versus non-preemptive scheduling. Under preemptive scheduling the OS can forcibly pause a running process, usually when its time quantum expires, and give the CPU to another. This relies on a hardware timer interrupt to regain control, ensuring no single program can hog the processor forever.

Key idea: the scheduler picks the next process by some policy, and preemptive scheduling uses a timer interrupt to stop any program from monopolizing the CPU.

Worked example: three policies, three answers

Policies sound similar until you compute what they do. Three jobs arrive together at time 0: job A needs 24 ms of CPU, job B needs 3 ms, job C needs 3 ms. Turnaround time is when a job finishes; waiting time is turnaround minus the work it actually needed.

First come, first served, in order A B C
    A finishes at 24, B at 27, C at 30
    waiting:     A 0,  B 24,  C 27      average wait  = 17.0 ms
    turnaround:  24, 27, 30             average turn  = 27.0 ms

Shortest job first, in order B C A
    B finishes at 3, C at 6, A at 30
    waiting:     B 0,  C 3,   A 6       average wait  =  3.0 ms
    turnaround:  3, 6, 30               average turn  = 13.0 ms

Round robin, quantum 4 ms, order A B C
    0-4 A, 4-7 B done, 7-10 C done, then A runs alone to 30
    waiting:     A 6,  B 4,   C 7       average wait  =  5.7 ms
    turnaround:  30, 7, 10              average turn  = 15.7 ms

Shortest job first wins on average waiting time, and that is not luck - it is provably optimal for that metric. It is also close to unusable on its own, for two reasons. It requires knowing how long each job will run, which nobody does, so real systems estimate from recent behaviour. And it can starve a long job indefinitely if short ones keep arriving.

Round robin lands between the two on both metrics, and buys something the averages do not show: B and C finished at 7 and 10 instead of 27 and 30, so an interactive task gets a response quickly even when a long job is running. That is why general-purpose systems favour round-robin-like policies. The quantum is the tuning knob - too long and the system feels sluggish, too short and switching overhead eats the machine.

What real schedulers do

Production schedulers combine these ideas rather than choosing among them. Linux's completely fair scheduler tracks how much CPU time each runnable task has received, weighted by priority, and always runs the one that has fallen furthest behind its fair share - which approximates round robin while automatically favouring tasks that block often, since a task that sleeps accumulates little runtime and therefore looks starved when it wakes. That single rule gives interactive processes good response times without any explicit rule about interactivity.

Multiple cores change the shape of the problem again. A single global queue would need a lock that every core contends for, so systems keep a run queue per core and periodically balance load between them. Moving a task to another core costs its cache warmth, so schedulers are reluctant to migrate, a preference called affinity. And on chips with fast and efficient cores of different designs, the scheduler must also decide which kind of core suits each task. Every one of these refinements is the same tension as before: fairness against throughput against locality.

Where people get stuck

• "A program and a process are the same thing." A program is passive code on disk; a process is that code actually running with its live state.
• "Multitasking on one core means truly simultaneous execution." A single core runs one process at a time; rapid context switching only makes it look simultaneous.
• "Applications can access hardware directly." User-mode programs must request privileged actions through system calls; only the kernel touches hardware freely.
• "Context switches are free." Saving and restoring state costs time, and the incoming process also inherits cold caches, which usually costs more than the switch itself.
• "A system call is just a function call into the kernel." It is a trap to one fixed entry point, followed by validation of every argument, precisely so it is not an ordinary call.
• "The fairest scheduler is the best one." Optimal average waiting time comes from running short jobs first, which is unfair by construction and can starve long jobs. Real policies trade the two deliberately.

Recap

• The OS manages and protects shared hardware, using kernel and user modes.
• A system call is a trap into one controlled entry point, where the kernel validates everything the caller supplied before acting.
• A process is a running program plus its state, tracked in a process control block.
• Processes are running, ready, or blocked, and each transition has a specific cause - a scheduler decision, a slow request, or an interrupt.
• A context switch saves one process and loads another; doing it rapidly time-shares the CPU, at a cost dominated by lost cache and TLB state.
• First come first served, shortest job first, and round robin give measurably different waiting and turnaround times on the same workload.
• The scheduler chooses the next process; preemptive scheduling uses a timer interrupt to stay in control, and multicore systems add per-core queues, load balancing, and affinity.

Notice how much of this rests on hardware from earlier lessons: privilege levels, the trap mechanism, the timer interrupt, and the cost of cold caches. An operating system is not built on top of the architecture so much as woven through it.

Sources

1. Tanenbaum, A. S., & Bos, H. (2015). Processes and threads. In Modern operating systems (4th ed., ch. 2). Pearson. find source ↗
2. Silberschatz, A., Galvin, P. B., & Gagne, G. (2018). Processes; CPU scheduling. In Operating system concepts (10th ed., ch. 3 and 5). Wiley. find source ↗
3. Bryant, R. E., & O'Hallaron, D. R. (2016). Exceptional control flow: Processes and system calls. In Computer systems: A programmer's perspective (3rd ed., ch. 8). Pearson. find source ↗
4. Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. (n.d.). Scheduling: Introduction. In Operating systems: Three easy pieces. University of Wisconsin-Madison. pages.cs.wisc.edu
5. Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. (n.d.). Mechanism: Limited direct execution. In Operating systems: Three easy pieces. University of Wisconsin-Madison. pages.cs.wisc.edu
6. Linux kernel contributors. (n.d.). CFS scheduler. The Linux Kernel documentation. docs.kernel.org
7. Kaashoek, F., & Morris, R. (2012). 6.828 Operating system engineering. MIT OpenCourseWare. ocw.mit.edu

Print the address of a variable in two programs running side by side and you may well see the same number twice. Neither program is wrong, and neither is looking at the other's data. Every address a program uses is a fiction maintained by hardware, translated on every single memory access, hundreds of millions of times a second, with an overhead small enough that you have never noticed it. That machinery is virtual memory, and it is arguably the most successful abstraction in computing.

The big picture

Every program acts as if it owns a clean, private, enormous memory, even though real RAM is shared and limited. That illusion is virtual memory. This lesson explains how the hardware and operating system translate each program's private addresses into real ones, what that costs, and why the scheme buys far more than just extra memory.

Two kinds of address

A virtual address is the address a program uses, drawn from its own private address space. A physical address is the real location in RAM. Virtual memory is the mechanism that maps virtual addresses to physical ones so that each program can pretend it has a large, contiguous memory starting at zero, regardless of where its data actually sits in RAM or how many other programs are running. It is like every guest in a hotel using room numbers 1, 2, 3 on their own floor, while the front desk quietly maps those to unique physical rooms in the building.

Key idea: programs use private virtual addresses that virtual memory translates into real physical addresses in RAM.

Pages and frames

To make mapping manageable, memory is divided into fixed-size chunks. A page is a fixed-size block of the virtual address space, commonly 4 kilobytes. A frame (or page frame) is a physical block of the same size in RAM. Virtual memory works by placing pages into frames, and it records where each page landed in a page table, one per process, that maps each virtual page number to the physical frame holding it.

Because pages and frames are the same size, any page can go in any free frame, which lets the OS scatter a program's memory wherever there is room while the program still sees it as continuous.

Translating an address

To turn a virtual address into a physical one, the hardware splits the address into a page number and an offset within the page. The page number is looked up in the page table to find the frame; the offset stays the same because it is just the position inside the block.

A small worked example with tiny numbers: suppose pages are 100 bytes (so the offset is the last two decimal digits) and virtual page 3 maps to frame 7. A virtual address of 342 splits into page 3 and offset 42. Page 3 lives in frame 7, so the physical address is frame 7 times 100 plus offset 42 = 700 + 42 = 742.

Now do it with realistic numbers, because the powers of two are what make the split free. With 4 KB pages, the offset needs log2(4096) = 12 bits, leaving the upper 20 bits of a 32-bit address as the virtual page number. No division is involved; the hardware simply takes the bits.

virtual address   0x00403ABC
                  = 0000 0000 0100 0000 0011 1010 1011 1100

  offset = low 12 bits  = 0xABC       (byte 2748 within the page)
  VPN    = high 20 bits = 0x00403     (virtual page 1027)

Suppose the page table says virtual page 0x00403 lives in frame 0x1F2.

  physical = (frame << 12) | offset
           = 0x1F2000 | 0xABC
           = 0x1F2ABC

The dedicated hardware that performs this lookup is the memory management unit (MMU). To keep it fast, the MMU caches recent translations in a translation lookaside buffer (TLB), so common addresses skip the page-table lookup.

Key idea: an address splits into a page number and offset; the page table maps the page to a frame while the offset is unchanged.

Why page tables are not flat

A flat page table sounds fine until you size it. A 32-bit address space with 4 KB pages has 2^20 = 1,048,576 pages, and at 4 bytes per entry that is a 4 MB table - per process. A hundred processes would spend 400 MB on tables alone, most of it describing pages that do not exist. For 64-bit address spaces the flat table is not merely wasteful, it is impossible.

The fix is a multi-level page table: a tree. The virtual page number is split into several fields, each indexing one level, and an entry is marked absent if that whole region of the address space is unused, which prunes the entire subtree below it. A process using a few megabytes then needs a handful of small tables instead of one enormous one. Real 64-bit machines use four or five levels, and the price is that a translation missing from the TLB requires walking every level - four or five dependent memory accesses to resolve one address.

What translation costs, and why huge pages exist

Four memory accesses per memory access would be catastrophic, which is why the TLB is not an optimization but a necessity. Put numbers on it. Say a TLB hit costs essentially nothing, adding 1 cycle, and a miss requires a page walk costing about 100 cycles.

effective translation cost = (hit rate x 1) + (miss rate x 100)

  at 99% hit rate:   0.99 x 1 + 0.01 x 100 = 1.99 cycles
  at 95% hit rate:   0.95 x 1 + 0.05 x 100 = 5.95 cycles
  at 90% hit rate:   0.90 x 1 + 0.10 x 100 = 10.9 cycles

The same brutal sensitivity as AMAT, for the same reason. And TLBs are small - a first-level TLB might hold 64 entries, which times 4 KB covers only 256 KB of memory at any moment. That is nothing next to a working set of hundreds of megabytes, and it is why traversing a large array with a big stride is punished twice: once in the cache, once in the TLB.

The standard remedy is a huge page. Map memory in 2 MB units instead of 4 KB and the same 64 entries cover 128 MB, a five-hundredfold increase in reach, with a shorter walk on a miss. Databases and virtual machine hosts enable huge pages for exactly this reason. The cost is granularity: 2 MB spent on a small object is mostly wasted, and building one needs contiguous physical memory, which is hard once memory is fragmented.

When a page is not in RAM: the page fault

Virtual memory can be larger than physical RAM because pages not currently needed are kept on disk. When a program accesses a page that is not in RAM, the MMU raises a page fault. The OS handles it by finding the page on disk, loading it into a free frame (evicting another page if necessary), updating the page table, and then restarting the instruction as if nothing happened. From the program's view the access simply worked, just a little slower that once. This is what lets a machine run programs whose combined memory needs exceed its RAM.

"A little slower" understates it by orders of magnitude. A memory access takes about 80 nanoseconds; a page fault served from an SSD takes around 100 microseconds and from a spinning disk around 10 milliseconds - a thousand to a hundred thousand times worse. A hit rate that would merely be embarrassing for a cache is catastrophic here. If the working set exceeds physical memory, pages are evicted just before they are needed again and the system enters thrashing, spending nearly all its time paging and almost none computing. Not every fault touches disk, though: many are minor faults for a fresh page that just needs zeroing, or a page already in memory but not yet mapped into this process.

Why virtual memory is worth it

Virtual memory buys three big things. First, isolation: each process has its own address space and cannot read or corrupt another's memory, since their virtual addresses map to different frames. Second, flexibility: a program need not fit in one contiguous stretch of RAM, and it can use more memory than physically exists. Third, simplicity for programmers: every program is written as if it starts at address zero with the whole space to itself, and the OS handles the messy reality. These benefits are why essentially all modern general-purpose systems use it.

Key idea: virtual memory provides isolation between programs, flexible use of RAM and disk, and a simple uniform view for every program.

The features that come for free once you have a mapping

Those three benefits are the textbook answer, and they undersell the mechanism badly. Once every access passes through a table you control, a series of otherwise difficult features become almost trivial.

• Protection per page. Each entry carries bits saying readable, writable, executable, and user-accessible. Marking code read-only and data non-executable, which blocks the injected-code attacks of Lesson 14, is a bit in a table.
• Sharing. Point two processes' page tables at the same frame and they share memory. A single copy of a system library serves every running program, which is why hundreds of processes fit in memory at all.
• Copy-on-write. When a process forks, do not copy its memory. Map both processes to the same frames, marked read-only, and copy a page only when one actually writes. Most forked processes immediately replace themselves with another program, so almost all the copying never happens.
• Memory-mapped files. Map a file into the address space and read it with ordinary loads, with the paging system fetching on demand. This is also how an executable is loaded: not read into memory, but mapped and faulted in as it runs.
• Demand loading. A large program starts instantly because none of it is in memory yet. Pages arrive as execution touches them, and code paths never taken are never loaded.

One consequence turned into a security problem. To make system calls cheap, kernels traditionally mapped kernel memory into every process's page table, marked inaccessible to user mode, so entering the kernel required no page-table swap. Meltdown showed that the accessibility bit was checked too late in the speculative pipeline to keep the data secret. The mitigation, kernel page-table isolation, gives user mode a table containing almost no kernel mapping - restoring safety by paying on every system call exactly the cost the original design existed to avoid.

Where people get stuck

• "A virtual address is the real location in RAM." It is a private address the program uses; the page table translates it to a physical frame.
• "Virtual memory cannot exceed physical RAM." Pages not in use are kept on disk, so the virtual space can be larger than RAM.
• "A page fault is a crash." A page fault is a normal event the OS handles by loading the page and retrying the instruction.
• "Translation happens in software on every access." The MMU translates in hardware, and the TLB caches recent translations to keep it fast.
• "The page table is one big array." A flat 32-bit table would be 4 MB per process, so real systems use a tree of four or five levels and prune the empty regions.
• "A bigger TLB would solve everything." TLBs must be fast, so they stay small. Increasing the page size increases coverage far more cheaply, which is what huge pages do.

Recap

• Programs use virtual addresses; virtual memory maps them to physical addresses.
• Memory is divided into pages (virtual) and frames (physical) of equal size, and a power-of-two page size makes the address split free.
• A page table maps each virtual page to a frame; the address offset is unchanged.
• Page tables are multi-level trees, because a flat table would be enormous and mostly empty.
• The MMU does translation in hardware, with a TLB caching recent lookups; the TLB hit rate matters as much as any cache hit rate, and huge pages exist to extend its reach.
• A page fault loads a needed page from disk and retries, so virtual space can exceed RAM - but a fault is thousands of times slower than an access, and thrashing is the failure mode.
• Virtual memory provides isolation, flexibility, and a simple uniform address space, plus per-page protection, sharing, copy-on-write, memory-mapped files, and demand loading.

Virtual memory is the clearest case in this course of an indirection that pays for itself many times over. One table lookup between the program and physical memory buys isolation, sharing, protection, and the ability to lie convincingly about how much memory exists.

Sources

1. Patterson, D. A., & Hennessy, J. L. (2020). Virtual memory. In Computer organization and design RISC-V edition: The hardware software interface (2nd ed., ch. 5.7). Morgan Kaufmann. find source ↗
2. Bryant, R. E., & O'Hallaron, D. R. (2016). Virtual memory. In Computer systems: A programmer's perspective (3rd ed., ch. 9). Pearson. find source ↗
3. Silberschatz, A., Galvin, P. B., & Gagne, G. (2018). Main memory; Virtual memory. In Operating system concepts (10th ed., ch. 9 and 10). Wiley. find source ↗
4. Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. (n.d.). Paging: Introduction. In Operating systems: Three easy pieces. University of Wisconsin-Madison. pages.cs.wisc.edu
5. Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. (n.d.). Paging: Faster translations (TLBs). In Operating systems: Three easy pieces. University of Wisconsin-Madison. pages.cs.wisc.edu
6. Linux kernel contributors. (n.d.). Page tables. The Linux Kernel documentation. docs.kernel.org
7. Linux kernel contributors. (n.d.). Page table isolation (PTI). The Linux Kernel documentation. docs.kernel.org

For thirty years, the way to make software faster was to wait. Each new processor generation ran the same code more quickly, and no programmer had to do anything. Lesson 8 explained why that ended: the extra transistors now go into more cores rather than a faster one, and a core does nothing for a program that cannot use it. Concurrency stopped being a specialist topic in about 2005 and became the price of admission for performance.

The big picture

Modern chips have several cores, and even a single core juggles many tasks. When multiple streams of execution touch the same data, subtle bugs appear that do not exist in simple sequential code. This lesson introduces threads, shows how sharing data can go wrong, explains the basic tools that keep concurrent programs correct, and gives you the arithmetic for how much parallelism is actually worth.

Threads: multiple flows in one program

A thread is an independent flow of execution within a process. A single process can have several threads that share the same memory but each run their own sequence of instructions, like several cooks working in one kitchen from a shared set of ingredients. Threads are useful because they let a program do things at the same time, for example one thread handling the user interface while another loads a file.

Concurrency means having multiple tasks in progress during overlapping time periods; parallelism means literally executing more than one at the very same instant, which requires multiple cores. Concurrency can exist on one core through rapid switching; parallelism needs real hardware duplication. The two often go together but are not the same.

The distinction between a thread and a process is exactly the address space. Two processes have separate page tables, so one cannot touch the other's memory even by accident - that is the isolation Lesson 17 provides. Two threads inside one process share a single page table, so all their global data is common ground. That makes communication between threads free, and it is also why every bug in this lesson exists. Threads also switch more cheaply, because there is no page table to swap and the caches stay warm.

Key idea: threads are separate flows sharing a process's memory; concurrency is overlapping progress, parallelism is truly simultaneous execution.

How much does another core buy you? Amdahl's law

Before writing any concurrent code it is worth knowing the ceiling. In 1967 Gene Amdahl pointed out something deflating: if part of a program cannot be parallelized, that part sets a hard limit on speedup no matter how many processors you add. Let p be the fraction of the work that parallelizes and N the number of processors.

speedup = 1 / ( (1 - p) + p/N )

p = 0.95 (95% parallel):
    N = 4     ->  1 / (0.05 + 0.2375)   = 3.48x
    N = 16    ->  1 / (0.05 + 0.059375) = 9.14x
    N = 1000  ->  1 / (0.05 + 0.00095)  = 19.6x
    N -> inf  ->  1 / 0.05              = 20x   (the hard ceiling)

p = 0.90:  ceiling is 10x, and 16 cores give only 6.4x
p = 0.50:  ceiling is  2x, and 16 cores give only 1.88x

Sit with the 95 percent line for a moment. A program that is 95 percent parallel - which would be an excellent result for real code - can never exceed 20x however much hardware you buy, and 16 cores deliver less than 10x of the theoretical 16. The serial 5 percent dominates everything. This is why the practical advice is to attack the serial fraction first, and why adding cores to a workload with a large sequential phase is money badly spent.

Amdahl's law is a ceiling, not a prophecy. It assumes a fixed problem size, and many real workloads grow: given a machine sixteen times larger, people simulate a finer mesh or train a bigger model rather than running the old problem faster. When the parallel portion scales with the machine, the picture is much more favourable, an observation usually credited to John Gustafson. Both framings are correct; they answer different questions. Ask which one your problem matches before quoting either.

The danger of shared data: race conditions

When two threads read and write the same data without coordination, the result can depend on the exact timing of their steps. This is a race condition, and it is a notorious source of bugs. The classic example is two threads each trying to add 1 to a shared counter. Incrementing looks like one action but is really three steps: read the value, add one, write it back. If the steps interleave badly:

1. Thread A reads the counter (say 5).
2. Thread B reads the counter (also 5, because A has not written yet).
3. Thread A adds one and writes 6.
4. Thread B adds one to its old value and writes 6.

Two increments happened but the counter went from 5 to 6, not 7. One update was silently lost. The bug appears only for certain timings, which makes it maddening to reproduce.

Critical sections and mutual exclusion

The stretch of code that touches shared data and must not be interrupted by another thread is a critical section. The fix for a race condition is mutual exclusion: ensuring only one thread is inside the critical section at a time. The common tool is a lock (also called a mutex, for mutual exclusion). A thread must acquire the lock before entering the critical section and release it when done; while one thread holds the lock, others wait. With a lock around the counter update, the read-add-write happens without interruption, so no update is lost.

Think of the lock as the single key to a one-person room: you can only go in if you hold the key, and you must return it before anyone else can enter.

Key idea: a lock enforces mutual exclusion so only one thread runs the critical section at a time, preventing races.

What a lock is made of

A lock is software, so it faces its own chicken-and-egg problem: acquiring it means reading a flag and then setting it, which is itself a read-modify-write that two threads could interleave. Pure software cannot escape this, so the hardware supplies a primitive. An atomic instruction performs a read and a write as one indivisible operation that no other core can split. The two you will meet by name are test-and-set, which writes 1 and returns the old value, and compare-and-swap, which writes a new value only if the current value matches an expected one.

acquire(lock):
    while compare_and_swap(lock, 0, 1) != 0:
        wait          # somebody else holds it
release(lock):
    lock = 0

Because the compare and the swap cannot be separated, exactly one thread sees the 0 and takes the lock. Every mutex, semaphore, and lock-free queue is built on top of instructions like these, which is why the instruction set has to provide them - and it is one more example of a software abstraction resting on a specific hardware guarantee.

Coherence, and the trap called false sharing

Cores have private caches, so a value can exist in several copies at once. Hardware keeps them consistent with a cache coherence protocol: before a core may write a line, it takes exclusive ownership and invalidates every other core's copy. Correctness is preserved automatically, and it is the reason threads can share memory at all.

It is also a performance trap with a name. Coherence works on whole cache lines, not on individual variables, so two threads updating two different counters that happen to sit in the same 64-byte line will fight over that line as if they shared a variable. Each write invalidates the other core's copy, and the line ping-pongs between them across the interconnect. Nothing is incorrect, and the code can run several times slower than the single-threaded version it replaced. This is false sharing, and the fix is to pad the data so that each thread's hot variables occupy their own line. It is a good illustration of a theme running through this whole course: a hardware unit invisible to correctness is entirely visible to performance.

Coherence has a companion issue. To hide latency, processors and compilers may reorder memory operations, so one thread can observe another thread's writes in an order the source code never suggests. The rules governing this are the memory model, and the tool for pinning down order where you need it is a barrier or an ordered atomic operation. In practice, use the synchronization your language provides and let it emit the right barriers; hand-rolled lock-free code without a firm grasp of the memory model is one of the most reliable ways to write a bug that appears once a month in production.

New hazards that locks introduce: deadlock

Locks solve races but bring their own risk. A deadlock is a standstill where threads are stuck forever, each waiting for a lock another holds. The classic picture is two threads and two locks: thread A holds lock 1 and wants lock 2, while thread B holds lock 2 and wants lock 1. Neither will release what it has, so both wait forever, like two people in a narrow hallway each refusing to step aside. A simple way to avoid this is to always acquire multiple locks in the same fixed order, so a cycle of waiting cannot form.

Deadlock is not the only way locking goes wrong. Starvation is a thread that is technically able to run but keeps losing, because other threads take the lock first every time. Livelock is worse in a way: threads are busy and making no progress, each politely backing off and retrying in step with the other, like two people repeatedly stepping the same way in a corridor.

There is also a design tension with no clean answer. One coarse lock around a whole data structure is easy to reason about and correct, and it serializes every thread through one bottleneck - which can leave a sixteen-core machine performing like one core. Many fine-grained locks allow real parallelism, and multiply the opportunities for deadlock, forgotten locks, and subtly wrong ordering. Experienced practice is to start coarse, measure, and split only where the measurement says it matters. Better still, avoid sharing where the problem allows it: give each thread its own data and combine results at the end, which is why message passing and immutable data have become popular answers to a problem that locks solve only awkwardly.

Key idea: a deadlock is a permanent standstill where threads wait on each other's locks, and consistent lock ordering helps prevent it.

Where people get stuck

• "Incrementing a shared counter is a single, safe operation." It is usually read, add, and write, which can interleave and lose updates without a lock.
• "Concurrency and parallelism are the same." Concurrency is overlapping progress; parallelism is simultaneous execution requiring multiple cores.
• "Locks make all concurrency problems disappear." Locks prevent races but can introduce deadlock if used carelessly.
• "A race condition always shows up in testing." Races depend on timing and may appear only occasionally, which is what makes them hard to catch.
• "Twice the cores means twice the speed." Amdahl's law says the serial fraction sets the ceiling. At 90 percent parallel, no number of cores can exceed 10x.
• "If two threads use different variables, they cannot interfere." They can, if those variables share a cache line. False sharing costs performance without costing correctness.

Recap

• A thread is an independent flow of execution that shares its process's memory, which is what makes communication free and bugs possible.
• Concurrency is overlapping progress; parallelism is truly simultaneous and needs multiple cores.
• Amdahl's law caps speedup at 1 / (1 - p), so the serial fraction, not the core count, usually decides the outcome.
• A race condition is a timing-dependent bug from uncoordinated shared access, such as a lost counter update.
• A critical section touches shared data; a lock enforces mutual exclusion to protect it, and locks are built on atomic hardware instructions such as compare-and-swap.
• Cache coherence keeps shared data correct automatically, but false sharing on a cache line can silently destroy performance.
• Careless locking can cause deadlock, starvation, or livelock; consistent lock ordering, coarse-then-measure granularity, and simply not sharing are the practical defences.

This is where the course closes the loop. The power wall of Lesson 8 forced the industry into multicore, multicore forced concurrency onto every programmer, and the caches, coherence, and atomic instructions that make concurrency work are the same hardware you have been studying since Module 1. The machine is one system, and its constraints propagate all the way up into the code you write.

Sources

1. Bryant, R. E., & O'Hallaron, D. R. (2016). Concurrent programming. In Computer systems: A programmer's perspective (3rd ed., ch. 12). Pearson. find source ↗
2. Silberschatz, A., Galvin, P. B., & Gagne, G. (2018). Synchronization tools; Deadlocks. In Operating system concepts (10th ed., ch. 6 and 8). Wiley. find source ↗
3. Amdahl, G. M. (1967). Validity of the single processor approach to achieving large scale computing capabilities. AFIPS Conference Proceedings, 30, 483-485. doi.org ↗
4. Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. (n.d.). Concurrency: An introduction. In Operating systems: Three easy pieces. University of Wisconsin-Madison. pages.cs.wisc.edu
5. Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. (n.d.). Locks. In Operating systems: Three easy pieces. University of Wisconsin-Madison. pages.cs.wisc.edu
6. MITRE Corporation. (n.d.). CWE-362: Concurrent execution using shared resource with improper synchronization (race condition). Common Weakness Enumeration. cwe.mitre.org
7. Kerrisk, M. (n.d.). pthreads(7) - Linux manual page. man7.org