Operating Systems Cheat Sheet

Process vs Thread

Property	Process	Thread
Definition	A program in execution, with its own memory space	A lightweight unit of execution within a process
Memory	Separate address space per process	Threads of the same process share memory
Communication	Needs IPC (pipes, shared memory, sockets)	Direct, via shared memory — faster
Creation cost	Heavy — new address space	Light — shares parent process’s resources
Crash impact	One process crashing doesn’t affect others	One thread crashing can crash the whole process

Process states & PCB

New → Ready → Running → Terminated
              ↕
           Waiting (Blocked)

New       — process being created
Ready     — waiting for CPU allocation
Running   — instructions being executed
Waiting   — waiting for I/O or an event
Terminated — execution finished

The Process Control Block (PCB) stores: process ID, process state, program counter, CPU registers, CPU scheduling info, memory management info, and I/O status info — one PCB per process, used for context switching.

CPU scheduling algorithms

Algorithm	Strategy	Preemptive?	Starvation risk
FCFS (First Come First Served)	Run in arrival order	No	No, but poor avg wait time
SJF (Shortest Job First)	Run shortest burst time next	No	Yes — long jobs can starve
SRTF (Shortest Remaining Time First)	Preemptive version of SJF	Yes	Yes
Priority Scheduling	Highest priority runs first	Either	Yes — low priority can starve
Round Robin	Fixed time quantum per process, cyclic	Yes	No

Key formulas

Turnaround Time = Completion Time − Arrival Time
Waiting Time     = Turnaround Time − Burst Time
Response Time    = Time of first CPU allocation − Arrival Time

Round Robin — quantum size matters

Quantum too large  → behaves like FCFS (poor response time)
Quantum too small  → excessive context-switch overhead
Ideal quantum       → slightly more than the average burst time

Process synchronization

Critical section problem — 3 requirements

1. Mutual Exclusion — only one process in the critical section at a time
2. Progress          — a process outside the critical section can't block others from entering
3. Bounded Waiting    — a limit exists on how long a process waits before entering

Semaphores vs Mutex

Property	Semaphore	Mutex
Type	Integer variable (counting or binary)	Binary lock, ownership-based
Can be used by	Multiple threads, signaling between them	Only the thread that locked it can unlock it
Operations	wait() / P() decrements, signal() / V() increments	lock() / unlock()
Use case	Resource counting, thread signaling	Protecting a single shared resource

// Binary semaphore usage — classic mutual exclusion
wait(mutex);      // P() — decrement, block if 0
    // critical section
signal(mutex);    // V() — increment, wake a waiting process

Classic synchronization problems

Problem	Core challenge
Producer-Consumer	Producer must not add to a full buffer; consumer must not remove from an empty one
Readers-Writers	Multiple readers can read simultaneously; a writer needs exclusive access
Dining Philosophers	Avoid deadlock when philosophers need two shared forks each

Deadlock

The 4 necessary conditions (Coffman conditions)

1. Mutual Exclusion    — resource held exclusively by one process
2. Hold and Wait        — process holds a resource while waiting for another
3. No Preemption        — a resource can't be forcibly taken away
4. Circular Wait         — a closed chain of processes, each waiting on the next

Deadlock requires ALL FOUR to hold simultaneously —
breaking even one prevents deadlock.

Handling strategies

Strategy	Approach
Prevention	Ensure at least one Coffman condition can never hold
Avoidance	Grant a request only if the resulting state is still “safe” (Banker’s Algorithm)
Detection & Recovery	Allow deadlock, detect via resource-allocation graph, then recover
Ignore (Ostrich algorithm)	Assume it won’t happen — used by most general-purpose OSes (like Windows/Linux)

Memory management

Paging vs Segmentation

Property	Paging	Segmentation
Division basis	Fixed-size blocks (pages)	Variable-size logical units (segments)
Visibility to programmer	Invisible — purely a memory-management technique	Visible — matches logical program structure (code, stack, heap)
External fragmentation	None	Possible
Internal fragmentation	Possible (last page may be partially filled)	None

Logical Address → Page Number + Offset
Page Table maps: Page Number → Frame Number (physical memory)
TLB (Translation Lookaside Buffer) caches recent Page Table lookups for speed

Page replacement algorithms

Algorithm	Strategy
FIFO	Replace the oldest-loaded page
LRU (Least Recently Used)	Replace the page unused for the longest time
Optimal	Replace the page that won’t be used for the longest time in the future (theoretical best, used as a benchmark)

Belady’s Anomaly: with FIFO specifically, increasing the number of page frames can sometimes increase the number of page faults — a well-known exam trap, since it’s counter-intuitive and does NOT happen with LRU or Optimal.

Thrashing

Thrashing = system spends more time swapping pages in/out
             than executing actual instructions.

Cause: too many processes, too little physical memory
       → high degree of multiprogramming exceeds what RAM can support

Fix: reduce the degree of multiprogramming
     (working-set model, load control)

Disk scheduling

Algorithm	Strategy
FCFS	Service requests in arrival order
SSTF (Shortest Seek Time First)	Service the closest request to current head position
SCAN (Elevator)	Head moves in one direction, servicing requests, reverses at the end
C-SCAN	Like SCAN, but jumps back to the start instead of reversing — uniform wait time
LOOK / C-LOOK	Like SCAN/C-SCAN, but reverses at the last request, not the disk’s physical end

CDAC C-CAT — top OS exam traps

Trap	Rule
Process vs Program	A program is passive code on disk; a process is an active instance of that program in execution.
Belady’s Anomaly	Only occurs with FIFO page replacement — more frames can mean MORE page faults, not fewer.
Deadlock conditions	ALL 4 Coffman conditions are required simultaneously — breaking any one prevents deadlock.
Mutex vs Semaphore	Mutex has ownership (only the locker can unlock). Semaphore is a general counter, any thread can signal it.
SJF starvation	SJF and Priority Scheduling can starve long/low-priority jobs. FCFS and Round Robin cannot.
Internal vs External fragmentation	Paging → internal fragmentation. Segmentation → external fragmentation.
Banker’s Algorithm	Deadlock AVOIDANCE, not prevention — it checks safety before granting each request.
Context switch overhead	Too small a Round Robin quantum increases context-switch overhead, hurting overall throughput.
Thrashing fix	Reduce the degree of multiprogramming — adding more processes makes thrashing worse, not better.
TLB	Caches recent page-table lookups — a TLB hit avoids a full page-table memory access, which is the actual speed benefit.

PYQs are indicative of exam style, not guaranteed exact repeats.