Operating Systems experimental

Operating Systems From the bare metal up: processes and threads, virtual memory, schedulers, file systems and system calls, against a small interactive kernel. Processes and threads. Processes and threads. Explain scheduling units and context switches.. Distinguish a process from a thread by what each does and does not share, and evaluate whether a given workload change would increase or decrease context-switch overhead.. Processes, Threads, Context switch, The process table Processes A process is a running program: its code, its data, its stack, and the kernel-side bookkeeping that makes it independent of every other process. Each process gets its own virtual address space, so a bug in one program cannot silently corrupt another. The kernel represents a process with a process control block (PCB), holding its process ID, saved register state, memory-management pointers (page table base), open file descriptors, and its current state: *new*, *ready*, *running*, *blocked* (waiting on I/O or an event), or *terminated*. A single CPU core runs exactly one process at a time; the illusion of many programs running simultaneously comes from the kernel rapidly switching between them. Threads A thread is a schedulable unit of execution *within* a process. Threads in the same process share the address space, open files, and heap, but each thread keeps its own stack, register set, and program counter. Because threads share memory, communication between them is cheap (no copying, no kernel involvement for shared reads/writes) but dangerous: concurrent access to shared data requires explicit synchronization (locks, semaphores) to avoid races. A process with one thread is the common case for simple programs; a web server or database typically runs many threads to overlap I/O waits with useful CPU work. Context switch A context switch is the kernel saving the full execution state of the currently running thread (registers, program counter, stack pointer) into its process control block or thread control block (TCB) and restoring the saved state of the next thread to run. This happens on a timer interrupt (preemption), a blocking system call (e.g., waiting on disk), or a voluntary yield. Context switches are not free: saving/restoring registers costs cycles, and switching between processes (as opposed to threads in the same process) also means changing the active page table, which flushes the cached address translations held in the translation lookaside buffer (TLB) and causes a burst of expensive memory lookups afterward. Frequent, unnecessary context switching is a real source of performance loss, which is why schedulers try to balance responsiveness against switching overhead. The process table The kernel keeps every process's PCB in a process table, a core data structure that the scheduler, memory manager, and system-call handlers all read and update. Looking up a process by ID, deciding who runs next, and cleaning up resources when a process exits are all table operations. When a process terminates before its parent collects its exit status, it lingers as a *zombie* entry in this table, a reminder that process lifecycle management is a first-class kernel responsibility, not just an implementation detail. Kernel threads versus user-level threads Not every threading implementation maps threads onto the kernel one-to-one. Early threading libraries multiplexed many user-level threads onto a single kernel-visible thread (an M:N or pure user-level model), which made thread creation and switching extremely cheap since no kernel involvement was needed, but at the cost that one thread blocking on a system call could stall the entire process, since the kernel had no visibility into the other user-level threads waiting behind it. Linux's Native Portable Operating System Interface (POSIX) Thread Library, merged into the mainline kernel in 2003, standardized a 1:1 model instead, mapping every user thread to a real kernel-scheduled thread; this trades some creation and switching overhead for the guarantee that a blocking call in one thread never stalls its siblings, a trade-off most general-purpose operating systems now make the same way. fork() and copy-on-write Unix's fork() system call creates a new process by duplicating the calling process's entire address space, and naively copying every page immediately would be wasteful, since most forked processes call exec() moments later and discard the copy entirely. Modern kernels instead implement fork() with copy-on-write: the child's page table initially points at the exact same physical frames as the parent, marked read-only, and only when either process actually writes to a shared page does the kernel intercept the resulting page fault and allocate a private copy for the writer. This means a fork() followed immediately by exec(), the single most common Unix process-creation pattern, touches almost no extra physical memory at all, since the address space it briefly duplicated is discarded before most of its pages are ever copied. Related CCI capabilities Computer Architecture (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/computer-architecture/). Optics Primer Series (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/optics/). Maths Refresher Series, Finance (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/maths-finance/). System Dynamics (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/system-dynamics/). CCI Lab: Run it, build with it, read the thinking, reuse the data. (https://www.cambridgecyberinternational.com/en/insights/lab/) Virtual memory. Virtual memory. Reason about paging and address translation.. Explain how a virtual address is translated to a physical address via the page table and TLB, and compute the resulting physical address or TLB miss count for a stated access sequence.. Address spaces, Page tables, TLB, Page faults Address spaces Every process sees memory through its own virtual address space: a private range of addresses from 0 up to some maximum, independent of where its data physically lives in RAM. The kernel and hardware memory-management unit (MMU) translate every virtual address into a physical address before the memory bus is touched. This indirection buys isolation (one process cannot read or write another's memory unless explicitly shared), a stable layout for the compiler and linker to target, and the ability to run more virtual memory than physical RAM exists, by keeping only the pages a process actually needs resident at any moment. Page tables Address spaces are divided into fixed-size pages (commonly 4 KiB), and physical memory into matching frames. A page table, one per process, maps each virtual page number to a physical frame number, plus permission bits (readable, writable, executable) and a present/valid bit. Translating an address means splitting it into a page number and an offset, looking up the page number to get a frame number, then appending the offset unchanged. Real page tables are multi-level trees rather than one flat array, because a flat table for a 64-bit address space would itself be larger than physical memory; multi-level tables let large unused regions of the address space cost nothing. TLB Walking a multi-level page table on every access would be far too slow, so the MMU caches recent translations in the translation lookaside buffer (TLB), a small, fast, fully-associative cache. A TLB hit turns translation into a single lookup; a TLB miss forces a full page-table walk, which is dramatically slower. Because the TLB caches translations for a specific address space, switching processes generally invalidates it, which is one reason context switches between processes cost more than switches between threads sharing a page table. Page faults A page fault occurs when the MMU finds a translation whose valid bit is unset: the page is not currently mapped to a frame. The kernel's fault handler determines why: the page may be legitimately backed by disk (swapped out, or not yet loaded from an executable), in which case the kernel allocates a frame, loads the data, updates the page table, and resumes the faulting instruction; or the reference may be illegal, in which case the process receives a segmentation violation. Page faults are what make demand paging and swapping possible: programs run with only a fraction of their pages resident, fetching the rest lazily, at the cost of a fault's latency the first time each page is touched. Huge pages and TLB pressure A standard 4 KiB page size means a process with a large working set needs many page-table entries and, more importantly, many TLB entries to keep its hot pages translated without a table walk; once the working set exceeds what the TLB can hold, performance degrades from repeated TLB misses even though physical memory itself is not scarce. Huge pages address this directly by mapping a much larger contiguous region (commonly 2 MiB or 1 GiB on x86-64) with a single TLB entry instead of hundreds or thousands of 4 KiB entries; Linux's transparent huge pages feature, merged into the mainline kernel in 2011, automates this for suitable workloads without requiring an application to request huge pages explicitly, trading some internal fragmentation for substantially fewer TLB misses on memory-intensive programs. The working set model and thrashing Peter Denning's 1968 working set model formalized a specific way to reason about how much memory a process needs resident at once: the working set is the set of pages a process has referenced within a recent window of time, and a process runs efficiently only when its entire working set fits in the frames the kernel has allocated to it. When too many processes compete for too little physical memory, each process's working set no longer fits, so nearly every memory access triggers a page fault, and the system spends almost all of its time servicing faults rather than doing useful work, a pathological state Denning named thrashing. Kernels detect and mitigate thrashing by monitoring each process's page-fault rate and reducing the number of concurrently resident processes (or their allotted frames) when fault rates spike, rather than continuing to add more competing processes to an already oversubscribed pool of physical memory. Related CCI capabilities Computer Architecture (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/computer-architecture/). Optics Primer Series (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/optics/). Maths Refresher Series, Finance (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/maths-finance/). System Dynamics (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/system-dynamics/). CCI Lab: Run it, build with it, read the thinking, reuse the data. (https://www.cambridgecyberinternational.com/en/insights/lab/) Scheduling. Scheduling. Compare scheduler policies.. Distinguish FIFO, round-robin, priority, and real-time scheduling policies by their trade-offs, and evaluate which policy best fits a stated workload.. FIFO and round-robin, Priorities, Fairness, Real-time FIFO and round-robin The simplest scheduling policy, first-in-first-out (FIFO), runs processes to completion in arrival order. It is trivial to implement and has no switching overhead beyond what's necessary, but a single long-running process can force everything behind it to wait (the classic *convoy effect*), which makes average turnaround time badly unpredictable when job lengths vary. Round-robin fixes the responsiveness problem by giving each ready process a fixed time quantum and cycling through them; a process that doesn't finish within its quantum is preempted and moved to the back of the ready queue. Round-robin gives good response time for interactive workloads, but the quantum size matters: too large and it degenerates toward FIFO; too small and context-switch overhead dominates useful work. Priorities Real workloads are not equally important. Priority scheduling always runs the highest-priority ready process, which lets the kernel favor latency-sensitive work (audio, input handling) over background batch jobs. The hazard is starvation: a low-priority process can wait indefinitely if higher-priority work keeps arriving. Kernels mitigate this with aging, gradually raising the priority of processes that have waited a long time, so that eventually every process is guaranteed to run. Priority inversion, where a low-priority process holding a lock blocks a high-priority one, is a related hazard solved with priority inheritance protocols. Fairness A scheduler is fair if no ready process is denied CPU time indefinitely and, ideally, if processes with equal claims receive roughly equal shares of the CPU over time. Completely Fair Scheduler (CFS)-style designs track each process's accumulated virtual runtime and always pick the process that has received the least service so far, which approximates an ideal of every process progressing at the same rate. Fairness and low-latency responsiveness are often in tension with maximizing total throughput, since strict fairness can mean more context switches than a policy that lets long jobs run uninterrupted. Real-time Some systems must guarantee that a task completes by a deadline, not just get to it eventually: a flight-control loop or an audio-buffer refill cannot be "eventually fast enough." Real-time schedulers such as rate-monotonic scheduling (fixed priority by period, shorter period = higher priority) and earliest-deadline-first (dynamic priority by nearest deadline) are designed around provable schedulability: given task periods and execution times, can every deadline be met? This is a fundamentally different goal from throughput or average-case fairness, and general-purpose schedulers are usually unsuitable for hard real-time guarantees without a dedicated real-time class layered on top. Multi-level feedback queues A multi-level feedback queue scheduler, first formalized in the Compatible Time-Sharing System developed at MIT beginning in 1961, combines the responsiveness of round-robin with an adaptive approximation of priority scheduling: a process starts in a high-priority queue with a short time quantum, and if it uses its full quantum without blocking (a sign it is CPU-bound rather than interactive), it is demoted to a lower-priority queue with a longer quantum. This lets interactive processes, which typically block quickly on I/O and rarely exhaust a quantum, stay in the fast, responsive top queues, while CPU-bound batch jobs sink to slower queues where switching overhead matters less relative to their long runtimes, all without the kernel needing to know in advance which category a given process belongs to. Scheduling on multi-core systems A single ready queue shared across many CPU cores becomes a scalability bottleneck once core counts grow, since every core contends for the same lock to pick its next process; modern kernels instead give each core its own local ready queue and only periodically rebalance load between cores, a design Linux calls per-CPU run queues with load balancing. This introduces a new question single-core scheduling never faced: when a process becomes runnable, which core should it run on. Migrating a process to an idle core improves latency but discards the cache state (the working data still warm in that process's previous core's cache), so schedulers weigh cache affinity against load balance, generally preferring to keep a process on the core it last ran on unless the imbalance across cores grows large enough to justify the migration cost. Related CCI capabilities Computer Architecture (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/computer-architecture/). Optics Primer Series (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/optics/). Maths Refresher Series, Finance (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/maths-finance/). System Dynamics (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/system-dynamics/). CCI Lab: Run it, build with it, read the thinking, reuse the data. (https://www.cambridgecyberinternational.com/en/insights/lab/) File systems and syscalls. File systems and syscalls. Trace a syscall end to end.. Explain the division of responsibility between an inode and a directory entry, and construct the correct sequence of steps a read() system call takes from user space to data return.. File abstractions, Inodes, System calls, User/kernel boundary File abstractions A file system presents a uniform abstraction (files and directories) over wildly different underlying storage. To a program, a file is just a named byte stream you open, read, write, seek within, and close; the kernel hides whether those bytes live on a solid-state drive (SSD), a spinning disk, a network share, or nowhere at all (a pipe or device file). Directories are themselves just files whose contents map names to the underlying objects they refer to, forming the tree that users navigate. This abstraction is what lets the same open/read/write calls work identically whether the target is /etc/passwd, a Universal Serial Bus (USB) drive, or /dev/null. Inodes Beneath the human-readable path, a Unix-style file system identifies every file by an inode: a fixed-size on-disk structure holding the file's metadata (owner, permissions, size, timestamps, link count) and the pointers to the data blocks that hold its actual contents. Crucially, the inode does *not* store the file's name; names live in directory entries that map a filename to an inode number. This separation is why a file can have multiple hard links (several directory entries pointing at one inode) and why deleting a file only frees its inode and blocks once its link count reaches zero and no process still holds it open. System calls A system call is the controlled gateway by which a user-space program asks the kernel to perform a privileged operation: opening a file, reading bytes, allocating memory, sending a network packet. The program cannot simply jump into kernel code; instead it executes a special trap instruction (historically int 0x80, more recently syscall/sysenter) with a syscall number and arguments placed in registers. This traps into the kernel at a controlled entry point, so user code can never bypass the kernel's checks by jumping to arbitrary kernel addresses. User/kernel boundary The CPU itself enforces the user/kernel boundary through privilege levels (rings): user-space code runs unprivileged and cannot execute instructions that touch hardware directly or change page-table mappings for other processes. The trap instruction that begins a system call switches the CPU into kernel mode, at which point the kernel's syscall handler validates the requested operation and arguments, performs the privileged work, and copies any result back into user-space memory before executing a return-from-trap instruction that drops the CPU back to user mode. Every trip across this boundary costs a mode switch, which is why chatty use of small system calls is a common performance trap, and why buffering libraries exist to batch user-space work between kernel crossings. Journaling and crash consistency A file system update often requires several separate on-disk writes (updating a data block, an inode, and a directory entry), and a crash or power loss between those writes can leave the file system in an inconsistent state, such as an inode pointing at a block that was never actually written. Journaling file systems, such as ext3, which added journaling to the earlier ext2 design in 2001, address this by first writing a compact description of the intended changes to a dedicated journal log, and only after that log write is durably committed does the file system apply the actual changes; on recovery after a crash, the kernel replays any committed-but-not-yet-applied journal entries and discards any incomplete ones, avoiding the lengthy full-disk consistency scan earlier Unix file systems required after an unclean shutdown. Reducing syscall overhead with the vDSO Not every operation that looks like it needs the kernel actually requires a full trap and mode switch. The virtual dynamic shared object, a small piece of kernel-provided code mapped read-only into every process's address space, lets certain frequently called, read-only operations, such as reading the current time, execute entirely in user space by reading a kernel-updated memory location directly, skipping the trap instruction, syscall dispatch, and return-from-trap entirely. For a function called extremely often, such as a timestamp lookup inside a tight logging loop, this optimization can turn a fixed per-call mode-switch cost into a plain memory read, illustrating that the boundary between user and kernel space is deliberately punctured in a few narrow, carefully controlled places precisely because that boundary's overhead is not free. Related CCI capabilities Computer Architecture (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/computer-architecture/). Optics Primer Series (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/optics/). Maths Refresher Series, Finance (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/maths-finance/). System Dynamics (Course): (https://www.cambridgecyberinternational.com/en/insights/academy/system-dynamics/). CCI Lab: Run it, build with it, read the thinking, reuse the data. (https://www.cambridgecyberinternational.com/en/insights/lab/)