Disk scheduling algorithms with numerical

Disk scheduling is the method the operating system uses to decide the order in which pending disk I/O requests are served. Its aim is to reduce the total seek time (arm movement), since seek time dominates disk access time (seek + rotational latency + transfer time), and so to improve throughput and fairness.

Algorithms

1. FCFS: serve requests in arrival order. Fair and simple, but the arm may swing wildly across the disk.
2. SSTF: serve the request nearest to the head. Low seek time, but far-away requests may starve.
3. SCAN (elevator): the arm moves in one direction serving requests, reaches the end of the disk, reverses and serves requests on the way back. No starvation.
4. C-SCAN: serve requests in one direction only; on reaching the end, return to the other end without serving, then sweep again. Gives a more uniform waiting time.
5. LOOK / C-LOOK: like SCAN / C-SCAN, but the arm goes only as far as the last request in each direction.

Numerical

Disk has cylinders 0–199, head at 53 and moving towards 0, queue = 98, 183, 37, 122, 14, 124, 65, 67.

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: 53 → 37 → 14 → 0 → 65 → 67 → 98 → 122 → 124 → 183 16 + 23 + 14 + 65 + 2 + 31 + 24 + 2 + 59 = 236

LOOK: 53 → 37 → 14 → 65 → 67 → 98 → 122 → 124 → 183 16 + 23 + 51 + 2 + 31 + 24 + 2 + 59 = 208

C-SCAN: 53 → 37 → 14 → 0 → 199 → 183 → 124 → 122 → 98 → 67 → 65 16 + 23 + 14 + 199 + 16 + 59 + 2 + 24 + 31 + 2 = 386 (return jump 0 → 199 counted)

C-LOOK: 53 → 37 → 14 → 183 → 124 → 122 → 98 → 67 → 65 16 + 23 + 169 + 59 + 2 + 24 + 31 + 2 = 326 (return jump 14 → 183 counted)

Answer: FCFS has the most movement (640) and LOOK the least (208). SSTF and SCAN both give 236. Under heavy load, SCAN/C-SCAN are preferred because they avoid starvation.