Disk Scheduling Algorithms

PerfectNotes Team•Updated May 2026

Share

This is a PerfectNotes study guide — also known as PN Notes or Perfect Notes. PerfectNotes provides free computer science student notes, MCQs, and interview preparation guides at perfectnotes.org.

Download PDF

Introduction to Disk Scheduling

Why Disk Scheduling Matters

The Hard Disk Drive (HDD) is a mechanical device operating in milliseconds, while the CPU operates in nanoseconds (million times slower).

Key Challenge:

When multiple processes request disk I/O, serving them in arrival order causes the disk arm to move inefficiently across the platter.

Disk Access Time Components

Total Disk Response Time Formula:

Total Disk Response Time = Queueing Delay + Disk Access Time

Where:

Disk Access Time = Seek Time + Rotational Latency + Transfer Time

Standard Example (Used Throughout)

We'll use this consistent example to compare all algorithms:

Current Head Position: 53
Request Queue: [98, 183, 37, 122, 14, 124, 65, 67]
Disk Track Range: 0-199
Direction (for directional algorithms): → (moving right)

Disk Scheduling Algorithms

A. FCFS (First Come First Serve)

How It Works:

Serve requests in arrival order (FIFO queue). No reordering or optimization.

Execution Path:

53 → 98 → 183 → 37 → 122 → 14 → 124 → 65 → 67

Calculation:

|53-98| + |98-183| + |183-37| + |37-122| + |122-14| + |14-124| + |124-65| + |65-67|
= 45 + 85 + 146 + 85 + 108 + 110 + 59 + 2
= 640 tracks

Visual Pattern:

The graph shows wild zigzag movements - arm jumps randomly across the disk: Sharp climb (53 → 98 → 183), Huge drop (183 → 37 = 146 tracks backward!), Another climb (37 → 122), Another drop (122 → 14).

Applications:

• SSDs: No seek time, so ordering doesn't matter
• Simple embedded systems: Code simplicity over performance
• Boot loaders: Minimal complexity required

Key Characteristics:

Advantages

• Perfect fairness: No starvation
• Simple: Just a FIFO queue, easy to implement

Disadvantages

• Worst performance: 640 tracks (highest)
• Random pattern: Chaotic zigzag causes delays

B. SSTF (Shortest Seek Time First)

How It Works:

Always pick the nearest request to current head position (greedy algorithm).

Execution (Step-by-Step):

From 53  → nearest is 65  (12 tracks)
From 65  → nearest is 67  (2 tracks)
From 67  → nearest is 37  (30 tracks)
From 37  → nearest is 14  (23 tracks)
From 14  → nearest is 98  (84 tracks - jump to next cluster)
From 98  → nearest is 122 (24 tracks)
From 122 → nearest is 124 (2 tracks)
From 124 → nearest is 183 (59 tracks)

Final Path:

53 → 65 → 67 → 37 → 14 → 98 → 122 → 124 → 183

Calculation:

12 + 2 + 30 + 23 + 84 + 24 + 2 + 59 = 236 tracks

Improvement: 640 → 236 = 63% reduction!

Visual Pattern:

The graph shows tight, localized movements: Small steps within clusters (65 → 67 = only 2 tracks), Efficient grouping of nearby requests, One major jump (14 → 98) to service distant cluster.

Applications:

• Batch processing systems: Throughput more important than fairness
• Database servers: Heavy sequential operations
• High-load systems: Maximize I/O operations per second

Key Characteristics:

Advantages

• Best performance: Only 236 tracks (fastest)
• High throughput: 30-40% improvement over FCFS

Disadvantages

• Starvation risk: Major issue, far requests may wait forever
• Unfair: Nearby requests always prioritized

C. SCAN (Elevator Algorithm)

How It Works:

Move in one direction, serve all requests along the way, reach disk physical end (0 or 199), then reverse direction.

Execution Path:

Forward (→): 53 → 65 → 67 → 98 → 122 → 124 → 183 → 199 (end)
Reverse (←): 199 → 37 → 14

Calculation:

Forward: 12 + 2 + 31 + 24 + 2 + 59 + 16 = 146 tracks
Reverse: 162 + 23 = 185 tracks
Total: 331 tracks

Visual Pattern:

The graph shows V-shape movement: Ascending slope (53 → 199 servicing all requests), Reversal point at track 199 (physical end), Descending slope (199 → 14 servicing missed requests). Named "Elevator Algorithm" because it works exactly like building elevators.

Applications:

• General-purpose OS: Standard for avoiding starvation
• Multi-user systems: Fair resource allocation
• Real-world elevators: Literally inspired by building elevators

Key Characteristics:

Advantages

• No starvation: Every request guaranteed service
• Predictable: Bounded maximum wait time

Disadvantages

• Non-uniform wait: Requests just missed wait longest
• Wasted movement: Goes to 199 even if no request there

D. C-SCAN (Circular SCAN)

How It Works:

Move in one direction only. At disk end, jump back to start (no service during return), then continue.

Execution Path:

Forward (→): 53 → 65 → 67 → 98 → 122 → 124 → 183 → 199
Jump: 199 → 0 (no service - just repositioning)
Resume (→): 0 → 14 → 37

Calculation:

Forward: 146 tracks
Jump (flyback): 199 tracks (no I/O operations)
Resume: 37 tracks
Total: 382 tracks

Visual Pattern:

The graph shows sawtooth wave: Climbing slope (53 → 199 servicing requests), Vertical drop (199 → 0 instant jump, dashed line), New climb (0 → 37 resume service).

Applications:

• Video streaming: Consistent data delivery required
• Audio playback: Variable latency causes stuttering
• Real-time systems: Predictable response time critical

Key Characteristics:

Advantages

• Uniform wait time: More predictable than SCAN
• Fair treatment: Inner and outer tracks equally prioritized

Disadvantages

• Wasted flyback: 199 tracks with zero I/O operations
• Higher total: 382 vs 331 for SCAN

E. LOOK (Smart SCAN)

How It Works:

Like SCAN, but stops at last request instead of going to physical disk end.

Execution Path:

Forward (→): 53 → 65 → 67 → 98 → 122 → 124 → 183 (STOP - no 199)
Reverse (←): 183 → 37 → 14 (STOP - no 0)

Calculation:

Forward: 12 + 2 + 31 + 24 + 2 + 59 = 130 tracks
Reverse: 146 + 23 = 169 tracks
Total: 299 tracks

Improvement over SCAN: 331 → 299 = 10% reduction

Visual Pattern:

The graph shows smart V-shape with highlighted "saved" regions: Stops at 183 (highest request) instead of 199, Stops at 14 (lowest request) instead of 0. Gray boxes show saved movement: (199-183) + (14-0) = 16 + 14 = 30 tracks saved.

Applications:

• Linux: CFQ (Completely Fair Queuing) scheduler
• Windows: Default disk scheduler
• Modern operating systems: Industry standard

Key Characteristics:

Why LOOK is Best (Industry Standard)

• Most efficient directional: Best practical algorithm (299 tracks)
• No wasted movement: Only travels to actual requests
• No starvation: Like SCAN, guaranteed service
• Industry standard: Used in production systems worldwide

F. C-LOOK (Circular LOOK)

How It Works:

Like C-SCAN, but stops at last request instead of going to disk ends.

Execution Path:

Forward (→): 53 → 65 → 67 → 98 → 122 → 124 → 183 (STOP)
Jump: 183 → 14 (jump to lowest, no service)
Resume (→): 14 → 37

Calculation:

Forward: 130 tracks
Jump: 169 tracks (no service but arm moves)
Resume: 23 tracks
Total: 322 tracks

Improvement over C-SCAN: 382 → 322 = 16% reduction

Applications:

• Database servers: Heavy concurrent access
• Enterprise systems: Predictable latency required
• Write-intensive workloads: Logging, journaling systems

Advanced Engineering Concepts

NVMe and the Obsolescence of Disk Scheduling

While disk scheduling algorithms were critical for HDDs, the rise of Non-Volatile Memory Express (NVMe) Solid State Drives has fundamentally shifted OS architecture. Because NVMe drives have zero moving parts and utilize thousands of parallel queues, applying SCAN or LOOK algorithms actually degrades performance by consuming CPU cycles unnecessarily. Modern kernels (like Linux 5.x+) implement a multi-queue block layer (blk-mq) that bypasses traditional scheduling entirely for NVMe storage, defaulting to simple FIFO or completely hardware-delegated queues.

Real-World Case Study: Linux Kernel CFQ Scheduler

The Linux kernel has gone through several disk schedulers over its history, eventually settling on the Completely Fair Queuing (CFQ) algorithm, which heavily utilizes LOOK principles.

Key Statistics & Industry Data (2026)

• Performance Impact — Implementing C-LOOK on a heavily loaded enterprise HDD array increases aggregate I/O throughput by up to 400% compared to basic FCFS scheduling, by minimizing mechanical seek delays. (Source: Storage Networking Industry Association, 2026)
• SSD Adoption — As of 2025, over 85% of consumer PCs utilize NVMe SSDs, meaning complex disk scheduling algorithms are bypassed entirely by the OS in favor of simple FIFO queues to save CPU overhead. (Source: IDC Storage Market Report, 2026)
• Mechanical Limits — Despite algorithmic optimizations, the physical limitation of an HDD actuator arm means a seek operation still takes an average of 4-8 milliseconds, which is millions of times slower than modern CPU cache access. (Source: Western Digital Technology Review, 2026)

Performance Comparison

Quick Reference Cheat Sheet

Performance Rankings

By Speed (Lower = Better):

1. SSTF: 236 tracks (fastest but unfair)
2. LOOK: 299 tracks (Best practical choice)
3. C-LOOK: 322 tracks
4. SCAN: 331 tracks
5. C-SCAN: 382 tracks
6. FCFS: 640 tracks (worst)

By Fairness:

1. FCFS: Perfect fairness (5/5)
2. C-SCAN / C-LOOK: Uniform wait time (4/5)
3. SCAN / LOOK: Bounded wait time (3/5)
4. SSTF: Highly unfair, starvation risk (1/5)

By Real-World Usage:

1. LOOK: Industry standard (Linux, Windows)
2. C-LOOK: Enterprise systems
3. SCAN: Older Unix systems
4. SSTF: Batch processing only
5. C-SCAN: Specialized use cases
6. FCFS: SSDs only