Operating Systems

Learn how an OS actually works by building its algorithms from scratch in C: process tables and schedulers, locks and deadlock detection, memory allocators, page tables and replacement policies, a filesystem's inodes and bitmaps, disk scheduling, a tiny shell, and a mini kernel simulator. The machinery under every program you have ever run.

10 projects, 250 hands-on levels, run in your browser.

Syllabus

Processes: A process is a running program plus the bookkeeping the kernel keeps about it: its state, its registers, its place in the family tree. This project builds that bookkeeping from scratch, the process control block, the five-state lifecycle and its legal transitions, a fixed-size process table with PID allocation, and the parent-child arithmetic behind fork, zombies, and orphans.
CPU Scheduling: One CPU, many ready processes: the scheduler decides who runs next, and that one decision shapes how responsive the whole machine feels. This project simulates the classic policies, first-come-first-served, shortest-job-first, priority, and Round Robin with its time slices, and computes the waiting, turnaround, and response times that let you judge them against each other.
Synchronization & Deadlock: Two processes touch the same counter and the result is wrong, sometimes. This project builds the machinery that tames shared state: the test-and-set lock, counting semaphores, the bounded ring buffer behind every producer-consumer pair, and then the failure mode of locking itself, deadlock, detected with wait-for graphs and avoided with the Banker's algorithm.
Memory Allocation: Behind every malloc is an allocator juggling a finite heap: find a hole, split it, hand it out, and merge it back when freed. This project builds the classic placement policies (first, best, worst fit), the split-and-coalesce machinery of the free list, the fragmentation arithmetic that explains why allocation fails with memory still free, and the elegant power-of-two buddy system.
Virtual Memory: Every process believes it owns all of memory; the MMU makes that lie true. This project builds the translation machinery: carving a virtual address into page number and offset, the page table that maps pages to frames with valid and dirty bits, fault detection, the TLB whose hit rate makes or breaks performance, and the two-level tables that keep the whole map sparse.
Page Replacement: When every frame is taken, loading one page means evicting another, and the choice of victim decides how often the machine stalls. This project runs reference strings through the classic policies: FIFO and its strange Belady anomaly, LRU and its timestamp bookkeeping, the clock algorithm that approximates LRU with one bit, and the optimal oracle that knows the future and sets the bar.
File Systems: A disk is just numbered blocks; a filesystem turns them into named files that survive reboots. This project builds the core structures: the inode with its direct and indirect block pointers, the bitmap that tracks free space, the FAT-style chains that link a file's clusters, the directories that map names to inodes, and the nine permission bits guarding it all.
Disk & I/O: Memory is nanoseconds; the disk is milliseconds, a million times slower, so the OS fights for every avoided seek. This project computes seek distances under the classic schedulers (FCFS, shortest-seek-first, and the SCAN elevator family), builds the buffer cache that makes most reads free, models read-ahead, and finishes with RAID striping and the XOR parity trick that survives a dead disk.
The Shell & IPC: The shell is just a program: read a line, split it into words, fork, exec, wait, repeat. This project builds its core machinery, tokenizing command lines, spotting pipes and redirections, modeling the pipe buffers that connect processes, decoding exit statuses, and the signal dispatch that delivers Ctrl-C. By the end, ls | grep foo > out is no longer magic.
Capstone: A Mini Kernel: Time to assemble the whole machine. A kernel is a loop: pick a process, run it for a slice, handle whatever it asks for, repeat until everyone is done. This capstone wires the pieces from the whole track into one simulator, a process table, a Round-Robin dispatcher, a frame allocator with FIFO replacement, a syscall layer, and the boot-to-idle run that accounts for every tick. At the end you will have stepped a kernel by hand.

Key concepts

Aging: The anti-starvation fix: a waiting job's priority improves with time, so even the lowliest job eventually runs.
Allocator: The machinery behind malloc: find a hole, split it, hand it out, merge it back on free. Placement policy and coalescing decide how fast the heap shatters.
Atomic operation: An operation that completes indivisibly, no other CPU can see it half-done. Test-and-set is the atomic primitive under every spinlock.
Banker's algorithm: Deadlock avoidance: grant a request only if some completion order still exists afterward (the state stays 'safe'). Pretend-finish processes one by one;…
Belady's anomaly: FIFO's scandal: on some reference strings, MORE frames cause MORE faults. LRU and OPT are immune (the stack property).
Blocked (waiting): A process that cannot run until some event happens, usually I/O finishing or a lock freeing. Blocking frees the CPU for someone else, the heart of multiprogram…
Buddy system: Allocate only powers of two, split blocks in halves: every block's buddy is found by one XOR (offset ^ size), making merges trivial. Elegance bought with i…
Buffer cache: Recently used disk blocks kept in memory: most reads never touch the disk. Dirty blocks queue for writeback; fsync forces them out.
Clock (second chance): LRU's cheap approximation: one referenced bit per frame and a sweeping hand that clears bits and evicts the first unreferenced page. What real kernels actu…
Coalescing: Merging adjacent free blocks back into big ones after free(). Without it the heap dissolves into useless slivers no request fits.
Coffman conditions: The four prerequisites of deadlock: mutual exclusion, hold-and-wait, no preemption, circular wait. Prevention strategies each attack one.
Context switch: Saving one process's registers into its PCB and restoring another's. The price of multitasking, paid in microseconds, thousands of times per second.
Convoy effect: Short jobs trapped behind a long one under FCFS, inflating everyone's waiting time. The reason no interactive system schedules FCFS.
Critical section: Code touching shared state that must not interleave. Correct locking caps occupancy at one; everything in synchronization exists to enforce that.
Deadlock: Processes each holding what another needs, waiting in a cycle nobody can break. Requires all four Coffman conditions; break any one and it cannot happen.
Demand paging: Load pages only when first touched. Programs start instantly and only their working set ever occupies memory.
Directory: A table mapping names to inode numbers, itself stored as a file. Path resolution walks one directory per component, /home/user is two lookups.
Disk block: The filesystem's allocation unit. File sizes round up to blocks, the unused tail is slack, and block size trades seek efficiency against that waste.
Disk scheduling: Reordering the request queue to cut head movement: SSTF grabs the nearest, SCAN sweeps like an elevator, C-SCAN sweeps one way for uniform waits.
Error codes (errno): How syscalls fail: negative codes like ENOENT (no such file), EBADF (bad descriptor), ENOMEM (out of memory). Checking them is the difference between robust an…
Exit status: The number a process leaves behind: 0 means success. wait() packs it with how the child died; shells show 128+signal for kills, and &&, ||, and $? all…
File allocation table (FAT): A linked list in an array: fat[cluster] points to the file's next cluster, a sentinel ends the chain. Simple enough to live on every USB stick; corruptible…
File descriptor: A small integer naming an open file, pipe, or socket in a process. open() returns the lowest free one, which is why redirections work by closing and reopening.
First / best / worst fit: Placement policies for a request among free holes: first fit takes the earliest, best fit the tightest (smallest leftover), worst fit the roomiest. Each shapes…
First-come, first-served (FCFS): Run jobs in arrival order, each to completion. Simple, but one long job at the front makes everyone wait, the convoy effect.
Five-state lifecycle: NEW, READY, RUNNING, BLOCKED, TERMINATED, and the legal moves between them. Only the dispatcher moves READY to RUNNING; only I/O completion moves BLOCKED back…
fork(): The Unix way to create a process: duplicate the caller. After n straight-line forks there are 2^n processes, the classic interview teaser.
Fragmentation: External: enough total free memory but no single hole big enough. Internal: waste inside rounded-up allocations. Both mean paying for memory you cannot use.
Free-space bitmap: One bit per block, set means used. Tiny, fast to scan, and the structure df reads to answer how much space is left.
I/O overlap: While one process waits on the disk, another computes: blocking I/O plus a scheduler turns dead wait time into useful work, the original argument for multiprog…
Indirect block: A block full of block pointers: the inode's escape hatch past its dozen direct slots. Single indirect, then double, multiply a file's maximum size by t…
init (pid 1): The first user process, ancestor of everything, adopter of orphans. If init dies, the system goes down with it.
Inode: The file's identity on disk: size, owner, permissions, and the direct plus indirect block pointers that locate its data. The name lives in a directory; the…
Job control: The shell juggling foreground, background, and stopped jobs: & launches in the background, Ctrl-Z stops, fg and bg resume. State machines over the job tabl…
Kernel mode vs user mode: The CPU's privilege split: user code cannot touch hardware or other processes' memory; kernel code can. Syscalls and interrupts are the only crossings.
LRU: Evict the page unused the longest, the best practical predictor of future use. Has the stack property (more memory never hurts) but costs a timestamp on every…
Multi-level feedback queue (MLFQ): Several priority queues with demotion: jobs that burn full quanta sink to lower levels, interactive jobs stay on top. How real desktop schedulers behave.
Mutex: A lock only one holder can own, the binary semaphore. The standard guard for critical sections; blocking versions sleep instead of spinning.
Orphan process: A process whose parent died first. The kernel re-parents orphans to init (pid 1), which dutifully waits on them.
Page & frame: Memory in fixed chunks: virtual pages map onto physical frames. An address splits into page number (translated) and offset (untouched).
Page fault: A trap on accessing an unmapped page. Could be demand loading (fetch and retry), could be a bug (segfault). Servicing one costs milliseconds against nanosecond…
Page replacement: Memory full, new page needed: who gets evicted? FIFO is simple, LRU predicts well, clock approximates LRU cheaply, and OPT (knowing the future) sets the unbeat…
Page table: One entry per virtual page: the frame plus valid, dirty, and referenced bits. Real tables are multi-level trees so unmapped regions cost nothing.
Page table entry (PTE): One packed word: the frame number plus flag bits, valid (mapped?), dirty (needs writeback?), referenced (recently used?). The replacement policies read these b…
Path resolution: Turning /a/b/c into an inode: start at the root, look up each component in the current directory, fail fast on a missing link. Every open() starts here.
Permission bits (rwx): Nine bits in three triplets, owner, group, other, each with read (4), write (2), execute (1). The kernel picks ONE triplet by your identity and tests the reque…
PID: The process identifier, a small integer naming each process. PIDs grow monotonically; pid 1 is init, the ancestor that adopts every orphan.
Pipe: A kernel ring buffer with two descriptors: writes block when full, reads block when empty, and a read on a closed-writer pipe returns EOF. The | in ls | grep.
Process: A running program plus the kernel's bookkeeping about it: its memory, registers, state, and identity. The fundamental unit of execution and isolation.
Process control block (PCB): The kernel's per-process record: PID, state, priority, saved registers, program counter. Everything needed to pause a process and resume it later.
Process table: The kernel's fixed array of PCBs, one slot per process. Spawning claims a free slot; ps walks it; PIDs index into it.
Producer-consumer: The bounded-buffer pattern: producers fill a fixed ring, consumers drain it, indices wrap. The structure inside every pipe, queue, and driver.
Race condition: A bug whose outcome depends on interleaving: two unsynchronized increments can lose one update, because counter++ is really load, add, store.
RAID: Many disks acting as one: RAID 0 stripes for speed, RAID 1 mirrors for safety, RAID 5 stripes with rotating parity, surviving any single dead disk at the cost…
Read-ahead: Prefetching the next blocks of a sequentially read file before they are asked for. Sequential scans become memory-speed; random access gains nothing.
Ring buffer: A fixed array with wrapping head and tail indices: put at the tail, get at the head, both modulo capacity. Constant-time FIFO in constant space.
Round Robin: Every ready job gets a fixed time slice, then goes to the back of the line. The interactive scheduler: fair and responsive, paid for in context switches.
SCAN / C-SCAN: The elevator algorithms: SCAN serves requests in sweep order, reversing at the ends; C-SCAN jumps back to the start instead, so edge cylinders wait no longer t…
Scheduler: The kernel component that picks which ready process runs next. Its policy shapes responsiveness, throughput, and fairness, often more than raw hardware speed.
Seek time: The milliseconds the disk arm spends moving between cylinders, the dominant cost of mechanical I/O and the currency disk schedulers optimize.
Semaphore: A counter with discipline: wait (P) decrements or blocks at zero; signal (V) increments or wakes a sleeper. Initialized to 1 it is a mutex; to k, a resource po…
Shell: Just a program: read a line, tokenize it, fork, exec, wait, repeat. Pipes, redirection, and job control are all built from the same few syscalls.
Shortest job first (SJF): Always run the shortest remaining job: provably optimal for average waiting time. The catches: you must predict burst lengths, and long jobs can starve.
Signal: An asynchronous poke from the kernel: Ctrl-C is SIGINT, kill -9 is SIGKILL. Each has a disposition, default, ignore, or handler, except KILL, which always kill…
Spinlock: A lock that retries in a tight loop until it wins. Fast when contention is brief, a CPU bonfire when it is not; ticket locks add fairness.
Starvation: A runnable job waiting indefinitely because the policy always prefers others, SJF's long jobs, low priorities under strict priority scheduling.
System call: The only door from user code into the kernel: a numbered request (read, write, fork...) that traps into kernel mode, gets validated, and returns a result or a…
Test-and-set: Atomically read a lock's old value and set it to 1. Returning 0 means you got the lock; looping on it makes a spinlock.
Thrashing: Fault rate so high the machine spends its time paging instead of computing. The fix is fewer processes or more memory, never a cleverer policy.
Thread: A schedulable execution stream inside a process. Threads share the process's memory but each has its own registers and stack, which is why they race on sha…
Throughput: Jobs completed per unit time. Often traded against responsiveness: batch systems chase throughput, desktops chase response time.
Time quantum: Round Robin's slice length. Too small drowns in switch overhead; too large degrades to FCFS. Real kernels pick milliseconds.
TLB: The translation cache: a tiny buffer of recent page-to-frame mappings checked before any table walk. Its hit rate decides whether paging is free or doubles mem…
Turnaround, waiting, response: The scheduler's yardsticks: turnaround = finish minus arrival; waiting = turnaround minus CPU time; response = first run minus arrival, what an interactive…
umask: The bits REMOVED from a new file's requested mode: effective = mode & ~umask. The classic 022 strips group and other write.
Virtual memory: Every process sees a private address space; the MMU translates each access through page tables to real frames. Isolation, overcommit, and demand loading all fa…
Wait-for graph: Nodes are processes; an edge points at the process you are blocked on. A cycle in this graph IS a deadlock, which makes detection a graph walk.
Working set: The pages a process touched in its recent window. If memory holds every process's working set the system hums; if not, it thrashes.
XOR parity: The parity block is the XOR of the data blocks, so any one missing block equals the XOR of the survivors plus parity. One extra disk buys survival of one failu…
Zombie process: A terminated process still occupying its table slot because its parent has not called wait() to collect its exit status. Harmless alone, a leak in bulk.