Operating SystemsOS Design & Interview

Numerical Problems in Operating Systems

LevelAdvanced

Duration180 mins

TopicOS Design & Interview

4 / 5

Disk Scheduling Seek Time Calculations

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.

What You Will Master

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)

Typical Disk Timing Parameters
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 component
c × distance = velocity-limited component

For interview problems, we typically use the simple model, measuring total cylinders moved.

Cylinder vs Track vs Block

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

Converting Mermaid diagram...

FCFS Weakness: The Zigzag Effect

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.

fcfs_disk.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
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)
    }
 
# Example
result = 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!

SSTF vs FCFS Comparison
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.

SSTF Starvation Problem

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.

sstf_disk.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
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)

SCAN Direction Selection

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.

C-SCAN Return Movement

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 Comparison
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.

Complete Algorithm Comparison
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

Real OS Schedulers

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

Time Breakdown by Algorithm
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

Rotational Latency Dominates

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.

Practice Problems with Solutions

Work through these problems to solidify your disk scheduling knowledge.

Problem 1: SCAN Direction Comparison

A disk has 300 cylinders (0-299). Initial head position: 100. Requests: 55, 58, 39, 18, 90, 160, 150, 184. Calculate total head movement for SCAN moving (a) toward 0 and (b) toward 299.

Requests sorted by position:

Below 100: 18, 39, 55, 58, 90
Above 100: 150, 160, 184

(a) SCAN toward 0:

Sequence: 100 → 90 → 58 → 55 → 39 → 18 → 0 → 150 → 160 → 184

Movement: 10 + 32 + 3 + 16 + 21 + 18 + 150 + 10 + 24 = 284 cylinders

(b) SCAN toward 299:

Sequence: 100 → 150 → 160 → 184 → 299 → 90 → 58 → 55 → 39 → 18

Movement: 50 + 10 + 24 + 115 + 209 + 32 + 3 + 16 + 21 = 480 cylinders

Answer: Toward 0 is significantly better (284 vs 480) because most requests are clustered below the starting position.

Problem 2: C-LOOK vs SSTF

Using the same disk (300 cylinders, head at 100, requests: 55, 58, 39, 18, 90, 160, 150, 184), calculate total head movement for (a) C-LOOK moving toward 299 and (b) SSTF. Which is better?

(a) C-LOOK toward 299:

Sequence: 100 → 150 → 160 → 184 → 18 → 39 → 55 → 58 → 90

Movement: 50 + 10 + 24 + 166 + 21 + 16 + 3 + 32 = 322 cylinders

(b) SSTF:

From 100, closest: 90 (dist 10)
From 90, closest: 58 (dist 32)
From 58, closest: 55 (dist 3)
From 55, closest: 39 (dist 16)
From 39, closest: 18 (dist 21)
From 18, closest: 150 (dist 132)
From 150, closest: 160 (dist 10)
From 160, closest: 184 (dist 24)

Sequence: 100 → 90 → 58 → 55 → 39 → 18 → 150 → 160 → 184
Movement: 10 + 32 + 3 + 16 + 21 + 132 + 10 + 24 = 248 cylinders

Answer: SSTF is better (248 vs 322), but C-LOOK provides more predictable service times.

Problem 3: Complete Time Analysis

A disk with 200 cylinders runs at 10,000 RPM with 0.05 ms seek time per cylinder. Head at 50, requests: 20, 45, 78, 120, 175. (a) Calculate total service time for LOOK moving toward 0. (b) What is the effective throughput in KB/s if each request reads 4KB?

(a) LOOK toward 0:

Sequence: 50 → 45 → 20 → 78 → 120 → 175

Movement: 5 + 25 + 58 + 42 + 55 = 185 cylinders

Seek time = 185 × 0.05 = 9.25 ms

Rotational latency:
  10,000 RPM → 60/10000 = 6 ms per revolution
  Average = 3 ms per request
  Total = 5 × 3 = 15 ms

Total service time = 9.25 + 15 = 24.25 ms

(b) Throughput:

Data transferred = 5 requests × 4 KB = 20 KB
Time = 24.25 ms = 0.02425 seconds

Throughput = 20 KB / 0.02425 s = 824.7 KB/s

Alternatively: 5 requests / 0.02425 s = 206 IOPS

Summary: Disk Scheduling Seek Time Calculations

Key Takeaways

•FCFS is fair but inefficient — Processes requests in order, ignoring head position
•SSTF minimizes seek but causes starvation — Always picks closest request, edge requests wait
•SCAN goes to disk edge — Reverses at 0 or max cylinder, predictable service
•LOOK stops at last request — More efficient than SCAN, doesn't waste edge travel
•C-SCAN/C-LOOK provide uniform waits — Service in one direction only, jump to start
•Initial direction affects total movement — Always specified or calculated for optimal path

Algorithm Selection Quick Reference:

Scenario	Best Algorithm
Batch system, fairness needed	FCFS
Throughput critical, no new requests	SSTF
General purpose, predictable	LOOK
Time-critical, uniform latency	C-LOOK

What's Next:

We've covered disk scheduling calculations. Next, we'll examine memory access time calculations, combining TLB and cache effects for complete memory system analysis.

Page Complete

You now have comprehensive knowledge of disk scheduling algorithms and seek time calculations. You can analyze any disk scheduling scenario, compare algorithms, and compute total service time including rotational latency.

4 / 5

Loading learning content...

Operating SystemsOS Design & Interview

Numerical Problems in Operating Systems

LevelAdvanced

Duration180 mins

TopicOS Design & Interview

4 / 5

Disk Scheduling Seek Time Calculations

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

What You Will Master

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)

Typical Disk Timing Parameters
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 component
c × distance = velocity-limited component

For interview problems, we typically use the simple model, measuring total cylinders moved.

Cylinder vs Track vs Block

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

Converting Mermaid diagram...

FCFS Weakness: The Zigzag Effect

fcfs_disk.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
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)
    }
 
# Example
result = 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!

SSTF vs FCFS Comparison
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.

SSTF Starvation Problem

sstf_disk.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
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)

SCAN Direction Selection

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

C-SCAN Return Movement

Algorithm Comparison
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.

Complete Algorithm Comparison
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

Real OS Schedulers

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

Time Breakdown by Algorithm
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

Rotational Latency Dominates

Practice Problems with Solutions

Work through these problems to solidify your disk scheduling knowledge.

Problem 1: SCAN Direction Comparison

A disk has 300 cylinders (0-299). Initial head position: 100. Requests: 55, 58, 39, 18, 90, 160, 150, 184. Calculate total head movement for SCAN moving (a) toward 0 and (b) toward 299.

Requests sorted by position:

Below 100: 18, 39, 55, 58, 90
Above 100: 150, 160, 184

(a) SCAN toward 0:

Sequence: 100 → 90 → 58 → 55 → 39 → 18 → 0 → 150 → 160 → 184

Movement: 10 + 32 + 3 + 16 + 21 + 18 + 150 + 10 + 24 = 284 cylinders

(b) SCAN toward 299:

Sequence: 100 → 150 → 160 → 184 → 299 → 90 → 58 → 55 → 39 → 18

Movement: 50 + 10 + 24 + 115 + 209 + 32 + 3 + 16 + 21 = 480 cylinders

Answer: Toward 0 is significantly better (284 vs 480) because most requests are clustered below the starting position.

Problem 2: C-LOOK vs SSTF

Using the same disk (300 cylinders, head at 100, requests: 55, 58, 39, 18, 90, 160, 150, 184), calculate total head movement for (a) C-LOOK moving toward 299 and (b) SSTF. Which is better?

(a) C-LOOK toward 299:

Sequence: 100 → 150 → 160 → 184 → 18 → 39 → 55 → 58 → 90

Movement: 50 + 10 + 24 + 166 + 21 + 16 + 3 + 32 = 322 cylinders

(b) SSTF:

From 100, closest: 90 (dist 10)
From 90, closest: 58 (dist 32)
From 58, closest: 55 (dist 3)
From 55, closest: 39 (dist 16)
From 39, closest: 18 (dist 21)
From 18, closest: 150 (dist 132)
From 150, closest: 160 (dist 10)
From 160, closest: 184 (dist 24)

Sequence: 100 → 90 → 58 → 55 → 39 → 18 → 150 → 160 → 184
Movement: 10 + 32 + 3 + 16 + 21 + 132 + 10 + 24 = 248 cylinders

Answer: SSTF is better (248 vs 322), but C-LOOK provides more predictable service times.

Problem 3: Complete Time Analysis

(a) LOOK toward 0:

Sequence: 50 → 45 → 20 → 78 → 120 → 175

Movement: 5 + 25 + 58 + 42 + 55 = 185 cylinders

Seek time = 185 × 0.05 = 9.25 ms

Rotational latency:
  10,000 RPM → 60/10000 = 6 ms per revolution
  Average = 3 ms per request
  Total = 5 × 3 = 15 ms

Total service time = 9.25 + 15 = 24.25 ms

(b) Throughput:

Data transferred = 5 requests × 4 KB = 20 KB
Time = 24.25 ms = 0.02425 seconds

Throughput = 20 KB / 0.02425 s = 824.7 KB/s

Alternatively: 5 requests / 0.02425 s = 206 IOPS

Summary: Disk Scheduling Seek Time Calculations

Key Takeaways

•FCFS is fair but inefficient — Processes requests in order, ignoring head position
•SSTF minimizes seek but causes starvation — Always picks closest request, edge requests wait
•SCAN goes to disk edge — Reverses at 0 or max cylinder, predictable service
•LOOK stops at last request — More efficient than SCAN, doesn't waste edge travel
•C-SCAN/C-LOOK provide uniform waits — Service in one direction only, jump to start
•Initial direction affects total movement — Always specified or calculated for optimal path

Algorithm Selection Quick Reference:

Scenario	Best Algorithm
Batch system, fairness needed	FCFS
Throughput critical, no new requests	SSTF
General purpose, predictable	LOOK
Time-critical, uniform latency	C-LOOK

What's Next:

We've covered disk scheduling calculations. Next, we'll examine memory access time calculations, combining TLB and cache effects for complete memory system analysis.

Page Complete

4 / 5

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

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

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

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

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

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