Question

I/O Scheduling Algorithms

a) For each of the following scheduling algorithms, give a 1-2 sentence description of how it works. The description should be precise enough to distinguish each algorithm from the others. Algorithms: FCFS, SSTF, SCAN, C-SCAN, C-LOOK. (1 point)

b) Given a hard disk with 200 cylinders and a queue with jobs having the following cylinder requests: 80, 190, 70, 130, 30, draw a diagram of the movements of the head for each of the algorithms listed in part a) above. Assume the head is initially at cylinder 120 for each algorithm. Calculate the total movement of the head.   There are diagrams provided at the end of the assignment for you to use. For SCAN, C-SCAN, and C-LOOK assume that, at the point the requests above begin, the disk arm has been moving from smallest cylinder number to largest. Also, for C-SCAN and C-LOOK, do not count the ‘jump’.. (2 points each for a total 10 points)

c) Which algorithm gave the best result? Worst? Did you expect these results? Explain. (1 point)  Could you have gotten different best or worst results with a different ordering of these same cylinder requests? Note: ‘Different’ meaning that the algorithm with the best or worst results in now changed? If ‘yes’, give an example with algorithm results. If ‘no’, justify your answer.)

      0                                                                                                                                                                  199

Answer 1

a)

FCFS:

First Come First Serve is the simplest Disk Scheduling algorithm.

It services the IO requests in the order in which they arrive. There is no starvation in this algorithm, every request is serviced. for ex:

if the original order is 10, 8, 2 then the scheduling order will be 10, 8, 2.

SSTF:

Shortest Seek time first algorithm will schedule with respect to shortest distance from the current position.

Selects the disk I/O request which requires the least disk arm movement from its current position.

If the cursor is at 7, the original order is 10, 8, 2 then the scheduling order will be 8, 10, 2.

SCAN:

In SCAN algorithm, the scheduling will be in one direction from cursor till the end is reached and satisfies all requests in the path, then reverses the direction and satisfies all requests in path till end.

If the cursor is at 7, the original order is 10, 8, 2 then the scheduling order will be 2, 8, 10.

C-SCAN:

In SCAN algorithm, the scheduling will be in one direction from cursor till the end is reached and satisfies all requests in the path, then reverses the direction and reaches the end without serving any requests and serves the remaining requests.

If the cursor is at 7, the original order is 10, 8, 2 then the scheduling order will be 2, 10, 8.

C-LOOK:

It is similar to C-SCAN algorithm but the difference is when going in one direction the scheduling stops if there are no further request in that direction and reverses direction and cursor moves to the last request in that direction, processes the remaining requests.

b)

FCFS:

total distance = (120-80)+(190-80)+(190-70)+(130-70)+(130-30)

total distance = 430

SSTF:

least disk arm movement from 120 is 130, distance = 10

least disk arm movement from 130 is 80, distance = 50

least disk arm movement from 80 is 70, distance = 10

least disk arm movement from 70 is 30, distance = 40

least disk arm movement from 30 is 190, distance = 160

total distance = 10+50+10+40+160 = 270

total distance = 270

SCAN:

Now in the given problem the current head position is at 120,

assume we move left i.e towards 0

then the requests order will be: 80,70,30,0

then reverses the direction and order is: 130,190,200

total distance = (120-80)+(80-70)+(70-30)+(30-0)+130+(190-130) +10= 320

total distance = 320.skipping jump =>total distance = 320-130 = 190.

C-SCAN:

Now in the given problem the current head position is at 120,

assume we move left i.e towards 0

then the requests order will be: 80,70,30,0

then reverses the direction and order is: 200,190,130

total distance = (120-80)+(80-70)+(70-30)+(30-0)+200+(200-190)+(190-130) = 390

total distance = 390.skipping jump =>total distance = 390-200 = 190.

C-LOOK:

Now in the given problem the current head position is at 120,

assume we move left i.e inwards

then the requests order will be: 80,70,30

then reverses the direction and order is: 190,130

total distance = (120-80)+(80-70)+(70-30)+(190-30)+(190-130) = 310

total distance = 310.skipping jump =>total distance = 310-160 = 150.

c)

the best algorithm is SSTF the distance traveled is 270.

the worst result is from FCFS scheduling. distance traveled = 430

because while following SSTF the seek time is calculated before and will optimize the scheduling.

when following FCFS the scheduling is in original order no optimisation of scheduling and hence takes long time or travels more distance.

yes for other order we would have got different best and worst situations:

ex: 30,70,80,130,190

the best case will be using FCFS , total distance = 40+10+50+60+90 = 250.

the worst case will be using C-SCAN, total distance = 390(same as in question b).