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

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

jst fab ...

---

Awesome explanation 

@Debashish Deka

---

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

---

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? 

---

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

---

Yes, I also never explicitly said to start from the middle in the answer.

---

@Debashish from 5 you are going to 8 why not to 7?

---

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

---

@vishalshrm539, what impact will it make if 5 & 7 are equidistant from 6?

---

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.

---

got it, thanks a lot

---

This seems correct explanation rather than not giving reason why others have started from random numbers to bring the answer 11.

---

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?

---

I also have the same doubt. What is the significance of 180 in the question?

---

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$

---

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

---

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?

---

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

---

@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

---

@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

---

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

---

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

@Satbir

---

No starting position is not treated as a request.

---

Can anyone please comment on my doubt here. (@Satbir @dd)

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.

---

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.

---

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

---

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

---

See the daigram given by skscool007 in comments below question , it is also correct sequence and we will get $12$

---

Yeah saw that diagram now. :P

---

@Satbir 

the same thing i mentioned in my above comment

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

---

 @Verma Ashish, @rohith1001

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

---

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

https://gateoverflow.in/1786/gate2014-1-19 

---

https://gateoverflow.in/3535/gate2007-it-83?show=328929#c328929

please read this discussion.

---

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.

---

what if the initial head position is also a request, we can satisfy 11 other requests apart from the current head location. But if we consider the current head location as a request then I think it should be 12...

---

@Abhineet, we should not consider the current head position as a request because the question says that head has to change direction

---

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 ?