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

↩ module page · 135 lines · 7437 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"
20
21const G_N: i64 = 8
22
23func gw(s: *u8) -> i64 { var n: i64=0; while s[n]!=(0 as u8){n=n+1} sys_write(1,s,n); return 0 }
24func 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
32}
33func 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
38}
39
40func 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
47
  // ---- 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)
57
  // ---- 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)
63
  // ---- 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)
71
  // ---- 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)
78
  // ---- 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) }
105
  // ---- 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)
114
  // ---- 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)
130
  gw("\n=== nx_clock_edf_gate " as *u8); gn(pass[0]); gw("/" as *u8); gn(total[0])
  if pass[0] == total[0] { gw("  GREEN (wall-clock EDF: drift-free periods, EDF order, honest starvation)\n" as *u8); sys_exit(0); return 0 }
  gw("  RED\n" as *u8)
  sys_exit(1); return 1
135}
nx_clock_edf_gate.nx source

`nx_clock_edf_gate.nx` source
