Commentary: process-scheduler

Three identical jobs in a multi-level feedback queue. The one that hands the CPU back a single tick early takes 98% of the machine. And the scheduler is not being fooled — the demotion rule is handed the identical evidence by a liar and by a job genuinely waiting on a disk, so the fix that stops one costs the other 3.8× its response time. A study guide for mlfq.py.

cd process-scheduler
python3 demo.py        # the aha (§6)
python3 verify_cf.py   # the counterfactuals (§6.5, §6.6)
python3 test_mlfq.py   # pins every number this page quotes

1. Orientation

A multi-level feedback queue is the scheduler design behind Solaris, FreeBSD's ULE, Windows NT, and every classic Unix. Several run queues at descending priorities; the highest non-empty one runs; and a feedback rule moves jobs between queues based on how they behave. Jobs that look interactive float to the top and get served instantly. Jobs that look like compute hogs sink, and get long uninterrupted slices when nothing else wants the machine. Nobody has to declare anything. The scheduler learns.

What it learns from is one bit per dispatch: did the timer have to take the CPU away from you, or did you hand it back? A job that hands it back is being polite, is probably waiting on a device, and keeps its priority. A job that has to be interrupted is a hog, and is demoted.

This toy runs three jobs that are identical in every respect — same arrival, same unbounded appetite for CPU — except that one of them releases the CPU one tick before its ten-tick slice expires. Over 1000 ticks:

You get more CPU by voluntarily giving it up. 98× more. The job that donates 10% of every slice ends up with 98% of the machine, and it donates nothing in wall-clock terms — it re-enters an empty queue and resumes immediately.

That much is a known exercise. What the rest of this page is about is the part that is not: the scheduler is not being fooled. Put the gamer beside a genuinely interactive job — one that really does wait 20 ticks for a device — and record the evidence the demotion rule is handed at each release. It is the identical sequence, (1 tick used, timer did not fire), for all 96 releases they have in common. One receives 1980 ticks and the other 96. The rule is not deceived by a clever trick; it is blind by construction, because the fact that separates the two jobs is what happens while neither is on the CPU, and no scheduler sees that.

Which means the fix has a bill. Turning the accounting cumulative — the textbook repair — drops the gamer from 1780 ticks to 216 and simultaneously takes the honest interactive job's response latency from 8.4 ticks to 32.2 and a third of its throughput, because a rule that cannot tell the two apart must punish both. And the other textbook rule, the periodic priority boost, turns out to fix nothing on its own while making interactive latency worse. Only both together work.

By the end you should be able to:

• state exactly what a scheduler can and cannot observe about a job, and derive the exploit from that alone rather than memorising it;
• derive the 980 from the quantum and the job count, and predict the number for a configuration you have not run;
• say why the periodic boost, which everyone reaches for first, is the wrong tool here, and show the row where it makes things worse;
• name the one modelling decision that flips the sign of the whole result, and which you will get wrong if you write this simulator yourself;
• say when none of this applies to you — two measured boundaries, one of which is "your MLFQ is secretly round robin."

2. The problem this mechanism exists to solve

A scheduler is handed a set of runnable jobs and has to pick one, thousands of times a second, knowing almost nothing. It wants two things that fight:

Low response time. When you press a key, the shell should run now, not in 40ms. Interactive work is characterised by tiny CPU bursts separated by long waits, so an interactive job asks for very little CPU and cares enormously about when it gets it.

High throughput. A compiler wants as much CPU as it can get and does not care about latency at all. It is best served by long uninterrupted slices, because every context switch is wasted work.

If you knew which job was which, this would be easy: run the interactive ones at high priority with short slices, the batch ones at low priority with long ones. Classic scheduling theory even names the optimal rule for average turnaround — shortest job first, and its preemptive form, shortest remaining time first. Both require knowing how long a job will run, which is the one thing nobody knows.

MLFQ's answer is to guess from history. Start every job at the top, and demote the ones that behave like hogs. The proxy for "hog" is the only signal available for free: whether the timer interrupt had to take the CPU away. This is a genuinely good idea — it costs nothing, needs no declarations from programs, and adapts when a job changes phase.

The competing goals that make more than one design defensible:

• Responsiveness vs. fairness. Keeping a job at the top because it is polite is exactly what you want for a text editor and exactly what you do not want for a job that has discovered politeness is profitable.
• Trusting behaviour vs. counting consumption. A rule that reacts to how you used the CPU can be gamed. A rule that only counts how much cannot, but it also cannot tell an editor from a compiler.
• Starvation vs. the value of demotion. Demotion is only useful if it sticks; a job at the bottom of a busy machine may never run again. Every fix for that erodes the demotion you just made.

The toy exists to show that the first two are not a trade-off you get to tune. They are the same rule read in two directions.

3. Background you need

The two starred rows carry the result. Everything else is scaffolding.

4. The mental model

The scheduler stands at the moment a job leaves the CPU and has to fill in one blank: was that a hog? Here is everything it has to go on.

That is the whole toy. The interesting fact about a job — whether its release was forced by physics or chosen for profit — is a fact about the job's time away from the processor, and a scheduler is not running then. It resumes at the next tick with a queue and a counter, and the counter says the same thing either way.

So there are exactly two families of repair, and neither is free:

• Count consumption instead of reading behaviour. Stop asking how the job left and only track how much it has used at this level. Ungameable, because it measures the thing the gamer is actually taking. Also blind in the other direction: the honest editor's tiny bursts add up too, and down it goes.
• Undo the accounting periodically. Sweep everyone back to the top every so often. Forgives the honest job — and forgives the gamer just as fast, while promoting the compute hogs into the editor's queue on the way past.

The toy measures both, and the resolution is that you need each one to cover the other's failure.

5. Reading the source

5.1 Job — one class, because the difference is not visible

class Job:
    """One runnable thing, described by what it does with the CPU.

    `yield_after` is the toy's entire model of voluntary release: after that
    many ticks of a slice, the job hands the CPU back. `block` is how long it
    then spends off-CPU. A job waiting on a disk and a job merely pretending
    differ ONLY in `block`, which is why they are one class and not two.
    """

    __slots__ = ("jid", "arrival", "service", "yield_after", "block",
                 "lvl", "burst", "allot", "cpu", "state", "wake",
                 "ready_at", "lat", "disp")

The temptation when building this is to write InteractiveJob and GamerJob as separate types, and it would wreck the toy. The claim the page makes is that these two things are indistinguishable to the scheduler, and the honest way to encode that claim is to make them the same type differing in one number the scheduler never reads. block is consulted in exactly one place in the scheduler — mlfq.py:189–192, deciding which list the job goes on — and in no branch that sets a priority.

Two counters, not one, is the other decision here. burst is ticks used in the current slice; allot is ticks used at this level across all slices. The entire toy is a fight over which of them the demotion rule reads.

5.2 The allotment default — making the comparison honest

    def __init__(self, jobs, quanta=(10, 20, 40), allots=None, boost=0,
                 policy=DEMOTE_BURST, switch=0, preempt=True):
        self.jobs = jobs
        self.quanta = list(quanta)
        # The allotment defaults to one quantum, so a job that never releases
        # the CPU voluntarily is demoted at exactly the same instant under
        # both policies. Every difference the demo reports is therefore caused
        # by voluntary releases and by nothing else.
        self.allots = list(allots) if allots else list(quanta)

This is the control, and it is four lines of constructor. If the allotment were larger than the quantum, R4-new would demote later than R4-old for every job, and every number in panel C would mix two effects: the accounting change, and a general loosening. With allots == quanta a job that never yields is demoted at the identical tick under both rules — test_mlfq.py asserts this directly, and the two policies produce the same [350, 340, 310] when nobody games.

So every difference the demo reports is attributable to voluntary releases, which is the only thing the page is arguing about.

5.3 run — the tick, and what the timer means

            slice_over = j.burst >= self.quanta[j.lvl]      # the timer fired
            gave_up = (not slice_over and j.yield_after is not None
                       and j.burst >= j.yield_after)        # voluntary release
            if not (slice_over or gave_up):
                continue                                    # keeps the CPU

Two booleans, and the entire mechanism is downstream of the distinction between them. slice_over is the hardware timer interrupt: it fires whether or not the job wanted it to, and it is the only involuntary way to lose the CPU here. gave_up is a system call — the job asking to be descheduled.

not slice_over and ... on the second line is worth pausing on. If a job's yield_after equals its quantum, the timer wins and the release is recorded as involuntary. That is the right tie-break: a job that intended to yield at exactly tick 10 and got interrupted at exactly tick 10 was, as far as anyone can tell, interrupted. Reverse it and a job could claim credit for a release the hardware performed.

The continue on line 171 is why a job holds the CPU across ticks at all — this loop runs one tick per pass, so "keep running" is expressed as declining to make a scheduling decision.

5.4 The load-bearing line

            # ---- THE LOAD-BEARING LINE ------------------------------------
            if self.policy == DEMOTE_ALLOT:
                demote = j.allot >= self.allots[j.lvl]
            else:
                demote = slice_over
            # ---------------------------------------------------------------

            # Everything the demotion rule was handed, recorded at the moment
            # it decided. demo.py prints two of these lists side by side.
            j.disp.append((j.burst, slice_over, demote))
            j.burst = 0
            if demote:
                if j.lvl + 1 < len(self.q):
                    j.lvl += 1
                j.allot = 0

demote = slice_over is the original R4, and it is a sentence in English: you are demoted if the timer had to stop you. It is the most natural thing to write, it is what the 1962 CTSS scheduler did, and it hands 98% of the machine to whoever notices.

demote = j.allot >= self.allots[j.lvl] never looks at how the job left, only at how much it has taken since it arrived at this level. Flipping between these two, with nothing else changed, is verify_cf.py's CF1:

j.burst = 0 on line 183 is the quiet half of the exploit, and it is outside the if demote: block on purpose. The slice counter resets on every release, voluntary or not — which is simply what a time slice means, a fresh one each time you are dispatched. R4-old's forgiveness is not a special case anyone wrote; it is the automatic consequence of a per-slice counter being per-slice. j.allot = 0 sits inside the if demote: because the allotment is per-visit-to-a-level, and surviving a release is not leaving the level.

That placement difference — one assignment inside the branch, one outside — is the whole repair.

5.5 Where block lands, and why it can't matter

            self.cur = None
            if gave_up and j.block:
                j.state = "blocked"
                j.wake = self.clock + j.block
                self.blocked.append(j)
            else:
                self._enq(j)

Here is the only place in 178 lines of scheduler that reads block, and note what has already happened: the priority decision was made at line 174–187, above this. By the time the code learns whether this job is going to wait for a device, it has already filed the paperwork on whether the job was a hog.

That ordering is not a quirk of the toy. It is the actual causal structure of a scheduler: you must decide what to do with a job at the moment it stops running, and whether its I/O will take 20 microseconds or 20 milliseconds is not knowable then. Writing it in this order makes the impossibility structural rather than asserted.

5.6 _boost — R5, and one line of determinism

    def _boost(self):
        """R5. Everything goes back to the top, running job included.

        Sorting by job id is not fairness, it is determinism: the boost is the
        only moment several jobs are re-queued at once, so it is the only
        place an arbitrary order could leak into a headline number.
        """
        pending = []
        for lvl in range(len(self.q)):
            pending.extend(self.q[lvl])
            self.q[lvl] = []
        if self.cur is not None:

Every other queue operation in the toy handles one job at a time, so FIFO order determines everything. The boost is the exception — it drains three queues into one — and an unsorted drain would make the headline numbers depend on which queue a job happened to be in when the sweep hit. Real schedulers do not care, because they are not trying to publish a table. This one is.

Note the running job is included in the sweep. A boost that spared whoever happened to be executing would give the incumbent a free extra slice, which is a small unfairness that compounds over 20 boosts.

6. The demo, and what it proves

python3 demo.py prints five panels: the exploit, the proof that it is not a trick, the fix and its bill, a piece of folklore that turns out to be inert, and the two boundaries.

6.1 Panel A — the act

The per-tick trace is the whole derivation, and it is worth reading a digit at a time.

Ticks 0–8: nine 0s. J0 runs its nine ticks and releases. Its burst is 9, the quantum is 10, so slice_over is false, so demote is false. It goes to the back of level 0 — behind J1 and J2, who are still there.

Ticks 9–18: ten 1s. J1 uses the whole slice. The timer fires, slice_over is true, and J1 is demoted to level 1. Ticks 19–28: J2, identically.

Tick 29 onwards: all 0s, forever. Level 0 now contains exactly one job, and it is the only job that will ever be in it, because the two others cannot be promoted without a boost and there is none. J0 releases the CPU every nine ticks into an empty queue and is immediately re-dispatched — a release that costs it nothing at all.

The arithmetic. J1 and J2 each get exactly one top-level quantum before being demoted, and nothing else. So J0's total is 1000 − 2×10 = 980. That generalises to a closed form, horizon − n × quantum[0], and CF4 checks it at ten configurations:

Exact at all ten. Note what that means for the shape of the problem: the gamer's take does not depend on how long the run is relative to anything — the honest jobs pay a one-off tax of one quantum each and then contribute nothing forever. Over an infinite run the gamer's share tends to 100%.

6.2 Panel B — the scheduler is not being fooled

The obvious reading of panel A is "the rule has a hole in it, patch the hole." Panel B is the argument that there is no hole.

disp is recorded by the scheduler itself, at line 182, at the instant the decision is made — not reconstructed afterwards from the tick trace. It is literally the argument list of the demotion rule.

The two lists are equal, element for element, over all 96 releases they share. (1, False) every time: one tick used, timer did not fire. The gamer goes on to make 1980 such releases and the honest job only manages 96, but that is the consequence of the decision, not an input to it.

20.6× is 1980 / 96. Both jobs consume exactly one tick per dispatch, so these are also dispatch counts: the gamer is dispatched 1980 times in 2000 ticks, the honest job 96 times, because it spends 20 ticks off-CPU per cycle and the gamer spends zero.

This is why "just detect the gaming" is not an available move. There is nothing in the input to detect it in. Any rule that demotes the first job demotes the second one identically, which is what panel C measures.

6.3 Panel C — the fix, and what it costs

Five jobs, 2000 ticks, and two independent switches. Read it a row at a time.

Row 1 — the disaster, and the virtue that causes it. The gamer takes 1780 of 2000 ticks; the two compute jobs get ten ticks each, exactly as in panel A. But look at the last column: the honest interactive jobs get 200 ticks and a mean response latency of 8.4. That is R4-old working perfectly. The rule that hands the machine to a liar is the same rule that answers the editor instantly, and it is doing both for the same reason.

Row 3 — the fix, and the mugging. Cumulative accounting drops the gamer to 216, roughly a tenth of what it was, and the compute jobs get their 1660 back. The bill is in the same last two columns: the interactive pair falls from 200 ticks to 124 — against an unloaded ceiling of 126 each, measured, so from 79% of what they want to 49% — and mean latency goes 8.4 → 32.2, a 3.8× regression on the exact metric the entire mechanism exists to deliver.

That is panel B's proof cashed out. The rule cannot separate them, so it punishes both.

Row 2 — the fix everyone reaches for first, failing twice. The periodic priority boost is the textbook answer to a starving job, so it looks like the answer here. It is not. The gamer keeps 1440 of 2000 — the exploit is barely dented, because a boost restores the gamer to the top exactly as fast as it restores anyone else, and the gamer is the one job that never leaves the top anyway. Worse, interactive latency goes from 8.4 to 18.1: the boost sweeps the two compute hogs into level 0 every 100 ticks, and they are now sitting in front of the editor.

A rule whose entire purpose is to protect low-priority jobs made the highest-priority job slower. That is worth sitting with.

Row 4 — both, and only both. The gamer gets 600. So does each compute hog — test_mlfq.py asserts the three are equal — while the interactive pair is restored to its full 200 ticks at 8.1 latency, marginally better than row 1. The gaming behaviour now earns exactly nothing.

The two rules cover each other's failure precisely. Cumulative accounting stops the exploit but cannot forgive an honest job whose small bursts have added up; the boost forgives everybody on a fixed schedule but cannot distinguish anyone. Neither alone is a scheduler you would ship, which is why real MLFQ carries both, and why OSTEP presents R4 and R5 as a pair rather than alternatives.

6.4 Panel D — a piece of folklore, measured and found inert

The exploit is usually stated as: run 99% of your quantum, then yield. The 99% sounds essential. It is worth exactly nothing:

The first column is flat. Releasing after one tick pays the same 980 as releasing after nine. Of course it does — R4-old's condition is slice_over, which is false for any burst < 10, and false is false. Nothing in the demotion rule cares how much below the quantum you stopped.

So the folklore's reason is wrong. But its advice is right, for a different reason, visible the moment a context switch costs anything: at switch=1 the same sweep runs 489 to 880, and CF5 confirms quantum − 1 is the optimum at every switch cost tested. The gamer yielding every tick pays 491 ticks of overhead out of 1000. Yielding at 9 pays 100.

You run to the last tick to amortise the context switch, not to dodge demotion. That is a better sentence than the folklore's, and it is only available because the toy has a switch parameter to turn off. With switching free the toy would quietly contradict advice that happens to be correct.

6.5 The counterfactual that flips the sign

verify_cf.py's CF2 is here rather than in §7 because it is the one a reader building their own simulator will get wrong, and it does not merely change the magnitude — it reverses the result.

Give the gamer's release a real cost — two ticks off-CPU, a syscall that actually does something — and ask whether it still wins. With preemption on wake-up, yes: 804 of 1000, because the instant its two ticks are up it takes the CPU back from whichever demoted job picked it up. Its duty cycle is 9/(9+2) = 81.8%, and it achieves 80.4%, so it is running essentially flat out.

Without preemption, the gamer wakes into level 0 and waits for the running job to finish a 40-tick slice at level 2. It gets 198 and the honest jobs get 412 and 390. The exploit becomes a self-inflicted penalty.

This was a real bug in the first prototype of this toy, and it had already produced a confident, wrong boundary claim ("a yield that costs two ticks destroys the exploit") before it was caught. The lesson generalises past this toy: in a scheduling simulator, when a waking job gets the CPU is not a detail, it is a top-three modelling decision, and it belongs in your test suite rather than your assumptions. Real schedulers preempt — that is what a priority level is for — which is why preempt=True is the default and the line carries a comment pointing here.

6.6 The other counterfactuals

Everyone games, and nobody wins. The exploit is positional, not absolute:

One gamer takes 970 of 1000. Two split it. At four, everybody is back at level 0 round-robining nine-tick slices, and the best-off job (252) is worse off than the best-off job in the all-honest run (270) — the extra releases bought nothing and cost a little. A textbook commons: the strategy is only profitable while it is rare, and it destroys its own value at scale.

How much rope does the fix give? CF6 sweeps the allotment:

The exploit never comes back. Even a hundred-fold allotment tops out at round robin (315/345/340) rather than running away, because the quantum still preempts every ten ticks regardless. A generous allotment buys the gamer more time at level 0; it does not buy exclusive possession of it. That distinction — allotment governs demotion, quantum governs preemption — is easy to lose when the two default to the same number.

Is it one lucky configuration? CF7 says no:

388 of 400 configurations put the gamer above its fair share under R4-old, median 3.95×. Under R4-new the median is 0.66× — below fair share, because a job that keeps handing the CPU back keeps going to the back of a queue it is no longer privileged in. Honesty is not rewarded by the fix either; the fix just stops rewarding the strategy.

6.7 Where the effect vanishes

Two measured boundaries. Both are ways of saying you do not have an MLFQ.

One level, and the exploit reverses.

With one queue there is no demotion, so releasing early is pure loss: the gamer goes to the back after nine ticks where the others get ten, and it ends with 315 against 345 and 340. Two levels is the entire requirement, and the third and fourth add nothing — 980 at every level count from 2 up. The exploit does not need a deep hierarchy. It needs a floor for the honest jobs to be dropped through.

Boost often enough and the two rules become the same rule.

Every boost interval from 1 to 38 produces identical CPU totals under both policies — the demo sweeps all 38 and test_mlfq.py asserts every one. They first diverge at 39. Below that, the sweep comes round before the accounting has had time to matter, so a job's level is set by the boost rather than by its behaviour, and MLFQ has degenerated into round robin with extra steps. The rule this page is about is not being consulted.

The practical form of the boundary: if your boost interval is close to your quanta, you do not have a feedback scheduler and none of this applies to you. Check the ratio before you worry about any of it. And note the corollary in the same table — at boost 100, 500 and none, R4-old leaves the gamer 800, 960 and 980. The boost never fixes the exploit at any interval where the scheduler is still an MLFQ.

6.8 The tests

test_mlfq.py pins every figure above: the 98× and the exact 40-character tick trace, the closed form at ten configurations, the 96-release equality and the {(1, False)} singleton set, all four rows of panel C to the tenth of a tick, the flat 980 column and the monotone switch=1 column, the boost boundary at every interval from 1 to 38 plus the divergence at 39, and the sign flip under preempt=False. Two conservation invariants sit underneath them: no tick is ever invented (cpu + idle + overhead == horizon at four switch costs) and the trace is exactly horizon entries long.

7. Design decisions and roads not taken

7.1 A virtual clock, and no randomness anywhere in the core

The clock is an integer advanced one tick per pass of run. There is no time.sleep, no random, no thread. Panel B's claim — that two lists of 96 tuples are equal — is not statable against a real scheduler, and neither is panel E's "identical for every interval from 1 to 38."

The one place randomness appears is CF7, which needs 400 different configurations and uses an explicit LCG seeded 20260803 rather than random, so the quartiles on this page are reproducible on any machine. _boost sorts by job id for the same reason (§5.6).

7.2 Jobs that never finish

Every job in the demo asks for 10⁹ ticks, so nothing ever completes and the runs end by hitting the horizon. This was deliberate: with jobs that finish, the headline number becomes a turnaround time, which mixes the scheduler's allocation with the accident of who was asked to do more work. An unbounded appetite makes "ticks received in 1000 ticks" a clean share of a fixed pie, and every number on this page sums to the horizon.

The cost is that classic MLFQ measurements — turnaround time, the SJF comparison, the sizes in a bag of short and long jobs — are not available. That is a different toy, and it is the one the backlog originally described.

7.3 Two policies, not four

Round robin and strict priority are both in here rather than beside it: one level is round robin (§6.7), and the gamer at level 0 with everyone else below is strict priority. A three-way comparison table of RR vs. priority vs. MLFQ would have been the obvious build, and it is a survey — the reader already knows the policies differ, and no single line in it would be load-bearing. The toy narrows to one rule inside MLFQ, and the discarded comparison shows up as the boundaries of that rule instead.

7.4 Preemption on wake-up, on by default

Covered at length in §6.5 because it flips the sign of the headline. The default is preempt=True and mlfq.py:116–121 carries a comment pointing at that section, because the alternative is not a variant, it is a different scheduler that happens to have queues.

One detail inside it: the preempted job goes back to the head of its queue (self.q[p.lvl].insert(0, p)), not the tail, and keeps its burst. It did not use its slice up — something took it away — so it is owed the rest. Sending it to the tail would make a high-priority arrival cost a low-priority job its entire accumulated slice, which is a second, unrelated unfairness.

7.5 No shortest-job-first, and no CFS

SJF is absent because it is the answer to a different question. It optimises average turnaround given knowledge of job lengths, and MLFQ exists precisely because that knowledge does not exist. It is named in §2 as the optimum you cannot implement, and that is the right role for it.

CFS, and now EEVDF, are absent because they are the actual modern answer, and including them would end the argument rather than illuminate it. Linux threw out the MLFQ heuristic family in 2007 for exactly the reason this page measures: a scheduler that infers intent from behaviour can be lied to, and every patch to the inference is another heuristic with another exploit. CFS replaced the whole idea with accounting — each task carries a vruntime, the runtime it has consumed scaled by its weight, and the scheduler simply runs whoever has the smallest one. Releasing the CPU early does not reduce your vruntime; it just means you accumulated less of it while running, which is what actually happened. There is nothing to game, because there is no inference: the "sleeper fairness" bonus that gives a waking task a small latency credit is bounded and explicitly capped, rather than being an unbounded promotion earned by behaving a certain way. EEVDF (default since 6.6) refines the latency half with an explicit deadline per task instead of a heuristic. The lesson is the one panel C reaches by measurement — count consumption, do not read behaviour — and Linux paid for it with a decade of O(1)-scheduler interactivity-heuristic bugs before adopting it.

7.6 A flat context-switch cost, present but off by default

switch bills a whole number of ticks per dispatch and defaults to 0. Panel D needs it to be non-zero to show the yield point is load-bearing, and every other panel needs it to be zero so that the CPU totals sum exactly to the horizon and the arithmetic stays checkable. Making it a parameter rather than a constant is what allows the page to say the folklore is right for the wrong reason, instead of quietly disagreeing with it.

8. What's simplified vs. the real thing

8.1 One CPU, and that is the biggest one

Everything here is a single run queue hierarchy on a single processor. Real schedulers are per-CPU run queues plus a load balancer, and that changes the problem qualitatively rather than by a constant:

• A job's priority is now one input among several to where it runs, and cache affinity often outranks it — Linux will leave a task on a busy CPU rather than migrate it to an idle one across a NUMA node.
• Gaming the scheduler on one core does not starve jobs on another, so the exploit's blast radius is one CPU's worth, not the machine's.
• Load balancing periodically reshuffles queues, which acts as an irregular, unintentional priority boost, and would smear panel E's clean boundary at 39.
• Group scheduling (cgroups, autogroup) puts a second hierarchy above this one, so a container's total share is capped no matter what its threads do internally. That is the production answer to a gaming tenant, and it works by not trusting per-thread accounting at all.

8.2 The other simplifications

• Blocking takes a fixed number of ticks. Job.block is a constant, so a device never queues, never varies, and never fails. Real I/O latency is a long-tailed distribution, and the tail is what makes interactive scheduling hard: a job that usually returns in 1ms and sometimes in 200ms will be misclassified by any accounting scheme built for the mean.
• No priorities, nice values or weights. Every job is equally entitled. Real schedulers have a static priority alongside the dynamic one, and most production "unfairness" is somebody's nice -20, not a clever exploit.
• The timer never misses. slice_over is exact because the tick loop is exact. Real quanta are enforced by an interrupt that can be delayed by a non-preemptible kernel section, and a job holding a spinlock at the moment its slice expires gets a little extra time for free.
• No kernel threads, interrupts or softirqs. Real machines spend a measurable fraction of every second on work that belongs to no job in the run queue and that preempts all of them.
• Nothing arrives or leaves. Jobs are eternal (§7.2). A real machine's scheduler spends most of its intelligence on the churn of short-lived processes, where a job may be demoted based on a history it will never live long enough to escape.
• The scheduler itself is free. Picking a job costs nothing but the optional switch ticks. Choosing among thousands of runnable tasks is why CFS uses a red-black tree keyed on vruntime and why the pre-2007 scheduler was called "the O(1) scheduler" — the data structure was the headline feature.
• A release is instantaneous and always voluntary in the same way. There is one way to give up the CPU here. Real jobs block on futexes, page faults, network sockets and pipes, and a scheduler treats several of those differently.

9. Check yourself

10. Further reading

• Operating Systems: Three Easy Pieces, ch. 8 — Scheduling: The Multi-Level Feedback Queue — Arpaci-Dusseau & Arpaci-Dusseau. The direct source for the rule numbering used throughout this page. §8.3 "Attempt #2: The Priority Boost" and §8.4 "Attempt #3: Better Accounting" are panel C's rows 2 and 3, and the chapter's figure 8.7 is the picture this toy turns into numbers. Free, and the clearest 20 pages on the subject.
• An Experimental Time-Sharing System — Corbató, Merwin-Daggett & Daley, SJCC 1962, scanned and transcribed by Corbató himself. The CTSS scheduler, and the origin of the multi-level feedback queue: read the "scheduling algorithm" section, where a process at level l gets 2^l quanta and is demoted when it uses them all. Worth it for how much of the modern design is already there in 1962, and how frankly it admits to guessing.
• Multilevel feedback queue — the short version, including the "gaming the scheduler" problem stated in one paragraph. Useful as a check that this page's framing is the standard one before it departs from it in §6.2.
• CFS Scheduler — Linux kernel documentation — the design document for the scheduler that replaced this whole family of heuristics. The section on vruntime is §7.5's argument in the authors' own words, and the note about "sleeper fairness" is where they explain the one bounded concession they make to interactivity.
• EEVDF Scheduler — Linux kernel documentation — what CFS became in 6.6. Eligible-time plus an explicit per-task virtual deadline, which is the latency half of the problem handled by construction rather than by heuristic.
• Completing the EEVDF scheduler — LWN, 2024. Jonathan Corbet on what EEVDF fixes and what it still argues about, including latency nice. The best available account of why this problem is still open in production 60 years after CTSS.
• The Linux Scheduler: a Decade of Wasted Cores — Lozi et al., EuroSys 2016. Four bugs in Linux's multicore load balancing that left cores idle while runnable threads waited. The paper §8.1 exists to point at: everything on this page is single-CPU, and the multicore problem is both harder and more consequential.
• sched_yield(2) — the syscall the gamer is calling, and a man page unusually blunt about it: "Avoid calling sched_yield() unnecessarily or inappropriately... it may end up wasting CPU time." Check yourself question 5 is this page in practice.