17,879 views

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$

yes ABHINEET, it will be independent.

You can start with any track, do zig zag, you will erach 2047 in 11 steps only.
edited
@Aalok8523 @Skscool007

Initially head will be at some position or moving in some specific direction then we should not take current position of head in cardinality of the request because if we do so then head will not change it's direction if request come at track on which it is currently there.

So that's why you are getting 12.

Because of above reason you should remove one track (initial position of head) and answer should be 11.

I hope it will help others who are confused in the battle of 11 and 12.
good question

(0+1) + (1+2) + (3+4) + (7+8) + (15+16) + ( 31+32) + (63+64) + (127+128)  + (255+256) + (511+512) + (1023+1024)

Hence 11 will be the answer.

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$

by

@Abhineet, we should not consider the current head position as a request because the question says that head has to change direction
yes, I think you are correct. I got a little confused after going through some commets above that have mentioned 12 as the answer
More formally for the series 1, 3, 7, …

$t_{n} = 2*t_{n-1} + 1$

= $2^{2}t_{n-2} + 2^{1} + 1$

= $2^{3}t_{n-3} + 2^{2} + 2^{1} + 1$

= $2^{n-1}t_{n – (n-1)} + 2^{n-2} + 2^{n-3} + … + 2 + 1$

= $2^{n-1}*t_{1} + 2^{n-2} + 2^{n-3} + … + 2 + 1$

Since $t_{1} = 1$

The GP series summation redices to

= $2^{n} – 1$

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:

by

If you start from 1366, there is no way you will get 180 as a request in the middle or at the end. If you don't beleive me you may try making it. Yes, but if you start from 1366, this will result in best case of fulfilling 12 request but when 180 is not given.

That's why they mentioned in the question 180, so that everyone will get same answer as 11.
Question is edited.. see once more
Yes, now answer should be 12. Sorry, I didn't see the edit.
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...
by

@gabbar how to take a sequence.........its why only 10 number??
In context of question it is 10  head at 180??
Answer should be 10. I think that the "head" should not be included in the request set.

Even in the first part of this question, 180th track which was the head was not included in the request set.

@Papesh
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.

### 1 comment

edited
As, initially no direction is given. So, isn't this Ambiguous ?