OS Theory¶
Core Theory — Intro OS (one semester)¶
Foundations¶
OS roles: resource manager, abstraction layer, protection boundary¶
An operating system manages computer resources such as the CPU, memory, storage, and devices. It provides simpler abstractions that allow programs to use hardware without controlling it directly. The OS also acts as a protection boundary to prevent programs from interfering with each other or the system.
Kernel vs user mode, privilege rings, system call mechanism¶
Operating systems separate privileged kernel code from less-privileged user programs. User programs use system calls to request services from the kernel, such as creating files or allocating memory. Privilege levels help prevent normal applications from performing dangerous operations directly.
Interrupts, traps, exceptions; interrupt vectors¶
Interrupts allow hardware or software to notify the CPU that an event needs attention. Traps and exceptions are events generated by software or by the CPU when something unusual occurs. An interrupt vector tells the processor where to find the code responsible for handling a particular event.
Monolithic vs microkernel vs hybrid structure¶
A monolithic kernel places most operating system services inside the kernel, providing high performance but creating a larger privileged codebase. A microkernel keeps the kernel small and moves many services into user space. Hybrid kernels combine ideas from both designs to balance performance, modularity, and reliability.
Processes & Threads¶
Process abstraction: address space, PCB, state diagram¶
A process is a running program with its own address space and operating system resources. The process control block (PCB) stores information the OS needs to manage the process. Processes typically move through states such as new, ready, running, blocked, and terminated.
Context switch mechanics and cost¶
A context switch occurs when the CPU stops running one process or thread and begins running another. The operating system must save the current execution state and restore the state of the next task. Context switches take time and can reduce performance because they do not directly perform useful application work.
Threads vs processes; user-level vs kernel-level threads¶
Threads are smaller units of execution that can share resources within the same process. Processes have separate address spaces, while threads in the same process normally share memory. User-level threads are managed by a library, while kernel-level threads are managed directly by the operating system.
Process creation/termination, parent-child hierarchy¶
Processes can create new processes, forming parent-child relationships. The operating system provides mechanisms for starting, managing, and terminating processes. When a process terminates, the OS must clean up its resources and handle its relationship with its parent and children.
Scheduling¶
Criteria: throughput, turnaround, response, fairness, starvation¶
CPU scheduling determines which ready process or thread should run next. Important goals include high throughput, low turnaround time, fast response time, and fair CPU allocation. A good scheduler should also prevent starvation, where a task waits indefinitely for CPU time.
Algorithms: FCFS, SJF/SRTF, priority, round robin, multilevel feedback queue¶
FCFS runs processes in the order they arrive, while SJF selects the shortest available job. Priority scheduling chooses tasks based on priority, and Round Robin gives each task a limited time slice. Multilevel feedback queues use multiple priority levels and can adjust priorities based on how processes behave.
Preemptive vs non-preemptive; convoy effect, priority inversion¶
Preemptive scheduling allows the OS to interrupt a running process and give the CPU to another process. Non-preemptive scheduling allows a process to keep the CPU until it finishes or voluntarily gives it up. Problems such as the convoy effect and priority inversion can reduce performance or cause lower-priority tasks to interfere with higher-priority tasks.
Multiprocessor scheduling basics: affinity, load balancing¶
Multiprocessor scheduling involves distributing work across multiple CPU cores. CPU affinity allows a process or thread to remain on a particular CPU, which can improve cache performance. Load balancing attempts to distribute tasks evenly so that no CPU remains unnecessarily idle while another is overloaded.
Concurrency¶
Race conditions, critical section, mutual exclusion requirements¶
A race condition occurs when the result of a program depends on the timing of concurrent operations. A critical section is a part of a program that accesses shared data and must be protected from simultaneous execution. Mutual exclusion ensures that only one thread can execute a protected critical section at a time.
Atomicity and hardware primitives (test-and-set, compare-and-swap)¶
An atomic operation completes as one indivisible action that cannot be interrupted halfway through. CPUs provide instructions such as test-and-set and compare-and-swap to help implement synchronization mechanisms. These primitives allow software to safely coordinate access to shared resources.
Locks, semaphores, condition variables, monitors¶
Locks allow only one thread at a time to access protected resources. Semaphores use counters to control access to shared resources and coordinate threads. Condition variables and monitors provide higher-level mechanisms for allowing threads to wait for and signal specific conditions.
Classic problems: producer-consumer, readers-writers, dining philosophers¶
The producer-consumer problem involves coordinating processes that produce and consume items from a shared buffer. The readers-writers problem focuses on safely allowing multiple readers while controlling access by writers. The dining philosophers problem demonstrates challenges involving shared resources, synchronization, and deadlock.
Deadlock: four necessary conditions, resource allocation graphs, prevention/avoidance/detection/recovery¶
Deadlock occurs when processes become permanently blocked while waiting for resources held by one another. It requires four conditions: mutual exclusion, hold and wait, no preemption, and circular wait. Operating systems can prevent, avoid, detect, or recover from deadlocks using techniques such as Banker’s algorithm and resource allocation graphs.
Livelock and starvation as distinct from deadlock¶
Livelock occurs when processes continue changing their state but make no useful progress. Starvation occurs when a process waits indefinitely because other processes continue receiving the resources it needs. Unlike deadlock, these situations do not necessarily involve processes permanently waiting for each other.
Memory Management¶
Address binding, logical vs physical addresses, MMU¶
Address binding determines how program addresses are mapped to locations in memory. Logical addresses are generated by programs, while physical addresses refer to actual locations in RAM. The memory management unit (MMU) performs address translation and helps enforce memory protection.
Contiguous allocation, fragmentation, internal/external, compaction¶
Contiguous allocation places a process in one continuous region of memory. Internal fragmentation occurs when allocated memory contains unused space, while external fragmentation occurs when free memory is split into small separated regions. Compaction can move allocated regions together to create larger areas of contiguous free space.
Paging: page tables, multi-level tables, TLB, translation cost¶
Paging divides virtual memory into fixed-size pages and physical memory into frames. Page tables store mappings between virtual pages and physical frames, while multi-level tables reduce the amount of memory needed for large page tables. A translation lookaside buffer (TLB) caches recent translations to make address translation faster.
Segmentation; segmented paging¶
Segmentation divides a program’s address space into logical sections such as code, data, and stack. Each segment can have its own size and protection permissions. Segmented paging combines segmentation with paging to provide logical organization while still using fixed-size pages for physical memory management.
Virtual memory: demand paging, page faults, locality¶
Virtual memory allows programs to use an address space that is larger than the available physical memory. Demand paging loads pages into RAM only when they are needed, with a page fault occurring when a required page is not currently present. Programs usually exhibit locality, meaning they tend to access the same or nearby memory locations repeatedly.
Replacement policies: FIFO, optimal, LRU and approximations, clock¶
Page replacement policies determine which page should be removed when memory is full. FIFO removes the page that has been in memory the longest, while LRU attempts to remove the page that has not been used recently. Clock and other approximations provide lower-cost ways to approximate LRU behavior.
Belady’s anomaly¶
Belady’s anomaly is a situation where increasing the number of available memory frames can actually increase the number of page faults. It can occur with certain replacement algorithms, particularly FIFO. This demonstrates that adding more memory does not always improve performance under every replacement policy.
Working set model, thrashing, frame allocation¶
The working set is the collection of pages a process is actively using during a period of time. Thrashing occurs when the system spends too much time moving pages between memory and storage instead of executing programs. Frame allocation determines how many physical memory frames should be given to each process.
Storage & File Systems¶
File abstraction, metadata, directory structures¶
A file provides a way for programs to store and access data on persistent storage. File metadata contains information such as the file’s size, permissions, owner, and timestamps. Directories organize files into structures that allow users and programs to locate them.
Allocation strategies: contiguous, linked, indexed (inodes)¶
Contiguous allocation stores a file’s blocks next to each other, providing fast access but making expansion difficult. Linked allocation connects file blocks together, allowing files to grow more easily but making random access slower. Indexed allocation uses an index structure, such as an inode, to keep track of a file’s data blocks.
Free space management, block size tradeoffs¶
File systems need to track which storage blocks are available for new data. Common methods include bitmaps and free lists. Larger blocks can improve transfer efficiency but may waste more space, while smaller blocks reduce wasted space but can require more metadata and operations.
Disk geometry, scheduling, and how SSDs invalidate it¶
Traditional hard drives have physical characteristics such as tracks, sectors, and moving heads that affect access time. Disk scheduling algorithms such as FCFS, SSTF, SCAN, and C-SCAN attempt to reduce the time spent moving the disk head. SSDs have no moving parts, so these traditional seek-based scheduling concerns are much less important.
Journaling, consistency and crash recovery¶
Journaling records information about filesystem changes before those changes are fully committed. If a system crashes, the journal can help the filesystem determine which operations need to be completed or rolled back. This helps maintain filesystem consistency after unexpected shutdowns.
RAID levels as reliability/performance tradeoffs¶
RAID combines multiple storage drives to improve performance, reliability, or both. Different RAID levels use techniques such as striping, mirroring, and parity in different ways. Each level provides different tradeoffs between usable storage capacity, performance, and protection from drive failures.
I/O¶
Device controllers, polling vs interrupt-driven vs DMA¶
Device controllers manage communication between the operating system and hardware devices. Polling requires the CPU to repeatedly check whether a device needs attention, while interrupts allow the device to notify the CPU. Direct Memory Access (DMA) allows devices to transfer data directly to memory with less CPU involvement.
Device driver abstraction, blocking vs non-blocking I/O¶
Device drivers provide software interfaces that allow the operating system to communicate with specific hardware. Blocking I/O causes a program to wait until an operation completes, while non-blocking I/O allows the program to continue executing. This distinction affects how programs handle slow devices and concurrent operations.
Buffering, caching, spooling¶
Buffering temporarily stores data while it is being transferred between components with different speeds. Caching keeps frequently used data in faster storage so it can be accessed more quickly. Spooling places data into a queue so devices such as printers can process requests one at a time.
Protection & Security¶
Protection domains, access matrix, ACLs vs capabilities¶
Protection mechanisms control which users and programs can access system resources. An access matrix represents which subjects can perform which operations on specific objects. Access control lists store permissions with each resource, while capabilities associate permissions with the entities that hold them.
Authentication, principle of least privilege¶
Authentication verifies the identity of a user or system before granting access. The principle of least privilege means users and programs should receive only the permissions they actually need. Limiting permissions reduces the potential damage caused by mistakes or compromised accounts.
Common attack surfaces: buffer overflow, privilege escalation¶
An attack surface consists of the parts of a system that could potentially be exploited by an attacker. Buffer overflows can occur when a program writes beyond the space allocated for a buffer. Privilege escalation occurs when an attacker gains permissions beyond those they were originally authorized to have.
Virtualization¶
Virtual machines, hypervisor types, trap-and-emulate¶
Virtual machines allow multiple operating systems to run on the same physical hardware. A hypervisor manages the virtual machines and controls their access to hardware resources. Trap-and-emulate allows privileged operations from a guest operating system to be intercepted and safely handled by the hypervisor.
Containers vs VMs — isolation mechanism differences¶
Virtual machines provide isolation by giving each guest operating system a virtualized hardware environment. Containers share the host operating system’s kernel while isolating applications and their resources. Containers are generally lighter and faster to start, while VMs typically provide stronger separation between operating systems.