Difficulty: Beginner
Explain disk scheduling algorithms. For requests 98, 183, 37, 122, 14, 124, 65, 67 with the head at 53 on a disk with cylinders 0 to 199, compute the total head movement for FCFS, SSTF and SCAN.
On a traditional hard disk, reading data involves three delays: seek time (moving the read/write head to the right cylinder), rotational latency (waiting for the sector to rotate under the head) and transfer time. Seek time dominates, so the OS reorders pending requests to minimize total head movement. This is disk scheduling. Think of an elevator: if it went to floors in the order people pressed buttons, it would zigzag wastefully, so real elevators sweep in one direction, serving requests on the way. Disk scheduling applies the same idea.
Let's define our data. The disk has cylinders 0 to 199, the head starts at 53, and the request queue is 98, 183, 37, 122, 14, 124, 65, 67. We measure total head movement in cylinders.
FCFS serves requests in arrival order. Movement: 53 to 98 is 45, 98 to 183 is 85, 183 to 37 is 146, 37 to 122 is 85, 122 to 14 is 108, 14 to 124 is 110, 124 to 65 is 59, 65 to 67 is 2. The total is 45 + 85 + 146 + 85 + 108 + 110 + 59 + 2 = 640 cylinders. It is fair but wild swings waste effort.
SSTF (Shortest Seek Time First) always serves the request closest to the current head position. From 53 the nearest is 65 (12), then 67 (2), then 37 (30), then 14 (23), then 98 (84), then 122 (24), then 124 (2), then 183 (59). The total is 12 + 2 + 30 + 23 + 84 + 24 + 2 + 59 = 236 cylinders. It is much better than FCFS but can starve far-away requests, if new close requests keep arriving, much like SJF.
SCAN, the elevator algorithm, moves the head in one direction to the end of the disk, serving requests along the way, and then reverses. Suppose the head is at 53 moving towards 0. It serves 37 and 14 (movement 16 then 23), continues to cylinder 0 (14 more), then reverses and travels up serving 65, 67, 98, 122, 124 and 183. Total movement is 53 to 0 (53) plus 0 to 183 (183) = 236 cylinders. It gives a fairly uniform wait time and avoids starvation. Its weakness is that cylinders just visited are revisited only after the head goes to the far end and back, so the wait is uneven for the edges.
C-SCAN (Circular SCAN) improves fairness by serving requests in one direction only. On reaching the end, the head jumps back to the start without serving anything on the return trip, and continues in the same direction. Going upward from 53: serve 65 through 183, go to 199, jump to 0, then serve 14 and 37. The movement is 146 up to 199, plus the return jump of 199 if counted, plus 37 from 0 to 37, so 382 in total when the jump is counted. Waiting times are more uniform than SCAN.
LOOK and C-LOOK are practical variants that go only as far as the last request in each direction instead of to the physical end of the disk. LOOK toward 0 first would give 53 to 14 (39) then 14 to 183 (169) = 208 cylinders, better than SCAN's 236 here.
Choosing an algorithm depends on load. Under light load, FCFS is fine. Under heavy load, SCAN or C-SCAN variants perform best and avoid starvation. Finally, mention that modern SSDs have no moving head, so seek-optimizing schedulers matter little; Linux uses simple schedulers like noop, mq-deadline or BFQ for them.
Queue: 98 183 37 122 14 124 65 67 Head = 53 Cylinders 0..199
FCFS : 53>98>183>37>122>14>124>65>67
45+85+146+85+108+110+59+2 = 640
SSTF : 53>65>67>37>14>98>122>124>183
12+2+30+23+84+24+2+59 = 236
SCAN (toward 0 first): 53>37>14>0>65>67>98>122>124>183
16+23+14+65+2+31+24+2+59 = 236 (= 53 + 183)
C-SCAN (upward, jump counted): 53>65>67>98>122>124>183>199>0>14>37
146 + 199 + 37 = 382
LOOK (toward 0 first): 53>37>14>65>67>98>122>124>183
39 + 169 = 208Total head movement is the sum of absolute differences between consecutive cylinder positions. SCAN and SSTF tie at 236 for this input by coincidence.
disk scheduling, seek time, SCAN, SSTF, C-SCAN