Disk Scheduling
1. What is Disk Scheduling?
Disk scheduling is the operating system technique used to decide which disk I/O request should be serviced first when multiple requests are waiting.
This is especially important for HDDs, where the disk head physically moves between tracks.
Simple example:
Pending requests: 98, 183, 37, 122, 14, 65, 67 Current head = 53
The OS must decide:
Which request should be served first? Which one next? Which order minimizes movement?
That decision is called disk scheduling.
2. Why Is Disk Scheduling Needed?
Suppose the disk head is at track 50.
Requests are:
10 20 80 90
If the OS processes them randomly:
50 → 10 → 90 → 20 → 80
The head travels a lot.
Instead, a better order might be:
50 → 80 → 90 → 20 → 10
Less unnecessary movement means:
- lower seek time
- better performance
- better throughput
- shorter waiting time
3. HDD Structure
A simplified HDD:
Disk ┌─────────────────┐ │ Track 0 │ │ Track 1 │ │ Track 2 │ │ Track 3 │ │ ... │ │ Track 199 │ └─────────────────┘ ↑ Disk Head
The head moves between tracks.
For example:
Track 20 ←──────── Head ────────→ Track 150
4. Important Disk Terms
Track
A circular path on an HDD platter.
Sector
A subdivision of a track.
Seek
Movement of the disk head to the required track.
Seek Time
Time required to move the disk head to the desired track.
Rotational Latency
Time waiting for the required sector to rotate under the head.
Transfer Time
Time required to actually transfer the data.
5. Total Disk Access Time
A simplified model is:
Disk Access Time = Seek Time + Rotational Latency + Transfer Time + Controller/queue overhead
For HDDs, seek time can be a major factor.
6. Disk Scheduling Algorithms
The major algorithms are:
Disk Scheduling │ ├── FCFS ├── SSTF ├── SCAN ├── C-SCAN ├── LOOK └── C-LOOK
Let's study each one.
7. FCFS — First Come First Serve
FCFS services requests in the order they arrive.
Example:
Requests: 98, 183, 37, 122, 14, 65, 67 Initial head = 53
FCFS order:
53 → 98 → 183 → 37 → 122 → 14 → 65 → 67
It doesn't try to optimize head movement.
8. FCFS Calculation
Calculate each movement:
53 → 98 = 45 98 → 183 = 85 183 → 37 = 146 37 → 122 = 85 122 → 14 = 108 14 → 65 = 51 65 → 67 = 2
Total:
45 + 85 + 146 + 85 + 108 + 51 + 2 = 522 tracks
Therefore:
Total head movement = 522 tracks
9. Advantages of FCFS
- Very simple
- Easy to implement
- Fair in arrival order
- No starvation caused by scheduling priority
10. Disadvantages of FCFS
- Poor performance
- Large head movement
- High average waiting time
- Does not optimize disk access
Memory trick
FCFS = Come first → Serve first
11. SSTF — Shortest Seek Time First
SSTF selects the request closest to the current head position.
Suppose:
Current = 53 Requests: 98, 183, 37, 122, 14, 65, 67
Distances:
98 → |98 - 53| = 45 183 → 130 37 → 16 122 → 69 14 → 39 65 → 12 67 → 14
Closest:
65
So:
53 → 65
Now current position is 65.
Remaining:
98, 183, 37, 122, 14, 67
Closest is:
67
So:
65 → 67
Then:
67 → 37
and so on.
One possible SSTF sequence is:
53 → 65 → 67 → 37 → 14 → 98 → 122 → 183
12. SSTF Calculation
Movement:
53 → 65 = 12 65 → 67 = 2 67 → 37 = 30 37 → 14 = 23 14 → 98 = 84 98 → 122 = 24 122 → 183 = 61
Total:
12 + 2 + 30 + 23 + 84 + 24 + 61 = 236 tracks
So SSTF is much better than the FCFS example in terms of total head movement.
13. Advantages of SSTF
- Reduces average seek time
- Usually better performance than FCFS
- Simple concept
14. Disadvantages of SSTF
The biggest problem is starvation.
Suppose requests keep arriving close to the current head:
Head = 50 Requests: 51, 52, 53, 54, 55...
A request at:
180
may keep getting ignored.
So:
SSTF can cause starvation.
Memory trick
SSTF = Serve the nearest request
15. SCAN Algorithm
SCAN is also called the Elevator Algorithm.
Why?
Because the disk head behaves somewhat like an elevator:
↑ ↑ ↑ ↓ ↓ ↓
It moves in one direction, servicing requests along the way.
When it reaches the end of the disk, it reverses direction.
16. SCAN Example
Suppose:
Disk = 0–199 Head = 53 Requests: 98, 183, 37, 122, 14, 65, 67
Assume the head is moving toward higher track numbers.
Requests greater than 53:
65, 67, 98, 122, 183
Requests less than 53:
37, 14
SCAN moves:
53 ↓ 65 ↓ 67 ↓ 98 ↓ 122 ↓ 183 ↓ 199 ↓ 37 ↓ 14
The important point is:
SCAN goes all the way to the disk end before reversing.
17. SCAN Diagram
0 199 |----------------------------------------------| 14 37 53 65 67 98 122 183 ↑ Head Direction → 53 → 65 → 67 → 98 → 122 → 183 → 199 Direction ← 199 → 37 → 14
18. Advantages of SCAN
- Better than FCFS
- More predictable than SSTF
- Reduces starvation
- Provides more uniform waiting times
19. Disadvantages of SCAN
- May travel to the disk end unnecessarily
- Requests just behind the head may wait
- More movement than necessary in some cases
Memory trick
SCAN = Go to end → Reverse
20. C-SCAN — Circular SCAN
C-SCAN means Circular SCAN.
Instead of reversing direction after reaching the end, the head returns to the beginning and continues in the same direction.
Example:
0 199 |----------------------------------------------| → → → → → → → → → → → →
Suppose:
Head = 53 Direction = right
It services:
65 → 67 → 98 → 122 → 183
Then reaches:
199
Instead of reversing:
199 → 0
Then continues:
0 → 14 → 37
21. C-SCAN Diagram
0 199 |----------------------------------------------| ↑ ↓ 37 14 183 122 98 ↑ 53 → 65 → 67 | └───────────────
Conceptually:
53 → 65 → 67 → 98 → 122 → 183 → 199 ↓ 0 ↓ 14 → 37
22. Why C-SCAN?
SCAN provides different waiting times depending on where the request is located.
C-SCAN provides a more uniform service pattern because it services requests in one direction.
Memory trick
C-SCAN = SCAN + Circular return
23. LOOK Algorithm
LOOK is similar to SCAN, but it does not go all the way to the physical end of the disk if there are no requests there.
This is the key difference.
Suppose:
Disk = 0–199 Head = 53 Requests: 14, 37, 65, 67, 98, 122, 183
Moving right:
53 → 65 → 67 → 98 → 122 → 183
At 183, there are no more requests in that direction.
LOOK immediately reverses:
183 → 37 → 14
It does not go to 199 first.
24. SCAN vs LOOK
SCAN
53 → ... → 183 → 199 → reverse
LOOK
53 → ... → 183 → reverse
Therefore:
LOOK looks for the last request instead of going to the physical disk end.
Memory trick
SCAN = reaches end
LOOK = looks for last request
25. C-LOOK
C-LOOK is the circular version of LOOK.
It moves in one direction.
When it reaches the highest pending request, it jumps to the lowest pending request and continues in the same direction.
Example:
53 → 65 → 67 → 98 → 122 → 183 ↓ 14 ↓ 37
Notice:
183 → 14
It does not need to travel physically through every track between them as a servicing sweep.
26. C-SCAN vs C-LOOK
C-SCAN
53 → ... → 183 → 199 ↓ 0 ↓ 14
C-LOOK
53 → ... → 183 ↓ 14
Therefore:
C-LOOK does not go to the physical ends unless required.
27. Complete Comparison
| Algorithm | Direction | Reverses? | Goes to disk end? | Starvation |
|---|---|---|---|---|
| FCFS | Arrival order | Not applicable | No | No |
| SSTF | Nearest request | Variable | No | Possible |
| SCAN | Both directions | Yes | Yes | Low |
| C-SCAN | One direction | No | Yes | Low |
| LOOK | Both directions | Yes | No | Low |
| C-LOOK | One direction | No | No | Low |
28. Visual Comparison
FCFS 53 → 98 → 183 → 37 → 122 → 14 → 65 → 67
SSTF 53 → nearest → nearest → nearest...
SCAN 53 → → → → → → 199 ↓ ← ← ←
C-SCAN 53 → → → → → → 199 ↓ 0 → → →
LOOK 53 → → → → → 183 ↓ ← ← ←
C-LOOK 53 → → → → → 183 ↓ 14 → → →
29. Important Numerical Problem
Let's solve one completely.
Given:
Disk range = 0–199 Initial head = 53 Request queue: 98, 183, 37, 122, 14, 65, 67
Assume initial direction is toward higher track numbers.
FCFS
Order:
53 → 98 → 183 → 37 → 122 → 14 → 65 → 67
Total:
|53-98| + |98-183| + |183-37| + |37-122| + |122-14| + |14-65| + |65-67| = 45 + 85 + 146 + 85 + 108 + 51 + 2 = 522 tracks
SSTF
One valid sequence:
53 → 65 → 67 → 37 → 14 → 98 → 122 → 183
Total:
12 + 2 + 30 + 23 + 84 + 24 + 61 = 236 tracks
SCAN
Moving right:
53 → 65 → 67 → 98 → 122 → 183 → 199
Then reverse:
199 → 37 → 14
Total:
(199 - 53) + (199 - 14)
146 + 185 = 331 tracks
LOOK
Moving right:
53 → 65 → 67 → 98 → 122 → 183
Reverse:
183 → 37 → 14
Total:
(183 - 53) + (183 - 14)
130 + 169 = 299 tracks
30. Important Point About SCAN/C-SCAN Calculations
When solving exam problems, always check:
- Disk range
- Initial head position
- Initial direction
- Request queue
- Whether the algorithm reaches the physical end
- Whether the algorithm jumps or physically traverses during circular return
- Whether the question counts the return movement
Different textbooks/questions can describe circular movement slightly differently, so follow the convention specified in the question.
31. Seek Time
Seek time is the time required for the head to move to the desired track.
If:
Head = 50 Request = 120
Head movement:
|120 - 50| = 70 tracks
If average movement is known:
Average seek time ≈ Average head movement × time per track
For example, if:
Average movement = 100 tracks Time per track = 0.1 ms
Then:
100 × 0.1 = 10 ms
32. Rotational Latency
After the head reaches the correct track, the required sector may not be directly under the head.
The platter must rotate.
Seek ↓ Correct track ↓ Wait for sector ↓ Data transfer
This waiting period is rotational latency.
For a disk rotating at RPM:
Time for one revolution = 60 / RPM seconds
Average rotational latency is approximately:
Average rotational latency ≈ Half of one revolution
So:
Average latency ≈ 30 / RPM seconds
or:
Average latency ≈ 30000 / RPM milliseconds
Example for 7200 RPM:
30000 / 7200 ≈ 4.17 ms
33. Total Disk Access Time
Simplified:
Disk Access Time = Seek Time + Rotational Latency + Transfer Time
For example:
Seek time = 6 ms Rotational latency = 4 ms Transfer time = 1 ms
Then:
Total = 6 + 4 + 1 = 11 ms
34. Why Disk Scheduling Is More Important for HDDs
HDD:
Mechanical movement ↓ Head movement costs time ↓ Scheduling can significantly reduce movement
SSD:
No moving head ↓ No traditional seek movement ↓ Classical disk scheduling is less important
However, SSDs still have I/O queues and scheduling mechanisms, just with different performance considerations.
35. Disk Scheduling Goals
The OS tries to:
1. Minimize seek time
Less head movement
2. Minimize waiting time
Requests should not wait unnecessarily.
3. Maximize throughput
More I/O operations per unit time
4. Provide fairness
Requests should get service.
5. Avoid starvation
A request shouldn't wait indefinitely.
36. FCFS vs SSTF vs SCAN
| Feature | FCFS | SSTF | SCAN |
|---|---|---|---|
| Simple | Excellent | Good | Moderate |
| Performance | Low | Good | Good |
| Starvation | No | Possible | Low |
| Fairness | Good arrival fairness | Lower | Good |
| Head movement | High | Lower | Controlled |
| Complexity | Very low | Low | Moderate |
37. Most Important Differences
FCFS
Arrival order
SSTF
Closest request
SCAN
Move → End → Reverse
C-SCAN
Move → End → Jump/return → Continue same direction
LOOK
Move → Last request → Reverse
C-LOOK
Move → Last request → Lowest request → Continue
🧠 Exam Revision
Definition
Disk scheduling is an operating-system technique that determines the order in which pending disk I/O requests are serviced to improve disk performance and reduce access time.
Algorithms
FCFS ↓ First request first SSTF ↓ Shortest seek first SCAN ↓ Go to end + reverse C-SCAN ↓ Go to end + circular return LOOK ↓ Go to last request + reverse C-LOOK ↓ Go to last request + circular jump
Memory trick
F-S-S-C-L-C
Think:
First → Shortest → Sweep → Circular → Look → Circular Look.
Most important formulas
Head Movement = Sum of |Current Position - Next Position|
TAT = CT − AT
That second formula is for CPU scheduling, not disk scheduling—don't mix them up.
For disk scheduling:
Total Head Movement = Σ |Current Track − Next Track|
And:
Disk Access Time ≈ Seek Time + Rotational Latency + Transfer Time