Disk Scheduling Algorithms

Overview

Disk scheduling algorithms determine the order in which disk I/O requests are processed by the operating system. When multiple processes request disk access simultaneously, the scheduler must decide which request to service first to optimize overall system performance. The primary goal is to minimize seek time—the time required for the disk arm to move to the correct track—while balancing fairness and preventing request starvation.

Traditional hard disk drives (HDDs) have mechanical components that move physically to access data. The disk arm moves across tracks, and each movement incurs a cost measured in milliseconds. Different scheduling algorithms make different trade-offs between minimizing total seek time, ensuring fair access, and preventing indefinite postponement of requests.

Disk Structure:
Track 0:  |------------|
Track 1:  |------------|
Track 2:  |------------|  <- Current head position
Track 3:  |------------|
Track 4:  |------------|

Request Queue: [98, 183, 37, 122, 14, 124, 65, 67]
Current Position: Track 53

The choice of disk scheduling algorithm affects system responsiveness, throughput, and fairness. Modern operating systems often implement hybrid approaches that adapt based on workload characteristics. While solid-state drives (SSDs) have different performance characteristics without mechanical seek time, understanding these algorithms remains relevant for systems using HDDs and for comprehending I/O scheduling principles.

Key Principles

Disk scheduling algorithms operate on several fundamental principles that govern how requests are ordered and serviced. The scheduler maintains a queue of pending I/O requests, each specifying a track number where data resides. The disk head position changes as requests are serviced, and the scheduler must determine the next request to process.

Seek Time represents the dominant cost in disk operations for HDDs. Seek time consists of the time to accelerate the disk arm, move it across tracks, and decelerate it at the destination. Minimizing total seek time across all requests improves overall throughput. The seek distance—the number of tracks between the current head position and the requested track—directly correlates with seek time.

Rotational Latency occurs after the head reaches the correct track. The disk must rotate until the desired sector passes under the head. Average rotational latency equals half the time for one complete rotation. Scheduling algorithms typically optimize seek time rather than rotational latency, though some advanced algorithms consider both factors.

Fairness ensures that all requests eventually receive service. Algorithms that aggressively optimize seek time may cause starvation, where requests far from the current head position wait indefinitely. Balancing efficiency with fairness prevents pathological cases where certain requests never complete.

Direction of Movement influences several algorithms. Once the disk head moves in a particular direction, continuing that direction for nearby requests often proves more efficient than reversing direction. This principle underlies the SCAN family of algorithms.

Request Patterns vary by workload. Sequential access patterns, where requests target consecutive tracks, differ from random access patterns. Database systems often generate localized request clusters, while multimedia applications produce sequential patterns. Effective scheduling algorithms adapt to these patterns.

The arrival order of requests affects some algorithms. First Come First Serve (FCFS) strictly follows arrival order, while other algorithms reorder requests based on optimization criteria. The scheduler must track both the original arrival sequence and the reordered service sequence.

Design Considerations

Selecting a disk scheduling algorithm requires analyzing workload characteristics, performance requirements, and fairness constraints. Different algorithms excel in different scenarios, and no single algorithm optimally handles all situations.

Throughput Optimization guides algorithm selection for high-volume systems. Algorithms like SSTF and SCAN minimize total seek time, maximizing the number of requests serviced per unit time. Systems processing large numbers of small I/O operations benefit from throughput-focused algorithms. However, extreme throughput optimization may compromise fairness, potentially causing starvation for requests to distant tracks.

Response Time Variation affects user experience in interactive systems. FCFS provides predictable response times since requests complete in arrival order, though overall response times may be longer. Algorithms that reorder requests introduce variance—some requests complete quickly while others wait longer. Applications requiring consistent latency prefer algorithms with bounded worst-case response times.

Workload Characteristics determine algorithm effectiveness. Sequential workloads, such as video streaming or database scans, naturally benefit from directional algorithms like SCAN. Random access workloads, typical of multi-user systems or virtual memory paging, may perform better with SSTF if the requests distribute evenly across the disk. Analyzing historical access patterns reveals whether requests cluster in specific disk regions or spread uniformly.

# Workload analysis determines algorithm selection
class WorkloadAnalyzer
  def initialize(requests)
    @requests = requests
  end
  
  def sequential_ratio
    sequential_count = 0
    @requests.each_cons(2) do |curr, nxt|
      sequential_count += 1 if (curr - nxt).abs <= 5
    end
    sequential_count.to_f / (@requests.size - 1)
  end
  
  def spread_metric
    @requests.max - @requests.min
  end
end

analyzer = WorkloadAnalyzer.new([50, 52, 100, 103, 105, 45])
analyzer.sequential_ratio  # => 0.6 (indicates sequential tendency)

Starvation Prevention requires careful consideration. SSTF and LOOK variants may indefinitely postpone requests to extreme track positions if requests continually arrive for middle tracks. Production systems must guarantee eventual service for all requests. Hybrid algorithms that periodically switch to FCFS mode or impose waiting time limits prevent starvation. Real-time systems may require strict deadlines, necessitating algorithms that guarantee maximum wait times.

Hardware Constraints influence algorithm implementation. Modern disk controllers cache requests and may reorder them internally, reducing the operating system scheduler's control. The disk's physical geometry—number of tracks, sectors per track, rotation speed—affects the relative cost of different operations. Some disks support Native Command Queuing (NCQ), allowing the drive firmware to optimize request ordering based on physical disk characteristics invisible to the OS.

System Load changes optimal algorithm selection. Under light load with few pending requests, algorithm choice matters less since reordering opportunities are limited. Heavy load with long request queues allows algorithms to make better optimization decisions. Adaptive scheduling systems switch algorithms based on current queue depth and system load.

Implementation Approaches

Disk scheduling algorithms differ in how they select the next request to service from the pending queue. Each approach maintains the request queue and current head position, but applies different selection logic.

First Come First Serve (FCFS) processes requests in strict arrival order. The implementation uses a simple FIFO queue. When a request completes, the scheduler removes the next request from the queue head. FCFS requires no complex data structures or sorting logic, making it the simplest algorithm to implement.

Request Queue: [98, 183, 37, 122, 14, 124, 65, 67]
Current Position: 53

Service Order: 98 -> 183 -> 37 -> 122 -> 14 -> 124 -> 65 -> 67
Total Seek Distance: 45 + 85 + 146 + 85 + 108 + 110 + 59 + 2 = 640 tracks

FCFS guarantees fairness and prevents starvation but provides poor performance when requests arrive in unfavorable orders. Wide disk arm movements waste seek time. FCFS works acceptably for systems with light I/O load or predictable sequential access patterns.

Shortest Seek Time First (SSTF) selects the request nearest to the current head position. The implementation maintains requests in a data structure supporting efficient nearest-neighbor queries. Each time a request completes, the scheduler scans pending requests to find the one requiring minimum seek distance.

Request Queue: [98, 183, 37, 122, 14, 124, 65, 67]
Current Position: 53

First selection: 65 (distance 12)
Next selection: 67 (distance 2)
Next selection: 37 (distance 30)
Continue selecting nearest...

Total Seek Distance significantly reduced compared to FCFS

SSTF minimizes average seek time and maximizes throughput. However, it suffers from starvation—requests to extreme tracks may wait indefinitely if requests continually arrive for middle tracks. SSTF also exhibits direction changes, potentially causing the disk arm to oscillate rather than sweep smoothly.

SCAN (Elevator Algorithm) moves the disk arm in one direction, servicing all requests in that direction until reaching the disk end, then reverses direction. The implementation maintains the current direction of movement and selects requests ahead of the current position in the movement direction.

Request Queue: [98, 183, 37, 122, 14, 124, 65, 67]
Current Position: 53, Direction: Increasing

Moving right: 65, 67, 98, 122, 124, 183, [reach end]
Reverse direction
Moving left: 37, 14

Total Seek Distance: Lower than FCFS, more fair than SSTF

SCAN provides better fairness than SSTF while maintaining good performance. Requests receive service in bounded time since the disk arm sweeps the entire disk periodically. The algorithm's name derives from its similarity to elevator scheduling in buildings.

Circular SCAN (C-SCAN) treats the disk as a circular structure. The arm moves in one direction, servicing requests, and upon reaching the end, returns to the beginning without servicing requests during the return sweep. C-SCAN provides more uniform wait times than SCAN since it eliminates the advantage given to middle tracks.

LOOK and C-LOOK optimize SCAN and C-SCAN by reversing direction at the last request in each direction rather than traveling to the disk end. This reduces unnecessary seeking to empty disk regions. LOOK serves requests in both directions while C-LOOK returns to the beginning after reaching the last request in one direction.

Ruby Implementation

Ruby implementations of disk scheduling algorithms demonstrate the core logic and data structure management. Production implementations typically reside in operating system kernels, but Ruby provides clear illustration of the algorithms.

class DiskScheduler
  attr_reader :requests, :head_position, :total_seek_distance
  
  def initialize(initial_head_position)
    @head_position = initial_head_position
    @requests = []
    @total_seek_distance = 0
    @service_order = []
  end
  
  def add_request(track)
    @requests << track
  end
  
  def service_order
    @service_order
  end
  
  protected
  
  def move_to(track)
    seek_distance = (track - @head_position).abs
    @total_seek_distance += seek_distance
    @head_position = track
    @service_order << track
    @requests.delete_at(@requests.index(track))
  end
end

The base class provides common functionality for tracking head position, calculating seek distance, and maintaining the service order. Specific algorithms inherit from this base and implement their scheduling logic.

class FCFSScheduler < DiskScheduler
  def schedule
    until @requests.empty?
      next_request = @requests.first
      move_to(next_request)
    end
  end
end

# Usage
scheduler = FCFSScheduler.new(53)
[98, 183, 37, 122, 14, 124, 65, 67].each { |r| scheduler.add_request(r) }
scheduler.schedule
scheduler.service_order  # => [98, 183, 37, 122, 14, 124, 65, 67]
scheduler.total_seek_distance  # => 640

FCFS implementation directly processes requests from the queue without reordering. The simplicity reflects the algorithm's straightforward nature.

class SSTFScheduler < DiskScheduler
  def schedule
    until @requests.empty?
      next_request = find_nearest_request
      move_to(next_request)
    end
  end
  
  private
  
  def find_nearest_request
    @requests.min_by { |track| (track - @head_position).abs }
  end
end

# Usage
scheduler = SSTFScheduler.new(53)
[98, 183, 37, 122, 14, 124, 65, 67].each { |r| scheduler.add_request(r) }
scheduler.schedule
scheduler.service_order  # => [65, 67, 37, 14, 98, 122, 124, 183]
scheduler.total_seek_distance  # => 236

SSTF finds the nearest request using Ruby's min_by method. Each iteration recalculates the nearest request based on the updated head position. The significant reduction in total seek distance compared to FCFS demonstrates SSTF's efficiency.

class SCANScheduler < DiskScheduler
  def initialize(initial_head_position, direction = :up)
    super(initial_head_position)
    @direction = direction
  end
  
  def schedule
    until @requests.empty?
      requests_in_direction = if @direction == :up
        @requests.select { |r| r >= @head_position }.sort
      else
        @requests.select { |r| r <= @head_position }.sort.reverse
      end
      
      if requests_in_direction.empty?
        @direction = (@direction == :up) ? :down : :up
        next
      end
      
      move_to(requests_in_direction.first)
    end
  end
end

# Usage
scheduler = SCANScheduler.new(53, :up)
[98, 183, 37, 122, 14, 124, 65, 67].each { |r| scheduler.add_request(r) }
scheduler.schedule
scheduler.service_order  # => [65, 67, 98, 122, 124, 183, 37, 14]
scheduler.total_seek_distance  # => 208

SCAN maintains direction state and selects requests ahead of the current position. When no requests remain in the current direction, the algorithm reverses. The implementation sorts requests in the current direction to process them in optimal order.

class LOOKScheduler < DiskScheduler
  def initialize(initial_head_position, direction = :up)
    super(initial_head_position)
    @direction = direction
  end
  
  def schedule
    until @requests.empty?
      requests_in_direction = if @direction == :up
        @requests.select { |r| r >= @head_position }.sort
      else
        @requests.select { |r| r <= @head_position }.sort.reverse
      end
      
      if requests_in_direction.empty?
        @direction = (@direction == :up) ? :down : :up
      else
        move_to(requests_in_direction.first)
      end
    end
  end
end

# LOOK avoids traveling to disk ends unnecessarily
scheduler = LOOKScheduler.new(53, :up)
[98, 183, 37, 122, 14, 124, 65, 67].each { |r| scheduler.add_request(r) }
scheduler.schedule
scheduler.total_seek_distance  # => 208 (same pattern as SCAN but potentially less if no requests at extremes)

LOOK improves upon SCAN by reversing at the last request rather than the disk boundary. The implementation logic closely resembles SCAN but provides better performance when requests don't span the entire disk.

class CSCANScheduler < DiskScheduler
  def initialize(initial_head_position, max_track = 199)
    super(initial_head_position)
    @max_track = max_track
  end
  
  def schedule
    until @requests.empty?
      requests_ahead = @requests.select { |r| r >= @head_position }.sort
      
      if requests_ahead.empty?
        # Jump back to beginning
        @head_position = 0
        next
      end
      
      move_to(requests_ahead.first)
    end
  end
end

# C-SCAN provides uniform wait time distribution
scheduler = CSCANScheduler.new(53, 199)
[98, 183, 37, 122, 14, 124, 65, 67].each { |r| scheduler.add_request(r) }
scheduler.schedule
scheduler.service_order  # => [65, 67, 98, 122, 124, 183, 14, 37]

C-SCAN unidirectionally services requests and returns to the disk start without servicing requests during the return. This approach provides more predictable wait times across all track positions.

Performance Considerations

Disk scheduling algorithm performance depends on multiple factors including request distribution, system load, and hardware characteristics. Different metrics reveal different aspects of algorithm effectiveness.

Average Seek Time measures the mean seek distance across all requests. SSTF typically achieves the lowest average seek time by consistently selecting nearby requests. SCAN and LOOK provide intermediate performance, while FCFS often exhibits the highest average seek time due to random movement patterns.

class PerformanceAnalyzer
  def initialize(scheduler_class, head_position, requests)
    @scheduler_class = scheduler_class
    @head_position = head_position
    @requests = requests
  end
  
  def analyze
    scheduler = @scheduler_class.new(@head_position)
    @requests.each { |r| scheduler.add_request(r) }
    scheduler.schedule
    
    {
      algorithm: @scheduler_class.name,
      total_seek: scheduler.total_seek_distance,
      average_seek: scheduler.total_seek_distance.to_f / @requests.size,
      service_order: scheduler.service_order,
      request_count: @requests.size
    }
  end
end

requests = [98, 183, 37, 122, 14, 124, 65, 67]

[FCFSScheduler, SSTFScheduler, SCANScheduler, LOOKScheduler].each do |algo|
  result = PerformanceAnalyzer.new(algo, 53, requests.dup).analyze
  puts "#{result[:algorithm]}: Average Seek = #{result[:average_seek].round(2)}"
end

# Output:
# FCFSScheduler: Average Seek = 80.00
# SSTFScheduler: Average Seek = 29.50
# SCANScheduler: Average Seek = 26.00
# LOOKScheduler: Average Seek = 26.00

Maximum Wait Time indicates fairness and starvation potential. FCFS provides bounded maximum wait time proportional to queue length. SSTF may cause unbounded wait times for distant requests under continuous arrival patterns. SCAN guarantees bounded wait time proportional to two full disk sweeps.

Variance in Wait Time affects perceived system responsiveness. FCFS exhibits high variance when requests arrive in random orders. SSTF shows extreme variance—nearby requests complete quickly while distant requests wait extensively. SCAN provides moderate variance with more uniform distribution than SSTF.

Throughput measures requests completed per time unit. SSTF typically achieves highest throughput by minimizing total seek time. However, under heavy load with continuous arrivals, SSTF may service the same disk region repeatedly while distant requests accumulate, eventually degrading throughput when the scheduler must address the backlog.

class ThroughputSimulator
  def initialize(scheduler_class, arrival_rate)
    @scheduler_class = scheduler_class
    @arrival_rate = arrival_rate
    @time = 0
    @completed = 0
  end
  
  def simulate(duration, disk_size = 200)
    scheduler = @scheduler_class.new(disk_size / 2)
    
    while @time < duration
      # Generate arrivals based on arrival rate
      arrivals = rand(0..@arrival_rate)
      arrivals.times { scheduler.add_request(rand(0...disk_size)) }
      
      # Service requests
      unless scheduler.requests.empty?
        scheduler.schedule
        @completed += scheduler.service_order.size
      end
      
      @time += 1
    end
    
    @completed.to_f / duration  # Throughput: requests per time unit
  end
end

Seek Pattern Locality impacts performance significantly. Sequential access patterns benefit all algorithms but especially SCAN-based approaches. Random access patterns expose algorithm differences more clearly. Database workloads often exhibit temporal locality—requests cluster in time—and spatial locality—requests cluster in disk regions. Algorithms that exploit locality outperform those treating requests independently.

Queue Length Effects change algorithm behavior. Short queues limit reordering opportunities, reducing differences between algorithms. Long queues allow aggressive optimization but increase average wait time for all algorithms. Very long queues may indicate system overload where no algorithm performs adequately.

Hardware Impact increasingly dominates algorithm performance. Modern disk drives with large caches, command queuing, and sophisticated firmware perform internal optimization that overrides OS-level scheduling decisions. The operating system submits multiple requests to the drive, which reorders them based on physical geometry knowledge unavailable to the OS. This reality reduces the performance gap between algorithms in production systems compared to theoretical analysis.

Practical Examples

Examining concrete scenarios demonstrates how different algorithms behave under various workload conditions and helps identify appropriate algorithm selection for specific use cases.

Database Transaction Processing generates random access patterns across the disk. Consider a database system processing multiple concurrent queries that access different table regions.

class DatabaseWorkloadSimulator
  def initialize(scheduler_class)
    @scheduler_class = scheduler_class
  end
  
  def simulate_transactions(num_transactions)
    # Database tables distributed across disk
    customer_table_tracks = (10..50)
    order_table_tracks = (100..150)
    product_table_tracks = (160..180)
    
    scheduler = @scheduler_class.new(75)  # Initial position
    
    num_transactions.times do
      # Each transaction accesses multiple tables
      scheduler.add_request(rand(customer_table_tracks))
      scheduler.add_request(rand(order_table_tracks))
      scheduler.add_request(rand(product_table_tracks))
    end
    
    scheduler.schedule
    
    {
      total_seek: scheduler.total_seek_distance,
      avg_seek: scheduler.total_seek_distance.to_f / (num_transactions * 3),
      service_order: scheduler.service_order
    }
  end
end

# Compare algorithms for database workload
fcfs_result = DatabaseWorkloadSimulator.new(FCFSScheduler).simulate_transactions(10)
sstf_result = DatabaseWorkloadSimulator.new(SSTFScheduler).simulate_transactions(10)
scan_result = DatabaseWorkloadSimulator.new(SCANScheduler).simulate_transactions(10)

puts "Database Workload Results:"
puts "FCFS: #{fcfs_result[:avg_seek].round(2)} tracks average"
puts "SSTF: #{sstf_result[:avg_seek].round(2)} tracks average"
puts "SCAN: #{scan_result[:avg_seek].round(2)} tracks average"

For database workloads with random access patterns, SSTF minimizes seek time but risks starving transactions requiring distant table access. SCAN provides better fairness, ensuring all transactions complete within bounded time. Production database systems often use SCAN variants or implement custom scheduling that considers transaction priorities.

Video Streaming Service produces sequential read patterns as the system reads video files stored contiguously on disk. Multiple concurrent streams create interleaved sequential access patterns.

class VideoStreamingSimulator
  def initialize(scheduler_class)
    @scheduler_class = scheduler_class
  end
  
  def simulate_streaming(num_streams, blocks_per_stream)
    scheduler = @scheduler_class.new(0)
    
    # Each stream starts at different disk location
    stream_positions = num_streams.times.map { |i| i * 40 }
    
    # Generate sequential reads for each stream
    num_streams.times do |stream_id|
      start_track = stream_positions[stream_id]
      blocks_per_stream.times do |block|
        scheduler.add_request(start_track + block)
      end
    end
    
    scheduler.schedule
    
    {
      total_seek: scheduler.total_seek_distance,
      service_order: scheduler.service_order
    }
  end
end

result = VideoStreamingSimulator.new(SCANScheduler).simulate_streaming(3, 10)

# SCAN efficiently handles sequential patterns
# Services requests in sweeping motion, naturally fitting sequential access

SCAN excels at video streaming workloads because its sweeping motion aligns with sequential access patterns. The algorithm services consecutive blocks for each stream during each sweep, providing smooth playback without excessive seeking. FCFS would thrash between streams, while SSTF might starve streams at disk extremes.

Virtual Memory Paging creates mixed access patterns. Page faults cause disk reads to swap pages into memory. The access pattern combines locality (programs often access nearby memory pages) with randomness (context switches between processes).

class PagingWorkloadSimulator
  def initialize(scheduler_class)
    @scheduler_class = scheduler_class
  end
  
  def simulate_paging(processes)
    scheduler = @scheduler_class.new(100)
    
    processes.each do |process|
      # Each process has working set (locality)
      base_page = process[:base_page]
      working_set_size = process[:working_set]
      
      # Generate page faults within working set
      process[:page_faults].times do
        # Most accesses near base (locality)
        if rand < 0.7
          page = base_page + rand(0...working_set_size)
        else
          # Occasional random access
          page = rand(0..199)
        end
        scheduler.add_request(page)
      end
    end
    
    scheduler.schedule
    
    {
      total_seek: scheduler.total_seek_distance,
      avg_seek: scheduler.total_seek_distance.to_f / 
                processes.sum { |p| p[:page_faults] }
    }
  end
end

processes = [
  { base_page: 20, working_set: 30, page_faults: 15 },
  { base_page: 100, working_set: 25, page_faults: 12 },
  { base_page: 170, working_set: 20, page_faults: 10 }
]

result = PagingWorkloadSimulator.new(LOOKScheduler).simulate_paging(processes)
puts "Paging workload average seek: #{result[:avg_seek].round(2)} tracks"

LOOK performs well for virtual memory paging because it exploits locality within each process's working set while avoiding starvation. When the scheduler sweeps through the disk, it services clustered page faults from each process efficiently. The algorithm adapts to the mixed random-sequential nature of paging workloads.

Real-Time System with Deadlines requires guaranteed completion times. Consider an industrial control system that must read sensor data from disk with strict deadlines.

class RealTimeScheduler < DiskScheduler
  def initialize(initial_head_position)
    super(initial_head_position)
    @deadlines = {}
  end
  
  def add_request_with_deadline(track, deadline)
    @requests << track
    @deadlines[track] = deadline
  end
  
  def schedule(current_time = 0)
    @time = current_time
    missed_deadlines = 0
    
    until @requests.empty?
      # Select request with earliest deadline
      next_request = @requests.min_by { |track| @deadlines[track] }
      
      seek_time = (next_request - @head_position).abs
      @time += seek_time
      
      if @time > @deadlines[next_request]
        missed_deadlines += 1
      end
      
      move_to(next_request)
    end
    
    missed_deadlines
  end
end

# Real-time system prioritizes deadlines over seek optimization
rt_scheduler = RealTimeScheduler.new(53)
rt_scheduler.add_request_with_deadline(98, 100)
rt_scheduler.add_request_with_deadline(14, 50)
rt_scheduler.add_request_with_deadline(183, 200)

missed = rt_scheduler.schedule(0)
puts "Missed deadlines: #{missed}"

Real-time systems require deadline-aware scheduling that may sacrifice seek time optimization to guarantee timing constraints. Earliest Deadline First (EDF) scheduling orders requests by deadline rather than track position. The system must ensure sufficient disk bandwidth to meet all deadlines under worst-case seek times.

Reference

Algorithm Comparison

Algorithm Characteristics

Performance Metrics

Use Case Recommendations

Implementation Considerations

Disk Hardware Parameters

Ruby Implementation Patterns