Notes / Revision / 10-Minute Rapid Revision TIMED REVISION · 1-MINUTE PANIC SHEETS
Operating Systems 10-Minute Rapid Revision Designed specifically for the crucial minutes before entering the exam hall. High-yield memory anchors, core mathematical invariants, and ASCII execution flowcharts.
SUBJECT: Operating Systems (15 Panic Sheets) DBMS (Coming Soon) Computer Networks (Coming Soon) Algorithms (Coming Soon)
PANIC SHEET 01 · OS Foundations & Kernel Architecture
Why Operating Systems Exist: The Dual Role Full Lesson → CORE INVARIANT ANCHOR: “OS = Resource Manager (arbitrator of CPU, RAM, I/O) + Extended Machine (abstractor of hardware into files, sockets, processes).”
Must-Remember Principles: — Kernel execution is reactive: Invoked strictly via Interrupts, Traps, or System Calls. — Hardware provides the protection boundary (Mode Bit); the OS sets the policy. Critical Exam Pitfalls: — Compilers, linkers, shells, and web browsers are NOT part of the OS kernel; they are user applications. — Device drivers run with kernel privileges, making poorly written drivers the leading cause of OS crashes. PANIC SHEET 02 · OS Foundations & Kernel Architecture
Dual-Mode Execution, Hardware Protection & System Calls Full Lesson → CORE INVARIANT ANCHOR: “Mode Bit = 1 (User Mode, non-privileged); Mode Bit = 0 (Kernel Mode, all hardware instructions allowed).”
Must-Remember Principles: — Trap = Synchronous (User → Kernel via instruction: syscall, int, divide by 0). — Interrupt = Asynchronous (External device → Kernel: timer, disk, keyboard). — Privileged instructions: HLT, CLI/STI, modify page tables, direct I/O. Critical Exam Pitfalls: — Mode switch ≠ Context switch! Mode switch stays in the same process context (just switches user stack → kernel stack). — User code NEVER branches directly into kernel memory addresses; it vectors through the system call table. Visual Decision & Execution Invariant: [ DUAL-MODE HARDWARE EXECUTION FLOW ]
[ USER MODE (Mode Bit = 1) ]
Application issues system call e.g., read()
│
▼ (Software Trap / CPU INT 0x80 / syscall instruction)
[ HARDWARE PRIVILEGE ELEVATION ]
1. CPU hardware flips Mode Bit: 1 ──> 0
2. Saves User PC & Flags onto Kernel Stack
3. Vectors to Interrupt Descriptor Table (IDT)
│
▼
[ KERNEL MODE (Mode Bit = 0) ]
1. Kernel validates parameters & user memory bounds
2. Executes privileged hardware I/O routine
3. Prepares return value
│
▼ (sysret / iret instruction)
[ HARDWARE PRIVILEGE RESTORATION ]
1. CPU hardware flips Mode Bit: 0 ──> 1
2. Restores User PC & Registers
│
▼
[ USER MODE (Mode Bit = 1) ]
Application resumes execution immediately after syscall PANIC SHEET 03 · Processes, Threads & Concurrency
The Process Concept, Memory Layout & The PCB Full Lesson → CORE INVARIANT ANCHOR: “Process = Program in execution with isolated virtual address space (==yellow:Text + Data/BSS + Heap + Stack==) + ==purple:PCB==.”
Must-Remember Principles: — ==yellow:Stack grows DOWNWARD== (High → Low addresses); ==yellow:Heap grows UPWARD== (Low → High addresses). — Threads SHARE: ==green:Code, Globals/BSS, Heap, Open files==. — Threads KEEP PRIVATE: ==pink:Stack, Registers, Program Counter (PC)==. Critical Exam Pitfalls: — ==pink:Static variables (even inside a local function block) live in DATA/BSS==, never on the stack. — ==purple:PCB is maintained exclusively in kernel space==; user code cannot read or overwrite its own PCB. Visual Decision & Execution Invariant: [ PROCESS MEMORY HIERARCHY & THREAD ISOLATION INVARIANT ]
[ 0xFFFF: HIGH MEMORY ]
┌────────────────────────────────────────────────────────┐
│ STACK (Local function frames, return addresses) │ Grows DOWNWARD (↓)
├────────────────────────────────────────────────────────┤
│ │
│ UNALLOCATED VIRTUAL MEMORY │ (Collision triggers
│ │ Stack Overflow)
├────────────────────────────────────────────────────────┤
│ HEAP (Dynamic memory via malloc() / new) │ Grows UPWARD (↑)
├────────────────────────────────────────────────────────┤
│ BSS SEGMENT (Uninitialized global & static vars = 0) │
├────────────────────────────────────────────────────────┤
│ DATA SEGMENT (Initialized global & static vars) │
├────────────────────────────────────────────────────────┤
│ TEXT SEGMENT (Binary machine instructions - Read-Only)│
└────────────────────────────────────────────────────────┘
[ 0x0000: LOW MEMORY ]
THREAD INVARIANT:
SHARED across Threads : Text, Data, BSS, Heap, Open Files.
PRIVATE to Each Thread : Stack, Registers, Program Counter (PC). PANIC SHEET 04 · Processes, Threads & Concurrency
Process States & Transitions: 5-State vs 7-State Models Full Lesson → CORE INVARIANT ANCHOR: “5 States: ==yellow:New → Ready ⇄ Running → Terminated==. Running → Waiting → Ready. 7 States add ==purple:Ready-Suspend & Blocked-Suspend on Disk==.”
Must-Remember Principles: — Running → Waiting: Process blocks voluntarily for I/O or event. — Waiting → Ready: Event finished. Enters Ready queue. — Running → Ready: ==yellow:Preemption (Time slice expired or higher priority process arrived)==. — Blocked-Suspend → Ready-Suspend: ==pink:Event finishes while swapped to secondary storage==. — Medium-Term Scheduler: Controls degree of multiprogramming via ==green:swapping (RAM ⇄ Disk)==. Critical Exam Pitfalls: — Blocked/Waiting processes ==pink:NEVER jump directly to the CPU core== (Blocked → Running is impossible). — Non-preemptive OS has ==pink:NO Running → Ready transition== (processes run until voluntary block or exit). — Blocked-Suspend does ==pink:NOT become Ready in RAM== when I/O finishes; it becomes ==yellow:Ready-Suspend on Disk==! Visual Decision & Execution Invariant: [ 5-STATE & 7-STATE PROCESS LIFECYCLE DECISION FLOW ]
┌──────────────────────────────── PHYSICAL RAM ───────────────────────────────┐
│ │
│ [NEW] ──(Long-Term Admit)──> [READY] ◄──(Dispatcher Dispatch)──► [RUNNING] │
│ │ ▲ (Timer Preemption) │ │
│ │ │ │ │
│ (Swap Out) ▲ │ │ (Swap In) (I/O Wait) │ │
│ │ │ │ ▼ │
│ │ ▼ │ [WAITING] │
│ │ │ │ │
└───────────────────────────────┼────┼──────────────────────────────────┼─────┘
│ │ │
Medium- │ │ Medium- │ Swap Out
Term │ │ Term ▼ (Memory Pressure)
│ │
┌───────────────────────────────┼────┼──────── SECONDARY STORAGE (DISK) ──────┐
│ ▼ │ │
│ [READY-SUSPEND] ◄────(I/O Completes)──── [BLOCKED- │
│ (Disk Ready) SUSPEND] │
│ │
└─────────────────────────────────────────────────────────────────────────────┘ PANIC SHEET 05 · Processes, Threads & Concurrency
Context Switching: Kernel Execution & Hardware Overhead Full Lesson → CORE INVARIANT ANCHOR: “Context Switch = ==yellow:Save state of P0 to PCB0 → Scheduler selects P1 → Load state of P1 from PCB1==. ==pink:100% pure overhead==.”
Must-Remember Principles: — Process Context Switch: ==pink:Saves registers + Swaps page tables (CR3) + Flushes TLB==. — Thread Context Switch: ==green:Saves registers + stack pointer only. Page tables and TLB stay intact==. Critical Exam Pitfalls: — ==pink:CPU performs zero productive computation during a context switch==. — Decreasing time quantum q too much causes ==pink:context switch overhead to dominate CPU time (thrashing)==. Visual Decision & Execution Invariant: [ HARDWARE CONTEXT SWITCH FLOW: PROCESS P0 ──> PROCESS P1 ]
1. [ HARDWARE INTERRUPT ] Timer expires or P0 issues blocking syscall
2. [ KERNEL ENTRY ] CPU flips Mode Bit 1 ──> 0; jumps to interrupt handler
3. [ STATE SAVE ] Save P0 Registers, PC, SP, Flags into PCB_0 (Kernel RAM)
4. [ SCHEDULER EXECUTION ] Short-term CPU scheduler picks P1 from Ready Queue
5. [ MMU RECONFIGURATION ] Reload CR3 / Page Table Pointer to P1; Flush TLB
6. [ STATE RESTORE ] Load P1 Registers, PC, SP from PCB_1
7. [ KERNEL EXIT ] Execute iret; CPU flips Mode Bit 0 ──> 1
8. [ USER RESUMPTION ] P1 begins executing at restored Program Counter PANIC SHEET 06 · Processes, Threads & Concurrency
Inter-Process Communication: Pipes, Shared Memory & Message Passing Full Lesson → CORE INVARIANT ANCHOR: “Pipes: unidirectional byte stream between related processes. Shared Memory: fastest IPC (zero kernel copies), requires user sync. Message Passing: kernel-managed message queues with built-in sync.”
Must-Remember Principles: — Total processes after n consecutive fork() calls = 2^n. — Total NEW child processes created = 2^n - 1. — fork() return values: > 0 (Child PID) in Parent; == 0 in Child; < 0 on failure. — pipe(fd): fd[0] is read end, fd[1] is write end. Critical Exam Pitfalls: — Shared memory requires explicit synchronization (semaphores/mutexes). Forgetting sync causes race conditions. — Unclosed pipe ends cause processes to hang indefinitely waiting for EOF on read()! — Variables modified in child after fork() do NOT mutate the parent's memory (independent address spaces / Copy-On-Write). Visual Decision & Execution Invariant: [ IPC MECHANISMS ARCHITECTURE SPECTRUM ]
SHARED MEMORY (Fastest) MESSAGE PASSING (Safe)
Process A Process B Process A Process B
│ │ │ │
└───►[ Shared ]◄───┘ └──►[ Kernel Queue ]──►┘
[ Memory ] [ Message Buffer ]
• Zero kernel copies • System call per message
• User must synchronize • Built-in kernel synchronization
• High throughput • Ideal for distributed systems PANIC SHEET 07 · CPU Scheduling Algorithms
Scheduling Metrics & Criteria: Arrival, Burst, Turnaround & Waiting Full Lesson → CORE INVARIANT ANCHOR: “Always build Gantt chart → Find Completion Time (CT) → TAT = CT - AT → WT = TAT - BT.”
Must-Remember Principles: — TAT = CT - AT (Total time in system) — WT = TAT - BT (Time spent waiting in ready queue) — Response Time (RT) = First time getting CPU - AT Critical Exam Pitfalls: — Never subtract AT from BT directly; WT is derived from TAT! — Account for CPU idle gaps in the Gantt chart if no process has arrived. Visual Decision & Execution Invariant: [ CPU SCHEDULING DERIVATION PIPELINE ]
GANTT CHART TIMELINE
┌───────────┬───────────────┬───────────────┐
│ P1 │ IDLE │ P2 │
0 4 5 8
▲ ▲ ▲
P1 finishes Idle gap P2 finishes
(CT_1 = 4) (CT_2 = 8)
STEP 1: Read Completion Time (CT) directly off Gantt right-edge.
STEP 2: Turnaround Time (TAT) = CT - AT
STEP 3: Waiting Time (WT) = TAT - BT
STEP 4: Response Time (RT) = (First CPU allocation time) - AT PANIC SHEET 08 · CPU Scheduling Algorithms
FCFS & Round Robin Scheduling: Gantt Charts & Time Quantum Full Lesson → CORE INVARIANT ANCHOR: “FCFS = Non-preemptive, Convoy Effect. RR = Preemptive with Quantum q. Low q → high overhead; High q → FCFS.”
Must-Remember Principles: — If new process arrives at time t when P is preempted: New arrival queued before preempted process. — If burst <= quantum, process finishes early and next process dispatches immediately. Critical Exam Pitfalls: — Do not allow quantum to expire if process has less than q time remaining. Visual Decision & Execution Invariant: [ ROUND ROBIN TIME QUANTUM PREEMPTION DECISION TREE ]
Process P_i is currently running on CPU:
│
▼
Remaining Burst ≤ q ?
│
┌───────┴──────────────────────┐
│ Yes │ No
▼ ▼
P_i runs for RemainingBurst P_i runs for full Quantum q
Calls exit() Timer Interrupt fires!
[ TERMINATES ] Preempted to Ready Queue Tail
(behind newly arrived processes!) PANIC SHEET 09 · CPU Scheduling Algorithms
SJF, SRTF & Priority Scheduling: Optimal Turnaround & Starvation Full Lesson → CORE INVARIANT ANCHOR: “SJF minimizes average waiting time (provably optimal). SRTF is preemptive SJF. Priority scheduling requires aging to prevent starvation.”
Must-Remember Principles: — Exponential Smoothing: tau_(n+1) = alpha * t_n + (1 - alpha) * tau_n. — TAT = CT - AT; WT = TAT - BT. — SRTF re-evaluates scheduling whenever a new process arrives with remaining burst < current process. Critical Exam Pitfalls: — SJF is provably optimal for average waiting time among all non-preemptive algorithms, but cannot be implemented without predicting future burst time. — Priority Inversion: High priority process blocked waiting for resource held by low priority process. Fixed by Priority Inheritance Protocol (PIP). Visual Decision & Execution Invariant: [ SRTF PREEMPTION DECISION TREE ]
New Process P_new arrives at time t:
│
▼
Is Remaining_BT(P_new) < Remaining_BT(P_current) ?
│
├─ Yes ───> [ PREEMPT P_current ]
│ Save context, move P_current to Ready Queue
│ Dispatch P_new to CPU
│
└─ No ───> [ KEEP RUNNING P_current ]
Insert P_new into Ready Queue ordered by remaining BT PANIC SHEET 010 · Process Synchronization & Concurrency
The Critical Section Problem & Semaphores Full Lesson → CORE INVARIANT ANCHOR: “Critical Section requires: Mutual Exclusion (at most 1 in CS), Progress (no deadlock by non-CS processes), Bounded Waiting (no starvation). Peterson's algorithm solves CS for 2 processes. Semaphores solve CS for N processes.”
Must-Remember Principles: — Peterson: flag[i]=true; turn=j; while(flag[j] && turn==j); /* CS */ flag[i]=false; — wait(S) / P(S): S = S - 1; if (S < 0) block(); — signal(S) / V(S): S = S + 1; if (S <= 0) wakeup(process); — If S < 0: exactly |S| processes are sleeping in the blocked queue. If S >= 0: 0 processes blocked. Critical Exam Pitfalls: — Never confuse Mutual Exclusion with Progress (Progress prevents deadlock). — Peterson's algorithm satisfies all 3 criteria on sequential consistency, but needs memory fences on modern multicore hardware. — A binary semaphore initialized to 0 is used for signaling/synchronization (order enforcement), NOT mutual exclusion. Visual Decision & Execution Invariant: [ SEMAPHORE SYNCHRONIZATION EXECUTION FLOW ]
wait(S) / P-operation signal(S) / V-operation
│ │
▼ ▼
S = S - 1 S = S + 1
│ │
▼ ▼
Is S < 0 ? Is S ≤ 0 ?
┌────┴────────────┐ ┌────┴────────────┐
Yes │ No │ Yes │ No │
▼ ▼ ▼ ▼
[ Process joins [ Enter CS ] [ Dequeue & wake [ No process ]
Blocked Queue ] sleeping process ] [ was waiting] PANIC SHEET 011 · Deadlocks: Principles, Prevention & Avoidance
Deadlock Conditions, RAG & Banker's Algorithm Full Lesson → CORE INVARIANT ANCHOR: “Deadlock requires 4 Coffman conditions: Mutual Exclusion + Hold & Wait + No Preemption + Circular Wait.”
Must-Remember Principles: — Minimum resources to prevent deadlock: M >= sum(Max_i - 1) + 1 = N*(K - 1) + 1. — Banker's Algorithm: Need = Max - Allocation. Condition to execute: Need <= Available. — Cycle in Single-instance RAG = Deadlock. Cycle in Multi-instance RAG = Potential Deadlock. Critical Exam Pitfalls: — Unsafe State != Deadlock. Safe states are a subset of deadlock-free states. — Deadlock Prevention eliminates at least one Coffman condition; Deadlock Avoidance checks runtime safety via Banker's algorithm. Visual Decision & Execution Invariant: [ BANKER'S ALGORITHM SAFETY & RESOURCE-REQUEST FLOW ]
Incoming Request from Process P_i:
│
▼
Is Request_i ≤ Need_i ?
│ Yes │ No
▼ ▼
Is Request_i ≤ Available ? ───> [ ERROR: Process exceeded its maximum claim ]
│ Yes │ No
▼ ▼
Speculative Allocation: ───> [ WAIT: Insufficient available resources ]
Available' = Available - Request_i
Allocation' = Allocation + Request_i
Need' = Need - Request_i
│
▼
Run Safety Check:
Find sequence <P_1, P_2, ...> where Need_k ≤ Work
│
┌───┴────────────────────────┐
│ Safe Sequence Found │ No Safe Sequence Exists (Unsafe State)
▼ ▼
[ GRANT REQUEST TO P_i ] [ ROLLBACK SPECULATION & BLOCK P_i ] PANIC SHEET 012 · Main Memory Management & Paging
Paging, Multi-Level Page Tables & The TLB Full Lesson → CORE INVARIANT ANCHOR: “Paging eliminates external fragmentation. Virtual Address = Page Number (p) + Offset (d). Physical Address = Frame Number (f) + Offset (d).”
Must-Remember Principles: — Page Offset bits = log2(Page Size). — Number of Page Table Entries = 2^(Virtual Address Bits - Offset Bits). — Page Table Size = (Number of Entries) * (PTE size in bytes). — EMAT = h*(t_tlb + t_m) + (1-h)*(t_tlb + (k+1)*t_m) for k-level paging. Critical Exam Pitfalls: — Paging STILL suffers from INTERNAL fragmentation (on the very last frame of a process, avg 1/2 page size). — Offset bits never change between virtual and physical addresses. Visual Decision & Execution Invariant: [ VIRTUAL ADDRESS TRANSLATION & TLB PIPELINE ]
Virtual Address: [ Page Number (p) | Page Offset (d) ]
│
▼
Lookup in Hardware TLB
│
┌────────────┴────────────┐
▼ ▼
TLB HIT TLB MISS
[ Frame Number (f) [ Walk Page Tables in RAM ]
fetched in t_tlb ] [ (k memory accesses) ]
│ │
│ Cache (p → f) in TLB
│ │
└────────────┬────────────┘
▼
Physical Address: [ Frame Number (f) | Page Offset (d) ]
│
▼
Access Target Byte in Physical RAM (t_m) PANIC SHEET 013 · Virtual Memory & Page Replacement
Page Replacement Algorithms: FIFO, Belady's Anomaly, LRU & Optimal Full Lesson → CORE INVARIANT ANCHOR: “Virtual Memory decouples logical address space from physical RAM via Demand Paging. Page Fault = accessing a non-resident page (Valid bit = 0). Page Replacement = selecting a victim frame when RAM is full.”
Must-Remember Principles: — EMAT = (1 - p) * t_m + p * S (where S is page fault service time, p is fault rate). — FIFO: Evict oldest loaded frame. Suffers from Belady's Anomaly. — LRU: Evict frame unreferenced for longest past duration. Stack algorithm (no Belady's anomaly). — Optimal: Evict frame unreferenced for longest FUTURE duration (Theoretical lower bound). — Working Set Condition for No Thrashing: sum(WSS_i) <= Total Physical Frames. Critical Exam Pitfalls: — Belady's Anomaly = More frames → MORE page faults (can occur in FIFO, never in LRU or Optimal). — Dirty/Modify Bit: An evicted victim page only needs a slow disk write-back if its Dirty Bit = 1. — Thrashing: CPU utilization collapses while disk queue is 100% full. Fix by REDUCING multiprogramming! Visual Decision & Execution Invariant: [ VIRTUAL MEMORY & PAGE FAULT / REPLACEMENT LIFECYCLE ]
CPU generates Virtual Address: [ Page Number (p) | Offset (d) ]
│
▼
Lookup in Page Table Entry (PTE)
│
┌────────────────┴────────────────┐
▼ Valid bit = 1 ▼ Valid bit = 0
[ RAM HIT: Fetch Frame ] [ HARDWARE TRAP: Page Fault ]
│
▼
Is Address Legal in PCB?
│
┌────────────┴────────────┐
▼ No ▼ Yes
[ SIGSEGV Crash ] Is Free Frame in RAM?
│
┌────────────┴────────────┐
▼ Yes ▼ No
[ Allocate Frame ] [ PAGE REPLACEMENT ]
│ Select Victim Page:
│ • FIFO (oldest)
│ • LRU (least recent)
│ • OPT (longest future)
│ │
│ Victim Dirty?
│ ├─ Yes ──> Write to Swap
│ └─ No ──> Discard Frame
│ │
└──────────┬──────────────┘
▼
Read Page from Disk into Frame
│
▼
Set PTE (Valid = 1, Frame = f)
│
▼
Restart Faulting Assembly Instruction PANIC SHEET 014 · File Systems & Storage Architecture
Unix Inodes & File Allocation Methods Full Lesson → CORE INVARIANT ANCHOR: “Unix Inode: Direct pointers (small files fast) + Indirect pointers (large files supported).”
Must-Remember Principles: — Pointers per index block = Block Size / Pointer Size. — Max Blocks = Direct + (P) + (P^2) + (P^3). — Max File Size = (Max Blocks) * (Block Size). Critical Exam Pitfalls: — A file's name is NOT stored in its inode! File names are stored in directory entries mapping name → inode number. Visual Decision & Execution Invariant: [ UNIX INODE POINTER HIERARCHY & MAXIMUM CAPACITY ]
INODE STRUCTURE (Fixed-size metadata header):
┌─────────────────────────────────────────────────────────────┐
│ [ Direct Pointers 0–11 ] ───> Data Blocks │ (12 × BlockSize)
├─────────────────────────────────────────────────────────────┤
│ [ Single Indirect ] ───> Index Block │
│ │ │
│ ▼ │
│ Data Blocks │ (P × BlockSize)
├─────────────────────────────────────────────────────────────┤
│ [ Double Indirect ] ───> Index Block │
│ │ │
│ ▼ │
│ Index Blocks │
│ │ │
│ ▼ │
│ Data Blocks │ (P² × BlockSize)
├─────────────────────────────────────────────────────────────┤
│ [ Triple Indirect ] ───> Index → Index → Data Blocks │ (P³ × BlockSize)
└─────────────────────────────────────────────────────────────┘
* P = (Block Size in Bytes) / (Pointer Size in Bytes) PANIC SHEET 015 · I/O Systems & Disk Scheduling
Disk Scheduling: SSTF, SCAN, C-SCAN & LOOK Full Lesson → CORE INVARIANT ANCHOR: “Disk Scheduling minimizes Seek Time. Seek time = physical arm movement across tracks.”
Must-Remember Principles: — SSTF: Greedy, picks closest request. Suffers from starvation. — SCAN: Elevator algorithm. Moves to end cylinder (0 or Max), reverses. — LOOK: Reverses at the farthest request (does not go to physical boundary). — C-SCAN / C-LOOK: Unidirectional service with fast return jump. Critical Exam Pitfalls: — SCAN visits cylinder 0 or 199 even if no request exists there. — LOOK reverses at the last actual request, saving head travel. Visual Decision & Execution Invariant: [ DISK SCHEDULING ALGORITHMS TRAJECTORY COMPARISON ]
Platter Cylinders: [ 0 ──────────────── 53 (Head) ──────────────── 199 ]
• FCFS: Jumps haphazardly to whatever arrives first (highest seek time).
• SSTF: Greedy jump to nearest cylinder (starvation for distant cylinders).
• SCAN: [ 53 ──────────> 199 (Disk Edge) ] ──reverses──> [ 37 ──────> 14 ]
* Always reaches extreme boundary (0 or 199)!
• LOOK: [ 53 ──────────> 183 (Last Request) ] ──reverses──> [ 37 ────> 14 ]
* Reverses at the farthest request without wasting travel to edge.
• C-SCAN: [ 53 ──> 199 ] ──fast jump to 0 (no service)──> [ 0 ──> 14 ──> 37 ]
• C-LOOK: [ 53 ──> 183 ] ──fast jump to 14 (no service)──> [ 14 ──> 37 ]