1. Why SSTF Was Not Enough
SSTF significantly improves performance by always selecting the nearest request. However, this optimization introduces a serious issue: starvation.
Consider a disk head currently servicing requests around the middle of the disk:
Current Head = 50
Pending Requests:
48, 49, 51, 52, 180
SSTF continuously chooses nearby requests:
50 → 49 → 48 → 51 → 52
Now suppose more nearby requests keep arriving:
47, 53, 46, 54...
The request at cylinder 180 may wait indefinitely.
Problems with SSTF
1. Starvation
Requests far from the current head position may never be serviced.
2. Unfair Waiting Time
Some requests receive immediate service while others wait excessively.
3. Unpredictable Behavior
Response times vary significantly depending on request locations.
What OS Designers Wanted
An algorithm that:
Reduces seek time
Prevents starvation
Provides predictable service
Maintains fairness
This led to the development of the SCAN algorithm.
Key Insight
SCAN sacrifices a small amount of performance compared to SSTF in order to guarantee fairness and eliminate starvation.
2. What is SCAN?
SCAN is a disk scheduling algorithm in which the disk head continuously moves in one direction, servicing all requests encountered along the way. When it reaches the end of the disk, it reverses direction and continues servicing requests.
Definition
The disk head sweeps back and forth across the disk, servicing requests in the order they are encountered.
Core Principle
Move in one direction
↓
Serve all requests encountered
↓
Reach disk end
↓
Reverse direction
↓
Repeat
Why Is It Called the Elevator Algorithm?
Because its behavior resembles an elevator:
Elevator goes up
↓
Serves all floors
Reaches top
↓
Comes down
Serves all floors
Similarly:
Disk head moves right
↓
Services requests
Reaches disk end
↓
Moves left
Services requests
Key Insight
The head movement follows a predictable sweep pattern rather than making random jumps.
3. How SCAN Works Internally
Unlike SSTF, SCAN does not continuously search for the nearest request.
Instead, it follows a fixed direction.
Step 1: Determine Current Direction
Example:
Head Position = 53
Direction = Right
Step 2: Separate Requests
Requests greater than 53:
65, 67, 98, 122, 124, 183
Requests less than 53:
37, 14
Step 3: Sort Requests
Since the head is moving right:
Right Side (Ascending):
65 → 67 → 98 → 122 → 124 → 183
Left Side (Descending after reversal):
37 → 14
Step 4: Sweep Right
Serve all requests while moving right.
Step 5: Reach Disk End
Continue until the physical end of the disk.
Step 6: Reverse Direction
After reaching the end, reverse and service remaining requests.
Key Insight
The head behaves like a sweeping arm rather than jumping between requests.
4. Numerical Example
Given
Initial Head Position:
53
Direction:
Right
Request Queue:
98, 183, 37, 122, 14, 124, 65, 67
Disk Range:
0 – 199
Step 1: Split Requests
Right of 53:
65, 67, 98, 122, 124, 183
Left of 53:
37, 14
Step 2: Sort Requests
Right:
65 → 67 → 98 → 122 → 124 → 183
Left:
37 → 14
Step 3: Determine Service Order
Since the head is moving right:
53
↓
65
↓
67
↓
98
↓
122
↓
124
↓
183
↓
199 (disk end)
↓
37
↓
14
Final SCAN Sequence
53 → 65 → 67 → 98 → 122 → 124 → 183 → 199 → 37 → 14
Important Note
Even though there is no request at cylinder 199, SCAN still moves there before reversing.
This is one of the defining characteristics of SCAN.
5. Head Movement Calculation
Step-by-Step Movement
53 → 65 = 12
65 → 67 = 2
67 → 98 = 31
98 → 122 = 24
122 → 124 = 2
124 → 183 = 59
183 → 199 = 16
199 → 37 = 162
37 → 14 = 23
Total Head Movement
12 + 2 + 31 + 24 + 2 + 59 + 16 + 162 + 23
= 331 Cylinders
Final Answer
Total Head Movement = 331 Cylinders
6. Visualizing SCAN Behavior
The movement pattern looks like:
0 --------------------------------------------------- 199
14 37 53 65 67 98 122 124 183
Head
Move Right →
53 → 65 → 67 → 98 → 122 → 124 → 183 → 199
Reverse ←
199 → 37 → 14
Key Observation
Notice that the head moves smoothly in one direction instead of zig-zagging.
7. Why SCAN Performs Better Than FCFS
FCFS Movement
53 → 98 → 183 → 37 → 122 → 14 → 124 ...
The head constantly changes direction.
SCAN Movement
53 → 65 → 67 → 98 → 122 → 124 → 183
Requests in the same direction are grouped together.
Result
Less Direction Changes
↓
Lower Seek Time
↓
Higher Throughput
Key Insight
SCAN exploits directional locality instead of nearest-request locality.
8. Important Characteristics of SCAN
8.1 Direction-Based Scheduling
Requests are serviced according to the current sweep direction.
The head does not choose requests randomly.
8.2 Predictable Behavior
Movement follows a fixed pattern.
This makes response times more predictable.
8.3 Guaranteed Service
Every request will eventually lie in the path of the moving head.
Key Insight
Unlike SSTF, no request can be postponed forever.
9. Starvation Analysis
Does SCAN Suffer from Starvation?
No
Why?
Suppose a request exists at cylinder 180.
Even if new requests continue arriving near cylinder 50:
48, 49, 51, 52...
the head will eventually continue moving toward 180.
It cannot remain permanently near the center.
Result
Every request gets serviced.
Key Insight
SCAN eliminates starvation by forcing the head to sweep across the entire disk.
10. Advantages of SCAN
10.1 No Starvation
Every request eventually gets serviced.
10.2 Better Fairness
Waiting times are more balanced.
10.3 Lower Seek Time Than FCFS
Head movement is more organized.
10.4 Higher Throughput
Reduced unnecessary movements improve performance.
10.5 Predictable Service
Requests experience more consistent waiting times.
Key Insight
SCAN provides a practical balance between efficiency and fairness.
11. Disadvantages of SCAN
11.1 Unnecessary Movement
The head moves to the disk end even if no request exists there.
Example:
Last Request = 183
Disk End = 199
Movement:
183 → 199
serves no request.
11.2 Edge Delay
Requests near disk ends may experience longer waits.
11.3 Not Always Optimal
Sometimes SSTF produces lower total head movement.
11.4 Direction Dependency
Performance depends on the current direction of the head.
Key Insight
SCAN improves fairness but occasionally performs extra movement.
12. Real-World Analogy
Think of an elevator in a building.
Elevator Behavior
Ground Floor
↓
Moves Up
Stops at requested floors
Reaches Top
Moves Down
Stops at requested floors
Disk Head Behavior
Start Position
↓
Moves Right
Services requests
Reaches Disk End
Moves Left
Services requests
Key Insight
SCAN is essentially an elevator operating on disk tracks instead of building floors.
13. Comparison with FCFS and SSTF
| Feature | FCFS | SSTF | SCAN |
|---|---|---|---|
| Strategy | Arrival Order | Nearest Request | Directional Sweep |
| Seek Time | High | Lowest (Local) | Low |
| Throughput | Low | High | High |
| Fairness | High | Low | High |
| Starvation | No | Yes | No |
| Predictability | High | Low | High |
| Complexity | Simple | Moderate | Moderate |
14. SSTF vs SCAN (Most Important Exam Comparison)
SSTF
Chooses nearest request
Advantages:
Lower seek time
Higher local efficiency
Disadvantages:
Starvation possible
Unfair
SCAN
Moves in one direction and sweeps the disk
Advantages:
No starvation
Better fairness
Predictable
Disadvantages:
Extra movement to disk ends
Key Insight
SSTF optimizes performance, while SCAN balances performance and fairness.
15. SCAN at a Glance
| Property | SCAN |
|---|---|
| Also Called | Elevator Algorithm |
| Strategy | Sweep in one direction |
| Starvation | No |
| Fairness | High |
| Seek Time | Low |
| Throughput | Good |
| Complexity | Moderate |
| Disk End Traversal | Yes |
| Practicality | High |
Final Insight
SCAN improves upon SSTF by eliminating starvation while still maintaining good performance. Instead of continuously chasing the nearest request, the disk head moves systematically across the disk, servicing all requests in its path before reversing direction. This makes SCAN one of the most important and widely studied disk scheduling algorithms because it achieves a practical balance between efficiency, fairness, and predictability.