Operating SystemsDisk Scheduling Algorithms

Disk Scheduling Algorithms

LevelIntermediate

Duration90 mins

TopicDisk Scheduling Algorithms

3 / 5

SCAN (Elevator Algorithm)

The Elevator Insight

FCFS is fair but inefficient. SSTF is efficient but unfair. Is there a way to achieve both high throughput AND bounded waiting times?

The answer comes from an unlikely source: elevators. Consider how an elevator services floor requests:

The elevator moves in one direction (up or down)
It stops at every requested floor along the way
When it reaches the end, it reverses direction
It services requests in the opposite direction

This simple discipline—move in one direction until you can't, then reverse—eliminates starvation while maintaining excellent seek optimization. An elevator doesn't skip floors to jump back and forth; neither should a disk head.

This insight gives us SCAN, also known as the Elevator Algorithm—the most influential disk scheduling algorithm ever designed.

What You Will Learn

By the end of this page, you will master the SCAN algorithm—its mechanics, performance characteristics, bounded wait time guarantee, and variations. You'll understand why SCAN became the foundation for disk scheduling in virtually every production operating system.

The SCAN Algorithm

SCAN moves the disk arm in one direction, servicing all requests along the way, until it reaches the end of the disk. Then it reverses direction and repeats.

Algorithm Definition:

The disk arm has a current direction (toward cylinder 0 or toward cylinder N-1)
Move the arm in the current direction
Service all pending requests at cylinders along the path
When reaching the end of the disk (cylinder 0 or N-1):
- Reverse direction
- Continue servicing requests in the new direction
Repeat indefinitely

Critical Detail: The arm travels to the physical end of the disk, not just the extreme request. This is what distinguishes SCAN from LOOK (covered later).

Formal Description:

Let $H$ be the current head position, $D \in {-1, +1}$ be the direction, and $N$ be the total cylinders.

The next cylinder to service is: $$\text{next} = \begin{cases} \min{c : c > H} & \text{if } D = +1 \text{ and } \exists c > H N-1 \text{ (end reached)} & \text{if } D = +1 \text{ and } exists c > H \max{c : c < H} & \text{if } D = -1 \text{ and } \exists c < H 0 \text{ (end reached)} & \text{if } D = -1 \text{ and } exists c < H \end{cases}$$

After reaching an end, reverse: $D \leftarrow -D$

scan_scheduler.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
"""
SCAN (Elevator) Disk Scheduling Algorithm
 
Implements the classic SCAN algorithm with direction tracking
and comprehensive metrics for analysis.
"""
 
from dataclasses import dataclass, field
from typing import List, Tuple, Optional
from enum import Enum
 
class Direction(Enum):
    """Arm movement direction."""
    INWARD = -1   # Toward cylinder 0
    OUTWARD = 1   # Toward cylinder N-1
 
@dataclass
class DiskRequest:
    """Represents a disk I/O request."""
    request_id: int
    cylinder: int
    arrival_time: float
 
@dataclass
class SCANScheduler:
    """
    SCAN Disk Scheduling Implementation
    
    Moves the disk arm in one direction until reaching the disk end,
    servicing all requests along the way, then reverses direction.
    """
    initial_head_position: int
    total_cylinders: int
    initial_direction: Direction = Direction.OUTWARD
    
    # State
    head_position: int = field(init=False)
    direction: Direction = field(init=False)
    pending: List[DiskRequest] = field(default_factory=list)
    
    # Metrics
    total_seek_distance: int = 0
    requests_serviced: int = 0
    service_order: List[int] = field(default_factory=list)
    seek_sequence: List[Tuple[int, int, str]] = field(default_factory=list)
    direction_reversals: int = 0
    
    def __post_init__(self):
        self.head_position = self.initial_head_position
        self.direction = self.initial_direction
    
    def submit_request(self, request: DiskRequest) -> None:
        """Add a request to pending queue."""
        self.pending.append(request)
    
    def get_requests_in_direction(self) -> List[DiskRequest]:
        """
        Get requests in the current direction, sorted by cylinder.
        
        If moving OUTWARD (toward N-1): requests with cylinder > head, ascending
        If moving INWARD (toward 0): requests with cylinder < head, descending
        """
        if self.direction == Direction.OUTWARD:
            # Get requests ahead (higher cylinders), sort ascending
            ahead = [r for r in self.pending if r.cylinder >= self.head_position]
            return sorted(ahead, key=lambda r: r.cylinder)
        else:
            # Get requests behind (lower cylinders), sort descending
            behind = [r for r in self.pending if r.cylinder <= self.head_position]
            return sorted(behind, key=lambda r: r.cylinder, reverse=True)
    
    def move_to_end(self) -> int:
        """
        Move to the end of the disk in the current direction.
        Returns the seek distance for this move.
        """
        if self.direction == Direction.OUTWARD:
            seek = (self.total_cylinders - 1) - self.head_position
            target = self.total_cylinders - 1
        else:
            seek = self.head_position - 0
            target = 0
        
        self.seek_sequence.append((
            self.head_position, 
            target, 
            f"End ({self.direction.name})"
        ))
        self.head_position = target
        self.total_seek_distance += seek
        return seek
    
    def reverse_direction(self) -> None:
        """Reverse the arm direction."""
        self.direction = (
            Direction.INWARD if self.direction == Direction.OUTWARD 
            else Direction.OUTWARD
        )
        self.direction_reversals += 1
    
    def service_request(self, request: DiskRequest) -> dict:
        """Service a single request."""
        seek = abs(request.cylinder - self.head_position)
        
        self.seek_sequence.append((
            self.head_position,
            request.cylinder,
            f"Request {request.request_id}"
        ))
        
        self.head_position = request.cylinder
        self.pending.remove(request)
        self.total_seek_distance += seek
        self.requests_serviced += 1
        self.service_order.append(request.cylinder)
        
        return {
            "request_id": request.request_id,
            "cylinder": request.cylinder,
            "seek_distance": seek,
        }
    
    def run_scheduling(self) -> dict:
        """
        Execute SCAN scheduling until all requests serviced.
        """
        results = []
        
        while self.pending:
            # Get requests in current direction
            direction_requests = self.get_requests_in_direction()
            
            if direction_requests:
                # Service all requests in this direction
                for request in direction_requests:
                    result = self.service_request(request)
                    results.append(result)
            
            # No more requests in this direction
            if self.pending:
                # Move to end and reverse
                self.move_to_end()
                self.reverse_direction()
        
        return {
            "algorithm": "SCAN",
            "service_order": self.service_order,
            "total_seek_distance": self.total_seek_distance,
            "average_seek_distance": (
                self.total_seek_distance / self.requests_serviced
                if self.requests_serviced > 0 else 0
            ),
            "requests_serviced": self.requests_serviced,
            "direction_reversals": self.direction_reversals,
            "seek_sequence": self.seek_sequence,
            "detailed_results": results,
        }
 
 
def demonstrate_scan():
    """
    Demonstrate SCAN with the standard example for comparison.
    
    Disk: 200 cylinders (0-199)
    Initial head: 50
    Initial direction: OUTWARD (toward 199)
    Requests: 95, 180, 34, 119, 11, 123, 62, 64
    """
    scheduler = SCANScheduler(
        initial_head_position=50,
        total_cylinders=200,
        initial_direction=Direction.OUTWARD
    )
    
    requests = [95, 180, 34, 119, 11, 123, 62, 64]
    for i, cyl in enumerate(requests):
        scheduler.submit_request(DiskRequest(i, cyl, 0.0))
    
    results = scheduler.run_scheduling()
    
    print("=== SCAN (Elevator) Disk Scheduling Demo ===")
    print(f"Disk: 200 cylinders, Head starts at 50")
    print(f"Initial direction: OUTWARD (toward 199)")
    print(f"Requests: {requests}
")
    
    print("Execution trace:")
    for from_cyl, to_cyl, note in results['seek_sequence']:
        print(f"  {from_cyl} -> {to_cyl} [{note}]")
    
    print(f"
Service order: {results['service_order']}")
    print(f"Total seek distance: {results['total_seek_distance']} cylinders")
    print(f"Average seek: {results['average_seek_distance']:.2f} cylinders")
    print(f"Direction reversals: {results['direction_reversals']}")
    
    # Comparison
    print("
=== Algorithm Comparison ===")
    print(f"FCFS:  644 cylinders (baseline)")
    print(f"SSTF:  208 cylinders (67.7% improvement)")
    print(f"SCAN:  {results['total_seek_distance']} cylinders", end="")
    print(f" ({(1 - results['total_seek_distance']/644)*100:.1f}% improvement)")
    
    return results
 
 
if __name__ == "__main__":
    demonstrate_scan()

Worked Example: SCAN Trace

Let's trace SCAN execution using our standard example, with initial direction OUTWARD (toward cylinder 199).

Scenario:

200 cylinders (0-199)
Head starts at cylinder 50
Direction: OUTWARD
Pending requests: {95, 180, 34, 119, 11, 123, 62, 64}

SCAN Execution Trace (Initial Direction: OUTWARD)
Step	Action	Head Movement	Seek Distance	Cumulative
Initial	Start	Head at 50	—	0
1	Service request	50 → 62	12	12
2	Service request	62 → 64	2	14
3	Service request	64 → 95	31	45
4	Service request	95 → 119	24	69
5	Service request	119 → 123	4	73
6	Service request	123 → 180	57	130
7	Move to end	180 → 199	19	149
8	Reverse direction	Direction → INWARD	—	149
9	Service request	199 → 34	165	314
10	Service request	34 → 11	23	337

SCAN Performance Metrics:

$$\text{Total Seek Distance} = 12 + 2 + 31 + 24 + 4 + 57 + 19 + 165 + 23 = 337 \text{ cylinders}$$

$$\text{Average Seek Distance} = \frac{337}{8} = 42.1 \text{ cylinders}$$

Service Order: 62 → 64 → 95 → 119 → 123 → 180 → 34 → 11

Converting Mermaid diagram...

Algorithm Comparison for Standard Example
Algorithm	Total Seek	Avg Seek	vs FCFS	Starvation?
FCFS	644 cyl	80.5 cyl	Baseline	No
SSTF	208 cyl	26.0 cyl	-67.7%	Yes
SCAN	337 cyl	42.1 cyl	-47.7%	No

The SCAN Tradeoff

SCAN uses 337 cylinders vs SSTF's 208—about 62% more seek distance. However, SCAN guarantees that every request will be serviced within at most two full disk sweeps. This bounded latency often outweighs the throughput difference in production systems.

Bounded Wait Time Guarantee

SCAN's most important property is its bounded wait time guarantee—no request can be starved, and the maximum wait time is calculable.

Maximum Wait Analysis:

Consider the worst-case scenario for a request:

Request arrives at cylinder $c$ just after the head passes $c$ moving away
The head continues to the disk end
The head reverses and sweeps back across the entire disk
The head finally reaches $c$ again

Maximum Wait Time Formula:

$$W_{max} = 2 \cdot N \cdot T_{seek_per_cylinder}$$

Where:

$N$ = total cylinders
$T_{seek_per_cylinder}$ = time to traverse one cylinder (typically ~0.01ms)

For a 10,000-cylinder disk with 0.01ms per cylinder: $$W_{max} = 2 \times 10,000 \times 0.01ms = 200ms$$

This is a hard upper bound—no request will ever wait longer, regardless of workload.

Expected Wait Time:

For uniformly distributed requests, the expected wait is approximately:

$$E[W] \approx N \cdot T_{seek_per_cylinder}$$

Half the maximum, because on average a request arrives when the head is halfway through one direction.

Variance:

Unlike SSTF where variance can be unbounded, SCAN's wait time variance is:

$$Var[W] \approx \frac{N^2 \cdot T^2}{12}$$

Bounded variance means predictable latency distribution—essential for SLA compliance.

Why Bounded Matters

With SSTF, you cannot predict worst-case latency—it could be seconds, minutes, or infinite. With SCAN, you can compute the absolute worst case mathematically and design systems accordingly. This predictability is invaluable for real-time systems, databases with latency SLAs, and any application where tail latency matters.

Fairness Analysis

While SCAN eliminates starvation, it introduces a subtle fairness bias that's important to understand.

The Edge Cylinder Problem:

Consider how often different cylinders are visited:

Center cylinders (like cylinder 100 on a 200-cylinder disk): Visited on every outward AND inward sweep
Edge cylinders (like cylinder 0 or 199): Visited only once per full cycle

This means requests at disk edges wait, on average, longer than requests at the center.

Wait Time by Position:

For a request at cylinder $c$ (disk has $N$ cylinders, head at center):

$$E[W_c] \propto \frac{|c - N/2|}{N/2} \cdot W_{max}$$

Center cylinders have wait ~50% of max; edge cylinders approach $W_{max}$.

Expected Wait Time by Cylinder Position (200-cylinder disk)
Cylinder	Position	Expected Wait (relative)	Probability of Long Wait
0	Edge (minimum)	~100% of max	High
50	Quarter	~75% of max	Medium-High
100	Center	~50% of max	Medium
150	Three-quarter	~75% of max	Medium-High
199	Edge (maximum)	~100% of max	High

Impact on Workloads:

This bias becomes problematic when:

Hot data at edges: If frequently-accessed data is stored at cylinder 0 (e.g., file system metadata in first sectors), those accesses experience higher average latency
Uneven aging: Edge requests age unevenly—they always wait for a complete sweep in one direction
Burst patterns: If bursts of requests alternately hit edges, the center benefits from both sweeps while edges wait

C-SCAN addresses this fairness issue, as we'll see in the next page.

Practical Fairness Concern

In real file systems, cylinder 0 often contains critical metadata (boot sectors, superblocks). This means the most critical data experiences the worst average latency under SCAN. This motivated the development of C-SCAN.

Performance Analysis

SCAN's performance characteristics depend heavily on workload distribution and queue depth.

Total Seek Distance Formula:

For a set of requests spanning from cylinder $min$ to cylinder $max$, starting at position $H$ with direction $D$:

If moving toward $max$ first: $$D_{SCAN} = (max - H) + (max - min) + (min \text{ to end penalty})$$

General case (moving to end each direction): $$D_{SCAN} \leq 2 \times (N-1)$$

SCAN never traverses more than twice the disk width—a hard upper bound.

SCAN Performance by Workload Type
Workload	Expected Seek	Comparison to SSTF	Notes
Uniform random	~1.33N per pass	10-30% worse	Competitive performance
Clustered single	~cluster width	Similar	Both excellent
Two clusters	Distance between + widths	Slightly worse	SSTF may jump; SCAN sweeps
Edge-heavy	~2N per cycle	Much worse	SCAN always goes to ends
Sequential	~N	Identical	Both optimal

Queue Depth Impact:

Like SSTF, SCAN benefits from deeper queues:

Shallow queue (1-2 requests): Little opportunity for optimization; similar to FCFS
Moderate queue (5-20 requests): SCAN achieves 40-60% of SSTF's throughput advantage
Deep queue (50+ requests): SCAN approaches SSTF performance while maintaining fairness

The Sweep Efficiency Principle:

SCAN's efficiency improves as the "density" of requests along the sweep path increases. With many requests, the head makes few wasted movements—most cylinder transitions service a pending request.

When SCAN Beats SSTF

For clustered workloads where data locality is high, SCAN can actually outperform SSTF. SSTF may waste seeks bouncing within a cluster, while SCAN efficiently sweeps through it once. Combined with SCAN's fairness, this makes it superior for many real workloads.

Implementation Details

Efficient SCAN implementation requires maintaining sorted request structures for quick access to the next request in the current direction.

efficient_scan.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
"""
Efficient SCAN Implementation
 
Uses two sorted lists for O(log n) insertion and O(1) selection.
Demonstrates production-quality implementation patterns.
"""
 
import bisect
from dataclasses import dataclass, field
from typing import List, Optional, Tuple
from enum import Enum
 
class Direction(Enum):
    INWARD = -1
    OUTWARD = 1
 
@dataclass
class EfficientSCANScheduler:
    """
    Optimized SCAN using two sorted lists.
    
    Maintains:
    - outward_queue: cylinders > head, sorted ascending
    - inward_queue: cylinders <= head, sorted descending (stored ascending, read reversed)
    
    This allows O(1) selection of next request and O(log n) insertion.
    """
    total_cylinders: int
    head_position: int
    direction: Direction = Direction.OUTWARD
    
    # Two sorted queues
    outward_queue: List[int] = field(default_factory=list)  # Sorted ascending
    inward_queue: List[int] = field(default_factory=list)   # Sorted ascending, pop from end
    
    # Metrics
    total_seek: int = 0
    service_order: List[int] = field(default_factory=list)
    
    def submit(self, cylinder: int) -> None:
        """
        O(log n) insertion into appropriate queue.
        """
        if cylinder > self.head_position:
            bisect.insort(self.outward_queue, cylinder)
        elif cylinder < self.head_position:
            bisect.insort(self.inward_queue, cylinder)
        else:
            # At head position - goes in current direction's queue
            if self.direction == Direction.OUTWARD:
                bisect.insort(self.outward_queue, cylinder)
            else:
                bisect.insort(self.inward_queue, cylinder)
    
    def get_next(self) -> Optional[int]:
        """
        O(1) selection of next request.
        Returns None if no requests pending.
        """
        if self.direction == Direction.OUTWARD:
            if self.outward_queue:
                return self.outward_queue[0]  # Smallest cylinder > head
            elif self.inward_queue:
                # Must go to end and reverse
                self._go_to_end()
                self._reverse()
                return self.inward_queue[-1] if self.inward_queue else None
        else:
            if self.inward_queue:
                return self.inward_queue[-1]  # Largest cylinder < head
            elif self.outward_queue:
                # Must go to end and reverse
                self._go_to_end()
                self._reverse()
                return self.outward_queue[0] if self.outward_queue else None
        return None
    
    def _go_to_end(self) -> None:
        """Move head to disk end in current direction."""
        if self.direction == Direction.OUTWARD:
            end = self.total_cylinders - 1
        else:
            end = 0
        seek = abs(end - self.head_position)
        self.total_seek += seek
        self.head_position = end
    
    def _reverse(self) -> None:
        """Reverse direction."""
        self.direction = (
            Direction.INWARD if self.direction == Direction.OUTWARD
            else Direction.OUTWARD
        )
    
    def service_next(self) -> Optional[Tuple[int, int]]:
        """
        Service the next request.
        Returns (cylinder, seek_distance) or None if empty.
        """
        next_cyl = self.get_next()
        if next_cyl is None:
            return None
        
        # Remove from appropriate queue
        if self.direction == Direction.OUTWARD:
            self.outward_queue.pop(0)
        else:
            self.inward_queue.pop()
        
        seek = abs(next_cyl - self.head_position)
        self.total_seek += seek
        self.head_position = next_cyl
        self.service_order.append(next_cyl)
        
        return (next_cyl, seek)
    
    def run_all(self) -> dict:
        """Run until all requests serviced."""
        while self.outward_queue or self.inward_queue:
            self.service_next()
        
        return {
            "service_order": self.service_order,
            "total_seek": self.total_seek,
        }
 
 
# Example usage
if __name__ == "__main__":
    scheduler = EfficientSCANScheduler(
        total_cylinders=200,
        head_position=50,
        direction=Direction.OUTWARD
    )
    
    for cyl in [95, 180, 34, 119, 11, 123, 62, 64]:
        scheduler.submit(cyl)
    
    result = scheduler.run_all()
    print(f"Service order: {result['service_order']}")
    print(f"Total seek: {result['total_seek']} cylinders")

SCAN Implementation Complexity
Operation	Naive	Optimized (Two Lists)	Notes
Insert request	O(1)	O(log n)	Sorted insertion
Select next	O(n)	O(1)	Head of appropriate list
Service request	O(n)	O(1)	Pop from list
Direction reversal	O(1)	O(1)	Flag toggle
Memory	O(n)	O(n)	Same total storage

Real-World Applications

SCAN and its variants are the foundation of disk scheduling in virtually every production operating system.

SCAN in Operating Systems

•Linux: Uses deadline scheduler (SCAN-based) and CFQ (incorporating SCAN principles) as default schedulers for HDDs. The newer mq-deadline scheduler continues this tradition.
•Windows: NTFS uses SCAN-based scheduling with priority support. The Windows Storage Stack includes SCAN variants for different device types.
•FreeBSD: The CAM (Common Access Method) layer implements SCAN-based scheduling for disk devices.
•Database Systems: Oracle, PostgreSQL, and MySQL all benefit from OS-level SCAN scheduling for their disk I/O patterns.
•Storage Controllers: Enterprise RAID controllers implement SCAN variants in hardware/firmware for maximum efficiency.

The SSD Era

With SSDs, SCAN's benefits diminish—there's no physical head to optimize. Modern Linux uses the 'noop' or 'none' scheduler for SSDs, essentially FCFS. However, SCAN remains critical for HDDs, which still dominate cold storage and high-capacity deployments.

Summary: SCAN Disk Scheduling

We have thoroughly examined the SCAN (Elevator) algorithm. Let's consolidate the key insights:

Key Takeaways

•SCAN moves in one direction until reaching disk end, then reverses—like an elevator
•SCAN guarantees bounded wait time — maximum wait is two full disk sweeps
•Performance is 40-60% better than FCFS while maintaining starvation-freedom
•SCAN has positional unfairness — edge cylinders wait longer than center cylinders
•Implementation uses two sorted lists for O(1) selection and O(log n) insertion
•SCAN is the foundation of virtually all production disk schedulers
•SCAN moves to physical disk ends, not just to extreme requests (vs. LOOK)

What's Next:

SCAN's positional unfairness—where edge cylinders experience longer waits—motivates an enhancement. In the next page, we'll study C-SCAN (Circular SCAN), which provides uniform wait time across all cylinder positions by treating the disk as a circular structure.

Page Complete

You now understand the SCAN algorithm at an expert level—its elevator-inspired design, bounded wait guarantee, positional fairness characteristics, and implementation strategies. SCAN represents the fundamental breakthrough in disk scheduling that made bounded-latency storage systems possible.

3 / 5

Loading learning content...

Operating SystemsDisk Scheduling Algorithms

Disk Scheduling Algorithms

LevelIntermediate

Duration90 mins

TopicDisk Scheduling Algorithms

3 / 5

SCAN (Elevator Algorithm)

The Elevator Insight

FCFS is fair but inefficient. SSTF is efficient but unfair. Is there a way to achieve both high throughput AND bounded waiting times?

The answer comes from an unlikely source: elevators. Consider how an elevator services floor requests:

The elevator moves in one direction (up or down)
It stops at every requested floor along the way
When it reaches the end, it reverses direction
It services requests in the opposite direction

This insight gives us SCAN, also known as the Elevator Algorithm—the most influential disk scheduling algorithm ever designed.

What You Will Learn

The SCAN Algorithm

SCAN moves the disk arm in one direction, servicing all requests along the way, until it reaches the end of the disk. Then it reverses direction and repeats.

Algorithm Definition:

The disk arm has a current direction (toward cylinder 0 or toward cylinder N-1)
Move the arm in the current direction
Service all pending requests at cylinders along the path
When reaching the end of the disk (cylinder 0 or N-1):
- Reverse direction
- Continue servicing requests in the new direction
Repeat indefinitely

Critical Detail: The arm travels to the physical end of the disk, not just the extreme request. This is what distinguishes SCAN from LOOK (covered later).

Formal Description:

Let $H$ be the current head position, $D \in {-1, +1}$ be the direction, and $N$ be the total cylinders.

After reaching an end, reverse: $D \leftarrow -D$

scan_scheduler.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
"""
SCAN (Elevator) Disk Scheduling Algorithm
 
Implements the classic SCAN algorithm with direction tracking
and comprehensive metrics for analysis.
"""
 
from dataclasses import dataclass, field
from typing import List, Tuple, Optional
from enum import Enum
 
class Direction(Enum):
    """Arm movement direction."""
    INWARD = -1   # Toward cylinder 0
    OUTWARD = 1   # Toward cylinder N-1
 
@dataclass
class DiskRequest:
    """Represents a disk I/O request."""
    request_id: int
    cylinder: int
    arrival_time: float
 
@dataclass
class SCANScheduler:
    """
    SCAN Disk Scheduling Implementation
    
    Moves the disk arm in one direction until reaching the disk end,
    servicing all requests along the way, then reverses direction.
    """
    initial_head_position: int
    total_cylinders: int
    initial_direction: Direction = Direction.OUTWARD
    
    # State
    head_position: int = field(init=False)
    direction: Direction = field(init=False)
    pending: List[DiskRequest] = field(default_factory=list)
    
    # Metrics
    total_seek_distance: int = 0
    requests_serviced: int = 0
    service_order: List[int] = field(default_factory=list)
    seek_sequence: List[Tuple[int, int, str]] = field(default_factory=list)
    direction_reversals: int = 0
    
    def __post_init__(self):
        self.head_position = self.initial_head_position
        self.direction = self.initial_direction
    
    def submit_request(self, request: DiskRequest) -> None:
        """Add a request to pending queue."""
        self.pending.append(request)
    
    def get_requests_in_direction(self) -> List[DiskRequest]:
        """
        Get requests in the current direction, sorted by cylinder.
        
        If moving OUTWARD (toward N-1): requests with cylinder > head, ascending
        If moving INWARD (toward 0): requests with cylinder < head, descending
        """
        if self.direction == Direction.OUTWARD:
            # Get requests ahead (higher cylinders), sort ascending
            ahead = [r for r in self.pending if r.cylinder >= self.head_position]
            return sorted(ahead, key=lambda r: r.cylinder)
        else:
            # Get requests behind (lower cylinders), sort descending
            behind = [r for r in self.pending if r.cylinder <= self.head_position]
            return sorted(behind, key=lambda r: r.cylinder, reverse=True)
    
    def move_to_end(self) -> int:
        """
        Move to the end of the disk in the current direction.
        Returns the seek distance for this move.
        """
        if self.direction == Direction.OUTWARD:
            seek = (self.total_cylinders - 1) - self.head_position
            target = self.total_cylinders - 1
        else:
            seek = self.head_position - 0
            target = 0
        
        self.seek_sequence.append((
            self.head_position, 
            target, 
            f"End ({self.direction.name})"
        ))
        self.head_position = target
        self.total_seek_distance += seek
        return seek
    
    def reverse_direction(self) -> None:
        """Reverse the arm direction."""
        self.direction = (
            Direction.INWARD if self.direction == Direction.OUTWARD 
            else Direction.OUTWARD
        )
        self.direction_reversals += 1
    
    def service_request(self, request: DiskRequest) -> dict:
        """Service a single request."""
        seek = abs(request.cylinder - self.head_position)
        
        self.seek_sequence.append((
            self.head_position,
            request.cylinder,
            f"Request {request.request_id}"
        ))
        
        self.head_position = request.cylinder
        self.pending.remove(request)
        self.total_seek_distance += seek
        self.requests_serviced += 1
        self.service_order.append(request.cylinder)
        
        return {
            "request_id": request.request_id,
            "cylinder": request.cylinder,
            "seek_distance": seek,
        }
    
    def run_scheduling(self) -> dict:
        """
        Execute SCAN scheduling until all requests serviced.
        """
        results = []
        
        while self.pending:
            # Get requests in current direction
            direction_requests = self.get_requests_in_direction()
            
            if direction_requests:
                # Service all requests in this direction
                for request in direction_requests:
                    result = self.service_request(request)
                    results.append(result)
            
            # No more requests in this direction
            if self.pending:
                # Move to end and reverse
                self.move_to_end()
                self.reverse_direction()
        
        return {
            "algorithm": "SCAN",
            "service_order": self.service_order,
            "total_seek_distance": self.total_seek_distance,
            "average_seek_distance": (
                self.total_seek_distance / self.requests_serviced
                if self.requests_serviced > 0 else 0
            ),
            "requests_serviced": self.requests_serviced,
            "direction_reversals": self.direction_reversals,
            "seek_sequence": self.seek_sequence,
            "detailed_results": results,
        }
 
 
def demonstrate_scan():
    """
    Demonstrate SCAN with the standard example for comparison.
    
    Disk: 200 cylinders (0-199)
    Initial head: 50
    Initial direction: OUTWARD (toward 199)
    Requests: 95, 180, 34, 119, 11, 123, 62, 64
    """
    scheduler = SCANScheduler(
        initial_head_position=50,
        total_cylinders=200,
        initial_direction=Direction.OUTWARD
    )
    
    requests = [95, 180, 34, 119, 11, 123, 62, 64]
    for i, cyl in enumerate(requests):
        scheduler.submit_request(DiskRequest(i, cyl, 0.0))
    
    results = scheduler.run_scheduling()
    
    print("=== SCAN (Elevator) Disk Scheduling Demo ===")
    print(f"Disk: 200 cylinders, Head starts at 50")
    print(f"Initial direction: OUTWARD (toward 199)")
    print(f"Requests: {requests}
")
    
    print("Execution trace:")
    for from_cyl, to_cyl, note in results['seek_sequence']:
        print(f"  {from_cyl} -> {to_cyl} [{note}]")
    
    print(f"
Service order: {results['service_order']}")
    print(f"Total seek distance: {results['total_seek_distance']} cylinders")
    print(f"Average seek: {results['average_seek_distance']:.2f} cylinders")
    print(f"Direction reversals: {results['direction_reversals']}")
    
    # Comparison
    print("
=== Algorithm Comparison ===")
    print(f"FCFS:  644 cylinders (baseline)")
    print(f"SSTF:  208 cylinders (67.7% improvement)")
    print(f"SCAN:  {results['total_seek_distance']} cylinders", end="")
    print(f" ({(1 - results['total_seek_distance']/644)*100:.1f}% improvement)")
    
    return results
 
 
if __name__ == "__main__":
    demonstrate_scan()

Worked Example: SCAN Trace

Let's trace SCAN execution using our standard example, with initial direction OUTWARD (toward cylinder 199).

Scenario:

200 cylinders (0-199)
Head starts at cylinder 50
Direction: OUTWARD
Pending requests: {95, 180, 34, 119, 11, 123, 62, 64}

SCAN Execution Trace (Initial Direction: OUTWARD)
Step	Action	Head Movement	Seek Distance	Cumulative
Initial	Start	Head at 50	—	0
1	Service request	50 → 62	12	12
2	Service request	62 → 64	2	14
3	Service request	64 → 95	31	45
4	Service request	95 → 119	24	69
5	Service request	119 → 123	4	73
6	Service request	123 → 180	57	130
7	Move to end	180 → 199	19	149
8	Reverse direction	Direction → INWARD	—	149
9	Service request	199 → 34	165	314
10	Service request	34 → 11	23	337

SCAN Performance Metrics:

$$\text{Total Seek Distance} = 12 + 2 + 31 + 24 + 4 + 57 + 19 + 165 + 23 = 337 \text{ cylinders}$$

$$\text{Average Seek Distance} = \frac{337}{8} = 42.1 \text{ cylinders}$$

Service Order: 62 → 64 → 95 → 119 → 123 → 180 → 34 → 11

Converting Mermaid diagram...

Algorithm Comparison for Standard Example
Algorithm	Total Seek	Avg Seek	vs FCFS	Starvation?
FCFS	644 cyl	80.5 cyl	Baseline	No
SSTF	208 cyl	26.0 cyl	-67.7%	Yes
SCAN	337 cyl	42.1 cyl	-47.7%	No

The SCAN Tradeoff

Bounded Wait Time Guarantee

SCAN's most important property is its bounded wait time guarantee—no request can be starved, and the maximum wait time is calculable.

Maximum Wait Analysis:

Consider the worst-case scenario for a request:

Request arrives at cylinder $c$ just after the head passes $c$ moving away
The head continues to the disk end
The head reverses and sweeps back across the entire disk
The head finally reaches $c$ again

Maximum Wait Time Formula:

$$W_{max} = 2 \cdot N \cdot T_{seek_per_cylinder}$$

Where:

$N$ = total cylinders
$T_{seek_per_cylinder}$ = time to traverse one cylinder (typically ~0.01ms)

For a 10,000-cylinder disk with 0.01ms per cylinder: $$W_{max} = 2 \times 10,000 \times 0.01ms = 200ms$$

This is a hard upper bound—no request will ever wait longer, regardless of workload.

Expected Wait Time:

For uniformly distributed requests, the expected wait is approximately:

$$E[W] \approx N \cdot T_{seek_per_cylinder}$$

Half the maximum, because on average a request arrives when the head is halfway through one direction.

Variance:

Unlike SSTF where variance can be unbounded, SCAN's wait time variance is:

$$Var[W] \approx \frac{N^2 \cdot T^2}{12}$$

Bounded variance means predictable latency distribution—essential for SLA compliance.

Why Bounded Matters

Fairness Analysis

While SCAN eliminates starvation, it introduces a subtle fairness bias that's important to understand.

The Edge Cylinder Problem:

Consider how often different cylinders are visited:

Center cylinders (like cylinder 100 on a 200-cylinder disk): Visited on every outward AND inward sweep
Edge cylinders (like cylinder 0 or 199): Visited only once per full cycle

This means requests at disk edges wait, on average, longer than requests at the center.

Wait Time by Position:

For a request at cylinder $c$ (disk has $N$ cylinders, head at center):

$$E[W_c] \propto \frac{|c - N/2|}{N/2} \cdot W_{max}$$

Center cylinders have wait ~50% of max; edge cylinders approach $W_{max}$.

Expected Wait Time by Cylinder Position (200-cylinder disk)
Cylinder	Position	Expected Wait (relative)	Probability of Long Wait
0	Edge (minimum)	~100% of max	High
50	Quarter	~75% of max	Medium-High
100	Center	~50% of max	Medium
150	Three-quarter	~75% of max	Medium-High
199	Edge (maximum)	~100% of max	High

Impact on Workloads:

This bias becomes problematic when:

Hot data at edges: If frequently-accessed data is stored at cylinder 0 (e.g., file system metadata in first sectors), those accesses experience higher average latency
Uneven aging: Edge requests age unevenly—they always wait for a complete sweep in one direction
Burst patterns: If bursts of requests alternately hit edges, the center benefits from both sweeps while edges wait

C-SCAN addresses this fairness issue, as we'll see in the next page.

Practical Fairness Concern

Performance Analysis

SCAN's performance characteristics depend heavily on workload distribution and queue depth.

Total Seek Distance Formula:

For a set of requests spanning from cylinder $min$ to cylinder $max$, starting at position $H$ with direction $D$:

If moving toward $max$ first: $$D_{SCAN} = (max - H) + (max - min) + (min \text{ to end penalty})$$

General case (moving to end each direction): $$D_{SCAN} \leq 2 \times (N-1)$$

SCAN never traverses more than twice the disk width—a hard upper bound.

SCAN Performance by Workload Type
Workload	Expected Seek	Comparison to SSTF	Notes
Uniform random	~1.33N per pass	10-30% worse	Competitive performance
Clustered single	~cluster width	Similar	Both excellent
Two clusters	Distance between + widths	Slightly worse	SSTF may jump; SCAN sweeps
Edge-heavy	~2N per cycle	Much worse	SCAN always goes to ends
Sequential	~N	Identical	Both optimal

Queue Depth Impact:

Like SSTF, SCAN benefits from deeper queues:

Shallow queue (1-2 requests): Little opportunity for optimization; similar to FCFS
Moderate queue (5-20 requests): SCAN achieves 40-60% of SSTF's throughput advantage
Deep queue (50+ requests): SCAN approaches SSTF performance while maintaining fairness

The Sweep Efficiency Principle:

SCAN's efficiency improves as the "density" of requests along the sweep path increases. With many requests, the head makes few wasted movements—most cylinder transitions service a pending request.

When SCAN Beats SSTF

Implementation Details

Efficient SCAN implementation requires maintaining sorted request structures for quick access to the next request in the current direction.

efficient_scan.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
"""
Efficient SCAN Implementation
 
Uses two sorted lists for O(log n) insertion and O(1) selection.
Demonstrates production-quality implementation patterns.
"""
 
import bisect
from dataclasses import dataclass, field
from typing import List, Optional, Tuple
from enum import Enum
 
class Direction(Enum):
    INWARD = -1
    OUTWARD = 1
 
@dataclass
class EfficientSCANScheduler:
    """
    Optimized SCAN using two sorted lists.
    
    Maintains:
    - outward_queue: cylinders > head, sorted ascending
    - inward_queue: cylinders <= head, sorted descending (stored ascending, read reversed)
    
    This allows O(1) selection of next request and O(log n) insertion.
    """
    total_cylinders: int
    head_position: int
    direction: Direction = Direction.OUTWARD
    
    # Two sorted queues
    outward_queue: List[int] = field(default_factory=list)  # Sorted ascending
    inward_queue: List[int] = field(default_factory=list)   # Sorted ascending, pop from end
    
    # Metrics
    total_seek: int = 0
    service_order: List[int] = field(default_factory=list)
    
    def submit(self, cylinder: int) -> None:
        """
        O(log n) insertion into appropriate queue.
        """
        if cylinder > self.head_position:
            bisect.insort(self.outward_queue, cylinder)
        elif cylinder < self.head_position:
            bisect.insort(self.inward_queue, cylinder)
        else:
            # At head position - goes in current direction's queue
            if self.direction == Direction.OUTWARD:
                bisect.insort(self.outward_queue, cylinder)
            else:
                bisect.insort(self.inward_queue, cylinder)
    
    def get_next(self) -> Optional[int]:
        """
        O(1) selection of next request.
        Returns None if no requests pending.
        """
        if self.direction == Direction.OUTWARD:
            if self.outward_queue:
                return self.outward_queue[0]  # Smallest cylinder > head
            elif self.inward_queue:
                # Must go to end and reverse
                self._go_to_end()
                self._reverse()
                return self.inward_queue[-1] if self.inward_queue else None
        else:
            if self.inward_queue:
                return self.inward_queue[-1]  # Largest cylinder < head
            elif self.outward_queue:
                # Must go to end and reverse
                self._go_to_end()
                self._reverse()
                return self.outward_queue[0] if self.outward_queue else None
        return None
    
    def _go_to_end(self) -> None:
        """Move head to disk end in current direction."""
        if self.direction == Direction.OUTWARD:
            end = self.total_cylinders - 1
        else:
            end = 0
        seek = abs(end - self.head_position)
        self.total_seek += seek
        self.head_position = end
    
    def _reverse(self) -> None:
        """Reverse direction."""
        self.direction = (
            Direction.INWARD if self.direction == Direction.OUTWARD
            else Direction.OUTWARD
        )
    
    def service_next(self) -> Optional[Tuple[int, int]]:
        """
        Service the next request.
        Returns (cylinder, seek_distance) or None if empty.
        """
        next_cyl = self.get_next()
        if next_cyl is None:
            return None
        
        # Remove from appropriate queue
        if self.direction == Direction.OUTWARD:
            self.outward_queue.pop(0)
        else:
            self.inward_queue.pop()
        
        seek = abs(next_cyl - self.head_position)
        self.total_seek += seek
        self.head_position = next_cyl
        self.service_order.append(next_cyl)
        
        return (next_cyl, seek)
    
    def run_all(self) -> dict:
        """Run until all requests serviced."""
        while self.outward_queue or self.inward_queue:
            self.service_next()
        
        return {
            "service_order": self.service_order,
            "total_seek": self.total_seek,
        }
 
 
# Example usage
if __name__ == "__main__":
    scheduler = EfficientSCANScheduler(
        total_cylinders=200,
        head_position=50,
        direction=Direction.OUTWARD
    )
    
    for cyl in [95, 180, 34, 119, 11, 123, 62, 64]:
        scheduler.submit(cyl)
    
    result = scheduler.run_all()
    print(f"Service order: {result['service_order']}")
    print(f"Total seek: {result['total_seek']} cylinders")

SCAN Implementation Complexity
Operation	Naive	Optimized (Two Lists)	Notes
Insert request	O(1)	O(log n)	Sorted insertion
Select next	O(n)	O(1)	Head of appropriate list
Service request	O(n)	O(1)	Pop from list
Direction reversal	O(1)	O(1)	Flag toggle
Memory	O(n)	O(n)	Same total storage

Real-World Applications

SCAN and its variants are the foundation of disk scheduling in virtually every production operating system.

SCAN in Operating Systems

•Linux: Uses deadline scheduler (SCAN-based) and CFQ (incorporating SCAN principles) as default schedulers for HDDs. The newer mq-deadline scheduler continues this tradition.
•Windows: NTFS uses SCAN-based scheduling with priority support. The Windows Storage Stack includes SCAN variants for different device types.
•FreeBSD: The CAM (Common Access Method) layer implements SCAN-based scheduling for disk devices.
•Database Systems: Oracle, PostgreSQL, and MySQL all benefit from OS-level SCAN scheduling for their disk I/O patterns.
•Storage Controllers: Enterprise RAID controllers implement SCAN variants in hardware/firmware for maximum efficiency.

The SSD Era

Summary: SCAN Disk Scheduling

We have thoroughly examined the SCAN (Elevator) algorithm. Let's consolidate the key insights:

Key Takeaways

•SCAN moves in one direction until reaching disk end, then reverses—like an elevator
•SCAN guarantees bounded wait time — maximum wait is two full disk sweeps
•Performance is 40-60% better than FCFS while maintaining starvation-freedom
•SCAN has positional unfairness — edge cylinders wait longer than center cylinders
•Implementation uses two sorted lists for O(1) selection and O(log n) insertion
•SCAN is the foundation of virtually all production disk schedulers
•SCAN moves to physical disk ends, not just to extreme requests (vs. LOOK)

What's Next:

Page Complete

3 / 5