GATE CS 2001 Q20 — I/O Scheduling

Here is the step-by-step solution for both parts of the question:

Part (A)

We are given:

• Tracks: $0$ to $99$
• Initial head position: $25$, moving upwards
• Requests: $32, 7, 45, 5, 10$
• Seek time per track = $0.2\text{ ms}$

Depending on the specific interpretation of the elevator algorithm, we analyze both standard variants:

1. LOOK Algorithm (reverses at the last request):
   • The head moves from $25 \to 32 \to 45$, then reverses and moves $45 \to 10 \to 7 \to 5$.
   • Total seek distance = $(45 - 25) + (45 - 5) = 20 + 40 = 60$ tracks.
   • Total seek time = $60 \times 0.2\text{ ms} = \mathbf{12\text{ ms}}$.
2. SCAN Algorithm (goes to the boundary):
   • The head moves from $25 \to 32 \to 45 \to 99$, then reverses and moves $99 \to 10 \to 7 \to 5$.
   • Total seek distance = $(99 - 25) + (99 - 5) = 74 + 94 = 168$ tracks.
   • Total seek time = $168 \times 0.2\text{ ms} = \mathbf{33.6\text{ ms}}$.

Part (B)

We are given:

• Rotation speed = $3000\text{ rpm} = 50\text{ rotations/sec}$
• Time for $1$ full rotation = $\frac{1}{50}\text{ s} = 20\text{ ms}$
• Sectors per track = $100$
• Transfer time for $1$ sector = $\frac{20\text{ ms}}{100} = 0.2\text{ ms}$

To find the worst-case time to complete $100$ arbitrary requests starting at track $0$:

• Worst-case distribution: Each of the $100$ requests lies on a different track (from track $0$ to $99$).
• Total Seek Time: The head traverses from track $0$ to $99$ in a single sweep. $$\text{Seek Time} = 99 \times 0.2\text{ ms} = 19.8\text{ ms}$$
• Worst-case Rotational Latency: For each request, the head arrives just after the target sector has passed, requiring a full rotation ($20\text{ ms}$). $$\text{Total Latency} = 100 \times 20\text{ ms} = 2000\text{ ms}$$
• Total Transfer Time: Reading $100$ sectors: $$\text{Total Transfer Time} = 100 \times 0.2\text{ ms} = 20\text{ ms}$$

$$\text{Total Worst-Case Time} = 19.8\text{ ms} + 2000\text{ ms} + 20\text{ ms} = \mathbf{2039.8\text{ ms}} \approx \mathbf{2.04\text{ seconds}}$$