Computer Science › How Computers Actually Work
This lab builds a userspace simulator implementing Paging and Page Tables' own multi-level page table walk over a simulated virtual address space, adds a small, fixed-size TLB cache in front of it exactly as The Translation Lookaside Buffer describes, and measures directly, by counting real simulated memory accesses, the actual hit rate difference a TLB makes and the actual thrashing behavior Page Replacement Policies predicts once the simulated working set is made to exceed available physical frames under FIFO versus LRU replacement.
This lab, matching the official OSTEP-projects xv6 scheduling assignment, replaces xv6's own default round-robin scheduler with a lottery scheduler, assigning each process a number of tickets and picking the next process to run via a weighted random draw, a genuinely different fairness mechanism from Multi-Level Feedback Queue Scheduling's own priority-adjustment approach, and one that sidesteps Priority Scheduling and Starvation's own starvation failure mode by construction, since every process with at least one ticket has a real, nonzero chance of being drawn on every scheduling decision.
The Heap and Dynamic Allocation already explains why malloc and free need to track free versus allocated space themselves, since the underlying operating system only hands out coarse-grained pages; CMU's own Malloc Lab is where a student implements malloc, free, and realloc for real, backed by a free list threading through the unused blocks themselves and boundary tags enabling constant-time coalescing of adjacent free blocks, graded on the same real, concrete tradeoff every allocator design actually faces: throughput (operations per second) against memory utilization (how little space is wasted to fragmentation and bookkeeping overhead).
A single, ordinary file on the host machine stands in for a raw disk in this lab, formatted with Files, Directories, and Inodes' own layout, a superblock, an inode table, and a data-block region tracked by a free-block bitmap reusing Lab 8's own free-space-management discipline at the block level instead of the byte level, and exercised through real create/write/read/delete operations, closing with a deliberate, injected crash mid-write to confirm File System Implementation and Journaling's own claim, that only a journaled file system, not this lab's intentionally simpler first version, actually survives that crash without corruption.
Operating Systems I's own closing concept traces a process through fork, scheduling, a page fault, and a disk write as a single, connected narrative; this capstone is where that narrative is run for real, against the actual components this whole discipline built, a process spawned and handed tickets by Lab 9's lottery scheduler, a memory access that misses Lab 10's simulated TLB and walks its page table, and a resulting write committed through Lab 11's own simple file system, with every one of those four events logged with a timestamp and produced as a single, continuous trace connecting this whole discipline's separately built labs into the one integrated system Operating Systems I only had room to describe in prose.
This lab leaves this discipline's own custom, toy CPU behind for real, compiled x86-64 machine code: CMU's own Bomb Lab, a Linux binary that reads a string from standard input and "explodes" if it does not match a hidden expected value across six increasingly difficult phases, defused entirely through disassembly (objdump), a debugger (gdb), and the register/condition-code reading skills already covered theoretically in x86-64 Registers and Data Movement and Condition Codes and Conditional Branches, with no access to source code at any point.
Stack Smashing and Buffer Overflows already proved, on paper, that an unchecked write past a stack buffer can overwrite a saved return address; CMU's own Attack Lab is where that proof becomes a real, working exploit against a real, compiled binary, three code-injection attacks that overwrite the return address with hand-crafted shellcode, followed by two harder return-oriented-programming attacks that chain together existing code fragments (gadgets) already present in the binary once the target binary defends against injected code at all, exactly the escalation The x86-64 Runtime Stack: Call and Ret's own stack-frame model makes legible.
NAND as a Universal Gate proved, on paper, that every other gate is expressible in NAND alone; this lab is where that proof stops being an exercise in boolean algebra and becomes working code, composing a software NAND primitive into AND, OR, NOT, XOR, and a 2-to-1 multiplexer, each one verified against its own truth table, exactly the first, foundational step of Nand2Tetris's own build-a-computer sequence.
Combinational logic alone has no memory, which is why this lab implements a D flip-flop as the base sequential primitive, composes it into a multi-bit register with a load-enable signal, and then composes an array of those registers, addressed through a decoder built from Lab 1's own gates, into a small, working RAM, matching From Flip-Flops to a Register File and RAM Organization and Address Decoding's designs with actual, runnable code instead of a circuit diagram.
This lab composes Lab 1's gate set into a working ALU matching the design already worked out theoretically in Designing an Arithmetic Logic Unit: a ripple-carry adder built from full adders built from Lab 1's own AND/XOR gates, an operation-select multiplexer choosing between add/subtract/AND/OR, and zero and overflow flags computed directly from the adder's own output bits rather than as an afterthought bolted on separately.
Every earlier lab in this arc built one component; this lab wires Lab 2's ALU, Lab 3's register file and RAM, and a control unit decoding this curriculum's own RISC-V-style ISA into a single, complete CPU that actually fetches, decodes, and executes a real instruction sequence, matching Assembling a Complete Single-Cycle CPU's own design and MIT 6.004's Beta CPU project, verified not by inspection but by loading a small, hand-assembled program into the built RAM and confirming the register file ends in the expected state after execution.
This lab closes the CPU-building arc by writing the tool that makes Lab 4's CPU actually usable: a two-pass assembler that first resolves every label to an address (a symbol table built from a first pass over the source), then translates each mnemonic instruction into the exact bit pattern Lab 4's control unit decodes, matching Assembly to Machine Code Translation's own account of the process, with the finished assembler's own output fed directly back into Lab 4's RAM as this lab's real, end-to-end correctness test.
Part of the Computer Science curriculum.
This lab builds a userspace simulator implementing Paging and Page Tables' own multi-level page table walk over a simulated virtual address space, adds a small, fixed-size TLB cache in front of it exactly as The Translation Lookaside Buffer describes, and measures directly, by counting real simulated memory accesses, the actual hit rate difference a TLB makes and the actual thrashing behavior Page Replacement Policies predicts once the simulated working set is made to exceed available physical frames under FIFO versus LRU replacement.
This lab, matching the official OSTEP-projects xv6 scheduling assignment, replaces xv6's own default round-robin scheduler with a lottery scheduler, assigning each process a number of tickets and picking the next process to run via a weighted random draw, a genuinely different fairness mechanism from Multi-Level Feedback Queue Scheduling's own priority-adjustment approach, and one that sidesteps Priority Scheduling and Starvation's own starvation failure mode by construction, since every process with at least one ticket has a real, nonzero chance of being drawn on every scheduling decision.
The Heap and Dynamic Allocation already explains why malloc and free need to track free versus allocated space themselves, since the underlying operating system only hands out coarse-grained pages; CMU's own Malloc Lab is where a student implements malloc, free, and realloc for real, backed by a free list threading through the unused blocks themselves and boundary tags enabling constant-time coalescing of adjacent free blocks, graded on the same real, concrete tradeoff every allocator design actually faces: throughput (operations per second) against memory utilization (how little space is wasted to fragmentation and bookkeeping overhead).
A single, ordinary file on the host machine stands in for a raw disk in this lab, formatted with Files, Directories, and Inodes' own layout, a superblock, an inode table, and a data-block region tracked by a free-block bitmap reusing Lab 8's own free-space-management discipline at the block level instead of the byte level, and exercised through real create/write/read/delete operations, closing with a deliberate, injected crash mid-write to confirm File System Implementation and Journaling's own claim, that only a journaled file system, not this lab's intentionally simpler first version, actually survives that crash without corruption.
Operating Systems I's own closing concept traces a process through fork, scheduling, a page fault, and a disk write as a single, connected narrative; this capstone is where that narrative is run for real, against the actual components this whole discipline built, a process spawned and handed tickets by Lab 9's lottery scheduler, a memory access that misses Lab 10's simulated TLB and walks its page table, and a resulting write committed through Lab 11's own simple file system, with every one of those four events logged with a timestamp and produced as a single, continuous trace connecting this whole discipline's separately built labs into the one integrated system Operating Systems I only had room to describe in prose.
This lab leaves this discipline's own custom, toy CPU behind for real, compiled x86-64 machine code: CMU's own Bomb Lab, a Linux binary that reads a string from standard input and "explodes" if it does not match a hidden expected value across six increasingly difficult phases, defused entirely through disassembly (objdump), a debugger (gdb), and the register/condition-code reading skills already covered theoretically in x86-64 Registers and Data Movement and Condition Codes and Conditional Branches, with no access to source code at any point.
Stack Smashing and Buffer Overflows already proved, on paper, that an unchecked write past a stack buffer can overwrite a saved return address; CMU's own Attack Lab is where that proof becomes a real, working exploit against a real, compiled binary, three code-injection attacks that overwrite the return address with hand-crafted shellcode, followed by two harder return-oriented-programming attacks that chain together existing code fragments (gadgets) already present in the binary once the target binary defends against injected code at all, exactly the escalation The x86-64 Runtime Stack: Call and Ret's own stack-frame model makes legible.
NAND as a Universal Gate proved, on paper, that every other gate is expressible in NAND alone; this lab is where that proof stops being an exercise in boolean algebra and becomes working code, composing a software NAND primitive into AND, OR, NOT, XOR, and a 2-to-1 multiplexer, each one verified against its own truth table, exactly the first, foundational step of Nand2Tetris's own build-a-computer sequence.
Combinational logic alone has no memory, which is why this lab implements a D flip-flop as the base sequential primitive, composes it into a multi-bit register with a load-enable signal, and then composes an array of those registers, addressed through a decoder built from Lab 1's own gates, into a small, working RAM, matching From Flip-Flops to a Register File and RAM Organization and Address Decoding's designs with actual, runnable code instead of a circuit diagram.
This lab composes Lab 1's gate set into a working ALU matching the design already worked out theoretically in Designing an Arithmetic Logic Unit: a ripple-carry adder built from full adders built from Lab 1's own AND/XOR gates, an operation-select multiplexer choosing between add/subtract/AND/OR, and zero and overflow flags computed directly from the adder's own output bits rather than as an afterthought bolted on separately.
Every earlier lab in this arc built one component; this lab wires Lab 2's ALU, Lab 3's register file and RAM, and a control unit decoding this curriculum's own RISC-V-style ISA into a single, complete CPU that actually fetches, decodes, and executes a real instruction sequence, matching Assembling a Complete Single-Cycle CPU's own design and MIT 6.004's Beta CPU project, verified not by inspection but by loading a small, hand-assembled program into the built RAM and confirming the register file ends in the expected state after execution.
This lab closes the CPU-building arc by writing the tool that makes Lab 4's CPU actually usable: a two-pass assembler that first resolves every label to an address (a symbol table built from a first pass over the source), then translates each mnemonic instruction into the exact bit pattern Lab 4's control unit decodes, matching Assembly to Machine Code Translation's own account of the process, with the finished assembler's own output fed directly back into Lab 4's RAM as this lab's real, end-to-end correctness test.