SCAN and C-SCAN Disk Scheduling
When a disk receives multiple read/write requests at the same time, it needs a strategy to decide which one to handle next.
Two of the more sensible approaches to this problem are the SCAN and C-SCAN algorithms, both of which take inspiration from something far more ordinary: an elevator.
SCAN Disk Scheduling
The SCAN algorithm moves the disk head in one direction, picking up all pending requests along the way. Once it hits the absolute physical boundary of the disk, it turns around and does the exact same thing in the opposite direction. This back-and-forth sweeping motion repeats until all requests are handled.
The logic is clean and predictable. Requests are never skipped over as long as they fall in the current direction of travel, preventing the wild starvation issues seen in SSTF.
A Worked Example (SCAN)
Suppose a disk has tracks numbered 0 through 249. The disk head is currently sitting at track 100, moving towards the right. The pending requests are: [55, 210, 75, 180, 30, 220].
| Movement | Calculation | Distance |
|---|---|---|
| 100 → 180 | |100 - 180| | 80 |
| 180 → 210 | |180 - 210| | 30 |
| 210 → 220 | |210 - 220| | 10 |
| 220 → 249 | |220 - 249| (Hits boundary) | 29 |
| 249 → 75 | |249 - 75| (Reverses left) | 174 |
| 75 → 55 | |75 - 55| | 20 |
| 55 → 30 | |55 - 30| | 25 |
Total Head Movement = 80 + 30 + 10 + 29 + 174 + 20 + 25 = 368 tracks.
C-SCAN Disk Scheduling
C-SCAN (Circular SCAN) solves a specific fairness issue that regular SCAN suffers from.
In standard SCAN, requests sitting near the boundary the head just bounced off of have to wait the longest. The head has to travel all the way to the opposite boundary and then sweep all the way back to reach them.
C-SCAN fixes this by NOT reversing direction. When the head reaches the far end (249), it instantly jumps all the way back to the beginning of the disk (0) and continues scanning in the original direction. This makes wait times remarkably consistent.
Same Example with C-SCAN
Initial Position: 100, sweeping right. Requests: [55, 210, 75, 180, 30, 220].
| Movement | Calculation | Distance |
|---|---|---|
| 100 → 180 | |100 - 180| | 80 |
| 180 → 210 | |180 - 210| | 30 |
| 210 → 220 | |210 - 220| | 10 |
| 220 → 249 | |220 - 249| (Hits right boundary) | 29 |
| 249 → 0 | |249 - 0| (Massive reset jump) | 249 |
| 0 → 30 | |0 - 30| (Sweeping right again) | 30 |
| 30 → 55 | |30 - 55| | 25 |
| 55 → 75 | |55 - 75| | 20 |
Total Head Movement = 80 + 30 + 10 + 29 + 249 + 30 + 25 + 20 = 473 tracks.
The total movement is technically higher than SCAN (473 vs 368) entirely because of that massive 249-track reset jump. The benefit is that no track region waits significantly longer than any other.
Comparing SCAN (left) and C-SCAN (right). Notice how C-SCAN executes a massive diagonal reset jump back to 0 to maintain a single direction of travel.
C++ Implementation
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int scan_disk_scheduling(vector<int> requests, int head, string direction, int disk_size) {
sort(requests.begin(), requests.end());
int total_head_movement = 0;
int index = 0;
for (int i = 0; i < (int)requests.size(); i++) {
if (head < requests[i]) {
index = i;
break;
}
index = requests.size();
}
vector<int> left(requests.begin(), requests.begin() + index);
vector<int> right(requests.begin() + index, requests.end());
if (direction == "right") {
for (int r : right) {
total_head_movement += abs(head - r);
head = r;
}
if (head != disk_size - 1) {
total_head_movement += abs((disk_size - 1) - head);
head = disk_size - 1;
}
reverse(left.begin(), left.end());
for (int r : left) {
total_head_movement += abs(head - r);
head = r;
}
} else {
reverse(left.begin(), left.end());
for (int r : left) {
total_head_movement += abs(head - r);
head = r;
}
if (head != 0) {
total_head_movement += head;
head = 0;
}
for (int r : right) {
total_head_movement += abs(head - r);
head = r;
}
}
return total_head_movement;
}
int cscan_disk_scheduling(vector<int> requests, int head, string direction, int disk_size) {
sort(requests.begin(), requests.end());
int total_head_movement = 0;
int index = 0;
for (int i = 0; i < (int)requests.size(); i++) {
if (head < requests[i]) {
index = i;
break;
}
index = requests.size();
}
vector<int> left(requests.begin(), requests.begin() + index);
vector<int> right(requests.begin() + index, requests.end());
if (direction == "right") {
for (int r : right) {
total_head_movement += abs(head - r);
head = r;
}
if (head != disk_size - 1) {
total_head_movement += abs((disk_size - 1) - head);
head = disk_size - 1;
}
// Jump to start
total_head_movement += disk_size - 1;
head = 0;
for (int r : left) {
total_head_movement += abs(head - r);
head = r;
}
} else {
reverse(left.begin(), left.end());
for (int r : left) {
total_head_movement += abs(head - r);
head = r;
}
if (head != 0) {
total_head_movement += head;
head = 0;
}
// Jump to end
total_head_movement += disk_size - 1;
head = disk_size - 1;
reverse(right.begin(), right.end());
for (int r : right) {
total_head_movement += abs(head - r);
head = r;
}
}
return total_head_movement;
}
int main() {
vector<int> requests = {55, 210, 75, 180, 30, 220};
int head = 100;
int disk_size = 250;
string direction = "right";
cout << "Total head movement using SCAN: "
<< scan_disk_scheduling(requests, head, direction, disk_size)
<< " tracks" << endl;
cout << "Total head movement using C-SCAN: "
<< cscan_disk_scheduling(requests, head, direction, disk_size)
<< " tracks" << endl;
return 0;
}Strengths and Weaknesses
SCAN handles requests much more fairly than FCFS and generally keeps total head travel lower, which directly translates to better disk performance.
That said, tracks near the far ends of the disk tend to wait longer than those in the middle, since the head only passes through the edges once per sweep but passes the middle twice.
C-SCAN trades a slightly higher total movement (due to the reset jump) for a perfectly even distribution of wait times. This matters immensely in systems where consistent response time is more important than raw efficiency.
Sort the Concepts
Classify the following behaviors into SCAN vs C-SCAN.