edited by
23,447 views
37 votes
37 votes
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.
edited by

5 Answers

Best answer
76 votes
76 votes

Refer : 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.

edited by
15 votes
15 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

6 votes
6 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

edited by
–1 votes
–1 votes
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
Answer:

Related questions

48 votes
48 votes
6 answers
3
makhdoom ghaya asked Feb 12, 2015
12,167 views
The following two functions $P1$ and $P2$ that share a variable $B$ with an initial value of $2$ execute concurrently.$$\begin{array}{|l|l|}\hline \text{P1() \{ } & \tex...
31 votes
31 votes
2 answers
4