Disk Scheduling in Operating Systems: 6 Algorithms with Worked Examples

An unstated direction or mishandled endpoint changes a disk-scheduling service order and total head movement. Compare FCFS, SSTF, SCAN, C-SCAN, LOOK and C-LOOK on one fixed queue and endpoint convention, with the full path and movement total for each. Keeping the workload fixed isolates the algorithm as the cause of different totals. This seek-distance model applies to rotating disks; SSDs have no moving head.

Related reading: FCFS and SSTF MCQs and disk access time.

Disk scheduling decides the next cylinder request

An HDD stores data on tracks, addressed here as cylinders. Pending read or write requests wait in a queue, and moving the disk head between cylinders creates seek distance. Disk scheduling chooses which pending cylinder to service next.

Head movement is the metric for these calculations; rotational latency and transfer time remain separate. For a complete head path:

total head movement = sum of |next cylinder - current cylinder|

Average head movement per request is total movement / number of requests. Do not divide by the number of distinct cylinders or by the largest cylinder number.

FCFS prioritises arrival order. SSTF prioritises the nearest request. SCAN-family methods sweep in a direction, while circular variants aim for more uniform waiting. The wider syllabus is mapped in GATE CS Exam Preparation.

Disk scheduling worked-example setup and conventions

Use the same dataset for all six algorithms:

• Cylinders: 0 through 199

• Starting head: 53

• Queue in arrival order: [98, 183, 37, 122, 14, 124, 65, 67]

• Requests: 8

• Initial SCAN-family direction: toward higher-numbered cylinders

Sorted once, the requests are [14, 37, 65, 67, 98, 122, 124, 183]. Around head 53, the lower side is [14, 37] and the higher side is [65, 67, 98, 122, 124, 183]. The starting head is not itself a request.

Under the endpoint convention used in these calculations, SCAN reaches physical endpoint 199, and C-SCAN travels from 199 to 0. LOOK and C-LOOK turn or wrap at the extreme pending requests instead. Both circular returns count as physical head movement. If a question states another convention, follow its wording.

FCFS and SSTF worked paths on the same queue

FCFS preserves arrival order:

53 -> 98 -> 183 -> 37 -> 122 -> 14 -> 124 -> 65 -> 67

The movement is:

45 + 85 + 146 + 85 + 108 + 110 + 59 + 2 = 640 cylinders

Average movement is 640 / 8 = 80.00 cylinders per request. FCFS is simple and arrival-fair, but the large reversals in this queue create a high seek distance.

SSTF repeatedly chooses the pending request closest to the current head:

53 -> 65 -> 67 -> 37 -> 14 -> 98 -> 122 -> 124 -> 183

Its movement is 12 + 2 + 30 + 23 + 84 + 24 + 2 + 59 = 236 cylinders, and its average is 236 / 8 = 29.50 cylinders per request.

From 53, request 65 is only 12 cylinders away. From 65, request 67 is 2 away. The closest lower requests then come before the remaining high requests. This local rule produces a smoother trace here, although it never plans the full path in advance.

SSTF saves 640 - 236 = 404 cylinders on this workload. That does not make it universally best. A continuing stream of nearby requests can postpone a distant request, so SSTF can cause starvation.

SCAN and C-SCAN include physical endpoints

SCAN moves upward first, services the higher requests, reaches the disk end, then reverses:

53 -> 65 -> 67 -> 98 -> 122 -> 124 -> 183 -> 199 -> 37 -> 14

The movement is 12 + 2 + 31 + 24 + 2 + 59 + 16 + 162 + 23 = 331 cylinders. Average movement is 331 / 8 = 41.375, reported as 41.38 cylinders per request.

The endpoint distance matters. After servicing 183, SCAN still travels 16 cylinders to 199 before reversing, then crosses 162 cylinders from 199 to request 37 on the lower side.

C-SCAN also services the higher side and reaches 199, but it then returns physically to 0 and continues upward through the lower side:

53 -> 65 -> 67 -> 98 -> 122 -> 124 -> 183 -> 199 -> 0 -> 14 -> 37

The movement is 12 + 2 + 31 + 24 + 2 + 59 + 16 + 199 + 14 + 23 = 382 cylinders. Average movement is 382 / 8 = 47.75 cylinders per request.

SCAN serves requests while moving in both directions. C-SCAN serves in one logical direction and uses the return trip to reset. Its extra reset distance in this example buys a more uniform direction of service, not a guaranteed lower total movement.

LOOK and C-LOOK stop at pending requests

LOOK follows SCAN's direction rule but does not visit 199 when no request lies beyond 183:

53 -> 65 -> 67 -> 98 -> 122 -> 124 -> 183 -> 37 -> 14

Its movement is 12 + 2 + 31 + 24 + 2 + 59 + 146 + 23 = 299 cylinders. Average movement is 299 / 8 = 37.375, reported as 37.38.

C-LOOK wraps from the highest pending request to the lowest pending request instead of using physical endpoints:

53 -> 65 -> 67 -> 98 -> 122 -> 124 -> 183 -> 14 -> 37

Its movement is 12 + 2 + 31 + 24 + 2 + 59 + 169 + 23 = 322 cylinders. Average movement is 322 / 8 = 40.25.

SSTF is lowest only for this example. Use Disk Scheduling MCQs: FCFS, SSTF, SCAN after you can reproduce the table.

Disk scheduling traps that change the answer

• Endpoint trap: Under this convention, SCAN reaches 0 or 199. LOOK turns at 14 or 183, the extreme pending requests. The names are not interchangeable.

• Direction trap: A SCAN-family order is incomplete until the initial direction is known. If the prompt omits it, state an assumption.

• Circular-jump trap: Under the convention used here, 199 -> 0 adds 199 cylinders and 183 -> 14 adds 169 cylinders. A question that excludes the reset produces a different total.

• Current-head request: With head 53 and a pending request at 53, movement is 0, and that request is serviced immediately.

• SSTF tie: With head 50, requests 40 and 60 are both 10 cylinders away. SSTF needs a stated tie-break rule.

Finally, disk scheduling is different from CPU process scheduling. Do not transfer a moving-head optimisation to SSDs as if their hardware had the same seek mechanics.

How GATE-style questions and interviews test disk scheduling

Common problem forms ask you to derive a service order, compute total or average movement, distinguish SCAN from LOOK, compare fairness and starvation, or explain why endpoint conventions produce different answers. A correct solution states the direction and endpoint convention before tracing the path.

Use this 60-second routine:

1. Write the starting head and cylinder bounds.

2. Sort the queue and split it below and above the head.

3. Mark the initial direction and any physical endpoints.

4. Trace the complete path.

5. Sum adjacent absolute differences.

The micro-check 40 -> 55 -> 50 gives 15 + 5 = 20, not merely |50 - 40| = 10. For broader revision, use Operating Systems for GATE: Deadlocks, Scheduling, Memory. Then test topic recall with Operating System MCQs.

Disk scheduling short version and next step

FCFS follows arrival order. SSTF chooses the nearest request but may starve distant work. SCAN and C-SCAN use physical endpoints under this convention, while LOOK and C-LOOK stop or wrap at pending-request extremes.

Hide the comparison table and recompute all six totals from head 53. Your targets, in algorithm order, are 640, 236, 331, 382, 299, 322. For structured concept revision, continue with GATE Guidance by Sanchit Sir.