Operating Systems - Quick Revision

📌 Last-minute revision before interviews. Scan these points quickly. Each topic links to detailed coverage elsewhere in this book.

Process & Thread

Key Facts

• fork(): Creates child process (COW — copy-on-write). Returns 0 to child, child PID to parent.
• exec(): Replaces current process image with new program. Doesn’t create new PID.
• Zombie: Terminated process, parent hasn’t called wait(). Entry in process table. Freed when parent waits or terminates.
• Orphan: Parent terminated. Adopted by init (PID 1) or subreaper.
• Daemon: Background process, no controlling terminal (e.g., sshd, cron).

Process Control Block (PCB)

Contains all process state: PID, state, program counter, registers, memory maps, open files, scheduling info, accounting.

Scheduling

Algorithms Comparison

Round Robin — Time Quantum

• Too small → Excessive context switches, high overhead
• Too large → Degenerates to FCFS
• Sweet spot → 80% of CPU bursts should complete in one quantum

Linux CFS (Completely Fair Scheduler)

• Tracks virtual runtime (vruntime) per process
• Lower vruntime = higher priority = gets CPU next
• Uses red-black tree for O(log n) scheduling
• Nice values adjust vruntime rate

Synchronization

Primitives

Mutex vs Semaphore

Classic Problems

Deadlock

Four Necessary Conditions

All four must hold simultaneously:

Strategies

graph TD
    A[Deadlock Handling] --> B[Prevention]
    A --> C[Avoidance]
    A --> D[Detection + Recovery]
    B --> B1["Break one of 4 conditions"]
    C --> C1["Banker's Algorithm"]
    D --> D1["Resource Allocation Graph"]
    D --> D2["Kill process / preempt"]

Banker’s Algorithm

• Maintain: Available, Max, Allocation, Need matrices
• Before granting: check if system remains in safe state
• Safe state = exists a sequence where all processes can finish
• O(m × n²) per request

Memory Management

Paging vs Segmentation

Page Table

Virtual Address: [VPN | Page Offset]
                 ↓
          Page Table Lookup
                 ↓
Physical Address: [PFN | Page Offset]

Multi-level page tables: Save memory by not allocating entries for unmapped regions. 4-level in x86-64 (PGD → PUD → PMD → PTE).

TLB (Translation Lookaside Buffer)

• Cache of recent page table entries
• TLB hit: ~1 cycle. TLB miss: walk page table (~100 cycles)
• Typical: 64-1024 entries, fully associative
• ASID: Address Space ID to avoid flush on context switch
• TLB shootdown: Invalidate TLB entries across cores (expensive)

Page Replacement Algorithms

Thrashing

• Cause: Working set > available frames → constant page faults
• Symptom: High page fault rate, low CPU utilization
• Detection: Page fault frequency (PFF) — if rate exceeds threshold, allocate more frames
• Solution: Reduce degree of multiprogramming (swap out processes)

Virtual Memory

Demand Paging

• Pages loaded only when accessed (not at process start)
• Page fault: Page not in memory → trap to OS → load from disk → restart instruction
• Page fault cost: ~10ms (disk access) vs ~100ns (memory access) = 100,000× slower

Copy-on-Write (COW)

• fork() shares parent’s pages (read-only mapping)
• On write → page fault → copy the page → mark writable
• Optimization: fork() + exec() never copies (exec replaces image)

Memory-Mapped Files (mmap)

• Map file contents directly into virtual address space
• File I/O through memory operations (load/store)
• Page faults load file data on demand
• Shared mmap enables IPC

File System

Inode Structure

Inode:
  - File type, permissions, owner
  - Size, timestamps
  - Direct pointers (12 blocks)
  - Single indirect pointer (1 block of pointers)
  - Double indirect pointer (1 block → blocks of pointers)
  - Triple indirect pointer

Links

Journaling (Write-Ahead Logging)

• Before modifying metadata, write intent to journal
• Crash → replay journal for consistency
• Journal modes: Metadata only (fast) vs Full data+metadata (safe)
• ext4: ordered (default), writeback, journal

IPC (Inter-Process Communication)

Signals

Key Concepts

User Mode vs Kernel Mode

DMA (Direct Memory Access)

• Device transfers data directly to/from memory, bypassing CPU
• CPU sets up transfer (source, dest, size), DMA controller handles it
• CPU notified via interrupt when complete
• Essential for high-throughput I/O (disk, network)

Race Condition

• Non-deterministic behavior from unsynchronized concurrent access
• Example: Two threads incrementing shared counter without lock
• Solution: Mutex, semaphore, atomic operations

Priority Inversion

• High-priority thread waits on low-priority thread holding a lock
• Medium-priority thread preempts low-priority → high-priority indirectly waits
• Solution: Priority inheritance — temporarily boost low-priority to high-priority

Real-Time OS

Interview Questions

1. What happens when you type ls in a terminal? Shell forks, child calls exec("/bin/ls"), kernel loads ELF, sets up page tables, starts at _start → main(). Parent calls wait(). LS reads directory entries via getdents() syscall, writes to stdout.

2. Mutex vs Semaphore? Mutex: binary, has ownership (only locker can unlock), for mutual exclusion. Semaphore: counting, no ownership (any thread can signal), for resource pools or signaling. Use mutex to protect a critical section. Use semaphore to allow N concurrent accesses.

3. Explain virtual memory. Each process has its own virtual address space mapped to physical memory via page tables. Pages not in memory trigger page faults (load from disk). Enables: isolation, more memory than physical RAM, memory-mapped files, COW. TLB caches translations for speed.

4. What is thrashing? Working set exceeds available frames → constant page faults → CPU spends all time swapping. Detection: high page fault rate. Solution: reduce multiprogramming (kill/suspend processes), increase memory, or use working set model to allocate frames.

5. What is a zombie process? Terminated process whose parent hasn’t called wait(). Entry remains in process table. Created by: child exits before parent reads exit status. Cleaned by: parent calls wait()/waitpid(), or parent terminates (init adopts and waits). Harmless in small numbers but exhausts PID space if uncontrolled.

6. Hard link vs soft link? Hard link: same inode, different directory entry. Can’t cross filesystems. Survives deletion of original. Soft link: separate inode storing path. Can cross filesystems. Breaks if target is deleted. ln file hard vs ln -s file soft.

7. How does fork() work with copy-on-write? fork() creates child with shared (read-only) pages. Both parent and child point to same physical pages. On write → page fault → OS copies the page → marks writable. Optimization: if followed by exec(), no copying occurs (exec replaces entire address space).

8. What is priority inheritance? Solution to priority inversion. When a high-priority thread blocks on a lock held by a low-priority thread, the low-priority thread temporarily inherits the high priority. This prevents medium-priority threads from preempting the lock holder and causing unbounded blocking.

Quick Reference: Key Numbers

🔗 Cross-References

• OS Cheatsheet — Detailed reference
• OS Interview Questions — Full Q&A
• Memory Hierarchy — Cache details
• Processes & Threads — Deep dive
• Virtual Memory — Detailed coverage
• File Systems — Detailed coverage
• Deadlock — Detailed analysis

References

• Silberschatz et al., Operating System Concepts (10th Edition) — “The Dinosaur Book”
• Tanenbaum & Bos, Modern Operating Systems (4th Edition)
• CS:APP — Chapter 9: Virtual Memory, Chapter 12: Concurrent Programming
• Arpaci-Dusseau, Operating Systems: Three Easy Pieces — free online
• Love, Linux Kernel Development (3rd Edition) — Linux internals