Loading learning content...
SCAN delivers bounded wait times but introduces a subtle unfairness: requests at disk edges wait longer than those at the center. This happens because SCAN sweeps back and forth, spending more time near the edges only once per cycle.
Imagine if we could make the disk behave like a circle rather than a line with two ends. The head would sweep in one direction, and when reaching the end, it would instantly "wrap around" to the beginning, like a circular conveyor belt.
This insight gives us C-SCAN (Circular SCAN)—an elegant enhancement that provides uniform wait time across all cylinder positions while maintaining SCAN's bounded latency guarantees.
By the end of this page, you will master C-SCAN—understanding how treating the disk as circular provides uniformity, analyzing its performance characteristics, comparing it quantitatively with SCAN, and knowing when each is appropriate.
C-SCAN (Circular SCAN) modifies SCAN by only servicing requests in one direction. When the head reaches the end of the disk, it immediately returns to the other end without servicing any requests during the return trip.
Algorithm Definition:
The "circular" nature comes from conceptualizing cylinder 0 as immediately following cylinder N-1:
$$\text{Cylinder layout: } 0 \rightarrow 1 \rightarrow ... \rightarrow N-1 \rightarrow 0 \rightarrow 1 \rightarrow ...$$
Why Return Without Servicing?
This seems wasteful—the head traverses the entire disk without doing useful work! But consider the benefit:
The "wasted" return trip is the price paid for uniformity—and it's often worth it.
The Circular Model:
$$\text{Wait time} = \text{distance around the circle to reach request}$$
Since requests are uniformly distributed around the "circle," expected wait is uniform.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179
"""C-SCAN (Circular SCAN) Disk Scheduling Algorithm Implements circular scanning with return-without-service semantics.Provides uniform wait times across all cylinder positions.""" from dataclasses import dataclass, fieldfrom typing import List, Tuple, Optional @dataclassclass DiskRequest: """Disk I/O request.""" request_id: int cylinder: int @dataclassclass CSCANScheduler: """ C-SCAN Disk Scheduling Implementation Always moves in one direction (toward max cylinder). Returns to cylinder 0 without servicing requests on return. """ initial_head_position: int total_cylinders: int # State head_position: int = field(init=False) pending: List[DiskRequest] = field(default_factory=list) # Metrics total_seek_distance: int = 0 total_return_distance: int = 0 # Non-service seek requests_serviced: int = 0 service_order: List[int] = field(default_factory=list) trace: List[Tuple[int, int, str]] = field(default_factory=list) def __post_init__(self): self.head_position = self.initial_head_position def submit(self, request: DiskRequest) -> None: self.pending.append(request) def get_requests_ahead(self) -> List[DiskRequest]: """Get requests with cylinder >= head, sorted ascending.""" ahead = [r for r in self.pending if r.cylinder >= self.head_position] return sorted(ahead, key=lambda r: r.cylinder) def get_requests_behind(self) -> List[DiskRequest]: """Get requests with cylinder < head, sorted ascending.""" behind = [r for r in self.pending if r.cylinder < self.head_position] return sorted(behind, key=lambda r: r.cylinder) def service_request(self, request: DiskRequest) -> dict: """Service a single request.""" seek = abs(request.cylinder - self.head_position) self.trace.append(( self.head_position, request.cylinder, f"Service {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 {"cylinder": request.cylinder, "seek": seek} def return_to_start(self) -> int: """ Return to cylinder 0 without servicing. This is the 'circular wrap-around'. """ # First, go to end (if not already there) if self.head_position < self.total_cylinders - 1: seek_to_end = (self.total_cylinders - 1) - self.head_position self.trace.append(( self.head_position, self.total_cylinders - 1, "Move to end" )) self.total_seek_distance += seek_to_end self.head_position = self.total_cylinders - 1 # Return to 0 (no service during return) return_distance = self.head_position # Distance from current to 0 self.trace.append(( self.head_position, 0, "Return (no service)" )) self.total_return_distance += return_distance self.total_seek_distance += return_distance self.head_position = 0 return return_distance def run_scheduling(self) -> dict: """Execute C-SCAN scheduling.""" results = [] while self.pending: # Service all requests ahead (ascending order) ahead = self.get_requests_ahead() for request in ahead: result = self.service_request(request) results.append(result) # If requests remain behind, do circular return if self.pending: self.return_to_start() # Now service remaining (which were behind) return { "algorithm": "C-SCAN", "service_order": self.service_order, "total_seek_distance": self.total_seek_distance, "service_seek_distance": self.total_seek_distance - self.total_return_distance, "return_distance": self.total_return_distance, "average_seek": ( self.total_seek_distance / self.requests_serviced if self.requests_serviced > 0 else 0 ), "requests_serviced": self.requests_serviced, "trace": self.trace, } def demonstrate_cscan(): """ Demonstrate C-SCAN with standard example. Disk: 200 cylinders, Head starts at 50 Requests: 95, 180, 34, 119, 11, 123, 62, 64 """ scheduler = CSCANScheduler( initial_head_position=50, total_cylinders=200 ) requests = [95, 180, 34, 119, 11, 123, 62, 64] for i, cyl in enumerate(requests): scheduler.submit(DiskRequest(i, cyl)) results = scheduler.run_scheduling() print("=== C-SCAN Disk Scheduling Demo ===") print(f"Disk: 200 cylinders, Head starts at 50") print(f"Requests: {requests}") print("Execution trace:") for from_cyl, to_cyl, action in results['trace']: print(f" {from_cyl} -> {to_cyl} [{action}]") print(f"Service order: {results['service_order']}") print(f"Total seek distance: {results['total_seek_distance']} cylinders") print(f" - Service seeks: {results['service_seek_distance']} cylinders") print(f" - Return (no service): {results['return_distance']} cylinders") print(f"Average seek: {results['average_seek']:.2f} cylinders/request") # Comparison print("=== Algorithm Comparison ===") print(f"FCFS: 644 cylinders") print(f"SSTF: 208 cylinders") print(f"SCAN: 337 cylinders") print(f"C-SCAN: {results['total_seek_distance']} cylinders") return results if __name__ == "__main__": demonstrate_cscan()Let's trace C-SCAN with our standard example, moving in the OUTWARD direction (toward cylinder 199).
Scenario:
| 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 | Return (no service) | 199 → 0 | 199 | 348 |
| 9 | Service request | 0 → 11 | 11 | 359 |
| 10 | Service request | 11 → 34 | 23 | 382 |
C-SCAN Performance Metrics:
$$\text{Total Seek Distance} = 12 + 2 + 31 + 24 + 4 + 57 + 19 + 199 + 11 + 23 = 382 \text{ cylinders}$$
$$\text{Service Seek Distance} = 382 - 199 = 183 \text{ cylinders}$$
$$\text{Return (Wasted) Distance} = 199 \text{ cylinders}$$
$$\text{Average Seek Distance} = \frac{382}{8} = 47.75 \text{ cylinders}$$
Service Order: 62 → 64 → 95 → 119 → 123 → 180 → 11 → 34
| Algorithm | Total Seek | Avg Seek | vs FCFS | Starvation? | Uniform Wait? |
|---|---|---|---|---|---|
| FCFS | 644 cyl | 80.5 cyl | Baseline | No | Yes (FIFO) |
| SSTF | 208 cyl | 26.0 cyl | -67.7% | Yes | No |
| SCAN | 337 cyl | 42.1 cyl | -47.7% | No | No (edge bias) |
| C-SCAN | 382 cyl | 47.8 cyl | -40.7% | No | Yes |
C-SCAN uses 382 cylinders vs SCAN's 337—about 13% more. This overhead comes from the return trip. However, C-SCAN provides uniform wait times across all positions, which may be more important than raw throughput in many scenarios.
C-SCAN's key advantage is uniform wait time. Let's analyze this mathematically.
SCAN Wait Time (Non-Uniform):
For a request at cylinder $c$ (disk has $N$ cylinders):
$$E[W_{SCAN}(c)] = \begin{cases} \frac{(N-c) + c}{N} \cdot \text{sweep time} & \text{if near edge} \frac{N}{2} \cdot \text{sweep time} & \text{if at center} \end{cases}$$
This formula shows center requests wait ~half the time of edge requests.
C-SCAN Wait Time (Uniform):
For a request at any cylinder $c$:
$$E[W_{CSCAN}(c)] = \frac{N + R}{2} \cdot \text{traverse time}$$
Where $R$ is return time. This is independent of $c$!
Why C-SCAN Achieves Uniformity:
Variance Comparison:
| Metric | SCAN | C-SCAN |
|---|---|---|
| Max wait | 2N | ~N+R |
| Min wait | ~0 (lucky timing) | ~0 (lucky timing) |
| Expected wait | N (varies by position) | (N+R)/2 (uniform) |
| Variance | High (position-dependent) | Low (only timing-dependent) |
C-SCAN trades slightly higher average wait for much lower variance—essential for SLA-sensitive systems.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122
"""Uniformity Analysis: SCAN vs C-SCAN Simulates many requests and measures wait time by cylinder positionto demonstrate C-SCAN's uniform wait characteristic.""" import randomfrom dataclasses import dataclassfrom typing import List, Dictimport statistics def simulate_scan_wait_times( total_cylinders: int, requests_per_position: int = 100, seed: int = 42) -> Dict[int, List[float]]: """ Simulate SCAN and measure wait times by cylinder position. Returns dict mapping cylinder -> list of wait times. """ random.seed(seed) wait_times: Dict[int, List[float]] = {c: [] for c in range(total_cylinders)} # Simplified simulation: measure "distance traveled before service" for _ in range(requests_per_position): # Random head position and direction head = random.randint(0, total_cylinders - 1) direction = random.choice([-1, 1]) # -1 = inward, 1 = outward for cylinder in range(total_cylinders): # Calculate wait distance under SCAN if direction == 1: # Moving outward if cylinder >= head: # Ahead: wait = cylinder - head wait = cylinder - head else: # Behind: wait = (N-1 - head) + (N-1 - cylinder) wait = (total_cylinders - 1 - head) + (total_cylinders - 1 - cylinder) else: # Moving inward if cylinder <= head: wait = head - cylinder else: wait = head + cylinder wait_times[cylinder].append(wait) return wait_times def simulate_cscan_wait_times( total_cylinders: int, requests_per_position: int = 100, seed: int = 42) -> Dict[int, List[float]]: """ Simulate C-SCAN and measure wait times by cylinder position. """ random.seed(seed) wait_times: Dict[int, List[float]] = {c: [] for c in range(total_cylinders)} for _ in range(requests_per_position): head = random.randint(0, total_cylinders - 1) for cylinder in range(total_cylinders): if cylinder >= head: # Ahead: wait = cylinder - head wait = cylinder - head else: # Behind: wait = (N-1 - head) + N-1 + cylinder # (go to end, return to 0, then reach cylinder) wait = (total_cylinders - 1 - head) + (total_cylinders - 1) + cylinder wait_times[cylinder].append(wait) return wait_times def analyze_uniformity(): """Compare wait time uniformity between SCAN and C-SCAN.""" N = 200 scan_waits = simulate_scan_wait_times(N) cscan_waits = simulate_cscan_wait_times(N) # Calculate average wait per cylinder position scan_avg = {c: statistics.mean(waits) for c, waits in scan_waits.items()} cscan_avg = {c: statistics.mean(waits) for c, waits in cscan_waits.items()} print("=== Wait Time Uniformity Analysis ===") print(f"Disk: {N} cylinders, 100 samples per position") print("Sample positions:") print(f"{'Position':<10} {'SCAN Avg Wait':<15} {'C-SCAN Avg Wait':<15}") print("-" * 40) for pos in [0, 25, 50, 75, 100, 125, 150, 175, 199]: print(f"{pos:<10} {scan_avg[pos]:<15.1f} {cscan_avg[pos]:<15.1f}") # Calculate variance across positions scan_position_means = list(scan_avg.values()) cscan_position_means = list(cscan_avg.values()) print(f"Variance of position-average wait times:") print(f" SCAN: {statistics.variance(scan_position_means):.1f}") print(f" C-SCAN: {statistics.variance(cscan_position_means):.1f}") print(f"Standard deviation of wait by position:") print(f" SCAN: {statistics.stdev(scan_position_means):.1f} cylinders") print(f" C-SCAN: {statistics.stdev(cscan_position_means):.1f} cylinders") print(f"Conclusion: C-SCAN provides ~{statistics.variance(scan_position_means)/max(0.1, statistics.variance(cscan_position_means)):.0f}x more uniform wait times") if __name__ == "__main__": analyze_uniformity()The simulation confirms: C-SCAN wait times vary only with arrival timing, not with cylinder position. Edge cylinders experience the same average wait as center cylinders. This uniformity is C-SCAN's defining advantage.
C-SCAN's performance differs from SCAN in important ways.
Total Seek Distance:
For a set of requests, C-SCAN's total seek includes:
$$D_{CSCAN} = D_{service} + D_{end} + D_{return}$$
Comparison with SCAN:
| Workload | SCAN Seek | C-SCAN Seek | Overhead | C-SCAN Advantage |
|---|---|---|---|---|
| All requests ahead | ~D | ~D | ~0% | None |
| Uniform random | ~1.5N | ~N + N | ~33% | Uniformity |
| Half ahead, half behind | ~1.5N | ~N + N | ~33% | Uniformity |
| All requests behind | ~N | ~2N | ~100% | Still uniform |
| Edge-heavy (0 and N-1) | ~2N | ~2N | ~0% | Uniformity |
Throughput Analysis:
C-SCAN's throughput (requests per second) is:
$$\text{Throughput} = \frac{\text{Requests serviced}}{\text{Time for one cycle}}$$
$$= \frac{n}{T_{service} + T_{return}}$$
Since $T_{return}$ is fixed (one full sweep), C-SCAN throughput increases with queue depth:
Choose C-SCAN when fairness matters more than throughput—SLA-bound systems, multi-tenant environments, or when writes are distributed across the disk (SSDs with wear leveling). Choose SCAN when pure throughput is the priority and positional unfairness is acceptable.
Several variants of C-SCAN address specific efficiency concerns:
C-LOOK Preview:
C-LOOK (covered in detail on the next page) is by far the most common variant. The key insight:
This can save up to half the seek distance when requests don't span the full disk.
Example:
Savings: $(199-150) + (20-0) = 69$ cylinders
C-SCAN implementation is straightforward—simpler than SCAN in some ways because there's no direction reversal logic.
| Approach | Selection | Insert | Notes |
|---|---|---|---|
| Sorted array | O(1) | O(n) | Simple; good for static queues |
| Two sorted lists | O(1) | O(log n) | Optimal for dynamic queues |
| Circular buffer | O(1) | O(1) amortized | Best for high-throughput |
| Priority queue | O(log n) | O(log n) | Overkill; no priority needed |
Optimal Data Structure: Single Sorted List
Unlike SCAN which needs two lists (ahead/behind), C-SCAN can use a single sorted list:
This is conceptually a circular sorted array with a cursor.
Handling New Requests:
New requests arriving during a sweep can be:
Most systems use immediate insertion for latency-sensitive workloads.
C-SCAN (and more commonly, C-LOOK) is widely used in production systems where fairness is valued.
While SSDs have reduced the need for seek optimization, C-SCAN principles remain relevant for fairness. Even SSDs benefit from ordered access patterns for wear leveling and garbage collection. C-SCAN's uniform-treatment philosophy applies whenever fair resource sharing matters.
We have thoroughly examined C-SCAN (Circular SCAN). Let's consolidate the key insights:
What's Next:
Both SCAN and C-SCAN travel to the physical ends of the disk—even when no requests exist there. This wastes seek time. In the next page, we'll study LOOK and C-LOOK, which optimize by only traveling to the extreme pending requests rather than disk ends. These are the algorithms actually used in most production systems.
You now understand C-SCAN at an expert level—its circular treatment of disk, uniform wait time guarantee, performance tradeoffs, and appropriate use cases. C-SCAN represents the gold standard for fair disk scheduling when positional uniformity is essential.