Disk Scheduling Algorithms: FIFO, SSF, SCAN, C-SCAN

Posted on Mar 30, 2025 in Mechanical Engineering

Disk Scheduling Algorithms

A. B. C. D. E. F. G. H.

seek: 0. 0. 0. 0. 8. 8. 8. 14.

cyl req 12. 4. 10 2. 20. 3. 17. 4

If these requests are served in FIFO order, then the following sequence of seeks ensues:

At time 0, requests A, B, C, and D arrive. To serve A, we seek 4 cylinders outward from 8 to 12. At time 4, we seek 8 cylinders inward to reach cylinder 4 and serve B (meanwhile E, F, G arrive). At time 12, we seek 6 cylinders outward to 10 to serve C (meanwhile H arrives).

At time 18, we seek 8 cylinders inward to 2 to serve D.

At time 26, we seek 18 cylinders outward to 20 to serve E.

At time 44, we seek 17 cylinders inward to 3 to serve F.

At time 61, we seek 14 cylinders outward to 17 to serve G.

At time 75, we seek 13 cylinders inward to 4 to serve H.

At time 88, all requests have been serviced. The average seeks per request is 88/8 = 11 seeks.

(a) Shortest Seek First (SSF) Algorithm

At time 0, requests A, B, C, and D arrive.

We seek 2 cylinders outward from 8 to 10 to serve C.

At time 2, we seek 2 cylinders outward to 12 to serve A.

At time 4, we seek 8 cylinders inward to 4 to serve B (meanwhile E, F, G arrive). At time 12, we seek 1 cylinder inward to 3 to serve F.

At time 13, we seek 1 cylinder inward to 2 to serve D (meanwhile H arrives). At time 14, we seek 2 cylinders outward to 4 to serve H.

At time 16, we seek 13 cylinders outward to 17 to serve G.

At time 29, we seek 3 cylinders outward to 20 to serve E.

At time 32, all requests have been serviced. The average seeks per request is 32/8 = 4 seeks.

(b) Elevator Algorithm (SCAN)

Consider the initial movement of the disk head to go inward from cylinder 8.

At time 0, requests A, B, C, and D arrive. We seek 4 cylinders inward from 8 to 4 to serve B.

At time 4, we seek 2 cylinders inward to 2 to serve D.

At time 6, we start seeking outward toward request C at cylinder 10. When we reach cylinder 4 on the way out, E, F, and G arrive. Since we’re moving outward, we continue out to cylinder 10. We reach cylinder 10 at time 14 and serve C (meanwhile H arrives).

At time 14, we seek 2 cylinders outward to 12 to serve A.

At time 16, we seek 5 cylinders outward to 17 to serve G. At time 21, we seek 3 cylinders outward to 20 to serve E. At time 24, we seek 16 cylinders inward to 4 to serve H. At time 40, we seek 1 cylinder inward to 3 to serve F.

At time 41, all requests have been serviced. The average seeks per request is 41/8 = 5.125 seeks.

(c) Circular Elevator Algorithm (C-SCAN)

Consider the initial movement of the disk head to go inward from cylinder 8 and only service requests on the way in.

At time 0, requests A, B, C, and D arrive. We seek 4 cylinders inward from 8 to 4 to serve B.

At time 4, we seek 2 cylinders inward to 2 to serve D.

At time 6, we start sending the head outward to cylinder 12, which is currently the highest request. But while in motion, requests E, F, G arrive, and now the highest request is at cylinder 20. So the head continues to cylinder 20, requiring 18 seeks and serves E (meanwhile H arrives).

At time 24, we seek 3 cylinders inward to 17 to serve G.

At time 27, we seek 5 cylinders inward to 12 to serve A.

At time 32, we seek 2 cylinders inward to 10 to serve C.

At time 34, we seek 6 cylinders inward to 4 to serve H.

At time 40, we seek 1 cylinder inward to 3 to serve F.

At time 41, all requests have been serviced. The average seeks per request is 41/8 = 5.125 seeks.