§8.3–8.6Attempt #2: The Priority Boost … MLFQ: Summary

Part I OSTEP pp. 83–86 · ~6 min read

  • priority boost
  • allotment
  • voo-doo constant
  • advice

Attempt #1 left three holes: starvation, gaming, and stranded phase-changers. Two rule changes close all three.

8.3 Attempt #2: The Priority Boost

The simple idea: periodically throw everyone back to the top.

ATTEMPT #2

  • Rule 5: After some time period S, move all the jobs in the system to the topmost queue.

One rule, two problems solved. No starvation: a job in the top queue shares via round robin (Rule 2), so everyone eventually gets service. And phase changes handled: a CPU-bound job that has turned interactive gets its priority boost and is re-judged on current behavior. Try it:

Figure 8.5: starvation — and the boost that cures it (set "boost S" to 50 and watch A reappear)
Q2A @ Q2: 0–10AB @ Q2: 100–101C @ Q2: 101–102B @ Q2: 102–103C @ Q2: 103–104B @ Q2: 104–105C @ Q2: 105–106B @ Q2: 106–107C @ Q2: 107–108B @ Q2: 108–109C @ Q2: 109–110B @ Q2: 110–111C @ Q2: 111–112B @ Q2: 112–113C @ Q2: 113–114B @ Q2: 114–115C @ Q2: 115–116B @ Q2: 116–117C @ Q2: 117–118B @ Q2: 118–119C @ Q2: 119–120B @ Q2: 120–121C @ Q2: 121–122B @ Q2: 122–123C @ Q2: 123–124B @ Q2: 124–125C @ Q2: 125–126B @ Q2: 126–127C @ Q2: 127–128B @ Q2: 128–129C @ Q2: 129–130B @ Q2: 130–131C @ Q2: 131–132B @ Q2: 132–133C @ Q2: 133–134B @ Q2: 134–135C @ Q2: 135–136B @ Q2: 136–137C @ Q2: 137–138B @ Q2: 138–139C @ Q2: 139–140B @ Q2: 140–141C @ Q2: 141–142B @ Q2: 142–143C @ Q2: 143–144B @ Q2: 144–145C @ Q2: 145–146B @ Q2: 146–147C @ Q2: 147–148B @ Q2: 148–149C @ Q2: 149–150B @ Q2: 150–151C @ Q2: 151–152B @ Q2: 152–153C @ Q2: 153–154B @ Q2: 154–155C @ Q2: 155–156B @ Q2: 156–157C @ Q2: 157–158B @ Q2: 158–159C @ Q2: 159–160B @ Q2: 160–161C @ Q2: 161–162B @ Q2: 162–163C @ Q2: 163–164B @ Q2: 164–165C @ Q2: 165–166B @ Q2: 166–167C @ Q2: 167–168B @ Q2: 168–169C @ Q2: 169–170B @ Q2: 170–171C @ Q2: 171–172B @ Q2: 172–173C @ Q2: 173–174B @ Q2: 174–175C @ Q2: 175–176B @ Q2: 176–177C @ Q2: 177–178B @ Q2: 178–179C @ Q2: 179–180B @ Q2: 180–181C @ Q2: 181–182B @ Q2: 182–183C @ Q2: 183–184B @ Q2: 184–185C @ Q2: 185–186B @ Q2: 186–187C @ Q2: 187–188B @ Q2: 188–189C @ Q2: 189–190B @ Q2: 190–191C @ Q2: 191–192B @ Q2: 192–193C @ Q2: 193–194B @ Q2: 194–195C @ Q2: 195–196B @ Q2: 196–197C @ Q2: 197–198B @ Q2: 198–199C @ Q2: 199–200B @ Q2: 200–201C @ Q2: 201–202B @ Q2: 202–203C @ Q2: 203–204B @ Q2: 204–205C @ Q2: 205–206B @ Q2: 206–207C @ Q2: 207–208B @ Q2: 208–209C @ Q2: 209–210B @ Q2: 210–211C @ Q2: 211–212B @ Q2: 212–213C @ Q2: 213–214B @ Q2: 214–215C @ Q2: 215–216B @ Q2: 216–217C @ Q2: 217–218B @ Q2: 218–219C @ Q2: 219–220B @ Q2: 220–221C @ Q2: 221–222B @ Q2: 222–223C @ Q2: 223–224B @ Q2: 224–225C @ Q2: 225–226B @ Q2: 226–227C @ Q2: 227–228B @ Q2: 228–229C @ Q2: 229–230B @ Q2: 230–231C @ Q2: 231–232B @ Q2: 232–233C @ Q2: 233–234B @ Q2: 234–235C @ Q2: 235–236B @ Q2: 236–237C @ Q2: 237–238B @ Q2: 238–239C @ Q2: 239–240B @ Q2: 240–241C @ Q2: 241–242B @ Q2: 242–243C @ Q2: 243–244B @ Q2: 244–245C @ Q2: 245–246B @ Q2: 246–247C @ Q2: 247–248B @ Q2: 248–249C @ Q2: 249–250B @ Q2: 250–251C @ Q2: 251–252B @ Q2: 252–253C @ Q2: 253–254B @ Q2: 254–255C @ Q2: 255–256B @ Q2: 256–257C @ Q2: 257–258B @ Q2: 258–259C @ Q2: 259–260B @ Q2: 260–261C @ Q2: 261–262B @ Q2: 262–263C @ Q2: 263–264B @ Q2: 264–265C @ Q2: 265–266B @ Q2: 266–267C @ Q2: 267–268B @ Q2: 268–269C @ Q2: 269–270B @ Q2: 270–271C @ Q2: 271–272B @ Q2: 272–273C @ Q2: 273–274B @ Q2: 274–275C @ Q2: 275–276B @ Q2: 276–277C @ Q2: 277–278B @ Q2: 278–279C @ Q2: 279–280B @ Q2: 280–281C @ Q2: 281–282B @ Q2: 282–283C @ Q2: 283–284B @ Q2: 284–285C @ Q2: 285–286B @ Q2: 286–287C @ Q2: 287–288B @ Q2: 288–289C @ Q2: 289–290B @ Q2: 290–291C @ Q2: 291–292B @ Q2: 292–293C @ Q2: 293–294B @ Q2: 294–295C @ Q2: 295–296B @ Q2: 296–297C @ Q2: 297–298B @ Q2: 298–299C @ Q2: 299–300Q1A @ Q1: 10–20AQ0A @ Q0: 20–100AA @ Q0: 300–400ADiskB I/O: 100–298C I/O: 298–299060120180240300360
jobarrivalruntimeturnaroundresponse
A02004000
B1001001990
C1001002001
average266.330.33

With boost off, interactive B and C (arriving at t=100) alternate at Q2 forever, and A — long since sunk to Q0 — receives exactly 0% of the CPU from t=100 on: starvation. Set boost S to 50: every 50 ms A is thrown back to the top queue and gets real slices (~20% share). Rule 5 in action.

Of course, Rule 5 introduces a knob: what should S be? Set it too high and long-running jobs still starve; too low and interactive jobs lose their edge.

Tip: Avoid voo-doo constants (Ousterhout’s Law)

John Ousterhout called values like S voo-doo constants — they seem to require black magic to set correctly. Avoid them when possible; unfortunately, as here, it often isn’t. The frequent result: a config file full of defaults that a seasoned admin could tweak — and nobody ever does. We’re left hoping the defaults work in the field.

8.4 Attempt #3: Better Accounting

Now the gamers. The culprits are Rules 4a/4b themselves: they forget how much slice a job used whenever it relinquishes the CPU. The fix is memory — track the allotment a job has consumed at its level, across however many bursts:

ATTEMPT #3 — 4a and 4b become one rule

  • Rule 4: Once a job uses up its time allotment at a given level (regardless of how many times it has given up the CPU), its priority is reduced (it moves down one queue).
Figure 8.6: gaming the scheduler — flip accounting from Rules 4a+4b to Rule 4
Q2G @ Q2: 0–9GH @ Q2: 9–19HG @ Q2: 19–28GG @ Q2: 29–38GG @ Q2: 39–48GG @ Q2: 49–58GG @ Q2: 59–68GG @ Q2: 69–78GG @ Q2: 79–88GG @ Q2: 89–98GG @ Q2: 99–108GG @ Q2: 109–118GG @ Q2: 119–120Q1H @ Q1: 28–29H @ Q1: 38–39H @ Q1: 48–49H @ Q1: 58–59H @ Q1: 68–69H @ Q1: 78–79H @ Q1: 88–89H @ Q1: 98–99H @ Q1: 108–109H @ Q1: 118–119H @ Q1: 120–130HQ0H @ Q0: 130–200HDiskG I/O: 8–10G I/O: 27–29G I/O: 37–39G I/O: 47–49G I/O: 57–59G I/O: 67–69G I/O: 77–79G I/O: 87–89G I/O: 97–99G I/O: 107–109G I/O: 117–1190306090120150180
jobarrivalruntimeturnaroundresponse
G01001200
H01002009
average160.004.50

G is the gamer: it computes 9 ms of every 10 ms slice, then issues a junk I/O. Under Rules 4a+4b it stays at Q2 and hogs ~80–90% of the CPU while honest H sinks. Switch accounting to Rule 4: G's allotment is counted across bursts, it descends like everyone else, and the CPU splits fairly.

Whether the allotment is burned in one long run or a hundred sneaky 99%-bursts, the outcome is the same: down you go. The 99%-and-I/O attack buys nothing.

8.5 Tuning MLFQ And Other Issues

How many queues? What slice per queue? How often to boost? There are no easy answers — only experience with workloads and tuning. A few patterns from real systems:

Varying time slices per level. High-priority queues hold interactive jobs — short slices (≤10 ms) and quick alternation make sense there. Low queues hold CPU-bound work — long slices (100s of ms) amortize switching:

Figure 8.7: lower priority, longer quanta (slices 10 / 20 / 40 ms)
AarrrunBarrrun
Q2A @ Q2: 0–10AB @ Q2: 10–20BQ1A @ Q1: 20–40AB @ Q1: 40–60BQ0A @ Q0: 60–100AB @ Q0: 100–140BA @ Q0: 140–170AB @ Q0: 170–200B0306090120150180
jobarrivalruntimeturnaroundresponse
A01001700
B010020010
average185.005.00

Both jobs take 10 ms turns at Q2, 20 ms turns at Q1, then settle into long 40 ms turns at Q0. High queues switch fast (interactive feel); low queues switch rarely (amortized batch work) — most real MLFQs are tuned this way.

Real implementations. Solaris’s Time-Sharing class (TS) is table-driven: ~60 queues, slices growing from 20 ms (high) to a few hundred ms (low), boosts about every second — and an administrator can edit the table. FreeBSD (4.3) took the formula route instead: decay-usage scheduling computes priority from recent CPU usage, decayed over time — the decay is the boost, delivered continuously. Other wrinkles: many systems reserve the very top priorities for OS work (user jobs can never reach them), and some accept user advice — nice nudges a job’s priority up or down from the command line.

Tip: Use advice where possible

The OS rarely knows what’s best for every process, so interfaces that let users and applications drop hints are widely useful: the scheduler’s nice, the memory manager’s madvise, file-system informed prefetching. The OS may ignore the hint — that’s why it’s called advice — but a good hint often makes a better decision.

8.6 MLFQ: Summary

The refined rule set, complete:

MLFQ — THE FIVE RULES

  • Rule 1: If Priority(A) > Priority(B), A runs (B doesn’t).
  • Rule 2: If Priority(A) = Priority(B), A & B run in round-robin fashion using the time slice of the given queue.
  • Rule 3: When a job enters the system, it is placed at the highest priority.
  • Rule 4: Once a job uses up its time allotment at a given level (regardless of how many times it has given up the CPU), its priority is reduced.
  • Rule 5: After some time period S, move all the jobs in the system to the topmost queue.

Why MLFQ matters: it demands no a priori knowledge — it observes and prioritizes accordingly, getting the best of both worlds: near-SJF/STCF performance for short interactive work, fairness and progress for long-running CPU-bound work. That’s why forms of MLFQ are the base scheduler in BSD UNIX derivatives, Solaris, and Windows NT and its successors. Multiple levels of queues; feedback sets the priority. History is its guide.

Homework: mlfq.py

The simulator reproduces everything on this page: rebuild the chapter’s figures, configure it to behave as pure round robin, craft a two-job workload that games old Rules 4a/4b (the -S flag) for 99% of the CPU, and compute how often to boost (-B) so a starving job is guaranteed 5% of the CPU. Also try -I: which end of the queue should a job rejoin after I/O? Get it at ostep-homework.

Check yourself

1.Rule 5 (boost everyone to the top every S) solves two problems at once. Which two?

2.Why does the book call the boost period S a 'voo-doo constant'?

3.How exactly does rewritten Rule 4 defeat the 99%-of-a-slice-then-junk-I/O attack?

4.Why do real MLFQs give LOW-priority queues longer time slices (e.g., 10 ms up top, 100s of ms at the bottom)?

5.Solaris tunes MLFQ with an editable 60-queue table; FreeBSD 4.3 used a decay-usage formula instead. What does the decay naturally provide?

5 questions