Operating Systems

Foundations

OS Roles

  • Resource Manager: Allocates CPU, memory, storage, and I/O devices efficiently and fairly among competing applications.

  • Abstraction Layer: Hides complex hardware details behind clean, uniform interfaces (e.g., files, sockets, processes).

  • Protection Boundary: Isolates programs from each other and the underlying hardware to maintain system stability and security.

Kernel vs. User Mode

  • Privilege Rings: Modern CPUs use hierarchical rings (typically Ring 0 for the kernel, Ring 3 for user applications) to restrict access to sensitive CPU instructions and memory.

  • System Call Mechanism: The controlled entry point for user applications to request kernel services (e.g., reading a file). It triggers a software trap/interrupt to switch from user mode to kernel mode safely.

Interrupts, Traps, and Exceptions

  • Interrupts: Asynchronous hardware events generated by external devices (e.g., I/O completion).

  • Traps (Software Interrupts): Synchronous events generated intentionally by software, primarily used for system calls.

  • Exceptions: Synchronous events caused by anomalous conditions during execution (e.g., division by zero, page faults).

  • Interrupt Vectors: An array of pointers to interrupt service routines (ISRs), indexed by interrupt type.

Kernel Structures

  • Monolithic: All OS services run in kernel space for high performance, but a bug anywhere can crash the entire system.

  • Microkernel: Minimal services in kernel space (IPC, basic scheduling); file systems and drivers run as user-mode servers for better fault isolation.

  • Hybrid: Combines monolithic performance with microkernel modularity (e.g., Windows, macOS), placing some critical services (like graphics drivers) in kernel space.

—

Processes & Threads

Process Abstraction

A process is a program in execution, consisting of: * Address Space: Virtual memory containing text, data, heap, and stack. * Process Control Block (PCB): Metadata tracking state, registers, PID, and open files. * State Diagram: Transitions between New, Ready, Running, Blocked (Waiting), and Terminated.

Context Switch Mechanics and Cost

Saving the state (registers, program counter) of the currently running process and loading the state of the next. This introduces overhead due to CPU register saving, TLB flushes, and cache pollution.

Threads vs. Processes

  • Threads: Lightweight execution units sharing the same process address space, heap, and open files, but maintaining independent stacks and registers.

  • User-level Threads: Managed entirely in user space via libraries; fast, but a blocking system call blocks the entire process.

  • Kernel-level Threads: Managed directly by the OS scheduler; allows true parallelism on multi-core CPUs.

Hierarchy and Lifecycle

  • Processes are created via system calls (e.g., fork()) forming a parent-child tree.

  • Termination occurs via exit(), with parents collecting exit status via wait().

—

Scheduling

Criteria and Metrics

  • Throughput: Number of processes completed per time unit.

  • Turnaround Time: Total time from submission to completion.

  • Response Time: Time from submission to the first response (crucial for interactive systems).

  • Fairness & Starvation: Ensuring every process gets fair CPU access without infinite delay.

Algorithms

  • FCFS (First-Come, First-Served): Non-preemptive, suffers from the convoy effect.

  • SJF / SRTF (Shortest Job First / Shortest Remaining Time First): Optimal average waiting time, requires future burst time estimation.

  • Priority Scheduling: Allocates CPU based on priority; vulnerable to starvation (solved by aging).

  • Round Robin (RR): Preemptive FIFO with a fixed time quantum.

  • Multilevel Feedback Queue (MLFQ): Dynamically adjusts process priorities based on CPU behavior and I/O wait times.

Multiprocessor Scheduling

  • Affinity: Keeping a thread on the same CPU core to preserve cache warmth.

  • Load Balancing: Distributing workload evenly across available cores.

—

Concurrency

Core Concepts

  • Race Conditions: Multiple threads accessing shared data concurrently, leading to unpredictable outcomes.

  • Critical Section: Code segment accessing shared resources that must execute mutually exclusively.

  • Mutual Exclusion Requirements: Progress, bounded waiting, and no assumptions about CPU speeds.

Hardware Primitives

Atomic instructions that cannot be interrupted mid-execution: * Test-and-Set * Compare-and-Swap (CAS)

Synchronization Mechanisms

  • Locks: Simple binary flags for mutual exclusion.

  • Semaphores: Integer variables supporting wait() (down) and signal() (up) for signaling and resource counting.

  • Condition Variables: Allow threads to sleep until notified of a state change.

  • Monitors: High-level abstractions combining shared data, locks, and condition variables.

Classic Problems & Deadlocks

  • Classic Problems: Producer-Consumer, Readers-Writers, Dining Philosophers.

  • Deadlock Conditions: Mutual exclusion, hold and wait, no preemption, and circular wait.

  • Handling Deadlocks: Prevention, Avoidance (Banker’s Algorithm), Detection, and Recovery.

  • Livelock & Starvation: Livelock involves active state changes without progress (unlike deadlocked waiting); starvation is indefinite postponement.

—

Memory Management

Addressing and Allocation

  • Address Binding: Translating symbolic addresses to logical, then physical addresses via the Memory Management Unit (MMU).

  • Contiguous Allocation: Memory split into fixed or variable partitions, suffering from internal and external fragmentation.

  • Paging: Fixed-size memory blocks (pages/frames) eliminating external fragmentation using page tables and Translation Lookaside Buffers (TLB).

  • Segmentation: Variable-size blocks based on logical program units (code, stack, heap).

Virtual Memory

  • Demand Paging: Loading pages into physical memory only when faulted.

  • Replacement Policies: FIFO, Optimal (Belady’s ideal), LRU, and approximations like the Clock (Second-Chance) algorithm.

  • Thrashing: Excessive page faulting where the OS spends more time swapping pages than executing instructions, mitigated by the Working Set Model.

—

Storage & File Systems

File Systems Architecture

  • File Abstraction & Metadata: Files provide a uniform byte-stream abstraction; metadata (inodes) tracks permissions, size, and timestamps.

  • Allocation Strategies: Contiguous, Linked, and Indexed (e.g., Unix inodes with direct/indirect blocks).

  • Free Space Management: Bitmaps, free lists, and linked counts.

  • Reliability: Journaling (write-ahead logging) for crash consistency, and RAID configurations for redundancy and performance.

Disk & SSD I/O

  • Disk Scheduling: FCFS, SSTF, and SCAN/C-SCAN to minimize mechanical head movement.

  • SSDs: Use flash memory with page-erase constraints, rendering mechanical disk scheduling obsolete and requiring wear-leveling and TRIM.

—

I/O & Protection

I/O Subsystem

  • Mechanisms: Polling, Interrupt-driven I/O, and Direct Memory Access (DMA).

  • Buffering & Caching: Smoothing out transfer rate differences between fast CPUs and slow I/O devices via spooling and caches.

Protection and Security

  • Access Control: Access Control Lists (ACLs) vs. Capabilities.

  • Principles: Principle of least privilege, authentication, and secure domain transitions.

  • Vulnerabilities: Buffer overflows and privilege escalation attacks.

—

Virtualization

Hypervisors and Containers

  • Virtual Machines (VMs): Emulate complete hardware systems via Type-1 (bare-metal) or Type-2 (hosted) hypervisors using trap-and-emulate or hardware-assisted virtualization.

  • Containers: Share the host OS kernel and use namespaces and cgroups for process and resource isolation, offering lightweight virtualization compared to VMs.