4.2.38 · D5Operating Systems
Question bank — Disk scheduling — FCFS, SCAN, C-SCAN, LOOK
Setup and notation (read this first)
True or false — justify
Each claim is either true or false. State which and why in one sentence.
FCFS never moves the head more than SCAN for the same queue.
False — FCFS follows arrival order and can zig-zag (e.g. 53→183→14), so it usually moves more than SCAN; it is only tied in trivial already-sorted queues.
SCAN and LOOK always service the requests in the same order.
True — both sweep one direction then reverse, so the request order is identical; they differ only in whether the head also visits the empty physical boundary.
C-SCAN always has a strictly larger total head movement than SCAN for the same queue and direction.
True as an inequality but with ties possible — C-SCAN adds the empty full-width return jump on top of a full sweep to the boundary, so its total is always ≥ SCAN's and never smaller; they can only tie in degenerate cases, never favour C-SCAN.
Choosing a smaller total head movement always gives a better real-world disk.
False — it ignores fairness (a far-edge request can starve under SSTF/SCAN) and ignores rotational latency, so "least travel" is not the whole story.
In C-SCAN the return jump (e.g. 199→0) services no requests.
True — that is the definition; C-SCAN only serves in one direction and resets empty to keep every cylinder's wait time uniform.
LOOK can starve a request the way FCFS cannot.
False — FCFS is the one algorithm that cannot starve (strict arrival order); LOOK/SCAN can delay an edge request that keeps getting overtaken, though they still eventually serve it on a sweep.
For a single pending request, FCFS, SCAN, C-SCAN and LOOK all move the head the same distance.
True — with one request there is no reordering and no boundary sweep needed (LOOK/SCAN stop at that one request), so every algorithm just travels start→request.
Total head movement depends on the head's starting cylinder , not only on the request set.
True — the first move is measured from , so two identical queues with different start positions generally give different totals.
Spot the error
Each line contains a flawed statement. Say what's wrong.
"SCAN total = sum of gaps between sorted requests."
Wrong — that formula forgets the trip to the physical boundary (0 or 199) and the reversal; SCAN's total is (start→end) + (end→farthest-other-side), not just adjacent request gaps.
"LOOK saves distance over SCAN equal to (end − last request)."
Wrong — the saving is : SCAN walks past the last request up to the wall (that's extra) and then walks that same stretch back from the wall (another ), so the wasted stretch is covered twice — e.g. last request 183, end 199 gives saved, exactly the in the parent.
"C-SCAN's total = SCAN's total + disk width."
Wrong — C-SCAN doesn't service on the return, so its downward-sweep distance differs from SCAN's; you cannot just add one disk width to SCAN's number, you must recompute the one-directional sweeps plus the jump.
"You can compute total head movement by sorting the queue and summing consecutive differences."
Wrong — that only works if the head sweeps monotonically from one end and ignores the start position and direction; it fails for FCFS entirely and for the reversal legs of SCAN/LOOK.
"The head starts wherever the first request in the sorted list is."
Wrong — the head starts at a given position (like 53) that need not be a request at all; the first move goes from to whichever request the algorithm picks first.
"C-SCAN is called 'circular' because the head physically loops around the platter edge."
Wrong — "circular" refers to the scheduling pattern (wrap the logical cylinder index back to 0), not any physical looping; the head is an arm that moves radially in and out.
"SSTF is just SCAN because both pick nearby requests."
Wrong — SSTF always jumps to the globally nearest request and can reverse direction repeatedly, so it may zig-zag; SCAN commits to one direction until it must reverse. See SSTF (Shortest Seek Time First).
Why questions
Explain the reasoning, not just the fact.
Why does disk scheduling exist at all when process scheduling already exists?
Because the disk head physically moves and seek time dominates I/O latency; reordering the request queue cuts head travel, a concern independent of CPU time-slicing in Process Scheduling — FCFS, SJF, Round Robin.
Why is total head movement measured with absolute values ?
Distance can't be negative — moving from cylinder 122 down to 14 costs 108 cylinders of travel regardless of direction, so we take the magnitude of each hop.
Why does FCFS remain popular despite being wasteful?
It is the only strictly fair, starvation-free scheme and is trivial to implement; on lightly loaded disks the reordering benefit is small, so simplicity wins.
Why does SCAN make edge cylinders wait longer than middle ones?
The head reverses at the boundary, so a request just behind the head must wait for the head to reach the far end and come all the way back — worst at the edges.
Why does C-SCAN give more uniform wait times than SCAN?
By servicing in only one direction and resetting to the start, every cylinder is treated like a point on a one-way loop, so no position is systematically "always last" the way SCAN's just-passed edge is.
Why does seek time, not rotational latency, drive scheduling decisions here?
Seek (arm movement across cylinders) is the largest, most reorderable delay; rotational latency is per-request and harder to optimize by queue order — see Seek time vs Rotational latency.
Why is direction (up vs down) part of the problem statement for SCAN/LOOK/C-SCAN?
The first sweep's direction decides which requests are served before the reversal, changing the order and therefore the total; without it the answer is undefined.
Why can't we always just run the algorithm with the smallest total?
Fairness and starvation matter (see Starvation and Fairness in OS); an algorithm minimizing travel may leave a far-edge request waiting indefinitely under heavy load.
Edge cases
Boundary and degenerate inputs — reason each out.
Queue is empty (no pending requests). What does every algorithm do?
Nothing — total head movement is 0 and the head stays at ; there is no order to choose.
All requests are on the same side of the head (all above 53). Does SCAN ever reverse?
SCAN still travels to the boundary in the chosen direction, but with no requests behind it, the reverse leg services nothing; LOOK would simply stop at the last request and end.
The head starts exactly on a requested cylinder. Is that first move counted?
The move to that cylinder is distance 0, so it adds nothing to the total; it is served "for free" before the head moves anywhere.
A request sits exactly at the disk boundary (cylinder 0 or 199). Do SCAN and LOOK then agree?
Yes on that end — LOOK's "last request" is the boundary, so it travels the same distance as SCAN there; they only differ when the last request is short of the edge.
Only one request exists, and it's behind the head in the chosen direction. What happens?
SCAN/LOOK go to the boundary (or, for LOOK, immediately reverse), then come back to serve it; the chosen direction can cost extra travel, showing why direction matters even for one request.
Two requests are at identical cylinders. Does ordering between them affect the total?
No — the second adds distance 0 since the head is already there; duplicate cylinders never change total head movement.
The head starts at the exact middle with symmetric requests. Does direction choice matter for the total?
For LOOK/SCAN a symmetric layout can make up-first and down-first give equal totals, but C-SCAN still differs because its one-way jump is asymmetric by design.
Recall One-line self-test
If someone says "C-SCAN is best because it's circular and efficient," what's your rebuttal? ::: Circular ≠ smaller travel; C-SCAN pays a full-width empty return jump and optimizes fairness/uniform wait, not total head movement.
Head-movement pictures
The three figures below show the head's path over one full service cycle for the parent note's standard setup (head start 53; queue 98, 183, 37, 122, 14, 124, 65, 67; range 0–199; up first). Read the horizontal axis as cylinder number and the vertical axis as time flowing downward — so a diagonal line is the head sliding, and its total length is what we sum.
SCAN — sweeps up to the wall at 199, then reverses down to 14:
LOOK — identical order, but reverses at the last request 183 instead of the wall (the saved stretch is highlighted):
C-SCAN — sweeps up to 199, then jumps straight back to 0 serving nothing (the dashed empty jump), and resumes upward:
Connections
- Parent topic
- SSTF (Shortest Seek Time First)
- Seek time vs Rotational latency
- Hard Disk Drive structure (cylinders, tracks, sectors)
- Starvation and Fairness in OS
- Process Scheduling — FCFS, SJF, Round Robin
- I/O Subsystem and Device Drivers