Random Scheduling, and All Six Compared
Chapter Ninety-Six
Syllabus topic Module 2, MU prints RSS among the disk scheduling algorithms
Pages 386 to 388 of 452
In one line
Serving the queue in a random order is the baseline every other algorithm has to beat, and on the standard queue it beats FCFS.
What RSS is
Random scheduling, which MU writes as RSS: pick a waiting request at random and serve it, then pick again.
Nobody builds it. It is in the list for two reasons, and both are worth writing in an answer.
| Why it is taught | What it gives |
|---|---|
| a baseline | an algorithm that does not beat a random order is doing nothing useful |
| an analysis tool | the average, the best and the worst possible orders bound what any algorithm can do |
Every possible order of the standard queue
The queue of Chapter ninety four and Chapter ninety five: head at 53, cylinders 0 to 199, and eight requests. Eight requests can be served in
orders = 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 40,320
40,320 different orders, and sim/disk.py works out the head movement of every one of them.
| Over all 40,320 orders | Total head movement |
|---|---|
| the best order | 208 |
| the mean, which is what RSS gives on average | 504.5 |
| the worst order | 702 |
208 is therefore the optimum, not merely a better order than SSTF's. Chapter ninety four showed the order 37, 14, 65, 67, 98, 122, 124, 183 costing 16 + 23 + 169 = 208; the enumeration proves no order does better, because every order was tried.
And the mean is 504.5, while FCFS came to 640. On this queue, serving the requests in the order they arrived is worse than serving them in a random order. FCFS is not a scheduling algorithm and this is the arithmetic that says so.
All seven results
| Algorithm | Total | Compared with random | Can a request starve |
|---|---|---|---|
| the best possible order | 208 | 296 less | not an algorithm |
| SSTF | 236 | 268 less | yes |
| LOOK | 299 | 205 less | no |
| C-LOOK | 322 | 182 less | no |
| SCAN | 331 | 173 less | no |
| C-SCAN | 382 | 122 less | no |
| RSS, on average | 504.5 | the baseline | in principle no, in practice unbounded |
| FCFS | 640 | 135 more | no |
| the worst possible order | 702 | 197 more | not an algorithm |
Three things to take from the table, and they are the three sentences a comparison question wants.
One: every real algorithm except FCFS beats the random baseline, and by a wide margin: SSTF by more than half.
Two: SSTF is the closest to the optimum and the only one that can starve a request. Everything else in the table is safe from starvation and pays for it in movement.
Three: the range is 208 to 702, a factor of more than three between the best and worst ways of serving the same eight requests. That factor is what disk scheduling is worth on a rotating disk, and Chapter ninety two's note about solid state drives is what has happened to it since.
Random Scheduling, and All Six Compared
Where RSS sits on fairness
The property a question can ask about, and the answer is a careful one.
| FCFS | RSS | SSTF | |
|---|---|---|---|
| Order depends on | arrival | chance | the head position |
| Longest wait | bounded: the queue length | unbounded, though each request is chosen eventually with probability one | unbounded, and a distant request may never be chosen |
| Fair | yes, strictly | on average | no |
Unbounded and never are not the same thing. Under RSS a request may be unlucky for a long time, but every draw gives it a chance, so it is served eventually. Under SSTF a request that is always the furthest away is never chosen at all while nearer requests keep arriving. That distinction is worth a mark.
What it does not mean
RSS is not an algorithm anybody uses. It is a baseline and a way of bounding what is possible.
The mean of 504.5 is not a measurement of one run. A single random order might give 208 or
- It is the average over every order, which is what a random choice gives in the long run.
208 is not SSTF done properly. It is the optimum, found by enumeration, and no greedy rule finds it in general.
A factor of three is not available on every queue. This queue was chosen because the algorithms differ on it; a queue already in cylinder order would give the same answer for all of them.
Beating the random baseline is not a high standard. It is the minimum for an algorithm to be worth its code, and FCFS does not clear it.
Quick revision
- RSS serves a randomly chosen waiting request. It is a baseline, not a design.
- Eight requests have 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 40,320 orders, and every one was
enumerated for the standard queue.
- Best 208, mean 504.5, worst 702. The 208 order is the optimum, which proves Chapter
ninety four's point about SSTF.
- FCFS at 640 is worse than the random mean of 504.5.
- The order on the standard queue:
best 208, SSTF 236, LOOK 299, C-LOOK 322, SCAN 331, C-SCAN 382, random 504.5, FCFS 640, worst 702.
- SSTF is nearest the optimum and the only one that can starve a request; the four sweeps are
safe and pay in movement.
- Under RSS a request's wait is unbounded but it is served eventually; under SSTF it
Random Scheduling, and All Six Compared
may never be served.
Test yourself
- What is RSS and why is it taught? Serving a randomly chosen waiting request; it is the
baseline an algorithm must beat and a way of bounding the best and worst possible totals. 2. How many orders are there for eight requests, and what were the best, mean and worst totals on the standard queue? 40,320 orders; 208, 504.5 and 702 cylinders.
- What does the enumeration prove about the order 37, 14, 65, 67, 98, 122, 124, 183? That
its 208 cylinders is the optimum for that queue, because every order was tried and none is shorter.
- Which algorithm fails to beat the random baseline, and by how much? FCFS: 640 against
504.5, which is 135 more than a random order costs on average.
- Put the six algorithms in order of head movement on the standard queue. SSTF 236, LOOK
299, C-LOOK 322, SCAN 331, C-SCAN 382, FCFS 640.
- Which algorithm is closest to the optimum, and what does it cost? SSTF, at 236 against
208, and it is the only one of the six that can starve a request.
- Distinguish an unbounded wait from starvation. Under RSS a request may wait a long time
but every draw gives it a chance, so it is served eventually; under SSTF a request that is always furthest from the head is never chosen while nearer ones keep arriving.
- Why was this particular queue chosen for all three chapters? Because the algorithms give
different answers on it: a queue already in cylinder order would give the same total for every one of them and prove nothing.
The rest of this subject
These notes are cut from the University's printed syllabus. Open the syllabus itself, or the past papers, for the same subject.