C-SCAN (Circular SCAN) is an enhanced version of the SCAN disk scheduling algorithm. In C-SCAN, the disk head moves from one end of the disk to the other, servicing requests along the way. However, when it reaches the end, it immediately returns to the beginning of the disk without servicing any requests on the return trip, and then starts servicing again.
How C-SCAN Works
C-SCAN is designed to provide more uniform wait times compared to the original SCAN algorithm. It treats the disk as a circular list that wraps around from the highest cylinder to the lowest cylinder.
The algorithm follows these steps:
- The disk arm moves in a particular direction (typically towards higher cylinder numbers), servicing all requests in its path
- When it reaches the end of the disk, it immediately jumps to the beginning (cylinder 0) without servicing any requests during this return journey
- It then begins moving in the same direction as before, servicing requests
- This creates a one-way circular scan pattern, ensuring more uniform waiting times
Example Calculation
Let's say we have a disk with 200 cylinders (0-199), and the head is currently at position 50, moving towards higher cylinder numbers. The request queue is:
| Request Sequence | 95 | 180 | 34 | 119 | 11 | 123 | 62 |
|---|
The C-SCAN algorithm will sort these requests based on the current head position and direction of movement:
| Requests Sorted by C-SCAN Algorithm (Initial Position: 50, Direction: Increasing) | ||||||
|---|---|---|---|---|---|---|
| 62 | 95 | 119 | 123 | 180 | 11 | 34 |
The head movements will be:
| Head Movement | |50-62| | |62-95| | |95-119| | |119-123| | |123-180| | |180-199| | |199-0| | |0-11| | |11-34| |
|---|---|---|---|---|---|---|---|---|---|
| Distance | 12 | 33 | 24 | 4 | 57 | 19 | 199 | 11 | 23 |
Total head movement = 12 + 33 + 24 + 4 + 57 + 19 + 199 + 11 + 23 = 382 cylinders
Note: In C-SCAN, the head needs to move to the end of the disk (cylinder 199) and then jump back to the beginning (cylinder 0) before servicing the remaining requests.
Differences Between SCAN and C-SCAN
- In SCAN, the head moves back and forth between both ends of the disk, servicing requests in both directions
- In C-SCAN, the head moves in only one direction (usually increasing), and after reaching the end, it jumps back to the beginning without servicing requests during the jump
- C-SCAN provides more uniform waiting times for cylinders, as every part of the disk is visited at constant intervals
- C-SCAN typically has higher total seek distance but offers better fairness in terms of waiting time
Advantages
- Provides more uniform wait times compared to SCAN
- Reduces the variation in waiting time between requests at different locations
- Avoids the favoritism that SCAN shows to middle cylinders
- Better for systems where uniform response time is crucial
Disadvantages
- Generally higher total seek distance compared to SCAN
- The immediate return to the beginning increases total head movement
- May not be as efficient as SCAN in terms of total throughput in some workloads
- More complex to implement than simpler algorithms like FCFS