Part 8 · 2 chapters · ~18 min

M8: OS Kernel Slice

A kernel in a tick-based simulator: process control blocks, timer interrupts and quanta, blocking syscalls woken by interrupts, round robin and MLFQ with demotion, priority preemption and boosts, demand paging with clock eviction, and swap-in as blocking I/O.

Scheduling, syscalls and virtual memory

multiplexing one CPU and a little memory

PCBs with states, program counters, levels and page tables.
Timer interrupts and the quantum, with a cost per context switch.
Blocking syscalls that sleep until an interrupt wakes them.
MLFQ: demote hogs, keep processes that block, preempt for higher priority, boost periodically.
Demand paging with clock eviction.
Swap-in is I/O, and the process blocks for it.

code

$ npm run demo
== rr ==  context switches: 17, evictions: 2
│ hog    │ turnaround 163 │ response  1 │ cpu 121 │
│ editor │ turnaround 167 │ response 22 │ cpu  19 │
│ backup │ turnaround  86 │ response 26 │ cpu   8 │ faults 6

== mlfq ==  context switches: 20, evictions: 2
│ hog    │ turnaround 168 │ response  1 │ cpu 121 │
│ editor │ turnaround  68 │ response  4 │ cpu  19 │      ← interactive work wins
│ backup │ turnaround  42 │ response  7 │ cpu   8 │ faults 6

where this connects

The Computers course covers the real hardware and OS underneath: interrupts, the MMU and TLB, Linux's CFS and EEVDF schedulers, and page reclaim. A browser tab is a process this kernel would schedule, and the Browser course's process model is these same ideas from the renderer's side.

TINY-KERNEL: TICKS, QUEUES AND FRAMES

three processes sharing one CPU and four page frames, under a scheduler that has to guess who is interactive

swipe the figure sideways, or tap expand for full screen

1/6

process table

The process table: each process has a PCB with its state (READY, RUNNING, BLOCKED, ZOMBIE), its program counter, its scheduling level and its page table. A hog computes for 120 ticks; an editor computes for 1 tick then waits for the disk, six times; a backup touches five pages and sleeps.

Building it: tiny-kernel

Repo: repos/kernel. One kernel file, a demo and tests.

code

// src/kernel.ts: one tick of the machine
step() {
  for (const p of this.procs) if (p.state === 'BLOCKED' && p.wakeAt !== undefined && p.wakeAt <= this.tick) this.wake(p);   // interrupts
  // MLFQ: a higher-priority process that became ready preempts at once
  if (this.policy.kind === 'mlfq' && this.running && this.queues.slice(0, this.running.level).some(q => q.length)) {
    const r = this.running; r.state = 'READY'; this.queues[r.level].unshift(r); this.running = null;
  }
  if (!this.running) this.dispatch();
  if (this.running) this.execute(this.running);
  this.tick++;
  // timer interrupt: quantum used and someone waiting → preempt (and, in MLFQ, demote)
  if (this.running && this.running.quantumUsed >= this.quantum(this.running) && this.queues.some(q => q.length)) {
    this.preempt(this.running); this.running = null;
  }
}

code

// clock eviction: a referenced frame gets a second chance
private evict(): number {
  for (;;) {
    const f = this.frames[this.clockHand]!; const idx = this.clockHand;
    this.clockHand = (this.clockHand + 1) % this.frames.length;
    if (f.referenced) { f.referenced = false; continue; }
    const owner = this.procs.find(p => p.pid === f.pid)!;
    owner.pageTable.delete(f.vpage);
    this.swap.add(`${f.pid}:${f.vpage}`);
    return idx;
  }
}

a bug the test found

The first MLFQ ran the editor slower than round robin: 234 ticks against 225. When the editor woke up at level 0, the hog, demoted to level 2 with a 32-tick quantum, kept the CPU until that quantum ran out. MLFQ needs priority preemption: a ready process at a higher level takes the CPU immediately. With that one rule added, the editor's time fell to 63.

Run it. In repos/kernel: npm test, then npm run demo. Change the quanta ([2, 8, 32] to [20, 20, 20]) and watch MLFQ degrade into round robin. Set frames: 2 and watch evictions and faults climb.

exercises

1. fork with copy-on-write: share frames read-only, copy on the first write fault. 2. Multiple CPUs with per-CPU run queues and work stealing. 3. CFS: a virtual-runtime-ordered tree, so the process that has run least goes next. 4. Working-set eviction compared against clock on a looping workload.