Operating Systems — Process, Scheduling, Deadlock, Memory
1. Process vs Thread
• Process — independent execution unit, own memory space (code, data, heap, stack)
• Thread — lightweight unit within a process, shares code/data/heap with sibling
threads, own stack + registers
• Context switch: process switch costlier (full memory map change) vs thread
switch (cheaper, shared address space)
2. Process States
New → Ready → Running → Waiting (Blocked) → Terminated - Ready→Running:
dispatched by scheduler - Running→Ready: time quantum expires (preemption) -
Running→Waiting: I/O or event wait - Waiting→Ready: I/O/event completes
3. CPU Scheduling Algorithms
Algorithm Type Key trait
FCFS Non-preemptive Simple, causes convoy
effect
SJF (Shortest Job First) Non-preemptive Optimal avg waiting time,
needs burst time prediction
SRTF Preemptive SJF Preempts if new process
has shorter remaining time
Round Robin Preemptive Fixed time quantum, fair,
quantum size critical (too
small→high overhead, too
large→behaves like FCFS)
Priority Scheduling Either Can cause starvation,
solved via aging
Multilevel Queue Either Separate queues per
process type, fixed priority
between queues
Key Formulas
• Turnaround Time = Completion Time − Arrival Time
• Waiting Time = Turnaround Time − Burst Time
• Response Time = Time of first CPU allocation − Arrival Time
4. Deadlock
Necessary Conditions (all 4 must hold — 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 — resource can’t be forcibly taken
4. Circular Wait — cycle of processes each waiting for resource held by next
Deadlock Handling Strategies
• Prevention — negate one of the 4 conditions structurally
• Avoidance — Banker’s Algorithm — grants request only if resulting state is “safe”
(safe sequence exists)
• Detection & Recovery — allow deadlock, detect via resource allocation graph cycle
check, recover by killing/preempting process
• Ignorance (Ostrich Algorithm) — assume it won’t happen (used by most real OSes
for simplicity, e.g. Linux, Windows)
Banker’s Algorithm — Safety Check
• Uses matrices: Allocation, Max, Need (Need = Max − Allocation), Available
• Find a sequence of processes where each can finish with Available + released
resources from earlier finished processes → if such sequence exists, state is safe
5. Memory Management
• Paging — divides memory into fixed-size frames (physical) and pages (logical), no
external fragmentation, has internal fragmentation
• Segmentation — divides by logical units (code, stack, heap segments), variable size,
no internal fragmentation, has external fragmentation
• Paging + Segmentation — combined approach used in many real systems
Page Replacement Algorithms
Algorithm Strategy
FIFO Replace oldest loaded page — suffers
Belady’s Anomaly (more frames can →
more faults)
Optimal (OPT) Replace page used farthest in future —
theoretical best, not implementable (needs
future knowledge)
LRU Replace least recently used page — good
approximation of OPT
LFU Replace least frequently used page
Belady’s Anomaly
• Increasing number of frames sometimes increases page faults (only occurs in FIFO,
not in stack-based algorithms like LRU/OPT)
6. Virtual Memory
• Demand Paging — pages loaded only when accessed (page fault triggers load from
disk)
• Thrashing — excessive page faulting due to insufficient frames, CPU utilization
drops sharply as processes spend more time swapping than executing
• Fixed via working set model or adjusting degree of multiprogramming
7. Synchronization
• Critical Section Problem — requires Mutual Exclusion, Progress, Bounded
Waiting
• Semaphore — integer variable, wait()/P() decrements, signal()/V() increments;
binary semaphore (0/1, mutex-like) vs counting semaphore
• Monitor — higher-level construct, encapsulates shared data + procedures +
condition variables, only one process active inside at a time
• Classic Problems: Producer-Consumer, Readers-Writers, Dining Philosophers — all
solvable via semaphores/monitors
8. Quick Distinctions
• Spooling vs Buffering — spooling handles speed mismatch between devices using
disk as buffer for jobs; buffering handles speed mismatch between
producer/consumer of data stream
• Multiprogramming (multiple jobs in memory, CPU switches on I/O wait) vs
Multitasking (rapid switching giving illusion of parallelism, usually time-sliced) vs
Multiprocessing (multiple CPUs, true parallelism)