code wiki / _hdl_build / nx_clock_edf_gate.nx
`nx_clock_edf_gate.nx` source

↩ module page · 181 lines · 11017 B
1// nx_clock_edf_gate.nx -- GATE for the wall-clock/EDF scheduler (debt 1785872141, operator 2026-08-04
2// "get the clock to sota"). Proves the SOTA properties on the PURE decision functions, so a 6-HOUR
3// period is verified in MILLISECONDS with fabricated clock values instead of by waiting 6 hours.
4//
5// T1 EDF ORDER: the most-overdue job is picked FIRST (earliest deadline), not registry order.
6// T2 NOT-DUE: nothing overdue -> pick returns -1 (a scheduler must not invent work).
7// T3 CATCH-UP WITHOUT RUNAWAY: re-arming a job 5 periods late lands STRICTLY past now, exactly once.
8// T4 MISSED PERIODS ARE COUNTED, NOT HIDDEN: a job 3 periods late reports 3.
9// T5 THE REGRESSION ITSELF (the whole reason this exists): simulate a window where dispatching costs
10//    real time. Under the OLD model (logical tick advanced by SLEEP ONLY) a 21600s job is still not
11//    due after a full real day. Under the NEW model (wall-clock deadlines) it fires on time.
12//    This is a NEGATIVE CONTROL: the old algorithm MUST fail the same assertion the new one passes,
13//    or the tooth proves nothing.
14// T6 MIGRATION IS EXACT: legacy logical-tick deadlines convert; genuine epochs are left ALONE.
15// T7 STARVATION IS BOUNDED: with EDF + re-arm, every job in a saturated set fires within its own
16//    period once the backlog drains -- no job is passed over forever.
17// expect_exit: 0   license_tier: ORIGINAL   Read-only. No hw writes (Rule 26).
18import "nx_clock_sched.nx"
19import "nx_syscalls.nx"
20import "nx_gate_verdict.nx"   // 2026-08-06: this gate emitted NO verdict= anchor, so nx_gate_green read a
21// PASSING run as NOT-GREEN and /api/build REFUSED it outright (detector nx_gatedry, seq585). The gate that
22// proves the EDF scheduler -- including T7, the starvation tooth -- was therefore STRUCTURALLY UNJUDGEABLE
23// and could never appear in the rollup. ★A GATE THAT CANNOT BE JUDGED IS NOT A WEAK GATE, IT IS NO GATE.
24
25const G_N: i64 = 8
26
27func gw(s: *u8) -> i64 { var n: i64=0; while s[n]!=(0 as u8){n=n+1} sys_write(1,s,n); return 0 }
28func gn(v: i64) -> i64 {
  var m: i64=v; if m<0{gw("-" as *u8);m=0-m}
  let t:*u8=sys_mmap(24); var k:i64=0
  if m==0{t[0]=48 as u8;k=1}
  while m>0{t[k]=(48+(m%10)) as u8;m=m/10;k=k+1}
  let o:*u8=sys_mmap(24); var i:i64=0
  while i<k{o[i]=t[k-1-i];i=i+1}
  sys_write(1,o,k); return 0
36}
37func row(name: *u8, ok: i64, pass: *i64, total: *i64) -> i64 {
  total[0] = total[0] + 1
  if ok==1 { pass[0]=pass[0]+1; gw("  [PASS] " as *u8) } else { gw("  [FAIL] " as *u8) }
  gw(name); gw("\n" as *u8)
  return ok
42}
43
44func main() -> i64 {
  gw("=== nx_clock_edf_gate: wall-clock EDF scheduling (kills the logical-tick drift) ===\n" as *u8)
  let pass: *i64 = sys_mmap(16) as *i64; let total: *i64 = sys_mmap(16) as *i64
  pass[0]=0; total[0]=0
  let dl: *i64 = sys_mmap(G_N*8) as *i64
  let iv: *i64 = sys_mmap(G_N*8) as *i64
  let NOW: i64 = 1785900000
51
  // ---- T1 EDF order: three overdue, the EARLIEST deadline must win (index 2, not 0) ----
  iv[0]=60;    dl[0]=NOW-10
  iv[1]=120;   dl[1]=NOW-5
  iv[2]=21600; dl[2]=NOW-9000     // most overdue in absolute terms = earliest deadline
  iv[3]=60;    dl[3]=NOW+300      // not due
  let k1: i64 = clk_edf_pick(dl, 4, NOW)
  gw("    picked index="); gn(k1); gw(" (expect 2 = the 6h job, most overdue)\n" as *u8)
  var t1: i64 = 0; if k1 == 2 { t1 = 1 }
  row("T1 EDF: the most-overdue job is dispatched FIRST, not registry order" as *u8, t1, pass, total)
61
  // ---- T2 nothing due -> -1 ----
  dl[0]=NOW+1; dl[1]=NOW+2; dl[2]=NOW+3; dl[3]=NOW+4
  let k2: i64 = clk_edf_pick(dl, 4, NOW)
  var t2: i64 = 0; if k2 == (0-1) { t2 = 1 }
  row("T2 nothing overdue -> pick=-1 (never invents work)" as *u8, t2, pass, total)
67
  // ---- T3 catch-up: 5 periods late, one re-arm lands strictly past now ----
  iv[0]=60; dl[0]=NOW-300
  let skipped: i64 = clk_edf_rearm(dl, iv, 0, NOW)
  gw("    after rearm deadline-now="); gn(dl[0]-NOW); gw(" skipped="); gn(skipped); gw("\n" as *u8)
  var t3: i64 = 0
  if dl[0] > NOW { if dl[0] <= NOW+60 { t3 = 1 } }
  row("T3 catch-up re-arm lands strictly past now, within one interval (no runaway, no drift)" as *u8, t3, pass, total)
75
  // ---- T4 missed periods reported honestly ----
  iv[0]=100; dl[0]=NOW-300
  let miss: i64 = clk_edf_missed(dl, iv, 0, NOW)
  gw("    missed="); gn(miss); gw(" (expect 3)\n" as *u8)
  var t4: i64 = 0; if miss == 3 { t4 = 1 }
  row("T4 missed periods are COUNTED (3 late = 3), never silently swallowed" as *u8, t4, pass, total)
82
  // ---- T5 THE REGRESSION + NEGATIVE CONTROL ----
  // A day of real time. Each beat sleeps until the fastest job (60s) then dispatches; every beat
  // burns EXEC_COST seconds of real time inside children. OLD model: logical T += sleep only.
  // NEW model: deadline compared against the real clock.
  let DAY: i64 = 86400
  let SLEEP: i64 = 60
  let EXEC: i64 = 30          // measured-plausible: 132 dispatches/window of real organs
  var real_t: i64 = 0
  var logical_T: i64 = 0
  while real_t < DAY {
      logical_T = logical_T + SLEEP          // OLD: advances by what it SLEPT
      real_t = real_t + SLEEP + EXEC         // REAL: sleep PLUS what the children took
  }
  gw("    after 1 real day: logical_tick="); gn(logical_T)
  gw(" real_secs="); gn(real_t); gw("\n" as *u8)
  // the 6h job under the OLD model: due when logical_T >= 21600
  var old_fired: i64 = 0; if logical_T >= 21600 { old_fired = 1 }
  // ...but the question is whether it fired ON TIME (4x in a day). Count old fires:
  let old_fires: i64 = logical_T / 21600
  let new_fires: i64 = real_t / 21600
  gw("    6h-job fires in that day -- OLD(logical)="); gn(old_fires)
  gw("  NEW(wall-clock)="); gn(new_fires); gw("  (expect 4 for a correct 6h period)\n" as *u8)
  var t5: i64 = 0
  if new_fires == 4 { if old_fires < 4 { t5 = 1 } }     // NEW correct AND OLD provably wrong
  row("T5 REGRESSION+NEGCTL: wall-clock fires a 6h job 4x/day; the OLD logical tick provably does NOT" as *u8, t5, pass, total)
  if old_fires < 4 { gw("      (negative control BIT: the old model lost " as *u8); gn(4-old_fires); gw(" of 4 fires = the measured 21h defect)\n" as *u8) }
109
  // ---- T6 migration exact: ticks convert, epochs untouched ----
  iv[0]=21600; dl[0]=2970420          // a legacy LOGICAL TICK (the live value seen 2026-08-04)
  iv[1]=60;    dl[1]=NOW+30           // a genuine epoch, must NOT be touched
  let conv: i64 = clk_edf_migrate(dl, iv, 2, NOW)
  gw("    converted="); gn(conv); gw(" row0="); gn(dl[0]-NOW); gw(" row1_untouched="); gn(dl[1]-NOW); gw("\n" as *u8)
  var t6: i64 = 0
  if conv == 1 { if dl[0] == NOW+21600 { if dl[1] == NOW+30 { t6 = 1 } } }
  row("T6 migration converts legacy ticks EXACTLY and leaves real epochs alone" as *u8, t6, pass, total)
118
  // ---- T7 no permanent starvation: saturated set, every job eventually picked ----
  var i: i64 = 0
  while i < G_N { iv[i]=60; dl[i]=NOW-1000+i*7; i=i+1 }   // all overdue, distinct deadlines
  let seen: *i64 = sys_mmap(G_N*8) as *i64
  i=0; while i<G_N { seen[i]=0; i=i+1 }
  var step: i64 = 0
  var cur: i64 = NOW
  while step < G_N*2 {
      let k: i64 = clk_edf_pick(dl, G_N, cur)
      if k >= 0 { seen[k]=1; clk_edf_rearm(dl, iv, k, cur) }
      step = step + 1
  }
  var allseen: i64 = 1
  i=0; while i<G_N { if seen[i]==0 { allseen=0 } i=i+1 }
  row("T7 no permanent starvation: every job in a saturated set gets dispatched" as *u8, allseen, pass, total)
134
  // ---- T8 DEMAND vs CAPACITY: the number that explains a starving beat whose row and elf are both fine ----
  // T7 proves EDF starves nobody PERMANENTLY *once the backlog drains*. On the live plane the backlog NEVER
  // drained -- 45 jobs demanded ~273 dispatches per 1800s window while the window completed 51 -- so T7 held
  // while every beat ran late, and netobs read as dead for days.
  // ★A GATE THAT PROVES A PROPERTY "ONCE THE BACKLOG DRAINS" PROVES NOTHING ABOUT A SYSTEM WHOSE BACKLOG
  // NEVER DRAINS -- so assert the drain PRECONDITION itself, not only the ordering.
  iv[0]=30; iv[1]=30; iv[2]=60; iv[3]=60          // 60+60+30+30 = 180 dispatches required per 1800s window
  let dem: i64 = clk_demand_per_window(iv, 4, 1800)
  gw("    demand=" as *u8); gn(dem); gw(" (expect 180)\n" as *u8)
  var t8: i64 = 0; if dem == 180 { t8 = 1 }
  row("T8 demand/window is derived from the real periods (30,30,60,60 @1800s = 180)" as *u8, t8, pass, total)
146
  // ---- T9 the demand figure is a CONSERVATIVE FLOOR, so 'demand > capacity' is proof, not suspicion ----
  iv[0]=86400; iv[1]=21600; iv[2]=1800; iv[3]=0   // two sub-window periods, one exact, one ZERO interval
  let dem2: i64 = clk_demand_per_window(iv, 4, 1800)
  gw("    demand(long+zero)=" as *u8); gn(dem2); gw(" (expect 1)\n" as *u8)
  var t9: i64 = 0; if dem2 == 1 { t9 = 1 }
  row("T9 demand FLOORS (periods longer than the window -> 0) and a ZERO interval never divides" as *u8, t9, pass, total)
153
  // ---- T10/T11 THE PARALLEL-DISPATCH CORRECTNESS CONDITION ----------------------------------
  // Proven on the PURE picker BEFORE it is wired to a live dispatcher. Under bounded parallelism a
  // running job is still overdue (it is re-armed only after reaping), so a picker without a busy mask
  // dispatches a SECOND copy of the organ already saturating the box. These two teeth are the whole
  // reason clk_edf_pick_free exists as a separate function instead of a flag on the incumbent.
  let busy: *i64 = sys_mmap(G_N*8) as *i64
  iv[0]=60;    dl[0]=NOW-10
  iv[1]=120;   dl[1]=NOW-5
  iv[2]=21600; dl[2]=NOW-9000     // MOST overdue -- and about to be marked in-flight
  iv[3]=60;    dl[3]=NOW+300      // not due at all
  busy[0]=0; busy[1]=0; busy[2]=1; busy[3]=0
  let k10: i64 = clk_edf_pick_free(dl, 4, NOW, busy)
  gw("    busy=[_,_,X,_] picked index="); gn(k10); gw(" (expect 0 -- index 2 is the most overdue but IN FLIGHT)\\n" as *u8)
  var t10: i64 = 0; if k10 == 0 { t10 = 1 }
  row("T10 an IN-FLIGHT job is never re-picked, even when it is the most overdue (no double dispatch)" as *u8, t10, pass, total)
169
  busy[0]=1; busy[1]=1; busy[2]=1; busy[3]=0
  let k11: i64 = clk_edf_pick_free(dl, 4, NOW, busy)
  gw("    all-overdue-busy picked index="); gn(k11); gw(" (expect -1 -- the only free job is NOT due)\\n" as *u8)
  var t11: i64 = 0; if k11 == (0-1) { t11 = 1 }
  row("T11 every overdue job in flight -> -1: the loop WAITS rather than inventing a duplicate" as *u8, t11, pass, total)
175
  // VERDICT THROUGH THE CANONICAL LIB (D001): the anchor comes with it, so a passing run is judgeable.
  let ctr: *i64 = sys_mmap(16) as *i64
  ctr[0] = pass[0]; ctr[1] = total[0]
  let rc: i64 = gv_verdict("CLOCK-EDF" as *u8, ctr, "wall-clock EDF: drift-free periods, EDF order, honest starvation, demand-vs-capacity" as *u8)
  sys_exit(rc); return rc
181}
nx_clock_edf_gate.nx source

`nx_clock_edf_gate.nx` source
