need ur approach here

The Gateway to Computer Science Excellence

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

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

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

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

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

0

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

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

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

(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

the same thing i mentioned in my above comment

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

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.

+51 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:

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

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

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

0

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

Best answer also considers that head can start at any position.

Best answer also considers that head can start at any position.

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.

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

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

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

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

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.

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.

Request are generated as $1366,1365,1368,1361,1376,1345,1408,1281,1536,1025,20148,1$ and the head is pointing to $1366$ initally.

+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

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

Please correct me if wrong.

0

@Arjun Sir, please read the 2nd comment.

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

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

50,833 questions

57,699 answers

199,397 comments

107,480 users