Disk Scheduling Algorithms

Introduction

A hard disk drive has a mechanical arm that moves a read/write head across the disk surface to reach different tracks. This physical movement (seeking) takes time — typically 3-15 milliseconds per seek. When multiple requests queue up for different disk locations, the order in which they are served dramatically affects total performance. Disk scheduling algorithms decide this order to minimize total seek time.

Think of it like an elevator deciding which floors to visit. A naive approach (serve requests in arrival order) might have the elevator going from floor 1 to floor 20 to floor 3 to floor 18 — wasting enormous time. A smarter approach (serve floors in one direction, then reverse) minimizes total travel. This is why SCAN is called the "elevator algorithm."

The Setup

Consider a disk with 200 tracks (0-199). The read/write head is currently at track 53. The request queue contains: 98, 183, 37, 122, 14, 124, 65, 67.

FCFS (First Come First Served)

Serve requests in arrival order.

Simple but potentially wild head swings.

SSTF (Shortest Seek Time First)

Always serve the request closest to the current head position.

Much better! But can cause starvation for distant requests.

SCAN (Elevator Algorithm)

Head moves in one direction, serving all requests along the way, then reverses direction.

No starvation, predictable behavior.

C-SCAN (Circular SCAN)

Head moves in one direction only. When it reaches the end, it jumps back to the beginning without servicing requests on the return trip. Provides more uniform wait times.

LOOK and C-LOOK

Like SCAN and C-SCAN but the head only goes as far as the last request in each direction (does not go all the way to 0 or 199).

Comparison

Modern Relevance

These algorithms were designed for spinning hard drives with mechanical arms. SSDs have no seek time (all locations are equally fast), making disk scheduling irrelevant for SSDs. However, HDDs are still used for large storage (NAS, data centers), and the concepts apply to any sequential-access optimization (elevator scheduling, robot arm movement, etc.).

Real-World Analogy

Disk scheduling is exactly like elevator scheduling in a building. FCFS is visiting floors in the order buttons were pressed (chaotic). SSTF is always going to the nearest requested floor (starves distant floors). SCAN is going all the way up, then all the way down (the standard elevator algorithm). C-SCAN is going up only and zipping back to the bottom to start again (like some express elevators).

Key Takeaways

• Disk scheduling optimizes the order of track requests to minimize total seek time
• FCFS is fair but slow; SSTF is fast but causes starvation
• SCAN (elevator) provides good performance without starvation
• C-SCAN provides more uniform wait times by servicing in one direction only
• LOOK/C-LOOK optimize SCAN/C-SCAN by not going to disk boundaries unnecessarily
• These algorithms are relevant for HDDs but not SSDs (which have uniform access time)
• Modern OS use variants of LOOK/C-LOOK with additional optimizations