GATE CS 2015 Set 1 Q30 — I/O Scheduling

To find the additional distance traversed by the R/W head using the SSTF algorithm compared to the SCAN algorithm, we calculate the total head movements for both.

1. Shortest Seek Time First (SSTF) Algorithm:

Starting at track $50$, the head always moves to the nearest pending request:

• $50 \to 45$ (distance: $|45 - 50| = 5$)
• $45 \to 60$ (distance: $|60 - 45| = 15$)
• $60 \to 70 \to 80 \to 90$ (distance: $|90 - 60| = 30$)
• $90 \to 25$ (distance: $|25 - 90| = 65$)
• $25 \to 20 \to 10$ (distance: $|10 - 25| = 15$)

$$\text{Total SSTF Distance} = 5 + 15 + 30 + 65 + 15 = 130 \text{ tracks}$$

2. SCAN (LOOK) Algorithm:

Starting at $50$ and moving towards $100$, the head services requests in that direction up to the last request ($90$), then reverses direction to service the remaining requests down to $10$:

• $50 \to 60 \to 70 \to 80 \to 90$ (distance: $|90 - 50| = 40$)
• $90 \to 45 \to 25 \to 20 \to 10$ (distance: $|10 - 90| = 80$)

$$\text{Total SCAN Distance} = 40 + 80 = 120 \text{ tracks}$$

3. Difference:

$$\text{Additional Distance} = 130 - 120 = 10 \text{ tracks}$$