edited by
22,758 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

1 votes
1 votes
I am getting 11.

Suppose head is at 1365

and request set is

0,1024,1280,1344,1360,1364,1367,1375,1407,1535,2047
1 votes
1 votes

I think the answer is option D. 12.

First of all, please note that this is the second part of a two part question. Part one is here : https://gateoverflow.in/3534/gate2007-it-82

So in part two, we can start anywhere we want.

In this question, we have no. of cylinders N = 2048. My suggestion is that we should look at smaller values of N and see a pattern. (Here, I'm using 1-indexing)

  • For N = 2, cardinality of request set is 2. Sequence : 1, 2.
  • For N = 4, cardinality of request set is 3. Sequence : 2, 3, 1.
  • For N = 8, cardinality of request set is 4. Sequence : 3, 4, 1, 8.

The pattern here is, the cardinality of request set is log(N) + 1. So, log(2048) + 1 = 11 + 1 = 12.

Explanation : Let's try to trace the longest path that we can trace for a given N. This task is easier if we work our way backwards.

  • Let's start at cylinder N. Let's assume that N is a power of 2, so N = $2^{n}$
  • To maximize the path, we go to cylinder 1. (Sweep =  $2^{n}$ - 1)
  • From 1, we can go only as far as cylinder $2^{n - 1}$. Because the next cylinder will be closer to the N than 1. (Sweep =  $2^{n - 1}$ - 1)
  • The next sweep will be of length  $2^{n - 2}$ - 1 so that the destination cylinder is closer to our source than 1.

We can see that the problem is now reduced to finding how many numbers of type $2^{i}$ - 1 are there between 1 and N. You can easily verify that the answer will be log(N). That gives us the number of jumps we made. Add 1 to it to get the number of cylinders visited to get the correct answer.

0 votes
0 votes

Explanation: Distance of SSTF changing – >

1 3 7 15 31 63 127 255 511 1023 2047
1 2 3 4 5 6 7 8 9 10 11

Head is changing it’s direction after servicing every request. Maximum Cardinality is thus 11

 180->181->178->185->170->201->138->265->10

gat_it_2007

0 votes
0 votes

answer should be 12.

consider this sequence: 1,513,641,673,681,683,684,688,704,768,1024,2048.

And head starts at 683.


How I got this sequence?

Above answers explains that max distance should be 2047.

Then we derive this sequence in out-to-in order.

2048 is reached from 1  (dist = 2047)

1 is reached from 1024  (dist = 1023)

1024 is reached from 513 (dist = 511)

......

 

Answer:

Related questions