Previous Year Questions: Disk Scheduling | Operating System - Computer Science Engineering (CSE) PDF Download

Q1: Consider the following five disk five disk access requests of the form (request id, cylinder number) that are present in the disk scheduler queue at a given time.  (2020)
(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
Ans: (b)
Sol: Shortest Seek Time First (SSTF), selects the request with minimum to seek time first from the current head position. In the given question disk requests are given in the form of  request id, cylinder number)
Cylinder Queue: (P, 155), (Q, 85), (R, 110), (S, 30), (Τ, 115)
Head starts at 100

• It is clear that R and T are serviced before P .
• Q is serviced when head is moving towards lower cylinders and P is serviced when head is moving
  towards higher cylinders thus reverses it direction at S .

Option B) is the correct answer

Q2: 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 _______.  (2018)
(a) 85
(b) 115
(c) 155
(d) 55
Ans: (a)
Sol: Shortest Seek Time First (SSTF), selects the request with minimum to seek time first from the current head position.
In the given question disk requests are given in the form of  
sectorNo, cylinderNo, platterNo).
Cylinder Queue: 72, 134, 20, 86, 116, 16
Head starts at: 80

Total head movements in SSTF (86  -80) + (86 - 72) + (134 - 72) + (134 -16) = 200

• Power dissipated in moving 100 cylinder  = 20 m W
• Power dissipated by 200 movements (say P1 ) = 0.2 * 200 = 40 m W
• Power dissipated in reversing head direction once = 15 m W
• Number of times head changes its direction = 3
• Power dissipated in reversing head direction (say P2 ) = 3 * 15 = 45 m W 

Total Power Consumption is P1 + P2 = 85 m W
Hence, 85mW is the correct answer.

Q3: 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 to wards larger cylinder numbers on its servicing pass. The cylinders are numbered from 0to 199. The total head movement (in number of cylinders) incurred while servicing these requests is____ .  (2016 SET 1)
(a) 346
(b) 146
(c) 546
(d) 446
Ans: (a)
Sol: 

The total head movement incurred while servicing these requests:
= (87 – 63) + (92 - 87) + (121 - 92) + (191 - 121) + (191 – 10) + (11 – 10) + (38 - 11) + (47 - 38)
= 24 + 5 + 29 + 70 + 181 + 1 + 27 + 9
= 346 (in number of cylinders)

Q4: Suppose the following disk request sequence (track numbers) for a disk with 100 tracks is given: 45, 20, 90, 10, 50, 60, 80, 25, 70. Assume that the initial position of the R/W head is on track 50. The additional distance that will be traversed by the R/W head when the Shortest Seek Time First (SSTF) algorithm is used compared to the SCAN (Elevator) algorithm (assuming that SCAN algorithm moves towards 100 when it starts execution) is____________ tracks.  (2015 SET 1)
(a) 8
(b) 9
(c) 10
(d) 11
Ans: (c)
Sol:  LOOK Algorithm: 

Header first goes to the farthest request towards the right and then returns to the farthest request 1.
For SCAN it takes 140 head movements
∴ Total Tracks = (100 - 50) + (100 - 10) = 90 + 50 = 140
Shortest Seek Time First (SSTF)

Total tracks = (50 - 45) + (90 - 45) + (90 - 10) = 130
Hence the additional distance that will be traversed by the R/W head when the Shortest Seek Time First (SSTF) algorithm is used compared to the SCAN is 140 - 130 = 10.

Q5: Suppose a disk has 201 cylinders, numbered from 0 to 200. At some time the disk arm is at cylinder 100, and there is a queue of disk access requests for cylinders 30, 85, 90, 100, 105, 110, 135 and 145. If Shortest-Seek Time First (SSTF) is being used for scheduling the disk access, the request for cylinder 90 is serviced after servicing ____________ number of requests.  (2014 SET 1)
(a) 2
(b) 3
(c)4
(d) 5
Ans: (b)
Sol: Requests are serviced in following order
100 105 110 90 85 135 145 30
So, request of 90 is serviced after 3 requests.

Q6: Consider a disk system with 100 cylinders. The requests to access the cylinders occur in following sequence:
4, 34, 10, 7, 19, 73, 2, 15, 6, 20
Assuming that the head is currently at cylinder 50, what is the time taken to satisfy all requests if it takes 1ms to move from one cylinder to adjacent one and shortest seek time first policy is used?  (2009)
(a) 95ms
(b) 119ms
(c) 233ms
(d) 276ms
Ans: (b)
Sol: = (50 - 34) + (34 - 20) + (20 - 19) + (19 - 15) + (15 -10) +(10 -7) + (7 - 6) + (6 - 4) +(4 -2) + (73 - 2)
=16 +14 + 1+ 4 + 5 + 3 +1 + 2 + 2 +71
= 119 ms
Answer is (B).

Q7: The head of a hard disk serves requests following the shortest seek time first (SSTF) policy.
What is the maximum cardinality of the request set, so that the head changes its direction after servicing every request if the total number of tracks are 2048 and the head can start from any track?  (2007)
(a) 9
(b) 10
(c) 11
(d) 12
Ans: (c)
Sol: We need two conditions to satisfy:

1. The alternating direction with shortest seeks time first policy.
2.  Maximize the no. of requests.

The first condition can be satisfied by not having two requests in the equal distance from the current location. As shown below, we must not have request located int he red marked positions.
Now to maximize the no of request we need the requests to be located as compact as possible. Which can be done by just placing the request in the next position after the red marked position in a particular direction (the direction in which the head need to move now to satisfy the
1^st criteria).
Seek length sequences for maximum cardinality and alternating head movements:

• 1, 3, 7, 15,...
• Or, 2¹-1, 2² 1, 2³ 1, 2⁴ 1,...
• We have 2048 tracks so, maximum swing (seek length) can be 2047
• Which corresponds to a seek length of 2 ¹¹−1 in the 11^th service.

Correct Answer: C

Q8: The head of a hard disk serves requests following the shortest seek time first (SSTF) policy. The head is initially positioned at track number 180. Which of the request sets will cause the head to change its direction after servicing every request assuming that the head does not change direction if there is a tie in SSTF and all the requests arrive before the servicing starts?  (2007)
(a) 11, 139, 170, 178, 181, 184, 201, 265
(b) 10, 138, 170, 178, 181, 185, 201, 265
(c) 10, 139, 169, 178, 181, 184, 201, 265
(d) 10, 138, 170, 178, 181, 185, 200, 265
Ans: (b)
Sol: It should be (B).
When the head starts from 180 . It seeks the nearest track which is . 181 Then, from 181  it seeks the nearest one which is178  and 184 . But the difference in both from181 is same and as given in the question. If there is a tie then the head wont change its direction, and therefore to change the direction we need to consider178  . and thus we can eliminate option (A) and (C).Coming next to option (B) and (D).
Following the above procedure you'll see that option (D) is eliminated on similar ground. And thus you can say option (B) is correct.