Scheduling and Memory: Virtual Memory, Paging and the TLB

// Jobs arrive together at time 0; each is { name, burst } in milliseconds.
// Wait time = finish - burst; turnaround = finish.
function summarize(finish, jobs) {
  const avg = (xs) => xs.reduce((a, b) => a + b, 0) / xs.length;
  return {
    finish,
    avgWait: avg(jobs.map((j) => finish[j.name] - j.burst)),
    avgTurnaround: avg(jobs.map((j) => finish[j.name])),
  };
}

export function fcfs(jobs) {
  const finish = {};
  let t = 0;
  for (const j of jobs) finish[j.name] = t += j.burst;
  return summarize(finish, jobs);
}

// Shortest job first: the best average wait, but it needs to know the burst and can starve long jobs.
export const sjf = (jobs) => fcfs([...jobs].sort((a, b) => a.burst - b.burst));

// Round robin: each job runs for at most `quantum`, then goes to the back of the queue.
export function roundRobin(jobs, quantum) {
  const left = Object.fromEntries(jobs.map((j) => [j.name, j.burst]));
  const queue = jobs.map((j) => j.name);
  const finish = {};
  let t = 0;
  while (queue.length) {
    const name = queue.shift();
    const ran = Math.min(quantum, left[name]);
    t += ran;
    left[name] -= ran;
    if (left[name] > 0) queue.push(name);
    else finish[name] = t;
  }
  return summarize(finish, jobs);
}

export const PAGE_SIZE = 4096;

export class PageFault extends Error {
  constructor(vpn) {
    super(`page fault on page ${vpn}`);
    this.vpn = vpn;
  }
}

// A virtual address is (page number, offset). The TLB remembers a few recent page -> frame answers.
export class Mmu {
  constructor(pageTable, tlbSize = 2) {
    this.pageTable = pageTable; // Map: page number -> frame number
    this.tlbSize = tlbSize;
    this.tlb = new Map(); // insertion order = least recently used first
    this.stats = { tlbHits: 0, walks: 0, faults: 0 };
  }

  translate(vaddr) {
    const vpn = Math.floor(vaddr / PAGE_SIZE);
    const offset = vaddr % PAGE_SIZE;
    let frame = this.tlb.get(vpn);
    if (frame !== undefined) {
      this.stats.tlbHits += 1;
      this.tlb.delete(vpn); // re-insert below to mark it most recent
    } else {
      this.stats.walks += 1; // TLB miss: walk the page table in memory
      frame = this.pageTable.get(vpn);
      if (frame === undefined) {
        this.stats.faults += 1; // not mapped: the kernel must step in
        throw new PageFault(vpn);
      }
      if (this.tlb.size >= this.tlbSize) this.tlb.delete(this.tlb.keys().next().value);
    }
    this.tlb.set(vpn, frame);
    return frame * PAGE_SIZE + offset;
  }
}

// How many page faults does a reference string cause with `frames` physical frames?
// FIFO evicts the page that has been in memory longest; LRU the one not used for longest.
export function faults(refs, frames, policy = 'lru') {
  const mem = []; // front = next victim
  let count = 0;
  for (const page of refs) {
    const at = mem.indexOf(page);
    if (at >= 0) {
      if (policy === 'lru') mem.push(...mem.splice(at, 1)); // a use makes it the newest
      continue;
    }
    count += 1;
    if (mem.length === frames) mem.shift();
    mem.push(page);
  }
  return count;
}