7.1.1 Master Rule Sheet (all rule cards merged)

Phase 7Ch 7.1 Master rule sheet≈ 60 min

Every Rule Card from the 33 lessons, grouped by phase, in course order. Use it for revision in the last weeks: read one phase per sitting, and for any line you cannot explain in your own words, open its lesson (the lesson ID links to it).

How to revise with this sheet

Cover the rules of a lesson with your hand; say them from its title alone.
Check, and mark the lesson's ID on paper if you missed anything.
Next day, re-test only the marked IDs (spaced recall).

🧭 Phase 0 · Foundations from Zero

0.1.1 Inside a computer: CPU, memory, disk, I/O; bits, bytes and powers of two

CPU executes, RAM holds current work (volatile), disk stores permanently, I/O connects the outside.
Program = file; process = program in execution.
Byte = 8 bits; n bits → 2ⁿ values; 1 KB = 2¹⁰, 1 MB = 2²⁰, 1 GB = 2³⁰.
2ⁿ bytes ↔ n address bits; divide powers of two by subtracting exponents.

0.1.2 What an operating system does: kernel, user mode and kernel mode, interrupts

OS = resource manager + abstraction + protection; kernel runs in kernel mode.
Mode bit: user mode (restricted) vs kernel mode (all instructions).
Privileged: I/O, set timer, enable/disable interrupts, memory-management registers, halt. Not privileged: arithmetic, read clock, trap/system-call instruction.
Interrupt = from hardware; trap/exception = from the running program; timer interrupt returns control to the OS.
Multiprogramming keeps the CPU busy; time-sharing switches fast for interaction.

0.1.3 System calls: how programs ask the operating system for help

System call: wrapper → parameters + number → trap → kernel handler via system-call table → result → return to user mode (2 mode switches).
Parameters: registers, memory block, or stack.
Categories: process (fork, exec, exit, wait), file (open, read, write, close, lseek), device, information, communication.
printf, malloc, strlen are library functions; write, brk are system calls.
Monolithic kernel vs microkernel.

⚙️ Phase 1 · Processes & Threads

1.1.1 Processes: memory layout, process control block and process states

Process memory: text (code), data (globals), heap (dynamic, grows up), stack (calls, grows down).
PCB: PID, state, program counter, registers, scheduling info, memory info, open files, accounting.
States: New, Ready, Running, Waiting, Terminated.
Transitions: admit, dispatch (Ready→Running), pre-empt (Running→Ready), I/O request (Running→Waiting), event done (Waiting→Ready), exit. Waiting→Running and Ready→Waiting are impossible.
Suspended-ready / suspended-waiting via swapping.

1.1.2 Creating processes with fork(), exec() and wait(); context switches and schedulers

fork: child is a copy; returns 0 in child, child PID in parent; memory is copied, not shared.
n sequential forks → 2ⁿ processes, 2ⁿ − 1 children; prints after forks happen once per process; inside a loop, add per iteration.
exec replaces the program; wait waits for a child; zombie = exited, not waited for; orphan = parent gone.
Context switch = save + load PCB (overhead).
Long-term (admission, degree of multiprogramming), short-term (CPU), medium-term (swapping).

1.2.1 Threads: what they share, user-level vs kernel-level threads

Thread = path of execution inside a process; shares code, data, heap, open files; private stack, registers, PC, thread ID.
Threads are cheaper to create and switch than processes.
User-level: fast, kernel unaware, one block blocks all, no parallelism. Kernel-level: kernel-scheduled, independent blocking, parallel on multiple cores.
Models: many-to-one, one-to-one, many-to-many.

1.2.2 Inter-process communication: shared memory, message passing and pipes

Shared memory: map a common region; fast; programmer synchronizes.
Message passing: send/receive via the kernel; direct or indirect (mailbox); blocking or non-blocking; works across machines; copies data.
Ordinary pipe: one-way, parent–child; named pipe (FIFO) for unrelated processes; two-way needs two pipes.
Producer waits when the buffer is full; consumer waits when empty.

⏱️ Phase 2 · CPU Scheduling

2.1.1 Scheduling basics: the times we measure; first-come first-served

AT, BT given; CT from the Gantt chart; TAT = CT − AT; WT = TAT − BT; RT = first start − AT.
Non-pre-emptive: keep the CPU till done; pre-emptive: can be interrupted.
FCFS: arrival order, non-pre-emptive, convoy effect; idle gaps when nothing has arrived.

2.1.2 Shortest job first and shortest remaining time first

SJF: when free, pick the smallest burst; non-pre-emptive; optimal average WT.
SRTF: at each arrival/completion, run the smallest remaining time; pre-emptive; optimal among pre-emptive.
Both can starve long jobs; bursts predicted by τₙ₊₁ = αtₙ + (1 − α)τₙ.

2.1.3 Priority scheduling, starvation and aging; highest response ratio next

Priority: pick the most important ready process (state the direction of numbers); non-pre-emptive or pre-emptive.
Starvation of low priorities; aging raises priority over time.
HRRN: non-pre-emptive; pick the largest (W + S)/S; no starvation.
SJF = priority by burst length.

2.2.1 Round robin and the time quantum

RR: FIFO ready queue; run min(q, remaining); unfinished → back; arrivals at the same instant queue before the pre-empted process.
Large q → FCFS; small q → overhead; useful fraction q/(q + s); max wait between turns (n − 1)q.
RR: worse average WT than SJF, better response time.
Context switches: count changes between different processes.

2.2.2 Multilevel queues, CPU and I/O bursts, CPU utilisation

Multilevel queue: fixed classes, fixed priority or time-sliced between queues; no movement.
MLFQ: start at the top; full quantum used → demote; aging → promote; defined by queues, algorithms, move rules.
CPU/I/O bursts: only CPU bursts compete; I/O overlaps; count idle at the start and end.
Utilisation ≈ 1 − pⁿ.

🔒 Phase 3 · Concurrency & Synchronization

3.1.1 Race conditions and the critical-section problem

x++ = load, add, store; a pre-emption can fall between them.
Race condition: the result depends on timing. Lost update: both load before either stores; the last store wins.
Structure: entry section, CS, exit section, remainder section.
Requirements: mutual exclusion, progress, bounded waiting; no assumptions about speed.
x++ in two loops of n ≥ 2 each from 0: minimum 2, maximum 2n.

3.1.2 Software solutions: turn and flag attempts, Peterson's algorithm

Lock variable: fails mutual exclusion.
Strict alternation (turn): mutual exclusion ✓, progress ✗.
Two flags: mutual exclusion ✓, progress ✗ (deadlock).
Peterson: flag[i] = true; turn = j; wait while (flag[j] && turn == j). All three ✓, 2 processes, busy waiting.
Swapping Peterson's first two lines breaks mutual exclusion.

3.1.3 Hardware help: test-and-set, compare-and-swap, spinlocks

Atomic instruction: finishes before anything else touches that memory.
TSL: return old, set true; lock = spin until old is false. ME ✓, progress ✓, bounded waiting ✗.
CAS(&v, e, n): if v == e then v = n; returns the old value. Swap exchanges atomically.
Spinlocks: good on multiprocessors for short sections; no context switch.
Disabling interrupts: one CPU, kernel only. Priority inversion → priority inheritance.

3.2.1 Semaphores: wait, signal, counting and binary semaphores

wait/P: S--; if S < 0 block. signal/V: S++; if S ≤ 0 wake one. Atomic.
Negative value −k = k processes waiting. Final value = initial − waits + signals.
Binary (mutex, starts 1) vs counting (starts k). Ordering semaphore starts 0.
Opposite orders of waits can deadlock; LIFO queues can starve.

3.2.2 Classic problems: bounded buffer, readers–writers, dining philosophers

Bounded buffer: mutex = 1, empty = N, full = 0; counting wait before mutex wait; signals in any order.
Readers–writers (reader priority): first reader waits on rw, last reader signals rw; writers may starve.
Dining philosophers: all left-first → deadlock; fixes: ≤ 4 at table, asymmetry, both-at-once. Max ⌊n/2⌋ eat together.

3.2.3 Monitors, and reasoning about concurrent code

Monitor: shared data + functions; one process active inside; condition variables wait/signal.
x.wait releases the monitor; x.signal wakes one, or does nothing if none waits.
Signal-and-wait vs signal-and-continue (re-check with while).
Code analysis: shared/local → split → extremes → semaphore values → ME, deadlock, progress, starvation.

🧱 Phase 4 · Deadlock

4.1.1 Deadlock: the four conditions and resource-allocation graphs

Deadlock: each process in a set waits for something only another in the set can give.
Four necessary conditions: mutual exclusion, hold and wait, no pre-emption, circular wait.
RAG: request P → R, assignment R → P. No cycle → no deadlock; cycle + single instances → deadlock; cycle + multiple instances → maybe.
Starvation ≠ deadlock.

4.1.2 Prevention and avoidance: safe states and the banker's algorithm

Prevention breaks a condition: all-at-once requests (hold and wait), pre-emption, resource ordering (circular wait).
Safe state: some order lets everyone finish. Unsafe ≠ deadlock.
Banker's: Need = Max − Allocation; Work = Available; pick Need ≤ Work; Work += Allocation; all finish → safe.
Request: ≤ Need, ≤ Available, pretend, check safety; grant only if safe.

4.1.3 Detection, recovery, and the minimum-resources formula

Strategies: prevention, avoidance, detection + recovery, ignore (ostrich).
Single instances: wait-for graph cycle = deadlock. Multiple: matrix detection with Request ≤ Work.
Recovery: kill all / one at a time; pre-empt with victim + rollback (avoid starving one victim).
No deadlock ⟺ R ≥ Σ(kᵢ − 1) + 1; n equal processes: R ≥ n(k − 1) + 1.

🧠 Phase 5 · Memory Management & Virtual Memory

5.1.1 Addresses and contiguous allocation: fits and fragmentation

Logical address from the CPU; MMU makes the physical address.
Base/limit: if L < limit then physical = base + L, else trap.
Fixed partitions → internal fragmentation; variable → external; compaction merges holes.
First fit (first big enough), next fit (continue from last), best fit (smallest big enough), worst fit (largest).
50% rule: N blocks allocated → about 0.5N lost (one third).

5.2.1 Paging: pages, frames, page tables and the address split

Page = frame size = 2ᵈ; offset = low d bits; page number = high m − d bits.
Physical = frame × page size + offset.
Page-table size = (#pages) × (PTE size); frame bits = physical bits − d.
PTE: frame, valid, protection, dirty, referenced. Shared code → same frames.
Paging: internal fragmentation only (≈ half a page per process).

5.2.2 TLBs, effective access time and multilevel page tables

EAT = h(t + m) + (1 − h)(t + 2m); with k levels the miss costs t + (k + 1)m.
TLB: small associative cache; flush on switch unless ASIDs.
Multilevel: entries per page = page size / PTE; bits per level = log₂ of it; levels = ⌈(m − d) / bits per level⌉.
Inverted table: one entry per frame, searched via hashing.

5.2.3 Segmentation, and segmentation with paging

Segment table entry (base, limit); (s, d) → base + d if d < limit, else trap.
Paging: equal pieces, internal fragmentation. Segmentation: logical pieces, external fragmentation, natural sharing/protection.
Segmentation with paging: (s, p, d); each segment paged.

5.3.1 Demand paging, page faults and effective access time

Demand paging: load on first reference; valid bit = in memory.
Page fault: trap → check → free frame (or victim) → disk read → update table → restart.
EAT = (1 − p)·ma + p·s; ms = 10⁶ ns.
Dirty victims must be written back; average s weighted by the dirty fraction.
Copy-on-write makes fork() cheap.

5.3.2 Page replacement: FIFO, optimal and LRU; Belady's anomaly

FIFO: evict earliest loaded. OPT: evict farthest next use (never used = best). LRU: evict least recently used.
Running string, 3 frames: FIFO 10, OPT 7, LRU 9; 4 frames: FIFO 7, OPT 6, LRU 6.
Belady (FIFO): 1 2 3 4 1 2 5 1 2 3 4 5 → 9 faults with 3 frames, 10 with 4. LRU and OPT are stack algorithms (no anomaly).
Faults ≥ distinct pages (from empty); exact LRU needs counters or a stack.

5.3.3 Frame allocation, thrashing, working sets and the clock algorithm

Equal: m/n. Proportional: aᵢ = sᵢ/S × m. Global vs local replacement.
Thrashing: more paging than work; cure by reducing multiprogramming.
Working set: distinct pages in last Δ references; D = Σ WSS > m → suspend someone. PFF bounds.
Clock: bit 1 → clear and move; bit 0 → replace (new page bit 1). Enhanced: prefer (0,0).

💾 Phase 6 · File Systems & I/O

6.1.1 Files, directories and access methods

File: attributes + operations; open() returns a descriptor; seek moves the pointer.
System-wide table (open count) + per-process table (file pointer).
Access: sequential, direct, indexed. Directories: single, two-level, tree (absolute/relative paths), acyclic graph, general graph.
Hard link = same inode, link count; soft link = path (can dangle).
UNIX rwx bits: owner/group/others, r4 w2 x1 (e.g. 754 = rwxr-xr--).

6.1.2 Allocation methods: contiguous, linked (FAT), indexed (inodes); free space

Contiguous: (start, length), block b = start + b; external fragmentation.
Linked: next pointers; block b needs b + 1 reads. FAT = one entry per disk block, cached.
Indexed/inode: k = B/P; max size = (direct + k + k² + k³) × B; reads: direct 1, single 2, double 3, triple 4.
Free space: bitmap (blocks/8 bytes), linked list, grouping, counting.

6.2.1 Disk structure and access time

Track, sector, cylinder; one head per surface.
Capacity = surfaces × tracks × sectors × bytes.
Access = seek + latency + transfer; rotation = 60/RPM s; average latency = half a rotation.
Transfer rate = bytes per track × rotations per second. Linear sector = (c × heads + h) × sectors + s.
SSD: no seek, no rotation.

6.2.2 Disk scheduling: FCFS, SSTF, SCAN, C-SCAN, LOOK, C-LOOK

FCFS: arrival order. SSTF: nearest next (starvation).
SCAN: sweep to the disk's end, reverse. LOOK: reverse at the last request.
C-SCAN: sweep to the end, jump to the other end, continue same direction. C-LOOK: jump from last request to the farthest one.
Running queue (head 53): FCFS 640, SSTF 236, SCAN ↓ 236 / ↑ 331, LOOK ↑ 299 / ↓ 208, C-SCAN ↑ 382, C-LOOK ↑ 322.

6.2.3 I/O techniques: programmed I/O, interrupts, DMA, buffering and spooling

Programmed I/O: CPU polls and moves data (busy waiting).
Interrupt I/O: CPU fraction = transfers/s × overhead per transfer.
DMA: one interrupt per block; cycle stealing fraction = words/s × memory cycle.
Buffer (in transit), double buffering, cache (copy for reuse), spool (queue of jobs for a non-sharable device).
Blocking, non-blocking, asynchronous I/O calls.