Operating System Interview Questions and Answers

Answer

A program is a passive artefact, a file of instructions sitting on disk, for example the ELF binary at /usr/bin/nginx. It consumes disk, not CPU, and it has no state. A process is that program in execution: the kernel has loaded it into memory, given it a PID, a virtual address space with text, data, heap and stack segments, a set of open file descriptors, a user and group identity, and a Process Control Block that tracks all of it.

Two people running nginx create two processes from one program, fully isolated from each other, because each gets its own page tables. A thread is a unit of execution inside a process. Threads of the same process share the address space, the heap, global variables, file descriptors and signal handlers, but each thread gets its own stack, its own register set, its own program counter and its own thread ID.

The picture that lands well in an interview: the program is the recipe printed in a book, the process is one cook actually cooking it in a kitchen stocked with ingredients, and the threads are several cooks working in that same kitchen, sharing the ingredients and the stove. Sharing is why threads are cheap to create and cheap to switch between, and also why two threads writing the same variable corrupt it while two processes cannot. On Linux the distinction is thinner than textbooks suggest: both are task_struct entries created by clone(), and a thread is simply a task created with CLONE_VM so it shares the memory map. That is why ps shows threads only when you ask for them.

$ ps -eo pid,ppid,nlwp,comm | grep nginx
  PID  PPID NLWP COMMAND
 1420     1    1 nginx      # master process
 1421  1420    4 nginx      # worker, 4 threads inside ONE process

$ ps -eLf | grep 1421        # -L shows individual threads (LWPs)
UID   PID  PPID   LWP  NLWP CMD
www  1421  1420  1421     4 nginx: worker
www  1421  1420  1433     4 nginx: worker

/* One address space, shared globals, separate stacks */
int counter = 0;              /* shared by all threads */

void *worker(void *arg) {
    int local = 0;            /* private, lives on this thread stack */
    counter += 1;             /* SHARED, needs a lock */
    return NULL;
}

Answer

The Process Control Block is the kernel data structure that represents a process, called task_struct on Linux. It holds the process identifier and parent identifier, the current process state, the saved CPU register set including the program counter and stack pointer, scheduling information such as priority, nice value and accumulated runtime, memory management information which is the pointer to the page table base plus the memory map of every mapped region, accounting data like CPU time used and limits, the open file descriptor table, the signal handler table and pending signal mask, the working directory and root directory, and the credentials, that is uid, gid and capabilities. The kernel keeps these in a list and the scheduler picks the next runnable one from it.

The PCB matters for context switching because a switch is precisely the act of writing the outgoing process's volatile state into its PCB and loading the incoming process's state out of its PCB. The bigger and more expensive the state, the costlier the switch. Registers are cheap to save, a few dozen stores.

What is expensive is the memory management part: switching to a different process means loading a different page table base register, which on x86 means writing CR3, and that invalidates cached address translations. Switching between two threads of the same process skips exactly that part, because the address space pointer is identical, and that single fact is the whole reason threads are cheaper than processes. In an interview, connecting the PCB contents to context switch cost is what turns a recall answer into an understanding answer.

/* What the kernel keeps per process, conceptually (Linux: task_struct) */
struct PCB {
    pid_t      pid, ppid;
    int        state;             /* NEW READY RUNNING WAITING TERMINATED */
    Registers  cpu_regs;          /* general regs, PC, SP, flags */
    int        prio, nice;
    u64        vruntime, cpu_time_used;
    struct mm *mm;                /* page table base + memory map */
    FileTable *open_files;        /* SHARED across threads */
    SigTable  *sig_handlers;      /* SHARED across threads */
    Creds      cred;              /* uid, gid, capabilities */
};

$ ls /proc/1420/       # the PCB, exposed as files
cmdline  cwd  environ  fd/  limits  maps  sched  stat  status  task/

$ grep -E 'Threads|VmRSS|State' /proc/1420/status
State:   S (sleeping)
Threads: 4
VmRSS:   918244 kB

Answer

The five state model is new, ready, running, waiting or blocked, and terminated. New to ready happens when the kernel finishes allocating the PCB and address space and puts the process on the run queue, so it is now eligible for CPU. Ready to running is dispatch, performed by the scheduler when it picks this process.

Running to ready is preemption, caused by the time quantum expiring or by a higher priority process becoming runnable, never by the process itself. Running to waiting is a voluntary block: the process issued a blocking system call such as read on a socket with no data, or waited on a lock, or called sleep, so the kernel takes it off the CPU and parks it on a wait queue. Waiting to ready is wakeup, triggered by the external event completing, disk interrupt fires, data arrives, lock released.

Note carefully that waiting goes to ready, never directly to running: the process must be rescheduled like everyone else, and drawing that arrow straight to running is the single most common mistake on this question. Running to terminated is exit, either by calling exit or by being killed. The transition a process can never make on its own is ready to running, which is the scheduler's decision alone, and equally a blocked process cannot unblock itself because by definition it is waiting on someone else. Linux refines the model: TASK_RUNNING covers both ready and running, TASK_INTERRUPTIBLE is a sleep that signals can break, TASK_UNINTERRUPTIBLE is the D state that appears when a process is stuck in disk or NFS I/O and cannot even be killed with SIGKILL, and EXIT_ZOMBIE is the terminated but unreaped state.

  new  ==(admit)==>  READY  ==(scheduler dispatch)==>  RUNNING
                       ^   ^                                |   |
                       |   |==(preempt: quantum expiry)=====|   |
                       |                                        |
                (wakeup: I/O done,                     (blocking syscall,
                 lock released)                         wait on a lock)
                       |                                        |
                    WAITING <================================

  RUNNING ==(exit or killed)==> TERMINATED (zombie until parent reaps)

There is NO arrow from WAITING straight to RUNNING.

$ ps -eo pid,stat,comm | head
  PID STAT COMMAND
  912 S    sshd        # S = interruptible sleep (WAITING)
 1044 R    java        # R = runnable (READY or RUNNING)
 1180 D    dd          # D = uninterruptible sleep, stuck in I/O
 1201 Z    backup.sh   # Z = zombie, exited but not reaped
 1310 T    gdb         # T = stopped

Answer

A context switch saves the volatile CPU state of the outgoing task into its PCB and restores the incoming task's state. Concretely that is the general purpose registers, the program counter, the stack pointer, the processor status or flags register, and on x86 optionally the floating point and vector register state, which modern kernels defer with lazy FPU switching because those registers are large. Then the kernel updates scheduler bookkeeping, runtime accounting and the current task pointer.

For a switch between two different processes there is one more step that dominates the cost: the address space changes, so the kernel loads a new page table base into CR3. On older hardware that flushes the entire Translation Lookaside Buffer, so every subsequent memory access misses the TLB and must walk the page table, and the L1 and L2 caches are effectively cold for the new working set. Modern x86 has Process Context Identifiers which tag TLB entries with an address space ID so the full flush can be avoided, but the caches are still polluted.

The direct cost of the switch itself is small, roughly one to five microseconds, while the indirect cost of cache and TLB refill can be tens of microseconds depending on the working set. A thread to thread switch inside the same process skips the CR3 write entirely, keeps the TLB valid, and keeps most of the cache warm because the two threads share the same data. That is the quantified answer: the same registers are saved, but there is no address space change, no TLB invalidation and no cold cache, which typically makes it several times cheaper.

PROCESS switch (P1 to P2)          THREAD switch (T1 to T2, same process)
=================================  =====================================
save general registers, PC, SP     save general registers, PC, SP
save or lazy save FPU and SIMD     save or lazy save FPU and SIMD
update scheduler accounting        update scheduler accounting
LOAD NEW PAGE TABLE (write CR3)    (skipped, same mm_struct)
TLB invalidated or PCID tagged     TLB stays valid
caches cold for new working set    caches mostly warm

$ vmstat 1
 r  b   swpd   free   si  so   in     cs  us sy id wa
 4  0      0 512000    0   0  980  18500  22  6 72  0
# cs = context switches per second. 18k/s across 4 cores is healthy.
# 400k/s with high sy and low us usually means lock contention.

$ pidstat -w -p 4102 1
   UID  PID   cswch/s  nvcswch/s  Command
  1000 4102    412.00    9840.00  java
# nvcswch = involuntary (preempted). Very high = CPU contention.

Answer

fork creates a new process that is a near duplicate of the caller. It is called once and returns twice: in the parent it returns the PID of the newly created child, a positive integer, and in the child it returns 0. On failure it returns a negative value in the parent and no child exists, typically because the process or user hit RLIMIT_NPROC or the system ran out of PIDs or memory.

That asymmetric return value is the only way the two identical looking code paths can tell each other apart, which is why every fork example immediately branches on the result. The child inherits a copy of the address space, the open file descriptors including their shared file offsets, the environment, the working directory and the signal dispositions. It does not inherit pending signals, file locks, or the parent's threads: fork in a multithreaded process gives a child with exactly one thread, the one that called fork, which is why a mutex held by another thread at fork time stays locked forever in the child and why only async signal safe calls are legal between fork and exec.

Copy on write is the optimisation that makes fork cheap. The kernel does not physically copy the parent's pages. It marks every writable page in both processes as read only and shares the same physical frames, incrementing reference counts.

Only when either side writes does the CPU raise a page fault, and the kernel then allocates a fresh frame, copies that single 4KB page, and marks it writable in the writer. So fork copies page tables and PCB metadata immediately, and copies data pages lazily, one page at a time, only when written.

#include <stdio.h>
#include <unistd.h>
#include <sys/wait.h>

int main(void) {
    int x = 10;
    pid_t pid = fork();

    if (pid < 0) {
        perror("fork failed");
        return 1;
    } else if (pid == 0) {
        x += 5;                       /* triggers copy on write of that page */
        printf("child  pid=%d ppid=%d x=%d\n", getpid(), getppid(), x);
    } else {
        wait(NULL);
        printf("parent pid=%d child=%d x=%d\n", getpid(), pid, x);
    }
    return 0;
}

/* Output:
   child  pid=4312 ppid=4311 x=15
   parent pid=4311 child=4312 x=10     <- parent x unchanged
*/

$ grep -E 'Private_Dirty|Shared_Clean' /proc/4312/smaps_rollup
Shared_Clean:     41220 kB    # still shared with the parent, COW pending
Private_Dirty:      132 kB    # pages this child actually wrote

Answer

The counting rule is that each fork doubles the number of processes, so n consecutive unconditional forks produce 2 to the power n total processes, of which 2 to the power n minus 1 are children. Three forks give 8 processes, so the printf after them executes 8 times. The way to reason about it on a whiteboard is a binary tree: start with one node, and every fork call level splits every existing node into two.

Conditional forks are where candidates fall over. If the code is fork() && fork(), C short circuit evaluation applies: the second fork runs only in the process where the first fork returned non zero, that is only in the parent, because the child got 0. So fork() && fork() creates 3 processes total, not 4.

Similarly fork() || fork() runs the second fork only where the first returned 0, the child, again 3 processes. The second trap is the difference between number of processes and number of output lines. If you print with a trailing newline to a terminal, stdout is line buffered and each process flushes its own line, so lines equal processes.

If you redirect to a file, stdout becomes fully buffered, and if you print without flushing before forking, the unflushed buffer content is duplicated into every child and printed again at exit, so the line count multiplies. That is the classic gotcha in Zoho and Adobe style rounds, and the correct thing to say is that you would call fflush(stdout) before fork to make the behaviour deterministic.

#include <stdio.h>
#include <unistd.h>

int main(void) {
    fork();
    fork();
    fork();
    printf("hello\n");   /* runs in 2^3 = 8 processes */
    return 0;
}

/* Variants worth memorising:
   fork(); fork();                  -> 4 processes
   fork() && fork();                -> 3 processes (2nd fork only in parent)
   fork() || fork();                -> 3 processes (2nd fork only in child)
   for (i = 0; i < 3; i++) fork();  -> 8 processes
*/

/* The buffering trap */
int main(void) {
    printf("hi");        /* no newline, sits in the stdio buffer */
    fork();
    return 0;            /* buffer flushed at exit in BOTH processes */
}
$ ./a.out            # terminal: line buffered, prints hi once
hi
$ ./a.out > out.txt  # file: fully buffered, buffer was duplicated
$ cat out.txt
hihi
/* Fix: fflush(stdout) before fork(). */

Answer

A zombie is a process that has already terminated but whose parent has not yet called wait or waitpid to collect its exit status. The kernel has torn down its memory, closed its file descriptors and released almost everything, but it must keep one thing alive, the entry in the process table holding the PID and the exit status, because the parent is still entitled to read it. In ps the state column shows Z and the command shows as defunct.

A zombie consumes no CPU and no memory beyond that table entry, so a handful are harmless, but a parent that never reaps in a loop leaks PIDs until the system hits kernel.pid_max and no new process can be created anywhere on the box, which is a genuine production outage. An orphan is the opposite case: the parent died first while the child is still running. The child is immediately reparented, classically to PID 1 which is init, and on a systemd box either to PID 1 or to the nearest ancestor marked as a subreaper, which is how systemd keeps a service's children inside its own cgroup.

Since PID 1 is written to call wait in a loop forever, an orphan is always eventually reaped when it exits, so orphans are harmless. The fixes for zombies are to call waitpid in the parent, to install a SIGCHLD handler that reaps in a loop with WNOHANG, or to set SIGCHLD to SIG_IGN so the kernel reaps automatically at the cost of never seeing an exit status. In containers the same bug appears when your application runs as PID 1 and does not reap, which is why Docker ships an init flag that inserts a tiny reaping init process.

$ ps -eo pid,ppid,stat,comm | grep -w Z
  PID  PPID STAT COMMAND
 8123  8100 Z    worker <defunct>       # parent 8100 never called wait

$ cat /proc/sys/kernel/pid_max
4194304                                 # leak enough zombies and you hit this

/* Reaping properly with a SIGCHLD handler */
#include <signal.h>
#include <sys/wait.h>

void reap(int sig) {
    /* loop: several children can exit before one signal is delivered */
    while (waitpid(-1, NULL, WNOHANG) > 0) { }
}

int main(void) {
    struct sigaction sa;
    sa.sa_handler = reap;
    sigemptyset(&sa.sa_mask);
    sa.sa_flags = SA_RESTART | SA_NOCLDSTOP;
    sigaction(SIGCHLD, &sa, NULL);
    /* ... fork children freely ... */
}

/* Blunt alternative: signal(SIGCHLD, SIG_IGN) makes the kernel auto reap,
   but then you can never read a child exit status. */

Answer

The shell implements every external command with the fork then exec then wait pattern. The shell forks, producing a child that is a duplicate of the shell. In the child it does any redirection setup, dup2 to point file descriptor 1 at a file, close unused descriptors, then calls one of the exec family. exec does not create a process.

It replaces the current process image: the kernel tears down the existing text, data, heap and stack, loads the new program's segments from the binary, resets the program counter to the new entry point, and keeps the same PID, the same parent, the same open file descriptors unless they are marked close on exec, and the same working directory. On success exec never returns, which is why correct code always has an error handler on the line right after the exec call and usually calls _exit there. Meanwhile the parent shell calls wait or waitpid, blocks until the child terminates, and reads the exit status, which is what populates the status variable in bash.

If you end the command with an ampersand, the shell skips the blocking wait and reaps asynchronously through SIGCHLD instead. The reason the design splits creation from loading, instead of offering a single spawn call, is precisely so the child can adjust its environment in between: that gap is where redirection, pipes, setuid drops, resource limits and signal resets happen, and no single call could offer that flexibility. The exec family variants differ only in how arguments and environment are passed: l takes a list, v takes a vector, p searches PATH, e takes an explicit environment array.

#include <stdio.h>
#include <unistd.h>
#include <sys/wait.h>

int main(void) {
    pid_t pid = fork();

    if (pid == 0) {
        /* child: this gap is where a shell wires up redirection */
        freopen("out.txt", "w", stdout);
        execlp("ls", "ls", "-l", (char *)NULL);
        perror("exec failed");   /* reached ONLY if exec failed */
        _exit(127);
    } else {
        int status;
        waitpid(pid, &status, 0);
        if (WIFEXITED(status))
            printf("child exited with %d\n", WEXITSTATUS(status));
        else if (WIFSIGNALED(status))
            printf("child killed by signal %d\n", WTERMSIG(status));
    }
    return 0;
}

/* exec family: execl execlp execle execv execvp execvpe
   l = arg list, v = arg vector, p = search PATH, e = explicit environ
   PID, parent, cwd and open fds SURVIVE exec.
   text, data, heap and stack are REPLACED. */

Answer

User level threads are managed entirely by a library in user space, and the kernel sees only one schedulable entity. Creation, switching and scheduling are just function calls, so they are extremely fast, and they work even on kernels with no thread support. The fatal weakness is that a blocking system call in any one thread blocks the entire process, because the kernel does not know the other threads exist, and the process can never use more than one CPU core.

Kernel level threads are created and scheduled by the kernel, so each blocks independently and the scheduler can place them on different cores for true parallelism, at the cost of a system call for creation and a kernel mediated context switch. The three mapping models follow from that. Many to one maps many user threads onto a single kernel thread, giving fast switching but no parallelism and process wide blocking, which is what old green thread runtimes did.

One to one maps each user thread to its own kernel thread, giving full parallelism and independent blocking, at the cost that ten thousand threads mean ten thousand kernel objects and heavy scheduler load. Many to many multiplexes m user threads over n kernel threads with n less than or equal to m, in theory the best of both, but the scheduler activation machinery proved so complex that Solaris and others abandoned it. Linux uses strict one to one through NPTL, where every pthread is a task created by clone with CLONE_VM, CLONE_FS, CLONE_FILES and CLONE_THREAD. Modern language runtimes rebuilt many to many in user space instead, and Go goroutines and Java virtual threads are the 2026 examples worth naming.

MANY TO ONE            ONE TO ONE (Linux NPTL)      MANY TO MANY
 u u u u                 u   u   u   u                 u u u u u
  \ | | /                |   |   |   |                  \ \ | / /
     K                   K   K   K   K                   K   K   K

 one blocking call       true parallelism              m user threads over
 blocks everything       heavy past 10k threads        n kernel threads

$ pstree -p 2410
java(2410)-+-{java}(2411)
           |-{java}(2412)      # each {} is a kernel scheduled thread
           |-{java}(2413)

/* pthread_create on Linux is clone() with sharing flags */
clone(CLONE_VM | CLONE_FS | CLONE_FILES | CLONE_SIGHAND | CLONE_THREAD, ...);

$ cat /proc/sys/kernel/threads-max
255432

Answer

The main mechanisms are anonymous pipes, named pipes or FIFOs, System V and POSIX message queues, shared memory, Unix domain and network sockets, and signals. Pipes are unidirectional byte streams between related processes, created before fork so both sides inherit the descriptors, with a kernel buffer of 64KB by default; they carry no message boundaries, so the receiver must frame the data itself. Named pipes are the same thing with a filesystem path, so unrelated processes can open them, still unidirectional and still a byte stream.

Message queues preserve message boundaries and priorities and let a reader select by message type, which pipes cannot do, but every message is copied into the kernel and back out. Shared memory maps the same physical pages into two address spaces, so after setup there are zero copies and zero system calls per transfer, which makes it by far the fastest, but it provides no synchronisation at all, so you must pair it with semaphores or a futex. Sockets are the only mechanism that works across machines, and Unix domain sockets are the local, faster variant that also supports passing file descriptors between processes.

Signals carry no payload beyond a number, so they are notification, not communication. For a 4KB message I would use a Unix domain socket or a pipe: the copy cost is trivial, the API is simple, framing and blocking semantics are well understood, and it composes with epoll. For a 500MB dataset I would use shared memory with a semaphore or an eventfd for handshaking, because copying half a gigabyte through the kernel twice is pure waste; the producer writes into the mapping and only a small notification crosses the boundary.

MECHANISM        BOUNDARIES  COPIES  CROSS HOST  NEEDS SYNC  TYPICAL USE
===============  ==========  ======  ==========  ==========  ================
pipe             no          2       no          no          shell pipelines
FIFO (named)     no          2       no          no          unrelated procs
message queue    yes         2       no          no          priority messaging
shared memory    n/a         0       no          YES         bulk, low latency
unix socket      yes (dgram) 2       no          no          local RPC, fd pass
TCP socket       no          2+      YES         no          across machines
signal           n/a         0       no          n/a         notification only

$ ipcs -m
key        shmid   owner  perms  bytes       nattch
0x000005dc 32769   app    600    524288000        2

$ ls /dev/shm/
ingest_buffer            # POSIX shared memory object, 500 MB

/* 500MB path: map once, then zero syscalls per record */
int fd = shm_open("/ingest_buffer", O_CREAT | O_RDWR, 0600);
ftruncate(fd, 500L * 1024 * 1024);
void *p = mmap(NULL, 500L*1024*1024, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0);

Answer

pipe(fd) fills a two element array where fd[0] is the read end and fd[1] is the write end, and it must be called before fork so that both processes inherit both descriptors. Immediately after fork, each side closes the end it does not use. This is not tidiness, it is required for correctness.

A pipe returns end of file to the reader only when the reference count on the write end drops to zero. If the reading process keeps its own inherited copy of the write end open, that count never reaches zero, read blocks forever and the program hangs; this is the single most common pipe bug and the exact thing the interviewer is probing. The mirror case matters too: if every read end is closed and a process writes, the kernel sends SIGPIPE, whose default action is to kill the writer.

That is why head closing a pipe terminates the upstream command in a shell pipeline, and why servers usually ignore SIGPIPE and handle the EPIPE error instead. Other properties worth stating: a pipe is unidirectional, so two way communication needs two pipes; the kernel buffer is 64KB by default on Linux, and writes block when it is full while reads block when it is empty, which gives you flow control for free; and writes of up to PIPE_BUF, which is 4096 bytes on Linux, are atomic, so concurrent writers staying under that size will not interleave. To build a shell pipeline you combine this with dup2 to move fd[1] onto standard output in the writer and fd[0] onto standard input in the reader.

#include <stdio.h>
#include <string.h>
#include <unistd.h>

int main(void) {
    int fd[2];
    char buf[128];

    if (pipe(fd) < 0) { perror("pipe"); return 1; }

    if (fork() == 0) {
        close(fd[0]);                    /* child WRITES: close read end */
        write(fd[1], "status=ok", 9);
        close(fd[1]);                    /* closing signals EOF to reader */
        _exit(0);
    } else {
        close(fd[1]);                    /* parent READS: MUST close write end */
        ssize_t n = read(fd[0], buf, sizeof buf - 1);
        buf[n] = 0;
        printf("parent got: %s\n", buf); /* parent got: status=ok */
        close(fd[0]);
    }
    return 0;
}

/* Shell pipeline, ls | wc :
   child1: dup2(fd[1], STDOUT_FILENO); close both; exec ls
   child2: dup2(fd[0], STDIN_FILENO);  close both; exec wc  */

$ mkfifo /tmp/jobs      # named pipe: unrelated processes can open it
$ cat /tmp/jobs &
$ echo "run" > /tmp/jobs

Answer

Under non preemptive or cooperative scheduling, once a process gets the CPU it keeps it until it voluntarily gives it up, either by blocking on I/O or by terminating, so the scheduler is invoked only on those two transitions. Under preemptive scheduling the kernel can forcibly take the CPU away, typically when a timer interrupt fires and the time quantum has expired, or when a higher priority process becomes runnable. Non preemptive scheduling is simpler and has no risk of a data structure being left half updated because a switch happened mid operation, but a single CPU bound process can monopolise the machine and interactive response collapses; that is why cooperative scheduling in early Windows and Mac systems meant one hung application froze the whole desktop.

Preemption gives you responsiveness, fairness and the ability to enforce priority, which is why every general purpose OS since the 1990s is preemptive. The costs are real and interviewers want them named. First, context switch overhead becomes a function of how aggressively you preempt, so a very small quantum burns CPU on switching rather than work.

Second, preemption is exactly what makes race conditions possible: a thread can now be interrupted between reading a variable and writing it back, so every shared structure needs synchronisation. Third, preempting a thread that holds a lock creates convoying and, at worst, priority inversion. Fourth, kernel code itself must be written to be preemption safe, which is why Linux has a configurable preemption model and why real time kernels push preemption deeper into the kernel. FCFS and non preemptive SJF are the classic non preemptive algorithms; round robin, SRTF and preemptive priority are the preemptive ones.

Answer

FCFS runs jobs in arrival order with no preemption. With P1 of burst 24, then P2 of 3 and P3 of 3, all arriving at time zero, the Gantt chart is P1 from 0 to 24, P2 from 24 to 27 and P3 from 27 to 30. Waiting time is start time minus arrival time, so P1 waits 0, P2 waits 24 and P3 waits 27, giving an average of 51 divided by 3, which is 17 time units.

Turnaround time is completion minus arrival, so 24, 27 and 30, averaging 27. Now reverse the order so the two short jobs run first: P2 from 0 to 3, P3 from 3 to 6, P1 from 6 to 30. Waiting becomes 0, 3 and 6, averaging 3.

The same three jobs, the same total work, the same finish time of 30, and average waiting time drops from 17 to 3 purely from ordering. That gap is the convoy effect: one long CPU bound job at the head of the queue makes every short job behind it wait, exactly the way a slow truck on a single lane road creates a convoy of cars. The practical damage is worse than the arithmetic suggests, because the short jobs are usually the I/O bound interactive ones.

While they queue behind the long job the disk and the network sit idle, and when they finally get the CPU they run for a millisecond and block again, so device utilisation collapses. This is the standard motivation for SJF, which provably minimises average waiting time, and for round robin, which caps how long any single job can hold the CPU.

FCFS, all arrive at t=0

|          P1 (24)          |  P2 (3) |  P3 (3) |
0                          24        27        30

Process  Burst  Start  Completion  Turnaround  Waiting
=======  =====  =====  ==========  ==========  =======
P1          24      0          24          24        0
P2           3     24          27          27       24
P3           3     27          30          30       27
                                 avg TAT=27   avg WT=17

Same jobs, short ones first (this is SJF)

| P2 |  P3 |            P1 (24)          |
0    3     6                             30

P2 waits 0, P3 waits 3, P1 waits 6   ->   avg WT = 3

Same work, same makespan of 30, average wait falls 17 to 3.
That gap is the convoy effect.

Answer

Round robin is FCFS with preemption on a fixed time quantum. Ready processes sit in a circular queue, the scheduler dispatches the head, and if the process is still running when the quantum expires the timer interrupt preempts it and puts it at the tail. A process that blocks or finishes early gives the CPU up sooner.

The guarantee round robin provides is bounded waiting: with n processes and quantum q, no process waits more than n minus 1 times q before it runs again, which is exactly what makes interactive systems feel responsive. Choosing q is a trade off against context switch cost. If q is very large, larger than the longest CPU burst, round robin degenerates into FCFS and the convoy effect returns.

If q is very small, say one millisecond with a switch costing 50 microseconds, you spend roughly five percent of every cycle switching rather than working, and at extreme settings the machine can spend more time switching than executing, which shows up as a huge cs number in vmstat and high system CPU with no throughput. The standard rule of thumb is to set q so that roughly 80 percent of CPU bursts complete within one quantum, which in practice lands between 10 and 100 milliseconds on general purpose systems. Note the counterintuitive part interviewers like: average turnaround time is not monotonic in q, so a smaller quantum often makes average turnaround worse even while it improves response time, which means you must say which metric you are optimising. Linux no longer uses fixed quantum round robin for normal tasks; CFS computes a dynamic slice from the scheduling period divided by the number of runnable tasks, weighted by nice value.

Round robin, quantum q=4, all arrive t=0: P1=24, P2=3, P3=3

| P1 | P2 | P3 |            P1 (20 left)            |
0    4    7    10                                    30

Process  Burst  Completion  Turnaround  Waiting
=======  =====  ==========  ==========  =======
P1          24          30          30        6
P2           3           7           7        4
P3           3          10          10        7
                          avg TAT=15.67  avg WT=5.67

Quantum sensitivity on the same workload
q = 1   -> best response time, ~29 switches, heavy overhead
q = 4   -> avg WT 5.67, 3 preemptions
q = 100 -> identical to FCFS, avg WT 17, convoy effect returns

$ vmstat 1     # cs spiking with low us and high sy = quantum too small
 r  b   free    in      cs  us sy id wa
 6  0 402000  1200  410000   9 58 33  0

$ sysctl kernel.sched_min_granularity_ns
kernel.sched_min_granularity_ns = 3000000     # CFS floor, 3 ms

Answer

A race condition exists when the correctness of a computation depends on the relative timing of two or more threads, so the same program produces different results on different runs. The canonical case is a shared counter incremented by two threads. The single line counter += 1 compiles to at least three machine instructions: load the value into a register, add one, store it back.

If a preemption or a second core lands between the load and the store, both threads read the same old value, both add one, both store, and one increment is silently lost. A critical section is the region of code that accesses the shared resource and must therefore be executed by only one thread at a time. Any correct solution to the critical section problem must satisfy three properties, and interviewers expect all three by name.

Mutual exclusion: if one process is executing in its critical section, no other process may be executing in its critical section. Progress: if no process is in its critical section and some processes want to enter, only those not in their remainder section may participate in deciding who enters next, and the decision cannot be postponed indefinitely, which is a formal way of saying no deadlock and no process outside the contest may block entry. Bounded waiting: there must exist a limit on how many times other processes are allowed to enter their critical sections after a process has requested entry and before that request is granted, which rules out starvation.

Solutions must also assume nothing about relative process speeds or the number of CPUs, which is why naive turn taking flags fail. In real code the fix is a mutex or an atomic operation, not a hand rolled algorithm.

/* The lost update, in three machine instructions */
counter += 1;
   mov  eax, [counter]     ; load
   add  eax, 1             ; increment
   mov  [counter], eax     ; store

Thread A: load(0)  add->1            store(1)
Thread B:          load(0)  add->1            store(1)
Result: counter = 1 after two increments. One update lost.

/* Reproduce it in ten lines */
#include <pthread.h>
long counter = 0;
void *bump(void *a) {
    for (long i = 0; i < 1000000; i++) counter += 1;
    return NULL;
}
/* 2 threads, expected 2000000, observed typically 1.1M to 1.9M */

THREE REQUIREMENTS
1. Mutual exclusion : at most one thread inside the critical section
2. Progress         : selection cannot be postponed indefinitely, no deadlock
3. Bounded waiting  : a finite bound on how many others may enter first

Answer

A mutex is a locking mechanism with ownership: the thread that locks it is the only one that may unlock it, and that ownership is what allows priority inheritance and recursive locking to be implemented. It protects a critical section. A semaphore is a signalling mechanism, an integer with two atomic operations, wait which decrements and blocks at zero, and signal which increments and wakes a waiter.

It has no ownership, so any thread may signal a semaphore another thread waited on, which is exactly what you need for producer consumer handoff and for ordering events across threads. A binary semaphore has values 0 and 1 only, so it looks like a mutex, but the missing ownership means a thread can accidentally signal a semaphore it never waited on, releasing a critical section it does not hold, and no priority inheritance is possible. A counting semaphore is initialised to N and lets up to N threads through at once, which is how you model a pool of N identical resources, for example a database connection pool of 20 or a rate limiter admitting 5 concurrent uploads.

A spinlock does not block at all; a thread that fails to acquire it loops on an atomic test until it succeeds, burning CPU. A spinlock is right when three conditions hold together: you are on a multiprocessor, the critical section is very short, on the order of a few dozen instructions, and the cost of a blocking context switch, one to five microseconds plus cache damage, would exceed the expected spin time. That is why the Linux kernel uses spinlocks for short critical sections and why you must never sleep while holding one. In application code spinning is almost always wrong, and on a single core it is strictly wrong, because the lock holder cannot run while you spin.

PRIMITIVE          OWNERSHIP  BLOCKS  COUNT  TYPICAL USE
=================  =========  ======  =====  =========================
mutex              yes        yes     1      protect a critical section
binary semaphore   no         yes     1      signalling, 0/1 handshake
counting semaphore no         yes     N      pool of N resources
spinlock           yes        NO      1      very short CS, multicore

/* Counting semaphore as a connection pool limiter */
sem_t pool;
sem_init(&pool, 0, 20);          /* 20 DB connections */

void handle_request(void) {
    sem_wait(&pool);             /* blocks when 20 are already in flight */
    Conn *c = checkout();
    query(c);
    checkin(c);
    sem_post(&pool);
}

/* Mutex: ownership means only the locker may unlock */
pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_lock(&m);
balance += amount;
pthread_mutex_unlock(&m);

/* Spinlock: correct only for very short CS on multicore */
pthread_spinlock_t s;
pthread_spin_init(&s, PTHREAD_PROCESS_PRIVATE);
pthread_spin_lock(&s);
list_head = node;                /* a few instructions, no syscalls */
pthread_spin_unlock(&s);

Answer

Deadlock requires all four Coffman conditions to hold simultaneously. Mutual exclusion: at least one resource is held in a non sharable mode, so only one process can use it at a time. Hold and wait: a process is holding at least one resource while waiting to acquire additional resources held by others.

No preemption: a resource cannot be forcibly taken from a process, it must be released voluntarily. Circular wait: there is a set of waiting processes P0 through Pn where P0 waits for a resource held by P1, P1 waits for one held by P2, and Pn waits for one held by P0. Break any single condition and deadlock becomes impossible, which is the basis of every prevention scheme.

The important nuance is that the first three are usually inherent to the problem while the fourth is the one you can actually attack in production, normally by imposing a global ordering on lock acquisition. Now the practical case: a fixed size thread pool where each task submits a subtask to the same pool and blocks waiting for its result. Say the pool has 10 threads and 10 tasks each submit a child and wait.

All 10 threads are held, the children sit in the queue, and nothing can finish. Map it onto the conditions: the threads are the non sharable resource, so mutual exclusion holds; each task holds a thread while waiting for another, so hold and wait holds; you cannot yank a thread away from a running task, so no preemption holds; and the wait is circular through the queue, since parents wait on children that wait on parents to release threads. All four hold, so it is a genuine deadlock, and the fix is either a separate pool for subtasks or making the parent help execute the queued work instead of blocking.

1. Mutual exclusion  : resource usable by one process at a time
2. Hold and wait     : holding one resource while requesting another
3. No preemption     : resources released only voluntarily
4. Circular wait     : P0 -> P1 -> P2 -> ... -> Pn -> P0

ALL FOUR must hold. Break one and deadlock cannot occur.

/* Thread pool self deadlock: all four conditions present */
ExecutorService pool = Executors.newFixedThreadPool(10);

Runnable parent = () -> {
    Future<Integer> child = pool.submit(() -> compute());  /* same pool */
    child.get();                 /* BLOCKS while holding a pool thread */
};
for (int i = 0; i < 10; i++) pool.submit(parent);
/* 10 threads held, 10 children queued forever, throughput zero */

/* Fixes: a separate pool for children, or CompletableFuture composition
   so the parent never blocks a worker thread. */

$ jstack 4102 | grep -c 'waiting on condition'
10

Answer

A system call is the controlled doorway from user mode into kernel mode. Your library function loads a syscall number into a register, on x86 64 that is rax, puts arguments in rdi, rsi, rdx and so on, and executes the syscall instruction. The CPU switches from ring 3 to ring 0, swaps to the kernel stack for that thread, and jumps to a fixed entry point.

The kernel validates the arguments, notably that any pointer you passed actually belongs to your address space, dispatches through the system call table to the handler, does the work, places the return value in rax and executes sysret to drop back to user mode. If the requested data is not ready, read blocks the calling thread, which is a full context switch to another task. The expense has several parts.

The mode transition itself is the cheapest piece today, roughly 50 to 100 nanoseconds, but Spectre and Meltdown mitigations made it materially worse: kernel page table isolation means the entry and exit paths swap page tables, adding TLB pressure, and speculation barriers add fixed cost. Then the kernel path pollutes the instruction cache and the branch predictors your user code was relying on. Multiply that by a workload doing a million small reads a second and it dominates the profile. That is why the ecosystem batches: readv and writev move several buffers per call, sendfile and splice avoid copying through user space at all, epoll reports many ready descriptors in one call rather than polling each, mmap turns file access into ordinary memory access with no call per byte, io_uring submits and completes many operations through shared ring buffers, and vDSO serves gettimeofday and clock_gettime from a page mapped into user space with no transition at all.

user space                  |  kernel space
============================|=================================
read(fd, buf, 4096)         |
  mov rax, 0   ; sys_read   |
  mov rdi, fd               |
  mov rsi, buf              |
  mov rdx, 4096             |
  syscall  =================>  ring 3 to ring 0, switch to kernel stack
                            |  validate buf lies in this address space
                            |  vfs_read -> filesystem -> page cache
                            |  (block here if the data is not resident)
  <================ sysret  |  return value in rax

$ strace -c -p 4102
% time   seconds  usecs/call   calls  syscall
 61.2   4.812301          11  437000  read
 22.0   1.730112          38   45500  epoll_wait
  9.4   0.739004           9   82000  write
# 437k tiny reads: move to readv, a larger buffer, or io_uring

$ strace -T -e trace=read ./app     # -T prints time spent in each call

Answer

Shortest Job First picks the ready process with the smallest next CPU burst and runs it to completion. Shortest Remaining Time First is the preemptive version: whenever a new process arrives, if its burst is shorter than the remaining time of the running process, the running process is preempted immediately. Take P1 arriving at 0 with burst 8, P2 at 1 with 4, P3 at 2 with 9 and P4 at 3 with 5.

Under SRTF, P1 starts at 0. At time 1, P2 arrives with 4 against P1's remaining 7, so P1 is preempted. P2 runs 1 to 5 and finishes.

At time 5 the candidates are P1 with 7 remaining, P3 with 9 and P4 with 5, so P4 runs 5 to 10. Then P1 runs 10 to 17, then P3 runs 17 to 26. Completion times are P1 17, P2 5, P3 26 and P4 10.

Turnaround is completion minus arrival, giving 17, 4, 24 and 7, averaging 13. Waiting is turnaround minus burst, giving 9, 0, 15 and 2, averaging 6.5. SJF is provably optimal for average waiting time because moving a shorter job ahead of a longer one always reduces total waiting, which you can prove by an exchange argument on any two adjacent jobs.

The catch is that it needs the length of the next CPU burst, which is unknowable, so real schedulers estimate it with an exponential moving average, tau of n plus one equals alpha times the last observed burst plus one minus alpha times tau of n, with alpha typically 0.5. SJF also starves long jobs whenever short ones keep arriving.

SRTF (preemptive SJF)
P1 arr=0 burst=8 | P2 arr=1 burst=4 | P3 arr=2 burst=9 | P4 arr=3 burst=5

|P1|   P2   |   P4   |       P1      |         P3        |
0  1        5        10              17                  26

Process Arr Burst Compl  TAT(C-A)  WT(TAT-B)
======= === ===== =====  ========  =========
P1        0     8    17        17          9
P2        1     4     5         4          0
P3        2     9    26        24         15
P4        3     5    10         7          2
                        avg TAT=13.0  avg WT=6.5

Same set, non preemptive SJF -> avg WT = 7.75
Same set, FCFS               -> avg WT = 8.75
SRTF is the floor for average waiting time.

Burst prediction (exponential average, alpha = 0.5)
tau[n+1] = alpha * t[n] + (1 - alpha) * tau[n]
tau0=10, t=6 -> 8 ; then t=4 -> 6 ; then t=6 -> 6

Answer

Priority scheduling assigns each process a number and always dispatches the highest priority runnable process, preemptively or not. Starvation, also called indefinite blocking, happens when higher priority work arrives faster than the low priority job can be scheduled, so a runnable process never reaches the CPU even though it is not blocked on anything. In the case described, a nightly report runs at low priority on a box that also serves API traffic.

Every request spawns higher priority work, and because the arrival rate never drops to zero during the window, the report's turn never comes. It is not deadlocked, it is starved, and the distinction matters because no deadlock detector will ever flag it and the process looks perfectly healthy in ps. The classic anecdote is the IBM 7094 at MIT which, when shut down in 1973, was found to still hold a low priority process submitted in 1967.

The standard fix is aging: gradually increase the priority of any process that has been waiting, so given enough time even the lowest priority job outranks newcomers. For example, raise priority by one level for every 15 seconds spent in the ready queue; a job starting at 127 in a scheme where 0 is highest reaches the top in about 32 minutes and is guaranteed to run. Linux achieves the same intent differently: CFS always picks the task with the smallest accumulated virtual runtime, and a task that has not run accumulates none, so it inevitably becomes the leftmost node in the red black tree and is chosen. Nice values scale how fast virtual runtime grows rather than creating strict priority bands, which is why even a nice 19 task keeps making progress on Linux.

Priority scheduling, lower number = higher priority, non preemptive

P  Burst  Priority
P1     10         3
P2      1         1
P3      2         4
P4      1         5
P5      5         2

| P2 |    P5    |       P1      | P3 | P4 |
0    1          6              16    18   19

avg WT = (6 + 0 + 16 + 18 + 1) / 5 = 8.2
P4, the lowest priority, waits 18 of 19 units. Add a steady stream of
priority 1 arrivals and P4 never runs at all: starvation.

Aging rule: effective_priority = base_priority - (wait_seconds / 15)

$ ps -eo pid,ni,pri,etime,stat,comm | grep report
  PID  NI PRI     ELAPSED STAT COMMAND
 9931  19  20    06:12:44 R    report.sh    # runnable for 6 hours, never ran

$ renice -n 0 -p 9931       # rescue by hand
$ chrt -b 0 ./report.sh     # or start it under SCHED_BATCH

Answer

A multilevel queue partitions the ready queue into several fixed queues, for example system processes, interactive processes, interactive editing, batch and student processes, each with its own scheduling algorithm, and a process is permanently assigned to one queue based on its type. Scheduling between queues is usually fixed priority preemptive, so nothing in the batch queue runs while anything sits in the interactive queue, which starves the lower queues; the alternative is time slicing between queues, giving for instance 80 percent of CPU to foreground and 20 percent to background. The rigidity is the problem: a process cannot move, so a misclassified job stays misclassified forever.

A multilevel feedback queue fixes that by letting processes move between queues based on observed behaviour. A new process enters the highest priority queue with a small quantum, say 8 milliseconds. If it uses the whole quantum it is demoted to a queue with a larger quantum, say 16 milliseconds, and if it uses that too it drops to an FCFS queue at the bottom.

Interactive processes that block for I/O before their quantum expires stay high, so the scheduler infers interactivity from behaviour instead of asking for a hint. Aging promotes long waiting processes back up to prevent starvation. MLFQ is the most general scheme and is parameterised by the number of queues, the per queue algorithm, the promotion and demotion rules, and the entry queue.

Linux CFS abandons queues and fixed quanta entirely. It keeps runnable tasks in a red black tree keyed by virtual runtime, always picks the leftmost node, and charges runtime scaled by the task's weight derived from its nice value. Fairness falls out of that invariant rather than from priority bands, and the time slice is computed dynamically as the scheduling period divided by the number of runnable tasks.

MULTILEVEL FEEDBACK QUEUE

Q0  quantum 8ms    [all new tasks enter here]
      | used the full quantum -> demote
      v
Q1  quantum 16ms
      | used the full quantum -> demote
      v
Q2  FCFS           [CPU bound jobs settle here]
      ^
      | aging: waited too long -> promote back up

Interactive task: blocks on I/O at 3ms, stays in Q0, stays responsive.
Compile job:      burns 8ms, drops to Q1, burns 16ms, drops to Q2.

LINUX CFS
vruntime += delta_exec * (NICE_0_WEIGHT / task_weight)
pick the leftmost node of the red black tree (smallest vruntime)
slice = sched_latency / nr_running, floored by sched_min_granularity

$ chrt -p 1420
pid 1420 current scheduling policy: SCHED_OTHER      # CFS
pid 1420 current scheduling priority: 0

$ grep -E 'vruntime|nr_switches' /proc/1420/sched
se.vruntime                : 913442.118
nr_switches                :  18422

Answer

Under contiguous allocation each process gets one continuous block of physical memory described by a base register and a limit register, and the hardware checks every address against the limit. When a request arrives the allocator must choose a hole from the free list. First fit scans from the start and takes the first hole large enough, which is fastest and in practice performs well.

Best fit takes the smallest adequate hole, which minimises the leftover but produces many tiny unusable slivers and requires scanning the whole list. Worst fit takes the largest hole on the theory that the remainder stays useful, and it performs worst in practice. Simulations give the classic result that first fit and best fit both beat worst fit, and first fit is generally faster.

External fragmentation is free memory that exists but is scattered across non adjacent holes, so a request for 100KB fails even though 300KB is free in three separate pieces. The fifty percent rule states that with first fit, for every N allocated blocks about 0.5N blocks are lost to fragmentation, so roughly a third of memory can become unusable. Internal fragmentation is different: it is space wasted inside an allocated block because the allocator rounds the request up to a fixed unit.

In fixed partition schemes a 5KB process in an 8KB partition wastes 3KB internally, and in paging a process needing 9KB with 4KB pages gets 3 pages and wastes 3KB in the last one. Compaction fixes external fragmentation by sliding allocated blocks together into one large hole, but it is only possible when relocation is dynamic, that is when addresses are translated at run time through base and limit registers, and it is expensive because it copies memory and must stop the affected processes. Paging removes the need for compaction entirely by dropping the contiguity requirement.

Free holes in order: 100K, 500K, 200K, 300K, 600K
Requests in order:   212K, 417K, 112K, 426K

FIRST FIT : 212->500K(288 left), 417->600K(183 left), 112->288K(176 left),
            426-> no hole fits, request FAILS
BEST FIT  : 212->300K(88),  417->500K(83),  112->200K(88),
            426->600K(174), all four satisfied
WORST FIT : 212->600K(388), 417->500K(83),  112->388K(276),
            426-> FAILS

EXTERNAL fragmentation: 88 + 83 + 88 = 259K free, unusable as one block
INTERNAL fragmentation: process needs 9KB, page size 4KB
                        -> 3 pages = 12KB allocated, 3KB wasted inside

Compaction (needs dynamic relocation)
before: [P1][ 60K ][P2][ 40K ][P3][ 30K ]
after : [P1][P2][P3][         130K free         ]

$ cat /proc/buddyinfo
Node 0, zone Normal  4021  1102   318    47    2   0  0  0  0  0  0
# counts of free blocks per order. Everything in low orders and nothing
# in high orders is external fragmentation in the buddy allocator.

Answer

Paging splits the virtual address space into fixed size pages and physical memory into frames of the same size, and a per process page table maps page numbers to frame numbers. With a 32 bit address space and 4KB pages, the offset needs log base 2 of 4096, which is 12 bits, leaving 20 bits for the page number, so there are 2 to the 20, about one million, pages per process. The MMU splits the virtual address, indexes the page table with the page number to get the frame number, and concatenates the frame number with the untouched offset to form the physical address.

Note that it is concatenation, not addition, because the offset is a position within the frame. Each page table entry holds the frame number plus control bits: valid or invalid, read write, user or supervisor, accessed or referenced, dirty or modified, and cache disable. The problem is that the page table itself lives in memory, so a naive translation needs two memory accesses per data access, one to read the entry and one to read the data, halving performance.

The Translation Lookaside Buffer is a small fully associative cache, typically 64 to 1536 entries, holding recent page to frame mappings. Effective access time with a TLB access of 20 nanoseconds, memory of 100 nanoseconds and a hit ratio of 98 percent is 0.98 times 120 plus 0.02 times 220, which is 117.6 plus 4.4, or 122 nanoseconds, a 22 percent overhead instead of 100 percent. Two follow ups are common: the TLB must be flushed or tagged on a context switch since mappings are per process, which is what address space identifiers or PCIDs solve, and huge pages of 2MB cover far more memory per entry so a large working set stops thrashing the TLB.

32 bit VA, 4KB pages

 31                    12 11            0
+========================+===============+
|   page number (20 b)   |  offset (12 b)|
+========================+===============+
           |                     |
           v                     |
     [ page table ] => frame no  |
           |                     |
           +==========> physical address = frame | offset

VA 0x00003ABC -> page 0x00003, offset 0xABC
if PTE[3] holds frame 0x00051 then PA = 0x00051ABC

Flat page table size: 2^20 entries * 4 bytes = 4 MB PER PROCESS

Effective access time (TLB 20ns, memory 100ns, hit ratio 98%)
EAT = 0.98 * (20 + 100) + 0.02 * (20 + 100 + 100)
    = 117.6 + 4.4 = 122 ns      (22% overhead, not 100%)

$ getconf PAGESIZE
4096
$ grep -E 'AnonHugePages|Hugepagesize' /proc/meminfo
AnonHugePages:   1050624 kB
Hugepagesize:       2048 kB

Answer

A flat page table for a 32 bit space with 4KB pages needs one million entries at 4 bytes each, so 4MB per process, and it must be physically contiguous. With 500 processes that is 2GB of page tables for address spaces that are almost entirely unused. Multilevel paging solves it by paging the page table itself.

On 32 bit x86 the 20 bit page number splits into a 10 bit outer index and a 10 bit inner index, so there is one outer directory of 1024 entries, each pointing to an inner table of 1024 entries. A process that touches only a few megabytes needs the directory plus two or three inner tables, tens of kilobytes rather than 4MB, because entries for untouched regions are simply marked not present and no inner table is allocated at all. The cost is one extra memory reference per level on a TLB miss.

On x86 64 with 48 bit addresses there are four levels, 9 plus 9 plus 9 plus 9 plus 12, so a TLB miss costs four memory accesses, and five level paging exists for 57 bit spaces. That is exactly why the TLB hit ratio matters so much on modern hardware and why page walkers cache intermediate levels. Inverted page tables take the opposite approach: keep one global table with one entry per physical frame rather than one per virtual page, so the size scales with physical memory, not with the number of processes.

Each entry records which process and which virtual page currently occupies that frame. The cost is that translation now requires searching the table for a matching process and page pair rather than indexing it, which is mitigated with a hash table plus a chain, and shared memory becomes awkward because a frame can hold only one process and page entry at a time. PowerPC and IA 64 used inverted tables; x86 uses hierarchical.

TWO LEVEL (x86, 32 bit)
 31      22 21      12 11        0
+==========+==========+===========+
| dir (10) | table(10)| offset(12)|
+==========+==========+===========+
     |          |
     v          v
 [page dir] => [page table] => frame

Flat    : 2^20 entries * 4B       = 4 MB per process, contiguous
Two level: 1 dir (4KB) + N tables = about 12 KB for a small process

FOUR LEVEL (x86 64, 48 bit VA)
| PML4 (9) | PDPT (9) | PD (9) | PT (9) | offset (12) |
TLB miss now costs 4 memory accesses to walk the hierarchy

INVERTED PAGE TABLE
one entry per PHYSICAL frame: [ pid | virtual page | control bits ]
size scales with RAM, not with process count
translation = hash(pid, page) then walk the collision chain
shared memory is hard: one frame maps to one (pid, page) entry

$ grep VmPTE /proc/1420/status
VmPTE:       412 kB     # page table pages this process actually uses

Answer

Paging divides memory into fixed size blocks decided by the hardware, invisible to the programmer, mapped through a page table indexed by page number. It eliminates external fragmentation completely because any free frame can hold any page, but it suffers internal fragmentation in the last page and it has no relationship to the logical structure of the program, so you cannot set permissions on a logical unit like a stack or a code module without aligning it to page boundaries. Segmentation divides memory into variable length segments that match the programmer's view, code, data, stack, heap and each library, and an address is a segment number plus an offset checked against that segment's limit.

It supports protection and sharing naturally: mark the code segment read execute and share it between every process running the same binary, and the limit register gives a precise bounds check rather than a page granular one. Its weakness is the mirror image, variable sizes mean external fragmentation and the eventual need for compaction. Segmentation with paging combines them: the logical address is a segment number plus offset, the segment table entry points at a page table, and that segment's pages are then scattered across frames.

You keep the logical structure and protection of segments while paging removes external fragmentation. MULTICS and the 80386 implemented exactly this. On x86 64 segmentation is essentially retired: in long mode the bases of CS, DS, ES and SS are forced to zero and the limits are ignored, so the flat model wins, and only FS and GS keep usable bases, which the kernel and thread local storage exploit. So the honest answer is that modern 64 bit systems use paging with vestigial segmentation, and the protection role segments used to play now lives in the page table entry bits and the no execute bit.

PAGING                        SEGMENTATION
======                        ============
fixed size blocks             variable size, logical units
invisible to the programmer   visible: code, data, stack, libs
internal fragmentation        external fragmentation
no external fragmentation     needs compaction
page table (page -> frame)    segment table (base + limit)
page granular protection      exact logical protection and sharing

SEGMENTATION WITH PAGING
| segment no | page no | offset |
       |          |
       v          v
 [segment table] -> [page table of that segment] -> frame

$ cat /proc/self/maps
55d1f3a00000-55d1f3a02000 r-xp 00000000 08:01 1310721  /usr/bin/cat
55d1f3c01000-55d1f3c02000 rw-p 00001000 08:01 1310721  /usr/bin/cat
55d1f5a21000-55d1f5a42000 rw-p 00000000 00:00 0        [heap]
7ffd8c2a1000-7ffd8c2c2000 rw-p 00000000 00:00 0        [stack]
# Each line is a VMA. Linux keeps segment like regions in software and
# enforces them through page table permission bits, not segment registers.

Answer

The instruction issues a virtual address. The MMU splits it, misses in the TLB, walks the page table and finds the valid bit clear, so the hardware raises a page fault, a trap into the kernel, and records the faulting address, on x86 in CR2, along with an error code describing whether it was a read or a write and whether it came from user or kernel mode. The kernel's handler first decides whether the fault is legal by looking up the address in the process's memory region list, the VMAs.

If the address is not in any region, or the access violates the region's permissions, for example a write to a read only mapping, the kernel delivers SIGSEGV and you get a segmentation fault. If it is legal, the kernel classifies it. A minor fault means the page is already in physical memory and only the mapping is missing, for example the content sits in the page cache from another process, or it is a copy on write fault where the frame exists but must be duplicated, or the mapping was simply never established after an mmap.

A minor fault needs no disk I/O and is fast. A major fault means the content must come from a backing store, so the kernel finds a free frame, evicting one via the page replacement algorithm and writing it out first if it is dirty, then schedules the read from the swap area or the file. The process is put in the blocked state and another process runs.

When the disk interrupt signals completion the kernel updates the page table entry with the new frame and sets the valid bit, updates the TLB, marks the process ready, and eventually the scheduler dispatches it and restarts the faulting instruction, which now succeeds. Restarting the instruction rather than resuming after it is the part candidates most often miss.

 1. CPU issues VA, TLB miss, page walk finds valid bit = 0
 2. hardware traps: page fault, faulting VA in CR2, error code pushed
 3. kernel checks the VMA list for this address
       not found, or permission violation -> SIGSEGV (segfault)
 4. legal fault, classify it:
       MINOR: frame already in RAM (page cache hit, COW, first touch)
              -> just fix the PTE, no disk I/O
       MAJOR: content lives on disk or in swap
 5. find a free frame, else run page replacement, write back if dirty
 6. issue the disk read, block the process, scheduler runs someone else
 7. disk interrupt: I/O complete
 8. update the PTE with the frame number, set valid, update TLB
 9. mark the process READY
10. scheduler dispatches it and RESTARTS the faulting instruction

$ ps -o min_flt,maj_flt,cmd -p 4102
 MINFL  MAJFL CMD
842119    317 /usr/bin/java -jar api.jar
# huge minor with tiny major = healthy. Climbing MAJFL = swapping.

$ /usr/bin/time -v ./app 2>&1 | grep -i 'page faults'
  Major (requiring I/O) page faults: 12
  Minor (reclaiming a frame) page faults: 91204

Answer

With three frames on that reference string, FIFO produces 15 faults, optimal produces 9 and LRU produces 12. FIFO evicts the page that has been resident longest regardless of use, which is trivial to implement as a queue but throws out hot pages simply because they arrived early. Optimal, also called OPT or Belady's algorithm, evicts the page that will not be used for the longest time in the future; it gives the provable lower bound on faults but is unimplementable because it requires knowledge of the future, so it exists only as a benchmark to measure real algorithms against.

LRU evicts the page unused for the longest time, using the recent past as a proxy for the near future, and it lands between the two. LRU is implementable but expensive: an exact implementation needs either a counter written into the page table entry on every single memory reference, or a doubly linked list updated on every reference, and no mainstream CPU offers hardware for either, which is why real kernels use approximations. Belady's anomaly is the counterintuitive result that with FIFO, adding more frames can increase the number of page faults.

The standard demonstration uses the string 1 2 3 4 1 2 5 1 2 3 4 5: with three frames FIFO takes 9 faults, with four frames it takes 10. The reason is that FIFO is not a stack algorithm, meaning the set of pages resident with n frames is not guaranteed to be a subset of the set resident with n plus 1 frames, so a larger memory can evict a page that a smaller memory would have kept. LRU and OPT are stack algorithms and provably never exhibit the anomaly, which is the strongest single argument for preferring LRU when the interviewer asks why anyone bothers.

String: 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1   frames = 3

FIFO, frame contents after each reference (F = fault)
7:[7]F  0:[7,0]F  1:[7,0,1]F  2:[2,0,1]F  0:hit  3:[2,3,1]F  0:[2,3,0]F
4:[4,3,0]F  2:[4,2,0]F  3:[4,2,3]F  0:[0,2,3]F  3:hit  2:hit  1:[0,1,3]F
2:[0,1,2]F  0:hit  1:hit  7:[7,1,2]F  0:[7,0,2]F  1:[7,0,1]F
TOTAL FIFO = 15 faults

OPTIMAL = 9 faults        LRU = 12 faults

BELADY'S ANOMALY, string 1 2 3 4 1 2 5 1 2 3 4 5, FIFO

3 FRAMES                      4 FRAMES
1 F [1]                       1 F [1]
2 F [1,2]                     2 F [1,2]
3 F [1,2,3]                   3 F [1,2,3]
4 F [4,2,3]  evict 1          4 F [1,2,3,4]
1 F [4,1,3]  evict 2          1 hit
2 F [4,1,2]  evict 3          2 hit
5 F [5,1,2]  evict 4          5 F [5,2,3,4] evict 1
1 hit                         1 F [5,1,3,4] evict 2
2 hit                         2 F [5,1,2,4] evict 3
3 F [5,3,2]  evict 1          3 F [5,1,2,3] evict 4
4 F [5,3,4]  evict 2          4 F [4,1,2,3] evict 5
5 hit                         5 F [4,5,2,3] evict 1
TOTAL = 9 faults              TOTAL = 10 faults   <- more frames, more faults

Answer

Thrashing is the state where a system spends more time servicing page faults than executing useful instructions. It has a characteristic feedback loop: the degree of multiprogramming rises, each process gets fewer frames than its working set needs, so page fault rates climb, processes block on disk, CPU utilisation appears to drop, and a naive scheduler responds by admitting even more processes, which makes it worse. The working set model explains why.

A process's working set is the set of pages it has referenced in the last delta references, and it approximates the pages it needs resident right now. If the sum of all working sets exceeds available frames, thrashing is guaranteed. The remedy is to reduce the degree of multiprogramming, that is suspend or kill processes, or add memory, and a working set based scheduler will refuse to admit a new process unless its working set fits.

Distinguishing thrashing from a CPU bottleneck at the terminal is the part interviewers actually want. In top, a CPU bottleneck shows high user time with low system time and near zero iowait. Thrashing shows the opposite: low user time, high system and iowait, and load average far above core count.

The decisive evidence is vmstat 1: the si and so columns, swap in and swap out pages per second, are near zero on a healthy box and in the thousands when thrashing, and the b column shows processes blocked. free -h shows swap used climbing while available memory sits near zero. Per process, the maj_flt counter in ps climbs continuously. The practical fix in production is to cut concurrency, thread pool size or worker count, before adding RAM, because that is what shrinks the summed working set.

$ vmstat 1
procs        memory         swap        io      system      cpu
 r  b   free   buff  cache   si   so   bi   bo   in     cs  us sy id wa
 2  0 891200  40100 610224    0    0    0    8  520   1100  12  4 84  0
 1  9  10240   1020   8804  482  926 9820 2140 9800  42000   9 61  2 28

Healthy row  : si=0 so=0, wa=0, us high
Thrashing row: si and so in the hundreds, b=9 blocked, wa=28, sy=61, us=9

$ free -h
              total   used   free  shared  buff/cache  available
Mem:            15G    14G   190M     12M        800M       210M
Swap:          4.0G   3.7G   300M

$ ps -eo pid,maj_flt,rss,comm | sort -k2 -rn | head -2
 4102  418902 8921044 java
 4180  201338 3120884 python
# columns: pid, major faults, RSS. Major faults climbing = swapping.

Working set model
WS(t, delta) = pages referenced in the last delta references
if SUM of WS over all processes > available frames -> thrashing
fix: lower the degree of multiprogramming, or add frames

Answer

Swap is disk space used as an overflow for anonymous memory, that is heap and stack pages that have no file backing. When memory pressure rises, kswapd reclaims: it drops clean page cache pages for free, writes dirty file pages back, and pushes anonymous pages out to swap. The swappiness tunable, 0 to 200 with a default of 60, biases that choice: a low value tells the kernel to prefer reclaiming page cache and to avoid swapping anonymous pages, which is what you want for a latency sensitive service, while a high value makes it more willing to swap.

Setting swappiness to 0 does not disable swap, it only makes it a last resort. When reclaim cannot keep up and an allocation still cannot be satisfied, the kernel invokes the out of memory killer. It scores every process with oom_score, driven mainly by resident memory as a fraction of available memory and adjustable per process through oom_score_adj, then kills the highest scorer and logs Out of memory: Killed process to dmesg.

Because the score is dominated by RSS, the victim is usually your largest process, which is normally the very database or JVM you least wanted killed. The container case is the one that trips people up. A cgroup has its own memory limit, and when a process inside it exceeds that limit the kernel runs a cgroup scoped OOM kill, which considers only the processes in that cgroup, regardless of how much memory the host has free.

So a JVM with a 4GB heap in a container limited to 2GB dies on a 64GB host. The JVM makes it worse historically by reading host memory when sizing its default heap, which is why container aware heap flags exist. Check memory.max and memory.events under the cgroup path to confirm.

$ cat /proc/sys/vm/swappiness
60
$ sysctl vm.swappiness=10        # prefer dropping page cache over swapping

$ dmesg -T | grep -i 'out of memory'
[Sun Aug 17 03:14:22 2026] Out of memory: Killed process 4102 (java)
  total-vm:9120044kB, anon-rss:8721004kB, file-rss:0kB, oom_score_adj:0

$ cat /proc/4102/oom_score        # higher = killed first
742
$ echo -500 > /proc/4102/oom_score_adj   # protect a critical process

/* Container case: cgroup v2 limits, not host memory */
$ cat /sys/fs/cgroup/memory.max
2147483648                       # 2 GB, regardless of a 64 GB host
$ cat /sys/fs/cgroup/memory.events
low 0
high 1204
max 88
oom 3
oom_kill 3                       # three cgroup scoped OOM kills

$ free -h                        # host looks fine, which confuses people
              total   used   free  available
Mem:            62G    18G    39G        43G

Answer

The bounded buffer needs three synchronisation objects. A counting semaphore named empty initialised to N counts free slots, a counting semaphore named full initialised to 0 counts filled slots, and a mutex or binary semaphore protects the buffer's indices and the array itself. The producer waits on empty, so it blocks when the buffer is full, acquires the mutex, inserts the item, releases the mutex, then signals full.

The consumer is the mirror: wait on full so it blocks when empty, acquire the mutex, remove, release the mutex, signal empty. Note that the counting semaphores do the flow control and the mutex does only mutual exclusion, and that separation is the whole design. The critical detail interviewers probe is the ordering of the two waits.

If the producer acquires the mutex first and then waits on empty, it will block holding the mutex when the buffer is full. The consumer then tries to acquire that same mutex to remove an item and blocks forever, so nothing is ever consumed, no slot is ever freed and the producer never wakes. That is a textbook deadlock caused purely by inverting two lines, and it satisfies all four Coffman conditions.

The rule to state out loud is that you always acquire the resource counting semaphore before the mutex, and release in reverse order. Two more points worth adding: the signal calls can safely be moved outside the mutex, which shortens the critical section and reduces contention; and in real systems you rarely hand roll this, you use a blocking queue, a Go channel or an ArrayBlockingQueue, all of which implement exactly this pattern internally with condition variables rather than raw semaphores.

semaphore empty = N;    /* free slots  */
semaphore full  = 0;    /* filled slots */
mutex     m;
item      buffer[N];
int       in = 0, out = 0;

PRODUCER                          CONSUMER
========                          ========
while (true) {                    while (true) {
    item = produce();                 wait(full);      /* block if empty */
    wait(empty);   /* block if full */ lock(m);
    lock(m);                           item = buffer[out];
    buffer[in] = item;                 out = (out + 1) % N;
    in = (in + 1) % N;                 unlock(m);
    unlock(m);                         signal(empty);
    signal(full);                      consume(item);
}                                 }

/* THE BUG: swap the first two lines of the producer */
lock(m);
wait(empty);        /* buffer full -> blocks WHILE HOLDING THE MUTEX */
/* consumer now blocks on lock(m) forever. Total deadlock. */

/* Rule: acquire the counting semaphore BEFORE the mutex,
   release in the reverse order. */

/* Real code just uses the library version */
BlockingQueue<Item> q = new ArrayBlockingQueue<>(N);
q.put(item);   /* blocks when full  */
q.take();      /* blocks when empty */

Answer

The readers writers problem allows any number of concurrent readers but requires a writer to have exclusive access. The first readers writers solution uses a mutex protecting a read_count integer plus a semaphore called wrt used for writer exclusion. A reader locks the count mutex, increments read_count, and if it is the first reader it waits on wrt to lock out writers, then unlocks the count mutex and reads.

On exit it decrements and the last reader out signals wrt. A writer simply waits on wrt, writes, and signals it. This is reader preferring, and that is exactly where the starvation comes from: while at least one reader is inside, read_count never reaches zero, so wrt is never signalled.

If readers keep arriving before the last one leaves, the count never drops and a waiting writer waits forever. In a read heavy service, say a config cache read thousands of times a second, this is not a theoretical risk, it is the normal outcome, and it shows up as a write that never lands. The second readers writers solution reverses the preference: once a writer is waiting, no new reader may enter, which starves readers instead.

The practical answer is a fair or write preferring lock that queues requests, so readers already in flight finish, waiting writers get the next turn, and readers that arrive after the writer queue behind it. In real code this is pthread_rwlock, which on Linux takes a writer preference attribute, or Java's ReentrantReadWriteLock constructed with the fair flag. Worth adding: a read write lock only pays off when reads genuinely dominate and critical sections are long, because the bookkeeping is heavier than a plain mutex, and for short sections a plain mutex or a copy on write structure is usually faster.

semaphore wrt = 1;        /* writer exclusion */
mutex     cnt_m;
int       read_count = 0;

READER                              WRITER
======                              ======
lock(cnt_m);                        wait(wrt);
read_count += 1;                    /* write */
if (read_count == 1) wait(wrt);     signal(wrt);
unlock(cnt_m);
/* read */
lock(cnt_m);
read_count -= 1;
if (read_count == 0) signal(wrt);
unlock(cnt_m);

/* STARVATION: readers arrive faster than they leave,
   read_count never returns to 0, signal(wrt) never runs,
   the waiting writer blocks indefinitely. */

/* Writer preferring in practice */
pthread_rwlockattr_t attr;
pthread_rwlockattr_init(&attr);
pthread_rwlockattr_setkind_np(&attr,
    PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP);
pthread_rwlock_t lock;
pthread_rwlock_init(&lock, &attr);

pthread_rwlock_rdlock(&lock);  /* many concurrent */
pthread_rwlock_wrlock(&lock);  /* exclusive, and now gets priority */

/* Java */
new ReentrantReadWriteLock(true);   /* fair ordering policy */

Answer

Five philosophers sit around a table with five forks, one between each pair. To eat, a philosopher needs both the fork on their left and the fork on their right. The naive solution has each philosopher wait on the left fork then the right fork.

If all five pick up their left fork at the same instant, every fork is held, every philosopher is waiting for their right fork, and the system is deadlocked. All four Coffman conditions are visible: a fork can be held by one philosopher at a time, mutual exclusion; each holds one fork while waiting for another, hold and wait; nobody can snatch a fork, no preemption; and philosopher 0 waits on 1 who waits on 2 and so on back to 0, circular wait. The first correct solution is resource ordering: number the forks 0 to 4 and require every philosopher to pick up the lower numbered fork first.

Philosopher 4, who would otherwise take fork 4 then fork 0, now takes fork 0 first. That breaks circular wait, because a cycle would require someone acquiring in descending order, and it is the technique you actually use in production for lock ordering. The second solution is an arbitrator or a semaphore initialised to 4, admitting at most four philosophers to the table at once, which guarantees at least one can obtain both forks; that breaks hold and wait at the system level by bounding contention.

A third common answer is asymmetry, odd philosophers take left first and even take right first, which also breaks the cycle. A fourth is atomic acquisition of both forks under a global mutex or with pthread_mutex_trylock plus back off, which breaks hold and wait directly, though naive back off can livelock without randomised delays. Always name which condition your fix breaks.

/* DEADLOCKS: everyone grabs left, then right */
void philosopher(int i) {
    while (1) {
        wait(fork[i]);              /* left  */
        wait(fork[(i + 1) % 5]);    /* right */
        eat();
        signal(fork[(i + 1) % 5]);
        signal(fork[i]);
        think();
    }
}

/* FIX 1: resource ordering, breaks CIRCULAR WAIT */
void philosopher(int i) {
    int a = i, b = (i + 1) % 5;
    int lo = (a < b) ? a : b;
    int hi = (a < b) ? b : a;
    wait(fork[lo]);            /* always lower numbered fork first */
    wait(fork[hi]);
    eat();
    signal(fork[hi]);
    signal(fork[lo]);
}

/* FIX 2: arbitrator, breaks HOLD AND WAIT by bounding contention */
semaphore seats = 4;           /* at most 4 of 5 at the table */
wait(seats);
  wait(fork[i]); wait(fork[(i + 1) % 5]);
  eat();
  signal(fork[(i + 1) % 5]); signal(fork[i]);
signal(seats);

/* FIX 3: asymmetry */
if (i % 2 == 0) { wait(right); wait(left); }
else            { wait(left);  wait(right); }

Answer

A monitor is a high level synchronisation construct that bundles shared data with the procedures that operate on it, and guarantees that only one thread executes inside the monitor at a time. Mutual exclusion is implicit rather than something you code, which is why monitors are much harder to misuse than raw semaphores; Java's synchronized methods and C sharp's lock are monitors in practice. Because the monitor lock alone cannot express waiting for a condition, monitors add condition variables with two operations, wait which atomically releases the monitor lock and suspends the calling thread, and signal or notify which wakes one waiting thread.

The atomicity of release and suspend is the key property, because if they were separate a signal could land in the gap and be lost forever. The reason you must wait in a while loop rather than an if has three independent causes and a good answer names all three. First, spurious wakeups: POSIX explicitly permits pthread_cond_wait to return without any corresponding signal, and Java documents the same for Object.wait, so a woken thread has no guarantee its condition became true.

Second, stolen wakeups under Mesa semantics, which is what every real system uses: signal only makes the waiter runnable, it does not transfer the lock, so between the signal and the waiter actually reacquiring the lock a third thread can enter and consume the item. Third, notifyAll or broadcast wakes every waiter, and at most one can proceed. In all three cases the woken thread must recheck the predicate, which is exactly what while gives you. Under the theoretical Hoare semantics, where the signaller immediately transfers control and the lock, an if would be safe, and that contrast is the follow up interviewers reach for.

/* Monitor with a condition variable, bounded buffer */
pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t  not_empty = PTHREAD_COND_INITIALIZER;
pthread_cond_t  not_full  = PTHREAD_COND_INITIALIZER;
int count = 0;

void put(item x) {
    pthread_mutex_lock(&m);
    while (count == N)                    /* WHILE, never if */
        pthread_cond_wait(&not_full, &m); /* atomically unlock + sleep */
    buffer[in] = x; in = (in + 1) % N; count += 1;
    pthread_cond_signal(&not_empty);
    pthread_mutex_unlock(&m);
}

item get(void) {
    pthread_mutex_lock(&m);
    while (count == 0)
        pthread_cond_wait(&not_empty, &m);
    item x = buffer[out]; out = (out + 1) % N; count -= 1;
    pthread_cond_signal(&not_full);
    pthread_mutex_unlock(&m);
    return x;
}

/* Three reasons the while loop is mandatory
   1. spurious wakeups are permitted by POSIX and by Java
   2. Mesa semantics: signal does not transfer the lock, another
      thread can consume the item before the waiter reacquires it
   3. broadcast / notifyAll wakes everyone, only one can proceed */

Answer

Peterson's solution is a software only mutual exclusion algorithm for two processes using two shared variables, a boolean array flag of size two and an integer turn. To enter, process i sets flag[i] to true announcing intent, sets turn to j politely yielding, then busy waits while flag[j] is true and turn equals j. To exit, it sets flag[i] to false.

The proof that it satisfies all three requirements is elegant: mutual exclusion holds because turn can hold only one value, so at most one of the two loop conditions can be false at a time; progress holds because a process not interested has flag false, so it cannot block the other; and bounded waiting holds because after exiting, a process must set turn to the other, so the other enters next and no process waits more than one turn. It fails on real hardware for a reason that has nothing to do with the logic. The proof assumes sequential consistency, that is that every processor sees memory operations in program order.

Real CPUs and real compilers both reorder. The x86 store buffer allows a store to flag[i] to sit unflushed while the subsequent load of flag[j] executes, so both processes can read a stale false and both enter the critical section. Compilers make it worse: without a volatile or atomic qualifier the compiler may hoist the loads of flag[j] and turn out of the loop entirely, producing an infinite loop or an unsynchronised entry.

The fix is explicit memory barriers, a store load fence between the write of turn and the read of flag[j], or in modern terms declaring the variables as atomics with sequentially consistent ordering. That is why nobody ships Peterson's algorithm; hardware atomics like compare and swap are both correct and faster. The educational value is precisely that it shows mutual exclusion is achievable without special instructions, and that memory models are not optional.

/* Peterson, process i, other process j */
bool flag[2] = { false, false };
int  turn;

/* entry */
flag[i] = true;                  /* I want in            */
turn = j;                        /* but you go first     */
while (flag[j] && turn == j) ;   /* spin                 */

/* critical section */

/* exit */
flag[i] = false;

/* WHY IT BREAKS ON REAL HARDWARE
   store buffer allows this reordering:
     P0: store flag[0]=true  (sits in store buffer)
     P0: load  flag[1]       -> reads stale false
     P1: store flag[1]=true  (sits in store buffer)
     P1: load  flag[0]       -> reads stale false
   BOTH enter the critical section. */

/* Correct version, C11 atomics */
#include <stdatomic.h>
atomic_bool flag[2];
atomic_int  turn;

atomic_store(&flag[i], true);
atomic_store(&turn, j);
atomic_thread_fence(memory_order_seq_cst);   /* store load barrier */
while (atomic_load(&flag[j]) && atomic_load(&turn) == j) ;

Answer

Software algorithms like Peterson's are fragile and do not scale past two processes, so hardware provides atomic read modify write instructions. Test and set atomically reads a memory word and sets it to true, returning the old value. Building a lock is then trivial: spin while test and set returns true, meaning someone else held it, and release by storing false.

Test and set guarantees mutual exclusion and progress but not bounded waiting, since an unlucky thread can lose every race indefinitely; the textbook fix adds a waiting array and passes the lock around in a circle. Compare and swap is strictly more powerful. It takes an address, an expected value and a new value, and atomically writes the new value only if the current value equals the expected one, returning either success or the value it actually found.

That conditional property is what enables lock free data structures: read the current head of a stack, compute the new head, and CAS; if another thread intervened the CAS fails and you retry from the fresh value. On x86 these compile to the lock prefixed instructions xchg and cmpxchg. The cost interviewers want named is the cache coherence traffic.

A lock prefixed instruction must obtain the cache line in exclusive state, so with sixteen cores hammering one counter the line ping pongs between cores and throughput collapses far below a single thread's, and under heavy contention a CAS retry loop can spin many times, each iteration paying that coherence cost. Two related traps: the ABA problem, where a value changes from A to B and back to A so the CAS succeeds although the structure changed underneath, solved with tagged pointers or hazard pointers, and false sharing, where two unrelated variables in one cache line cause the same ping pong, solved with padding to 64 bytes.

/* TEST AND SET, atomic in hardware */
bool test_and_set(bool *target) {
    bool old = *target;
    *target = true;
    return old;
}

bool lock = false;
while (test_and_set(&lock)) ;   /* spin */
/* critical section */
lock = false;

/* COMPARE AND SWAP */
int compare_and_swap(int *v, int expected, int new_val) {
    int old = *v;
    if (old == expected) *v = new_val;
    return old;                 /* caller checks old == expected */
}

/* Lock free stack push with CAS retry */
void push(Node *n) {
    Node *old_head;
    do {
        old_head = head;
        n->next  = old_head;
    } while (!atomic_compare_exchange_weak(&head, &old_head, n));
}

/* C11 portable forms */
atomic_flag_test_and_set(&f);
atomic_compare_exchange_strong(&ptr, &expected, desired);

/* Contention cost: the lock prefix needs the cache line EXCLUSIVE
   16 cores incrementing one shared counter -> the line ping pongs,
   throughput falls BELOW single threaded. Fix: per core counters,
   or pad hot variables to a 64 byte cache line. */
struct counter { long v; char pad[56]; };   /* avoid false sharing */

Answer

An interrupt is asynchronous and comes from hardware: a timer tick, a key press, a network card announcing a packet, a disk controller announcing completion. It is unrelated to whatever instruction the CPU was executing, it arrives between instructions, and the CPU vectors through the interrupt descriptor table to a handler, saves state, services it and returns. A trap, also called an exception or a software interrupt, is synchronous and is caused by the currently executing instruction: division by zero, an invalid opcode, a page fault, a breakpoint, or the deliberate syscall instruction.

The distinguishing property is reproducibility, since re executing the same instruction in the same state produces the same trap, whereas an interrupt is not reproducible. A signal is a different layer entirely: it is a kernel to process notification, effectively a software interrupt delivered to user code, and it is how the kernel tells a process something happened to it. The layering is the answer interviewers want: hardware raises interrupts and traps, the kernel handles them, and where a user process needs to know, the kernel converts the event into a signal.

A bad memory access is a page fault trap in hardware that the kernel turns into SIGSEGV; a divide by zero trap becomes SIGFPE; the terminal interrupt key raises a hardware interrupt that becomes SIGINT. DMA sits in the middle of all this. Without it, programmed I/O forces the CPU to copy every word from the device register to memory, burning the CPU on pure data movement.

With DMA the CPU programs the DMA controller with a source, destination and length, then goes and runs something else while the controller moves the data directly into memory over the bus, and only when the whole transfer is complete does the controller raise one interrupt. So DMA converts thousands of CPU mediated word copies into one setup plus one interrupt, which is why high throughput disk and network I/O is feasible at all.

INTERRUPT   asynchronous, from hardware, unrelated to current instruction
            timer tick, NIC packet, disk DMA completion
            $ cat /proc/interrupts
              CPU0    CPU1
   0:        18     0   IO-APIC   2-edge      timer
  24:   4210332  9821   PCI-MSI   nvme0q1

TRAP        synchronous, caused by the current instruction, reproducible
            divide by zero, page fault, invalid opcode, syscall

SIGNAL      kernel to process notification, a software interrupt
            SIGSEGV from a bad access trap, SIGFPE from divide by zero,
            SIGINT from the terminal, SIGKILL and SIGSTOP uncatchable

#include <signal.h>
void on_term(int sig) { cleanup(); _exit(0); }
signal(SIGTERM, on_term);        /* SIGKILL can never be caught */

DISK READ WITH DMA
1. driver programs the DMA controller: source, dest, length
2. CPU is FREE, scheduler runs another process
3. controller moves data device -> memory directly over the bus
4. transfer complete, controller raises ONE interrupt
5. ISR marks the page valid and wakes the blocked process

Without DMA (programmed I/O) the CPU copies every word itself.

Answer

Banker's algorithm is deadlock avoidance: every process declares its maximum demand up front, and before granting any request the system checks whether the resulting state is still safe. Safe means there exists at least one ordering of the processes such that each can obtain its remaining need from the currently available resources plus everything released by the processes ahead of it. Note that unsafe is not the same as deadlocked; an unsafe state merely means the system can no longer guarantee that deadlock is avoidable, so the request is refused and the process waits.

The method is mechanical. Compute Need as Max minus Allocation. Set Work equal to Available and mark every process unfinished.

Scan for any unfinished process whose Need is component wise less than or equal to Work. Pretend it runs to completion: add its Allocation to Work and mark it finished. Repeat.

If every process finishes, the state is safe and the order in which you finished them is the safe sequence. With Available at 3 3 2 and the standard matrix, only P1 has Need 1 2 2 that fits, and after it releases Work becomes 5 3 2, then P3 with Need 0 1 1 fits and Work becomes 7 4 3, then P4, then P0, then P2, giving the safe sequence P1, P3, P4, P0, P2. For the request check, say P1 requests 1 0 2.

First verify the request does not exceed Need and does not exceed Available, then tentatively grant it, updating Available to 2 3 0, Allocation for P1 to 3 0 2 and Need to 0 2 0, and re run the safety check. It still yields a safe sequence, so the request is granted. The reasons Banker's is not used in real systems are worth naming: processes rarely know their maximum demand in advance, the resource set is not fixed, and the check is order n squared times m on every single request.

5 processes, 3 resource types (A B C), Total = 10 5 7, Available = 3 3 2

        Allocation      Max          Need = Max - Alloc
        A  B  C       A  B  C          A  B  C
P0      0  1  0       7  5  3          7  4  3
P1      2  0  0       3  2  2          1  2  2
P2      3  0  2       9  0  2          6  0  0
P3      2  1  1       2  2  2          0  1  1
P4      0  0  2       4  3  3          4  3  1

SAFETY CHECK, Work = Available = 3 3 2
P1 Need 1 2 2 <= 3 3 2   run it, Work = 3 3 2 + 2 0 0 = 5 3 2
P3 Need 0 1 1 <= 5 3 2   run it, Work = 5 3 2 + 2 1 1 = 7 4 3
P4 Need 4 3 1 <= 7 4 3   run it, Work = 7 4 3 + 0 0 2 = 7 4 5
P0 Need 7 4 3 <= 7 4 5   run it, Work = 7 4 5 + 0 1 0 = 7 5 5
P2 Need 6 0 0 <= 7 5 5   run it, Work = 7 5 5 + 3 0 2 = 10 5 7

SAFE SEQUENCE = < P1, P3, P4, P0, P2 >

REQUEST: P1 asks for 1 0 2
  1 0 2 <= Need(P1) 1 2 2      ok
  1 0 2 <= Available 3 3 2     ok
  tentatively grant:
    Available 2 3 0, Alloc(P1) 3 0 2, Need(P1) 0 2 0
  re run safety -> < P1, P3, P4, P0, P2 > still works
  GRANT the request.

Answer

Prevention structurally negates one of the four Coffman conditions so deadlock is impossible. You can attack mutual exclusion by making resources sharable, which works only for read only data. You can attack hold and wait by requiring a process to request everything at once before it starts, which wastes resources held but unused and can starve processes that need popular resources.

You can attack no preemption by forcing a process that requests something unavailable to release everything it holds, which suits CPU registers and memory but not printers or half written files. You can attack circular wait by imposing a total ordering on resources and requiring acquisition in increasing order, which is the only one commonly used in real software because it costs nothing at run time. Avoidance is Banker's algorithm: allow all four conditions but refuse any request that would leave the system in an unsafe state, which requires prior knowledge of maximum demand and a costly check on every request.

Detection and recovery lets deadlock happen, then finds it by searching a wait for graph for cycles, or by running a Banker's style detection matrix when the resource types have multiple instances, and recovers by aborting processes one at a time or by preempting and rolling back to a checkpoint. Databases do exactly this: MySQL InnoDB and PostgreSQL run cycle detection on their lock graphs and abort the cheapest victim transaction. The ostrich algorithm is to ignore the problem entirely, and Linux, Windows and macOS all choose it for kernel resources. The reasoning is economic: deadlocks in a general purpose kernel are rare, prevention would cripple the resource model, avoidance needs information applications cannot supply, and detection costs continuous overhead, so the rational choice is to let the rare occurrence happen and let the user reboot or kill the process.

PREVENTION      negate a condition structurally
  mutual excl   make resources sharable (read only data only)
  hold and wait request everything up front (wasteful, starvation)
  no preempt    force release of everything on a failed request
  circular wait TOTAL ORDER on locks, acquire ascending  <- the practical one

AVOIDANCE       Banker's algorithm, needs max demand declared up front
DETECTION       wait for graph, find a cycle, then recover
RECOVERY        abort a victim, or preempt and roll back to a checkpoint
OSTRICH         ignore it (Linux, Windows, macOS for kernel resources)

RESOURCE ALLOCATION GRAPH
  P1 -> R1        request edge
  R2 -> P1        assignment edge
  single instance per resource: a CYCLE means DEADLOCK
  multiple instances:           a cycle means MAYBE, run detection

/* Databases choose detection and recovery */
mysql> SHOW ENGINE INNODB STATUS\G
LATEST DETECTED DEADLOCK
*** (1) TRANSACTION: UPDATE orders  WHERE id = 55
*** (2) TRANSACTION: UPDATE payments WHERE id = 91
*** WE ROLL BACK TRANSACTION (2)

postgres=# SHOW deadlock_timeout;
 1s        # wait this long, then run cycle detection

Answer

This is circular wait expressed in database row locks. Service A begins a transaction, updates the orders row which takes an exclusive lock, then updates the payments row. Service B, running concurrently, updates payments first and then orders.

When the interleaving is unlucky, A holds the orders lock and waits for payments while B holds payments and waits for orders, and neither can proceed. All four Coffman conditions are present: row locks are exclusive, each transaction holds one while requesting another, the database will not revoke a lock from a live transaction, and the wait is circular. It appears intermittently because it requires the two transactions to overlap in a specific window, which is why it correlates with traffic peaks and why it never reproduces in staging.

The database itself will detect it, InnoDB and PostgreSQL both run cycle detection on the lock graph, and will abort one transaction with a deadlock error, so the visible symptom is usually a periodic transaction rollback rather than a hang. Ranked fixes. First and best, impose a global lock ordering: make every code path that touches both tables acquire them in the same order, for example always orders then payments, or more generally sort the primary keys before updating a batch.

This eliminates circular wait entirely, costs nothing at run time, and is the exact textbook prevention technique. Second, shrink the transaction so the two updates are not held open across a network call, an external API or user think time, which drastically narrows the overlap window without eliminating the possibility. Third, accept the deadlock and retry: catch the deadlock error code and retry the transaction with randomised exponential back off, which is a legitimate production pattern because the database has already rolled back cleanly, but it treats the symptom rather than the cause. A fourth option, coarser locking such as SELECT FOR UPDATE on a parent row, works but serialises throughput.

SERVICE A                         SERVICE B
BEGIN;                            BEGIN;
UPDATE orders   SET ... id=55;    UPDATE payments SET ... id=91;
   /* holds lock on orders 55 */      /* holds lock on payments 91 */
UPDATE payments SET ... id=91;    UPDATE orders   SET ... id=55;
   /* WAITS for B */                  /* WAITS for A */
                DEADLOCK

mysql> SHOW ENGINE INNODB STATUS\G
*** WE ROLL BACK TRANSACTION (2)
ERROR 1213 (40001): Deadlock found when trying to get lock

/* FIX 1 (best): global lock ordering, breaks circular wait */
/* Rule: always touch orders BEFORE payments, everywhere. */
UPDATE orders   SET ... WHERE id = 55;
UPDATE payments SET ... WHERE id = 91;
/* For batches, sort the keys first */
List<Long> ids = new ArrayList<>(input);
Collections.sort(ids);
for (Long id : ids) update(id);

/* FIX 2: shrink the transaction, never span a network call */
BEGIN;  update; update;  COMMIT;      /* no HTTP call inside */

/* FIX 3: retry with jittered back off, treats the symptom */
for (int attempt = 0; attempt < 3; attempt++) {
    try { runTxn(); break; }
    catch (DeadlockException e) {
        Thread.sleep(50L * (1L << attempt) + rand.nextInt(50));
    }
}

Answer

Priority inversion occurs when a high priority task is blocked waiting for a resource held by a low priority task, so the effective priority of the high priority task is inverted. That alone is bounded and acceptable. The dangerous form is unbounded priority inversion, which needs a third task: a medium priority task that is runnable and preempts the low priority lock holder.

The low priority task now cannot run, so it cannot release the lock, so the high priority task stays blocked for as long as the medium priority task chooses to run, which is unbounded. In July 1997 the Mars Pathfinder lander began resetting on the Martian surface. Its VxWorks system had a high priority bus management task, a low priority meteorological data task, and medium priority communications tasks.

The two data tasks shared a mutex on the information bus. When the meteorological task held the mutex and was preempted by long running communications work, the bus management task blocked past its deadline, a watchdog concluded the system had hung, and it triggered a total system reset. JPL reproduced it on the ground replica, and the fix was uploaded to Mars: VxWorks mutexes supported priority inheritance but the flag had been left off, so they toggled it remotely.

The two standard protocols are worth naming precisely. Priority inheritance: when a high priority task blocks on a mutex, the holder temporarily inherits the blocked task's priority for as long as it holds the lock, so no medium priority task can preempt it, and it reverts on release. Priority ceiling: every mutex is assigned a ceiling equal to the highest priority of any task that may acquire it, and any task holding it immediately runs at that ceiling, which also prevents deadlock and bounds blocking to one critical section. On Linux, pthread_mutexattr_setprotocol with PTHREAD_PRIO_INHERIT enables inheritance, and futexes support a kernel assisted priority inheritance mode.

TASKS: H (high), M (medium), L (low). H and L share mutex X.

t0  L acquires X
t1  H becomes runnable, preempts L, tries to take X, BLOCKS
t2  M becomes runnable, preempts L (M outranks L)
t3  M runs and runs and runs...
    L cannot run, so L cannot release X, so H stays blocked.
    H is effectively running at M's mercy: UNBOUNDED inversion.

MARS PATHFINDER, July 1997
  H = bus management task
  M = communications tasks
  L = meteorological data task, held the information bus mutex
  watchdog saw the bus task miss its deadline -> full system reset
  fix uploaded to Mars: turn ON priority inheritance in VxWorks

/* PRIORITY INHERITANCE: L runs at H's priority while holding X */
pthread_mutexattr_t attr;
pthread_mutexattr_init(&attr);
pthread_mutexattr_setprotocol(&attr, PTHREAD_PRIO_INHERIT);
pthread_mutex_init(&x, &attr);

/* PRIORITY CEILING: the mutex carries a fixed ceiling priority */
pthread_mutexattr_setprotocol(&attr, PTHREAD_PRIO_PROTECT);
pthread_mutexattr_setprioceiling(&attr, 90);

$ chrt -f 80 ./control_loop     # SCHED_FIFO, real time priority 80

Answer

A barber shop has one barber, one barber chair and N waiting chairs. If there are no customers the barber sleeps. A customer who arrives wakes the barber if he is asleep, sits in a waiting chair if one is free, and leaves if the shop is full.

The problem models a bounded worker pool with a queue and a drop policy, which is exactly a thread pool with a bounded queue and a rejection handler, and that is the framing that makes it worth asking. The standard solution uses three semaphores and one shared counter. The semaphore customers, initialised to 0, counts waiting customers and is what the barber blocks on, so waiting on it is literally the barber sleeping.

The semaphore barbers, initialised to 0, signals that the barber is ready to cut. A mutex protects waiting, the integer count of customers in chairs. The barber loops: wait on customers, lock the mutex, decrement waiting, signal barbers, unlock, then cut hair.

The customer locks the mutex, and if waiting is less than N it increments waiting, signals customers, unlocks, waits on barbers and gets a haircut, otherwise it unlocks and leaves. The race a naive version leaves is the check then act problem on the seat count. If the customer tests waiting less than N outside the mutex and then increments inside, two customers can both observe N minus 1 and both sit, overflowing the shop; equally, if the customer signals customers before incrementing waiting under the mutex, the barber can wake, decrement a counter that has not yet been incremented and drive it negative.

The rule is that the test and the increment must be atomic under the same mutex, and the signal must happen while the invariant holds. A subtler variant asks who gets the chair when the barber signals barbers and two customers are waiting, which is not fair by default; semaphores make no ordering guarantee, so a fair shop needs a ticket queue.

semaphore customers = 0;    /* number waiting, barber sleeps on this */
semaphore barbers   = 0;    /* barber is ready                       */
mutex     m;
int       waiting   = 0;    /* customers in waiting chairs           */
const int N         = 5;    /* waiting chairs                        */

BARBER                              CUSTOMER
======                              ========
while (true) {                      lock(m);
    wait(customers); /* sleep */    if (waiting < N) {
    lock(m);                            waiting += 1;
    waiting -= 1;                       signal(customers);  /* wake barber */
    signal(barbers);                    unlock(m);
    unlock(m);                          wait(barbers);      /* wait my turn */
    cut_hair();                         get_haircut();
}                                   } else {
                                        unlock(m);
                                        leave();            /* shop full */
                                    }

/* THE RACE in naive versions
   if (waiting < N) { lock(m); waiting += 1; unlock(m); ... }
   two customers both read waiting = N-1 outside the mutex,
   both enter, waiting becomes N+1, the shop overflows.
   Test and increment MUST be atomic under one mutex. */

/* Same shape as a real thread pool */
new ThreadPoolExecutor(1, 1, 0L, MILLISECONDS,
    new ArrayBlockingQueue<>(5),            /* N waiting chairs */
    new ThreadPoolExecutor.AbortPolicy());  /* customer leaves  */

Answer

Exact LRU requires either a timestamp counter written into the page table entry on every memory reference, or a doubly linked list moved on every reference. Both need hardware to intervene on each access, and no mainstream CPU offers that, so kernels approximate. The hardware does give one cheap bit, the reference or accessed bit, which the MMU sets automatically when a page is touched and the kernel can clear.

The second chance algorithm is FIFO plus that bit: examine the oldest page, and if its reference bit is 0 evict it, but if the bit is 1 clear it, give the page a second chance and move on to the next. The clock algorithm is the same policy implemented as a circular list with a moving hand, which avoids the list shuffling of plain FIFO. Enhanced second chance uses the reference and modify bits as an ordered pair, preferring to evict a page that is neither referenced nor dirty because that needs no write back, then referenced but clean, and so on, which meaningfully reduces disk traffic.

LFU counts references and evicts the least frequently used, but it has a well known flaw: a page that was heavily used during startup keeps a high count forever and never gets evicted, so real implementations age the counters by shifting them right periodically. MFU exists as a curiosity based on the argument that a low count page has just arrived and will likely be used. What Linux actually does is a two list clock variant: an active list and an inactive list, both approximating LRU per memory zone, with pages promoted from inactive to active on a second access and demoted under pressure, so a single scan of a large file cannot evict the working set. Multi generational LRU, merged in recent kernels, refines this into several generations and improves behaviour under memory pressure considerably.

SECOND CHANCE / CLOCK

        hand
         |
   [P4:1]-[P7:0]-[P2:1]-[P9:1]

examine the page at the hand:
  ref bit 0 -> EVICT it
  ref bit 1 -> set it to 0, advance the hand, give a second chance
if every bit is 1, the hand makes a full circle clearing bits,
degenerating to plain FIFO. That is the worst case.

ENHANCED SECOND CHANCE, (reference, modify) pairs, best first
  (0,0) not used, not dirty  -> best victim, no write back
  (0,1) not used, dirty      -> must write back first
  (1,0) used, clean
  (1,1) used and dirty       -> worst victim

LFU flaw: a page hot during startup keeps a huge count forever.
Fix: age the counters, count = count >> 1 every K references.

LINUX: two clock lists per zone
  inactive list  <-> active list
  second access promotes to active, pressure demotes to inactive
  a one time scan of a huge file fills inactive and is reclaimed first,
  so it cannot evict the real working set

$ grep -E 'Active|Inactive' /proc/meminfo
Active:          4210332 kB
Inactive:        6120884 kB
Active(file):    2810220 kB
Inactive(file):  5904412 kB

Answer

On a rotating disk, access time is seek time plus rotational latency plus transfer time, and seek dominates, so the scheduler's job is to minimise head movement. Take the classic queue 98, 183, 37, 122, 14, 124, 65, 67 with the head at cylinder 53 on a 200 cylinder disk. FCFS services them in arrival order and moves 640 cylinders, which is terrible but perfectly fair.

SSTF always picks the closest request, giving 236 cylinders, but it starves distant requests indefinitely if nearby ones keep arriving, exactly like SJF starves long jobs. SCAN, the elevator algorithm, sweeps in one direction servicing everything on the way, then reverses at the end of the disk, giving 236 here when sweeping toward cylinder 0 first; it bounds waiting but treats the middle of the disk better than the edges, and a request just behind the head waits a full sweep. C-SCAN fixes the fairness asymmetry by servicing in one direction only and then jumping back to the start without servicing, which gives a much more uniform wait time at the cost of the return trip, 382 cylinders here.

LOOK and C-LOOK are the practical variants: identical to SCAN and C-SCAN except the head reverses at the last actual request rather than at the physical end of the disk, giving 299 for LOOK. On a modern NVMe SSD, none of this matters much. There is no head and no rotation, so access time is essentially uniform regardless of address, and reordering by logical block address buys almost nothing.

What matters instead is parallelism, since an NVMe device has many deep queues and thrives on many outstanding requests, write amplification and the flash translation layer's garbage collection, and TRIM telling the device which blocks are free. That is why Linux ships the none scheduler for NVMe, uses mq deadline or kyber for cases needing latency fairness, and reserves bfq for rotational or desktop interactive workloads.

Head at 53, queue: 98 183 37 122 14 124 65 67, disk 0 to 199

FCFS   53>98>183>37>122>14>124>65>67
       45+85+146+85+108+110+59+2                = 640 cylinders

SSTF   53>65>67>37>14>98>122>124>183
       12+2+30+23+84+24+2+59                    = 236 cylinders
       (starves far requests if near ones keep arriving)

SCAN   53>37>14>0>65>67>98>122>124>183   (sweep down, then up)
       53 + 183                                 = 236 cylinders

C-SCAN 53>65>67>98>122>124>183>199>0>14>37
       146 + 199 + 37                           = 382 cylinders
       (uniform waiting time, that is the point)

LOOK   53>65>...>183 then reverse at the last request >37>14
       130 + 169                                = 299 cylinders

$ cat /sys/block/nvme0n1/queue/scheduler
[none] mq-deadline kyber
$ cat /sys/block/nvme0n1/queue/rotational
0                      # no head, no seek, reordering buys little

$ iostat -x 1 | head -4
Device  r/s    w/s   rareq-sz  aqu-sz  %util
nvme0n1 4102  1820      24.0    12.4   38.2
# aqu-sz (queue depth) is what matters on NVMe, not seek order

Answer

An inode is the on disk structure holding everything about a file except its name: type and permissions, owner and group, size, timestamps, link count, and the pointers to data blocks, typically twelve direct pointers plus single, double and triple indirect blocks in classic ext style layouts. The name lives in a directory entry, which is just a mapping from name to inode number, and that separation explains links. A hard link is an additional directory entry pointing at the same inode, so the two names are indistinguishable peers, they share permissions and content, and the inode's link count is incremented.

Deleting a name only decrements the count, and the data is freed only when the count reaches zero and no process holds the file open, which is why deleting a large log file that a process still has open does not return the space until the process closes it. Hard links cannot cross filesystems because inode numbers are only meaningful within one filesystem, and are not permitted for directories because that would allow cycles. A soft or symbolic link is a small file whose content is a path string, so it can cross filesystems and point at directories, but it dangles if the target is removed.

Journaling protects metadata consistency across a crash by writing intent to a log before applying it, so recovery replays or discards the journal instead of running a full fsck over the whole filesystem. ext4 offers three modes: journal, which logs both data and metadata and is safest and slowest; ordered, the default, which journals metadata only but forces data blocks to disk before the metadata commits; and writeback, which journals metadata with no ordering guarantee and can expose stale data after a crash. For RAID under a database, RAID 10, striped mirrors, is the standard choice because it keeps write performance high and rebuilds quickly, while RAID 5 and 6 suffer the read modify write penalty on every small random write. RAID 0 is striping with no redundancy and RAID 1 is pure mirroring.

$ ls -li file.txt hardlink.txt softlink.txt
 INODE  LINKS  SIZE  NAME
786434      2   120  file.txt
786434      2   120  hardlink.txt      # SAME inode, link count 2
786501      1     8  softlink.txt -> file.txt

$ stat file.txt
  Size: 120   Blocks: 8   IO Block: 4096   regular file
Device: 8,1   Inode: 786434   Links: 2

$ df -i                 # inode exhaustion: disk free but no inodes left
Filesystem      Inodes   IUsed  IFree IUse% Mounted on
/dev/sda1      6553600 6553600      0  100% /

$ lsof +L1              # deleted but still open, space not reclaimed
COMMAND  PID  USER  FD  TYPE  SIZE      NLINK  NODE NAME
java    4102  app   3w  REG   9812440064     0 78202 /var/log/api.log (deleted)

EXT4 JOURNAL MODES
  data=journal   log data + metadata   safest, slowest
  data=ordered   log metadata, flush data first   DEFAULT
  data=writeback log metadata only     fastest, stale data after a crash
$ tune2fs -l /dev/sda1 | grep 'Default mount options'

RAID
  0   striping, no redundancy, any disk loss is total loss
  1   mirroring, 50 percent capacity, fast reads
  5   striping + distributed parity, read modify write penalty on writes
  6   dual parity, survives 2 failures, worse write penalty
  10  striped mirrors: the standard choice for databases

Answer

A monolithic kernel runs the entire operating system, scheduler, memory manager, filesystems, network stack and device drivers, in a single address space in kernel mode. Communication between subsystems is a function call, so it is fast, but any bug in any driver can corrupt any kernel data structure and panic the machine, and the codebase is large and tightly coupled. A microkernel keeps only the minimum in kernel mode, typically address space management, thread scheduling and inter process communication, and pushes filesystems, drivers and network stacks into user space servers.

The benefits are strong isolation, since a crashed driver takes down only its own server which can be restarted, better security because a compromised driver has no kernel privileges, and easier extensibility. The cost is that every operation that used to be a function call becomes message passing across address spaces, so a single file read may cross the user kernel boundary several times, and that overhead sank the first generation of microkernels. Mach and MINIX are the classic examples, QNX is the successful commercial one in automotive and embedded, and seL4 is the formally verified modern one.

Hybrid kernels sit in between: Windows NT and XNU on macOS are structurally microkernel influenced but run most services in kernel mode for performance. Linux is emphatically monolithic, yet it gets most of the practical benefit of modularity through loadable kernel modules, which are object files linked into the running kernel at run time with insmod or modprobe and removed with rmmod. That gives you the ability to ship, load and unload drivers without recompiling or rebooting, but note the crucial difference: a module runs in kernel space with full privileges, so it delivers packaging modularity and not fault isolation. The modern refinement worth naming is eBPF, which safely runs verified user supplied programs inside the kernel, and userspace driver frameworks like FUSE and DPDK that move filesystems and networking out of the kernel by choice.

MONOLITHIC (Linux)          MICROKERNEL (QNX, seL4)     HYBRID (NT, XNU)
=========================   ========================    ================
 user apps                   apps  fs  drv  net          user apps
=========================    =========================   ================
 scheduler mm fs net drv     IPC, sched, addr spaces      most services
=========================    =========================   ================
 function calls, fast        message passing, isolated   pragmatic mix
 one driver bug panics all   crashed driver restarts     compromise

$ lsmod | head -4
Module                  Size  Used by
nvme                   49152  3
ext4                  921600  2
btrfs                1560576  0

$ sudo modprobe nvme          # load a driver into the RUNNING kernel
$ sudo rmmod btrfs            # unload it
$ modinfo ext4 | head -3
filename:  /lib/modules/6.8.0/kernel/fs/ext4/ext4.ko
license:   GPL

/* A module runs in KERNEL space with full privilege.
   Modularity of packaging, NOT fault isolation. */

$ bpftool prog list          # eBPF: verified programs run in kernel safely
$ ls /dev/fuse               # FUSE: filesystems implemented in user space

Answer

A container is not a lightweight virtual machine, it is an ordinary Linux process whose view of the system has been restricted. A virtual machine runs a full guest kernel on virtualised hardware provided by a hypervisor, so it boots, has its own scheduler and memory manager, takes hundreds of megabytes and seconds to start, and is isolated at the hardware boundary. A container shares the host kernel, so it starts in milliseconds, costs the memory of the process itself, and is isolated only by kernel features.

Those features are namespaces and cgroups, and naming them precisely is the whole point of this question. Namespaces control what a process can see: the PID namespace gives the container its own process tree where its main process is PID 1 and it cannot see host processes; the mount namespace gives it its own filesystem view, which combined with pivot_root is what makes the image look like the root filesystem; the network namespace gives it its own interfaces, routing table and iptables rules; UTS gives its own hostname; IPC isolates shared memory and message queues; the user namespace maps container root to an unprivileged host uid; and cgroup namespace hides the host's cgroup hierarchy. Cgroups control what a process can use: CPU shares and quota, memory limits, block I/O throttling, and PID count limits.

Layered on top are capabilities, which drop most of root's powers, seccomp filters restricting the allowed system calls, and LSMs like AppArmor or SELinux. Docker is a packaging and lifecycle tool over these primitives; runc actually calls clone with the namespace flags and writes the cgroup files. The consequences follow directly: a container cannot run a different kernel from the host, a kernel exploit escapes the container, top inside a container may show host CPU counts unless the runtime hides it, and the container is OOM killed at its cgroup memory limit while the host still has free memory.

VIRTUAL MACHINE                CONTAINER
=======================        =========================
guest kernel per VM            SHARES the host kernel
hypervisor virtualises HW      namespaces + cgroups
boots in seconds, GBs          starts in ms, MBs
hardware boundary isolation    kernel feature isolation
can run a different OS         must match the host kernel

NAMESPACES (what a process can SEE)
  pid     own process tree, its main process is PID 1
  mnt     own filesystem view (with pivot_root)
  net     own interfaces, routes, firewall rules
  uts     own hostname
  ipc     own shared memory and message queues
  user    container root maps to an unprivileged host uid
  cgroup  hides the host cgroup hierarchy

CGROUPS (what a process can USE)
  cpu.max  memory.max  io.max  pids.max

$ lsns -t pid -t net
        NS TYPE NPROCS   PID USER COMMAND
4026531836 pid     212     1 root /sbin/init
4026532210 pid       1  8841 root nginx: master

$ cat /proc/self/cgroup
0::/system.slice/docker-9f2a1c.scope
$ cat /sys/fs/cgroup/system.slice/docker-9f2a1c.scope/memory.max
536870912                        # 512 MB, host free memory is irrelevant

$ unshare -pfm /bin/bash       # new PID and mount namespaces
# mount -t proc proc /proc     # give it its own /proc
# ps -ef
UID  PID  PPID  CMD
root   1     0  /bin/bash              # you are PID 1 now