edited by
22,763 views
94 votes
94 votes

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?

  1. $9$
  2. $10$
  3. $11$
  4. $12$
edited by

16 Answers

Best answer
89 votes
89 votes

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 $\color{red}{\text{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 $\color{red}{\text{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,\ldots$
  • Or, $2^1-1,2^2-1,2^3-1,2^4-1,\ldots$
  • We have $2048$ tracks so, maximum swing (seek length) can be $2047$
  • Which corresponds to a seek length of $2^{11} - 1$ in the $11^{th}$ service.

Correct Answer: $C$

edited by
59 votes
59 votes

Here Head is changing it's direction after servicing every request. 

Now, we can see distance of SSTF changing like 1,3,7,15,31,63,127,255,511,1023,2047

So, maximum cardinality will be 11.

and following are the track requests:

edited by
21 votes
21 votes
10,138,170,178,180,181,185,201,265,521 should be sequence of access if head is at 180 th track...

Let suppose head is at 512th

So sequence should be ..

171,427,491,507,511,512,514,522,554,684,1194

So ans should be 11...

If same type of question has been asked ...I think we can do it directly... 2028 =2^11..so 11 is the ans...with the condition head can start from any point...
edited by
4 votes
4 votes
Ans) C (11) Consider the following request set (1025,1023,1028,1017,1040,993,1088,897,1280,513,2048) Suppose head is initially positioned at track number 1024.So very first time there is tie between two requests 1025 and 1024 (because both are same distance). So without loss of generality let's assume initially head moving toward right direction(mean first 1025 track request will be serviced). So apply the SSTF afterwards.
Answer:

Related questions