GATE CS 2016 Set 1 Q.58 (CS Q.48): File Systems, I/O and Disk Scheduling

Consider a disk queue with requests for I/O to blocks on cylinders 47, 38, 121, 191, 87, 11, 92, 10. The C-LOOK scheduling algorithm is used. The head is initially at cylinder number 63, moving towards larger cylinder numbers on its servicing pass. The cylinders are numbered from 0 to 199. The total head movement (in number of cylinders) incurred while servicing these requests is _____.

Your answer

Official answer and solution

Official answer: 346
From: Official GATE 2016 answer key

Solution

Trace the head movements in C-LOOK disk scheduling for the given request sequence and starting position.

Given requests: 47, 38, 121, 191, 87, 11, 92, 10.
Arranged in sorted order: $10, 11, 38, 47, 87, 92, 121, 191$ .
Initial head position: $63$ .
Current direction: Towards larger cylinder numbers.

In C-LOOK (Circular LOOK) scheduling:

The head services requests in the current direction up to the last request in that direction.
It then jumps directly to the lowest requested cylinder at the other end without servicing requests during the jump.
Finally, it services remaining requests moving in the original direction.

Path trace:

From initial position $63$ , move towards larger cylinders to service $87, 92, 121, 191$ :

\text{Head movement} = 191 - 63 = 128

From the highest cylinder requested ( $191$ ), jump to the lowest requested cylinder ( $10$ ):

\text{Head movement} = 191 - 10 = 181

From cylinder $10$ , move upwards to service the remaining requests $11, 38, 47$ :

\text{Head movement} = 47 - 10 = 37

Calculate total head movement:

\text{Total movement} = 128 + 181 + 37 = 346\text{ cylinders}

Final answer

346

Common trap

Treating C-LOOK like C-SCAN by moving all the way to the boundary cylinder 199 and wrapping to cylinder 0, which yields $(199 - 63) + 199 + 47 = 382$ .

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

Source

Paper: GATE 2016 Computer Science and Information Technology (CS) Session 1
Question: 58 of 65, printed as CS Q.48
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