Operating System Concepts

An OS is the privileged program that owns the machine. It multiplexes CPU, memory and devices among programs, isolates those programs from each other and from raw hardware, and abstracts devices behind a stable interface (files, processes, sockets, virtual memory). Interviews that ask "is it just a library?" want this: a library cannot enforce isolation because it does not control the mode bit or the page tables.

The CPU has a privilege bit (or exception level). In user mode the running code cannot execute privileged instructions: no device I/O, no page-table writes, no halt, no flip of the mode bit. In kernel mode those instructions are legal. The hardware switches mode on a syscall, interrupt or exception and switches back on return-from-exception. User programs include shells, apps and most daemons; only the kernel (and a hypervisor at a higher level) is trusted with the MMU and devices.

A hardware lattice of privilege. The textbook x86 picture has rings 0 (most privileged) through 3. Mainstream kernels use two: ring 0 / EL1 for the kernel and ring 3 / EL0 for user. Extra levels exist for a hypervisor (EL2) and firmware (EL3). The interview point is not the trivia of every ARM level; it is that isolation is hardware-enforced. If any program could raise its own privilege, a wild pointer could rewrite page tables or program DMA into another process.

A numbered, documented request into the kernel: open, read, mmap, fork, clone, and so on. Userspace (usually libc) loads a number and arguments into ABI registers and executes a trap instruction (syscall, svc). Hardware raises privilege and vectors to a dispatcher. The kernel validates arguments — especially user pointers — does the work or sleeps, and returns a result. It is not a normal C function call: the stack, privilege and trust boundary all change. See C for the libc stub and Linux kernel & BSP for the entry path.

Dual mode is the hardware rule that user code cannot perform privileged operations. Without it, isolation is a social convention: any process could disable interrupts, remap memory or write another process's pages. With it, the only crossings are well-defined vectors the kernel handles. That is why "run the whole OS in user mode on paper" is a research idea that still needs some trusted TCB, not a reason to drop the mode bit on a phone.

An interrupt (IRQ) is asynchronous: a device or timer fires independently of the current instruction. A trap is synchronous and deliberate (syscall, breakpoint). An exception is synchronous but not "please do this POSIX service" — the instruction cannot complete as issued (page fault, divide-by-zero, illegal opcode). In interview English, sort by who caused it and whether you will retry the instruction.

Both are exceptions. A fault is typically restartable: the kernel repairs the condition and retries the same instruction. A page fault is the important case — virtual memory is built on it. An abort is not restartable (serious hardware error, some double faults); the process or the machine is done. If you say "page fault kills the process", you have mixed a protection violation (bad address) with a not-present fault on a legal mapping.

A program in execution: a private virtual address space, credentials, a file-descriptor table, signal state, resource limits, and one or more threads. It is the usual isolation boundary. The kernel's record of that bundle is the PCB. Two processes do not share memory unless they both map the same pages (shared memory, shared file maps) or they are still sharing COW pages after fork.

The process control block is the kernel object describing a process or task. Interview contents: PID and parent, state, CPU context (often per-thread), pointer to page tables / mm, file table, credentials, scheduling parameters, accounting, and pending signals. On Linux the living form is task_struct plus satellite structs — that split is kernel material. Here: the PCB is what you context-switch and what ps is displaying.

Classic five: new (being created), ready (runnable, waiting for a CPU), running (on a CPU), waiting/blocked (cannot run until an event), terminated (exited; may still be a zombie). Dispatch: ready → running. Preempt: running → ready. Block (I/O, lock, wait): running → waiting. Wake: waiting → ready. Exit: running → terminated. Some books add swapped-out suspended states; mention them only if asked.

The kernel saves one thread's registers and kernel stack pointer and loads another's. If the next thread is in a different address space, it also switches the page-table root, which flushes or retags the TLB. Direct cost is thousands of cycles. Indirect cost is often larger: the next job does not share the previous job's hot cache lines. Same-process thread switches skip the mm switch and are cheaper. That is why a huge number of threads with a tiny RR quantum destroys throughput.

fork creates a child that is a copy of the parent (modern kernels: COW pages). Child sees return value 0; parent sees the child's PID. exec replaces the current address space with a new program; the PID and most fds remain. exit releases memory and files and leaves an exit status. wait/waitpid lets the parent collect that status and free the zombie PCB. The usual "run another program" path is fork then exec; Android's zygote is fork without exec for a pre-warmed runtime — see Android frameworks.

A zombie has already exited; the parent has not waited. Almost no memory remains — only a process-table slot so the exit code can be read. Ignore children and you leak PIDs, not RAM. An orphan is still running after its parent died. The OS reparents it (classically to PID 1) so someone will wait. An orphan is not a zombie; it may become one later, and the new parent will reap it.

Threads in one process share the address space (code, heap, globals), file descriptors, and credentials. They do not share stacks or, by default, TLS values. Separate processes share nothing unless they set up IPC or inherited COW/mmap mappings. Threads are cheaper to create and switch and pass data by pointer; processes isolate faults and security domains. Browsers and sandboxed renderers pick processes on purpose.

The unit the scheduler runs: a register set, a stack, TLS, and a scheduling state, living inside a process. "The process runs" is loose language — a thread runs on a core. A single-threaded process is just the special case of one thread. Java threads and the JVM memory model are on the Java page; here the OS fact is that a thread is a kernel-schedulable (1:1) or library-schedulable (N:1) execution context.

User-level threads are scheduled by a library; the kernel sees one task. Switch is a function call (fast), but one blocking syscall or page fault blocks all of them, and you cannot use more than one core. Kernel-level threads are first-class tasks; blocking and SMP work. Modern POSIX pthreads on Linux are 1:1 kernel threads. Language runtimes that multiplex green threads are an M:N or N:1 story on top.

Storage that looks like a global but has one instance per thread: errno, a thread id, a scratch buffer. The ABI keeps a register (FS/GS, TPIDR) pointing at a per-thread block; TLS symbols are offsets from that pointer. That is why errno is thread-safe without a lock. It is not a substitute for a mutex on heap data you actually share.

A CPU burst is a stretch of execution that needs the processor. An I/O burst is a stretch waiting for a device (or a lock, or a sleep). Interactive jobs have short CPU bursts and frequent I/O; batch jobs have long CPU bursts. Schedulers estimate or observe the next CPU burst. Mixing them under FCFS is how you get the convoy effect.

Non-preemptive (cooperative): a thread runs until it blocks, yields or exits. A runaway loop starves the machine. Preemptive: a timer tick or a higher-priority wake-up can seize the CPU. General-purpose OS schedulers are preemptive. Textbook numericals still use non-preemptive SJF or FCFS; say which you assumed when you draw the Gantt chart.

FCFS (first-come first-served) runs ready jobs in arrival order until each CPU burst finishes. The convoy effect is a long CPU-bound job at the head; short I/O-bound jobs wait, run for a moment, block, then queue behind the long job again. Average waiting time explodes. RR, SJF and MLFQ exist in part to break convoys.

Each ready job gets a time quantum q, then goes to the tail of the ready queue. Response time is good for interactive work. If q is tiny, context-switch overhead dominates (CPU spends its life saving registers). If q is huge, RR collapses to FCFS. Pick q large compared to a switch (milliseconds, not microseconds) but small compared to a human-noticeable delay. There is no universal number; state the trade-off.

Turnaround = completion time − arrival time (how long the job was in the system). Waiting time = turnaround − CPU burst time (time in the ready queue, not I/O wait). Response time = first time on the CPU − arrival (how long until it first "twitches"). Quote averages over a set of jobs. Throughput is completed jobs per unit time; utilisation is the fraction of time the CPU is not idle.

A situation where correctness depends on the interleaving of concurrent operations. The lost-update: two threads read the same counter, both add one, both write, and one increment vanishes. Shared memory plus no synchronisation is sufficient. Data races are undefined behaviour in C and C++ (C, C++); in OS language, they are the reason critical sections exist.

The region of code that must appear atomic with respect to other threads that share the same data. Entry and exit protocols (a mutex, an atomic algorithm) implement that atomicity. The section should be as short as you can make it: hold time is contention and, if you spin, wasted CPU. I/O inside a critical section is a common design smell.

A mutex is an owned lock: the thread that locks it must unlock it; it is for protecting a critical section. A semaphore is a counter plus a wait queue: P/wait decrements and may sleep, V/signal increments and may wake. No owner — any thread may V. A binary semaphore can mimic a mutex but can also be used as a pure signal ("this event happened"). A counting semaphore tracks N identical resources. Prefer a mutex for exclusion; use a semaphore when the count or the cross-thread signal is the point.

Binary: the count is 0 or 1. Counting: the count is a non-negative integer. Use counting for N buffers, N devices, or the empty/full counts in producer-consumer. Use binary for a single-event signal or a crude mutex. Neither has ownership; if you need "only the locker may unlock" and priority inheritance, you want a mutex.

Deadlock is a set of processes such that each is waiting for a resource another in the set holds, and none will release what they hold. The four conditions, all required: mutual exclusion (the resource is not shared), hold and wait (hold one, wait for another), no preemption (you cannot yank the held resource), circular wait (a cycle). Break any one and deadlock cannot occur. That is prevention. Avoidance (Banker's) and detection-plus-recovery are different policies.

A logical (virtual) address is what the program issues. A physical address is a location in RAM (or device memory) on the bus. The MMU, using kernel-installed page tables, translates one to the other or raises a fault. Relocation and isolation both come from this: two processes can both use address 0x400000 and not collide. Without an MMU you bind at compile or load time and you do not get this isolation.

External: free memory exists but is carved into holes too small for the next variable-size request (classic segments, a naive heap). Fix by compaction or by allocating only fixed frames (paging). Internal: you received a block larger than you needed; slack inside the page or slab is wasted. Paging has internal fragmentation on the last page of a mapping. You tolerate it; you do not compact it away.

Paging splits memory into fixed-size pages and frames. The process sees a flat virtual array. No external fragmentation of RAM; some internal slack; the table can be huge unless it is hierarchical. Segmentation uses variable-size logical regions that match how programmers think (code, stack, heap). External fragmentation returns. Modern OS: paging is the mechanism; "segments" are just named mappings (VMAs) on top of pages.

The CPU failed a translation: no valid PTE, or a permission violation, or a reserved bit. Hardware saves the faulting address and traps to the kernel. If the address is illegal, the process is signalled (UNIX: SIGSEGV). If the mapping is legal but not present, the kernel allocates a frame, fills it (zero, file, swap, COW copy), installs the PTE, and restarts the instruction. That restartable path is demand paging.

Each process has a large, isolated logical address space. Only the pages it uses need RAM frames; the rest live on a backing store (the file, swap) or do not exist yet. Demand paging, the TLB, replacement, COW and mmap are the machinery. It is not "infinite RAM": thrashing and out-of-memory exist. On Android, the LMK may kill a process under pressure rather than swap forever — frameworks.

A file is a persistent byte stream plus metadata. An inode is the identity: owner, mode, timestamps, size, and the map from offsets to disk blocks. A directory is a listing that maps names to inode numbers (or equivalent). The name is not stored in the inode. That split is why two names can refer to one file (hard links) and why renaming is a directory operation, not a rewrite of the data.

A hard link is another directory entry for the same inode: same data, same inode number, cannot cross filesystems, usually forbidden for directories. The inode's link count drops on unlink; data is freed when the count is 0 and no fd remains. A symbolic link is a small file holding a path. It may dangle, may cross filesystems, and is resolved when you use it. Permissions on the target usually decide access.

IPC is how separate address spaces exchange bytes or events. An anonymous pipe is a unidirectional kernel buffer, typically set up by a parent and inherited across fork — shell pipelines. A socket is bidirectional, has a richer API (connect, listen, datagram vs stream), and can leave the machine. Use a UNIX-domain socket when two local processes need a bidirectional channel or credentials passing; use a pipe for a simple one-way inherited stream. Shared memory wins for bulk data if you will write the synchronisation yourself.

UID/GID are the credentials the kernel stamps on a process and compares to object ownership and mode bits (or ACLs). A process is an address space plus those credentials. A container is still processes on the same kernel, with extra namespace views and cgroup limits. A VM virtualises hardware and usually runs a guest kernel. Isolation strength and density go in opposite directions: process < container < VM for isolation; the reverse for density and start time.

Libc places the syscall number and arguments in the architecture's ABI registers and executes a trap instruction. Hardware saves the user program counter and status, raises privilege, and vectors to the kernel entry. The kernel saves user registers, looks up the number, copies and checks user pointers (never trust a raw address), performs the work or sleeps, writes the return value, then return-from-exception drops privilege and resumes userspace. If the thread slept, another thread ran in between — that is the scheduler, not part of the stub. Kernel entry details: Linux kernel & BSP.

Then every bug is a kernel bug. A wild pointer can rewrite page tables, program a DMA engine into another process, or disable the timer that preempts runaways. Dual mode plus a narrow syscall ABI is how we keep a browser tab from owning the machine. Microkernels move more policy to user servers, but they still have a privileged core that owns the MMU. The interview answer is isolation and a stable ABI, not "syscalls are fast".

A same-process thread switch saves/restores registers and kernel stacks but keeps the same page-table root. A process switch also switches the address space: load a new CR3/TTBR, flush or retag the TLB, and lose cache warmth for the previous working set. File tables and credentials may be switched too. That is why "just use more processes" is the wrong default for fine-grain parallelism, and why browsers accept the cost only when they want a crash domain.

Each child that exits becomes a zombie: the address space is gone, but the PCB slot and exit status remain. Enough of them exhaust the PID space; fork starts failing. Memory does not leak in the "child heap still allocated" sense. The fix is wait/waitpid (or a SIGCHLD handler that reaps), or to have the parent die so the children are reparented and reaped by init / a subreaper.

When the parent exits first, the OS reparents the live child. Classically the new parent is PID 1 (init), which loops on wait and collects zombies. Linux can reparent to a designated subreaper instead. The guarantee is: someone will wait, so orphans do not become permanent zombies. Service managers that spawn workers rely on this if a worker outlives its launcher.

N:1 multiplexes many user threads onto one kernel thread: cheapest switch, no parallelism, one blocking syscall freezes all. 1:1 maps each user thread to a kernel thread: blocking and SMP work; create/switch go through the kernel (still cheap). This is POSIX on modern Linux and the usual Android/ART native thread. M:N parks M green threads on N kernel workers: can hide I/O and use several cores, but you now have two schedulers, messy signals, and hard stop-the-world cases. Interviewers want the trade-off, not a brand name.

Threads: shared working set, cheap hand-off of pointers, need many concurrent I/O or parallel CPU workers inside one program (a server, a UI plus workers). Processes: fault isolation (a renderer crash must not take the browser chrome), different credentials, a sandbox, or a blast radius you can kill. The cost of IPC and of a heavier create/switch is the price of that isolation. See system design for multi-process services and frameworks for app process policy.

The kernel deschedules the one task it sees. Every user thread in that process stops, including ones that were ready to run. The library cannot context-switch them because it is not running. Page faults have the same effect. That is the historic reason N:1 died for general-purpose servers. Workarounds (non-blocking I/O plus a user scheduler) reinvent M:N.

Both pick the job with the shortest next CPU burst. SJF is non-preemptive: once a burst starts, it finishes. SRTF is preemptive: a newly arrived shorter remaining burst seizes the CPU. Both minimise average waiting time if you know the future. You do not; you estimate (exponential average of past bursts, or "interactive vs batch" feedback). Long jobs can starve; aging or a lower bound on share is the patch. These are textbook policies, not Linux CFS.

If a high-priority stream is always ready, a low-priority job never runs. That is starvation, not deadlock (the system is making progress). Aging increases priority as wait time grows, so the low job eventually outranks the chatter and gets a turn. Mention aging whenever you mention priority, SRTF, or an MLFQ without boosts.

A multilevel queue has fixed classes (interactive, batch, RT). A job is assigned a queue and stays there; each queue may have its own policy and a priority between queues. Misclassification is permanent. MLFQ lets jobs move: burn your quantum and you are demoted (you look CPU-bound); block early and you stay high (you look interactive). You need aging or periodic boosts so a long job is not buried forever. MLFQ is the "learn the workload" textbook design behind a lot of interactive OS folklore.

Write arrival times and burst lengths. Draw the chart under the policy (watch preemption points). For each job: completion is the time its last slice ends; turnaround = completion − arrival; waiting = turnaround − burst (only CPU burst; do not subtract I/O unless the problem included I/O in the "burst" column). Average the columns. Response is the start of the first slice minus arrival. State whether the policy is preemptive. A common arithmetic bug is using finish − burst and forgetting a late arrival.

Mutual exclusion: at most one thread in the section. Progress: if the section is free and someone wants in, selection cannot be postponed by threads that are not interested. Bounded waiting: a bound on how many times others may enter after you have requested entry. Peterson's algorithm is the software classic; hardware atomics plus an OS sleep queue are what you ship. A spin-forever lock can fail bounded waiting if a thread is never scheduled.

You need exclusion on the buffer and "do not write when full" / "do not read when empty". One mutex (or a binary semaphore used as a mutex) protects put/get. A counting semaphore empty starts at N; a producer P(empty) before filling and V(full) after. A consumer P(full) before taking and V(empty) after. Invert the P order (mutex first, then empty/full) and you can deadlock: you hold the mutex while sleeping for a slot. Always take the "resource count" semaphores outside the mutex, or use a mutex plus two condition variables and wait in a loop on the predicate.

Many readers may hold the data at once; a writer needs exclusive access. Readers-preference: a waiting writer can starve if readers keep arriving. Writers-preference: readers can starve. A fair queue (one waiter line, or a ticket) avoids both at the cost of extra state. Always state which policy you chose. Implementation is usually a mutex, a reader count, and a write lock (or two condition variables).

A monitor is a language construct: data plus operations that run with implicit mutual exclusion, plus condition variables. Java synchronized methods are the interview example (Java). A condition variable is not a lock. wait atomically releases the mutex and sleeps; signal/broadcast wakes waiter(s). Under Mesa semantics (the one you will ship), a wake is a hint: re-test the predicate in a loop. Hoare semantics hands the mutex to the waiter immediately; textbooks mention it, kernels and pthreads do not implement it that way.

Spin when the critical section is a handful of instructions and the holder is running on another core (so the flag will clear soon) and you are not allowed to sleep (hard IRQ context on Linux — kernel). Sleep (mutex) when the hold may include I/O or a long computation, or you are on a uniprocessor (spinning waits for a holder that cannot run until you deschedule). Adaptive mutexes spin a little, then sleep. Priority inversion is worse with a spinlock held while a low-priority holder is preempted.

Prevention designs out a Coffman condition: global lock order (breaks circular wait), allocate everything up front (breaks hold-and-wait), or make the resource preemptive. Avoidance (Banker's) checks each grant against a safe-state test; needs declared maxima; rare for mutexes, common as a numerical. Detection builds a wait-for graph or runs a reduction, then kills or rolls back a victim. Many desktops are "ostrich": ignore and hope. Databases detect; lock-heavy servers prevent with ordering.

Each process declares a maximum claim per resource type. The allocator tracks Allocation, Need = Max − Allocation, and Available. When a process requests units, pretend you granted them. Then search for a safe sequence: an order of processes that can each finish with Available + what they would free. If no such order exists, refuse (the waiter sleeps) even if the units are free right now. You stay in a safe state. Real lock libraries do not run this; they use lock ranking. Be ready to walk a 3×3 matrix if they put one on the board. Searching for a sequence is a graph/greedy exercise; see DSA if you want the loop structure.

Deadlock: a cycle of waiting; no one in the set changes state in a useful way. Livelock: everyone keeps reacting (retry, backoff together, step aside the same way) but nobody makes progress. Starvation: the system progresses, but one participant never gets a turn. Fixes differ: break a Coffman condition or recover; add randomness/exponential backoff; age priorities or fair-queue. Do not use the three words as synonyms.

Compile-time binding assumes a known physical address (no MMU, or a fixed embedded map). Load-time binding patches the binary when it is loaded. Execution-time binding (virtual memory) translates every access; the program never sees physical addresses. Relocation is why the same ELF can run in many processes at once. PIC/PIE is the userspace cousin (see C); the OS story is the MMU.

Compaction slides allocated regions together so free holes become one region. It requires the ability to move a live object and fix every pointer or to rewrite translations. With variable-size physical partitions, you compact or you fail to place the next job. Paging allocates fixed frames: any free frame will do, so external fragmentation of RAM disappears (internal slack remains). Userspace heaps still fragment; that is a malloc problem, not an OS placement problem.

A 64-bit space with 4 KiB pages has an absurd number of virtual pages. A flat array of PTEs would be huge even if the process uses a few megabytes. A radix tree (3–4 levels) stores only the branches you populated: unused quadrants cost a null upper pointer, not a forest of empty leaves. The cost is L dependent memory loads on a TLB miss. That cost is why the TLB — and huge pages that shorten the walk — exist.

The TLB caches recent VPN → PFN translations (and permissions). Hit: about t_TLB + t_mem for the data. Miss: t_TLB + L memory references for the walk + t_mem for the data. EAT = h(t_TLB + t_mem) + (1−h)(t_TLB + (L+1)t_mem). A hit-rate drop from 99% to 90% is painful because misses are so expensive. A process switch that flushes an untagged TLB resets h. If they give numbers, plug them in and keep L explicit.

Hardware: TLB miss, walker finds invalid PTE or no PTE, fault with the VA and the PC. Kernel: is this a bad address, a permission error, or a legal not-present mapping? Bad → signal/kill. Legal: find or allocate a frame. File-backed: schedule disk I/O and sleep (major fault). Anonymous: zero a frame. COW write: copy the page. Install a valid PTE, update TLB, return so the instruction retries. Minor faults (page already in cache, just not mapped here) skip the disk. Linux VMA details: kernel.

Do not load a program's pages at exec time. Map the address space as not-present (or file-backed holes) and fill a frame on the first touch. Startup is faster and unused code/data never occupies RAM. The downsides are a fault storm at first use (working-set warm-up) and the need for a replacement policy when frames run out. Prefetch / readahead is a policy on top, not a different mechanism.

FIFO evicts the oldest loaded page: simple, can evict a hot page, Belady-anomaly. OPT evicts the page whose next use is farthest in the future: unrealisable, the lower bound you compare against. LRU evicts the least recently used: good approximation to OPT; exact LRU needs a stack or timestamps on every reference. Clock / second chance walks a ring; if the referenced bit is set, clear it and skip (a second chance). Hardware gives you the bit; Clock is the LRU you actually implement.

For some reference strings, FIFO produces more page faults with more frames. More memory is not always fewer faults under FIFO. OPT and stack algorithms (LRU) do not have this anomaly: a stack algorithm's resident set of size n is nested, so growing n only adds pages. If they give a string, simulate FIFO at two frame counts and show the fault counts. Mention it whenever you mention FIFO replacement.

Share a physical page among several mappings, marked read-only. The first store faults; the kernel copies the page, assigns a private writable frame, and resumes. fork uses this so the child is logically a full copy without a full copy. exec soon after means almost no copies happen. MAP_PRIVATE mmap of a file is the same idea: reads share the page cache; writes break off a private page. Snapshots and some VM balloon tricks use the same primitive.

mmap maps the file into the address space. You can parse in place (no extra userspace copy) and let the page cache be the buffer. Random access is pointer arithmetic. Costs: first-touch faults (latency jitter), harder error reporting (a fault vs a return code), and you must still msync if you need durability. read is simpler, copies into a buffer you control, and reports errors on the call. Large read-mostly files and shared mappings as IPC are the usual mmap wins. Implementation: kernel.

PIO: the CPU moves every word and often polls a status register — simple, burns a core, fine for tiny or boot-time transfers. Interrupt-driven: the CPU does other work; an IRQ says "a byte/packet is ready"; the handler or a deferred path still copies. DMA: the CPU programs a controller (addresses, length); the device is bus master; an IRQ means done or error. DMA still needs cache maintenance and an interrupt. Do not start a Linux probe lecture.

These describe how the thread waits, not how bytes move (DMA can back any of them). Blocking: the syscall sleeps until it can complete (or a signal hits). Non-blocking: return data or EAGAIN now; you poll or use select/epoll. Asynchronous: submit a request and be notified later (completion queue, callback) without sitting in the syscall. One thread can overlap compute and I/O with async; with blocking you use more threads. Do not call epoll "async I/O" unless you are precise: it is readiness, then you still read.

Contiguous: start + length. Great sequential I/O; external fragmentation; growth is painful. Linked: each block points to the next (or a FAT does). Easy growth; random access is a chain walk; one bad pointer loses the tail. Indexed: an index block (or a tree, or extents) lists data blocks. Random access is good; small files pay index overhead if you are naive. Real filesystems mix ideas: extents are "indexed, but runs of contiguous blocks".

FAT keeps a table with one entry per cluster: 0 means free, EOF ends a file, a number is the next cluster. Directories store the first cluster. Random access walks the table. The table is a single point of corruption. A UNIX inode stores a few direct block pointers and then single/double/triple indirect blocks, plus metadata (owner, mode, times, link count). Names live in directory entries that point at the inode. Extents replace many pointers with (start, length) runs on modern layouts.

A crash mid-update can leave bitmaps, trees and directories disagreeing. A journal writes intended changes to a log, commits, then writes home locations. After a crash, replay committed records. That restores crash consistency of metadata (and of data if you journal data too). It does not make every write durable the instant it returns — that is fsync / barriers. It does not fix a disk that lies about flush. Soft updates and copy-on-write filesystems are other consistency designs; mention them as alternatives, not as Linux driver trivia.

The kernel presents one inode / open-file / directory API so read does not care whether the backing store is a disk filesystem, a pipe, a socket, or a pseudo-fs. Each implementation fills in operations (read, write, lookup). Userspace sees fds. That is why you can cat a file and also read from a pipe with the same syscall. Linux dentry/inode objects are kernel material; the interview word is "one surface, many implementations".

Pipe: inherited one-way stream (parent-child, shell). Named pipe: same stream, unrelated processes, still local. Message queue: record boundaries and maybe priorities; multiple consumers selecting by type. Shared memory: bulk and latency; you must add a mutex/futex protocol and think about visibility. Signal: "please die", job control, a timer — not a payload path. Socket: bidirectional, credentials, and a path to the network if you ever need it. On Android, app-to-system RPC is Binder, not POSIX queues — frameworks.

An ACL lives on the object: "these principals may do these ops". Easy to audit one file; hard to list everything a process can still do. Revocation is "edit the list". A capability is a token the subject holds; possession is authorisation. UNIX fds are capability-like for open files (passing an fd delegates). POSIX process capabilities are a different thing: they split root into bits. Say which you mean. Isolation still starts with page tables; ACLs and capabilities decide authorised crossings.

Time-of-check to time-of-use: you stat a path, decide it is safe, then open the same path. An attacker swaps the name for a symlink in the gap. The check did not bind to the same kernel object as the use. Fixes: open then fstat on the fd; openat with a directory fd; O_CREAT|O_EXCL for exclusive create; never follow user-controlled paths from a privileged process if you can take a handle instead. The pattern is general, not only files.

Cores have store buffers and private caches. Thread A may execute data = 42; ready = 1 and thread B may observe ready == 1 while data is still stale, unless a happens-before edge orders those writes. Unlock/lock on a mutex (or a matching release/acquire atomic pair) is that edge: the locker publishes, the acquirer observes. volatile in C is not a lock and not a portable barrier (C). The OS contributes the sleep/wake side (a futex wait sees the same write that the waker published). Interview sentence: "locks give exclusion and publication."

Userspace hold times are unpredictable (you might call into a library that pages or does I/O). Sleeping is the default. The kernel has paths that must not sleep (interrupt handlers, code that already holds a spinlock on Linux) and paths whose critical sections are a few instructions with the holder running on another CPU. There, spinning is correct and cheaper than a full deschedule. Mixing the two — spinning in userspace on a lock whose holder is preempted — wastes a core and can invert priorities. Hybrid locks exist because the first dozen cycles of a short hold look like a spin win.

Low-priority L holds a lock. High-priority H blocks on that lock. Medium-priority M runs and preempts L. H is now stuck behind M even though H outranks M. That is inversion. Inheritance lets L run at H's priority until it unlocks, so M cannot sneak in. Ceiling boosts anyone who takes the lock to a predeclared ceiling. On phones this is an audio/camera/RT story: a SCHED_NORMAL thread holding a lock that an RT or audio thread needs produces glitches. Android and real-time Linux use inheritance (including PI futexes) so the UI or audio path does not wait on a background job. Keep it light unless they are hiring for RT; power interaction is power & thermal.

Instead of one tree per process indexed by VPN, keep one entry per physical frame: "this frame is (pid, vpn)" plus a hash to find a VPN quickly. Table size tracks RAM, not virtual space — attractive on huge address spaces. The downsides are: translate-this-VA becomes a search, shared pages need extra care, and the radix-tree plus TLB design is already good enough on the machines you will discuss. Mention it as an alternative organisation, not as "what Linux uses on ARM".

W(t, Δ) is the set of pages referenced in the last Δ time. If the sum of working sets exceeds RAM, almost every reference misses, the disk is saturated, and CPU utilisation falls (the CPU is waiting on paging). That is thrashing. Fixes: admit fewer processes, enlarge RAM, shrink the working set (leak, oversized cache), or a working-set / page-fault-frequency policy that suspends a job until there are frames. A trap: "the box is slow, add CPU" when the iowait and fault rates say otherwise.

Frames sit in a ring with a clock hand. On a need for a victim, look at the page under the hand. If the referenced (access) bit is 0, evict. If it is 1, clear it and advance — that page got a second chance. A hot page keeps getting its bit set by hardware and is skipped. This approximates LRU without a timestamp on every load. A dirty bit can add a third chance (prefer clean victims to skip a writeback). If the hand spins too fast, you are already thrashing.

OPT (MIN) is the offline lower bound: evict the page whose next use is farthest in the future. You cannot know the future in a general-purpose OS, but you can measure how close LRU or Clock came on a trace. If OPT still faults a lot, the working set does not fit — no clever replacement will save you. If OPT is fine and FIFO is terrible, the policy is the problem. That is why it appears in every numerical and in every "which algorithm is best" discussion.

A translator: device registers, DMA descriptors and IRQs on one side; a uniform kernel interface on the other (block, character, network). The filesystem should not know the SSD brand; the scheduler should not know the NIC. Drivers are trusted because they run with kernel privilege (or in a userspace I/O server with a narrow DMA API). How Linux binds a compatible string and runs probe is Linux kernel & BSP. Here the point is the abstraction boundary and why a bug in a driver is a kernel bug.

Several designs: fsck walks the tree after a crash and repairs (slow, last-century default). Soft updates order metadata writes so a crash leaves a reachable, slightly leaked state rather than a broken pointer. Copy-on-write / shadow paging (new tree, then an atomic root swap) never overwrites the old consistent tree. Journaling is the common middle path: a log plus home-location writes. Interviewers want you to name the problem (metadata graph torn by a crash) and at least two remedies, not a vendor's on-disk format.

A signal is an asynchronous control event with almost no payload. It can interrupt a thread between any two instructions (except where masked). The handler may call only async-signal-safe functions; malloc, printf and most locks are unsafe. Re-entrancy and interrupted syscalls (EINTR) are the tax. Use signals for "terminate", "job control", "a timer fired". Use a pipe, socket or a dedicated thread waiting on a signalfd-style descriptor if you need to turn the event into ordinary control flow. See C for the safe-function rule.

Two processes mapping the same pages are just threads with a more expensive create path: they can tear structs, lose updates, and see stale stores. You need a mutex, a process-shared futex, a semaphore, or a carefully ordered lock-free protocol — plus the same visibility story. You also need a way to agree that the mapping exists (a POSIX shm name, an inherited fd, a mapped file). Fast path is loads/stores; the hard part is the protocol. Binder exists on Android in part so most app code never writes that protocol — frameworks.

Run the guest in a deprivileged mode. Ordinary instructions execute natively. Privileged operations (load a page-table root, mask IRQs, issue I/O) trap to the hypervisor, which emulates the effect on virtual hardware and resumes the guest. This is the classic model. It requires that every sensitive instruction actually traps. Historic x86 had sensitive instructions that ran silently in user mode; that broke the model until hardware added a guest mode. Modern CPUs provide that mode; software VMMs still emulate devices.

It fails when a guest instruction is sensitive (it would reveal or change privileged state) but is not privileged (it does not trap). The hypervisor never gets control, so the guest sees the host's truth or changes state it must not. Fixes: rewrite those instructions (binary translation), or use hardware virtualization extensions that make them trap or that give the guest its own view. Interviewers want the definition of "sensitive but unprivileged", not a product name.

Namespaces virtualise names: PID (you can be PID 1 in a box), mount (your own filesystem view), network (your own interfaces and addresses), UTS, IPC, user. cgroups limit and account resources: CPU, memory, I/O, freezer. Together they are the usual container recipe. They do not give you a second kernel or a second scheduler. A kernel bug is still a host bug. Implementation knobs: Linux kernel & BSP. The concept: names vs quotas vs hardware virtualization.

Userspace: C read in libc (C); Java would sit above this via ART/JNI (Java). Trap into the kernel (dual mode). Current thread's PCB → fd table → open file (offset, vnode). VFS read: pipe/socket may block (IPC + scheduler). Regular file: page cache lookup. Hit: copy to the validated user buffer. Miss: allocate a frame, submit block I/O, state = waiting, another thread runs. DMA + IRQ complete; waiter goes ready; scheduler eventually runs it; copy out; return. Kernel path: Linux kernel & BSP. Do not continue into device tree.

One paragraph, then stop. CFS (and its fair-class successors) approximate ideal fair sharing: each task has a virtual runtime; the task that has been cheated the most runs next, so over a window everyone gets a weight-adjusted share. It is not FCFS and not textbook RR. POSIX FIFO/RR real-time classes sit above the fair class. Energy-aware scheduling, cgroup cpu controllers and Android binder-thread pools are kernel / power material. If they want a Gantt chart, they want a textbook policy, not CFS.

Dual mode keeps user code from installing its own translations. Page tables keep process A from issuing loads that resolve to process B's frames (unless a shared mapping exists). Credentials and ACLs decide authorised kernel crossings (files, IPC). Namespaces and VMs add more views or another kernel. If the MMU story is broken, none of the higher policy matters: a write goes wherever the attacker maps it. That is why "isolation" answers should start with translations, not with a firewall.

The device writes RAM. The CPU may still hold a stale line in cache, or the CPU may write back over a just-arrived packet. You need coherent interconnects or explicit cache flush/invalidate around the buffer. The device also needs a physical (or IOMMU-translated) address, not the process's virtual address. Bounce buffers exist when the device cannot reach the memory. This is still conceptual: IOMMU and Linux DMA APIs live on Linux kernel & BSP.

Split the VA into unused high bits, three VPN indices, and a page offset. The page-table base register points at the L2 table. Index 1 selects an L1 table; index 2 selects a PTE; the PTE's PFN concatenated with the offset is the PA. Permissions live in the PTE (and sometimes in upper levels for entire regions). A TLB hit skips this. Draw the boxes; name "dependent loads". If they want Linux's 4-level/5-level names, send them to the kernel page.

The child contains one thread: the one that called fork. Every other thread vanishes. If one of those threads held a mutex, the mutex stays locked in the child with no owner running to unlock it. The safe patterns are fork-then-exec (the new image has one thread and fresh locks) or to use pthread_atfork handlers that you actually understand. This is a favourite follow-up after "fork is just COW".

A wait-for graph has processes as nodes and an edge P_i → P_j if P_i waits for a resource P_j holds. With single-instance resources, a cycle is deadlock. A full resource-allocation graph also has resource nodes and assignment/request edges. With multiple instances, a cycle is necessary but not sufficient — you may still reduce the graph (Banker's-style) and finish. Detection is cycle-find plus, for multi-instance, a safe-sequence search. Graph algorithms: DSA.

Stores go to the page cache. Durability happens on writeback, msync, fsync, or eviction — not on the store instruction. A crash can lose dirty pages. Journaling of data (or a COW filesystem with a committed root) changes the story; metadata-only journals can leave a file whose size updated but whose new data did not, or the reverse, depending on mode. Interviewers want "mmap is not fsync" and a sentence on ordered vs data=journal, not an ext4 mount-option recitation.

Metadata-only: fast; after a crash the tree is consistent but file contents may be stale or contain stale junk in freshly allocated blocks if you are sloppy. Ordered: write data blocks to their home locations before committing the metadata that points at them — the usual middle path. Data=journal: log data too; safest and heaviest. Pick by whether "file contains zeros or old bytes after a crash" is acceptable. Databases often do their own WAL and want the FS out of the way (fsync semantics), which is a system design conversation.

A container calls the host kernel. The syscall ABI is large. A kernel memory-safety bug is often a host compromise. Namespaces hide names; they do not give you a second MMU for the kernel itself. A VM fails closed at the hypervisor and (usually) a guest kernel: the attack surface is virtual devices plus hypercalls, which is smaller if you keep the VMM tight. Density and start time go the other way. Use both: VMs as tenant boundaries, containers as deploy units, if the threat model says so.

Batch: readv/writev, one mmap instead of many reads, io_uring-style submission queues (Linux-specific; name the idea: amortise the crossing). Avoid: stay in userspace with a cache, use huge pages to cut TLB misses, use shared memory for a hot IPC path. The OS topic is the crossing cost (mode switch + validation + possible schedule). Micro-optimising a single getpid is not the point; the point is that a chatty ABI kills throughput. See also system design for batching at service level.

Classic VM thrashes: it keeps everyone alive and pages. A phone would feel frozen and burn flash. Android prefers to kill a cached process (oom_adj / LMK policy) and keep the foreground working set in RAM. That is admission control by death, not a different page-replacement algorithm. The theory is still working sets; the product policy is on Android frameworks.

A mutex in shared memory must live in memory both processes can see and must wake a waiter in another address space. Fast path is still an atomic in userspace. Slow path (contention) needs the kernel to sleep and wake — Linux's futex is that wait queue keyed by an address. You do not implement a futex in an OS-concepts interview; you say "userspace atomic plus a kernel sleep queue" and send details to the kernel page. Language wrappers: C++, Java (monitors are in-process unless you add IPC).

A 2 MiB or 1 GiB page occupies one TLB entry instead of 512 or more 4 KiB entries, so the TLB covers more of the working set and hit rate rises. The walk is shorter (you stop at a leaf that describes a large page). Costs: internal fragmentation, harder to move/evict, and allocation can fail if physical memory is fragmented. Mention as a TLB-capacity tool, not as a Linux THP tuning session.

If the CPU is idle, it is not "compute bound". Look at I/O wait and paging: thrashing (disk busy, high fault rate, load average high because tasks are stuck in D / uninterruptible I/O), a lock convoy, or a filesystem journal stuck on a dying disk. Memory pressure with swap or a storm of major faults matches the working-set story. On Android, LMK killing and restarting can feel like freeze-and-jank — frameworks. Do not start with a faster CPU.

Those are zombies: children exited, the parent never waited. RAM is probably fine; PID space is not. The parent is buggy (no SIGCHLD reap, or it ignored children). Fix the parent, or kill the parent so the zombies are reparented and reaped. If the parent is stuck in an infinite loop that never waits, that is a process-lifecycle bug, not a memory leak.

A fork bomb: exponential process create until the PID table, memory (even with COW, each task_struct and kernel stack costs something), or a cgroup/nproc limit stops you. The machine becomes unresponsive because the scheduler and memory allocator are drowning. Defence is a process limit (ulimit/cgroup pids), not a clever scheduler. This is a resource-isolation question as much as a fork question.

Lost update: both read, both add, both write. It is a race on a critical section that is one increment. Fix: a mutex around the increment, or an atomic fetch-add. Do not use volatile as the fix in C. Mention visibility: after the lock, other threads must see the new value — a correct mutex already publishes. If they ask you to write the code, keep the critical section to the increment; do not hold the lock across I/O.

Each philosopher picks up the left fork then waits for the right: hold-and-wait plus circular wait. Prevention: (1) a global lock order (even-numbered philosopher takes right first), (2) pick up both forks atomically (or via a waiter/arbitrator), (3) a counting semaphore of N−1 philosophers so one seat is always empty and the cycle cannot close. Detection is a wait-for cycle among five processes. This is the Coffman checklist in costume.

The audio or RT thread is high priority and needs the lock. A low-priority worker holds it. A medium-priority batch job runs and preempts the worker. The audio thread waits — inversion. Fix: priority inheritance on that lock, or do not take a sleep-lock on the audio path (lock-free ring buffer, try-lock and drop a frame). This is the light Android/RT note; do not dive into scheduler classes unless they ask — then kernel.

SIGKILL is not delivered until the thread returns to a killable context. If it is in uninterruptible sleep waiting on I/O (classic UNIX "D state"), it will not handle signals until the I/O completes or fails. The portable story: some waits are uninterruptible so a filesystem is not left half-updated. The Linux specifics (D state, hung task detector) are kernel. User takeaway: the disk or a driver is the suspect, not "kill −9 is broken".

Without a consistency scheme, bitmaps, directory entries and inodes can disagree: a name that points at a free inode, or allocated blocks that no file owns. A metadata journal would replay committed operations and restore a tree that could have existed. You might still lose the last un-fsynced data. fsck is the slow alternative. This is crash consistency, not "the journal makes every write immortal".

A context switch is thousands of cycles plus cache/TLB loss. If the quantum is on the order of the switch, the CPU spends its life in the scheduler. Response time may even get worse because of the overhead. RR needs a quantum large versus a switch and small versus a human delay. Snappy interactive behaviour is more MLFQ/fair+priority than "tiny q".

Threads: cheaper, easy to share a cache, one wild pointer or one infinite loop (without preemption of that thread's siblings... actually 1:1 threads preempt) — more importantly, one memory-corruption bug in a renderer can take the chrome if they share an address space. Processes: crash and security isolation, separate UID/sandbox, higher RAM (duplicated heaps, unless you share via IPC or a zygote-style fork). Real browsers pick processes for renderers. That is isolation over IPC cost — system design plus this page's process vs thread table.

They used a plain store to a flag without a release/acquire pair or a process-shared mutex. The payload write can stay in a store buffer or be reordered. Fix: put the payload write before a release-store on the flag, and load-acquire the flag before reading the payload; or just use a mutex around the publish. This is the visibility question in IPC clothing.

First gather a wait-for graph: who holds which lock, who waits (thread dumps, lockdep-style traces). A cycle is the smoking gun for single-instance locks. Prevention going forward: lock ranking, smaller critical sections, try-lock with backoff. Recovery now: kill a victim thread or restart the process (databases roll back a transaction). Banker's is almost never how you fix a live mutex deadlock — you do not have declared maxima. Tools are platform-specific; the vocabulary is this page.

A PID namespace: the box has its own PID 1 and its own numbering. It cannot name host tasks by their host PIDs. It still shares the kernel, so it can still issue the same syscalls (unless a filter is added) and a kernel bug still matters. Memory and CPU limits are cgroups, not namespaces. Network isolation is a network namespace. Keep the "names vs quotas vs kernel" triangle straight.

The store dirtied a cache page. No msync/fsync means the disk may have old data, new data, or a mix if writeback raced the crash. The directory may already show the new size if metadata was journaled first (or the reverse). Tell them mmap is a cache, not a durability API. For a header that must be atomic, write to a temp file and rename (atomic dir update) after fsync, which is also a system design pattern.

Demand paging: the working set is being faulted in (code, data, mapped libraries). Major faults hit disk; minor faults map pages already in the page cache (shared libs). Then the working set fits and the fault rate drops. Fixes: demand-paging is working as designed; if the storm is too long, reduce the working set, prefetch the hot path, or keep a process warm (Android zygote is this idea — frameworks). Do not call it thrashing unless the fault rate stays high and the CPU is idle.

Log daemon on the same machine: UNIX-domain socket or a named pipe (records vs stream: prefer a socket or a message-oriented protocol so lines do not tear). Shared memory only if the volume is huge and you will write a ring buffer with a futex. Off-box later: start with a stream socket and a versioned protocol so the transport can become TCP. Signals are wrong (no payload). Android apps talking to system_server: Binder — frameworks.

Between stat and chmod the user can replace the path with a symlink to /etc/passwd (or any sensitive file). The helper applied a user-controlled name twice. Fix: open the path once (with O_NOFOLLOW if needed), fstat the fd, then fchmod the same fd. Bind check and use to one object. This is the exam version of "never operate twice on a raw path from an untrusted client".

Thrashing or a working set that did not fit: the job looked busy but much of the "CPU time" was wait-on-page-fault, or the disk was the bottleneck. Extra frames let the working set stay resident, faults dropped, useful CPU rose. Check major fault counts and iowait before and after. A true CPU-bound job would have been at 100% compute with few faults and would not have doubled in speed from RAM alone.

Convoy effect under FCFS (or RR with a huge quantum). The long CPU burst blocks the short ones; they then all I/O-wait and rejoin behind it. Change to RR with a sane quantum, MLFQ (demote the compile), or a priority/fair class that reserves share for interactive work. CFS's fair share is the Linux example of "the compile does not own the machine" — one sentence, then stop.

C program calls read (C). libc traps. Kernel: fd → file → VFS. Page cache miss: allocate a frame, attach a bio, submit to the block layer, put the thread in waiting. Scheduler runs someone else. Disk DMA fills the frame; IRQ signals completion; the waiter is marked ready. Later it runs, copies bytes to the user buffer, returns the count. Privilege dropped. If this were Java, ART and JNI sit above libc (Java). Hardware/driver objects: Linux kernel & BSP.

MAP_SHARED: they share page-cache pages; a store is visible to the other and is a candidate for writeback to the file. MAP_PRIVATE: reads share until a write; the write COWs a private page that will not go back to the file (and the sibling still sees the old page). After fork, the child's private maps are COW against the parent as well. Ask which flags they used before you debug "why doesn't the other process see my write?".

Causes: tiny RR quantum, too many runnable threads (1:1 thread-per-connection without a pool), lock ping-pong (threads wake each other for tiny critical sections), or blocking I/O with no batching. Fixes: fewer threads (event loop or a pool), longer quantum / fair scheduler, coarsen the locking, batch syscalls, use shared memory instead of a chatty pipe. Switching is not free; the indirect cache cost is why. DSA-level "too many workers" is the same idea as too many threads here.