Advanced Operating Systems — Comprehensive Week-by-Week Notes Summary & Study Notes

📘 Course Goals & Scope

Advanced OS focuses on design trade-offs, reading real kernel code, implementing OS mechanisms, and evaluating performance, scalability, and correctness. The course emphasizes connecting theory to real systems (Linux, xv6, microkernels) and developing a systems mindset that accounts for concurrency, failures, security, and hardware constraints.

⚖️ Design Tensions

Every OS design balances competing goals: performance vs. abstraction overhead, security vs. flexibility, simplicity vs. functionality, scalability vs. centralized control, and portability vs. hardware exploitation. There is no single correct design—only choices with different trade-offs.

🧩 OS as an Abstraction Layer

The operating system intermediates between hardware (CPU, memory, devices) and applications. Its job is to virtualize resources, enforce isolation, provide abstractions (process/thread, virtual address space, filesystem), and manage concurrency. Each abstraction eases programming but adds cost and complexity.

🏛 Kernel Architectures (Overview)

Common models: Monolithic kernels (fast, large trusted codebase), Microkernels (minimal kernel, better isolation, IPC overhead), and Exokernels (expose hardware, push complexity to applications). Hybrid kernels mix approaches for pragmatic trade-offs.

🔁 Concurrency as Fundamental

Modern OSes are inherently concurrent (multiple processes, CPUs, interrupts). Concurrency is not optional—it's central to OS correctness and performance. Small kernel bugs can be catastrophic, so understanding internals matters even if you don't write kernel code.

🛡 Role of the Kernel

The kernel is the privileged core responsible for managing hardware resources, enforcing protection, providing abstractions (processes, files, virtual memory), and mediating access between applications and hardware. Applications cannot access hardware directly—privileged operations go through the kernel.

👥 Kernel vs. User Space

Modern OSes separate execution into user space (unprivileged, application code) and kernel space (privileged, OS code). This separation is enforced by hardware privilege levels (e.g., x86 rings, ARM ELs, RISC-V modes) and prevents user code from performing privileged instructions or accessing kernel memory.

⚙️ Hardware Support for Privilege

CPUs provide mechanisms for isolation (rings/exception levels), enforce privileged instruction restrictions, memory access permissions, and controlled transitions between modes. These features underlie secure systemcall and interrupt handling.

🔁 System Calls: What & Why

A system call is the controlled user→kernel interface for privileged services (file ops, process control, memory management, device interaction). System calls provide argument validation, permission checks, and safe execution in kernel mode.

🚪 Invocation Mechanisms & Path

Invocation: trap-based (software interrupt/trap like x86 int 0x80, ARM SVC) or fast instructions (syscall/sysenter). Typical system call path: prepare arguments → execute syscall instruction → CPU switches to kernel → kernel dispatcher selects service → kernel executes (validate, check resources) → return to user with result. Kernel stacks are separate from user stacks for safety.

⏱ Performance & Security Considerations

System calls incur overhead (mode switch, cache/TLB effects). Optimizations: reduce syscalls, batch operations, shared memory, fast syscall instructions. System calls are also a major attack surface—strict validation, capability checks, and hardware mitigations (SMEP/SMAP/KPTI) help harden kernels.

🧭 Processes: The Unit of Isolation

A process is an instance of a program with its own address space, resources (file descriptors, sockets), execution context (registers, PC), and runtime attributes (PID, priority). Processes provide isolation and own OS-visible resources; they are created via fork, transformed via exec, and terminated via exit.

🔀 Threads: Concurrency Within a Process

A thread is a lightweight execution context that shares a process’s address space and resources but has its own stack and registers. Threads enable parallelism on multi-core systems and better overlap of computation and I/O.

👥 User vs Kernel Threads

User-level threads are managed in user space (fast switching but blocking syscalls block the whole process). Kernel-level threads are scheduled by the OS (can utilize multiple cores, more expensive to manage). Hybrid (M:N) models combine both approaches.

🔁 Context Switching Costs

A context switch saves the current state and loads another thread’s state; switching address spaces updates MMU/TLB and causes cache/TLB disruption. Schedulers try to minimize unnecessary switches due to this non-trivial cost.

🎯 Scheduling Objectives & Types

Schedulers balance CPU utilization, throughput, latency, fairness, and real-time constraints. Models include preemptive (timer-driven, responsive) and cooperative (tasks yield voluntarily). Common algorithms: Round-Robin, Priority scheduling, MLFQ, Linux CFS (proportional sharing), and real-time schemes (RM, EDF).

🧩 Multi-core & Virtualized Scheduling Challenges

Multi-core scheduling must consider affinity, cache locality, NUMA, and load balancing. Virtualization introduces nested scheduling (hypervisor vs guest), causing unpredictability and the need for cgroups, quotas, and CPU shares. Scheduling and synchronization interact closely (locks can block runnable tasks; priority inversion solutions may be required).

⚙️ Concurrency Problems & Correctness

Concurrency arises from multi-core execution, time-sliced scheduling, and interrupts. Key correctness issues: race conditions, data corruption, deadlocks, starvation, and priority inversion. These bugs are often non-deterministic and hard to reproduce.

🧯 Critical Sections & Atomicity

A critical section accesses shared mutable state and must be protected. Correct synchronization relies on hardware atomic operations (test-and-set, CAS, fetch-and-add, load-linked/store-conditional) and proper memory ordering semantics enforced with barriers.

🧠 Memory Consistency

Modern CPUs do not guarantee sequential consistency. Reordering, store buffers, and cache coherence vs memory consistency distinctions mean OS code must use memory barriers and atomic ops correctly to avoid subtle bugs.

🔒 Locks & Primitives

• Spinlocks: busy-wait, suitable for short critical sections and contexts where sleeping is illegal (kernel/interrupt contexts).
• Mutexes: put threads to sleep if unavailable—CPU-efficient for long waits but involve scheduler overhead.
• Semaphores and condition variables: for resource counting and waiting for conditions (used with mutexes).

🧩 Granularity, Deadlocks, Priority Inversion

Lock granularity trades simplicity for scalability: coarse-grained is simple but less scalable; fine-grained improves concurrency but is more complex. Deadlocks require four conditions (mutual exclusion, hold-and-wait, no-preemption, circular wait); handling strategies include prevention, avoidance, detection/recovery, or ignoring in some kernels. Priority inversion can be mitigated via priority inheritance or priority ceiling protocols.

🧪 Kernel Synchronization Techniques

Kernels use techniques tailored to constraints: spinlocks with interrupt disabling, per-CPU variables, lock-free data structures, and RCU (Read-Copy-Update) for read-mostly workloads. Some contexts cannot sleep, so blocking primitives are illegal.

🔁 Lock-Free & Wait-Free Algorithms

Lock-free algorithms ensure global progress using atomics (some threads may starve). Wait-free algorithms guarantee per-thread progress (stronger but much more complex). These are used selectively in high-performance or real-time code.

⚡ Reducing Synchronization Overhead

Optimize by reducing shared state, minimizing lock hold time, using per-thread/per-CPU data, preventing false sharing (cache-line padding), and favoring read-optimized structures. Correctness must come first; performance optimizations must preserve safety.

🧠 Motivation for Virtual Memory

Virtual memory (VM) gives each process the illusion of a large private contiguous address space. Goals: isolation, protection (R/W/X), abstraction from physical RAM, efficiency (support programs larger than physical memory), and flexibility (sharing, memory-mapped files, COW).

🔄 Address Translation & Paging

CPUs generate virtual addresses translated by the MMU to physical addresses via page tables. Paging divides memory into pages and frames (e.g., 4 KB). Page table entries (PTEs) include frame number, present/valid bit, permissions, accessed/dirty bits.

🏗 Multi-Level Page Tables & TLB

Multi-level page tables reduce memory overhead by allocating table pages on demand. The TLB caches recent virtual→physical translations to avoid costly walks. TLB misses cause page table walks; TLB shootdowns (invalidations on other cores) are expensive and limit scalability.

⚠️ Page Faults, Demand Paging, COW

A page fault occurs when a page is not present or permissions are violated. The OS handles faults by loading pages from disk or allocating memory and updating page tables. Demand paging loads pages lazily. Copy-on-write (COW) enables efficient fork: parent and child share pages read-only and private copies are made on write.

🗂 Memory-Mapped Files & Swapping

Files can be mapped into virtual memory for convenient I/O and IPC. When RAM is full, the OS swaps pages to disk and uses replacement policies: FIFO, LRU (approximate), Clock, and working-set methods. Poor choices cause thrashing (excessive paging, severe performance loss).

🔐 VM Security & Separation

VM enforces security via page-level permissions, non-executable (NX) pages, kernel/user separation, and ASLR (address space layout randomization). These mechanisms raise the cost of exploits like ROP and code injection.

🛠 Performance Overheads & Optimizations

Sources of VM overhead: TLB misses, page faults, cache effects (aliasing, eviction), and TLB shootdowns. Optimizations: huge pages (reduce PTEs and TLB misses), NUMA-aware placement, per-CPU page structures, and minimizing address-space switches. VM design balances performance, flexibility, and security.

✅ Summary

Virtual memory is essential for isolation and efficiency. Pagetables and the TLB enable fast translation; page faults drive demand paging and COW; VM affects both correctness and performance and must be carefully designed for scalability.