Answer

I built, ran, and verified the full model. The complete self-contained write-up is saved at /workspace/SOLUTION.md; the runnable module is at /workspace/rtpi. Here is the solution document.

Modeling the Linux RT PI mutex (rt_mutex) as an exact single-CPU scheduler in Go 1.26

Problem class: go-futex-pi-chain-robin-unlock-bounded-inversion-exactness Environment: Go 1.26, standard library only Artifact: /workspace/rtpi (package rtpi), golden at /workspace/rtpi/testdata/trace.golden

1. Root-cause analysis

A naive event simulator ("run the named thread, FIFO waiter queue, wake the head on unlock") is wrong in four independent ways, each of which shows up as an immediate numeric mismatch:

1. Lost priority boost. rt_mutex computes Eff(t) = max(normal_prio, top pi_waiter) and keeps the top waiter of every lock t owns in pi_waiters. This is transitive (rt_mutex_adjust_prio_chain). Omit it and runq, wticks, and the inversion window change on the next event.
2. FIFO waiters / no steal. Waiters sort by effective priority (__waiter_less). On unlock the kernel does not transfer ownership: mark_wakeup_next_waiter() deboosts the releaser, sets owner = RT_MUTEX_HAS_WAITERS, wakes the top waiter and leaves it queued. The waiter acquires only when it runs try_to_take_rt_mutex(); a strictly higher-priority arrival can rt_mutex_steal() the ownerless lock first (the "robin-unlock" reordering).
3. Handoff/deboost race. The releaser's deboost and the wake happen together, so a just-handed-off top waiter can be immediately deboosted to its own priority by a queued unlock of another lock it owns, without cancelling the handoff. Eager ownership transfer cannot represent this.
4. No EDEADLK detection. The chain walk returns -EDEADLK when it reaches orig_lock or an owner equal to top_task. The victim is deterministic: the task that closes the cycle. Without it, a cyclic wait-for graph deadlocks.

ModeNaive in the code is exactly "FIFO + no PI + no detection + no steal", so the failure is reproducible with go test -red.

2. The exact fix

2.1 Data model (1:1 with kernel state)

• Thread.Base=normal_prio, Thread.Eff=prio, Thread.PiWaiters=pi_waiters, Thread.BlockedOn=pi_blocked_on.
• Lock.Owner=rt_mutex_owner(), Lock.Waiters=wait tree, sorted by effective priority descending, FIFO among equals.
• Waiter carries the task's effective priority, so boosts flow transitively.

2.2 PI as a least fixpoint

Because cycles are rejected, the closed form is unique and equals the incremental chain walk:

Eff(t) = max(Base(t), max over locks L owned by t of topWaiter(L).Task.Eff)

recompute() iterates from Base to the least fixpoint; this also correctly re-sorts a blocked task's waiter after setpriority.

2.3 Core functions (from model.go)

// try_to_take_rt_mutex(): the lock must be ownerless; take if it is the top
// waiter, or (Steal) if strictly higher than the top waiter. On a steal the
// top waiter stays queued.
func (s *Sim) tryTake(l *Lock, t *Thread, w *Waiter) bool {
    if l.Owner != nil {
        return false
    }
    if len(l.Waiters) == 0 {
        l.Owner = t
        if w != nil {
            t.BlockedOn = nil
        }
        s.recompute()
        return true
    }
    top := l.Waiters[0]
    cand := t.Eff
    if w != nil {
        cand = w.Task.Eff
    }
    if (w != nil && w == top) || (s.Mode.Steal && cand > top.Task.Eff) {
        if w != nil {
            s.removeWaiter(l, w)
            t.BlockedOn = nil
        }
        l.Owner = t
        s.recompute()
        return true
    }
    return false
}

// mark_wakeup_next_waiter(): leave the lock ownerless, wake the top waiter,
// keep it queued; recompute applies the deboost.
func (s *Sim) doUnlock(ev Event) {
    t := s.Threads[ev.Thread]
    l := s.lock(ev.Lock)
    if l.Owner != t {
        s.Errors = append(s.Errors, fmt.Sprintf("t=%d T%d unlock %s EBADF", ev.At, ev.Thread, ev.Lock))
        return
    }
    l.Owner = nil
    if len(l.Waiters) > 0 {
        w := l.Waiters[0]
        if w.Task.Blocked {
            w.Task.Blocked = false
            w.Task.runSeq = s.nextRunSeq()
        }
    }
    s.recompute()
}

// Deterministic victim: the requester that closes the wait-for cycle.
func (s *Sim) wouldDeadlock(t *Thread, l *Lock) bool {
    seen := map[*Lock]bool{}
    for cur := l; cur != nil; {
        if seen[cur] {
            return true
        }
        seen[cur] = true
        o := cur.Owner
        if o == nil {
            return false
        }
        if o == t {
            return true
        }
        if o.BlockedOn == nil {
            return false
        }
        cur = o.BlockedOn.Lock
    }
    return false
}

doLock runs the self/cycle check, then tryTake(l,t,nil), then enqueues and blocks. The woken waiter actually acquires inside tick() via tryTake(..., waiter), which is where the steal race is decided. doTimeout removes the waiter and clears pi_blocked_on. recompute is the PI fixpoint. Full source (630 lines) is in /workspace/rtpi/model.go; the red-to-green suite is /workspace/rtpi/model_test.go.

3. Verification

3.1 Commands

cd /workspace/rtpi
go vet ./...
gofmt -l .                        # prints nothing
go test -count=1 -v ./...         # GREEN
go test -count=1 -red ./...       # RED baseline: 4 failures
go test -run TestGoldenTrace -update ./...   # regenerate golden (if intended)

3.2 Green run (all 9 tests)

--- PASS: TestKernelInversionChainBounded
--- PASS: TestNaiveInversionChainUnbounded
--- PASS: TestKernelDeadlockDetection
--- PASS: TestNaiveDeadlocks
--- PASS: TestGoldenTrace
--- PASS: TestTopWaiterHandoffAndQueuedDeboost
--- PASS: TestStealReordersAheadOfWokenWaiter
--- PASS: TestTimeoutRemovesWaiter
--- PASS: TestLostBoostIsANumericMismatch
PASS
ok      example.com/rtpi    0.002s

3.3 Red run — go test -red ./...

--- FAIL: TestKernelInversionChainBounded
    green: kernel PI must erase the inversion window, got 102
--- FAIL: TestKernelDeadlockDetection
    green: cycle must be broken by EDEADLK
--- FAIL: TestGoldenTrace
    byte mismatch (naive dump differs)
--- FAIL: TestStealReordersAheadOfWokenWaiter
    kernel: T4 must steal S1
FAIL

3.4 Golden trace byte-equality

TestGoldenTrace compares s.Dump() byte-for-byte with testdata/trace.golden. The green run reaches:

final runq=[T5:5 T4:4 T3:3 T2:2] block=[T1:0 T2:10 T3:8 T4:0 T5:8] wticks=155 \
maxInvWindow=0 maxInvDepth=0 deadlocked=no \
deadlocks=[t=31 T4 lock D1 EDEADLK(cycle)] errors=[t=31 T4 lock D1 EDEADLK(cycle)]

The golden trace exercises, in order: transitive 3-deep inheritance (T1:5), the handoff+queued-unlock deboost ([008] T2 drops to 2 while still the queued top waiter on A), a timeout, the steal at t=23 (T4 takes ownerless S1 while T2 stays queued), and the EDEADLK whose victim is the closer T4.

3.5 What each test proves

Test	Invariant
TestKernelInversionChainBounded	5 threads, depth 3; T1 inherits 5 transitively, maxInvWindow == 0.
TestNaiveInversionChainUnbounded	FIFO/no-PI baseline has a long window (102) and no boost.
TestKernelDeadlockDetection	5-thread cycle broken; victim is the closer (T5).
TestNaiveDeadlocks	Same trace without detection deadlocks.
TestGoldenTrace	Byte-equality of the whole dump and final maxInvWindow.
TestTopWaiterHandoffAndQueuedDeboost	Handoff leaves A ownerless with T2 queued; queued unlock of B deboosts T2 to base 2 without cancelling the handoff.
TestStealReordersAheadOfWokenWaiter	Higher arrival at the same tick takes the ownerless lock; naive does not.
TestTimeoutRemovesWaiter	remove_waiter clears the wait entry and pi_blocked_on, owner unchanged.
TestLostBoostIsANumericMismatch	Lost boost immediately changes wticks and maxInvWindow.

3.6 The maxInvWindow metric

Per tick, inv = max over non-running t of max(0, t.Base - running.Eff). maxInvWindow is the longest consecutive run with inv > 0. Under correct PI the boosted owner is the running thread, so the chain yields inv == 0; any dropped boost makes inv > 0 on the very next tick — the exactness requirement.

3.7 Determinism

Total ordering everywhere: threads in ID order, waiters on (Eff desc, seq), run-queue ties on runSeq, explicit integer timestamps. Re-runs are byte-identical.

Reproduce: cd /workspace/rtpi && go test ./... (green) and go test -red ./... (red). Full markdown: /workspace/SOLUTION.md.

# Evidence
- Problem class: go-futex-pi-chain-robin-unlock-bounded-inversion-exactness
- Model: openrouter/deepseek/deepseek-v4.1-flash
- Solved: 2026-09-25T04:13:02.710Z
- Verification: solution produced by pi in sandbox; see signatures.json

{"description": "In Go 1.26 with the standard library only, model the Linux real-time PI mutex (rt_mutex) as a deterministic single-CPU scheduler: given an event trace of lock/unlock waiter-timeout/setpriority operations across N threads and a fixed 5-priority band, after every event emit the exact run queue, each thread's accumulated blocking time, and the priority-weighted tick counter so any lost priority boost becomes an immediate numeric mismatch. Correctness requires transitive inheritance down multi-level waiter chains, chain splicing plus top-waiter handoff on unlock (including the race where a just-handed-off top waiter is immediately deboosted to its own priority by a queued unlock), robin-unlock reordering of an arriving higher-priority waiter ahead of a blocked owner's waiters, and EDEADLK cycle detection over the waiter-priority graph with the kernel's deterministic victim choice. Ship a red-to-green test suite that includes a five-thread, three-deep inversion chain which deadlocks under naive FIFO waiter handling, and assert the exact byte-equality of the per-event trace dump plus the final max inversion window.", "environment": "go1.26", "language": "go", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "go-futex-pi-chain-robin-unlock-bounded-inversion-exactness", "provider": "openrouter", "solved_at": "2026-09-25T04:13:02.711Z", "version": "1.26"}