Operating Systems
Process/thread management, scheduling, memory, deadlocks, and synchronization — the theory that underlies every "why is this slow / how does this scale" system design question.
1. Process vs Thread
- · Independent unit with its own memory address space
- · Heavyweight — expensive to create (fork) and context-switch
- · Isolated: a crash in one process doesn't affect another
- · Inter-process communication needs IPC (pipes, sockets, shared memory)
- · Lightweight unit of execution within a process
- · Shares heap, code, and file descriptors with sibling threads
- · Own stack, registers, and program counter
- · Cheap to create/switch but crash in one thread can kill the process
Why it matters: Threads share memory → fast communication but need synchronization (race conditions). Processes don't share memory → safe but communication is slower. This is exactly why Node.js uses a single-threaded event loop + worker processes, while Java uses a multi-threaded model with locks.
2. Process Lifecycle & CPU Scheduling
| Algorithm | How it works | Trade-off |
|---|---|---|
| FCFS (First Come First Serve) | Run processes strictly in arrival order, non-preemptive. | Simple but causes the convoy effect — one long process blocks all short ones behind it. |
| SJF / SRTF | Pick the process with shortest (remaining) burst time next. | Optimal average waiting time, but needs to know burst time in advance and can starve long processes. |
| Round Robin | Each process gets a fixed time quantum, then goes to back of queue. | Fair, good for interactive systems. Too small a quantum → excessive context switching overhead. |
| Priority Scheduling | Highest priority process runs first. | Can starve low-priority processes. Fixed with 'aging' — increase priority the longer a process waits. |
| Multilevel Feedback Queue | Multiple queues by priority; process demoted to lower queue if it uses full quantum. | Adapts to process behavior (I/O-bound vs CPU-bound). Used by real OS schedulers (Linux CFS is similar in spirit). |
3. Memory Management
Fixed-size blocks (pages/frames). No external fragmentation, but internal fragmentation (last page partially used). Enables non-contiguous allocation and swapping.
Variable-size logical units (code, stack, heap segments). Matches program structure but causes external fragmentation as segments are allocated/freed.
| Page Replacement | Rule | Trade-off |
|---|---|---|
| FIFO | Evict the oldest page loaded into memory. | Simple, but can suffer Belady's Anomaly (more frames → more page faults). |
| LRU (Least Recently Used) | Evict the page not used for the longest time. | Good approximation of optimal; needs extra bookkeeping (counters/stack) per access. |
| Optimal (Belady's) | Evict the page that won't be used for the longest time in the future. | Theoretical best — needs future knowledge, used only as a benchmark. |
| Clock (Second-Chance) | Circular list with reference bits; skip pages with bit=1 (clear it), evict bit=0. | Cheap approximation of LRU, used in real OS kernels (Linux, xv6). |
Thrashing: when a process spends more time swapping pages in/out than executing — happens when the working set doesn't fit in available frames. Fix: reduce degree of multiprogramming or increase RAM.
4. Deadlocks
- · Mutual exclusion — resource held by only one process at a time
- · Hold and wait — process holds a resource while waiting for another
- · No preemption — resource can't be forcibly taken away
- · Circular wait — a cycle of processes each waiting on the next
- · Prevention — break one of the 4 conditions (e.g. always acquire locks in a fixed global order to prevent circular wait)
- · Avoidance — Banker's Algorithm: only grant a resource request if the system stays in a "safe state"
- · Detection & Recovery — periodically build a wait-for graph, detect cycles, kill/rollback a process
- · Ostrich algorithm — ignore it (what most OSes do; rare enough that a reboot is cheaper)
5. Process Synchronization
| Primitive | Semantics | Use case |
|---|---|---|
| Mutex | Binary lock. Only the thread that acquired it can release it. | Protecting a single shared resource / critical section. |
| Semaphore (counting) | Integer counter; N threads can proceed concurrently. Any thread can signal (release). | Limiting concurrent access, e.g. a connection pool of size N. |
| Monitor | Language-level construct that bundles a lock + condition variables (wait/signal). | Higher-level synchronization, e.g. Java's synchronized + wait()/notify(). |
| Spinlock | Busy-waits in a loop instead of sleeping. | Very short critical sections on multi-core systems, avoids context-switch cost. |
Producers add to a bounded buffer, consumers remove. Use 2 semaphores (empty/full slots) + a mutex.
Many readers can read concurrently; writers need exclusive access. Watch out for writer starvation.
N philosophers, N forks, deadlock risk if all pick up their left fork simultaneously. Fix: odd/even ordering or a waiter/arbitrator.
6. Inter-Process Communication (IPC)
| Mechanism | How | Trade-off |
|---|---|---|
| Pipe | Unidirectional byte stream between related processes (parent/child). | Simple, but one-directional and limited to related processes (unless named pipe/FIFO). |
| Message Queue | Kernel-managed queue of discrete messages. | Decouples producer/consumer timing, but has size/throughput limits. |
| Shared Memory | Processes map the same physical memory region. | Fastest IPC (no copying/kernel calls) but needs explicit synchronization (semaphores). |
| Sockets | Bidirectional communication, works across machines (network) or locally (Unix domain sockets). | Most flexible and the only option across machines; higher overhead than shared memory. |
| Signals | Async notification (e.g. SIGKILL, SIGTERM) delivered to a process. | Good for simple control (stop/kill) not for data transfer. |
7. Common Interview Questions
A: The OS saves the current process/thread's CPU state (registers, program counter, stack pointer) into its PCB, then loads the next one's. Expensive because of the save/restore overhead plus cache/TLB pollution — the new process starts with cold caches, causing extra cache misses.
A: Unbounded thread creation exhausts memory (each thread reserves a stack, often 1-8MB) and causes excessive context switching once the CPU core count is exceeded. A bounded pool reuses threads and applies backpressure once saturated, protecting the system under load.
A: Each process gets its own virtual address space; the OS maps only the actively-used pages into physical RAM and keeps the rest on disk (swap). Page faults trigger the OS to load missing pages on demand — this is 'demand paging'.
A: Deadlock: a set of processes are permanently blocked, each waiting on a resource held by another in the cycle — nothing progresses. Starvation: a process is perpetually denied a resource (e.g. always outranked by higher-priority processes) even though the system as a whole keeps making progress.
A: The OS can preempt a thread mid-operation (e.g. between reading and writing a counter's value), interleaving with another thread's read/write — a race condition. Single-core doesn't prevent this because instructions like 'count++' aren't atomic (read-modify-write, 3 separate steps).
A: When fork() creates a child process, instead of copying the entire address space immediately, both processes share the same physical pages marked read-only. Only when either process writes to a page does the OS actually copy it. Makes fork() cheap — critical for how Unix spawns processes and how Redis takes snapshots (BGSAVE) without blocking.