Part 2 of 2 · Fair Scheduling Across Queues with Deficit-Weighted Round Robin (DWRR)

Reviewing a Fair Scheduler: From Promises to Evidence

What a scheduler promises, what its tests demonstrate, and what still needs an argument.

By ·10 min read

A scheduler can return every item exactly once and still be unfair. It can even return the right items in the wrong order, and a test that counts them will congratulate it.

Taking Turns describes deficit-weighted round robin. Here, let’s look at the Go implementation, dwrr. What can a caller depend on, and what would convince us that the code does it?

Each queue gets credit, its quantum, at the start of a visit. It spends that credit on items from the front until it can’t afford the next one. The scheduler selects and removes work; it doesn’t run it. Fairness is about declared cost, not item counts, runtime, or completion order. A caller can undo fair selection with an unfair worker pool.

The documented behavior and all source links below are pinned to commit 492dc7e3e54f430212f483a728957ff7f151b4a5. This reviews the fixed-quantum implementation before the callable-policy change released in v0.11.0; the current Go tool documentation covers that different API. The review stays with this revision so its assertions and source links describe the same code.

What are we checking?

“Deficit weighted round robin” doesn’t tell a caller what happens when a batch ends halfway through a turn. The README does. These twenty-four acceptance criteria collect its promises; they aren’t a claim that every case has a test. Weight means the API’s quantum, changed with SetQuantum. A visit is a queue’s turn to spend credit.

Queues and inputs

  1. NewDWRR creates the requested number of empty queues, each with weight 1. The zero value is unsupported; use the constructor.
  2. Queue numbers start at 0 and stay stable while their queues exist. AddQueue appends an empty queue with weight 1. RemoveQueue removes only the last queue and its contents; a later addition may reuse that number.
  3. Removing a queue leaves the scheduler ready to continue. Removing the queue being visited ends that visit. Removing from no queues does nothing.
  4. Item costs and queue weights must be from 1 through 2^63−1. Invalid costs return ErrZeroCost or ErrCostTooLarge; invalid weights return ErrZeroQuantum or ErrQuantumTooLarge.
  5. A rejected batch or weight change leaves the scheduler unchanged: no part of an invalid batch is accepted.
  6. Invalid queue numbers panic. SetQuantum checks the queue number before validating the weight.

Scheduling

  1. Visits cycle through queues in queue-number order. Each visit starts with one grant of credit equal to that queue’s weight.
  2. Within a visit, the scheduler serves the front item only if the queue can afford it, then subtracts its cost. An unaffordable front item ends the visit; cheaper items behind it cannot pass it.
  3. Unused credit carries forward while a queue has items. An empty queue’s credit resets to zero.
  4. With stable weights and continuously backlogged queues, fairness concerns weighted shares of declared cost, not item counts, runtime, or completion order.
  5. Skipping whole rounds that would serve nothing must preserve service order and use exact arithmetic without overflow.

Retrieving and changing work

  1. Take(n) returns up to n items in service order, each with its source queue, payload, and accepted cost. It returns fewer only when queued work runs out.
  2. If the retrieval limit interrupts a visit, the next call continues at the same position with the remaining credit and no new grant, absent intervening mutations.
  3. Take(0) changes nothing and returns a non-nil, empty slice. Retrieval with no queues or no work also returns a non-nil, empty slice, even if empty queues still exist. A negative limit panics.
  4. Enqueue appends in FIFO order. Items added to the queue being visited join that visit without another credit grant. Adding a queue also preserves the visit in progress.
  5. Changing a weight preserves saved credit and any paused visit. The next grant uses the new weight; setting the same weight changes nothing.
  6. RemoveHead withdraws the front item without scheduling it, returning the item and true, or the zero item and false if empty. Credit and visit state survive if items remain; emptying the queue resets its credit and ends its visit.
  7. DrainQueue returns the queue’s items in FIFO order, resets its credit, and ends its active visit.

Ownership and memory

  1. Enqueue copies item records, not the objects their payloads may point to. Later edits to the caller’s input slice cannot change accepted costs.
  2. Returned records don’t share queue storage. Payloads remain shallow copies, so pointed-to objects may still be shared.
  3. Removed items’ references are cleared from retained storage slots. Emptying a queue through Take or RemoveHead keeps its remaining storage for reuse; draining or removing a queue drops the scheduler’s reference to its storage.

Concurrent use and responsibilities

  1. A mutex protects scheduler state. Take(0) returns, and a negative Take panics, before acquiring that lock.
  2. Take doesn’t wait for future arrivals, though it may wait for the lock.
  3. Callers run the selected work and control its completion order; they also synchronize access to shared payloads. Don’t copy the scheduler after first use.

A batch boundary is not a scheduling boundary

Give queue 0 a quantum of 3 and two cost-1 items. Take(1) returns its first item, leaving credit 2. Whose turn is it now?

Still queue 0’s. The caller asked for one item, not for the queue to give up its turn. The next call must continue without another grant (AC13). Advancing to queue 1 would cut the turn short; granting queue 0 another quantum would give it credit it hasn’t earned.

The code keeps two facts separately: cursor identifies the queue, and active records whether its visit has received credit. Take grants credit only when active is false. Reaching the output limit exits the loop without ending the visit.

The batch-equivalence test compares one Take(17) with seventeen Take(1) calls. It checks the records and the state left behind, including every queue’s credit. The items can agree while the credit left for the next call differs. This fixture uses quantum 1, though. The mutation test supplies the quantum-3 example above. An appended item joins the unfinished visit, and adding a queue doesn’t displace it. Another case changes the quantum from 3 to 1 while paused: queue 0 must still return its second item before queue 1 gets a turn.

SetQuantum changes the weight, not the savings. That distinction also prevents a less obvious failure. In TestSetQuantumDoesNotStarve, one queue has a cost-10 head while another has 1,000 cost-1 items. Before every single-item retrieval, the waiting queue’s quantum alternates between 3 and 4. If each change erased its credit, it would never save 10. The busy queue would keep producing results while the expensive item waited.

The test requires that expensive item exactly once across 1,000 retrievals. It catches this starvation bug, not every possible way to starve a queue. The new quantum applies at the next grant, not when a visit resumes.

Even asking for nothing has a consequence worth checking: Take(0) must leave the paused visit alone.

Skip the waiting, not the winner

If a head costs a billion and its quantum is 1, visiting it a billion times is faithful but not very helpful. We can skip rounds that serve nothing, provided we don’t change who goes next (AC11).

Consider two queues with quantum 3. If both heads cost 10, both have credit 9 after three rounds. On the fourth, queue 0 gets to 12 first and serves its item. Change its cost to 13, and it can’t afford that fourth-round item. Queue 1 wins instead. The tie and near-tie test checks both cases, including leftover credit and cursor. A three-queue case puts the first affordable head last and requires order 2, 1, 0.

The shortcut in fastForward stops short of making any head affordable. Let gap be the head’s cost minus its current credit:

go
1cycles := (gap - 1) / quantum

Suppose the gap is 6 and the quantum is 3. Skipping two rounds would make the head affordable. Subtracting one allows only one round to disappear. The next ordinary visit must decide whether this queue goes first.

The code takes the smallest safe skip across all waiting queues, then gives each skip * itsQuantum credit. They receive the same number of rounds, not the same amount of credit. Every head is still unaffordable afterward. Visits resume at the existing cursor to settle the order, including ties.

The same calculation bounds the arithmetic: skip * quantum <= gap - 1 for every queue. The multiplication fits, and the resulting credit stays below a cost no greater than 2^63−1.

An ordinary grant can go much higher. Outside a visit, credit is at most MaxCost−1: a visit ends below its head’s cost, and emptying resets credit. Removing a head may expose a cheaper one but adds no credit. The next grant adds at most MaxQuantum, giving:

text
1(MaxCost − 1) + MaxQuantum = 2^64 − 3

That fits in uint64, with little room to spare. The peak-credit test gets there by saving credit, raising the quantum, and removing an expensive head to expose a cost-1 item. It observes 2^64−4 after serving that item. The peak is one higher; the assertion doesn’t observe it directly.

The arbitrary-precision test checks large numbers, but not large skips. Those aren’t the same test.

TestExtremeDifferentialBigReference compares results and credit with an arbitrary-precision scheduler. Its quanta are so large that a head needs at most two grants. The large-skip test instead uses quanta 1 and 2 near MaxCost, checking who wins and how much the other queue has saved.

Removing an item is not enough to release it

A queue can look empty while its backing array still holds pointers to everything it served. The output tests won’t notice. The garbage collector will.

Enqueue validates the whole batch and copies its records. The cost-copying test changes the caller’s costs to 0 and 100 after enqueueing, then requires the accepted costs, 2 and 1. But copying a record doesn’t copy everything it points to. If T contains a pointer, both records still refer to the same object. A private result slice isn’t permission to mutate shared payloads without synchronization.

The storage question is different (AC21). After returning an item, does the scheduler still hold its payload reference?

The retained-slot test saves a view of the original backing array before removing pointer-valued items through Take and RemoveHead. It checks that the slots contain zero item records. Saving that original view is the interesting part: after reslicing, the queue’s current view no longer includes the discarded prefix. Inspecting only that view could miss the very references we’re looking for.

Both popHead and the removal path in Take clear a slot before reslicing. Reslicing changes what the queue exposes; clearing erases what the array still holds. On the last removal, the queue keeps a zero-length slice with its remaining capacity.

Reusing storage and releasing payload references aren’t opposites. The array can stay; its old contents shouldn’t.

The reuse test checks repeated enqueue-and-remove operations with single-item queues. RemoveHead needs no allocation; Take is allowed one for its result. This isn’t a promise that every workload will reuse all its original capacity.

DrainQueue does something else: it copies the result, clears the queue, and sets its slice to nil. The drain-storage test requires nil even when a previous removal already emptied the queue. Dropping the scheduler’s array reference doesn’t promise immediate garbage collection, either. Returned items and other callers may still have references.

Appendix: where else to look

The remaining checks are worth reading alongside the code:

These checks aren’t an exhaustive correctness proof. Agreement with a reference can’t repair a promise both implementations misunderstood.

A scheduler can return every item and still get the turns wrong. That’s why this review follows the credit across calls, through skipped rounds, and into the next grant. And returning the right item still leaves one more question: did the queue let go of it?

See also