§9.1–9.3Tickets … Implementation

Chapters 7 and 8 optimized turnaround and response. This chapter wants something else entirely: guarantee each job a slice of the pie — proportional-share proportional share Scheduling that guarantees each job a percentage of the CPU rather than optimizing turnaround/response (a.k.a. fair-share). defined in ch. 9 — open in glossary (fair-share) scheduling. The early classic is Waldspurger and Weihl’s lottery scheduling (1994), and its core idea fits in a sentence: every so often, hold a lottery; jobs that deserve more CPU get more chances to win.

9.1 Basic Concept: Tickets Represent Your Share

Everything rests on the ticket ticket A token representing a share of a resource; percent of tickets held = share received. Reusable far beyond CPUs (e.g., hypervisor memory). defined in ch. 9 — open in glossary : a token representing a share of a resource. Hold 75 of the 100 tickets in play, and you should receive 75% of the CPU. Lottery scheduling lottery scheduling Every slice, draw a random winning ticket; the holder runs. Probabilistically proportional, minimal state, no global bookkeeping. defined in ch. 9 — open in glossary delivers that share probabilistically: every time slice, the scheduler draws a winning ticket (0 to total−1) and runs its holder:

Randomness gives probabilistic correctness — no guarantee on any short window (the book’s 20-draw example handed B 20% instead of 25%), but the law of large numbers pulls long runs toward target.

9.2 Ticket Mechanisms

Tickets come with a small toolkit:

• Ticket transfer ticket transfer Temporarily handing your tickets to another process — e.g., a client boosting the server working on its request. defined in ch. 9 — open in glossary : temporarily hand your tickets to another process — the classic case is a client passing tickets to a server so the server runs fast while doing the client’s work, then hands them back.
• Ticket inflation ticket inflation A process raising/lowering its own ticket count — sensible only among mutually trusting processes. defined in ch. 9 — open in glossary : a process boosts (or trims) its own ticket count. Nonsense among competitors — a greedy process could grab the machine — but in a group of mutually trusting processes, it’s a lightweight way to say “I need more CPU right now” without any communication.

9.3 Implementation

The most amazing part: the whole scheduler needs a random number generator, a list of processes, and the total ticket count. To decide, draw winner in [0, total), then walk the list accumulating tickets until the counter exceeds the winner:

// counter: used to track if we've found the winner yet
int counter = 0;

// winner: use some call to a random number generator to
//         get a value, between 0 and the total # of tickets
int winner = getrandom(0, totaltickets);

// current: use this to walk through the list of jobs
node_t *current = head;
while (current) {
    counter = counter + current->tickets;
    if (counter > winner)
        break; // found the winner
    current = current->next;
}
// 'current' is the winner: schedule it...

Figure 9.1: Lottery Scheduling Decision Code

With the list A(100) → B(50) → C(250) and winning ticket 300: counter hits 100 (A — keep going), 150 (B — keep going), 400 (> 300 — stop): C wins. One micro-optimization: keep the list sorted by descending tickets — correctness is unaffected (any order works), but the biggest holders are found in the fewest iterations. Here’s that exact workload, live:

Simple mechanism, three knobs on top of it, and an implementation that fits on an index card. Next: what randomness costs (short-run unfairness), and the deterministic alternatives — stride scheduling and Linux’s CFS.