Operating SystemsDisk Scheduling Algorithms

Disk Scheduling Algorithms

LevelIntermediate

Duration90 mins

TopicDisk Scheduling Algorithms

5 / 5

LOOK and C-LOOK

The Obvious Optimization

In our study of SCAN and C-SCAN, you may have noticed something wasteful: the head always travels to the physical ends of the disk (cylinder 0 and N-1), even when no requests exist there. Why visit cylinder 199 when the highest requested cylinder is 180?

This observation leads to an obvious optimization: instead of traveling to disk ends, only travel as far as the extreme pending requests. The head "looks" ahead to see if more requests exist in the current direction—if not, it reverses (LOOK) or returns (C-LOOK) immediately.

LOOK and C-LOOK are the algorithms actually deployed in production operating systems. When engineers say "SCAN" or "C-SCAN" in practical contexts, they usually mean LOOK or C-LOOK.

What You Will Learn

By the end of this page, you will master LOOK and C-LOOK—understanding their optimization over SCAN/C-SCAN, quantifying the performance improvement, analyzing real-world implementations, and understanding why these are the algorithms that run on virtually every computer with an HDD.

The LOOK Algorithm

LOOK is an optimization of SCAN that avoids traveling to disk ends unnecessarily.

Algorithm Definition:

Move the disk arm in the current direction
Service all pending requests along the path
When reaching the last request in the current direction:
- "Look" to see if there are more requests ahead
- If none exist, reverse direction immediately
Continue servicing requests in the opposite direction

Key Difference from SCAN:

Aspect	SCAN	LOOK
End behavior	Goes to cylinder 0 or N-1	Goes to extreme request
Reversal point	Physical disk end	Last pending request
Wasted seeks	Up to N-1 cylinders	Zero

Why "LOOK"?

The name comes from the head "looking ahead" before deciding to continue. If no requests exist in the current direction, there's no point continuing—the head "looks" and reverses.

look_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
"""
LOOK Disk Scheduling Algorithm
 
Optimized SCAN that reverses at extreme requests rather than disk ends.
This is what most systems actually implement when they say 'SCAN'.
"""
 
from dataclasses import dataclass, field
from typing import List, Tuple, Optional
from enum import Enum
 
class Direction(Enum):
    INWARD = -1   # Toward cylinder 0
    OUTWARD = 1   # Toward cylinder N-1
 
@dataclass
class DiskRequest:
    """Disk I/O request."""
    request_id: int
    cylinder: int
 
@dataclass
class LOOKScheduler:
    """
    LOOK Disk Scheduling Implementation
    
    Like SCAN, but stops at extreme requests rather than disk ends.
    Avoids wasteful seeks beyond the request range.
    """
    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)
    trace: 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(self, request: DiskRequest) -> None:
        self.pending.append(request)
    
    def has_requests_in_direction(self) -> bool:
        """Check if any pending requests exist in current direction."""
        if self.direction == Direction.OUTWARD:
            return any(r.cylinder >= self.head_position for r in self.pending)
        else:
            return any(r.cylinder <= self.head_position for r in self.pending)
    
    def get_next_request(self) -> Optional[DiskRequest]:
        """
        Get the next request in the current direction.
        Returns None if no requests in current direction.
        """
        if self.direction == Direction.OUTWARD:
            candidates = [r for r in self.pending if r.cylinder >= self.head_position]
            if not candidates:
                return None
            return min(candidates, key=lambda r: r.cylinder)
        else:
            candidates = [r for r in self.pending if r.cylinder <= self.head_position]
            if not candidates:
                return None
            return max(candidates, key=lambda r: r.cylinder)
    
    def service_request(self, request: DiskRequest) -> dict:
        """Service a 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 reverse_direction(self) -> None:
        """Reverse arm direction."""
        old_dir = self.direction
        self.direction = (
            Direction.INWARD if self.direction == Direction.OUTWARD
            else Direction.OUTWARD
        )
        self.direction_reversals += 1
        self.trace.append((
            self.head_position,
            self.head_position,
            f"Reverse: {old_dir.name} -> {self.direction.name}"
        ))
    
    def run_scheduling(self) -> dict:
        """Execute LOOK scheduling."""
        results = []
        
        while self.pending:
            # Try to get next request in current direction
            next_request = self.get_next_request()
            
            if next_request:
                result = self.service_request(next_request)
                results.append(result)
            else:
                # No requests in current direction - reverse
                # (This is the key LOOK behavior)
                self.reverse_direction()
        
        return {
            "algorithm": "LOOK",
            "service_order": self.service_order,
            "total_seek_distance": self.total_seek_distance,
            "average_seek": (
                self.total_seek_distance / self.requests_serviced
                if self.requests_serviced > 0 else 0
            ),
            "requests_serviced": self.requests_serviced,
            "direction_reversals": self.direction_reversals,
            "trace": self.trace,
        }
 
 
def demonstrate_look():
    """
    Demonstrate LOOK with standard example.
    
    Disk: 200 cylinders, Head at 50, Direction: OUTWARD
    Requests: 95, 180, 34, 119, 11, 123, 62, 64
    """
    scheduler = LOOKScheduler(
        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(DiskRequest(i, cyl))
    
    results = scheduler.run_scheduling()
    
    print("=== LOOK Disk Scheduling Demo ===")
    print(f"Disk: 200 cylinders, Head at 50, Direction: OUTWARD")
    print(f"Requests: {requests}\n")
    
    print("Execution trace:")
    for from_cyl, to_cyl, action in results['trace']:
        if from_cyl == to_cyl:
            print(f"  [{action}]")
        else:
            print(f"  {from_cyl} -> {to_cyl} [{action}]")
    
    print(f"\nService order: {results['service_order']}")
    print(f"Total seek: {results['total_seek_distance']} cylinders")
    print(f"Direction reversals: {results['direction_reversals']}")
    
    # Comparison
    print("\n=== vs SCAN (goes to disk ends) ===")
    print(f"SCAN total:  337 cylinders")
    print(f"LOOK total:  {results['total_seek_distance']} cylinders")
    savings = 337 - results['total_seek_distance']
    print(f"Savings: {savings} cylinders ({savings/337*100:.1f}%)")
    
    return results
 
 
if __name__ == "__main__":
    demonstrate_look()

Worked Example: LOOK Trace

Let's trace LOOK with our standard example and compare directly with SCAN.

Scenario:

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

LOOK vs SCAN Comparison
Step	SCAN Action	LOOK Action	Difference
1	50 → 62	50 → 62	Same
2	62 → 64	62 → 64	Same
3	64 → 95	64 → 95	Same
4	95 → 119	95 → 119	Same
5	119 → 123	119 → 123	Same
6	123 → 180	123 → 180	Same
7	180 → 199 (disk end)	Reverse at 180	LOOK saves 19 cyl
8	199 → 34	180 → 34	LOOK saves 19 cyl
9	34 → 11	34 → 11	Same
10	(finish)	(finish)	Same

LOOK Performance:

$$\text{Total Seek (LOOK)} = 12 + 2 + 31 + 24 + 4 + 57 + 146 + 23 = 299 \text{ cylinders}$$

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

Savings: $$\text{LOOK Savings} = 337 - 299 = 38 \text{ cylinders} = 11.3%$$

LOOK saved the unnecessary trip from cylinder 180 to 199 and back.

Converting Mermaid diagram...

LOOK Efficiency

LOOK achieves 11% better efficiency than SCAN for this example, purely by avoiding unnecessary travel. The savings increase when request ranges are narrow relative to disk size—common in practice when applications access clustered data.

The C-LOOK Algorithm

C-LOOK optimizes C-SCAN the same way LOOK optimizes SCAN—by only traveling to extreme requests rather than disk ends.

Algorithm Definition:

Move the disk arm toward higher cylinders
Service all pending requests along the path
When reaching the highest pending request:
- Jump to the lowest pending request (not cylinder 0)
- Do NOT service during jump
Resume servicing from the lowest request upward

C-LOOK vs C-SCAN:

Aspect	C-SCAN	C-LOOK
Service limit	Goes to cylinder N-1	Stops at max request
Return target	Cylinder 0	Min pending request
Return distance	Always N-1	Varies with request spread
Wasted seeks	Can be 2×(N-1)	Only (max - min)

The Key Optimization:

C-LOOK's return distance is $(max_request - min_request)$ rather than C-SCAN's $(N-1)$. If requests span only 50% of the disk, C-LOOK's return is ~50% shorter.

clook_scheduler.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
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
"""
C-LOOK Disk Scheduling Algorithm
 
The practical implementation of C-SCAN used in real operating systems.
Returns to lowest pending request rather than cylinder 0.
"""
 
from dataclasses import dataclass, field
from typing import List, Tuple, Optional
 
@dataclass
class DiskRequest:
    """Disk I/O request."""
    request_id: int
    cylinder: int
 
@dataclass
class CLOOKScheduler:
    """
    C-LOOK Disk Scheduling Implementation
    
    Optimized C-SCAN that only travels to extreme pending requests.
    This is what production systems actually use.
    """
    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
    service_seek_distance: int = 0
    return_distance: int = 0
    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]:
        """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]:
        """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.service_seek_distance += seek
        self.requests_serviced += 1
        self.service_order.append(request.cylinder)
        
        return {"cylinder": request.cylinder, "seek": seek}
    
    def jump_to_min(self, min_request: DiskRequest) -> int:
        """
        Jump to the minimum pending request (C-LOOK return).
        Unlike C-SCAN, we don't go to cylinder 0.
        """
        jump_distance = self.head_position - min_request.cylinder
        
        self.trace.append((
            self.head_position,
            min_request.cylinder,
            "Jump to min (no service)"
        ))
        
        self.head_position = min_request.cylinder
        self.total_seek_distance += jump_distance
        self.return_distance += jump_distance
        
        return jump_distance
    
    def run_scheduling(self) -> dict:
        """Execute C-LOOK scheduling."""
        results = []
        
        while self.pending:
            # Service all requests ahead (ascending)
            ahead = self.get_requests_ahead()
            for request in ahead:
                result = self.service_request(request)
                results.append(result)
            
            # If requests remain behind, jump to minimum
            behind = self.get_requests_behind()
            if behind:
                self.jump_to_min(behind[0])
                # Now service remaining (will be picked up as 'ahead')
        
        return {
            "algorithm": "C-LOOK",
            "service_order": self.service_order,
            "total_seek_distance": self.total_seek_distance,
            "service_seek_distance": self.service_seek_distance,
            "return_distance": self.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_clook():
    """
    Demonstrate C-LOOK with standard example.
    """
    scheduler = CLOOKScheduler(
        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-LOOK Disk Scheduling Demo ===")
    print(f"Disk: 200 cylinders, Head at 50")
    print(f"Requests: {requests}\n")
    
    print("Execution trace:")
    for from_cyl, to_cyl, action in results['trace']:
        print(f"  {from_cyl} -> {to_cyl} [{action}]")
    
    print(f"\nService order: {results['service_order']}")
    print(f"Total seek: {results['total_seek_distance']} cylinders")
    print(f"  - Service seeks: {results['service_seek_distance']} cylinders")
    print(f"  - Return jump: {results['return_distance']} cylinders")
    
    # Full comparison
    print("\n=== Complete Algorithm Comparison ===")
    algorithms = [
        ("FCFS", 644),
        ("SSTF", 208),
        ("SCAN", 337),
        ("LOOK", 299),
        ("C-SCAN", 382),
        ("C-LOOK", results['total_seek_distance']),
    ]
    
    for name, seek in algorithms:
        improvement = (1 - seek/644) * 100
        print(f"  {name:8}: {seek:3} cylinders ({improvement:+5.1f}% vs FCFS)")
    
    return results
 
 
def compare_all_algorithms():
    """
    Run all algorithms on the same workload and compare.
    """
    print("\n" + "=" * 60)
    print("COMPREHENSIVE ALGORITHM COMPARISON")
    print("=" * 60)
    print("Workload: 8 requests on 200-cylinder disk, head at 50")
    print("Requests: {95, 180, 34, 119, 11, 123, 62, 64}")
    print("=" * 60 + "\n")
    
    results = {
        "FCFS": {"seek": 644, "order": "95→180→34→119→11→123→62→64"},
        "SSTF": {"seek": 208, "order": "34→11→62→64→95→119→123→180"},
        "SCAN": {"seek": 337, "order": "62→64→95→119→123→180→[end]→34→11"},
        "LOOK": {"seek": 299, "order": "62→64→95→119→123→180→34→11"},
        "C-SCAN": {"seek": 382, "order": "62→64→95→119→123→180→[end→0]→11→34"},
        "C-LOOK": {"seek": 322, "order": "62→64→95→119→123→180→[→11]→34"},
    }
    
    print(f"{'Algorithm':<10} {'Seek':<10} {'vs FCFS':<12} {'Starvation':<12} {'Uniform Wait':<12}")
    print("-" * 60)
    
    for alg in ["FCFS", "SSTF", "SCAN", "LOOK", "C-SCAN", "C-LOOK"]:
        seek = results[alg]["seek"]
        vs_fcfs = f"{(1-seek/644)*100:+.1f}%"
        starve = "Yes" if alg == "SSTF" else "No"
        uniform = "N/A" if alg == "FCFS" else ("No" if alg in ["SCAN", "LOOK"] else "Yes")
        print(f"{alg:<10} {seek:<10} {vs_fcfs:<12} {starve:<12} {uniform:<12}")
    
    print("\n" + "-" * 60)
    print("BEST CHOICE BY CRITERIA:")
    print(f"  Throughput only:  SSTF (208 cyl) - but has starvation risk")
    print(f"  Throughput+Fair:  LOOK (299 cyl) - 54% better than FCFS, no starvation")
    print(f"  Uniform+Fair:     C-LOOK (322 cyl) - 50% better than FCFS, uniform wait")
 
 
if __name__ == "__main__":
    demonstrate_clook()
    compare_all_algorithms()

Worked Example: C-LOOK Trace

Let's trace C-LOOK with our standard example.

Scenario:

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

C-LOOK Execution Trace
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	Jump to min	180 → 11	169	299
8	Service request	11 → 34	23	322

C-LOOK vs C-SCAN Comparison:

Metric	C-SCAN	C-LOOK	Savings
Before return	130 cyl	130 cyl	0
Go to end	19 cyl (180→199)	0 cyl	19 cyl
Return	199 cyl (199→0)	169 cyl (180→11)	30 cyl
After return	34 cyl (0→11→34)	23 cyl (11→34)	11 cyl
Total	382 cyl	322 cyl	60 cyl (15.7%)

C-LOOK saves 60 cylinders by:

Not going to cylinder 199 (saves 19)
Returning to cylinder 11 instead of 0 (saves 30+11)

Final Algorithm Comparison - Standard Example
Algorithm	Total Seek	Avg Seek	vs FCFS	Starvation?	Uniform?
FCFS	644 cyl	80.5 cyl	Baseline	No	Yes
SSTF	208 cyl	26.0 cyl	-67.7%	Yes	No
SCAN	337 cyl	42.1 cyl	-47.7%	No	No
LOOK	299 cyl	37.4 cyl	-53.6%	No	No
C-SCAN	382 cyl	47.8 cyl	-40.7%	No	Yes
C-LOOK	322 cyl	40.3 cyl	-50.0%	No	Yes

C-LOOK: The Production Standard

C-LOOK achieves 50% improvement over FCFS while providing both starvation-freedom AND uniform wait times. It's 15.7% more efficient than C-SCAN while preserving all of C-SCAN's fairness properties. This is why C-LOOK is the de facto standard in production systems.

Performance Analysis

Let's quantify exactly when and how much LOOK/C-LOOK outperform SCAN/C-SCAN.

Request Span Definition:

Let $span = max_request - min_request$ represent the cylinder range covered by pending requests.

LOOK Savings Formula:

$$\text{LOOK savings vs SCAN} = (N - 1 - max_request) + (min_request - 0)$$ $$= N - 1 - span - min_request + min_request = N - 1 - span$$

Simplified: LOOK saves approximately $(N - 1 - span)$ cylinders—the distance from request range to disk ends.

C-LOOK Savings Formula:

$$\text{C-LOOK savings vs C-SCAN} \approx 2 \times (N - 1 - span)$$

Double the savings because C-SCAN goes to both ends while C-LOOK skips both.

Savings by Request Span (200-cylinder disk)
Request Span	% of Disk	LOOK Savings	C-LOOK Savings
199 (full disk)	100%	0 cyl	0 cyl
150 cyl	75%	~49 cyl	~98 cyl
100 cyl	50%	~99 cyl	~198 cyl
50 cyl	25%	~149 cyl	~298 cyl
20 cyl (clustered)	10%	~179 cyl	~358 cyl

Key Insight: The savings are proportional to unused disk range. For clustered workloads (databases, applications with locality), LOOK/C-LOOK can be dramatically more efficient than SCAN/C-SCAN.

Real-World Impact:

Most production workloads exhibit locality:

Database hot tables span ~10-30% of disk
Application working sets are typically clustered
File system metadata is concentrated in specific regions

These patterns mean LOOK/C-LOOK typically save 30-70% of the wasted seeks that SCAN/C-SCAN would incur.

Locality Amplifies Benefits

The more clustered your workload, the more LOOK/C-LOOK outperform SCAN/C-SCAN. This is why production systems universally choose LOOK variants—real workloads almost always have some locality.

Real-World Implementations

LOOK and C-LOOK are the algorithms actually running in production operating systems.

Production Systems Using LOOK/C-LOOK

•Linux Deadline Scheduler: The default HDD I/O scheduler uses C-LOOK as its core algorithm, enhanced with per-request deadlines to prevent starvation of reads during heavy write loads.
•Linux CFQ (Completely Fair Queuing): Historically the default, CFQ used C-LOOK internally for each process's I/O queue, providing both seek optimization and process-level fairness.
•Linux mq-deadline: The multi-queue successor to deadline uses C-LOOK per hardware queue, optimized for modern multi-queue storage devices.
•FreeBSD CAM: The Common Access Method uses a variant of C-LOOK for disk scheduling, with additional heuristics for rotational latency.
•Windows Storage Stack: NTFS and ReFS use LOOK-based algorithms with priority boosting for interactive I/O.
•Enterprise RAID Controllers: LSI, Adaptec, and other controllers implement C-LOOK in firmware with adaptive parameters tuned to drive characteristics.

Linux I/O Scheduler Selection:

# Check current scheduler
cat /sys/block/sda/queue/scheduler

# Options typically: [mq-deadline] kyber bfq none
# 'none' for NVMe SSDs (no scheduling needed)
# 'mq-deadline' for HDDs (C-LOOK based)

Why Not Pure C-LOOK?

Production schedulers add enhancements:

Deadline enforcement: Prevent any request from waiting too long
Read prioritization: Reads often block user processes; prioritize them
Write coalescing: Combine adjacent writes to reduce overhead
NCQ awareness: Coordinate with drive's internal queue

SSD Scheduling

SSDs don't benefit from seek optimization (no mechanical head). Modern kernels use 'none' or 'noop' schedulers for SSDs—essentially FCFS. The SSD's internal controller handles request reordering if beneficial.

Algorithm Selection Guide

After studying all six disk scheduling algorithms, here's a comprehensive selection guide:

Disk Scheduling Algorithm Selection Matrix
Criterion	Best Algorithm	Avoid	Notes
Maximum throughput	SSTF / LOOK	FCFS	SSTF slightly better but starves
No starvation	LOOK / C-LOOK	SSTF	LOOK family has bounded wait
Uniform wait time	C-LOOK	SCAN / LOOK	Edge cylinders wait same as center
Predictable latency	C-LOOK	SSTF	Bounded worst case
Simple implementation	FCFS	SSTF	FCFS is trivial
SSD storage	FCFS/None	Any seek-optimized	No seeks to optimize
Low CPU overhead	FCFS / LOOK	SSTF	SSTF needs min-finding
Real-time systems	C-LOOK + deadlines	Pure SSTF	Need bounded latency

Decision Flowchart:

1. Is storage SSD/NVMe?
   YES → Use FCFS (no scheduling) or 'none'
   NO → Continue

2. Is starvation acceptable?
   YES → Consider SSTF for max throughput
   NO → Continue

3. Is uniform wait time needed?
   YES → Use C-LOOK
   NO → Use LOOK

4. Add deadline enforcement for production use

The Standard Answer: C-LOOK

For general-purpose HDD I/O, C-LOOK with deadline enforcement is the standard choice. It provides 50%+ throughput improvement over FCFS, guarantees bounded wait times, provides uniform wait across positions, and is simple enough for kernel implementation. This is why it's the default in Linux and most other operating systems.

Summary: LOOK and C-LOOK

We have completed our comprehensive study of disk scheduling algorithms. Let's consolidate the key insights for LOOK and C-LOOK:

Key Takeaways

•LOOK optimizes SCAN by only traveling to extreme requests, not disk ends
•C-LOOK optimizes C-SCAN by returning to minimum request, not cylinder 0
•Savings are proportional to unused disk range — clustered workloads benefit most
•LOOK achieves ~54% improvement over FCFS while being starvation-free
•C-LOOK achieves ~50% improvement while providing uniform wait times
•Production systems use C-LOOK with deadline enforcement — not pure SCAN/C-SCAN
•SSDs don't need seek optimization — use FCFS or no scheduler

Module Complete: Disk Scheduling Algorithms

You have now mastered the fundamental disk scheduling algorithms:

FCFS: Simple, fair, but inefficient baseline
SSTF: Optimal throughput but causes starvation
SCAN: Bounded wait time with elevator-style movement
C-SCAN: Uniform wait time via circular treatment
LOOK: Practical SCAN that avoids unnecessary seeks
C-LOOK: Practical C-SCAN used in production systems

This knowledge enables you to understand how operating systems manage disk I/O, evaluate storage system performance, and make informed decisions about storage configuration.

Module Complete

Congratulations! You now possess expert-level understanding of disk scheduling algorithms—from theoretical foundations through production implementations. You can analyze any disk scheduling scenario, calculate performance metrics, and understand the tradeoffs that production systems navigate. This knowledge is fundamental to understanding operating system I/O performance.

5 / 5

Loading learning content...

Operating SystemsDisk Scheduling Algorithms

Disk Scheduling Algorithms

LevelIntermediate

Duration90 mins

TopicDisk Scheduling Algorithms

5 / 5

LOOK and C-LOOK

The Obvious Optimization

LOOK and C-LOOK are the algorithms actually deployed in production operating systems. When engineers say "SCAN" or "C-SCAN" in practical contexts, they usually mean LOOK or C-LOOK.

What You Will Learn

The LOOK Algorithm

LOOK is an optimization of SCAN that avoids traveling to disk ends unnecessarily.

Algorithm Definition:

Move the disk arm in the current direction
Service all pending requests along the path
When reaching the last request in the current direction:
- "Look" to see if there are more requests ahead
- If none exist, reverse direction immediately
Continue servicing requests in the opposite direction

Key Difference from SCAN:

Aspect	SCAN	LOOK
End behavior	Goes to cylinder 0 or N-1	Goes to extreme request
Reversal point	Physical disk end	Last pending request
Wasted seeks	Up to N-1 cylinders	Zero

Why "LOOK"?

The name comes from the head "looking ahead" before deciding to continue. If no requests exist in the current direction, there's no point continuing—the head "looks" and reverses.

look_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
"""
LOOK Disk Scheduling Algorithm
 
Optimized SCAN that reverses at extreme requests rather than disk ends.
This is what most systems actually implement when they say 'SCAN'.
"""
 
from dataclasses import dataclass, field
from typing import List, Tuple, Optional
from enum import Enum
 
class Direction(Enum):
    INWARD = -1   # Toward cylinder 0
    OUTWARD = 1   # Toward cylinder N-1
 
@dataclass
class DiskRequest:
    """Disk I/O request."""
    request_id: int
    cylinder: int
 
@dataclass
class LOOKScheduler:
    """
    LOOK Disk Scheduling Implementation
    
    Like SCAN, but stops at extreme requests rather than disk ends.
    Avoids wasteful seeks beyond the request range.
    """
    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)
    trace: 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(self, request: DiskRequest) -> None:
        self.pending.append(request)
    
    def has_requests_in_direction(self) -> bool:
        """Check if any pending requests exist in current direction."""
        if self.direction == Direction.OUTWARD:
            return any(r.cylinder >= self.head_position for r in self.pending)
        else:
            return any(r.cylinder <= self.head_position for r in self.pending)
    
    def get_next_request(self) -> Optional[DiskRequest]:
        """
        Get the next request in the current direction.
        Returns None if no requests in current direction.
        """
        if self.direction == Direction.OUTWARD:
            candidates = [r for r in self.pending if r.cylinder >= self.head_position]
            if not candidates:
                return None
            return min(candidates, key=lambda r: r.cylinder)
        else:
            candidates = [r for r in self.pending if r.cylinder <= self.head_position]
            if not candidates:
                return None
            return max(candidates, key=lambda r: r.cylinder)
    
    def service_request(self, request: DiskRequest) -> dict:
        """Service a 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 reverse_direction(self) -> None:
        """Reverse arm direction."""
        old_dir = self.direction
        self.direction = (
            Direction.INWARD if self.direction == Direction.OUTWARD
            else Direction.OUTWARD
        )
        self.direction_reversals += 1
        self.trace.append((
            self.head_position,
            self.head_position,
            f"Reverse: {old_dir.name} -> {self.direction.name}"
        ))
    
    def run_scheduling(self) -> dict:
        """Execute LOOK scheduling."""
        results = []
        
        while self.pending:
            # Try to get next request in current direction
            next_request = self.get_next_request()
            
            if next_request:
                result = self.service_request(next_request)
                results.append(result)
            else:
                # No requests in current direction - reverse
                # (This is the key LOOK behavior)
                self.reverse_direction()
        
        return {
            "algorithm": "LOOK",
            "service_order": self.service_order,
            "total_seek_distance": self.total_seek_distance,
            "average_seek": (
                self.total_seek_distance / self.requests_serviced
                if self.requests_serviced > 0 else 0
            ),
            "requests_serviced": self.requests_serviced,
            "direction_reversals": self.direction_reversals,
            "trace": self.trace,
        }
 
 
def demonstrate_look():
    """
    Demonstrate LOOK with standard example.
    
    Disk: 200 cylinders, Head at 50, Direction: OUTWARD
    Requests: 95, 180, 34, 119, 11, 123, 62, 64
    """
    scheduler = LOOKScheduler(
        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(DiskRequest(i, cyl))
    
    results = scheduler.run_scheduling()
    
    print("=== LOOK Disk Scheduling Demo ===")
    print(f"Disk: 200 cylinders, Head at 50, Direction: OUTWARD")
    print(f"Requests: {requests}\n")
    
    print("Execution trace:")
    for from_cyl, to_cyl, action in results['trace']:
        if from_cyl == to_cyl:
            print(f"  [{action}]")
        else:
            print(f"  {from_cyl} -> {to_cyl} [{action}]")
    
    print(f"\nService order: {results['service_order']}")
    print(f"Total seek: {results['total_seek_distance']} cylinders")
    print(f"Direction reversals: {results['direction_reversals']}")
    
    # Comparison
    print("\n=== vs SCAN (goes to disk ends) ===")
    print(f"SCAN total:  337 cylinders")
    print(f"LOOK total:  {results['total_seek_distance']} cylinders")
    savings = 337 - results['total_seek_distance']
    print(f"Savings: {savings} cylinders ({savings/337*100:.1f}%)")
    
    return results
 
 
if __name__ == "__main__":
    demonstrate_look()

Worked Example: LOOK Trace

Let's trace LOOK with our standard example and compare directly with SCAN.

Scenario:

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

LOOK vs SCAN Comparison
Step	SCAN Action	LOOK Action	Difference
1	50 → 62	50 → 62	Same
2	62 → 64	62 → 64	Same
3	64 → 95	64 → 95	Same
4	95 → 119	95 → 119	Same
5	119 → 123	119 → 123	Same
6	123 → 180	123 → 180	Same
7	180 → 199 (disk end)	Reverse at 180	LOOK saves 19 cyl
8	199 → 34	180 → 34	LOOK saves 19 cyl
9	34 → 11	34 → 11	Same
10	(finish)	(finish)	Same

LOOK Performance:

$$\text{Total Seek (LOOK)} = 12 + 2 + 31 + 24 + 4 + 57 + 146 + 23 = 299 \text{ cylinders}$$

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

Savings: $$\text{LOOK Savings} = 337 - 299 = 38 \text{ cylinders} = 11.3%$$

LOOK saved the unnecessary trip from cylinder 180 to 199 and back.

Converting Mermaid diagram...

LOOK Efficiency

The C-LOOK Algorithm

C-LOOK optimizes C-SCAN the same way LOOK optimizes SCAN—by only traveling to extreme requests rather than disk ends.

Algorithm Definition:

Move the disk arm toward higher cylinders
Service all pending requests along the path
When reaching the highest pending request:
- Jump to the lowest pending request (not cylinder 0)
- Do NOT service during jump
Resume servicing from the lowest request upward

C-LOOK vs C-SCAN:

Aspect	C-SCAN	C-LOOK
Service limit	Goes to cylinder N-1	Stops at max request
Return target	Cylinder 0	Min pending request
Return distance	Always N-1	Varies with request spread
Wasted seeks	Can be 2×(N-1)	Only (max - min)

The Key Optimization:

C-LOOK's return distance is $(max_request - min_request)$ rather than C-SCAN's $(N-1)$. If requests span only 50% of the disk, C-LOOK's return is ~50% shorter.

clook_scheduler.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
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
"""
C-LOOK Disk Scheduling Algorithm
 
The practical implementation of C-SCAN used in real operating systems.
Returns to lowest pending request rather than cylinder 0.
"""
 
from dataclasses import dataclass, field
from typing import List, Tuple, Optional
 
@dataclass
class DiskRequest:
    """Disk I/O request."""
    request_id: int
    cylinder: int
 
@dataclass
class CLOOKScheduler:
    """
    C-LOOK Disk Scheduling Implementation
    
    Optimized C-SCAN that only travels to extreme pending requests.
    This is what production systems actually use.
    """
    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
    service_seek_distance: int = 0
    return_distance: int = 0
    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]:
        """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]:
        """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.service_seek_distance += seek
        self.requests_serviced += 1
        self.service_order.append(request.cylinder)
        
        return {"cylinder": request.cylinder, "seek": seek}
    
    def jump_to_min(self, min_request: DiskRequest) -> int:
        """
        Jump to the minimum pending request (C-LOOK return).
        Unlike C-SCAN, we don't go to cylinder 0.
        """
        jump_distance = self.head_position - min_request.cylinder
        
        self.trace.append((
            self.head_position,
            min_request.cylinder,
            "Jump to min (no service)"
        ))
        
        self.head_position = min_request.cylinder
        self.total_seek_distance += jump_distance
        self.return_distance += jump_distance
        
        return jump_distance
    
    def run_scheduling(self) -> dict:
        """Execute C-LOOK scheduling."""
        results = []
        
        while self.pending:
            # Service all requests ahead (ascending)
            ahead = self.get_requests_ahead()
            for request in ahead:
                result = self.service_request(request)
                results.append(result)
            
            # If requests remain behind, jump to minimum
            behind = self.get_requests_behind()
            if behind:
                self.jump_to_min(behind[0])
                # Now service remaining (will be picked up as 'ahead')
        
        return {
            "algorithm": "C-LOOK",
            "service_order": self.service_order,
            "total_seek_distance": self.total_seek_distance,
            "service_seek_distance": self.service_seek_distance,
            "return_distance": self.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_clook():
    """
    Demonstrate C-LOOK with standard example.
    """
    scheduler = CLOOKScheduler(
        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-LOOK Disk Scheduling Demo ===")
    print(f"Disk: 200 cylinders, Head at 50")
    print(f"Requests: {requests}\n")
    
    print("Execution trace:")
    for from_cyl, to_cyl, action in results['trace']:
        print(f"  {from_cyl} -> {to_cyl} [{action}]")
    
    print(f"\nService order: {results['service_order']}")
    print(f"Total seek: {results['total_seek_distance']} cylinders")
    print(f"  - Service seeks: {results['service_seek_distance']} cylinders")
    print(f"  - Return jump: {results['return_distance']} cylinders")
    
    # Full comparison
    print("\n=== Complete Algorithm Comparison ===")
    algorithms = [
        ("FCFS", 644),
        ("SSTF", 208),
        ("SCAN", 337),
        ("LOOK", 299),
        ("C-SCAN", 382),
        ("C-LOOK", results['total_seek_distance']),
    ]
    
    for name, seek in algorithms:
        improvement = (1 - seek/644) * 100
        print(f"  {name:8}: {seek:3} cylinders ({improvement:+5.1f}% vs FCFS)")
    
    return results
 
 
def compare_all_algorithms():
    """
    Run all algorithms on the same workload and compare.
    """
    print("\n" + "=" * 60)
    print("COMPREHENSIVE ALGORITHM COMPARISON")
    print("=" * 60)
    print("Workload: 8 requests on 200-cylinder disk, head at 50")
    print("Requests: {95, 180, 34, 119, 11, 123, 62, 64}")
    print("=" * 60 + "\n")
    
    results = {
        "FCFS": {"seek": 644, "order": "95→180→34→119→11→123→62→64"},
        "SSTF": {"seek": 208, "order": "34→11→62→64→95→119→123→180"},
        "SCAN": {"seek": 337, "order": "62→64→95→119→123→180→[end]→34→11"},
        "LOOK": {"seek": 299, "order": "62→64→95→119→123→180→34→11"},
        "C-SCAN": {"seek": 382, "order": "62→64→95→119→123→180→[end→0]→11→34"},
        "C-LOOK": {"seek": 322, "order": "62→64→95→119→123→180→[→11]→34"},
    }
    
    print(f"{'Algorithm':<10} {'Seek':<10} {'vs FCFS':<12} {'Starvation':<12} {'Uniform Wait':<12}")
    print("-" * 60)
    
    for alg in ["FCFS", "SSTF", "SCAN", "LOOK", "C-SCAN", "C-LOOK"]:
        seek = results[alg]["seek"]
        vs_fcfs = f"{(1-seek/644)*100:+.1f}%"
        starve = "Yes" if alg == "SSTF" else "No"
        uniform = "N/A" if alg == "FCFS" else ("No" if alg in ["SCAN", "LOOK"] else "Yes")
        print(f"{alg:<10} {seek:<10} {vs_fcfs:<12} {starve:<12} {uniform:<12}")
    
    print("\n" + "-" * 60)
    print("BEST CHOICE BY CRITERIA:")
    print(f"  Throughput only:  SSTF (208 cyl) - but has starvation risk")
    print(f"  Throughput+Fair:  LOOK (299 cyl) - 54% better than FCFS, no starvation")
    print(f"  Uniform+Fair:     C-LOOK (322 cyl) - 50% better than FCFS, uniform wait")
 
 
if __name__ == "__main__":
    demonstrate_clook()
    compare_all_algorithms()

Worked Example: C-LOOK Trace

Let's trace C-LOOK with our standard example.

Scenario:

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

C-LOOK Execution Trace
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	Jump to min	180 → 11	169	299
8	Service request	11 → 34	23	322

C-LOOK vs C-SCAN Comparison:

Metric	C-SCAN	C-LOOK	Savings
Before return	130 cyl	130 cyl	0
Go to end	19 cyl (180→199)	0 cyl	19 cyl
Return	199 cyl (199→0)	169 cyl (180→11)	30 cyl
After return	34 cyl (0→11→34)	23 cyl (11→34)	11 cyl
Total	382 cyl	322 cyl	60 cyl (15.7%)

C-LOOK saves 60 cylinders by:

Not going to cylinder 199 (saves 19)
Returning to cylinder 11 instead of 0 (saves 30+11)

Final Algorithm Comparison - Standard Example
Algorithm	Total Seek	Avg Seek	vs FCFS	Starvation?	Uniform?
FCFS	644 cyl	80.5 cyl	Baseline	No	Yes
SSTF	208 cyl	26.0 cyl	-67.7%	Yes	No
SCAN	337 cyl	42.1 cyl	-47.7%	No	No
LOOK	299 cyl	37.4 cyl	-53.6%	No	No
C-SCAN	382 cyl	47.8 cyl	-40.7%	No	Yes
C-LOOK	322 cyl	40.3 cyl	-50.0%	No	Yes

C-LOOK: The Production Standard

Performance Analysis

Let's quantify exactly when and how much LOOK/C-LOOK outperform SCAN/C-SCAN.

Request Span Definition:

Let $span = max_request - min_request$ represent the cylinder range covered by pending requests.

LOOK Savings Formula:

$$\text{LOOK savings vs SCAN} = (N - 1 - max_request) + (min_request - 0)$$ $$= N - 1 - span - min_request + min_request = N - 1 - span$$

Simplified: LOOK saves approximately $(N - 1 - span)$ cylinders—the distance from request range to disk ends.

C-LOOK Savings Formula:

$$\text{C-LOOK savings vs C-SCAN} \approx 2 \times (N - 1 - span)$$

Double the savings because C-SCAN goes to both ends while C-LOOK skips both.

Savings by Request Span (200-cylinder disk)
Request Span	% of Disk	LOOK Savings	C-LOOK Savings
199 (full disk)	100%	0 cyl	0 cyl
150 cyl	75%	~49 cyl	~98 cyl
100 cyl	50%	~99 cyl	~198 cyl
50 cyl	25%	~149 cyl	~298 cyl
20 cyl (clustered)	10%	~179 cyl	~358 cyl

Real-World Impact:

Most production workloads exhibit locality:

Database hot tables span ~10-30% of disk
Application working sets are typically clustered
File system metadata is concentrated in specific regions

These patterns mean LOOK/C-LOOK typically save 30-70% of the wasted seeks that SCAN/C-SCAN would incur.

Locality Amplifies Benefits

The more clustered your workload, the more LOOK/C-LOOK outperform SCAN/C-SCAN. This is why production systems universally choose LOOK variants—real workloads almost always have some locality.

Real-World Implementations

LOOK and C-LOOK are the algorithms actually running in production operating systems.

Production Systems Using LOOK/C-LOOK

•Linux Deadline Scheduler: The default HDD I/O scheduler uses C-LOOK as its core algorithm, enhanced with per-request deadlines to prevent starvation of reads during heavy write loads.
•Linux CFQ (Completely Fair Queuing): Historically the default, CFQ used C-LOOK internally for each process's I/O queue, providing both seek optimization and process-level fairness.
•Linux mq-deadline: The multi-queue successor to deadline uses C-LOOK per hardware queue, optimized for modern multi-queue storage devices.
•FreeBSD CAM: The Common Access Method uses a variant of C-LOOK for disk scheduling, with additional heuristics for rotational latency.
•Windows Storage Stack: NTFS and ReFS use LOOK-based algorithms with priority boosting for interactive I/O.
•Enterprise RAID Controllers: LSI, Adaptec, and other controllers implement C-LOOK in firmware with adaptive parameters tuned to drive characteristics.

Linux I/O Scheduler Selection:

# Check current scheduler
cat /sys/block/sda/queue/scheduler

# Options typically: [mq-deadline] kyber bfq none
# 'none' for NVMe SSDs (no scheduling needed)
# 'mq-deadline' for HDDs (C-LOOK based)

Why Not Pure C-LOOK?

Production schedulers add enhancements:

Deadline enforcement: Prevent any request from waiting too long
Read prioritization: Reads often block user processes; prioritize them
Write coalescing: Combine adjacent writes to reduce overhead
NCQ awareness: Coordinate with drive's internal queue

SSD Scheduling

Algorithm Selection Guide

After studying all six disk scheduling algorithms, here's a comprehensive selection guide:

Disk Scheduling Algorithm Selection Matrix
Criterion	Best Algorithm	Avoid	Notes
Maximum throughput	SSTF / LOOK	FCFS	SSTF slightly better but starves
No starvation	LOOK / C-LOOK	SSTF	LOOK family has bounded wait
Uniform wait time	C-LOOK	SCAN / LOOK	Edge cylinders wait same as center
Predictable latency	C-LOOK	SSTF	Bounded worst case
Simple implementation	FCFS	SSTF	FCFS is trivial
SSD storage	FCFS/None	Any seek-optimized	No seeks to optimize
Low CPU overhead	FCFS / LOOK	SSTF	SSTF needs min-finding
Real-time systems	C-LOOK + deadlines	Pure SSTF	Need bounded latency

Decision Flowchart:

1. Is storage SSD/NVMe?
   YES → Use FCFS (no scheduling) or 'none'
   NO → Continue

2. Is starvation acceptable?
   YES → Consider SSTF for max throughput
   NO → Continue

3. Is uniform wait time needed?
   YES → Use C-LOOK
   NO → Use LOOK

4. Add deadline enforcement for production use

The Standard Answer: C-LOOK

Summary: LOOK and C-LOOK

We have completed our comprehensive study of disk scheduling algorithms. Let's consolidate the key insights for LOOK and C-LOOK:

Key Takeaways

•LOOK optimizes SCAN by only traveling to extreme requests, not disk ends
•C-LOOK optimizes C-SCAN by returning to minimum request, not cylinder 0
•Savings are proportional to unused disk range — clustered workloads benefit most
•LOOK achieves ~54% improvement over FCFS while being starvation-free
•C-LOOK achieves ~50% improvement while providing uniform wait times
•Production systems use C-LOOK with deadline enforcement — not pure SCAN/C-SCAN
•SSDs don't need seek optimization — use FCFS or no scheduler

Module Complete: Disk Scheduling Algorithms

You have now mastered the fundamental disk scheduling algorithms:

FCFS: Simple, fair, but inefficient baseline
SSTF: Optimal throughput but causes starvation
SCAN: Bounded wait time with elevator-style movement
C-SCAN: Uniform wait time via circular treatment
LOOK: Practical SCAN that avoids unnecessary seeks
C-LOOK: Practical C-SCAN used in production systems

This knowledge enables you to understand how operating systems manage disk I/O, evaluate storage system performance, and make informed decisions about storage configuration.

Module Complete

5 / 5