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

@bikram sir

need ur approach here

---

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. :)

 

---

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.

---

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 @Skscool007 in correct viewing angle. Note that in above comment, i started with track no. 683 and initially movement done in right side, but @Skscool007 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.

---

@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

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$

Comments

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$

---

After serving the last request the direction of the head would not change, it would remain there. So the direction would be changed 10 times in 11 such track requests.

Answer 2

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:

Comments

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.

Answer 3

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

Comments

@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

Answer 4

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.

Comments

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