GATE 2020 CS Q.35: solution and answer

GATE 2020 · CSQ.35 · 2 marks · MCQ

Consider the following five disk access requests of the form (request id, cylinder number) that are present in the disk scheduler queue at a given time.

(P, 155), (Q, 85), (R, 110), (S, 30), (T, 115)

Assume the head is positioned at cylinder 100. The scheduler follows Shortest Seek Time First scheduling to service the requests.

Which one of the following statements is FALSE?

(A)
T is serviced before P.
(B)
Q is serviced after S, but before T.
(C)
The head reverses its direction of movement between servicing of Q and P.
(D)
R is serviced before P.

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The false statement is (B): under SSTF the order is R, T, Q, S, P, so Q is served before S and after T.

Official answer: BSource: Official answer key, GATE 2020 CS (IIT Delhi)

Shortest Seek Time First always serves the pending request whose cylinder is nearest the current head position. The head starts at cylinder 100.
From 100 the distances are $P = 55$ , $Q = 15$ , $R = 10$ , $S = 70$ , $T = 15$ . The nearest is $R$ (110), so serve $R$ . The head is now at 110.
From 110 the distances are $P = 45$ , $Q = 25$ , $S = 80$ , $T = 5$ . Serve $T$ (115). The head is now at 115.
From 115 the distances are $P = 40$ , $Q = 30$ , $S = 85$ . Serve $Q$ (85). The head is now at 85.
From 85 the distances are $P = 70$ , $S = 55$ . Serve $S$ (30). The head is now at 30. The last request is $P$ (155).
$Order Request Cylinder 1 R 110 2 T 115 3 Q 85 4 S 30 5 P 155$
Check the options against this order. (A) $T$ is 2nd and $P$ is 5th, so $T$ is served before $P$ : true. (B) $Q$ is 3rd and $S$ is 4th, so $Q$ is served before $S$ , not after it (and it is also after $T$ , not before it): false. (C) After $Q$ (85) the head moves down to 30 for $S$ , then up to 155 for $P$ , so it reverses direction between $Q$ and $P$ : true. (D) $R$ is 1st and $P$ is 5th: true.
The only false statement is (B).

KEY IDEA

With SSTF, recompute the distance from the current head position to every pending request after each service and always take the smallest. Write down the full service order, then test each option against it.

WATCH OUT FOR

Computing every distance from the starting cylinder 100 once and sorting by it. That gives R, then Q or T, then P, then S, which is wrong because the head moves after each service. Another slip is missing that Q (85) and T (115) are both 15 away at the start, so the tie only matters if you do not move first. Here R is strictly nearest, and the head then reaches T before Q.

From the GATE 2020 CS paper. Every question of this paper · Download the full paper · All 6 File systems & disks questions, with notes

GATE 2020 CS Q.35: solution and answer

Answer and solution

More File systems & disks questions