Locks, Deadlock & Dining Philosophers

import { Mulberry32 } from "../random";import type { Tracer } from "../trace";/** One step of a thread that uses locks: take one, give one back, or do something while holding them. */export type LockOp = { kind: "acquire"; lock: string } | { kind: "release"; lock: string } | { kind: "work"; what: string };export interface LockThread {  name: string;  ops: readonly LockOp[];}export const LOCK_POLICIES = ["round-robin", "random"] as const;export type LockPolicy = (typeof LOCK_POLICIES)[number];export const MAX_LOCK_THREADS = 6;export const MAX_LOCK_STEPS = 96;export interface LockReport {  steps: number;  deadlocked: boolean;  /** The threads in the wait-for cycle, each waiting on the next, or empty. */  cycle: string[];  finished: string[];  waits: number;  /** The thread holding each lock, or null. */  holders: Record<string, string | null>;}/** * A lock lets one thread at a time into a piece of code: acquire it, * do the work, release it, and anyone else who asks meanwhile waits. * That fixes a race, and it creates a new way to stop forever. Five * philosophers at a round table each need the fork on their left and * the fork on their right to eat. If everyone picks up the left fork * first, everyone then waits for a right fork that a neighbour holds, * and nobody will ever release anything: a deadlock, a cycle in the * graph of who waits for whom. This scheduler runs threads of acquire, * release, and work steps, blocks a thread that asks for a held lock, * wakes the waiters when it is released, and after every block looks * for a cycle. The cures are all ways of making the cycle impossible: * take locks in one global order, or ask a single arbitrator for both * at once. * * Time: O(threads) per step. Space: O(threads + locks). */export class LockScheduler {  private readonly holders = new Map<string, number>();  private readonly waitingFor: (string | null)[];  private readonly pc: number[];  private readonly random: Mulberry32;  private last = -1;  private steps = 0;  private waits = 0;  private cycle: string[] = [];  constructor(    private readonly threads: readonly LockThread[],    private readonly policy: LockPolicy,    seed = 1,    private readonly tracer?: Tracer,  ) {    if (threads.length < 1 || threads.length > MAX_LOCK_THREADS) throw new RangeError(`threads must be in [1, ${MAX_LOCK_THREADS}]`);    if (!LOCK_POLICIES.includes(policy)) throw new RangeError(`unknown policy ${String(policy)}`);    const total = threads.reduce((sum, thread) => sum + thread.ops.length, 0);    if (total > MAX_LOCK_STEPS) throw new RangeError(`${total} steps exceeds ${MAX_LOCK_STEPS}`);    this.waitingFor = threads.map(() => null);    this.pc = threads.map(() => 0);    this.random = new Mulberry32(seed);  }  /** Who holds each lock named by any thread, or null. */  locks(): Record<string, string | null> {    const names = new Set<string>();    for (const thread of this.threads) for (const op of thread.ops) if (op.kind !== "work") names.add(op.lock);    for (const thread of this.threads) for (const instruction of thread.ops) if (instruction.kind !== "work") names.add(instruction.lock);    return Object.fromEntries([...names].map((lock) => [lock, this.holderName(lock)]));  }  /** The locks a thread holds, in the order it took them. */  held(thread: number): string[] {    return [...this.holders.entries()].filter(([, holder]) => holder === thread).map(([lock]) => lock);  }  /** Runs until every thread finishes or a deadlock is found. */  run(): LockReport {    while (this.cycle.length === 0) {      const runnable = this.runnable();      if (runnable.length === 0) break;      this.step(this.pick(runnable));    }    return {      steps: this.steps,      deadlocked: this.cycle.length > 0,      cycle: [...this.cycle],      finished: this.threads.filter((_, i) => this.pc[i] === this.threads[i]!.ops.length).map((thread) => thread.name),      waits: this.waits,      holders: this.locks(),    };  }  /** One step of one thread: it may block instead of advancing. */  step(thread: number): void {    const program = this.threads[thread];    const op = program?.ops[this.pc[thread] ?? 0];    const instruction = program?.ops[this.pc[thread] ?? 0];    if (!program || !op) throw new RangeError(`thread ${thread} has nothing left to run`);    if (!program || !instruction) throw new RangeError(`thread ${thread} has nothing left to run`);    if (this.waitingFor[thread] !== null) throw new RangeError(`${program.name} is blocked`);    this.steps++;    switch (op.kind) {    switch (instruction.kind) {      case "acquire": {        const holder = this.holders.get(op.lock);        const holder = this.holders.get(instruction.lock);        if (holder !== undefined) {          this.waitingFor[thread] = op.lock;          this.waitingFor[thread] = instruction.lock;          this.waits++;          // ▸ the lock is held, so the thread blocks until the holder releases it          this.tracer?.emit("wait", { thread, name: program.name, lock: op.lock, holder: this.threads[holder]!.name, holding: this.held(thread), waits: this.waits, step: this.steps });          this.tracer?.emit("wait", { thread, name: program.name, lock: instruction.lock, holder: this.threads[holder]!.name, holding: this.held(thread), waits: this.waits, step: this.steps });          this.cycle = this.detect(thread);          // ▸ following who waits for whom came back to the start: a cycle nobody in it can break          if (this.cycle.length > 0) this.tracer?.emit("deadlock", { cycle: [...this.cycle], locks: this.cycle.map((name) => this.waitingFor[this.threads.findIndex((t) => t.name === name)]), step: this.steps });          return;        }        this.holders.set(op.lock, thread);        this.holders.set(instruction.lock, thread);        // ▸ the lock is free, so the thread takes it and goes on        this.tracer?.emit("acquire", { thread, name: program.name, lock: op.lock, holding: this.held(thread), step: this.steps });        this.tracer?.emit("acquire", { thread, name: program.name, lock: instruction.lock, holding: this.held(thread), step: this.steps });        break;      }      case "release": {        if (this.holders.get(op.lock) !== thread) throw new RangeError(`${program.name} does not hold ${op.lock}`);        if (this.holders.get(instruction.lock) !== thread) throw new RangeError(`${program.name} does not hold ${op.lock}`);        this.holders.delete(op.lock);        this.holders.delete(instruction.lock);        // Every thread waiting for this lock may try again on its next turn.        const woken = this.threads.flatMap((waiter, i) => (this.waitingFor[i] === op.lock ? [waiter.name] : []));        const waitersWoken = this.threads.flatMap((waiter, i) => (this.waitingFor[i] === instruction.lock ? [waiter.name] : []));        this.waitingFor.forEach((lock, i) => {          if (lock === op.lock) this.waitingFor[i] = null;          if (lock === instruction.lock) this.waitingFor[i] = null;        });        // ▸ the thread gives the lock back and every thread waiting for it may try again        this.tracer?.emit("release", { thread, name: program.name, lock: op.lock, woken, holding: this.held(thread), step: this.steps });        this.tracer?.emit("release", { thread, name: program.name, lock: instruction.lock, waitersWoken, holding: this.held(thread), step: this.steps });        break;      }      case "work":        // ▸ the thread does what it took the locks for        this.tracer?.emit("work", { thread, name: program.name, what: op.what, holding: this.held(thread), step: this.steps });        this.tracer?.emit("work", { thread, name: program.name, what: instruction.what, holding: this.held(thread), step: this.steps });        break;    }    this.pc[thread] = this.pc[thread]! + 1;    // ▸ the thread has run its last step    if (this.pc[thread] === program.ops.length) this.tracer?.emit("exit", { thread, name: program.name, step: this.steps, finished: this.threads.filter((_, i) => this.pc[i] === this.threads[i]!.ops.length).length });  }  /** Follows who waits for whom from a thread; the names of the cycle if the walk comes back, else empty. */  private detect(thread: number): string[] {    const path: number[] = [];    let current: number | undefined = thread;    while (current !== undefined && !path.includes(current)) {      path.push(current);      const lock: string | null | undefined = this.waitingFor[current];      current = lock === null || lock === undefined ? undefined : this.holders.get(lock);    }    if (current === undefined) return [];    return path.slice(path.indexOf(current)).map((i) => this.threads[i]!.name);  }  private runnable(): number[] {    return this.threads.flatMap((thread, i) => (this.pc[i]! < thread.ops.length && this.waitingFor[i] === null ? [i] : []));  }  private pick(runnable: readonly number[]): number {    const chosen = this.policy === "round-robin" ? (runnable.find((thread) => thread > this.last) ?? runnable[0]!) : runnable[this.random.index(runnable.length)]!;    this.last = chosen;    return chosen;  }  private holderName(lock: string): string | null {    const holder = this.holders.get(lock);    return holder === undefined ? null : this.threads[holder]!.name;  }}