Disk Scheduling - I/O Optimization

Introduction

When multiple processes simultaneously request disk I/O, the operating system must decide the order in which to service these requests. Since the disk head must physically move to the correct track for each request, the order matters enormously — a poor ordering can result in the head traveling back and forth across the entire disk, while an optimal ordering minimizes total head movement and reduces average access time.

Disk scheduling is primarily relevant for magnetic HDDs where seek time dominates. For SSDs (which have no moving parts), scheduling is less critical — but understanding these algorithms remains important for the many HDD-based systems still in operation and for exam preparation.

Why Disk Scheduling Matters

Consider a disk with 200 tracks (0-199) and a request queue: [98, 183, 37, 122, 14, 124, 65, 67]. Head starts at track 53.

Random order (no scheduling): Head moves 53→98→183→37→122→14→124→65→67 Total movement: 45+85+146+85+108+110+59+2 = 640 tracks

Optimized order (SCAN): Total movement could be as low as 236 tracks.

That is a 2.7x improvement — directly translating to faster disk performance.

FCFS (First Come First Served)

Service requests in the order they arrive. Simple but often poor performance.

Example: Queue: [98, 183, 37, 122, 14, 124, 65, 67], Head at 53

Advantages: Fair, simple, no starvation. Disadvantages: Poor performance (wild head swings), no optimization.

SSTF (Shortest Seek Time First)

Always service the request closest to the current head position. Greedy approach.

Example: Same queue, head at 53

Advantages: Better average performance than FCFS. Disadvantages: Can cause starvation (requests far from head may wait indefinitely if closer requests keep arriving). Not optimal globally.

SCAN (Elevator Algorithm)

The head moves in one direction, servicing all requests until it reaches the end, then reverses direction. Like an elevator in a building.

Example: Head at 53, moving toward 0 (left direction first)

Advantages: No starvation, better average than FCFS, bounded waiting time. Disadvantages: Requests just visited may wait almost two full sweeps. Going all the way to the end wastes time if no requests are there.

C-SCAN (Circular SCAN)

Like SCAN but head only services requests in one direction. When it reaches the end, it jumps back to the beginning without servicing requests on the return trip. Provides more uniform wait times.

Example: Head at 53, servicing in increasing direction

Note: The "jump" time is usually counted as the full distance (199) or treated separately depending on the problem context.

Advantages: More uniform response time than SCAN (no bias toward middle tracks). Disadvantages: Slightly higher total movement than SCAN due to the return trip.

LOOK and C-LOOK

Improved versions of SCAN and C-SCAN. Instead of going all the way to the physical end of the disk, the head reverses at the LAST request in that direction.

LOOK Example: Head at 53, moving left

C-LOOK: Service in one direction only, jump from last request to first request in queue (not to physical track 0).

Algorithm Comparison

Choosing the Right Algorithm

• FCFS: Use only when I/O load is very light (few pending requests)
• SSTF: Good throughput but unfair — avoid for real-time systems
• SCAN/LOOK: Good balance of throughput and fairness — default choice for most systems
• C-SCAN/C-LOOK: Best for systems requiring uniform response time

Disk Scheduling in Modern Linux

Linux implements multiple I/O schedulers:

Modern schedulers operate on multi-queue architectures that handle thousands of concurrent I/O operations efficiently.

Key Takeaways

• Disk scheduling optimizes head movement to reduce total seek time
• FCFS is simple but wastes significant movement on random access patterns
• SSTF minimizes local seek but can starve distant requests
• SCAN (elevator) provides good balance of throughput and fairness
• LOOK variants improve SCAN by not traveling to physical disk ends
• C-SCAN/C-LOOK provide most uniform wait times (no directional bias)
• For SSDs, disk scheduling is unnecessary — use noop/none scheduler