Basics

The two jobs

Everything an OS does is one of these, and saying so out loud organises an otherwise sprawling subject:

• Abstraction. Turn awkward hardware into clean interfaces — disks become files, network cards become sockets, physical RAM becomes a private address space. Programs get portability; the OS absorbs the mess.
• Arbitration. Decide who gets the CPU, the memory, the disk bandwidth — and enforce that decision against programs that would rather have all of it. This is where scheduling, quotas, and isolation live.

Kernel mode vs user mode

The CPU itself has a privilege bit. On x86 these are rings: ring 0 is kernel mode, ring 3 is user mode (rings 1 and 2 exist and are essentially unused). The mode determines which instructions are legal.

This single bit is the enforcement mechanism for the entire isolation model. When your process tries to write to address 0, the CPU checks the page tables (which only kernel mode can change), finds no mapping, and traps into the kernel — which kills your process instead of letting it corrupt someone else's.

Kernel architectures

Linux is monolithic but modular — drivers load and unload at runtime as kernel modules. That's a packaging distinction, not an isolation one: a loaded module still runs in ring 0 and can still panic the box.

The three ways into the kernel

All three vector through the same machinery: the CPU switches to kernel mode, looks up a handler in the interrupt descriptor table, and runs it. The distinction that matters for interviews is who caused it and whether the current instruction can be resumed. A page fault is resumable — fix the mapping and re-execute. A divide by zero is not.

What a system call actually costs

// What you write
n = read(fd, buf, 4096);

// What happens
1. libc puts the syscall number in a register (rax) and args in rdi/rsi/rdx
2. executes SYSCALL  → CPU switches to ring 0, jumps to the kernel entry point
3. kernel saves user registers, switches to the kernel stack
4. validates: is fd open? is buf a writable user address? is len sane?
      // this validation is not optional — skipping it is a privilege escalation
5. does the work (maybe from the page cache; maybe blocks on disk)
6. restores registers, SYSRET → back to ring 3, right after the SYSCALL

Direct cost: ~50–100 ns on modern x86 (SYSCALL/SYSRET are fast).
Real cost: often much more, because the entry/exit path flushes speculation
state and pollutes caches. Spectre/Meltdown mitigations roughly doubled it.

Consequence: batching matters. Reading 1 MB in 4 KB chunks is 256 syscalls;
one 1 MB read is one. This is why buffered I/O exists, why io_uring exists,
and why "just add a syscall per event" designs collapse under load.

Interrupt handling and the two halves

An interrupt handler runs at a bad time — it has stolen the CPU from whatever was running, often with interrupts disabled. So it must be short. Linux splits the work:

• Top half (hard IRQ): acknowledge the device, grab the data out of the way, schedule the rest. Microseconds. Cannot sleep, cannot block.
• Bottom half (softirq, tasklet, or workqueue): the actual processing — parse the packet, wake the waiting process. Runs with interrupts enabled and can be preempted.

Why it matters practically: a network card at 1M packets/second would spend the entire CPU in interrupt handlers. The fix is interrupt coalescing (the device batches and interrupts once per N packets) and polling (Linux NAPI switches from interrupts to polling under load). This is the same batching insight as syscalls.

The boot path, briefly

power on → firmware (BIOS/UEFI) → POST, find a boot device
  → bootloader (GRUB) loads the kernel + initramfs into memory
  → kernel: set up page tables, detect hardware, mount root
  → start PID 1 (systemd/init) in user mode
  → PID 1 starts everything else
The only reason to know this: it explains why PID 1 is special (it adopts
orphans and cannot be killed) and where "kernel panic: no init found" comes from.

What a process is made of

Address space (virtual, per-process)      Kernel-side (the PCB)
┌──────────────────────┐ high             · PID, PPID, UID/GID
│ stack   ↓ grows down │                  · process state
├──────────────────────┤                  · saved registers + program counter
│      (unmapped)      │                  · page table pointer (CR3)
├──────────────────────┤                  · open file descriptor table
│ heap    ↑ grows up   │  ← malloc/brk    · signal handlers + pending signals
├──────────────────────┤                  · cwd, umask, resource limits
│ BSS  (zero-init)     │                  · accounting: CPU time, faults
├──────────────────────┤                  · exit status (kept for the parent)
│ data (initialised)   │
├──────────────────────┤            In Linux the PCB is task_struct,
│ text (code, r-x)     │ low         and it is per-THREAD, not per-process.
└──────────────────────┘

Process states

fork, exec, wait

fork()   duplicate the calling process. Returns TWICE:
           child gets 0, parent gets the child's PID, −1 on failure.
         The child gets a copy of the address space — but lazily, via
         copy-on-write: pages are shared read-only until one side writes.

exec()   REPLACE this process's image with a new program.
         Same PID, same fds (unless marked close-on-exec). Does not return.

wait()   parent blocks until a child exits, and collects its exit status.
         This is what REAPS the zombie.

// The universal shell pattern: fork, then exec in the child
pid_t pid = fork();
if (pid == 0)      { execvp("ls", args); _exit(127); }  // child
else if (pid > 0) { waitpid(pid, &status, 0); }             // parent

What's shared and what isn't

Threading models

Goroutines are the model worth naming: a goroutine starts with a ~2–8 KB growable stack against a thread's 8 MB, and Go's runtime multiplexes them onto one OS thread per core, moving a goroutine off when it blocks. That's why a million goroutines is routine and a million OS threads is not.

Choosing: process, thread, or neither

Sizing heuristics worth quoting: for CPU-bound work, threads ≈ number of cores (more just adds switching). For I/O-bound work, threads ≈ cores × (1 + wait time / compute time), which is why an I/O-heavy service can usefully run far more threads than cores.

What happens

1. An interrupt or trap enters the kernel (timer tick, syscall that blocks, or a higher-priority task waking).
2. Save the outgoing task's registers, program counter and stack pointer into its PCB.
3. The scheduler picks the next task.
4. If it's a different process, switch address spaces — load the new page table root (CR3 on x86). This is the expensive part.
5. Restore the incoming task's registers and return to user mode. Execution resumes exactly where it stopped.

The real cost is indirect

Direct cost      1–3 µs: saving/restoring registers, scheduler bookkeeping.
                 Measurable, and honestly small.

Indirect cost    THE ACTUAL PROBLEM.
  · Cache pollution — the new task evicts the old task's L1/L2/L3 lines.
    When the old task resumes, it starts cold. Rebuilding a working set
    can cost tens of microseconds, 10–100× the direct cost.
  · TLB pressure — address-space switch invalidates translations. Tagged
    TLBs (PCID on x86) reduce but do not remove this.
  · Branch predictor and prefetcher state are lost too.

Thread → thread in the SAME process is cheaper: same page tables, so no
CR3 reload and much less TLB damage. Caches are still disturbed.

Rule of thumb: a switch effectively costs low tens of microseconds once
you count the cold cache. That is why a 4 ms quantum is fine (<1% overhead)
and a 10 µs quantum would be catastrophic.

The metrics

The algorithms

Worked example — the same jobs, four algorithms

Job  Arrival  Burst
P1     0        7
P2     2        4
P3     4        1
P4     5        4

FCFS            P1(0-7)  P2(7-11)  P3(11-12)  P4(12-16)
  WT: P1=0, P2=5, P3=7, P4=7                      avg WT = 4.75
  P3 needs 1ms and waits 7 — the convoy effect in one line.

SJF (non-preemptive)   P1(0-7)  P3(7-8)  P2(8-12)  P4(12-16)
  WT: P1=0, P2=6, P3=3, P4=7                      avg WT = 4.00
  At t=7 it picks P3 (burst 1) over P2 (burst 4). P1 already ran because
  nothing else had arrived at t=0 — non-preemptive can't undo that.

SRTF (preemptive SJF)
  P1(0-2) P2(2-4) P3(4-5) P2(5-7) P4(7-11) P1(11-16)
  WT: P1=9, P2=1, P3=0, P4=2                      avg WT = 3.00
  Best average — and P1, the longest job, absorbs all the pain.

Round robin (quantum = 2)
  P1(0-2) P2(2-4) P1(4-6) P3(6-7) P2(7-9) P4(9-11) P1(11-13) P4(13-15) P1(15-16)
  WT: P1=9, P2=5, P3=2, P4=6                      avg WT = 5.50
  Worst average waiting time — and the best RESPONSE time: every job
  runs within one round. That trade is the entire point of RR.

Multi-level feedback queues

The clever idea: rather than being told which jobs are short, find out. Start every job at the top priority. If it uses its whole quantum it's probably CPU-bound, so demote it. If it blocks before the quantum expires it's probably interactive, so keep it high.

Q0  quantum 8ms   ← new jobs start here; interactive tasks stay here
Q1  quantum 16ms  ← used a full quantum at Q0
Q2  quantum 32ms  ← CPU-bound; longer slices, fewer switches
Q3  FCFS          ← background batch

Rules:  higher queue always runs first
        used the whole quantum → drop a level
        blocked before it expired → stay (or move up)
        PERIODIC BOOST: every ~1s, move everything back to Q0

The boost exists for two reasons: it stops long-running jobs starving
forever, and it handles a job that CHANGES behaviour — a compiler that
finishes compiling and starts waiting on input. Without it, gaming the
scheduler is easy: issue a pointless I/O just before your quantum ends
and you stay at top priority forever.

Linux CFS — fair queuing instead of priorities

The Completely Fair Scheduler discards queues entirely. It tracks each task's virtual runtime (vruntime) — CPU time consumed, weighted by priority — in a red-black tree, and always runs the task with the smallest vruntime. In the limit, everyone converges to an equal share.

Why this design is elegant, and worth saying: starvation is impossible without any ageing machinery, because a starved task's vruntime stops growing and it automatically becomes the leftmost node. Fairness falls out of the data structure rather than being bolted on. A new or newly-woken task gets vruntime set near the minimum, so interactive tasks get served quickly without being explicitly detected. (Newer kernels replace CFS with EEVDF, which adds an explicit latency guarantee — same fairness idea, better tail behaviour.)

Scheduling classes and real-time

Real-time means predictable, not fast. A hard real-time system guarantees a deadline is met (airbag controller); soft real-time tolerates occasional misses (video playback). Linux is not hard real-time out of the box — PREEMPT_RT exists precisely to reduce worst-case latency.

Multiprocessor scheduling

• Per-CPU run queues avoid a single global lock, which would be a scalability disaster at high core counts.
• Load balancing periodically migrates tasks between queues. Migration is costly — the task loses its warm cache and may land on a different NUMA node with slower memory.
• Affinity keeps a task near its cache. Soft affinity is a preference; taskset gives hard pinning, which is standard for latency-sensitive services.