Hikikomori

21 object(s)
 

603. operating system

Operating System

A digital computer without an operating system (OS) is just bare metal. The OS is the foundational systems software, a program which provides services to other programs rather than directly to users, managing hardware resources so that application software does not have to. Its kernel manages what runs (processes and threads), where it lives in memory (virtual memory and page tables), and what it reads and writes (files, devices, and the uniform file descriptor interface).

I

1.1. History

The earliest generation of electronic computers (1940s-50s), such as the ENIAC, were programmed manually in pure machine code by rewiring circuits or feeding in punched cards. Programs ran in isolation, required laborious setup, and left machines idle between jobs. The concept of an OS emerged in the 1950s with batch processing systems which grouped similar jobs for sequential execution without manual intervention. A key example is GM-NAA I/O, developed for the IBM 704, which used control cards to interpret jobs and automate execution, and whose successors (SOS, IBSYS) later scheduled Fortran jobs.

The 1960s marked a shift toward time-sharing systems (TSS) and multiprogramming, which admitted concurrent execution of multiple programs residing in memory by rapidly switching the CPU among them. This trajectory produced Multics, a pioneering TSS jointly built by AT&T Bell Labs, GE, and MIT to support a robust, multi-user computing environment. However, discontent with its complexity prompted researchers at Bell Labs to develop Unix in 1969. This newer and simpler OS incorporated a modular kernel, hardware abstraction, and multi-user support, and these principles remain central to modern operating system design.

The 1980s ushered in the era of personal computing, shifting OS development from command-line interfaces (CLI) to graphical user interfaces (GUI) to improve accessibility for non-technical users. Microsoft introduced MS-DOS in 1981, a single-tasking CLI-based OS, followed by successive versions of Windows that adopted cooperative and later preemptive multitasking. Around the same time, Apple’s Macintosh system software (later Mac OS, now macOS) brought the GUI into mainstream. In the 1990s, Linux emerged as a free and open-source Unix-like alternative, that became a foundation for innovation across servers, mobiles, and embedded systems.

What emerged from this history is a common set of abstractions that shield programs from hardware: i) A process refers to the running program with its isolated execution environment; ii) virtual memory lets each process have the illusion of a large contiguous address space independent of physical RAM; iii) file descriptors present all I/O endpoints via a uniform read/write interface. These abstractions decouple programs from specific hardware, so the same source code compiles and runs on any machine the OS supports (portability). §I traces the Unix and Linux lineage that shaped them, §II examines the kernel internals, and §III examines each abstraction in turn.

1.2. Unix

Unix emerged in 1969 at Bell Labs, when Ken Thompson and Dennis Ritchie (Turing Award, 1983) repurposed a spare PDP-7 minicomputer to build a lightweight alternative to Multics. Where Multics pursued complexity, Unix pursued simplicity: a small kernel, a hierarchical file system (HFS), and a minimal API with a clean separation between kernel mechanisms and user-space utilities. In the early 1970s, Unix was rewritten from assembly into C, also created by Ritchie, making it the first widely portable operating system. The design decisions that followed shaped the three abstractions examined in §III (process, virtual memory, file).

Before Unix, each class of device (disk, tape, terminal, printer) required its own set of I/O instructions and access methods, coupling programs to specific hardware. Unix’s central design decision was the “everything is a file” abstraction, which collapsed all I/O behind a single open/read/write/close interface so that a program reading bytes need not know whether they come from a disk, a keyboard, or a network. On top of this uniform interface, Unix introduced the fork-exec-wait process model, pipes (added in 1973 at Doug McIlroy’s insistence, wiring one program’s output to another’s input), and signals for asynchronous notification. Combined with plain-text configuration, these primitives made the environment composable and scriptable.

As AT&T was restricted by a 1956 antitrust consent decree from commercialising Unix, it spread freely through academia. The Berkeley software distribution (BSD), launched in the late 1970s by Bill Joy at UC Berkeley, evolved from a set of enhancements into a full OS that contributed the first complete TCP/IP stack and became a reference platform for early Internet development. BSD’s code lives on in FreeBSD, Apple’s Darwin (the Unix core of macOS/iOS), and even Windows networking. Meanwhile, Bell Labs continued with Plan 9 (1980s), which pushed the “everything is a file” abstraction to network and system resources, influencing Linux’s /proc and /sys. As Unix variants proliferated and diverged, the IEEE introduced the Portable Operating System Interface (POSIX) standard in the late 1980s, codifying a portable API around processes, file descriptors, and signals that unified the fragmented landscape.

1.3. Linux

Linux began in 1991 as a personal project by Linus Torvalds to build a free, Unix-like kernel for the Intel 80386 architecture. Inspired by MINIX (a teaching OS by Andrew Tanenbaum) and licensed under the GPL, it attracted contributions from developers worldwide and was paired with the GNU Project’s user-space tools (e.g. gcc, glibc, coreutils) to form a complete open-source operating system. Unlike proprietary Unix systems tied to specific vendors, Linux grew through a decentralised, community-driven model, a development approach that would later be mirrored by the open-source AI community (e.g. Hugging Face, PyTorch, llama.cpp).

Architecturally, Linux uses a monolithic kernel, integrating core services such as process scheduling, virtual memory, networking, and file systems into a single privileged binary. To balance this with modularity, it supports loadable kernel modules (LKMs) that allow dynamic insertion of drivers and extensions at runtime without rebooting. Written in portable C, Linux was quickly ported beyond x86 to architectures including ARM, PowerPC, and SPARC, and later incorporated features such as control groups (cgroups), namespaces, and pluggable schedulers, features that now underpin containerised workloads (§607).

Though not derived from any Unix source tree, Linux closely follows POSIX standards and Unix design principles. By the early 2000s, it had displaced proprietary Unix as the dominant OS for servers and infrastructure. Today, it runs on everything from Android smartphones to all Top500 supercomputers, and serves as the default runtime for virtually all large-scale ML workloads. Cloud ML platforms (e.g. AWS SageMaker) run Linux-based containers, as do distributed training frameworks (e.g. DeepSpeed, Megatron-LM) and inference servers (e.g. vLLM, TGI), because its open-source nature and fine-grained hardware control make it the natural fit.

II

2.1. Kernel (+ Shell)

A kernel is a C binary compiled for a specific CPU architecture which remains resident for the lifetime of the machine, managing hardware on behalf of user programs: process scheduling, memory management, file systems, networking, and device control. It maintains all system state in C structs: what programs run (i.e. processes), where they live in memory (i.e. pages), and what they read/write (i.e. file descriptors). While it manages hardware through interrupt handling, device registers, and DMA, its codebase has architecture-specific code (e.g. arch/x86/, arch/arm64/) alongside portable C code (e.g. kernel/, mm/, fs/).

Its architecture varies in how much code runs privileged. Monolithic kernels (e.g. Linux) place all services in a single binary for fast in-kernel function calls, and so a single bug can crash the entire system. Microkernels (e.g. seL4) preserve scheduling, IPC, and memory management privileged, running other kernel components as user-space servers at the cost of IPC overhead. Hybrid kernels (e.g. XNU on macOS) keep performance-critical services (e.g. file system, networking, graphics) in kernel space. The distinction matters most for device drivers, code that translates generic I/O requests into hardware-specific operations, as they are highly crash-prone components.

Regardless of architecture, user code executes in user mode and enters the kernel through a privilege transition. There are three causes: i) system call (syscall): an intentional request by a program (e.g. write(), fork()), implemented via a trap instruction (e.g. syscall on x86-64) that saves state and jumps to a kernel entry point. ii) Fault: a synchronous exception raised by the CPU during instruction execution (e.g. page fault, division by zero), often restartable after the kernel resolves the cause, though some (e.g. invalid opcode) are fatal. iii) Interrupt: an asynchronous signal from hardware (e.g. disk I/O completion, timer tick), handled independently of any running process. Syscalls and faults are synchronous and handled in the context of the current process; interrupts can arrive at any time. The timer interrupt (every 1-10 ms) is what allows the kernel to preempt running programs. On x86-64, syscalls enter via MSR_LSTAR, while faults and interrupts dispatch through the interrupt descriptor table (IDT).

Of the three, syscalls are the primary interface for user programs, typically issued through a shell, a command interpreter that parses input and dispatches the corresponding syscalls. The shell is a user-space process which repeatedly reads a command, forks a child, execs the binary, and waits for completion. CLI shells (e.g. Bash, Zsh) build on this loop with scripting, I/O redirection, job control, and process substitution. A pipeline such as ls | grep foo compiles into the target syscalls: fork(), pipe(), dup2(), and exec(), orchestrated by the shell before any program executes. Graphical desktop environments (e.g. Aqua, GNOME) expose the same interface visually.

2.2. System Call

The syscall lifecycle on Linux x86-64 proceeds as follows. The program calls a libc wrapper (e.g. write()), which places the syscall number in rax (1 for write) and arguments in rdi, rsi, rdx, then executes the syscall instruction. The CPU saves the instruction pointer (RIP → RCX) and flags (RFLAGS → R11), switches to kernel mode, and jumps to the entry point registered in MSR_LSTAR. The kernel indexes into a syscall table by the number in rax, dispatches the handler (e.g. sys_write), places the return value in rax, and executes sysret to restore user mode. The program resumes unaware of the privilege transition.

Standard libraries (e.g. libc) wrap these register conventions and trap instructions into portable function signatures (open(), read(), write(), close()), so programmers never issue syscalls directly. In Python, os.write(1, b”Hello”) chains through CPython’s C runtime into libc’s write(), which issues the syscall instruction. Windows exposes the same functionality through WriteFile() with a distinct ABI and trap mechanism (syscall on x64, int 0x2e on early NT, sysenter from XP onward). Cross-platform portability is achieved via standardised APIs (e.g. POSIX) or runtime layers (e.g. JVM, Python interpreter).

Linux x86-64 defines ~450 system calls, each identified by a number in a syscall table spanning process control (fork(), execve()), file operations (open(), read()), memory management (mmap(), brk(), used by malloc underneath), and networking (socket(), connect()). Fast syscalls like getpid() return immediately. Blocking syscalls like read() or accept() may suspend the calling process, as the kernel marks it as waiting and schedules another until hardware signals completion via an interrupt. Each mode switch costs roughly 100-1000 ns, which is why performance-sensitive code minimises crossings through buffered I/O, vectored operations (readv()/writev()), or batching interfaces like io_uring.

III

3.1. Process

A process (i.e. resource-owning unit) is the kernel’s abstraction of a running program that provides an isolated address space and its own kernel resources. A thread (i.e. scheduling unit) shares the process’s address space and fd, but maintains its own stack, PC, SP, registers, and flags, to enable concurrent execution without duplicating the address space. In Linux, both are represented by a single task_struct (i.e. process control block), where thread(s) in the same process simply point to the same mm_struct and files_struct. The distinction between the two is therefore structural rather than fundamental, while all processes always begin with a single main thread.

Creating a process from scratch would require allocating a fresh address space, page tables, and fd table. Unix avoids this with a two-step mechanism. i) fork() (kernel/fork.c) duplicates the calling process via copy-on-write (CoW), producing a child with a new PID that shares the parent’s pages until either side writes; ii) The child calls exec() to load a new program, and the parent calls wait() to block until the child terminates; For example, when a user types ls, the shell forks → child execs /bin/ls (i.e. replaces the shell code with the ls binary) → parent waits → next prompt. A terminated child whose parent has not yet called wait() is also known as a zombie process.

Specifically, exec() reads the executable header (e.g. ELF, §602) and maps its segments into the process’s (virtual-) address space. i) text: machine code, read-only and shareable via CoW; ii) data/BSS: initialised and zero-initialised global and static variables; iii) heap: growing upward via brk() / mmap(); iv) stack: growing downward for local variables and function frames; Notice that dynamically linked shared libraries are mapped between heap and stack by the runtime linker (ld.so), allowing multiple processes to share a single copy in physical memory (§602). Execution then begins at the entry point _start, which initialises the C runtime and calls main.

Once created, each thread advances through a life cycle of mutually exclusive states: new, ready (queued for CPU), running (actively scheduled), waiting (blocked on I/O or synchronisation), and terminated. Each transition corresponds to a field update in the thread’s task_struct. For example, read() on a slow device moves the thread from running to waiting; the device interrupt moves it back to ready. The kernel organises threads by state into queues, maintaining a ready queue for threads awaiting CPU time and wait queues for those blocked on events. On multicore systems, the scheduler keeps per-core ready queues and periodically rebalances load.

The CPU scheduler determines which ready thread to dispatch on each core. Cooperative scheduling relies on threads voluntarily relinquishing the CPU (via yield(), I/O, or sleep), so a thread that never yields starves all others. Preemptive scheduling, adopted by all modern OSes, removes this dependency via the hardware timer interrupt. Each decision triggers a context switch that saves the current thread’s CPU state into its task_struct and restores the next thread’s. Intra-process switches are inexpensive, but inter-process switches require a page table swap and TLB flush. Selecting which thread to run next is therefore a policy decision.

The classical scheduling algorithms formalise its choice. Round robin (RR) cycles through the ready queue with a fixed time quantum. Shortest Job First (SJF) selects the smallest expected CPU burst, minimising average wait at the risk of starving long jobs. Highest Response Ratio Next (HRN) mitigates this via $(w + s) / s$ ($w$ = waited, $s$ = est. service time), so longer-waiting threads eventually win. Priority scheduling dispatches the highest-priority thread, risking starvation unless aging boosts lower priorities. Multi-level feedback queues (MLFQ) unify these with multiple queues that dynamically adjust priority based on observed behaviour (I/O-bound promoted).

In practice, Linux synthesises these ideas into a fair scheduler. The Completely Fair Scheduler (CFS, kernel/sched/) maintained a per-thread virtual runtime that advances inversely with its nice value (weight), dispatching the thread with the smallest value via a red-black tree ($O(\log n)$). The EEVDF (Earliest Eligible Virtual Deadline First) scheduler replaced CFS in kernel 6.6 (2023), adding a deadline component to reduce latency for interactive tasks while keeping fairness. Both operate under the default SCHED_NORMAL policy; real-time tasks use SCHED_FIFO or SCHED_RR with fixed priorities that unconditionally preempt normal threads.

Once scheduled and running, processes may need to exchange data across their isolated address spaces. The kernel facilitates this through inter-process communication (IPC). Message passing delegates transfer to the kernel via pipes, Unix domain sockets (UDS), or message queues. Unlike TCP over loopback, UDS bypasses the network stack, addressed by a file path (e.g. /var/run/docker.sock). Shared memory maps the same physical pages into multiple address spaces, avoiding the copy. Message passing is simpler (the kernel handles synchronisation), but shared memory offers higher throughput since data never crosses the kernel boundary. All IPC mechanisms are accessed through file descriptors (§3.3).

fork() duplicates the parent process’s fd table, and exec() preserves it, so a child process inherits all open file descriptors. This inheritance is the mechanism behind shell I/O redirection and pipes, where pipe() creates a pair of fds connected by a kernel buffer and dup2(oldfd, newfd) copies one fd onto another slot, replacing what was there. To build ls | grep foo, the shell creates a pipe, forks twice, uses dup2() to replace each child’s stdout or stdin with the appropriate pipe end, then calls exec() in each child. Neither ls nor grep contains any redirection logic; both simply read from fd 0 and write to fd 1 as usual.

3.2. Virtual Memory

Given that physical memory is a flat, byte-addressable array (§601), virtual memory interposes a hardware translation layer (e.g. MMU + TLB), in which each process sees a large, contiguous address space rather than physical memory. Modern general-purpose OSes leverage the abstraction, where the kernel maintains the mapping for the hardware to enforce it on every memory access, as it allows i) isolation: one process cannot access another’s memory; ii) sharing: common pages mapped without duplication, with CoW deferring copies until a write occurs; and iii) overcommitment: total virtual allocation may exceed physical capacity, backed by disk.

The kernel partitions virtual address space and physical memory into fixed-size pages and frames, respectively, typically 4 KB. Each process is given a page table that maps virtual page numbers to physical frame numbers. On each memory access, the MMU splits the virtual address into a page number and an offset, looks up the page number in the table, and replaces it with the physical frame number. Each page table entry (PTE) is per-page metadata that records the physical frame number, a present bit that triggers a page fault, and permission flags (rwx). On context switch, the kernel updates the page table register, e.g. {x86: CR3, ARM: TTBR}, to point to the new process’s table.

Fixed-size paging naturally eliminates external fragmentation at the cost of internal fragmentation. However, the tables also reside in physical memory, and a naive flat table becomes impractical as the address space widens. For instance, let $N$, $P$, and $E$ denote the virtual address width, page size exponent, and PTE size exponent, respectively. A flat table with one entry per page costs $2^{N - P + E}$ B per process. On x86-64 (i.e. $N = 48$, $P = 12$, $E = 3$), this yields $2^{39}$ B = 512 GB of pre-allocated memory per process, regardless of actual usage, which makes a flat table prohibitive.

Multi-level page tables solve the flat table problem by partitioning the virtual address into multiple index fields, each selecting an entry in a successively deeper table. Only subtrees covering populated regions are allocated, making each process’s page table cost proportional to actual usage. x86 (32-bit) uses a 2-level hierarchy, requiring two memory reads per translation; x86-64 extends this to 4 levels for wider address spaces. However, multiple memory reads per translation is still expensive, so the TLB (§601#1.3) caches recent translations. It is effective because programs exhibit strong locality: a single 4 KB page holds many instructions, so consecutive accesses frequently result in a TLB hit. A TLB miss triggers the full page table walk, and a TLB flush invalidates all cached entries.

Physical frames are not allocated until first accessed, a strategy called demand paging. When a process touches an unmapped page, the CPU raises a page fault (mm/memory.c) and the kernel allocates a frame, either zero-initialising it or loading content from disk. If physical memory is exhausted, a page replacement policy evicts a victim frame. While this permits overcommitment, sustained faulting leads to thrashing.

In practice, virtual memory and file I/O are tightly coupled. The page cache (mm/filemap.c) buffers disk blocks in RAM, so repeated reads of the same file resolve from memory rather than disk. mmap() (mm/mmap.c) turns page faults into file reads, allowing np.memmap to access a large on-disk array as if it resided in memory, with the kernel paging in only the blocks actually touched. Swap inverts this relationship, using disk as a backing store for memory pages with no file origin. In all three cases, the kernel moves data between RAM and disk in page-sized units, making the boundary between abstractions ii) and iii) thinner than it appears.

3.3. File System

In Unix, a file is an unstructured sequence of bytes with no format imposed by the kernel, and a file system is the software layer which organises files into a hierarchy of named paths, each associated with metadata (e.g. size, ownership, permission). The indirection (i.e. abstraction) between names and raw bytes is what maps files onto the raw blocks of a disk (§601#1.4), though the same interface extends to memory-backed (tmpfs), network-backed (NFS), and kernel-generated (/proc) file systems. Therefore, the kernel is format-agnostic, file extensions (e.g. .txt, .py) are merely a user-space convention, and file(1) inspects magic bytes in the content to determine its type.

Programs do not access files directly; they ask the kernel for a file descriptor (fd) via the open() syscall, which resolves the path and allocates entries in internal bookkeeping tables before returning a small non-negative integer. The fd is the mechanism that makes this uniform interface possible. The kernel tracks it through three layers of data structures: per-process fd table $\to$ system-wide open-file table $\to$ in-kernel file object, and it returns the lowest available integer, so the first three fds on a fresh process are 0 (standard input), 1 (standard output), 2 (standard error) by convention (POSIX).

read(fd, buf, n) receives up to $n$ bytes and write(fd, buf, n) sends them. Both return the number of bytes transferred, which may be less than requested (a short read/write), and read() returning 0 signals end-of-file (EOF). By default, read() on a source with no available data (e.g. an empty pipe) blocks the calling process until bytes arrive or the write end closes. lseek() repositions the fd’s offset for random access, and close() releases the fd, decrementing the reference counts at each layer. In practice, standard libraries (e.g. C’s stdio) wrap fds in buffered handles (e.g. FILE*), and higher-level languages (e.g. Python’s open()) add further abstraction.

Given the uniform interface applicable to all I/O endpoints, each back-end has its own file system implementation. Specifically on disk, a file is represented as an index node (inode) and data blocks. The on-disk inode is a per-file struct storing metadata and pointers to data blocks (fixed-size chunks, typically 4 KB) that hold the file’s bytes; the kernel loads it into memory when the file is opened, producing the in-kernel file object in the three-layer model above. Just as a flat page table cannot scale to a wide address space, a fixed set of direct pointers cannot address a large file. ext2 solved this with 12 direct pointers plus single-, double-, and triple-indirect blocks; ext3 retained this scheme and added journaling, yielding a maximum file size of $(12 + p + p^2 + p^3) \times b$, where $b$ is the block size and $p = b/4$ the number of pointers per block. With $b = 4$ KB and $p = 1024$, this gives ~4 TB. ext4 replaced indirect blocks with extents, raising the limit further.

The inode does not store the file name. A directory is a file that maps names to inode numbers; directories referencing other directories form the tree hierarchy (/, /home, /usr, …) that users navigate daily. On Linux, the Filesystem Hierarchy Standard (FHS) standardises this layout (e.g. /bin for essential binaries, /etc for configuration, /home for user directories). Because names live in directory entries rather than inodes, multiple names can reference the same inode and renaming requires only updating the directory entry. A hard link is a second directory entry for the same inode; the data persists until all links are removed (the inode tracks a link count). A symbolic link (symlink) is a separate inode that stores a target path; unlike a hard link, deleting the target leaves a broken symlink. Each inode encodes a 9-bit permission field (read/write/execute $\times$ owner/group/other) checked on every operation. In ls -l output, a leading character indicates the inode type (d for directory, l for symlink, - for regular file), followed by the nine permission bits (e.g. drwxr-xr– for a directory readable by all, executable by owner and group, writable only by the owner).

The preceding paragraphs describe one file system on one disk, but a single machine may mount ext4 on its local disk, NFS for a remote share, and tmpfs for scratch space simultaneously. Even on the same back-end, different file systems embody different design tradeoffs (e.g. ext4 vs btrfs vs XFS). Without a common dispatch layer, every syscall would need to know which file system it is talking to. A virtual file system (VFS) solves this by providing a single abstraction layer through which all file system operations pass. The in-kernel file object in the three-layer model is a VFS object, populated from the on-disk inode for disk-backed files or synthesised by the kernel for pipes, sockets, and pseudo-filesystems. Each filesystem registers a file_operations struct whose function pointers implement open, read, write for that format; VFS dispatches every syscall through these pointers. Mounting a FAT32 USB drive alongside APFS (Apple’s default disk file system) requires no change to user-space code.

The fd abstraction grew from files (disk I/O) $\to$ pipes (inter-process byte streams) $\to$ sockets (network endpoints) $\to$ devices, each extending the same read/write interface to a new domain. In Unix, a file is therefore any I/O endpoint the kernel exposes through a file descriptor. Device drivers bridge this abstraction to real hardware by implementing two contracts: upward, they conform to the kernel’s file interface so that user-space sees a file descriptor; downward, they speak the device’s register protocol, handle its interrupts, and manage its DMA buffers. When installed, a driver registers with the kernel’s bus subsystem (e.g. PCI), probes the device, and exposes it as a file in /dev (e.g. /dev/sda for a disk, /dev/nvidia0 for a GPU). Pseudo-filesystems like /proc (originating in 8th Edition Unix, 1984) and /sys expose live kernel and hardware state through the same interface. These files have no backing data on disk; the kernel generates their contents dynamically on each read(), making system introspection as simple as reading a file.



I gathered words solely for my own purposes without any intention to break the rigour of the subjects.
I also prefer eating corn in spiral .

Code licensed under MIT License