05 - OS Fundamentals

Why This Matters for Temple

Temple (ex-Zomato founding team) builds high-concurrency backend services where understanding processes, threads, memory, and scheduling is non-negotiable. Expect questions on concurrency primitives, deadlock reasoning, and memory layout -- especially how they map to Node.js and real-world system design decisions.

---

Quick Reference

Scan this table in 5 minutes before your interview.

Topic	Key Points	Interview Tip
Process vs Thread	Process = isolated memory, thread = shared memory within process; threads are lighter but need synchronization	Use Node.js worker threads vs child processes as your concrete example
Deadlocks	4 Coffman conditions must ALL hold: mutual exclusion, hold & wait, no preemption, circular wait	Lead with prevention (break any one condition), not just detection
Virtual Memory	Page table maps virtual -> physical; demand paging loads pages on access; page fault triggers disk read	Draw the page table lookup diagram
Page Replacement	FIFO (simple, Belady's anomaly), LRU (most asked), Optimal (theoretical benchmark)	Be ready to trace LRU on a reference string
Stack vs Heap	Stack: LIFO, auto, fast, limited size; Heap: dynamic, GC/manual, fragmentation risk	const arr = [1,2,3] -- pointer on stack, array data on heap
Process Scheduling	FCFS (convoy effect), SJF (optimal avg wait, starvation), RR (time quantum, interactive), Priority (aging)	Know trade-offs, not just definitions
Mutex vs Semaphore	Mutex: binary, ownership (only locker unlocks); Semaphore: counting, no ownership, permits N access	Mutex = key to a single bathroom, Semaphore = parking lot with N spots
Producer-Consumer	Bounded buffer with mutex + two semaphores (empty + full)	Classic interview problem -- know the pseudocode cold

---

1. Process vs Thread

Process

An independent execution unit with its own memory space. Processes are isolated from each other by the OS -- one process crashing does not bring down another.

Characteristics:

• Own virtual address space (code, data, heap, stack)
• OS-managed resources (file descriptors, sockets, memory mappings)
• Communication requires IPC: pipes, sockets, shared memory, message queues
• Heavier to create and context-switch (full memory space swap)

Thread

A lightweight execution unit within a process. Threads share the process's memory space (heap, global data) but each has its own stack and register state.

Characteristics:

• Shared heap and global memory with other threads in the same process
• Own stack and program counter
• Cheaper to create and switch (no address space swap)
• Requires synchronization (mutexes, semaphores) to avoid race conditions

Comparison Table

Dimension	Process	Thread
Memory	Own address space	Shared within process
Creation cost	Heavy (fork, copy page tables)	Light (just a stack + registers)
Communication	IPC required (pipes, sockets, shared memory)	Direct shared memory access
Crash impact	Isolated -- other processes unaffected	Can crash entire process
Context switch	Expensive (TLB flush, page table swap)	Cheap (same address space)
Use case	Isolation, fault tolerance	Parallelism within a single task

Node.js Example: Worker Threads vs Child Processes

// Worker Thread -- shares memory, good for CPU-bound parallel work
import { Worker, isMainThread, workerData } from 'worker_threads';

if (isMainThread) {
  // SharedArrayBuffer allows zero-copy shared memory
  const shared = new SharedArrayBuffer(1024);
  const worker = new Worker(__filename, { workerData: { shared } });
  worker.on('message', (result) => console.log('Result:', result));
} else {
  // Worker can directly read/write shared memory
  const { shared } = workerData;
  const view = new Int32Array(shared);
  Atomics.add(view, 0, 42); // atomic operation on shared memory
}

// Child Process -- isolated, good for untrusted code or crash isolation
import { fork } from 'child_process';

const child = fork('./payment-processor.js');

// Communication via IPC (message passing, not shared memory)
child.send({ orderId: 123, amount: 299 });
child.on('message', (result) => console.log('Payment:', result));
child.on('exit', (code) => {
  if (code !== 0) console.log('Payment processor crashed, main app unaffected');
});

When to use which:

• Worker Threads: CPU-intensive tasks (image processing, parsing large JSON, crypto) where you want parallelism without process overhead
• Child Processes: Isolation-critical tasks (payment processing, plugin execution) where a crash must not affect the main process

---

2. Deadlocks

A deadlock occurs when two or more processes/threads are each waiting for a resource held by another, forming a circular dependency where none can proceed.

Four Coffman Conditions (ALL Must Hold)

Condition	Meaning	Example
Mutual Exclusion	Resource can only be held by one process at a time	A database row lock
Hold and Wait	Process holds at least one resource while waiting for another	Holding lock on row A, waiting for lock on row B
No Preemption	Resources cannot be forcibly taken from a process	Lock cannot be revoked by the OS
Circular Wait	P1 waits for P2, P2 waits for P1 (or longer cycle)	T1 holds A, wants B; T2 holds B, wants A

Deadlock Prevention (Break Any One Condition)

Condition to Break	Strategy	Trade-off
Mutual Exclusion	Use sharable resources (read locks, immutable data)	Not always possible for writes
Hold and Wait	Request all resources upfront before starting	Reduces concurrency, may hold resources longer than needed
No Preemption	Allow resource preemption (forcibly release locks on timeout)	Requires rollback capability
Circular Wait	Impose a global ordering on resources, always acquire in order	Requires discipline across codebase

Consistent lock ordering is the most practical prevention strategy:

async function transferFunds(fromId: number, toId: number, amount: number) {
  // Always lock the lower ID first -- prevents circular wait
  const [firstId, secondId] = fromId < toId
    ? [fromId, toId]
    : [toId, fromId];

  await db.transaction(async (trx) => {
    await trx.query('SELECT * FROM accounts WHERE id = $1 FOR UPDATE', [firstId]);
    await trx.query('SELECT * FROM accounts WHERE id = $1 FOR UPDATE', [secondId]);

    await trx.query('UPDATE accounts SET balance = balance - $1 WHERE id = $2', [amount, fromId]);
    await trx.query('UPDATE accounts SET balance = balance + $1 WHERE id = $2', [amount, toId]);
  });
}

Detection: Resource Allocation Graph / Wait-For Graph

The OS (or database) builds a directed graph:

• Resource Allocation Graph: Nodes are processes AND resources. Edges show assignments and requests.
• Wait-For Graph: Simplified -- nodes are processes only. Edge from P1 to P2 means "P1 is waiting for a resource held by P2."

A cycle in the wait-for graph = deadlock.

Wait-For Graph:

  T1 -------> T2
  ^            |
  |            v
  T4 <------- T3

  Cycle: T1 -> T2 -> T3 -> T4 -> T1  =  DEADLOCK

Recovery Strategies

Strategy	How It Works	Downside
Kill a process	Terminate one process in the cycle (the "victim")	Lost work, must retry
Rollback	Roll back one transaction to a safe checkpoint	Requires checkpoint mechanism
Preempt resources	Forcibly take a resource from one process, give it to another	Complex, may cause starvation

Victim selection criteria: Least work done, fewest resources held, lowest priority, most easily restartable.

Cross-reference: For database-specific deadlock detection and prevention (PostgreSQL wait-for graph, FOR UPDATE NOWAIT, lock ordering in SQL), see 04 - DBMS, Section 7: Deadlock Detection.

---

3. Memory Management

Virtual Memory

Why it exists: Gives each process the illusion of having its own large, contiguous address space, regardless of actual physical RAM available.

How it works:

1. Each process gets a virtual address space (e.g., 0 to 2^48 on 64-bit)
2. A page table maps virtual pages to physical frames
3. The MMU (Memory Management Unit) translates addresses in hardware
4. Pages not in RAM live on disk (swap space) and are loaded on demand

Virtual Address Space (Process A)     Physical RAM
┌──────────────────┐                  ┌──────────────────┐
│ Page 0 (code)    │ ───────────────> │ Frame 5          │
│ Page 1 (data)    │ ───────────────> │ Frame 2          │
│ Page 2 (heap)    │ ──── on disk ──> │ [swap]           │
│ Page 3 (stack)   │ ───────────────> │ Frame 8          │
└──────────────────┘                  └──────────────────┘
                    Page Table
                    ┌────────┬────────┬───────┐
                    │ Virtual│Physical│Present│
                    │ Page   │ Frame  │ Bit   │
                    ├────────┼────────┼───────┤
                    │ 0      │ 5      │ 1     │
                    │ 1      │ 2      │ 1     │
                    │ 2      │ --     │ 0     │ ← page fault if accessed
                    │ 3      │ 8      │ 1     │
                    └────────┴────────┴───────┘

Paging

Physical memory is divided into fixed-size frames; virtual memory is divided into same-size pages (typically 4 KB).

Page fault handling (demand paging):

1. Process accesses a virtual address
2. MMU checks page table -- present bit is 0
3. Page fault trap to OS
4. OS finds the page on disk, loads it into a free frame
5. OS updates the page table entry (present bit = 1, frame number set)
6. Instruction is restarted

Cost: Page faults are expensive (~milliseconds for disk I/O). A well-tuned system minimizes them through good locality and sufficient RAM.

Page Replacement Algorithms

When RAM is full and a new page must be loaded, the OS must evict an existing page.

Algorithm	How It Works	Pros	Cons
FIFO	Evict the oldest page (first loaded)	Simple to implement	Belady's anomaly (more frames can cause MORE faults)
LRU	Evict the least recently used page	Good approximation of optimal	Expensive to track exact usage (needs timestamps or stack)
Optimal	Evict the page that won't be used for the longest time	Fewest page faults possible	Impossible in practice (requires future knowledge); used as benchmark

LRU Trace Example (most commonly asked):

Reference string: 7, 0, 1, 2, 0, 3, 0, 4
Frames available: 3

Step | Ref | Frame 1 | Frame 2 | Frame 3 | Fault?
-----|-----|---------|---------|---------|-------
  1  |  7  |    7    |    -    |    -    |  Yes
  2  |  0  |    7    |    0    |    -    |  Yes
  3  |  1  |    7    |    0    |    1    |  Yes
  4  |  2  |    2    |    0    |    1    |  Yes  (evict 7, LRU)
  5  |  0  |    2    |    0    |    1    |  No   (0 already in frame)
  6  |  3  |    2    |    0    |    3    |  Yes  (evict 1, LRU)
  7  |  0  |    2    |    0    |    3    |  No   (0 already in frame)
  8  |  4  |    4    |    0    |    3    |  Yes  (evict 2, LRU)

Total page faults: 6

Stack vs Heap

Dimension	Stack	Heap
Allocation	LIFO, automatic (push/pop on function call/return)	Dynamic, manual or GC-managed
Speed	Very fast (pointer increment/decrement)	Slower (search for free block, fragmentation)
Size	Limited (typically 1-8 MB per thread)	Large (limited by virtual memory)
Lifetime	Scoped to function call	Until explicitly freed or GC'd
Fragmentation	None (contiguous, LIFO)	External fragmentation possible
Thread safety	Each thread has its own stack	Shared across threads, needs synchronization
What lives here	Primitives, function params, return addresses, local pointers	Objects, arrays, dynamically allocated data

Common Interview Question: What Happens When You Declare const arr = [1, 2, 3]?

const arr = [1, 2, 3];

Answer:

1. Stack: The variable arr (a pointer/reference, typically 8 bytes on 64-bit) is stored on the stack
2. Heap: The actual array data [1, 2, 3] is allocated on the heap (the JS engine, e.g. V8, manages this)
3. arr on the stack points to the heap address where the array lives
4. const prevents reassigning arr to a different reference, but the heap data is still mutable (arr.push(4) works)

Stack                          Heap
┌──────────────────┐           ┌──────────────────┐
│ arr: 0xABCD ─────┼──────────>│ [1, 2, 3]        │
│ (8 bytes)        │           │ (dynamic size)    │
└──────────────────┘           └──────────────────┘

This is why passing arrays/objects to functions is "pass by reference" (actually pass by value of the reference) -- the pointer is copied, not the data.

---

4. Process Scheduling

The OS scheduler decides which process/thread gets CPU time and for how long.

Key Metrics

• Turnaround Time: Completion time - Arrival time (total time in system)
• Waiting Time: Turnaround time - Burst time (time spent waiting, not executing)
• Response Time: Time from arrival to first execution (critical for interactive systems)
• Throughput: Number of processes completed per unit time

FCFS (First Come, First Served)

Non-preemptive. Processes execute in arrival order.

Process | Arrival | Burst
--------|---------|------
  P1    |    0    |  24
  P2    |    1    |   3
  P3    |    2    |   3

Gantt Chart:
|---- P1 (24) ----|-- P2 (3) --|-- P3 (3) --|
0                 24           27           30

Avg Waiting Time = (0 + 23 + 25) / 3 = 16.0

Problem: Convoy effect -- short processes stuck behind a long one. If P1 is a 24-unit CPU burst, P2 and P3 wait forever even though they only need 3 units each.

SJF (Shortest Job First)

Pick the process with the shortest burst time. Can be non-preemptive or preemptive (SRTF -- Shortest Remaining Time First).

Process | Arrival | Burst
--------|---------|------
  P1    |    0    |   6
  P2    |    1    |   2
  P3    |    2    |   8
  P4    |    3    |   3

Non-preemptive SJF:
|-- P1 (6) --|-- P2 (2) --|-- P4 (3) --|--- P3 (8) ---|
0            6            8           11              19

Avg Waiting Time = (0 + 5 + 9 + 8) / 4 = 5.5

Pros: Optimal average waiting time (provably). Cons: Starvation -- long processes may never run if short ones keep arriving. Requires knowing burst time in advance (in practice, estimated).

Round Robin (RR)

Each process gets a fixed time quantum (e.g., 4 units). After the quantum expires, the process is preempted and moved to the back of the ready queue.

Process | Arrival | Burst
--------|---------|------
  P1    |    0    |  10
  P2    |    0    |   4
  P3    |    0    |   6

Time Quantum = 4

Gantt Chart:
|-- P1 (4) --|-- P2 (4) --|-- P3 (4) --|-- P1 (4) --|-- P3 (2) --|-- P1 (2) --|
0            4            8           12           16           18           20

Avg Waiting Time = (10 + 4 + 8) / 3 = 7.33

Quantum trade-off:

• Too large -> degenerates into FCFS
• Too small -> excessive context switch overhead
• Rule of thumb: 80% of CPU bursts should be shorter than the quantum

Priority Scheduling

Each process gets a priority number. CPU goes to the highest priority process.

Problem: Starvation -- low-priority processes may never execute. Solution: Aging -- gradually increase the priority of waiting processes over time.

// Aging: every 1 second of waiting, increase priority by 1
interface Process {
  pid: number;
  priority: number; // lower number = higher priority
  waitTime: number;
}

function applyAging(processes: Process[]): void {
  for (const p of processes) {
    if (p.waitTime > 0) {
      p.priority = Math.max(0, p.priority - Math.floor(p.waitTime / 1000));
    }
  }
}

Comparison Table

Algorithm	Preemptive?	Starvation?	Best For
FCFS	No	No	Batch systems, simple workloads
SJF	Optional (SRTF is preemptive)	Yes (long jobs)	Minimizing average wait time
Round Robin	Yes	No	Interactive / time-sharing systems
Priority	Optional	Yes (low priority)	Mixed workloads with urgency levels
Multilevel Queue	Varies per queue	Possible	Separating interactive from batch

Real-World Context

Modern OS schedulers (Linux CFS -- Completely Fair Scheduler) don't use any single algorithm. They combine:

• Priority-based scheduling with dynamic priority adjustment
• Time-slice allocation proportional to priority (weighted fair queuing)
• CPU affinity to reduce cache misses on context switch

---

5. Concurrency Primitives

Mutex (Mutual Exclusion)

A binary lock with ownership. Only the thread that acquired the lock can release it.

Characteristics:

• Binary state: locked or unlocked
• Ownership: the locking thread must be the one to unlock
• Used to protect critical sections (one thread at a time)

class Mutex {
  private locked = false;
  private owner: number | null = null;
  private waitQueue: Array<() => void> = [];

  async acquire(threadId: number): Promise<void> {
    if (!this.locked) {
      this.locked = true;
      this.owner = threadId;
      return;
    }

    // Wait until lock is available
    return new Promise((resolve) => {
      this.waitQueue.push(() => {
        this.locked = true;
        this.owner = threadId;
        resolve();
      });
    });
  }

  release(threadId: number): void {
    if (this.owner !== threadId) {
      throw new Error('Only the lock owner can release the mutex');
    }

    if (this.waitQueue.length > 0) {
      const next = this.waitQueue.shift()!;
      next(); // wake up next waiting thread
    } else {
      this.locked = false;
      this.owner = null;
    }
  }
}

Semaphore

A counting lock with no ownership. Allows up to N concurrent accesses. Any thread can signal (release), not just the one that waited.

Characteristics:

• Integer counter initialized to N (max concurrent access)
• wait() (P operation): decrement counter; if < 0, block
• signal() (V operation): increment counter; if waiters exist, wake one
• No ownership: any thread can call signal

class Semaphore {
  private permits: number;
  private waitQueue: Array<() => void> = [];

  constructor(initialPermits: number) {
    this.permits = initialPermits;
  }

  async wait(): Promise<void> {
    if (this.permits > 0) {
      this.permits--;
      return;
    }

    return new Promise((resolve) => {
      this.waitQueue.push(() => {
        this.permits--;
        resolve();
      });
    });
  }

  signal(): void {
    this.permits++;
    if (this.waitQueue.length > 0) {
      const next = this.waitQueue.shift()!;
      next();
    }
  }
}

Comparison: Mutex vs Semaphore

Dimension	Mutex	Semaphore
Type	Binary (locked/unlocked)	Counting (0 to N)
Ownership	Yes (only locker can unlock)	No (any thread can signal)
Purpose	Protect a critical section	Limit concurrent access to N
Analogy	Key to a single bathroom	Parking lot with N spots
Deadlock risk	Yes (if not released)	Yes (if wait/signal mismatched)
Use case	Exclusive access to shared data	Connection pool, rate limiting, bounded buffer

Producer-Consumer Problem

The classic concurrency problem: producers add items to a bounded buffer, consumers remove them. Must handle:

• Buffer full: producer waits
• Buffer empty: consumer waits
• Concurrent access: only one thread modifies the buffer at a time

Solution: Mutex (for exclusive buffer access) + two semaphores (empty slots + filled slots).

Pseudocode:

  mutex    = Mutex()
  empty    = Semaphore(BUFFER_SIZE)   // tracks empty slots
  full     = Semaphore(0)             // tracks filled slots

  Producer:
    item = produce()
    empty.wait()          // wait for an empty slot
    mutex.acquire()       // exclusive buffer access
    buffer.add(item)
    mutex.release()
    full.signal()         // signal that a slot is now filled

  Consumer:
    full.wait()           // wait for a filled slot
    mutex.acquire()       // exclusive buffer access
    item = buffer.remove()
    mutex.release()
    empty.signal()        // signal that a slot is now empty
    consume(item)

TypeScript-like implementation:

class BoundedBuffer<T> {
  private buffer: T[] = [];
  private mutex = new Mutex();
  private empty: Semaphore;  // counts empty slots
  private full: Semaphore;   // counts filled slots

  constructor(private capacity: number) {
    this.empty = new Semaphore(capacity);
    this.full = new Semaphore(0);
  }

  async produce(item: T, threadId: number): Promise<void> {
    await this.empty.wait();          // block if buffer is full
    await this.mutex.acquire(threadId);
    this.buffer.push(item);
    this.mutex.release(threadId);
    this.full.signal();               // notify consumers
  }

  async consume(threadId: number): Promise<T> {
    await this.full.wait();           // block if buffer is empty
    await this.mutex.acquire(threadId);
    const item = this.buffer.shift()!;
    this.mutex.release(threadId);
    this.empty.signal();              // notify producers
    return item;
  }
}

// Usage
const buffer = new BoundedBuffer<string>(5);

// Producer
async function producer(id: number) {
  for (let i = 0; i < 10; i++) {
    const item = `item-${id}-${i}`;
    await buffer.produce(item, id);
    console.log(`Producer ${id} produced ${item}`);
  }
}

// Consumer
async function consumer(id: number) {
  while (true) {
    const item = await buffer.consume(id);
    console.log(`Consumer ${id} consumed ${item}`);
  }
}

Why the order matters: empty.wait() MUST come before mutex.acquire(). If reversed, a producer holding the mutex on a full buffer will block on empty.wait() while still holding the mutex -- deadlock, because the consumer cannot acquire the mutex to free a slot.

---

Interview Tips Summary

1. Process vs Thread: Start with the isolation/sharing trade-off, then give a concrete example (Node.js worker threads for CPU work, child processes for crash isolation).
2. Deadlocks: Name all four Coffman conditions. Lead with prevention (consistent lock ordering) over detection. Mention that PostgreSQL detects deadlocks automatically.
3. Memory: If asked "what happens when a variable is declared," walk through stack vs heap allocation. For const obj = {}, the pointer is on the stack, the object is on the heap.
4. Page replacement: Be ready to trace LRU on a reference string with N frames. Know that Optimal is the theoretical benchmark and FIFO has Belady's anomaly.
5. Scheduling: Know the convoy effect (FCFS), starvation (SJF/Priority), and the quantum trade-off (RR). Modern schedulers combine these with dynamic priority.
6. Concurrency: Mutex = ownership + binary, Semaphore = no ownership + counting. Know the producer-consumer solution with the correct wait/acquire ordering.