03substrate

CONTRACT 01deadlockd

A real-time deadlock simulator and concurrency visualiser.

01Identification

LiveLive site Source

My role

Sole author — engine, WebSocket bridge and client

Domain: Concurrency
Level: 03 · Substrate
Stack: Go · Next.js · TypeScript
Licence: MIT
Built: April 2026
Sourced statements: 14

02Context

The problem

Deadlock is taught as a diagram and examined as a definition. Neither shows the thing that actually matters: that a system can be one allocation away from a circular wait and still look completely healthy.

Why it matters

A safety check is only worth having if it can be watched being wrong. Making the state observable is what turns the algorithm from an exam answer into something you can trust in a running system.

03What it does

A Go backend runs the simulation; a Next.js client renders the resource-allocation graph live over a WebSocket bridge. Processes request and release resources, the engine checks whether each request leaves the system in a safe state, and when a circular wait closes the graph locks and the cycle is recovered and displayed.

The correctness is the product. The visualiser exists so the correctness can be observed — which is the only reason the frontend is there at all.

And where that is proven

The safety check copies system state under mutex, then releases the lock before running its O(P²·R) search — so the expensive computation never blocks other goroutines.

backend/engine/banker.go:L15–L30

Cycle detection uses an explicit-stack iterative DFS with white/gray/black colouring rather than recursion, so deep process graphs carry no stack-depth risk — and it recovers the actual cycle through a parent array.

backend/engine/detection.go

Tests assert exact matrix state, not that the code merely ran: a granted safe request must move Available, Allocation and Need to specific expected values.

backend/engine/scenarios_test.go

CI runs go mod verify and the full Go test suite, plus an independent frontend production build, on every push and pull request.

.github/workflows/ci.yml

04Architecture

Two processes and a socket between them. Every decision about safety happens in the Go engine; the browser receives state snapshots and draws them. That split is the design: a correctness engine that needs its own interface in order to be right is not a correctness engine.

Layers, shallow to deep

Next.js clientDashboard, sandbox and matrix viewers, with the resource-allocation graph drawn through @xyflow/react. It computes nothing about safety.
WebSocket hubCommands in, state snapshots out. The only thing the client talks to, and the only thing that talks back.
Simulation managerApplies a request tentatively, asks the safety check, then commits it or rolls it back under the same mutex.
Safety and detectionBanker's safety search and the wait-for cycle detector. Both read a copy of the matrices; neither touches the live ones.
System stateAvailable, Allocation and Need behind a sync.Mutex, with one goroutine per simulated process.

What happens to one request

Request
A process asks for a quantity of a resource.
Tentative allocation
The manager applies it to the state before deciding anything about it.
Safety check
IsSafeState looks for an order in which every process could still finish.
Commit or roll back
Safe grants the resource; unsafe restores the previous allocation under mutex and rejects the request.
Snapshot
The resulting state is dispatched to every connected client.

README.md — system architecture

05Decisions

Each one states what forced it, what was rejected, the reasoning, and what it cost.

01Decision
Copy Available, Allocation and Need under the mutex, release it, and run the search on the copy.
over Holding the mutex for the duration of the search.
The pressure
The safety search is O(P²·R) and reads every matrix in the system, while goroutines standing in for processes are asking for resources the whole time.
Why this way
The lock exists to keep the matrices consistent, not to serialise the simulation. A quadratic search inside the critical section makes every other goroutine wait on work that does not need live state.
What it cost and bought
The check never blocks a request, and it answers about the state as it was at copy time — which is the correct semantics for a decision the manager is about to act on under the same lock.
backend/engine/banker.go:L15–L30Verify: open backend/engine/banker.go:L15–L30 on GitHub in a new tab
02Decision
An iterative depth-first search with an explicit frame stack and white/gray/black colouring.
over Recursive DFS.
The pressure
Cycle detection over a wait-for graph is naturally recursive, and the graph is as deep as the process count — which the simulation lets you raise.
Why this way
Recursion depth would be bounded by user input. A stack overflow in the detector would take the engine down at exactly the moment it was most needed.
What it cost and bought
Depth costs heap instead of stack, and the gray edge that closes the cycle is unwound from the live stack — so the detector reports which processes are deadlocked, not merely that something is.
backend/engine/detection.goVerify: open backend/engine/detection.go on GitHub in a new tab
03Decision
Rebuild the graph on every detection pass — an edge from a process needing an exhausted resource to every process currently holding any of it.
over Maintaining a wait-for graph incrementally beside the matrices.
The pressure
A wait-for graph is not stored anywhere. The simulation holds allocation matrices, and an edge between two processes is an inference from them.
Why this way
Two representations of the same fact drift apart, and here the one that drifts is the one that decides whether the system is deadlocked.
What it cost and bought
Detection pays for a rebuild each pass. In exchange there is exactly one place where the truth about allocation lives.
backend/engine/detection.goVerify: open backend/engine/detection.go on GitHub in a new tab
04Decision
Assert exact matrix state in the tests, and ship the visualiser as part of the product rather than as a demo.
over A command-line simulator and a suite that checks the code ran.
The pressure
An engine's correctness is invisible. A safety check that quietly returns the wrong answer looks exactly like one that works.
Why this way
A granted safe request has one correct effect on Available, Allocation and Need. Asserting that effect is a different claim from asserting no error was returned, and watching the graph close is a different kind of evidence again.
What it cost and bought
The client is a dependency of the explanation, never of the engine: go test ./... and go run . are both complete without it.
backend/engine/scenarios_test.goVerify: open backend/engine/scenarios_test.go on GitHub in a new tab

06Challenges

The constraint
Two readers — the safety check and the detector — each need a coherent view of three matrices that a dozen goroutines are mutating.
What the system does about it
Both take the mutex only long enough to copy and then let go. Every critical section in the engine is short by construction, because the expensive work is always outside it.
backend/engine/banker.goVerify: open backend/engine/banker.go on GitHub in a new tab
The constraint
A deadlock is only worth showing while it forms, which means the client has to keep up with a graph that changes on every allocation.
What the system does about it
The engine dispatches state snapshots over the socket and the client re-renders memoised nodes. Nothing about the graph is recomputed in the browser, so the rendering cost does not sit on the path that decides safety.
README.md — design notes and constraintsVerify: open README.md — design notes and constraints on GitHub in a new tab

07Results

Commits mine: 6/6; Sole contributor
Safety search: O(P²·R); Documented in-header
CI gates: 2; Go tests · frontend build
Engine modules: 8

08Attribution

Sole author. Six of six commits, engine and client.

Concurrency engine — Banker's Algorithm, cycle detection, recoverySagar6 of 6 commits

WebSocket bridge and Next.js visualiserSagar6 of 6 commits

deadlockd — contributors

09Evidence

backend/engine/banker.goL14 — L30

14func IsSafeState(state *SystemState) (bool, []int) {15	state.Mu.Lock()16	np := len(state.Processes)17	nr := len(state.Resources)19	work := make([]int, nr)20	copy(work, state.Available)24	for i := 0; i < np; i++ {27		copy(need[i], state.Need[i])28		copy(alloc[i], state.Allocation[i])29	}30	state.Mu.Unlock()

Still to write

8 of 10 sections written and sourced

The rest are absent rather than filled with plausible prose, which is the whole point: inventing them would cost exactly the credibility the rest of this page is built to earn.

LessonsNot written yet
Next iterationNot written yet

What these mean: Key to the states above.
Not written yet: Real and known, but not written up.

Identification

Context

What it does

And where that is proven

Architecture

Layers, shallow to deep

What happens to one request

Decisions

Copy Available, Allocation and Need under the mutex, release it, and run the search on the copy.

An iterative depth-first search with an explicit frame stack and white/gray/black colouring.

Rebuild the graph on every detection pass — an edge from a process needing an exhausted resource to every process currently holding any of it.

Assert exact matrix state in the tests, and ship the visualiser as part of the product rather than as a demo.

Challenges

Results

Attribution

Evidence

Still to write