"""Five panels. A job gets 98% of a CPU by giving it up, and the fix costs the job the rule exists to protect. python3 demo.py """ from mlfq import Job, MLFQ, DEMOTE_BURST, DEMOTE_ALLOT Q = (10, 20, 40) H1 = 1000 H2 = 2000 def hogs(policy, quanta=Q, boost=0, yield_at=9, n=2, horizon=H1, switch=0): """One gamer plus `n` jobs identical to it that never release the CPU.""" jobs = [Job(0, 0, 10 ** 9, yield_after=yield_at)] jobs += [Job(i, 0, 10 ** 9) for i in range(1, n + 1)] sim = MLFQ(jobs, quanta=quanta, policy=policy, boost=boost, switch=switch) sim.run(horizon) return jobs, sim def rule(title): print() print(title) print("-" * len(title)) # ---------------------------------------------------------------- panel A rule("A. Three identical CPU-hungry jobs. J0 releases the CPU 1 tick early.") jobs, sim = hogs(DEMOTE_BURST) print(" MLFQ levels %s, %d ticks, demote-on-slice-exhaustion, no boost" % (Q, H1)) print() for x in jobs: print(" J%d %-18s cpu = %4d ticks (%5.1f%%) ends at level %d" % (x.jid, "yields at 9 of 10" if x.yield_after else "runs flat out", x.cpu, x.cpu / 10.0, x.lvl)) print() print(" %d / %d = %dx" % (jobs[0].cpu, jobs[1].cpu, jobs[0].cpu // jobs[1].cpu)) print() print(" who holds the CPU, ticks 0-39:") print(" " + "".join(str(t[1]) if t[1] is not None else "." for t in sim.trace[:40])) print(" J0 runs 0-8 and releases; J1 runs 9-18 and the timer demotes it;") print(" J2 runs 19-28 and the timer demotes it. From tick 29 level 0 is") print(" J0's alone. 1000 - 2*10 = %d." % (H1 - 2 * Q[0])) # ---------------------------------------------------------------- panel B rule("B. What the demotion rule actually reads") print(" Two jobs that each release after 1 tick. The only difference is what") print(" they do off-CPU: the gamer waits 0 ticks, the honest one waits 20.") print() seen = {} for blk, name in ((0, "gamer "), (20, "interactive")): js = [Job(0, 0, 10 ** 9, yield_after=1, block=blk)] js += [Job(i, 0, 10 ** 9) for i in (1, 2)] MLFQ(js, quanta=Q, policy=DEMOTE_BURST).run(H2) seen[blk] = [(b, s) for (b, s, _) in js[0].disp] print(" %s cpu = %4d releases = %4d first 6 (used, slice_expired):" % (name, js[0].cpu, len(seen[blk]))) print(" %s" % (seen[blk][:6],)) n = min(len(seen[0]), len(seen[20])) print() print(" identical over the common prefix of %d releases: %s" % (n, seen[0][:n] == seen[20][:n])) print(" ...and they receive 1980 and 96 ticks. %.1fx the CPU on identical" % (1980 / 96.0)) print(" evidence. The rule is not fooled, it is blind by construction.") # ---------------------------------------------------------------- panel C rule("C. The fix, and what it costs") def mixed(policy, boost): js = [Job(0, 0, 10 ** 9, yield_after=9, block=0)] # the gamer js += [Job(1, 0, 10 ** 9), Job(2, 0, 10 ** 9)] # CPU hogs js += [Job(3, 0, 10 ** 9, yield_after=2, block=30), Job(4, 0, 10 ** 9, yield_after=2, block=30)] # interactive MLFQ(js, quanta=Q, policy=policy, boost=boost).run(H2) lat = js[3].lat + js[4].lat return (js[0].cpu, js[1].cpu + js[2].cpu, js[3].cpu + js[4].cpu, sum(lat) / len(lat)) print(" %d ticks: 1 gamer + 2 CPU hogs + 2 real interactive jobs (2 ticks of" % H2) print(" CPU per 30-tick device wait). Fair share 400; the interactive pair's") print(" unloaded ceiling is 126 ticks each.") print() print(" %-24s %7s %7s %11s %10s" % ("", "gamer", "hogs", "interact.", "inter.lat")) for label, pol, b in (("R4-old, no boost", DEMOTE_BURST, 0), ("R4-old + boost(100)", DEMOTE_BURST, 100), ("R4-new, no boost", DEMOTE_ALLOT, 0), ("R4-new + boost(100)", DEMOTE_ALLOT, 100)): g, h, i, l = mixed(pol, b) print(" %-24s %7d %7d %11d %10.1f" % (label, g, h, i, l)) print() print(" row 3 kills the exploit and mugs the honest job: interactive") print(" latency 8.4 -> 32.2. Row 2, the textbook anti-starvation boost,") print(" leaves the gamer 1440 of 2000 and makes latency WORSE (8.4 ->") print(" 18.1) by promoting the hogs into the interactive jobs' queue.") print(" Only row 4 gets all three.") # ---------------------------------------------------------------- panel D rule("D. The folklore: 'run 99% of the quantum, then yield'") print(" yield_at free yield switch=1 switch=2 (gamer cpu of %d)" % H1) for y in (1, 3, 5, 7, 9): row = [hogs(DEMOTE_BURST, yield_at=y, switch=sw)[0][0].cpu for sw in (0, 1, 2)] print(" %8d %10d %8d %8d" % (y, row[0], row[1], row[2])) print() print(" With a free release the yield POINT is worth exactly nothing:") print(" releasing after 1 tick pays the same 980 as releasing after 9.") print(" Charge one tick per context switch and the same sweep spans") print(" 489..880. You run to the last tick to amortise the switch, not") print(" to dodge demotion.") # ---------------------------------------------------------------- panel E rule("E. Where the effect vanishes") print(" (i) one level -- MLFQ with a single queue IS round robin:") print(" levels gamer cpu honest cpu") for nl in (1, 2, 3, 4): q = tuple(Q[0] * 2 ** i for i in range(nl)) j, _ = hogs(DEMOTE_BURST, quanta=q) print(" %6d %9d %s" % (nl, j[0].cpu, [x.cpu for x in j[1:]])) print(" At one level the gamer gets 315 -- LESS than either honest job.") print(" The exploit needs somewhere to be left standing above.") print() print(" (ii) boost often enough and the two rules become indistinguishable:") print(" boost R4-old gamer R4-new gamer rules agree?") first_div = None for b in list(range(1, 46)) + [100, 500, 0]: o = [x.cpu for x in hogs(DEMOTE_BURST, boost=b)[0]] w = [x.cpu for x in hogs(DEMOTE_ALLOT, boost=b)[0]] if first_div is None and o != w and b: first_div = b if b in (1, 10, 20, 30, 38, 39, 100, 500, 0): print(" %5s %12d %12d %s" % ("none" if b == 0 else b, o[0], w[0], o == w)) print(" Identical CPU totals for every boost interval from 1 to %d;" % (first_div - 1)) print(" they first diverge at %d. Boost fast enough and nothing lives" % first_div) print(" long enough to be demoted: MLFQ has collapsed into round robin") print(" and there is no rule left to argue about.") print()