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

Dark Mode

17,879 views

86 votes

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?

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

0

edited
Jan 30, 2021
by tusharSingh

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

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.

1

83 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,\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$

0

1

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$

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

1

55 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:

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.

That's why they mentioned in the question 180, so that everyone will get same answer as 11.

0

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