"""A multi-level feedback queue, and the one rule that decides a job's priority. MLFQ is the scheduler design behind Solaris, FreeBSD's ULE, Windows NT and every classic Unix: several run queues at descending priorities, and a rule that moves a job between them based on how it behaves. The rules, numbered as in OSTEP chapter 8: R1/R2 the highest-priority runnable job runs; ties round-robin. R3 every job enters at the top level. R4 a job is demoted when it "uses too much CPU" -- and the whole toy is about what that phrase is allowed to mean: DEMOTE_BURST it used up a whole time slice without giving the CPU up voluntarily. (the original rule) DEMOTE_ALLOT it used up its cumulative allotment at this level, summed across however many slices. (the fix) R5 every `boost` ticks, every job is moved back to the top level. Time is an integer virtual clock. Nothing sleeps, nothing is random, and the scheduler never inspects a job's future -- it sees only what a real one sees: how many ticks the job just used, and whether the timer had to take the CPU away. `Job.block` is the fact it cannot see, and that is the point. """ DEMOTE_BURST = "burst" # R4, original: demote only on slice exhaustion DEMOTE_ALLOT = "allot" # R4, fixed: demote on cumulative time at a level 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") def __init__(self, jid, arrival, service, yield_after=None, block=0): self.jid = jid self.arrival = arrival self.service = service # total CPU ticks the job wants self.yield_after = yield_after # ticks into a slice at which it releases self.block = block # ticks spent off-CPU per release self.lvl = 0 # which queue it is in self.burst = 0 # ticks used in the current slice self.allot = 0 # ticks used at this level, all slices self.cpu = 0 # total CPU ticks received self.state = "new" self.wake = 0 # tick at which a block expires self.ready_at = None # tick it last became runnable self.lat = [] # response latencies: runnable -> on CPU self.disp = [] # (burst, slice_expired, demoted) per release def __repr__(self): return "J%d(cpu=%d,lvl=%d)" % (self.jid, self.cpu, self.lvl) class MLFQ: """The scheduler. `run(horizon)` advances the clock one tick at a time.""" 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) self.boost = boost self.policy = policy self.switch = switch # ticks burned per context switch self.preempt = preempt self.q = [[] for _ in self.quanta] self.blocked = [] self.clock = 0 self.cur = None self.switch_left = 0 self.switches = 0 self.overhead = 0 # ticks lost to context switching self.preempts = 0 self.idle = 0 self.trace = [] # (tick, jid | -1 switch | None idle, lvl) def _enq(self, j): j.state = "ready" self.q[j.lvl].append(j) def _pick(self): for lvl in range(len(self.q)): if self.q[lvl]: return self.q[lvl].pop(0) return None def run(self, horizon): """Advance the clock to `horizon`, one tick per pass.""" while self.clock < horizon: t = self.clock for j in self.jobs: if j.state == "new" and j.arrival <= t: j.lvl = 0 j.burst = j.allot = 0 j.ready_at = t self._enq(j) for j in list(self.blocked): if j.wake <= t: self.blocked.remove(j) j.ready_at = t # the device answered self._enq(j) if self.boost and t > 0 and t % self.boost == 0: self._boost() # R1, the part that makes the top level worth occupying: a job # that becomes runnable at a strictly higher priority takes the # CPU at once. The victim goes back to the HEAD of its queue with # its slice intact -- it did not use anything up, so it is owed # the rest. Take this away and the whole result changes sign; see # the commentary, section 7.4. if self.preempt and self.cur is not None and self.switch_left == 0: best = next((l for l in range(len(self.q)) if self.q[l]), None) if best is not None and best < self.cur.lvl: p = self.cur p.state = "ready" self.q[p.lvl].insert(0, p) self.cur = None self.preempts += 1 if self.cur is None and self.switch_left == 0: nxt = self._pick() if nxt is not None: nxt.state = "run" self.cur = nxt self.switches += 1 self.switch_left = self.switch if self.switch_left > 0: # paying for the switch self.switch_left -= 1 self.overhead += 1 self.trace.append((t, -1, -1)) self.clock += 1 continue if self.cur is None: # nothing runnable self.idle += 1 self.trace.append((t, None, None)) self.clock += 1 continue j = self.cur if j.ready_at is not None: j.lat.append(t - j.ready_at) j.ready_at = None j.cpu += 1 j.burst += 1 j.allot += 1 self.trace.append((t, j.jid, j.lvl)) self.clock += 1 if j.cpu >= j.service: j.state = "done" self.cur = None continue 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 # ---- 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 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) return self.clock 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: pending.append(self.cur) self.cur = None self.switch_left = 0 for j in self.blocked: j.lvl = 0 j.burst = j.allot = 0 pending.sort(key=lambda j: j.jid) for j in pending: j.lvl = 0 j.burst = j.allot = 0 self._enq(j)