Disk Scheduling Algorithms

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
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257

"""
SSTF (Shortest Seek Time First) Disk Scheduling Algorithm
 
Implements greedy seek optimization with comprehensive metrics tracking.
Demonstrates the performance gains and starvation potential.
"""
 
from dataclasses import dataclass, field
from typing import List, Optional, Tuple, Set
from enum import Enum
import heapq
 
class TieBreakStrategy(Enum):
    """Strategy for breaking ties when multiple requests are equidistant."""
    LOWER_CYLINDER = "lower"       # Choose lower cylinder number
    HIGHER_CYLINDER = "higher"     # Choose higher cylinder number
    MAINTAIN_DIRECTION = "direction"  # Continue current direction
    FCFS = "fcfs"                  # First-come among tied
 
@dataclass
class DiskRequest:
    """Represents a single disk I/O request."""
    request_id: int
    cylinder: int
    arrival_time: float
    process_id: int
    arrival_order: int = 0  # For FCFS tie-breaking
    
    def __hash__(self):
        return hash(self.request_id)
    
    def __eq__(self, other):
        return self.request_id == other.request_id
 
@dataclass
class SSTFScheduler:
    """
    SSTF Disk Scheduling Implementation
    
    Maintains a set of pending requests and always services
    the closest request to the current head position.
    """
    initial_head_position: int
    total_cylinders: int
    tie_break: TieBreakStrategy = TieBreakStrategy.LOWER_CYLINDER
    
    # Internal state
    pending: Set[DiskRequest] = field(default_factory=set)
    head_position: int = field(init=False)
    last_direction: int = field(default=1)  # 1 = outward, -1 = inward
    
    # Metrics
    total_seek_distance: int = 0
    requests_serviced: int = 0
    service_order: List[int] = field(default_factory=list)
    seek_sequence: List[Tuple[int, int, int]] = field(default_factory=list)
    starvation_ages: List[int] = field(default_factory=list)
    
    def __post_init__(self):
        self.head_position = self.initial_head_position
        
    def submit_request(self, request: DiskRequest) -> None:
        """Add a new request to the pending set."""
        self.pending.add(request)
        
    def find_nearest(self) -> Optional[DiskRequest]:
        """
        Find the request closest to current head position.
        Applies tie-breaking strategy when multiple requests equidistant.
        """
        if not self.pending:
            return None
            
        # Group requests by distance
        distance_map: dict[int, List[DiskRequest]] = {}
        for req in self.pending:
            dist = abs(self.head_position - req.cylinder)
            if dist not in distance_map:
                distance_map[dist] = []
            distance_map[dist].append(req)
        
        min_distance = min(distance_map.keys())
        candidates = distance_map[min_distance]
        
        if len(candidates) == 1:
            return candidates[0]
            
        # Apply tie-breaking strategy
        if self.tie_break == TieBreakStrategy.LOWER_CYLINDER:
            return min(candidates, key=lambda r: r.cylinder)
        elif self.tie_break == TieBreakStrategy.HIGHER_CYLINDER:
            return max(candidates, key=lambda r: r.cylinder)
        elif self.tie_break == TieBreakStrategy.MAINTAIN_DIRECTION:
            # Prefer request in direction of last movement
            for req in candidates:
                if (req.cylinder - self.head_position) * self.last_direction > 0:
                    return req
            return candidates[0]  # Fallback
        else:  # FCFS
            return min(candidates, key=lambda r: r.arrival_order)
    
    def service_request(self, request: DiskRequest) -> dict:
        """
        Service a request: move head and update state.
        
        Returns metadata about the service operation.
        """
        old_position = self.head_position
        seek_distance = abs(request.cylinder - old_position)
        
        # Update direction
        if request.cylinder != old_position:
            self.last_direction = 1 if request.cylinder > old_position else -1
        
        # Move head
        self.head_position = request.cylinder
        self.pending.remove(request)
        
        # Track starvation: how many requests were skipped
        positions_before = len([r for r in self.pending 
                               if abs(r.cylinder - old_position) < seek_distance])
        
        # Update metrics
        self.total_seek_distance += seek_distance
        self.requests_serviced += 1
        self.service_order.append(request.cylinder)
        self.seek_sequence.append((old_position, request.cylinder, seek_distance))
        
        return {
            "request_id": request.request_id,
            "cylinder": request.cylinder,
            "seek_distance": seek_distance,
            "from": old_position,
            "to": request.cylinder,
            "pending_after": len(self.pending),
        }
    
    def run_scheduling(self) -> dict:
        """
        Execute SSTF scheduling until all requests serviced.
        """
        results = []
        
        while self.pending:
            nearest = self.find_nearest()
            if nearest:
                result = self.service_request(nearest)
                results.append(result)
        
        return {
            "algorithm": "SSTF",
            "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,
            "seek_sequence": self.seek_sequence,
            "detailed_results": results,
        }
 
 
def demonstrate_sstf():
    """
    Demonstrate SSTF with the same scenario as FCFS for comparison.
    
    Disk configuration:
    - 200 cylinders (0-199)
    - Head starts at cylinder 50
    - Request queue: 95, 180, 34, 119, 11, 123, 62, 64
    """
    scheduler = SSTFScheduler(
        initial_head_position=50,
        total_cylinders=200,
        tie_break=TieBreakStrategy.LOWER_CYLINDER
    )
    
    # Submit requests (same as FCFS example)
    requests = [95, 180, 34, 119, 11, 123, 62, 64]
    for i, cylinder in enumerate(requests):
        scheduler.submit_request(DiskRequest(
            request_id=i,
            cylinder=cylinder,
            arrival_time=0.0,
            process_id=1000 + i,
            arrival_order=i,
        ))
    
    results = scheduler.run_scheduling()
    
    # Display results
    print("=== SSTF Disk Scheduling Demo ===")
    print(f"Initial head position: 50")
    print(f"Request queue: {requests}")
    print(f"
Service Order: 50 -> {' -> '.join(map(str, results['service_order']))}")
    print(f"Total Seek Distance: {results['total_seek_distance']} cylinders")
    print(f"Average Seek Distance: {results['average_seek_distance']:.2f} cylinders")
    
    print("
Seek Sequence:")
    for i, (from_cyl, to_cyl, dist) in enumerate(results['seek_sequence']):
        print(f"  Move {i+1}: {from_cyl} -> {to_cyl} (distance: {dist})")
    
    # Compare with FCFS
    fcfs_total = 644  # From previous example
    print(f"
=== Comparison with FCFS ===")
    print(f"FCFS Total Seek: {fcfs_total} cylinders")
    print(f"SSTF Total Seek: {results['total_seek_distance']} cylinders")
    print(f"Improvement: {(1 - results['total_seek_distance']/fcfs_total)*100:.1f}%")
    
    return results
 
 
def demonstrate_starvation():
    """
    Demonstrate how SSTF can cause starvation.
    
    Scenario: Continuous requests near head, one request at far end.
    """
    print("
=== SSTF Starvation Demonstration ===")
    
    scheduler = SSTFScheduler(
        initial_head_position=100,
        total_cylinders=200
    )
    
    # Request at far end
    scheduler.submit_request(DiskRequest(
        request_id=0, cylinder=199, arrival_time=0, process_id=1000, arrival_order=0
    ))
    
    # Many requests near current position
    for i in range(1, 20):
        scheduler.submit_request(DiskRequest(
            request_id=i,
            cylinder=95 + (i % 10),  # Cylinders 95-104
            arrival_time=float(i),
            process_id=1000 + i,
            arrival_order=i,
        ))
    
    results = scheduler.run_scheduling()
    
    # Find when request 0 (cylinder 199) was serviced
    position_of_far_request = results['service_order'].index(199) + 1
    print(f"Request at cylinder 199 (submitted first) was serviced: #{position_of_far_request}")
    print(f"It waited for {position_of_far_request - 1} other requests to complete!")
    print("This demonstrates SSTF starvation - early requests can wait indefinitely.")
 
 
if __name__ == "__main__":
    demonstrate_sstf()
    demonstrate_starvation()

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

"""
SSTF Starvation Analysis
 
Demonstrates how SSTF can cause unbounded waiting times
for requests at disk extremes under continuous load.
"""
 
import random
from dataclasses import dataclass
from typing import List, Optional
import statistics
 
@dataclass
class StarvationMetrics:
    """Tracks waiting time statistics for starvation analysis."""
    request_id: int
    cylinder: int
    arrival_order: int
    service_order: int
    wait_count: int  # How many requests were serviced before this one
    
def analyze_starvation(
    head_start: int,
    total_cylinders: int,
    hot_zone_center: int,
    hot_zone_width: int,
    cold_requests: List[int],
    hot_request_count: int,
    seed: int = 42
) -> dict:
    """
    Analyze SSTF starvation behavior.
    
    Creates a scenario with:
    - "Cold" requests at specified extreme positions
    - "Hot" requests continuously generated near hot_zone_center
    
    Returns statistics on how long cold requests wait.
    """
    random.seed(seed)
    
    # Initialize pending requests
    pending = []
    request_id = 0
    
    # Add cold requests (at extremes)
    for cyl in cold_requests:
        pending.append({
            "id": request_id,
            "cylinder": cyl,
            "arrival": request_id,
        })
        request_id += 1
    
    cold_count = len(cold_requests)
    
    # Add hot requests (near center)
    for _ in range(hot_request_count):
        cyl = hot_zone_center + random.randint(-hot_zone_width, hot_zone_width)
        cyl = max(0, min(total_cylinders - 1, cyl))
        pending.append({
            "id": request_id,
            "cylinder": cyl,
            "arrival": request_id,
        })
        request_id += 1
    
    # Run SSTF
    head = head_start
    serviced = []
    
    while pending:
        # Find nearest
        nearest_idx = min(
            range(len(pending)),
            key=lambda i: abs(pending[i]["cylinder"] - head)
        )
        req = pending.pop(nearest_idx)
        head = req["cylinder"]
        
        serviced.append(StarvationMetrics(
            request_id=req["id"],
            cylinder=req["cylinder"],
            arrival_order=req["arrival"],
            service_order=len(serviced),
            wait_count=len(serviced) - req["arrival"]
        ))
    
    # Analyze cold request behavior
    cold_metrics = [s for s in serviced if s.request_id < cold_count]
    hot_metrics = [s for s in serviced if s.request_id >= cold_count]
    
    return {
        "cold_requests": {
            "count": len(cold_metrics),
            "avg_wait": statistics.mean(m.wait_count for m in cold_metrics),
            "max_wait": max(m.wait_count for m in cold_metrics),
            "service_positions": [m.service_order for m in cold_metrics],
        },
        "hot_requests": {
            "count": len(hot_metrics),
            "avg_wait": statistics.mean(m.wait_count for m in hot_metrics),
            "max_wait": max(m.wait_count for m in hot_metrics),
        },
        "starvation_ratio": (
            statistics.mean(m.wait_count for m in cold_metrics) /
            statistics.mean(m.wait_count for m in hot_metrics)
            if hot_metrics else float('inf')
        ),
    }
 
 
# Demonstration
if __name__ == "__main__":
    # Scenario: 1000 cylinder disk
    # Hot zone: cylinders 450-550 (center at 500)
    # Cold requests: cylinders 10, 990 (at extremes)
    # 100 hot requests
    
    result = analyze_starvation(
        head_start=500,
        total_cylinders=1000,
        hot_zone_center=500,
        hot_zone_width=50,
        cold_requests=[10, 990],
        hot_request_count=100,
    )
    
    print("=== SSTF Starvation Analysis ===
")
    print("Scenario: Head at 500, hot zone 450-550, cold at 10 and 990
")
    
    print("Cold Requests (at extremes):")
    print(f"  Average wait: {result['cold_requests']['avg_wait']:.1f} requests")
    print(f"  Maximum wait: {result['cold_requests']['max_wait']} requests")
    print(f"  Service positions: {result['cold_requests']['service_positions']}")
    
    print("
Hot Requests (near center):")
    print(f"  Average wait: {result['hot_requests']['avg_wait']:.1f} requests")
    print(f"  Maximum wait: {result['hot_requests']['max_wait']} requests")
    
    print(f"
Starvation Ratio: {result['starvation_ratio']:.1f}x")
    print("(Cold requests wait this many times longer than hot requests)")

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

"""
Aged SSTF Implementation
 
Combines SSTF's seek optimization with aging to prevent starvation.
Requests gradually increase in priority as they wait longer.
"""
 
from dataclasses import dataclass
from typing import Set, Optional
import time
 
@dataclass
class AgedRequest:
    request_id: int
    cylinder: int
    arrival_time: float
    
@dataclass
class AgedSSTFScheduler:
    """
    SSTF with aging to prevent starvation.
    
    Priority = seek_distance - (age_weight * age)
    
    Lower priority = higher chance of selection.
    As age increases, effective "distance" decreases until
    any request will eventually be selected.
    """
    head_position: int
    age_weight: float = 10.0  # Cylinders reduced per second of waiting
    
    pending: Set[AgedRequest] = None
    current_time: float = 0.0
    
    def __post_init__(self):
        if self.pending is None:
            self.pending = set()
    
    def submit(self, request: AgedRequest) -> None:
        self.pending.add(request)
    
    def get_effective_distance(self, request: AgedRequest) -> float:
        """
        Calculate aged priority for a request.
        
        effective_distance = actual_distance - (age_weight * wait_time)
        
        This ensures that even distant requests will eventually
        have negative effective distance and be selected.
        """
        actual_distance = abs(request.cylinder - self.head_position)
        wait_time = self.current_time - request.arrival_time
        age_bonus = self.age_weight * wait_time
        
        return actual_distance - age_bonus
    
    def select_next(self) -> Optional[AgedRequest]:
        """Select request with minimum effective distance."""
        if not self.pending:
            return None
            
        return min(self.pending, key=self.get_effective_distance)
    
    def service(self, request: AgedRequest) -> int:
        """Service a request and return seek distance."""
        seek = abs(request.cylinder - self.head_position)
        self.head_position = request.cylinder
        self.pending.remove(request)
        return seek
    
    def advance_time(self, delta: float) -> None:
        """Advance simulation time (for aging calculation)."""
        self.current_time += delta
 
 
def demonstrate_aged_sstf():
    """Show how aging prevents starvation."""
    scheduler = AgedSSTFScheduler(head_position=100, age_weight=5.0)
    
    # Submit distant request first
    scheduler.submit(AgedRequest(0, 199, arrival_time=0.0))
    
    # Submit close requests
    for i in range(1, 6):
        scheduler.submit(AgedRequest(i, 95 + i, arrival_time=0.1 * i))
    
    print("=== Aged SSTF Demo ===")
    print("Without aging, request at 199 would be served last.")
    print("With age_weight=5.0 cylinders/second:
")
    
    service_order = []
    
    # Simulate with time advancement
    while scheduler.pending:
        next_req = scheduler.select_next()
        if next_req:
            print(f"Time {scheduler.current_time:.1f}s: ", end="")
            print(f"Select cylinder {next_req.cylinder} ", end="")
            print(f"(eff_dist={scheduler.get_effective_distance(next_req):.1f})")
            
            scheduler.service(next_req)
            service_order.append(next_req.cylinder)
            
            # Simulate seek time (0.01s per cylinder simplified)
            scheduler.advance_time(0.1)
    
    print(f"
Service order: {service_order}")
    print("Note: Distant request served earlier than pure SSTF due to aging.")
 
 
if __name__ == "__main__":
    demonstrate_aged_sstf()