RAPID EXAM REFERENCE · 1-PAGE SUMMARIES

Operating Systems Cheat Sheets

High-density reference sheets designed for the student with 10 minutes before an exam. Review core invariants, calculation formulas, and subtle traps across every major topic.

SUBJECT:Operating Systems (6 Topic Sheets)DBMS (Coming Soon)Computer Networks (Coming Soon)COA (Coming Soon)
Module 5: Deadlocks

Deadlocks & Banker's Algorithm Reference Sheet

Open Full Lesson →
Must-Remember Principles:
  • —4 Coffman Conditions must hold simultaneously: Mutual Exclusion, Hold & Wait, No Preemption, Circular Wait.
  • —Deadlock Prevention removes at least ONE Coffman condition before execution.
  • —Deadlock Avoidance checks resource request dynamically (Banker's Algorithm).
  • —Deadlock-Free Bound: M ≥ N · (K - 1) + 1 where N = processes, K = max demand each, M = available resources.
Mathematical Formulas:
Need[i][j] = Max[i][j] - Allocation[i][j]
Safety Condition: Need[i] ≤ Work
Work_new = Work_old + Allocation[i]
Critical Pitfalls & Exam Traps:
  • ×A cycle in a Resource Allocation Graph (RAG) is NOT sufficient for deadlock if multi-instance resources exist.
  • ×Safe state guarantees NO deadlock; unsafe state MIGHT lead to deadlock, but is not automatically deadlocked.
Module 3: CPU Scheduling

CPU Scheduling Algorithms & Metrics Reference Sheet

Open Full Lesson →
Must-Remember Principles:
  • —Turnaround Time (TAT) = Completion Time (CT) - Arrival Time (AT).
  • —Waiting Time (WT) = Turnaround Time (TAT) - Burst Time (BT).
  • —Response Time (RT) = Time when process first gets CPU - Arrival Time (AT).
  • —Shortest Job First (SJF) is mathematically optimal for minimum average WT.
  • —Round Robin performance depends heavily on time quantum q: if q is too large, it degrades to FCFS; if q is too small, context switch overhead dominates.
Mathematical Formulas:
TAT = CT - AT
WT = TAT - BT
Highest Response Ratio Next (HRRN): Ratio = (W + S) / S
Critical Pitfalls & Exam Traps:
  • ×In Round Robin, always break arrival ties using process arrival order or lower PID, never assume random order.
  • ×SRTF (Preemptive SJF) re-evaluates remaining time ONLY when a new process arrives or current completes.
Module 6: Memory Management

Memory Management, Paging & TLB Reference Sheet

Open Full Lesson →
Must-Remember Principles:
  • —Logical Address = Page Number (p) + Page Offset (d).
  • —Physical Address = Frame Number (f) + Page Offset (d).
  • —Page size MUST equal Frame size. Offset bits (d) are identical in logical and physical addresses.
  • —Number of Pages = Logical Address Space / Page Size.
  • —Page Table Size = Number of Pages · Page Table Entry (PTE) size.
Mathematical Formulas:
EMAT = h · (t_tlb + t_m) + (1 - h) · (t_tlb + (k + 1) · t_m)
k = Number of Page Table Levels (k=1 for single level, k=2 for two level)
Offset bits d = log2(Page Size in bytes)
Critical Pitfalls & Exam Traps:
  • ×Do not forget that accessing the page table in RAM takes t_m time per level.
  • ×If TLB lookup and memory access occur in parallel, formula changes to: EMAT = h · (t_m) + (1 - h) · (t_tlb + (k + 1) · t_m).
Module 7: Virtual Memory

Virtual Memory & Page Replacement Reference Sheet

Open Full Lesson →
Must-Remember Principles:
  • —Belady's Anomaly: For some page replacement algorithms (specifically FIFO), increasing the number of page frames can INCREASE the number of page faults.
  • —Stack algorithms (LRU, Optimal) CANNOT suffer from Belady's Anomaly because the set of pages in n frames is always a subset of pages in n+1 frames.
  • —Thrashing occurs when a process spends more time paging than executing (Sum of locality sizes > Total physical memory).
Mathematical Formulas:
Effective Access Time = (1 - p) · t_m + p · (Page Fault Service Time)
p = Page fault rate (typically < 0.001)
Critical Pitfalls & Exam Traps:
  • ×LRU requires hardware timestamp or stack support; clock algorithm (Second Chance) is its practical approximation.
  • ×Optimal page replacement requires future knowledge and is used only as an impossible benchmark.
Module 4: Concurrency

Process Synchronization & Semaphores Reference Sheet

Open Full Lesson →
Must-Remember Principles:
  • —3 Critical Section Requirements: Mutual Exclusion (mandatory), Progress (mandatory), Bounded Waiting (desirable).
  • —Counting Semaphore S: S > 0 indicates available resource units; S < 0 means |S| processes are currently blocked.
  • —Wait(S) or P(S): S = S - 1; if S < 0, block process.
  • —Signal(S) or V(S): S = S + 1; if S ≤ 0, wake one blocked process.
Mathematical Formulas:
Final S = Initial S - (P operations) + (V operations)
Blocked processes count = |S| when S < 0
Critical Pitfalls & Exam Traps:
  • ×Busy waiting semaphores (Spinlocks) waste CPU cycles; block-and-wake semaphores put processes into waiting state.
  • ×Swapping the order of wait(mutex) and wait(empty) in Producer-Consumer causes immediate DEADLOCK.
Module 9: I/O & Storage

Disk Scheduling & Unix Inode Reference Sheet

Open Full Lesson →
Must-Remember Principles:
  • —FCFS: Serves requests in arrival order; high seek time.
  • —SSTF: Selects request closest to current head position; susceptible to starvation of distant requests.
  • —SCAN (Elevator): Moves in one direction servicing requests until the end boundary cylinder, then reverses.
  • —C-SCAN (Circular SCAN): Moves in one direction to the end cylinder, then jumps directly back to the opposite start cylinder without servicing on return.
  • —LOOK / C-LOOK: Like SCAN / C-SCAN, but only travels as far as the last request in each direction (no boundary travel).
Mathematical Formulas:
Total Seek Distance = Sum of |Cylinder_{current} - Cylinder_{target}|
Unix Inode Max File Size = (Direct + Indirect · BlockPointers + DoubleIndirect · BlockPointers² + TripleIndirect · BlockPointers³) · BlockSize
Critical Pitfalls & Exam Traps:
  • ×In SCAN and C-SCAN, make sure to include the boundary cylinder (0 or Max-1) if specified in the question.
  • ×In LOOK and C-LOOK, NEVER travel to cylinder 0 or Max-1 unless there is an actual request at those cylinders.