SSTF Disk Scheduling Algorithm
Every time a program needs to read or write data on a disk, the operating system has to decide which request to handle first. This decision-making process is handled by disk scheduling algorithms.
One of the more practical and widely studied among these is the Shortest Seek Time First algorithm, commonly known as SSTF.
What is SSTF?
The core idea behind SSTF is straightforward: instead of serving requests in the order they arrive, the disk head always moves to whichever pending request is physically closest to its current position. The assumption is that servicing nearby tracks first will cut down on unnecessary movement, saving time overall.
Compared to the basic First Come First Served approach, SSTF does a noticeably better job at reducing total head travel.
How the Algorithm Works
The process follows a logical, greedy sequence:
1. The disk head starts at its current track. 2. The system looks at all outstanding requests and calculates the absolute distance to each one. 3. It picks the nearest track, moves the head there, and processes it. 4. It repeats this calculation from the new position until the queue is entirely empty.
Worked Example
Suppose the disk requests are lined up as follows: 82, 170, 45, 130, 10, 135, 60, 64. The disk head begins at track 50.
| Movement | Calculation | Distance (Tracks) |
|---|---|---|
| 50 → 45 | |50 - 45| | 5 |
| 45 → 60 | |45 - 60| | 15 |
| 60 → 64 | |60 - 64| | 4 |
| 64 → 82 | |64 - 82| | 18 |
| 82 → 10 | |82 - 10| | 72 |
| 10 → 130 | |10 - 130| | 120 |
| 130 → 135 | |130 - 135| | 5 |
| 135 → 170 | |135 - 170| | 35 |
Total Head Movement = 5 + 15 + 4 + 18 + 72 + 120 + 5 + 35 = 274 tracks.
Average Seek Length = 274 / 8 = 34.25 tracks.
If the same set of requests were handled using FCFS, the head would have traveled considerably more because it blindly follows the arrival order regardless of physical distance. SSTF clearly handles the workload much more efficiently.
SSTF Head Movement Sequence. The head efficiently serves local clusters before being forced to make a long jump across the disk.
Python Implementation
import heapq
def sstf_disk_scheduling(requests, head):
total_head_movement = 0
seek_sequence = []
requests = requests.copy()
while requests:
# Calculate distance to all pending requests
distances = [(abs(head - req), req) for req in requests]
heapq.heapify(distances)
# Pop the one with the shortest distance
shortest_distance, closest_request = heapq.heappop(distances)
total_head_movement += shortest_distance
head = closest_request
seek_sequence.append(closest_request)
requests.remove(closest_request)
return total_head_movement, seek_sequence
requests = [82, 170, 45, 130, 10, 135, 60, 64]
initial_head = 50
total_movement, sequence = sstf_disk_scheduling(requests, initial_head)
print("Total Head Movement:", total_movement)
print("Seek Sequence:", sequence)Practice Walkthrough
Let's try tracing another sequence. Disk requests arrive in this order: 55, 20, 95, 8, 75. The disk head starts at track 35.
| Movement | Calculation | Distance |
|---|---|---|
| 35 → 20 | |35 - 20| | 15 |
| 20 → 8 | |20 - 8| | 12 |
| 8 → 55 | |8 - 55| | 47 |
| 55 → 75 | |55 - 75| | 20 |
| 75 → 95 | |75 - 95| | 20 |
Total Head Movement = 15 + 12 + 47 + 20 + 20 = 114 tracks.
Strengths and Weaknesses
SSTF consistently delivers much lower average seek times than simpler algorithms like FCFS, making far better use of the disk hardware. For workloads where requests tend to cluster in certain regions of the disk, it performs exceptionally well.
| Strengths | Weaknesses |
|---|---|
| Significantly reduces total head movement compared to FCFS. | Starvation: Distant tracks can be ignored indefinitely if nearby tracks keep generating requests. |
| Lower average seek time improves total system throughput. | Overhead: The system must constantly recalculate distances for every single pending request. |
| Highly efficient for localized data access patterns. | Unpredictable variance in response times (some fast, some incredibly slow). |
Calculate SSTF Seek Time
Question 1 of 1Test your ability to trace SSTF and calculate physical time.