GATE CS 2020 Q.45 (CS Q.35): File Systems, I/O and Disk Scheduling

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?

T is serviced before P.

Q is serviced after S, but before T.

The head reverses its direction of movement between servicing of Q and P.

R is serviced before P.

Official answer and solution

Official answer: B
From: Official GATE 2020 answer key

Solution

Simulate the Shortest Seek Time First (SSTF) disk scheduling algorithm from starting cylinder 100.

Requests: $P(155), Q(85), R(110), S(30), T(115)$ . Initial head position: 100.

Step-by-step SSTF simulation:

From 100:
- Distance to $R(110) = 10$
- Distance to $Q(85) = 15$ , $T(115) = 15$ , $P(155) = 55$ , $S(30) = 70$
- Minimum is $R(110)$ . Head moves to 110.
From 110:
- Distance to $T(115) = 5$
- Distance to $Q(85) = 25$ , $P(155) = 45$ , $S(30) = 80$
- Minimum is $T(115)$ . Head moves to 115.
From 115:
- Distance to $Q(85) = 30$
- Distance to $P(155) = 40$ , $S(30) = 85$
- Minimum is $Q(85)$ . Head moves to 85.
From 85:
- Distance to $S(30) = 55$
- Distance to $P(155) = 70$
- Minimum is $S(30)$ . Head moves to 30.
From 30:
- Only $P(155)$ remains. Head moves to 155.

Service sequence:

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

Evaluate the statements:

A: 'T is serviced before P' is TRUE (T is 2nd, P is 5th).
B: 'Q is serviced after S, but before T' is FALSE (Q is 3rd, while S is 4th; so Q is serviced before S).
C: 'The head reverses its direction of movement between servicing of Q and P' is TRUE (from T to Q to S, direction is decreasing; from S to P, direction is increasing).
D: 'R is serviced before P' is TRUE (R is 1st, P is 5th).

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2020 Computer Science and Information Technology (CS)
Question: 45 of 65, printed as CS Q.35
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source