GATE IT 2007 | Question: 83

Question

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?

• A. $9$
• B. $10$
• C. $11$
• D. $12$

Comments

yes ABHINEET, it will be independent.

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

---

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

Answer 1

As we already know from the previous answers that the difference between the sequence of requests will be like 1,3,7,15,31,63,127,511,1023,2047 and head can start from any position then we can start the zigzag line from backward i.e from 2048 to 1 (or we can do from 1 to 2048)

We can do it till the difference is 1.

So answer will be 11.

 

*As it is asked about the about cardinality of requeste set i.e the number of requests (not how many times it changed its direction) then it will be 11, as requests are 684, 681, 688, 673, 704, 641, 768, 513, 1024, 1, 2048.

*Here the head (683) is not included because head it self is not a request of the current request set.

Answer 2

video explanation .………………...

Answer 3

QUESTION IS AMBIGUOS

Consider the request in this order by assuming header is at 1023, [1022,1024,1026,1018,1034,1002,1066,938, 1194, 682, 1706,2047,0]. 

Now think, what is the condition of SSTF algorithm? When there is a tie between the requests, in which direction should it chose? 

The above question will remove the ambiguity of the question if answered in the question.

For the above given request consider these conditions: 1) At start header move towards right or left. 2) When there is tie, header changes the direction. 

Hence the maximum number of time header changes the direction is 12, not 11.

 

ANSWER IS OPTION  - D

Answer 4

B...let say it starts from middle track 1024. First track would be 2^0 distance away from 1024 and next track on the opposite side 2^1 distance away from 1024 and similarly following the same pattern of zig zag motion we get the 683th track on lower end (341 distance away1024th track) and now to change its direction it has to go to the other side which means there should not be any request left on the lower end of the track. Now the last movement would be to track  number 1706th(682 away from middle track). Hence total will be  10 requests and 9 movement.

Comments

@Marv: How did you eliminate other options ??

Why can't we take 12 requests and make change the direction every time ??

Please respond to this.

---

we can only change the direction if it is following the shortest seek time. If there is a request on one end (where the head is currently) which is closer to the head then it will service that, so the only way to go to other side is when otherside request is closer to the head then any request to this side. Please try to draw the picture the way I said on the answer, the other option will be eliminated by it.