GATE - 2007 | OS | The head of a hard disk serves requests following the SSTF

GATE - 2007 | OS | The head of a hard disk serves requests following the SSTF
Posted on 17-02-2022

GATE - 2007 [Operating System]

Question:

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. 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?

A

9

B

10

C

11

D

12

  

Solution:

Option (C) is Correct.

We need two conditions to satisfy:
1) The alternating direction with SSTF policy.
2) Maximize the no. of requests.
The first condition can be satisfied by not having two requests at an equal distance from the current location. As shown below, we must not have requests located in the circle marked positions.
Now to maximize the no. of requests 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 circle marked position in a particular direction (the direction in which the head needs to move).
Now to satisfy the 1st criteria:
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. 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?
Seek length sequence for maximum cardinality and alternating head movements:
→ 1, 3, 7, 15, ...
→ or, 21-1, 22-1, 23-1, 24-1, ...
→ We have 2048 tracks so, the maximum swing (seek length) can be 2047.
→ Which corresponds to a seek length of 211-1 in the 11th service.

Thank You