1. Why SCAN Was Not Enough
SCAN solved one of the biggest problems of SSTF: starvation.
Every request eventually gets serviced because the disk head continuously sweeps across the disk.
However, SCAN still suffers from a subtle fairness issue.
The Hidden Problem in SCAN
Consider a disk with tracks numbered:
0 ---------------------------- 199
Suppose requests arrive near:
Middle Tracks:
90, 100, 110
and near:
End Tracks:
5, 190
What Happens in SCAN?
The head moves:
Left → Right → Left → Right
continuously.
As a result:
Middle tracks are crossed twice
during every complete sweep.
Example:
0 -------------------- 100 -------------------- 199
↑
Middle Region
The head visits this region:
Once while moving right
Again while moving left
Consequence
Requests near the middle receive service more frequently.
Requests near the ends may wait longer.
Key Problem
SCAN introduces a bias
towards middle tracks.
What OS Designers Wanted
A scheduling algorithm that:
Maintains fairness
Eliminates starvation
Provides uniform waiting time
Treats all tracks equally
This led to C-SCAN.
Key Insight
C-SCAN improves fairness by making the head move in only one servicing direction.
2. What is C-SCAN?
C-SCAN (Circular SCAN) is a disk scheduling algorithm in which the head services requests while moving in one direction only. Upon reaching the end of the disk, it immediately returns to the beginning without servicing requests during the return trip.
Definition
The disk head performs a circular sweep across the disk.
Core Principle
Move Right
↓
Service Requests
↓
Reach End
↓
Jump to Beginning
↓
Continue Moving Right
Why "Circular" SCAN?
Because the disk is logically treated as:
0 → 1 → 2 → ... → 199
↑ ↓
└─────────────────┘
The end is conceptually connected back to the beginning.
Key Insight
Requests are serviced in only one direction, creating more uniform waiting times.
3. How C-SCAN Works Internally
Unlike SCAN, which services requests in both directions:
→ Service
← Service
C-SCAN does:
→ Service
Jump
→ Service
Servicing Direction
Only one direction is considered active.
Return Path
The return path is ignored for servicing.
Key Insight
The return movement exists physically but is not used for processing requests.
4. Numerical Example
Given
Initial Head Position:
53
Direction:
Right
Request Queue:
98, 183, 37, 122, 14, 124, 65, 67
Disk Range:
0 – 199
Step 1: Split Requests
Requests to the right of 53:
65, 67, 98, 122, 124, 183
Requests to the left of 53:
37, 14
Step 2: Sort Requests
Since direction is right:
Right Side (Ascending):
65 → 67 → 98 → 122 → 124 → 183
Left Side (Ascending after jump):
14 → 37
Why Ascending?
Because after returning to 0, the head again moves right.
Key Insight
All requests are serviced in the same direction.
5. Service Order
Starting at 53:
53
↓
65
↓
67
↓
98
↓
122
↓
124
↓
183
↓
199
↓
0
↓
14
↓
37
Final Sequence
53 → 65 → 67 → 98 → 122 → 124 → 183 → 199 → 0 → 14 → 37
Important Difference from SCAN
SCAN:
53 → ... → 199 → 37 → 14
C-SCAN:
53 → ... → 199
Jump
0 → 14 → 37
Key Insight
The reverse sweep is skipped entirely.
6. Head Movement Calculation
Step-by-Step
53 → 65 = 12
65 → 67 = 2
67 → 98 = 31
98 → 122 = 24
122 → 124 = 2
124 → 183 = 59
183 → 199 = 16
199 → 0 = 199
0 → 14 = 14
14 → 37 = 23
Total Head Movement
12 + 2 + 31 + 24 + 2 + 59 + 16 + 199 + 14 + 23
= 382 Cylinders
Final Answer
Total Head Movement = 382 Cylinders
7. Visualizing C-SCAN
0 --------------------------------------------------- 199
14 37 53 65 67 98 122 124 183
Head
Move Right →
53 → 65 → 67 → 98 → 122 → 124 → 183 → 199
Jump
199 → 0
Move Right →
0 → 14 → 37
Key Observation
The head never services requests while moving back.
8. Why C-SCAN Exists
The primary goal is not better seek time.
The primary goal is:
Uniform Waiting Time
In SCAN
Middle tracks:
Serviced frequently
End tracks:
Wait longer
In C-SCAN
Every request waits for at most:
One complete circular sweep
Result
More predictable response times.
Key Insight
C-SCAN sacrifices some efficiency to achieve fairness.
9. Understanding Waiting Time
Consider two requests:
Track 20
Track 100
In SCAN
Track 100 may be encountered twice during one cycle.
Track 20 may wait much longer.
In C-SCAN
Both requests are serviced during the next circular sweep.
Waiting times become more uniform.
Key Insight
C-SCAN removes positional bias.
10. Performance Analysis
10.1 Seek Time
Usually slightly higher than SCAN.
Reason:
Extra jump
199 → 0
10.2 Throughput
Still very good.
Movement remains structured.
10.3 Fairness
Higher than SCAN.
10.4 Response Time
More predictable.
Key Insight
C-SCAN trades some performance for consistency.
11. Starvation Analysis
Does C-SCAN Suffer from Starvation?
No
Why?
The head continuously moves through all cylinders.
Every request eventually lies in its path.
Result
Guaranteed Service
for all requests.
Key Insight
Like SCAN, C-SCAN completely eliminates starvation.
12. Advantages of C-SCAN
12.1 Uniform Waiting Time
All tracks are treated similarly.
12.2 No Starvation
Every request eventually gets serviced.
12.3 Better Fairness
No middle-track bias.
12.4 Predictable Performance
Response times are more consistent.
12.5 Suitable for Heavy Workloads
Works well when many requests arrive continuously.
Key Insight
C-SCAN is often preferred in systems where fairness matters more than absolute seek-time minimization.
13. Disadvantages of C-SCAN
13.1 Higher Head Movement
The jump from:
199 → 0
adds extra movement.
13.2 Slightly Lower Efficiency
Compared to SCAN.
13.3 Longer Travel Distance
Some requests may require waiting for a full circular sweep.
Key Insight
C-SCAN pays a performance cost to achieve fairness.
14. Real-World Analogy
Imagine a circular bus route.
Bus Behavior
Start
↓
Visit Stops
↓
Reach End
↓
Return Empty
↓
Start Again
Passengers are picked up only during the forward trip.
Disk Head Behavior
Move Right
↓
Serve Requests
↓
Reach End
↓
Jump to Start
↓
Serve Requests Again
Key Insight
C-SCAN behaves like a one-way circular transportation system.
15. SCAN vs C-SCAN
| Feature | SCAN | C-SCAN |
|---|---|---|
| Service Direction | Both Directions | One Direction Only |
| Return Path | Services Requests | Skips Requests |
| Fairness | Good | Better |
| Middle Track Bias | Yes | No |
| Starvation | No | No |
| Seek Time | Lower | Slightly Higher |
| Waiting Time | Variable | More Uniform |
| Predictability | Good | Excellent |
16. SCAN vs C-SCAN vs SSTF
| Feature | SSTF | SCAN | C-SCAN |
|---|---|---|---|
| Strategy | Nearest Request | Bidirectional Sweep | Circular Sweep |
| Seek Time | Lowest | Low | Moderate |
| Fairness | Poor | Good | Excellent |
| Starvation | Possible | No | No |
| Predictability | Low | Good | Very Good |
| Complexity | Moderate | Moderate | Moderate |
17. C-SCAN at a Glance
| Property | C-SCAN |
|---|---|
| Full Form | Circular SCAN |
| Direction | One-Way |
| Disk Model | Circular Queue |
| Fairness | High |
| Starvation | No |
| Seek Time | Slightly Higher than SCAN |
| Waiting Time | Uniform |
| Predictability | High |
| Practical Usage | Multi-user Systems |
Final Insight
C-SCAN is an enhancement of SCAN designed to provide more uniform waiting times across the entire disk. Instead of servicing requests during both forward and backward movement, the head services requests in only one direction and performs a circular return to the beginning. This eliminates the middle-track bias of SCAN, ensures fairness, prevents starvation, and provides highly predictable performance, making it particularly suitable for heavily loaded systems where consistency is important.