1. Why SSTF Was Introduced
FCFS is simple and fair, but it completely ignores the physical location of disk requests.
Consider the queue:
98, 183, 37, 122, 14, 124, 65, 67
If the head is currently at cylinder 53, FCFS services requests in arrival order even when a much closer request exists.
This causes:
Excessive head movement
High seek time
Low throughput
Poor disk utilization
The Core Observation
When the disk head is at a particular location, some pending requests are much closer than others.
For example:
Current Head = 53
Requests:
37, 65, 67, 98, 122, 124, 183
Clearly:
65 and 67
are much closer than:
183
The Question
Instead of serving requests in arrival order, why not always serve the nearest request?
This idea leads to SSTF.
Key Insight
SSTF reduces seek time by always selecting the request requiring the smallest immediate head movement.
2. What is SSTF?
SSTF (Shortest Seek Time First) is a disk scheduling algorithm that selects the pending request closest to the current disk head position.
Definition
At every step, SSTF chooses the request with the minimum seek distance from the current head location.
Core Principle
Next Request
=
Closest Pending Request
Mathematical View
For a current head position H and pending requests Ri:
Choose Ri such that
|H − Ri|
is minimum
Example
Current Head:
53
Pending Requests:
98, 37, 65, 67
Distances:
|53−98| = 45
|53−37| = 16
|53−65| = 12
|53−67| = 14
Smallest distance:
12
Therefore:
53 → 65
Key Insight
SSTF is a greedy algorithm because it always makes the locally optimal choice.
3. How SSTF Works Internally
Unlike FCFS, SSTF continuously evaluates all pending requests.
Step 1: Maintain Request Queue
Example:
98, 183, 37, 122, 14, 124, 65, 67
Step 2: Examine Current Head Position
Suppose:
Head = 53
Step 3: Compute Distances
Calculate:
Distance = |Current Head − Request|
for every pending request.
Step 4: Select Closest Request
Choose the minimum distance.
Step 5: Move Head
Service the selected request.
Step 6: Remove Request
Delete serviced request from queue.
Step 7: Repeat
Continue until all requests are completed.
Key Insight
SSTF continuously adapts to the current head location.
4. Numerical Example (Step-by-Step)
Given
Initial Head Position:
53
Request Queue:
98, 183, 37, 122, 14, 124, 65, 67
Step 1: Head at 53
Distances:
|53−98| = 45
|53−183| = 130
|53−37| = 16
|53−122| = 69
|53−14| = 39
|53−124| = 71
|53−65| = 12
|53−67| = 14
Closest request:
65
Movement:
53 → 65
= 12
Step 2: Head at 65
Remaining Requests:
98, 183, 37, 122, 14, 124, 67
Distances:
|65−98| = 33
|65−183| = 118
|65−37| = 28
|65−122| = 57
|65−14| = 51
|65−124| = 59
|65−67| = 2
Closest request:
67
Movement:
65 → 67
= 2
Step 3: Head at 67
Remaining Requests:
98, 183, 37, 122, 14, 124
Distances:
|67−98| = 31
|67−183| = 116
|67−37| = 30
|67−122| = 55
|67−14| = 53
|67−124| = 57
Closest request:
37
Movement:
67 → 37
= 30
Step 4: Head at 37
Remaining Requests:
98, 183, 122, 14, 124
Distances:
|37−98| = 61
|37−183| = 146
|37−122| = 85
|37−14| = 23
|37−124| = 87
Closest request:
14
Movement:
37 → 14
= 23
Step 5: Head at 14
Remaining Requests:
98, 183, 122, 124
Distances:
|14−98| = 84
|14−183| = 169
|14−122| = 108
|14−124| = 110
Closest request:
98
Movement:
14 → 98
= 84
Step 6: Head at 98
Remaining Requests:
183, 122, 124
Distances:
|98−183| = 85
|98−122| = 24
|98−124| = 26
Closest request:
122
Movement:
98 → 122
= 24
Step 7: Head at 122
Remaining Requests:
183, 124
Distances:
|122−183| = 61
|122−124| = 2
Closest request:
124
Movement:
122 → 124
= 2
Step 8: Head at 124
Remaining Request:
183
Movement:
124 → 183
= 59
5. Final Service Order
The SSTF sequence becomes:
53 → 65 → 67 → 37 → 14 → 98 → 122 → 124 → 183
Key Observation
Notice how SSTF tends to service nearby requests together.
6. Total Head Movement
Calculate total movement:
53 → 65 = 12
65 → 67 = 2
67 → 37 = 30
37 → 14 = 23
14 → 98 = 84
98 → 122 = 24
122 → 124 = 2
124 → 183 = 59
Total:
12 + 2 + 30 + 23 + 84 + 24 + 2 + 59
= 236 Cylinders
Final Answer
Total Head Movement = 236 Cylinders
7. Comparison with FCFS
For the same request sequence:
| Algorithm | Total Head Movement |
|---|---|
| FCFS | 640 |
| SSTF | 236 |
Improvement
Reduction
= 640 − 236
= 404 Cylinders
Percentage Improvement
(404 / 640) × 100
≈ 63.1%
Key Insight
SSTF dramatically reduces unnecessary disk head movement.
8. Why SSTF Performs Better
Most students memorize:
"SSTF reduces seek time."
But understanding why is more important.
SSTF Exploits Spatial Locality
Consider:
65, 67
These cylinders are physically close.
Instead of jumping elsewhere, SSTF services them together.
Result
Less Head Movement
↓
Less Seek Time
↓
Faster Disk Access
Key Insight
SSTF groups nearby requests naturally.
9. Performance Analysis
9.1 Seek Time
Much lower than FCFS.
Reason:
Nearest request chosen every time.
9.2 Throughput
Higher.
Reason:
Less movement
↓
Less waiting
↓
More requests completed
9.3 Average Response Time
Generally lower than FCFS.
Requests near the head are serviced quickly.
9.4 Disk Utilization
Better utilization because the head spends less time moving.
Key Insight
SSTF significantly improves overall disk efficiency.
10. The Hidden Problem: Starvation
This is the most important theoretical limitation of SSTF.
Scenario
Current Head:
50
Pending Requests:
180, 190
Now suppose new requests continuously arrive near:
48, 52, 49, 51, 53
What SSTF Does
Always selects:
48, 49, 51, 52, 53
because they are closer.
What Happens to 180 and 190?
They keep waiting.
More nearby requests arrive.
They wait again.
Potentially forever.
Result
Starvation
Definition
Starvation occurs when a request waits indefinitely because other requests continuously receive priority.
Key Insight
SSTF improves performance by sacrificing fairness.
11. Real-World Analogy
Imagine a taxi driver.
Current Location:
City Center
Passenger Requests:
2 km away
3 km away
50 km away
The driver always chooses the nearest passenger.
Efficient?
Yes
Fair?
No
The passenger 50 km away may wait indefinitely.
Key Insight
SSTF behaves exactly like a nearest-customer strategy.
12. Advantages of SSTF
12.1 Lower Seek Time
Reduces total head movement significantly.
12.2 Better Throughput
More requests serviced per unit time.
12.3 Better Disk Utilization
Head spends less time seeking.
12.4 Simple Improvement over FCFS
Easy to understand and implement.
Key Insight
SSTF offers a large performance gain with relatively low complexity.
13. Disadvantages of SSTF
13.1 Starvation
Far requests may never be serviced.
13.2 Unfair Scheduling
Nearby requests get preferential treatment.
13.3 Not Globally Optimal
Greedy decisions may not produce the best overall path.
13.4 Request Reordering
Service order differs from arrival order.
Key Insight
SSTF optimizes performance but compromises fairness.
14. SSTF at a Glance
| Feature | SSTF |
|---|---|
| Full Form | Shortest Seek Time First |
| Strategy | Closest Request First |
| Type | Greedy Algorithm |
| Seek Time | Low |
| Throughput | High |
| Fairness | Poor |
| Starvation | Possible |
| Complexity | Moderate |
| Performance | Better than FCFS |
Final Insight
SSTF improves disk performance by always selecting the request nearest to the current head position. This significantly reduces seek time and increases throughput compared to FCFS. However, because it continuously favors nearby requests, distant requests may suffer indefinite delays, leading to starvation. SSTF therefore represents the classic trade-off between efficiency and fairness in operating system design.