.. include:: ../global.rst *************************** 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.