Part 4 of 7 · 2 min read
Stride
In plain words: A group shares a bicycle, and each rider writes a score on the board each time they ride. The rider with the lowest score goes next, and after riding, the rider's score rises by an amount that is small for a rider with a high share and large for a rider with a low share. The analogy stops in one place: the riders choose a ride length, while in a scheduler the quantum is fixed.
Stride scheduling is the deterministic version of lottery. Each process gets a stride, a number inversely proportional to its tickets: stride = a large constant ÷ tickets. It also has a pass value that starts at 0. At each decision, the scheduler runs the process with the lowest pass for one quantum, then adds its stride to its pass. Ties go to the first name in the list.
Take the same tickets and a constant of 1,000: A (100 tickets) has a stride of 10, B (50) has 20, C (250) has 4.
| Pick | Process | Pass before | Pass after |
|---|---|---|---|
| 1 | A | 0 | 10 |
| 2 | B | 0 | 20 |
| 3 | C | 0 | 4 |
| 4 | C | 4 | 8 |
| 5 | C | 8 | 12 |
| 6 | A | 10 | 20 |
| 7 | C | 12 | 16 |
| 8 | C | 16 | 20 |
| 9 | A | 20 | 30 |
| 10 | B | 20 | 40 |
In 400 picks, a run of this method gave exactly A 100, B 50 and C 250, the shares of the tickets, with no luck. Unlike a lottery, it keeps one number for each process, and a new process needs a sensible starting pass (neither 0, which would let it monopolise the processor, nor huge).
Stride scheduling
Stride scheduling is a deterministic proportional-share policy that gives each process a stride inversely proportional to its tickets and a pass counter, runs the process with the lowest pass, and then adds the stride to that pass.
Example: a process with a stride of 4 is picked 2.5 times as often as one with a stride of 10, because it advances more slowly.
Check yourself: 1. Compute the stride of a process with 125 tickets for a constant of 1,000. 2. Why is stride scheduling exact where lottery is only approximate? 3. What problem arises for a process that joins late?