6.1k views

The head of a hard disk serves requests following the shortest seek time first (SSTF) policy. The head is initially positioned at track number $180$.

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 | 6.1k views
0
@bikram sir

need ur approach here
+3

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.

0
beautiful question
0

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

+4

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.

+6

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

0
best ans by @rawan !! thanks :)
0

Why is everyone saying 11?

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

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$...
• Or, $2^1-1,2^2-1,2^3-1,2^4-1...$
• 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 Veteran (57k points)
edited
0
jst fab ...
0

Awesome explanation

0
@ Debashish max-swing can't be 2047 it will exceed the total no of tracks i.e with swing of 2047 the track no will be >2047..

We can have swing length only till 1023 to be in the range of 0-2047. So I feel it can only go till 1023 i.e 2^10-1 and hence the 10th service.

correct me if I am wrong..
+9

I guess my numbering in the above image is not correct.

But I think if you look at the following image, for a total $16$ tracks we can have $15$ ( $=2^{\color{red}{4}} - 1$ ) length swing. And in the question, it is mentioned that we can start from any track. The track $6$ is the starting point in the following case. We need not worry about the starting point. But we just know that $2047$ swing length is possible indeed. Does it make sense?

+4
Ohh okay! I was under the impression that we only get max requests when we start from the middle, and if we do start from the middle i.e even in this example of yours  Our middle will be 8 and from there we wont get a swing length of 15..So yes we needn't start from middle and swing length of 15 is possible. Yes, Thankyou:)
0
Yes, I also never explicitly said to start from the middle in the answer.
0
@Debashish from 5 you are going to 8 why not to 7?
0
@charul

if we go to 7 from 5, then 6 will have two equal distances on either sides (5 & 7), which we don't want.
0
@vishalshrm539, what impact will it make if 5 & 7 are equidistant from 6?
+1
If current direction of head is right(lower to upper blocks), then at 6, it will have same distance to 5 & 7, so it may go to 7(in most of the cases it will), which is right of it so the condition we want will fail, that at each step, head should change its direction.
0
got it, thanks a lot
0
This seems correct explanation rather than not giving reason why others have started from random numbers to bring the answer 11.
+1
I didn't really get why 180 was given in the question. If 180->181->178->185->170->201->138->265->10->511 this order is to be considered, it counts to 10 numbers and not 11. If we need not start from 180, What is the significance of 180 in the question?
+1
I also have the same doubt. What is the significance of 180 in the question?
0

I think answer should be 9, because we need to consider that Head is initially positioned at 180. and following is the sequence:

$181,178,188,170,201,138,265,10,521$

+1
Why cannot we take the starting position as one request and consider cardinality as 12?
0

But what is the use of (2^i) - 1 ?

@Debashish Deka we get only last track by using this formula,but not any intermediate tracks.

According to your last picture how can I found intermediate tracks by using this formula?

–1

@Vamsi krishna satya That's because you are right. If we have 11 services, that means we have 12 elements in the set. So 12 is the correct answer.

0

@Vamsi krishna satya I have taken starting point as one request and still getting 11. Can you point some mistake if I have made in my comment? Thanks

0

@basant 180 is given in the question because it is part 2 of a two-part question. Part 1 is here: https://gateoverflow.in/3534/gate2007-it-82

0
what if 100 not include in the request queue, does answer became 2?
0

Shouldn't we have to consider head starting position as one request?

If we consider starting of head also as a request then there will be 12 requests that can be serviced.

https://gateoverflow.in/?qa=blob&qa_blobid=4656701868800323057

@Satbir

0
No starting position is not treated as a request.

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 Veteran (117k points)
edited
+1

Where have u used  head can start at any track?

+2
yes, is that make any difference, if head positioned at 180 or to some other?
0
@bikram sir

from 180 to 185

is it not 6 changes ?
0
Anybody has the official answer ?
0
Will you gt till 2047 ?
+2
@srestha Can you please clear me this

if the disk header is at 180 then to get the sequence 1,3,7,15..

180-181 = 1 now the disk is at 181.

181-178=3   now the disk is at 178.

185-178=7   now the disk is at 185.

185-170=15 now the disk is at 170.

201-170=31 now the disk is at 201.

201-138=63 now the disk is at 138.

265-138=127 now the disk is at 265.

265-10=255  now the disk is at 10.

Now to maintain the sequence ... the next one should be 511

So, the disk header should move to 521.

521-10=511 now the disk is at 511.

Again to maintain the sequence ... the next one should be 1023

Now as the previous direction was from 10 to 521 the next one should be  from 521 to it's left.

521-x=1023 => x=521-1023<0 which is not possible.

Then at this point we realize that we should not have started from 180. Am i right?
0
yes coeect
0
seems correct!
0

Manu Thakur

​​​​​​​m not getting how u approach this sequence .pls explain further

0
chk @Debashish comment then
0
@Manu Thakur

why u started from 1023?
+1
@srestha that i only chose randomly. As you have already mentioned, the difference of the track numbers should be at least less than by 1 between the track request at the same direction and in the opposite direction.

You can notice that, left most served track request is 341 and right most served track request is 1364, but the tracks are from 0 to 2047. it means if deduct 1 or 2 or etc from all the requests then also we will get another requests in which head will change its direction 11 times.
I took 1023 randomly, though others sequence are also possible, but it's better to start from the middle because both sides head gets equal chance to move its direction.
0

Now, we can see distance of SSTF changing like 1,3,7,15,31,63,127,255,511,1023,2047

Shouldn't this be :- 0,1,3,7,15,31,63,127,255,511,1023

2047 distance will not come here.

0
@srestha

But in your figure (last one) only 9 times directions are changing.
0

@srestha  . Can u plz explain what is wrong with this approach.... It is following SSTF as well as alternating sequence

0
I have done same too :p

I think no wrong in that too
0
But mam yours sequence is 1,3,7..... and mine is 1,2,3,4.... dont u think then ans will vary then?
0

see if u are at 180, u can go anywhere either to  181 or 179; now lets say if it comes to 179;then why it will go to 181 (where diff is 2) .it will go to 178 from 179 ; since diff is 1 only ans sstf is used;

so u are doing just opposite of what qn has asked!

at every request we have to make sure that head changes its direction!!

hope u got it!!

0

According to the question there are 2048 tracks and head can start from any track.. (instead of 0-2047, i assumed tracks are 1-2048).

Here total 12 requests are satisfied.. if we consider head starting position as one request.

@srestha

0

@Verma Ashish

how r u telling

head can start from any track.

Starting position of head is given

0
It is given in the last line-- the head can start from any track.

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 Boss (25.5k points)
edited by
+1
Just like the prev given question, where the head was at 180, and the request sets are given...Similarly from where we are starting the sequence, we should assume the head to be resting at that position, and the remaining track numbers are to be included.
0
what is the correct answer 11 or 12?

can anyone explain how u arrive at this solution?
0
@gabbar how to take a sequence.........its why only 10 number??
0
In context of question it is 10  head at 180??
0
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.
by (277 points)
+1
As, initially no direction is given. So, isn't this Ambiguous ?
+1 vote

Let the head start from 1024.

Requests are: 344, 854, 982, 1014, 1022, 1025, 1028, 1045, 1109, 1364

Cardinality: 10
by Boss (33.8k points)
+1
1024 itself can be included in the set right? Then we start at 1024, first serve request for 1024 and then move to 1025 and so on. That will make the cardinality 11.
0
1024 should not be included in the set. Even in the first part of the question, 180th track which was the head was not included in the request set.

@Vaibhav
+1 vote
I am getting 11.

and request set is

0,1024,1280,1344,1360,1364,1367,1375,1407,1535,2047
by Boss (15.7k points)
+2

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

by (465 points)

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

by Loyal (5.3k points)