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

edited | 6.9k 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.

+8

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 :)
+3

Why is everyone saying 11?

The ans should be 12 and here is how...   0
see my answer below $11$ is correct , not $12$.

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 (57.3k points)
edited
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.
0

Can anyone please comment on my doubt here.

I completely agree with @chauhansunil20th and I think the answer is 8.

The sequence is: 181,178,188,170,201,138,265,10,521 --> This will give 8 times change in direction of the head. If we include the first direction as well, then we will get answer as 9.

Here's how I got the sequence.

To get the sequence we should cumulatively add the below numbers with initial number as 180. Here is the sequence.

+1 -3 +7 -15 +31 -63 +127 -255 +511 -1023 +2047

This will give us: 181, 178, 185, 170, 201, 138, 265, 10, 521, -502, 1545.

Please note that the cylinder number -502 is negative. Assuming cylinder numbering starts from 0, this negative cylinder number is not valid and hence can't be considered. If we ignore this negative cylinder number, we will get 8 times change in direction of the head.

We can even try cumulatively adding the below sequence to initial cylinder number 180 as well.

-1 +3 -7 +15 -31 +63 -127 +255 -511 +1023 -2047

This will give us: 179, 182, 175, 190, 159, 222, 95, 350, -161, 862, -1185

Please note here also the 2 cylinder numbers -161 and -1185 are negative. If we ignore these negative cylinder numbers we will get only 7 times change in direction of the head.

Hence maximum number of times cylinder head changes its direction is 8.

0

The two statements(shown below in block quotes) are making the question ambiguous.

The head is initially positioned at track number 180.

if the total number of tracks are 2048 and the head can start from any track?

If we take initial track as 682 we can get maximum of 11 requests. If we also include the initial request (682) it becomes 12 requests.

0

@rohith1001

There is no ambiguity , question is clearly saying

What is the maximum cardinality of the request set  if the head can start from any track

so 180 does not matter. and i think 12 is correct answer.

0
The possible sequence of requests taking 682 as initial track is shown below. (taking 800 as initial track it is not possible to have 11 requests, it will exceed 2047 tracks. I have edited my previous comment.)

(682), 683, 680, 687, 672, 703, 640, 767, 512, 1023, 0, 2047

11 requests in total, if we consider the initial request it becomes 12 :)
0
See the daigram given by skscool007 in comments below question , it is also correct sequence and we will get $12$
0
Yeah saw that diagram now. :P
0

the same thing i mentioned in my above comment

​​​​​​ And you replied that we shouldn't have to consider initial one. :/

+1

see my answer below , $11$ is correct answer, $NOT$ $12$

0

@dd

1.Don't we need to calculate initial position as a one request to get max no. of requests ?

Suppose if we are starting from the position X, then do we need to consider X as one request or not ?

If we don't consider initial position then we will get the ans as 11. otherwise ans should be 12.

Can anybody clarify my doubt.

2. in the below given question initial position also considered as one request.

0
0
should we not consider the case when head is at track x and the first request is for the same track x.and after that we apply the same approach. Then ans will be 12. 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 (119k 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 ?
+3
@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!!

+1

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.

0

I think as it is given, 180 should be one of the requests made by the system. So, the proper "diagram" should be: Hence answer is 11 and cannot be 12 in any case.

0

head can start from any track. If you start from 180 then you'll get 10requests served.

yes 11 is correct answer but it should've to start from 1366 and we should not have to consider start position of head as a request.

0
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.
0
Question is edited.. see once more
0
Yes, now answer should be 12. Sorry, I didn't see the edit.
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.7k 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.9k 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 (16k 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....

+1 vote
We can start from any track.

$1366\overset{-1}{\rightarrow}1365\overset{+(1+2)}{\rightarrow}1368\overset{-(3+4)}{\rightarrow}1361\overset{+(7+8)}{\rightarrow}1376\overset{-(15+16)}{\rightarrow}1345\overset{+(31+32)}{\rightarrow}$$1408\overset{-(63+64)}{\rightarrow}1281\overset{+(127+128)}{\rightarrow}1536\overset{-(255+256)}{\rightarrow}1025\overset{+(511+512)}{\rightarrow}2048\overset{-(1023+1024)}{\rightarrow}1$

$-$ indicates we are going in left direction

$+$ indicates we are going in right direction.

$new\ distance = previous\ distance +( previous\ distance + 1)$

$+1$ is used to remove ambiguity when choosing next track.

Hence Option $D. \ 12$ is correct answer.
by Boss (25.1k points)
edited by
0
Did you mean 1366 also included ?

But note that, it is start of the sequence you assumed.. So it is not counted as request.
+1
I have assumed that $1366$ is the 1st request and coincidentally head was also pointing to it.

Request are generated as $1366,1365,1368,1361,1376,1345,1408,1281,1536,1025,20148,1$ and the head is pointing to $1366$ initally.
0
Convincing point, but still have doubt about that request.
+1

@Satbir then it violate the requirement that head changes its direction after every request.

I just modified the question to remove the part which was actually meant for question number 82.

0

Sir, in my answer the directions are denoted by + and - signs and they are changing after processing every request.

+1
The question is whether to count the first one or not -- it shouldnt be
0

Why we are not counting the first one ?  I have considered $1366$  also as a request. Please explain.

0
Let We are at some track, can't we have request to same track again?

If yes, then we have to count the initial one too...

After servicing this request, head move to either left or right which is indirectly meaning, head changes it's direction.
+4
We can have request to same track but then the head won't change its direction and this violate the condition given in question.
correct answer C 