14,287 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$

@bikram sir

need ur approach here
edited by

Hi Guys,

This is good question. Think on following points -

1. Why can we  not have multiple seek series ?
2. Why is greedy algo. working ?
3. Why are we starting from 1 ?
4. Does starting points matters ?

PS: Think in terms of seek sequence. For answer hint check @Debashish Deka ji's top comment.

beautiful question

thank you @ Chhotu for comment

Hi Guys,

This is good question. Think on following points -

1. Why can we  not have multiple seek series ?
2. Why is greedy algo. working ?
3. Why are we starting from 1 ?
4. Does starting points matters ?

I tried by self and got the some logic. which was correct.

really beautiful question. :)

edited

Earlier I assumed that why we are not starting from track 180 as initially head is positioned at 180. But in the later part of the question it is mentioned that "head can start from any track". that's why answer is 11 but not 9.

edited by

A slightly different explanation:

Let's say our track head is at position 0 and our track numbers go in both directions around 0. To ensure that we always change directions and that we do this as many times as possible, we have to go right 1 track to get +1, then left 3 tracks to get -2, then right again 7 tracks to get +5,and so on...

$0 \rightarrow +1 \rightarrow -2 \rightarrow +5 \rightarrow ...$

Notice that in each step, we move exactly $2^n - 1$ tracks to the left and right in alternating fashion, where $n$ is the step number. For example, we moved $1 (=2^1 - 1)$ track to the right in the first step, $3 (= 2^2 - 1)$ tracks in the second step and so on.

The critical thing to remember is this:

Our limit of at most 2048 tracks will be reached exactly when the next step requires us to move more than 2047 places.

Or in other words, as soon as we need to move more than 2047 tracks in the next step, we know that we can't, and then stop.

So in our last step, we can choose to move $2047 (= 2^{11} - 1)$ places. So total number of steps = 11. These steps represent the track numbers other than the track 0 that we started with. So there are 11 + 1 = 12 elements (track numbers) in the request set.

So the correct answer is D. 12

EDIT: Since the question mentions that “the head changes its direction after servicing every request”, the track on which the head is at the start cannot be considered a request (since the direction doesn’t change after servicing it). So, the correct answer is C. 11

best ans by @rawan !! thanks :)

Why is everyone saying 11?

The ans should be 12 and here is how...

see my answer below $11$ is correct , not $12$.

Option D should be correct. See reason in below image :-

Re-posting image of @ in correct viewing angle. Note that in above comment, i started with track no. 683 and initially movement done in right side, but @ started with track no. 1366 (i.e 2048-682) and initially movement  done in Left side.

Due to this reason, we able to get two "request set" with maximum possible cardinality.

IN GO PDF, question is else, here its else.

Why did they remove starting from 180

I dont know!
will this be independent of the initial head position? If not how to know where to start from initially...
One of the best question in OS
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.

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

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)

......

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.

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

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.

@Marv: How did you eliminate other options ??

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