I/O Management

Disk Scheduling

Shortest Seek Time First (SSTF) and other algorithms optimizing hard disk read/write head movements.

What is Disk Scheduling?

Disk Scheduling algorithms decide the execution sequence of disk I/O track requests. Shortest Seek Time First (SSTF) selects the request that requires the least seek time or cylinder movement from the current head position. This minimizes head travel overhead, though it can starve distant cylinder requests.

Key Characteristics:

  • Minimizes overall seek distances compared to naive FCFS.
  • Subject to starvation of requests far from the active head region.
  • Requires tracking current head track index.
  • Used to optimize disk controller access throughput.

Complexity Analysis

Avg Time Complexity: O(N^2) where N is requests count (simplified linear search)
Space Complexity: O(N) storage array
Best Case: O(N) (requests arrive in sequential track order)
Worst Case: O(N^2) (frequent search over fluctuating cylinder requests)

How it Works Step-by-Step

  1. Read Current Head: Note the active disk read/write head track location.
  2. Compute Seek Distances: Calculate absolute track distance between head and all pending requests.
  3. Find Minimum Seek: Select the request requiring the smallest cylinder change.
  4. Update Stats: Move head to the selected track, add seek distance to total, and mark as completed.
  5. Iterate: Repeat steps 2-4 until all requests are serviced.

Code Implementation

Worked Trace Example

With requests [90, 150, 40] and head initially at 50:
1. Distances: |90-50|=40, |150-50|=100, |40-50|=10. Closest is track 40.
2. Move to 40 (Seek distance: 10). Pending requests: [90, 150].
3. Distances: |90-40|=50, |150-40|=110. Closest is track 90.
4. Move to 90 (Seek distance: 50). Pending: [150].
5. Move to 150 (Seek distance: 60).
Result: Total seek distance = 10 + 50 + 60 = 120 cylinders.

Ready to Understand Disk Scheduling Visually?

Don't just read about it. Launch our interactive, premium OS visualizer to see the processes, memory blocks, Page replacement queues, or disk head movements update in real-time.

Launch Disk Scheduling Visualizer →