Numerical Problems in Operating Systems
Disk Scheduling Seek Time Calculations
Read aloud is unavailable in this browser.
The Mechanical Reality of Disk I/O
Despite the rise of SSDs, traditional hard disk drives (HDDs) remain prevalent in data centers, cloud storage, and cost-sensitive deployments. Understanding disk scheduling is essential because:
- HDDs are still widely used — Cost per terabyte is 5-10× lower than SSDs
- Seek time dominates performance — Moving the disk head is orders of magnitude slower than reading data
- Algorithms matter enormously — The right scheduling algorithm can improve throughput by 2-10×
- Interview staple — Disk scheduling numerical problems are extremely common
The fundamental insight is that disk access time has three components:
Disk Access Time = Seek Time + Rotational Latency + Transfer Time
Seek time (moving the head between tracks) is typically the dominant factor and is what disk scheduling algorithms optimize. Understanding seek time calculations reveals why algorithm choice is critical.
By the end of this page, you will be able to calculate total seek time, average seek time, and total head movement for any disk scheduling algorithm. You'll understand the trade-offs between FCFS, SSTF, SCAN, C-SCAN, and LOOK variants, and be able to solve any disk scheduling numerical problem.
Disk Geometry and Seek Operations
Before calculating seek times, understand the physical model we're working with.
Disk Physical Structure:
- Platters: Multiple rotating disks stacked vertically
- Tracks: Concentric circles on each platter
- Cylinders: All tracks at the same radial position across platters
- Sectors: Divisions within a track (typically 512 bytes or 4 KB)
- Read/Write Head: One per platter surface, move together as a unit
Key Insight: Since all heads move together, we only need to track the cylinder (radial position) for seek calculations.
Disk Timing Components:
1. Seek Time:
- Time to move heads from current cylinder to target cylinder
- Proportional to distance (cylinders traveled)
- Typical range: 3-15 ms
- Formula varies:
Seek Time = a + b × distance(linear model)
2. Rotational Latency:
- Time for target sector to rotate under head
- Average = 1/2 revolution time
- At 7200 RPM: 1 revolution = 8.33 ms, average latency = 4.17 ms
3. Transfer Time:
- Time to read data once positioned
- Depends on data size and disk speed
- Typically negligible for single sector (< 0.1 ms)
| Parameter | 7200 RPM HDD | 15000 RPM HDD | SSD |
|---|---|---|---|
| Average Seek | 8-9 ms | 3-4 ms | 0 (no seek) |
| Full Stroke Seek | 15-20 ms | 8-10 ms | 0 |
| Rotational Latency (avg) | 4.17 ms | 2.0 ms | 0 |
| Transfer Rate | 100-200 MB/s | 200-300 MB/s | 500-7000 MB/s |
Seek Time Models:
Simple Model (for calculations):
Seek Time = |Current Cylinder - Target Cylinder| × Time per Cylinder
Often simplified to just counting cylinder movements (head movement):
Total Head Movement = Σ |Cylinder[i] - Cylinder[i-1]|
Realistic Model:
Seek Time = a + b × sqrt(distance) + c × distance
Where:
a= startup time (~1 ms)b × sqrt(distance)= acceleration componentc × distance= velocity-limited component
For interview problems, we typically use the simple model, measuring total cylinders moved.
Problems may use 'track', 'cylinder', or 'block' interchangeably when specifying disk addresses. For seek time calculations, they all represent the radial position of the head. Always check if the problem specifies otherwise (e.g., blocks per track).
FCFS (First-Come, First-Served) Disk Scheduling
FCFS is the simplest disk scheduling algorithm: requests are serviced in the order they arrive.
Algorithm:
- Queue requests in arrival order
- Process each request in queue order
- Move head to each cylinder in sequence
Calculation Method:
Total Head Movement = Σ |Cylinder[i] - Cylinder[i-1]|
Starting from the initial head position, sum the absolute differences.
Example:
Given:
- Initial head position: 50
- Request queue: 95, 180, 34, 119, 11, 123, 62, 64
- Total cylinders: 200 (0-199)
Step-by-Step:
| From | To | Movement |
|---|---|---|
| 50 | 95 | 45 |
| 95 | 180 | 85 |
| 180 | 34 | 146 |
| 34 | 119 | 85 |
| 119 | 11 | 108 |
| 11 | 123 | 112 |
| 123 | 62 | 61 |
| 62 | 64 | 2 |
Total Head Movement = 45 + 85 + 146 + 85 + 108 + 112 + 61 + 2 = 644 cylinders
Notice how the head moves erratically between 180, 34, 119, 11—traversing the entire disk multiple times. FCFS can produce extremely high seek distances because it ignores the mechanical reality of head movement.
12345678910111213141516171819202122232425262728293031
def fcfs_disk_scheduling(initial_head: int, requests: list) -> dict: """ Calculate FCFS disk scheduling metrics. Returns total head movement and sequence. """ if not requests: return {'total_movement': 0, 'sequence': [initial_head]} sequence = [initial_head] + requests total_movement = 0 movements = [] for i in range(1, len(sequence)): move = abs(sequence[i] - sequence[i-1]) movements.append(move) total_movement += move return { 'sequence': sequence, 'movements': movements, 'total_movement': total_movement, 'average_seek': total_movement / len(requests) } # Exampleresult = fcfs_disk_scheduling(50, [95, 180, 34, 119, 11, 123, 62, 64])print(f"Sequence: {result['sequence']}")print(f"Movements: {result['movements']}")print(f"Total: {result['total_movement']} cylinders")print(f"Average: {result['average_seek']:.1f} cylinders/request")SSTF (Shortest Seek Time First) Disk Scheduling
SSTF selects the request closest to the current head position, minimizing individual seek distances.
Algorithm:
- From current position, find the closest pending request
- Service that request
- Repeat until all requests processed
This is a greedy algorithm and produces locally optimal decisions.
Example (Same request set):
Given:
- Initial head position: 50
- Request queue: 95, 180, 34, 119, 11, 123, 62, 64
Step-by-Step:
| Current | Pending Requests | Closest | Movement |
|---|---|---|---|
| 50 | 95,180,34,119,11,123,62,64 | 62 (dist=12) | 12 |
| 62 | 95,180,34,119,11,123,64 | 64 (dist=2) | 2 |
| 64 | 95,180,34,119,11,123 | 34 (dist=30) | 30 |
| 34 | 95,180,119,11,123 | 11 (dist=23) | 23 |
| 11 | 95,180,119,123 | 95 (dist=84) | 84 |
| 95 | 180,119,123 | 119 (dist=24) | 24 |
| 119 | 180,123 | 123 (dist=4) | 4 |
| 123 | 180 | 180 (dist=57) | 57 |
Total Head Movement = 12 + 2 + 30 + 23 + 84 + 24 + 4 + 57 = 236 cylinders
Improvement over FCFS: 644 → 236 = 63% reduction!
| Metric | FCFS | SSTF | Improvement |
|---|---|---|---|
| Total Movement | 644 cyl | 236 cyl | 63% less |
| Average Seek | 80.5 cyl | 29.5 cyl | 63% less |
| Max Single Seek | 146 cyl | 84 cyl | 42% less |
| Fairness | Excellent | Poor (starvation risk) |
SSTF Walkthrough Visualization:
Cylinder: 0 11 34 50 62 64 95 119 123 180 199
|----|----|----|----|--|----|----|----|----|----|----|
↑ ↑ ↑ ★ ↑ ↑ ↑ ↑ ↑ ↑
7 4 3 HEAD 1 2 5 6 7 8
Order of service: 62, 64, 34, 11, 95, 119, 123, 180
Notice how SSTF clusters nearby requests together, but this creates a problem: requests at the extremes (like 11 and 180) must wait while the head services the middle region.
If new requests keep arriving near the current head position, requests at the disk edges may wait indefinitely. In our example, if requests 50, 55, 60 kept arriving, request 180 would starve. SSTF is not used in production OS schedulers for this reason.
12345678910111213141516171819202122232425262728293031
def sstf_disk_scheduling(initial_head: int, requests: list) -> dict: """ Calculate SSTF disk scheduling metrics. """ if not requests: return {'total_movement': 0, 'sequence': [initial_head]} pending = requests.copy() sequence = [initial_head] total_movement = 0 current = initial_head while pending: # Find closest request closest = min(pending, key=lambda x: abs(x - current)) move = abs(closest - current) sequence.append(closest) total_movement += move current = closest pending.remove(closest) return { 'sequence': sequence, 'total_movement': total_movement, 'average_seek': total_movement / len(requests) } result = sstf_disk_scheduling(50, [95, 180, 34, 119, 11, 123, 62, 64])print(f"Sequence: {result['sequence']}")print(f"Total: {result['total_movement']} cylinders")SCAN (Elevator) Algorithm
SCAN moves the head in one direction, servicing all requests until reaching the disk edge, then reverses direction. Like an elevator, it doesn't change direction until reaching an endpoint.
Algorithm:
- Move head in current direction (toward 0 or toward max)
- Service all requests encountered
- When reaching disk edge (0 or max cylinder), reverse direction
- Continue until all requests serviced
Key Decision: Direction of initial movement must be specified!
Example: SCAN Moving Toward 0
Given:
- Initial head position: 50
- Request queue: 95, 180, 34, 119, 11, 123, 62, 64
- Initial direction: toward 0
- Total cylinders: 200 (0-199)
Requests sorted by position:
- Below 50: 11, 34
- Above 50: 62, 64, 95, 119, 123, 180
Movement:
- Move toward 0, service: 34, 11
- Reach cylinder 0
- Reverse, service: 62, 64, 95, 119, 123, 180
Sequence: 50 → 34 → 11 → 0 → 62 → 64 → 95 → 119 → 123 → 180
Head Movement Calculation:
| From | To | Movement |
|---|---|---|
| 50 | 34 | 16 |
| 34 | 11 | 23 |
| 11 | 0 | 11 |
| 0 | 62 | 62 |
| 62 | 64 | 2 |
| 64 | 95 | 31 |
| 95 | 119 | 24 |
| 119 | 123 | 4 |
| 123 | 180 | 57 |
Total Head Movement = 16 + 23 + 11 + 62 + 2 + 31 + 24 + 4 + 57 = 230 cylinders
Note: We went to cylinder 0 even though the last request in that direction was at 11. This is standard SCAN behavior—it always goes to the disk edge.
Example: SCAN Moving Toward 199
Same request set, different initial direction:
Movement:
- Move toward 199, service: 62, 64, 95, 119, 123, 180
- Reach cylinder 199
- Reverse, service: 34, 11
Sequence: 50 → 62 → 64 → 95 → 119 → 123 → 180 → 199 → 34 → 11
| From | To | Movement |
|---|---|---|
| 50 | 62 | 12 |
| 62 | 64 | 2 |
| 64 | 95 | 31 |
| 95 | 119 | 24 |
| 119 | 123 | 4 |
| 123 | 180 | 57 |
| 180 | 199 | 19 |
| 199 | 34 | 165 |
| 34 | 11 | 23 |
Total = 12 + 2 + 31 + 24 + 4 + 57 + 19 + 165 + 23 = 337 cylinders
The initial direction matters significantly! (230 vs 337 cylinders)
Problems should specify the initial direction. If not specified, calculate both and note which you chose. In practice, the direction is often toward the larger cluster of requests to maximize early service.
C-SCAN (Circular SCAN) Algorithm
C-SCAN addresses SCAN's unfairness by treating the disk as circular. The head only services requests in one direction, then returns to the start without servicing.
Algorithm:
- Move head in one direction, servicing requests
- When reaching disk edge, jump to the other edge (no servicing during return)
- Continue servicing in the same direction
Key Difference from SCAN: The return movement doesn't service requests, making wait times more uniform.
Example:
Given:
- Initial head position: 50
- Request queue: 95, 180, 34, 119, 11, 123, 62, 64
- Direction: toward 199 (increasing)
- Total cylinders: 200 (0-199)
Movement:
- Service toward 199: 62, 64, 95, 119, 123, 180
- Reach 199, jump to 0 (counting this movement)
- Service from 0: 11, 34
Sequence: 50 → 62 → 64 → 95 → 119 → 123 → 180 → 199 → 0 → 11 → 34
Head Movement Calculation:
| From | To | Movement | Notes |
|---|---|---|---|
| 50 | 62 | 12 | Service |
| 62 | 64 | 2 | Service |
| 64 | 95 | 31 | Service |
| 95 | 119 | 24 | Service |
| 119 | 123 | 4 | Service |
| 123 | 180 | 57 | Service |
| 180 | 199 | 19 | To edge |
| 199 | 0 | 199 | Return (no service) |
| 0 | 11 | 11 | Service |
| 11 | 34 | 23 | Service |
Total Head Movement = 12 + 2 + 31 + 24 + 4 + 57 + 19 + 199 + 11 + 23 = 382 cylinders
Trade-off: C-SCAN has higher total movement (382 vs 337 for SCAN toward 199) but provides more uniform wait times. Requests at cylinder 11 don't have to wait for the head to go all the way down and back up.
Some problem formulations don't count the return movement (199 → 0) in total head movement since no data is transferred. Always check the problem statement. If unclear, count it (more realistic) but note your assumption.
| Algorithm | Total Movement | Max Wait (relative) | Fairness |
|---|---|---|---|
| FCFS | 644 | Unbounded | Fair (FIFO) |
| SSTF | 236 | Unbounded (starvation) | Poor |
| SCAN ↓ | 230 | 2 × disk traversal | Medium |
| SCAN ↑ | 337 | 2 × disk traversal | Medium |
| C-SCAN ↑ | 382 | 1 × disk traversal | Good |
LOOK and C-LOOK Algorithms
LOOK and C-LOOK are practical improvements to SCAN and C-SCAN. Instead of going all the way to the disk edge, they only go as far as the last request in each direction.
LOOK: Like SCAN, but reverses at the last request instead of disk edge. C-LOOK: Like C-SCAN, but jumps from last request to first request instead of edge to edge.
LOOK Example:
Given:
- Initial head position: 50
- Request queue: 95, 180, 34, 119, 11, 123, 62, 64
- Direction: toward 0
Movement:
- Move toward 0, service: 34, 11 (stop at 11, NOT at 0)
- Reverse, service: 62, 64, 95, 119, 123, 180 (stop at 180)
Head Movement:
| From | To | Movement |
|---|---|---|
| 50 | 34 | 16 |
| 34 | 11 | 23 |
| 11 | 62 | 51 |
| 62 | 64 | 2 |
| 64 | 95 | 31 |
| 95 | 119 | 24 |
| 119 | 123 | 4 |
| 123 | 180 | 57 |
Total LOOK = 16 + 23 + 51 + 2 + 31 + 24 + 4 + 57 = 208 cylinders
Improvement over SCAN (230): Saved 22 cylinders by not going to cylinder 0.
C-LOOK Example:
Given:
- Initial head position: 50
- Request queue: 95, 180, 34, 119, 11, 123, 62, 64
- Direction: toward higher cylinders
Movement:
- Service toward end: 62, 64, 95, 119, 123, 180
- Jump to lowest request (11), NOT to 0
- Service: 11, 34
Head Movement:
| From | To | Movement | Notes |
|---|---|---|---|
| 50 | 62 | 12 | |
| 62 | 64 | 2 | |
| 64 | 95 | 31 | |
| 95 | 119 | 24 | |
| 119 | 123 | 4 | |
| 123 | 180 | 57 | Last in direction |
| 180 | 11 | 169 | Jump to first request |
| 11 | 34 | 23 |
Total C-LOOK = 12 + 2 + 31 + 24 + 4 + 57 + 169 + 23 = 322 cylinders
Improvement over C-SCAN (382): Saved 60 cylinders by jumping request-to-request instead of edge-to-edge.
| Algorithm | Total Movement | vs FCFS | Notes |
|---|---|---|---|
| FCFS | 644 | baseline | Fair but inefficient |
| SSTF | 236 | -63% | Best movement, starvation risk |
| SCAN ↓ | 230 | -64% | Predictable, goes to edge |
| LOOK ↓ | 208 | -68% | Practical SCAN, no wasted edge travel |
| C-SCAN ↑ | 382 | -41% | Uniform wait, goes to edge |
| C-LOOK ↑ | 322 | -50% | Practical C-SCAN, request-to-request |
Modern Linux uses more sophisticated schedulers (CFQ, deadline, BFQ) that combine ideas from these algorithms with priority, batching, and fairness guarantees. However, understanding these fundamentals is essential for both interviews and appreciating scheduler design.
Converting Head Movement to Seek Time
So far we've calculated head movement in cylinders. Let's convert to actual seek time.
Simple Linear Model:
Seek Time per request = Head Movement × Time per Cylinder
Example:
- Total head movement: 208 cylinders (LOOK)
- Seek time per cylinder: 0.1 ms
- Number of requests: 8
Total Seek Time = 208 × 0.1 = 20.8 ms
Average Seek Time = 20.8 / 8 = 2.6 ms per request
Including All Components:
Total Service Time = Total Seek Time + Total Rotational Latency + Total Transfer Time
For n requests:
- Seek time: calculated above
- Rotational latency: n × average_rotational_latency
- Transfer time: n × time_per_sector (often negligible)
Comprehensive Example:
Given:
- LOOK algorithm result: 208 cylinders total movement
- 8 requests, each for 1 sector
- Disk: 7200 RPM, 0.1 ms per cylinder seek
- Sector transfer: 0.01 ms
Calculations:
Rotational latency per request:
RPM = 7200
Revolution time = 60/7200 = 8.33 ms
Average rotational latency = 8.33/2 = 4.17 ms
Total seek time = 208 × 0.1 = 20.8 ms
Total rotational latency = 8 × 4.17 = 33.36 ms
Total transfer time = 8 × 0.01 = 0.08 ms
Total service time = 20.8 + 33.36 + 0.08 = 54.24 ms
Average service time per request = 54.24 / 8 = 6.78 ms
Throughput = 8 requests / 54.24 ms = 147.5 requests/second
| Algorithm | Seek (ms) | Rotational (ms) | Total (ms) | Throughput (req/s) |
|---|---|---|---|---|
| FCFS | 64.4 | 33.36 | 97.76 | 82 |
| SSTF | 23.6 | 33.36 | 56.96 | 140 |
| LOOK ↓ | 20.8 | 33.36 | 54.16 | 148 |
| C-LOOK ↑ | 32.2 | 33.36 | 65.56 | 122 |
Notice that rotational latency (33.36 ms) often exceeds total seek time for efficient algorithms. This is why modern optimizations focus on rotational position scheduling (RPS) and native command queuing (NCQ) to reduce rotational delays.
KEEP LEARNING
Keep learning for free.
Read the complete lesson, save your notes and pick up where you left off with a free account. No card needed.