Assuming the current disk cylinder to be 50 and the sequence for the cylinders to be 1, 36, 40, 65, 53, 12, 20, 55, 16, 65, and 78, find the sequence of servicing using: 1. Shortest seek time first (SSTF) 2. Elevator disk scheduling (SCAN)
GATE 1990 · Operating System · Disk Scheduling · medium
Answer: SSTF servicing order: 53, 55, 65, 65, 78, 40, 36, 20, 16, 12, 1. SCAN servicing order: 53, 55, 65, 65, 78, then 40, 36, 20, 16, 12, 1.
- SSTF: greedy nearest-first servicing: Start=50. Remaining: {1,36,40,65,53,12,20,55,16,65,78} From 50: nearest=53 (dist 3). -> 53. Remaining: {1,36,40,65,12,20,55,16,65,78} From 53: nearest=55 (dist 2). -> 55. Remaining: {1,36,40,65,12,20,16,65,78} From 55: nearest=65 (dist 10). -> 65. Remaining: {1,36,40,12,20,16,65,78} From 65: nearest=65 (dist 0). -> 65. Remaining: {1,36,40,12,20,16,78} From 65: nearest=78 (dist 13) vs 40(dist 25). -> 78. Remaining: {1,36,40,12,20,16} From 78: nearest=40 (dist 38). -> 40. Remaining: {1,36,12,20,16} From 40: nearest=36 (dist 4). -> 36. Remaining: {1,12,20,16} From 36: nearest=20 (dist 16). -> 20. Remaining: {1,12,16} From 20: nearest=16 (dist 4). -> 16. Remaining: {1,12} From 16: nearest=12 (dist 4). -> 12. Remaining: {1} From 12: -> 1. SSTF Order: 50->53->55->65->65->78->40->36->20->16->12->1
- SCAN (Elevator): sweep up then down: Start=50, moving upward. Requests >= 50 (sorted ascending): 53, 55, 65, 65, 78 Requests < 50 (sorted descending): 40, 36, 20, 16, 12, 1 SCAN Order: 50->53->55->65->65->78 (reverse) ->40->36->20->16->12->1