Disk Scheduling (SCAN, C-SCAN)

Disk Scheduling (SCAN, C-SCAN)

Why This Matters

Think of disk scheduling like an elevator. When you press buttons on different floors, the elevator doesn't go to them in random order—it uses a strategy (like going up, then down) to minimize travel time. Disk scheduling does the same for disk I/O—it orders read/write requests to minimize disk head movement, improving performance.

This matters because disk I/O is slow (milliseconds vs nanoseconds for memory). If the disk head moves randomly between requests, it wastes time seeking. Disk scheduling algorithms (SCAN, C-SCAN, SSTF) optimize this by ordering requests to minimize seek time. This can significantly improve I/O performance.

In interviews, when someone asks "How does the OS optimize disk I/O?", they're testing whether you understand disk scheduling. Do you know how SCAN works? Do you understand seek time optimization? Most engineers don't. They just read/write files and wonder why it's slow.

What Engineers Usually Get Wrong

Most engineers think "disk scheduling is automatic and I don't need to worry about it." But understanding disk scheduling helps you understand I/O performance. If you're making many random disk reads, disk scheduling can't help much—the head moves all over. Sequential reads are much faster because the head moves in one direction.

Engineers also don't understand that modern SSDs don't have moving parts, so traditional disk scheduling (which optimizes seek time) doesn't apply. SSDs have different characteristics—they're fast for both random and sequential access. But the OS still uses scheduling algorithms for fairness and to optimize for SSD characteristics.

How This Breaks Systems in the Real World

A service was doing many random disk reads. The disk head was moving all over the place, causing high seek times. I/O performance was poor. The service was slow. The fix? Optimize for sequential access. Batch reads, use read-ahead, or use SSDs (which don't have seek time). Understanding disk scheduling helps you understand why sequential I/O is faster.

Another story: A service was using a disk scheduling algorithm (SCAN) that favored requests in one direction. Requests in the opposite direction waited a long time (starvation). Some requests never completed. The fix? Use a fairer algorithm (like C-SCAN, which serves requests in one direction then immediately returns), or use deadline scheduling to prevent starvation.

---

Examples

Example 1: SCAN Algorithm

Scenario: Disk with tracks 0-199, head at track 50, requests at [10, 100, 20, 80, 30]

SCAN execution (moving right first):

Current: 50
Moving: Right
Order: 50 → 80 → 100 → 20 → 30 → 10 (reverses at end)
Head movement: 30 + 20 + 80 + 10 + 20 = 160 tracks

FCFS (for comparison):

Order: 50 → 10 → 100 → 20 → 80 → 30
Head movement: 40 + 90 + 80 + 60 + 50 = 320 tracks

Benefit: SCAN reduces head movement by 50%!

Example 2: C-SCAN vs SCAN

Scenario: Requests at tracks [10, 50, 100, 150, 190], head at 100

SCAN:

100 → 150 → 190 → 10 → 50
Wait time for track 10: 90 tracks (must wait for reversal)

C-SCAN:

100 → 150 → 190 → 0 → 10 → 50
Wait time for track 10: 90 tracks (immediate return)
More uniform wait times

Example 3: SSTF Starvation

Scenario: Head at 50, requests at [51, 52, 53, 10]

SSTF execution:

50 → 51 → 52 → 53 → 10
Track 10 waits while closer requests are served (starvation)

SCAN (fairer):

50 → 51 → 52 → 53 → 10 (if moving right, serves all before reversing)
More fair, prevents starvation

---

Common Pitfalls

Pitfall 1: Using disk scheduling algorithms for SSDs

• Problem: SSDs don't have moving parts, so seek time optimization doesn't apply
• Solution: Use deadline scheduler or noop scheduler for SSDs
• Example: Using SCAN for SSD wastes CPU on unnecessary scheduling

Pitfall 2: Not optimizing for sequential access

• Problem: Random I/O patterns can't be optimized well by any scheduler
• Solution: Design for sequential access, batch operations, use read-ahead
• Example: Many small random reads perform poorly regardless of scheduler

Pitfall 3: Ignoring starvation in SSTF

• Problem: SSTF can starve distant requests indefinitely
• Solution: Use SCAN or C-SCAN for fairness, or use deadline scheduler
• Example: SSTF serving nearby requests while distant requests wait forever

Pitfall 4: Not considering workload characteristics

• Problem: Choosing wrong scheduler for workload type
• Solution: Understand workload (random vs sequential, read vs write ratio)
• Example: Using FCFS for high-throughput sequential I/O wastes performance

Pitfall 5: Not monitoring I/O performance

• Problem: Not knowing if scheduler is effective
• Solution: Monitor seek time, throughput, latency, queue depth
• Example: Poor I/O performance without understanding root cause

---

Interview Questions

Beginner

Q: What is disk scheduling and why is it needed?

A: Disk scheduling is the process of ordering I/O requests to optimize disk head movement. Traditional hard disks have mechanical components (disk head) that must physically move to different tracks to read/write data. If requests are served in random order, the head moves back and forth, wasting time on seeks. Disk scheduling algorithms (like SCAN, C-SCAN) order requests to minimize head movement, significantly improving I/O performance. Sequential I/O is much faster than random I/O because it minimizes seeks.

---

Intermediate

Q: How does SCAN algorithm work, and what are its advantages and disadvantages compared to C-SCAN?

A: SCAN (also called elevator algorithm) works by:

1. Moving the disk head in one direction (e.g., right)
2. Serving all requests in that direction
3. Reversing direction when reaching the end
4. Serving requests in the opposite direction

Advantages:

• Minimizes seek time (head moves in one direction)
• Fair (all requests eventually served)
• Better than FCFS

Disadvantages:

• Requests at the end wait longer (must wait for reversal)
• Uneven wait times

C-SCAN (Circular SCAN) improves fairness:

• Moves in one direction, serves requests
• Immediately returns to start (doesn't serve on return)
• More uniform wait times
• Prevents starvation better than SCAN

Example: With requests at [10, 50, 100, 150], head at 100:

• SCAN: 100 → 150 → 10 → 50 (track 10 waits for reversal)
• C-SCAN: 100 → 150 → 0 → 10 → 50 (more uniform wait times)

---

Senior

Q: How would you design a disk I/O system that handles both random and sequential workloads efficiently while ensuring fairness?

A: I would use a multi-layered approach:

1. Workload detection:

   • Monitor I/O patterns (sequential vs random ratio)
   • Detect workload type (database, file server, web server)
   • Adjust strategy based on workload

2. Hybrid scheduling:

   • Sequential workloads: Use SCAN/C-SCAN for optimal performance
   • Random workloads: Use deadline scheduler to prevent starvation
   • Mixed workloads: Use multi-queue schedulers (like Linux mq-deadline)

3. Fairness mechanisms:

   • Use deadline scheduler to prevent starvation
   • Implement request aging (increase priority of waiting requests)
   • Separate queues for read/write with different priorities

4. SSD optimization:

   • Detect SSD vs HDD
   • Use noop or deadline scheduler for SSDs (no seek time)
   • Optimize for parallelism (SSDs can handle multiple requests)

5. I/O prioritization:

   • Prioritize critical I/O (database transactions)
   • Use I/O classes (real-time, best-effort, idle)
   • Implement bandwidth limits per process/class

6. Performance optimization:

   • Use read-ahead for sequential patterns
   • Batch small requests
   • Use write-back caching with proper flush policies

7. Monitoring:

   • Track seek time, throughput, latency
   • Monitor queue depth and wait times
   • Measure fairness metrics (max wait time, variance)

This design optimizes for both sequential and random workloads while ensuring fairness and preventing starvation.

---

• Disk scheduling: Orders I/O requests to minimize disk head movement (seek time)

• SCAN: Elevator algorithm, moves in one direction then reverses, minimizes seek time

• C-SCAN: Circular SCAN, serves requests in one direction then immediately returns, prevents starvation

• FCFS: First come first served, simple but poor performance (random seeks)

• SSTF: Shortest seek time first, fast but can cause starvation

• Sequential vs random: Sequential I/O much faster (minimizes seeks)

• SSDs: No moving parts, different optimization strategies needed

• Best practices: Optimize for sequential I/O, choose algorithm based on workload

• I/O Management - How disk scheduling is part of overall I/O management

• File Systems (EXT4, NTFS, FAT32) - How file systems interact with disk scheduling for I/O operations

• System Calls - How file I/O operations are requested through system calls

• Context Switching - How I/O blocking triggers context switches

• Process vs Thread - How I/O operations affect processes and threads