Disk Scheduling Strategies

Definition

Disk Scheduling: Determining the order in which disk I/O requests are serviced. Different algorithms optimize for seek time, fairness, or throughput.

Disk I/O Queue

Requests Arrive

I/O Queue:
[Request A: cylinder 80]
[Request B: cylinder 30]
[Request C: cylinder 120]
[Request D: cylinder 50]
[Request E: cylinder 100]

Current Head Position: cylinder 20

Scheduling Algorithm determines order!

Seek Time Metric

Access Time = Seek Time + Rotational Latency + Transfer Time

Rotational latency: Similar for all requests (~4ms)
Transfer time: Similar for all requests (~microseconds)

ONLY seek time varies!

Minimizing seek time = Minimizing access time

Common Scheduling Algorithms

1. FCFS (First Come First Served)

Algorithm: Serve requests in arrival order

Queue: [80, 30, 120, 50, 100]
Head at: 20

Head movement:
20 → 80 (distance 60)
80 → 30 (distance 50)
30 → 120 (distance 90)
120 → 50 (distance 70)
50 → 100 (distance 50)

Total seek distance: 60 + 50 + 90 + 70 + 50 = 320 cylinders

Characteristics:

  • ✓ Fair (no starvation)
  • ✓ Simple
  • ❌ Poor performance (random order)
  • ❌ Large seek distances

2. SSTF (Shortest Seek Time First)

Algorithm: Serve request closest to current head

Queue: [80, 30, 120, 50, 100]
Head at: 20

Closest: 30 (distance 10)
20 → 30 (distance 10)

Queue: [80, 120, 50, 100]
Head at: 30
Closest: 50 (distance 20)
30 → 50 (distance 20)

Queue: [80, 120, 100]
Head at: 50
Closest: 80 (distance 30)
50 → 80 (distance 30)

Queue: [120, 100]
Head at: 80
Closest: 100 (distance 20)
80 → 100 (distance 20)

Queue: [120]
Head at: 100
120 (distance 20)
100 → 120 (distance 20)

Total seek distance: 10 + 20 + 30 + 20 + 20 = 100 cylinders

Compare to FCFS: 100 vs 320 (3.2x better!)

Characteristics:

  • ✓ Better performance (minimizes seeking)
  • ✓ Greedy approach
  • ❌ Starvation risk (favors middle cylinders) 
    Requests for cylinders 0 and 200
Head at cylinder 100
New requests at 90, 110 constantly added
Requests to 0 and 200 never served!

3. SCAN (Elevator Algorithm)

Algorithm: Move head in one direction, service all requests, reverse direction

Queue: [80, 30, 120, 50, 100]
Head at: 20, moving right

Move right, serve all:
20 → 30 (distance 10)
30 → 50 (distance 20)
50 → 80 (distance 30)
80 → 100 (distance 20)
100 → 120 (distance 20)

At end, reverse direction
120 → 0 (distance 120) - if more requests
(return to start, repeat)

Total seek distance: 10 + 20 + 30 + 20 + 20 = 100 cylinders (same as SSTF)

Characteristics:

  • ✓ Good performance
  • ✓ Prevents starvation (all requests eventually served)
  • ✓ Fairer than SSTF
  • ❌ Slightly worse than SSTF for same queue

4. C-SCAN (Circular Scan)

Algorithm: Move in one direction, return to start without serving, repeat

Queue: [80, 30, 120, 50, 100]
Head at: 20, moving right

Move right, serve all:
20 → 30 (distance 10)
30 → 50 (distance 20)
50 → 80 (distance 30)
80 → 100 (distance 20)
100 → 120 (distance 20)

At end, jump back to start:
120 → 0 (distance 120) - WITHOUT serving

Move right again (if new requests added)

Total seek distance: 10 + 20 + 30 + 20 + 20 + 120 = 220 cylinders

Why worse than SCAN?: Wasted movement returning to start

Advantages:

  • ✓ More uniform wait times (no requests at far ends wait too long)
  • ✓ Fairer distribution

5. LOOK

Algorithm: Like SCAN but don’t go past last request

Queue: [80, 30, 120, 50, 100]
Head at: 20, moving right

SCAN would go 0-max
LOOK stops at last request:
20 → 30 (distance 10)
30 → 50 (distance 20)
50 → 80 (distance 30)
80 → 100 (distance 20)
100 → 120 (distance 20) - Stop here (last request)

Reverse direction (next requests assumed to arrive)

Don't seek to cylinder 0 if no requests there
Saves unnecessary movement!

Characteristics:

  • ✓ Better than SCAN/C-SCAN (stops at endpoints)
  • ✓ Prevents wasted seeking
  • ✓ Modern systems use this

6. C-LOOK

Algorithm: Like C-SCAN but stop at last request

Similar improvement over C-SCAN as LOOK over SCAN

Algorithm Comparison

Performance (Total Seek Distance)

Queue: [80, 30, 120, 50, 100]
Head at: 20

FCFS:   320 cylinders ▓▓▓▓▓▓▓▓
SSTF:   100 cylinders ▓▓
SCAN:   100 cylinders ▓▓
LOOK:   100 cylinders ▓▓
C-SCAN: 220 cylinders ▓▓▓▓▓
C-LOOK: 140 cylinders ▓▓▓

Fairness (Wait Time Variance)

Extreme cylinders (0, 200):
FCFS:   Equal chance (fair)
SSTF:   Starvation risk (unfair!)
SCAN:   Long wait (fair)
LOOK:   Long wait (fair)
C-LOOK: Relatively uniform (fair)

Practical Consideration

Algorithm | Performance | Fairness | Speed | Implementation
──────────┼─────────────┼──────────┼───────┼────────────────
FCFS      | Poor        | Good     | O(1)  | Simple
SSTF      | Good        | Poor     | O(n)  | Medium
SCAN      | Good        | Good     | O(n)  | Medium
LOOK      | Very Good   | Good     | O(n)  | Medium
C-LOOK    | Very Good   | Better   | O(n)  | Medium

Decision Factors

Minimizing Seek Time

SSTF or LOOK (minimize distance)

Fairness

SCAN, LOOK, or C-LOOK (no starvation)

Real Workload

Most modern systems: LOOK or C-LOOK Good balance of performance and fairness

Example Walkthrough: LOOK Algorithm

Detailed Scenario

Queue (in order of arrival):
Time 0: Request for cylinder 100
Time 1: Request for cylinder 50
Time 2: Request for cylinder 200
Time 3: Request for cylinder 10
Time 4: Request for cylinder 150

Head position: 25 (moving right initially)

LOOK Algorithm:
Move right, serve in order

25 → 50 (distance 25) time +5ms
50 → 100 (distance 50) time +12ms
100 → 150 (distance 50) time +12ms
150 → 200 (distance 50) time +12ms

At 200, no more requests to the right
Reverse direction

200 → 10 (distance 190) time +45ms

Total seek distance: 25 + 50 + 50 + 50 + 190 = 365 cylinders
Total time: ~75ms (at 5ms per 100 cylinders typical)

Compare to FCFS (arrival order: 100, 50, 200, 10, 150):
25 → 100 = 75
100 → 50 = 50
50 → 200 = 150
200 → 10 = 190
10 → 150 = 140
Total: 605 cylinders (1.7x worse!)

Modern Disk Scheduling

SSD Scheduling

SSD has no mechanical latency
Seek time irrelevant
All cylinders equally fast to access

No need for complex scheduling!
FCFS acceptable for SSD
(Simpler implementation, same performance)

Hybrid Scheduling

Modern systems mix approaches:
1. LOOK algorithm for standard requests
2. Adaptive scheduling based on workload
3. I/O priorities (some requests more important)
4. Deadline scheduling (ensure latency bounds)

Linux I/O Scheduler

CFQ (Completely Fair Queuing):
- Time slice for each process
- Fair CPU-like scheduling
- Each process gets I/O turns

Deadline:
- Ensures request latency bounds
- High priority for system I/O
- Good for real-time

noop (no operation):
- For SSD or high-speed devices
- FCFS, minimal overhead
- Ideal for SSD

Summary

Disk scheduling determines order of serving I/O requests. FCFS fair but slow. SSTF fast but risks starvation. SCAN/LOOK fair and fast. C-LOOK combines benefits. LOOK/C-LOOK common in modern systems. SSD makes optimization less critical (no mechanical latency). Linux pluggable schedulers allow tuning. Understanding algorithms important for appreciating I/O performance tuning and historical evolution.