Operating System Concepts
Processes, threads, memory, scheduling, deadlocks, file systems & networking fundamentals
Core CS + Interview
A process is a running instance of a program. It has its own memory space, file descriptors, and resources.
Process States
┌─────────┐
create ──→ │ New │
└────┬────┘
↓
┌─────────┐ schedule ┌─────────────┐
│ Ready │ ──────────────→ │ Running │
└────┬────┘ ←────────────── └──────┬──────┘
↑ preempt / yield │
│ ↓
│ ┌──────────┐
└─── I/O complete ────── │ Waiting │
└──────────┘
│
The process terminates from ↓
Running state ──────────────→ ┌────────────┐
│ Terminated │
└────────────┘
Process Control Block (PCB)
OS maintains a PCB for each process containing:
- PID: Unique process identifier
- State: Current process state (new, ready, running, waiting, terminated)
- Program Counter: Address of next instruction
- CPU Registers: Saved register values during context switch
- Memory info: Page tables, segment tables
- Open files: File descriptor table
- Priority: Scheduling priority
Inter-Process Communication (IPC)
| Method | Description | Use Case |
|---|
| Pipe | Unidirectional byte stream between parent/child | Shell pipes: ls | grep |
| Named Pipe (FIFO) | Pipe with a name in filesystem, unrelated processes | Simple IPC between processes |
| Message Queue | Structured messages via kernel-managed queue | Decoupled communication |
| Shared Memory | Multiple processes access same memory region | High-speed data sharing (fastest) |
| Socket | Network or local communication endpoint | Client-server, network apps |
| Signal | Async notification (SIGTERM, SIGKILL, etc.) | Process control (kill, stop) |
When multiple threads/processes access shared resources, we need synchronization to prevent race conditions.
Critical Section Problem
A critical section is code that accesses shared resources. Requirements for a correct solution:
- Mutual Exclusion: Only one thread in the critical section at a time
- Progress: If no thread is in the CS, one waiting thread must be allowed in
- Bounded Waiting: No thread waits forever (no starvation)
Synchronization Primitives
| Primitive | Description | Use Case |
|---|
| Mutex (Lock) | Binary lock — only the owner can unlock | Protecting shared data (one writer at a time) |
| Semaphore | Counter-based — allows N concurrent accessors | Connection pool, rate limiting |
| Condition Variable | Wait until a condition is true (used with mutex) | Producer-consumer pattern |
| Read-Write Lock | Multiple readers OR one writer | Read-heavy workloads (caches, config) |
| Spinlock | Busy-wait loop instead of sleeping | Very short critical sections (kernel) |
| Atomic operations | Hardware-level indivisible operations (CAS) | Lock-free data structures, counters |
Classic Problems
- Producer-Consumer: Bounded buffer with semaphores — producer waits if full, consumer waits if empty
- Readers-Writers: Multiple readers can read simultaneously; writers need exclusive access
- Dining Philosophers: 5 philosophers, 5 forks — avoid deadlock with resource ordering or semaphores
A deadlock occurs when two or more processes are waiting for each other to release resources, and none can proceed.
Four Necessary Conditions (Coffman)
All four must hold simultaneously for deadlock:
- Mutual Exclusion: Resource held exclusively by one process
- Hold and Wait: Process holds resource while waiting for another
- No Preemption: Resources can't be forcibly taken away
- Circular Wait: Circular chain of processes each waiting for the next's resource
Handling Deadlocks
| Strategy | How | Trade-off |
|---|
| Prevention | Break one of the four conditions (e.g., ordered resource acquisition) | Restricts system, may reduce concurrency |
| Avoidance | Banker's algorithm — check if granting resource is safe | Requires advance knowledge of max needs |
| Detection & Recovery | Build wait-for graph, detect cycles, kill a process | Overhead of detection; may lose work |
| Ignore (Ostrich) | Assume deadlocks are rare, reboot if it happens | Used in most real systems (Linux, Windows) |
Memory Layout of a Process
High Address ─────────────────────────────
│ Stack │ ← grows downward (local vars, return addr)
│ ↓ │
│ (free space) │
│ ↑ │
│ Heap │ ← grows upward (malloc, new)
│──────────────────────────── │
│ Uninitialized Data (BSS) │ ← global vars = 0
│ Initialized Data (.data) │ ← global vars with values
│ Text (Code) │ ← compiled machine code (read-only)
Low Address ─────────────────────────────
Memory Allocation
| Type | Where | Lifetime | Speed |
|---|
| Stack | Stack segment | Function scope (auto) | Very fast (pointer bump) |
| Heap | Heap segment | Until explicitly freed | Slower (malloc/free overhead) |
| Static/Global | Data/BSS segment | Entire program lifetime | Allocated at load time |
Fragmentation
- External fragmentation: Free memory scattered in small blocks — total is enough but no single block fits. Fix: compaction, paging.
- Internal fragmentation: Allocated block is larger than needed — wasted space inside. Fix: smaller allocation units.
Each process gets its own virtual address space mapped to physical memory via page tables.
How It Works
- Virtual address space divided into fixed-size pages (typically 4 KB)
- Physical memory divided into frames (same size as pages)
- Page table maps virtual pages → physical frames
- TLB (Translation Lookaside Buffer): CPU cache for recent page table entries — speeds up translation
Page Fault
When a process accesses a page not in physical memory:
- CPU generates a page fault interrupt
- OS checks if the access is valid (segfault if not)
- OS finds a free frame (or evicts a page using replacement algorithm)
- OS reads the page from disk into the frame
- OS updates the page table and restarts the instruction
Benefits
- Isolation: Each process has its own address space — can't corrupt other processes
- Larger than physical: Programs can use more memory than physically available (swap to disk)
- Shared memory: Multiple processes can map the same physical frame (shared libraries)
- Lazy loading: Pages loaded only when first accessed (demand paging)
When physical memory is full and a new page is needed, which page do we evict?
| Algorithm | How It Works | Pros / Cons |
|---|
| FIFO | Evict the oldest page | Simple. Belady's anomaly (more frames can cause more faults). |
| Optimal (OPT) | Evict page not used for longest time in future | Best possible. Impossible in practice (requires future knowledge). |
| LRU | Evict least recently used page | Close to optimal. Expensive to implement perfectly. |
| Clock (Second Chance) | FIFO with reference bit — give each page a second chance | Good approximation of LRU. Used in real systems. |
| LFU | Evict least frequently used page | Works well for stable access patterns. |
🔑 Thrashing: When a process spends more time swapping pages than executing. Happens when working set exceeds available frames. Fix: increase memory, reduce multiprogramming, use better page replacement.