Scheduling — Smith’s Rule Plus Aging

What goes wrong with a naive approach

The effect queue runs background work (Cmd::perform, async subscriptions, telemetry flushes) alongside rendering. Three naive scheduling policies all fail in predictable ways:

• FIFO — one slow effect blocks all the light ones behind it. A telemetry flush that takes 200 ms stalls a trivial cursor repaint.
• SRPT (shortest remaining processing time) — optimal for average completion time in the unweighted case. But a 10-second export job never runs while short jobs keep arriving. Starvation.
• Priority queues with a static order — nothing ever bubbles up from low priority; long-waiting low-priority jobs die of old age.

The right policy is a weighted SRPT with an aging bonus:

1. Order primarily by Smith’s rule — $w_i / r_i$, the weighted inverse remaining time. This is optimal for weighted mean completion time on a single machine.
2. Add a wait-time bonus so no job waits forever. The aging term is a linear function of the time spent in the queue.

The combination gives optimal throughput for a given weight vector and a provable worst-case wait bound.

Mental model

Every queued job carries three numbers:

• $w$ — importance (weight; default 1.0).
• $r$ — remaining-time estimate (default 10 ms).
• wait — time since enqueue.

Compute priority as:

Pick the maximum. On each tick decrement $r$ for the running job; other jobs accumulate more wait.

• Light, important jobs surface instantly because $w/r$ is large.
• Heavy, unimportant jobs would starve under pure SRPT, but the aging term drags them upward linearly until they run.

The math

Priority function

The schedule at time $t$ is $\arg\max_i P_i(t)$.

Starvation bound

For a job $j$ with minimum weight $\min(w)$, the worst-case wait time before it runs is:

where $S_{\max}$ is the longest job in the queue and $a$ is the aging factor. Halving $a$ doubles the bound; doubling $a$ halves it but costs throughput because more short jobs are starved by aged long jobs.

Throughput vs. fairness trade

$a = 0$ recovers pure Smith’s rule (optimal throughput, unbounded starvation). $a \to \infty$ recovers FIFO (bounded starvation, terrible throughput). FrankenTUI picks $a = 0.1$, empirically a sweet spot on TUI workload traces.

Defaults

Worked example — three jobs

Queue after enqueueing in order A, B, C:

A:  w=1, r=100 ms, wait=0   → priority = 0.01
B:  w=1, r=5 ms,   wait=0   → priority = 0.20   ← picked
C:  w=2, r=10 ms,  wait=0   → priority = 0.20   ← tied with B; id tiebreak

B runs first. Five ms later:

A:  w=1, r=100,    wait=5   → 0.01 + 0.5  = 0.51   ← aged up
C:  w=2, r=10,     wait=5   → 0.20 + 0.5  = 0.70   ← still first

C runs next. After another 10 ms the queue has:

A:  w=1, r=100,    wait=15  → 0.01 + 1.5 = 1.51  ← picked

A is heavy and low-weight but the aging term lifted it above short- job dominance. Nothing starves.

Rust interface

use ftui_runtime::queueing_scheduler::{QueueingScheduler, QueueingConfig, Job};
 
let mut sched = QueueingScheduler::new(QueueingConfig {
    aging_factor: 0.1,
    weight_default: 1.0,
    estimate_default_ms: 10.0,
});
 
sched.enqueue(Job::new("persist")
    .with_weight(1.0)
    .with_estimate_ms(100.0));
sched.enqueue(Job::new("paint-cursor")
    .with_weight(1.0)
    .with_estimate_ms(2.0));
 
let job = sched.pick(); // weighted SRPT with aging

The runtime owns the scheduler; effects enqueue into it from the Cmd executor. See /runtime/rollout/effect-queue for how the scheduler plugs into the runtime’s effect pipeline.

How to debug

Every pick emits a queue_select line:

{"schema":"queue_select","job_idx":17,"id":"persist-state",
 "priority":0.51,"weight":1.0,"remaining_ms":100,
 "wait_time_ms":15,"aging_boost":1.50}

FTUI_EVIDENCE_SINK=/tmp/ftui.jsonl cargo run -p ftui-demo-showcase
 
# Which jobs are being aged heavily?
jq -c 'select(.schema=="queue_select")
       | [.id, .aging_boost]' /tmp/ftui.jsonl | sort -k2 -n | tail -20

A job with aging_boost dominating weight/remaining_ms every pick is essentially FIFO-ing — likely the result of a wrong estimate; raise its weight or fix the estimator.

Pitfalls

Cross-references

• /runtime/rollout/effect-queue — how the scheduler is wired into the effect executor.
• /runtime/overview — the bigger runtime picture.
• Input fairness — Jain’s index intervention that protects input from rendering starvation.

Where next