GATE CS 2018 Q.63 (CS Q.53): File Systems, I/O and Disk Scheduling

Consider a storage disk with 4 platters (numbered as 0, 1, 2 and 3), 200 cylinders (numbered as 0, 1, … , 199), and 256 sectors per track (numbered as 0, 1, … , 255). The following 6 disk requests of the form [sector number, cylinder number, platter number] are received by the disk controller at the same time:

[120, 72, 2] , [180, 134, 1] , [60, 20, 0] , [212, 86, 3] , [56, 116, 2] , [118, 16, 1]

Currently the head is positioned at sector number 100 of cylinder 80, and is moving towards higher cylinder numbers. The average power dissipation in moving the head over 100 cylinders is 20 milliwatts and for reversing the direction of the head movement once is 15 milliwatts. Power dissipation associated with rotational latency and switching of head between different platters is negligible.

The total power consumption in milliwatts to satisfy all of the above disk requests using the Shortest Seek Time First disk scheduling algorithm is _______.

Your answer

Official answer and solution

Official answer: 85
From: Official GATE 2018 answer key

Solution

Trace the SSTF cylinder service sequence, calculate total cylinder distance and count direction reversals.

The requests are on cylinders: $\{16, 20, 72, 86, 116, 134\}$ . Head starts at cylinder 80, moving towards higher cylinders.

Trace SSTF (Shortest Seek Time First):

From 80: Closest request is 86 (seek distance $|80 - 86| = 6$ ). Move to 86 (direction: increasing).
From 86: Remaining requests are $\{16, 20, 72, 116, 134\}$ .
Distances: $|86 - 72| = 14$ , $|86 - 116| = 30$ . Closest is 72. Move to 72 (seek distance 14, reversal 1: now decreasing).
From 72: Remaining requests are $\{16, 20, 116, 134\}$ .
Distances: $|72 - 116| = 44$ , $|72 - 20| = 52$ . Closest is 116. Move to 116 (seek distance 44, reversal 2: now increasing).
From 116: Remaining requests are $\{16, 20, 134\}$ .
Distances: $|116 - 134| = 18$ , $|116 - 20| = 96$ . Closest is 134. Move to 134 (seek distance 18, direction: increasing).
From 134: Remaining requests are $\{16, 20\}$ .
Closest is 20 (seek distance $|134 - 20| = 114$ ). Move to 20 (reversal 3: now decreasing).
From 20: Remaining request is 16 (seek distance $|20 - 16| = 4$ ). Move to 16 (direction: decreasing).

Total seek distance:

\text{Total cylinders} = 6 + 14 + 44 + 18 + 114 + 4 = 200\text{ cylinders}

Power for cylinder movement:

\text{Power}_{\text{seek}} = \frac{200}{100} \times 20\text{ mW} = 40\text{ mW}

Direction changes (reversals):

Reversal 1 at cylinder 86 (increasing to decreasing)
Reversal 2 at cylinder 72 (decreasing to increasing)
Reversal 3 at cylinder 134 (increasing to decreasing)
Total reversals = 3.
Power for reversals:

\text{Power}_{\text{reversal}} = 3 \times 15\text{ mW} = 45\text{ mW}

Total power consumption:

\text{Total} = 40\text{ mW} + 45\text{ mW} = 85\text{ mW}

Final answer

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

Source

Paper: GATE 2018 Computer Science and Information Technology (CS)
Question: 63 of 65, printed as CS Q.53
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