need ur approach here

The Gateway to Computer Science Excellence

+55 votes

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?

- $9$
- $10$
- $11$
- $12$

+3

Hi Guys,

This is good question. Think on following points -

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

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

0

thank you @ Chhotu for comment

Hi Guys,

This is good question. Think on following points -

- Why can we not have multiple seek series ?
- Why is greedy algo. working ?
- Why are we starting from 1 ?
- 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 **

+54 votes

Best answer

We need **two** conditions to satisfy:

- The
**alternating direction**with**shortest seeks time first policy**. - 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$

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

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

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

if we go to 7 from 5, then 6 will have two equal distances on either sides (5 & 7), which we don't want.

+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

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?

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$

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

Anyone please reply,,

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

+48 votes

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:

+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?

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?

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

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

In the given answer,the statement:-

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 . Can u plz explain what is wrong with this approach.... It is following SSTF as well as alternating sequence

0

0

hey your answer is wrong ! Pawan Kumar 2

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

+18 votes

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

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

+4 votes

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 vote

Answer: B

Let the head start from 1024.

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

Cardinality: 10

Let the head start from 1024.

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

Cardinality: 10

+1 vote

I am getting 11.

Suppose head is at 1365

and request set is

0,1024,1280,1344,1360,1364,1367,1375,1407,1535,2047

Suppose head is at 1365

and request set is

0,1024,1280,1344,1360,1364,1367,1375,1407,1535,2047

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,645 questions

56,586 answers

195,788 comments

101,839 users