The Gateway to Computer Science Excellence
+26 votes
6.8k views
Suppose the following disk request sequence (track numbers) for a disk with $100$ tracks is given:

$45, 20, 90, 10, 50, 60, 80, 25, 70.$

Assume that the initial position of the R/W head is on track $50$. The additional distance that will be traversed by the R/W head when the Shortest Seek Time First (SSTF) algorithm is used compared to the SCAN (Elevator) algorithm (assuming that SCAN algorithm moves towards $100$ when it starts execution) is________________tracks.
in Operating System by Boss (30.8k points)
edited by | 6.8k views
0

assuming that SCAN algorithm moves towards 100 when it starts execution

if this is not given what will default case for scan?

0
try both the cases.
0
Both from 50 to 0 and from 50 to 100 ?
0
Yes, but it will be mentioned in the question i guess.
+1

please anyone tell what is the answer 10 or -10 or 0  

as  different people saying different answer and selected one as Hence, not additional but 140−130=10  140−130=10 less head movements SSTF takes.

0
Generally we move from lower cylinder to higher cylinder in SCAN that is inner most track to outer most track
0
@learner_geek how can disk movements be negative?
0
In case of SCAN , why we are not going till 1  ?
+1
@rohan30 coz 10 is the last request to be served. If our head initially moved from 50 to 0 then we would have reached 1 but then not 100.
0
Thanks @tusharp
+2
I think they didn't frame the question correctly- they are asking additional distance over SCAN algo. using SSTF algo. which is 0. There isn't any additional distance.

5 Answers

+49 votes
Best answer

check : http://www.cs.iit.edu/~cs561/cs450/disksched/disksched.html

So, for SSTF it takes $130$ head movements and for SCAN it takes $140$ head movements.

Hence, not additional but $140-130 = 10$ less head movements SSTF takes.

by Boss (30.8k points)
selected by
+7
If we consider disks numbered 1-100, we will get the no of movements in SCAN as 140.So the answer will change then. Can you please comment on this ? I took the disk numbered 1-100 as it was mentioned in the question that for SCAN, the head moves towards "100" .
0

What you said is correct. We should prefer taking numbering from 1-100 in such a case.

+2

so, Amar , should it be -10 ?

+1

Yes, Link given in this answer supports that by stating "Scan is more optimal than SSTF". But is it always the case? I doubt that.

+2
In this question, SSTF is more optimal than Scan.  So, it should not be always the case..
0
in scan Alogrithm is it needed to go to 100(last track) why doesn't it turn back after 90?it would be efficient
0
140-130 or 130-120??
+2
140-130
+2
As it is not explicitly mentioned in the question from where the tracks start, I took 100 tracks as 0 - 99 and by that approach I'm getting head movement for SCAN as 138 !

So my question is when to consider 0-99 and when 1-100 ??
+18

@just_bhavana I wqas also having the same doubt. But they have given a hint in the question itself by saying it is moving towrds 100.If numbering was 0-99 then question should say moving towards 99 and not 100

0
Same thing same doubt
+1
Why answer cannot be 0 as SSTF did not cover any additional distance/?
0
please provide me theory part of this...actually i dont have any idea about these algorithms
0

@https://gateoverflow.in/user/rahul+sharma+5 same doubt why it is 10 as SSTF need to travel 10 lesser than SCAN  so additional should be ZERO(0)

0
SSTFis best always,,,take any case
0
moving toward 100 means question giving us direction of scan not say to visit 100. if we visit 100 there is no difference betwn scan and c-scan???
+2
why we are not going till 1 ? we stopped at 10. In case of scan we go till the end and hence we go  till 100 but then not same at left side. correct me if i am wrong
0
Shouldn't the answer be -20 as SSTF will make 20 less head movements?? @Arjun sir plz help
0
In case of SCAN why are we not going till 1?

The read write head is going till 100 but in other direction it must go till 1 right?

why are we stopping at 10?
0
why track numbers are numbered 1-100 why not 0-99?
0
why we are marking the answer as 10 and why not -10.  as we found out that the cylinder moment is less in sstf in compare to scan method....
0
Because question says,"moving towards 100",that means there is a physical track which is numbered as 100
0

@amarVashishth @srestha @Arjun @Satbir

https://gateoverflow.in/88222/gate1989-4-xii

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

Why in the figure we are considering the request of 50 again in case of SSTF as it is not taken into consideration in these similar kind of question.

Answer remains same here but still do we need to consider that or not & same doubt for SCAN also ?

0

@Kushagra गुप्ता

 We need not consider request of 50 when coming back from 90(incase of sstf) or 100(incase of scan). Because new requests are not being added while servicing existing requests...

Either it must be mistake in the diagram or they might have marked it to show the number of head movements between rhe cylinders..

Hope this clears..

+11 votes

SSTF:

Initial position 50. So, shortest sequence will be 

50 45 60 70 80 90 25 20 10 

and the corresponding distances will be

0 5 15 10 10 10 65 5 10

giving total distance of 130.

SCAN:

Here requests from 50 are serviced in ascending order of their track number (as the movement is from 50 to 100) and at the end of the sequence, the remaining requests are serviced in the descending order. So, the service order will be

50 60 70 80 90 45 25 20 10

and the corresponding distances

0 10 10 10 10 45 20 5 10

giving a total distance of 120

So, extra distance of SSTF = 130 - 120 = 10

Ref: http://courses.cs.vt.edu/cs2506/Fall2014/Notes/L17.IOScheduling.pdf

by Veteran (431k points)
+1
actually at the time of counting in scan algo i did mistake ..
thank you arjun sir ..
+26
Sir, the question is regarding SCAN but I think you are using LOOK, that's why you have returned after 90 and not gone till 100, please correct me if I am wrong.
+1
In SCAN , head moves to other end of disk and then starts moving in opposite direction , here why we have taken till last track request before moving in opp direction  as 90 and  not 100 ? If we take 90 as last track request before moving in opp direction then won't it be LOOK scheduling ??

Plz explain..
+1

here, LOOK algorithm has been used instead of SCAN (elevator) algorithm.
Its called elevator algorithm cause, during early years of Elevators it used to go all the way to top before it can start to move in the opposite direction.

also, check : http://www.cs.iit.edu/~cs561/cs450/disksched/disksched.html

0

@Arjun Sir, Please address this issue this(http://www.cs.iit.edu/~cs561/cs450/disksched/disksched.html) resource have conflict(in C-Scan and C-look algo) with Galvin's book also please also check these two(on disk scheduling)
https://gateoverflow.in/108475/

Answer to Gate 2016-1-48 don't match using cs.iit.edu resource.

https://gateoverflow.in/39716/gate-2016-1-48 Comments Comment1 and Comment2

–1
Yes, Arjun sir is right! Scan means only goes till Max or Minimum side and in the case of C-Scan(Complete scan) goes till the boundary value!
0
sir y r u not considering 100?? as the question says using scan algo ...
0
100 is considered, chk again
+3
according to scan

45, 20, 90, 10, 50, 60, 80, 25, 70.  R/W head is on track 50

50->60->70->80->90->100>45->25->20>10

so (60-50)+(70-60)+(80-70)+(90-80)+(100-90)+(100-45)+(45-25)+(25-20)+(20-10)

=10+10+10+10+10+55+20+15+10

=140

right??
0
what to follow galvins definition right?
+1
@Puja yes.

@sushmita yes Galvin
0
Thanx sretha.
0
in scan method we will go till the end of the cylinder not till the last request in moving side of the head
0

@Arjun sir

@Deepakk Poonia (Dee) sir

can you please explain me how answer is 10.

according to me

using SSTF distance traversed = 130

using SCAN distance traversed =140

so additional distance traversed on using SSTF compared to SCAN is 0 because SSTF is traversing less distance as compared to SCAN

+5 votes

SSTF:

Initial position 50. So, shortest sequence will be 

50 45 60 70 80 90 25 20 10 

and the corresponding distances will be

0 5 15 10 10 10 65 5 10

giving total distance of 130.

SCAN:

Here requests from 50 are serviced in ascending order of their track number (as the movement is from 50 to 100) and at the end of the disk ( not sequence as in LOOK scheduling), the remaining requests are serviced in the descending order. So, the service order will be

50 60 70 80 90 100 45 25 20 10

and the corresponding distances

0 10 10 10 10 10 55 20 5 10

giving a total distance of 140

So, extra distance of SSTF = 130 - 140 = -10

SOURCES ::

http://www.cs.iit.edu/~cs561/cs450/disksched/disksched.html

http://www4.comp.polyu.edu.hk/~csajaykr/myhome/teaching/eel358/ds.pdf

by Active (1.2k points)
edited by
0
As per references both versions exist. Still "additional" in question gives a hint to which version to take. Lets see what GATE key says.
0
@arjun sir,

Can you make the final comment for the question please.
+3
Well "10" was the answer in GATE key. I would have still marked "10". GATE questions values "English grammar" and it does not make sense to say "-10" with additional. I see that most test series questions are so off in this regard.
0
@Sir, thanks for the update.
0
@Arjun sir,

Can't we imagine "-10" as not additional but deficiency in  disk movements when SSTF compared with SCAN ?
–1 vote
In SSTF Request processed in given order..

50->45->60->70->80->80->90->25->20->10

So, In SSTF total Head movement =

(50-50)+(50-45)+(60-45)+(70-60)+(80-70)+(90-80)+(90-25)+(25-20)+(20-10)

0+5+15+10+10+10+65+5+10=130

In SCAN request processed in order.....

50->60->70->80->90->45->25->20->10

So, In SSTF total Head movement =

(60-50)+(70-60)+(80-70)+(90-80)+(90-45)+(45-25)+(25-20)+(20-10)

10+10+10+10+45+20+5+10=120

In SCAN total Head Movement .  120

So in SSTF extra distance covered compred to SCAN 130-120= 10
by Active (1.8k points)
0
it is look not scan
0
what you told is look not scan...
+1
because in SCAN we're supposed to reach the disk end and then traverse to the other side, while in look we can change direction after the last request in the direction in which disk head is moving (no need to reach the disk end)

Source : Operating system by Galvin
–3 votes

when the Shortest Seek Time First (SSTF) algorithm used we get 130
when the SCAN (Elevator) algorithm is used we get 120
The additional distance that will be traversed =130-120 =10

 

by Active (5k points)
edited by
0
if 100 was not considered to be hit during scan then what will be difference between scan and look. by the way if we consider 100 during scan we should also consider 0 no??
0
we won't consider to go to zero(0) because the requests will be over at 10 only so no need to go for ahead to zero.
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,306 answers
198,314 comments
105,011 users