C-SCAN Disk Scheduling: One-Way Sweeps
Sweep one way serving requests, jump straight back to the start without serving, and sweep the same way again.
How C-SCAN Disk Scheduling Works
C-SCAN (Circular SCAN) serves requests in one direction only. When it reaches the end of the disk it jumps back to the beginning without serving anything on the return, and starts again. The platter is treated as a circular space rather than a line to be swept back and forth.
- Choose a single service direction conventionally toward higher cylinder numbers — and keep it for every sweep.
- Serve every pending request in that direction in cylinder order as the head passes.
- Continue to the end of the disk once the last request in that direction has been served.
- Jump straight back to cylinder 0 without serving anything on the way this is one long seek, not a service pass.
- Begin the next sweep in the same direction, so every cylinder is approached from the same side every time.
- Service happens in one direction only
- The return to 0 is a single non-serving seek
- Every cylinder is approached from the same side
- The disk is treated as circular rather than linear
Why Give Up the Return Sweep
SCAN's flaw is subtle: cylinders in the middle of the disk get served twice per round trip, once going up and once coming down, while cylinders at the extremes are served once. A request at cylinder 100 waits on average half as long as one at cylinder 199.
C-SCAN removes that asymmetry. Because every sweep runs the same way, every cylinder is visited exactly once per cycle and the expected wait is uniform across the disk. For a system where predictable latency matters more than average latency — a database with a service-level guarantee, say — that uniformity is worth paying for.
The price is visible in the total: 382 cylinders, the second worst of the six and 51 more than SCAN. Most of that is the 199-cylinder return jump, which serves nothing.
- SCAN serves middle cylinders twice per round trip
- C-SCAN gives every cylinder the same expected wait
- 382 cylinders — 51 more than SCAN on this queue
- The uniformity is the point; the total is the price
C-SCAN on the standard request queue
def c_scan(requests, head, disk_size=200):
"""Sweep up, jump to 0, sweep up again. Returns (order, total)."""
above = sorted(c for c in requests if c >= head)
below = sorted(c for c in requests if c < head)
# Both edges are visited: the top to finish the sweep, cylinder 0 to
# restart it. Neither serves a request.
order = above + [disk_size - 1, 0] + below if below else above
total, position = 0, head
for cylinder in order:
total += abs(cylinder - position)
position = cylinder
return order, total
order, total = c_scan([98, 183, 37, 122, 14, 140, 65], 53)
print(order, total)#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
using namespace std;
// Returns total head movement in cylinders; `order` receives the service order.
int cScan(const vector<int>& requests, int head, vector<int>& order, int diskSize = 200) {
int total = 0, position = head;
// Up to the edge, jump to 0, then up again. Neither edge serves a request.
vector<int> above, below;
for (int c : requests) (c >= head ? above : below).push_back(c);
sort(above.begin(), above.end());
sort(below.begin(), below.end());
for (int c : above) order.push_back(c);
if (!below.empty()) {
order.push_back(diskSize - 1);
order.push_back(0);
}
for (int c : below) order.push_back(c);
total = 0;
position = head;
for (int cylinder : order) {
total += abs(cylinder - position);
position = cylinder;
}
return total;
}
int main() {
vector<int> requests = {98, 183, 37, 122, 14, 140, 65}, order;
int total = cScan(requests, 53, order);
for (int c : order) cout << c << " ";
cout << "| " << total << " cylinders" << endl;
return 0;
}import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class CScanDiskScheduling {
// Returns total head movement in cylinders; `order` receives the service order.
static int cScan(int[] requests, int head, List<Integer> order, int diskSize) {
int total = 0, position = head;
// Up to the edge, jump to 0, then up again. Neither edge serves a request.
List<Integer> above = new ArrayList<>(), below = new ArrayList<>();
for (int c : requests) (c >= head ? above : below).add(c);
Collections.sort(above);
Collections.sort(below);
order.addAll(above);
if (!below.isEmpty()) {
order.add(diskSize - 1);
order.add(0);
}
order.addAll(below);
total = 0;
position = head;
for (int cylinder : order) {
total += Math.abs(cylinder - position);
position = cylinder;
}
return total;
}
public static void main(String[] args) {
int[] requests = {98, 183, 37, 122, 14, 140, 65};
List<Integer> order = new ArrayList<>();
int total = cScan(requests, 53, order, 200);
System.out.println(order + " | " + total + " cylinders");
}
}Step through it
Running on requests [98, 183, 37, 122, 14, 140, 65], head at 53
Why the Long Jump Is Cheaper Than It Looks
The 199-cylinder return looks catastrophic when counted as head movement, but on real hardware it is not equivalent to 199 cylinders of ordinary seeking. Seek time is dominated by acceleration and settling, not by distance travelled at speed, so one long seek costs far less than the many short seeks covering the same distance.
This matters for how the comparison should be read. Counting cylinders — the standard exam model — treats all movement as equally expensive, which overstates C-SCAN's disadvantage against SCAN. A model weighting each seek by a fixed startup cost plus a distance term narrows the gap considerably.
C-LOOK applies the same saving as LOOK: rather than returning to cylinder 0, it jumps only to the lowest pending request. On this queue that is 14 rather than 0, which brings the total down from 382 to 322.
- One long seek costs less than many short ones on real drives
- The cylinder-count model overstates the return jump's cost
- C-LOOK jumps to the lowest request instead of to 0
- That change alone saves 60 cylinders here
Where C-SCAN Still Runs Today
C-SCAN's contribution was uniform waiting time, and that idea outlived the hardware assumption it was built on.
The return sweep exists to stop the middle cylinders being served twice as often as the edges. On an SSD there are no cylinders and no edges: the flash translation layer scatters logical blocks across channels, so the positional unfairness C-SCAN corrects does not arise. Linux therefore defaults NVMe to none, and the full-length seek back to cylinder 0 — the price C-SCAN pays for uniformity — would be pure waste on a device where that jump costs nothing anyway.
The goal survives in a different form. Modern schedulers still ask has anyone waited too long?, but they measure it in time rather than position. mq-deadline gives each request an explicit expiry; bfq allocates each process a fair share of bandwidth. Both provide C-SCAN's uniformity guarantee without needing a geometric sweep to deliver it.
- Uniform wait was C-SCAN's goal; the sweep was only the mechanism
- Flash has no positional bias for the return sweep to correct
mq-deadlineenforces fairness with time-based expiry, not geometrybfqdivides bandwidth between processes rather than across cylinders