Skip to content
Tutorials Center
My learning

Topics

Lesson 54 of 66 ยท I/O and Disk Scheduling

Disk Scheduling Algorithms (FCFS, SSTF, SCAN, LOOK)

Compare FCFS, SSTF, SCAN, C-SCAN, LOOK and C-LOOK disk scheduling with a worked example, total head movement, starvation and fairness, and run every algorithm in Python.

On a hard disk, the slowest thing you can do is move the arm. If several processes have requests waiting for different tracks, the order in which the OS serves them decides how far the arm travels in total. Disk scheduling is the policy that chooses the next request to serve. A good one raises throughput, lowers average waiting time and keeps any single request from waiting forever.

Throughout this lesson we use the same textbook-style workload so the algorithms are easy to compare. The disk has tracks 0 to 199, the head is at track 53, and the queue holds requests for tracks:

TEXT
98, 183, 37, 122, 14, 124, 65, 67

The cost we measure is total head movement: the sum of the distances between consecutive tracks visited. See disk access time for why seek distance matters so much.

What a scheduler tries to achieve

  • Throughput: serve as many requests per second as possible.
  • Low average response time and low variance (predictability).
  • Fairness: no request starves.
  • Low overhead: the decision must be cheap.

Scheduling only makes sense while there is a queue. With one request at a time every algorithm behaves the same.

FCFS (First Come, First Served)

Serve requests in arrival order. It is fair and simple, but the arm swings wildly.

Path: 53, 98, 183, 37, 122, 14, 124, 65, 67. Distances: 45 + 85 + 146 + 85 + 108 + 110 + 59 + 2 = 640 tracks.

SSTF (Shortest Seek Time First)

Always pick the pending request closest to the current head position. It resembles Shortest Job First, and like SJF it has good throughput but can starve requests that are far from the busy area: a steady stream of nearby requests can keep the arm away from a distant one indefinitely.

Path: 53, 65, 67, 37, 14, 98, 122, 124, 183. Total: 12 + 2 + 30 + 23 + 84 + 24 + 2 + 59 = 236 tracks.

SCAN (the elevator algorithm)

The arm sweeps in one direction, serving every request on the way, goes all the way to the end of the disk, then reverses and sweeps back. Like an elevator it serves everything in its path before turning around. It avoids starvation, because every request is reached within two sweeps, and it keeps the variance low, though tracks in the middle are visited more often than tracks at the edge.

Moving toward 0 first: 53 to 37, 14, then to 0, then up to 65, 67, 98, 122, 124, 183. Total: 53 + 183 = 236 tracks.

C-SCAN (Circular SCAN)

Sweep in one direction only. When the arm reaches the end, it jumps back to the beginning without serving anything on the return trip, then sweeps again. Every track gets the same average wait because requests are always served in the same direction. Whether the return jump counts as head movement is a convention; it is quick and many textbooks include it.

LOOK and C-LOOK

SCAN and C-SCAN wastefully run to the physical edge even if no requests are there. LOOK reverses at the last request in each direction, and C-LOOK jumps from the last request to the first request of the other end. They are the practical versions used in real systems.

LOOK toward 0 first: 53, 37, 14, then up to 65, 67, 98, 122, 124, 183: (53 - 14) + (183 - 14) = 39 + 169 = 208 tracks.

flowchart LR
    A["FCFS<br/>arrival order"] --> B["SSTF<br/>closest first"]
    B --> C["SCAN<br/>sweep to the ends"]
    C --> D["C-SCAN<br/>one-way sweep"]
    C --> E["LOOK<br/>turn at last request"]
    D --> F["C-LOOK<br/>jump to first request"]

From the simplest policy to the practical ones.

Run them all

This program implements every algorithm and prints the service order and total movement.

Python Six disk scheduling algorithms

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The totals are 640, 236, 236, 382, 208 and 322. The C- variants count the long return jump, which is why they look worse in a single batch; their advantage is uniform waiting under continuous load.

Starvation in action

SSTF is greedy. Watch a far request wait while new nearby requests keep arriving.

Python SSTF starving a distant request

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

After 30 ticks the arm is still wandering around the low tracks, nowhere near 190. Real schedulers fix this with aging (raise the priority of old requests) or with deadlines, as Linux's deadline and BFQ schedulers do.

Algorithm comparison

Algorithm Head movement Fairness Starvation Notes
FCFS High Fair None Simple, poor under load
SSTF Low Unfair Possible Greedy, like SJF
SCAN Moderate Better None Elevator; middle favoured
C-SCAN Moderate Uniform waits None One direction only
LOOK Low Better None Practical SCAN
C-LOOK Low-moderate Uniform waits None Practical C-SCAN

Other variants you may meet: LIFO (serve the newest request, good locality but starves old ones), N-step SCAN and FSCAN (freeze the queue during a sweep so new arrivals cannot postpone it), and RSS (random, used as a baseline).

What real systems do

  • The choice depends on the load: with a light load, FCFS and SSTF behave alike; with a heavy load, SCAN-family algorithms perform best.
  • Modern drives reorder internally (command queueing) and hide their real geometry, so OS-level elevator logic is less exact than the textbooks suggest.
  • File layout matters as much as scheduling: allocating a file's blocks close together (allocation methods) shortens every seek.
  • For SSDs, there is no arm, so Linux uses none or mq-deadline; the goal there is fairness and latency, not seek distance.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which disk scheduling algorithm can cause starvation?

    SSTF always chooses the nearest request, so a distant request can wait indefinitely while closer ones keep arriving.
  2. 2. How does LOOK differ from SCAN?

    SCAN goes to the physical edge; LOOK turns around as soon as there are no more requests in that direction.
  3. 3. Why does C-SCAN give more uniform waiting times than SCAN?

    In SCAN the middle tracks are passed twice per cycle and the edges once. C-SCAN treats all tracks alike.
  4. 4. Head at 53, queue 98, 183, 37, 122, 14, 124, 65, 67. What is the total head movement under FCFS?

    45 + 85 + 146 + 85 + 108 + 110 + 59 + 2 = 640.
  5. 5. Which statement about SSDs is most accurate?

    Flash has no seek time, so the scheduler mostly works on fairness and latency.

Summary

  • Disk scheduling orders pending requests to reduce head movement, improve throughput and keep waits fair.
  • FCFS is fair but slow; SSTF is fast but can starve; SCAN and C-SCAN sweep the disk; LOOK and C-LOOK turn at the last request.
  • On the classic example the totals are FCFS 640, SSTF 236, SCAN 236, LOOK 208.
  • Aging, deadlines and N-step variants prevent starvation; SSDs need little seek scheduling.

Next: Disk Management, Swap Space and RAID