Operating Systems Cheatsheet

Processes vs Threads

Aspect	Process	Thread
Memory	Separate address space	Shared heap, own stack
Creation	Expensive (fork)	Cheap
Communication	IPC (pipes, sockets)	Shared memory (needs mutex)
Crash isolation	Crash doesn't affect siblings	One crash kills whole process

Process States

New → Ready → Running → Terminated
              ↑    ↓
              Waiting (Blocked) ← I/O / sleep / event

// New:      being created
// Ready:    in run queue, waiting for CPU
// Running:  executing on CPU right now
// Waiting:  blocked on I/O, lock, or event — CPU freed
// Terminated: finished or killed

CPU Scheduling Algorithms

Algorithm	Preemptive?	Key property	Weakness
FCFS	No	Arrival order	Convoy effect
SJF	No (SRTF = yes)	Optimal avg wait time	Starvation, burst time unknown
Round Robin	Yes	Fair; good response time	High overhead if quantum too small
Priority	Both variants	Important tasks first	Starvation (fix: aging)
MLFQ	Yes	Adapts to behaviour	Complex to tune; real OS standard

Memory — Virtual Memory & Paging

Virtual address → [Page Table] → Physical address (frame)

Page size: typically 4 KB
Page fault: page not in RAM → OS loads it from disk (swap)

TLB (Translation Lookaside Buffer): hardware cache of recent VA→PA
  translations; makes most address lookups O(1)

// Page Replacement (eviction when RAM full):
FIFO       — evict oldest loaded page; Bélády's anomaly possible
LRU        — evict least recently used; good in practice
Clock      — approximates LRU using reference bits; used in real OS
Optimal    — theoretical best; evict page used furthest in future

Synchronisation Primitives

// Mutex — one thread at a time in critical section
mutex.lock()
// critical section
counter++
mutex.unlock()

// Semaphore(n) — allows up to n threads concurrently
sem = Semaphore(10)   // e.g. DB connection pool
sem.wait()            // acquire (block if 0)
// use resource
sem.signal()          // release (wake waiter)

// Race condition: two threads read→increment→write same counter
// Without lock: both read 0, both write 1 → lost update

Deadlock — 4 Conditions (ALL must hold)

Condition	Meaning	Break it by…
Mutual Exclusion	Resource not shareable	Make resource shareable (e.g. read locks)
Hold & Wait	Holds resource, waits for more	Request all resources at once
No Preemption	Resources released voluntarily only	Allow OS to forcibly reclaim
Circular Wait	P1 waits for P2, P2 waits for P1	Always acquire locks in the same order

File System Concepts

Concept	Description
inode	File metadata (permissions, size, timestamps, data block pointers); not the filename
Hard link	Another directory entry → same inode; deleting one doesn't remove data
Soft link	File containing path to another file; breaks if target is deleted
Journaling	Log writes before executing; enables recovery after crash (ext4, NTFS)

Key Rules

Process = isolation. Thread = shared memory + cheap creation, but needs synchronisation.
Always acquire locks in a consistent global order to prevent circular wait (deadlock).
Page fault = not in RAM, must load from disk — expensive (~ms). TLB miss = must walk page table (~100ns).
LRU is the gold standard for page replacement; Clock algorithm is the practical approximation.
MLFQ is the basis of most real OS schedulers (Linux CFS is a variant).