4.2.38 · D1Operating Systems

Foundations — Disk scheduling — FCFS, SCAN, C-SCAN, LOOK

1,911 words9 min readBack to topic

Before you can read the parent note and follow every line, you need to own a handful of symbols and pictures. This page builds each one from absolutely nothing, in an order where each idea leans on the one before it. Nothing here is assumed — if the parent used it, we define it here.


1. The disk as a set of rings — what a "cylinder" is

Picture a shiny circular platter, like a tiny record. Data is not written randomly on it — it lives on concentric rings, one inside the other, like the rings you see when you cut a tree trunk.

Figure — Disk scheduling — FCFS, SCAN, C-SCAN, LOOK

The picture: each ring in the figure is one cylinder. The innermost ring is cylinder ; they count outward.

Why the topic needs it: the entire game is moving between rings. If there were no rings — if data were one blob — there would be nothing to schedule. See Hard Disk Drive structure (cylinders, tracks, sectors) for the full anatomy.


2. Numbering the rings — the "cylinder number"

We give every ring a whole number so we can do arithmetic on positions.

The picture: unroll the rings into a straight number line — a ruler laid from on the left to on the right. Every request is now just a dot on that ruler. This "flatten the rings into a line" trick is the single most important visual of the whole topic.

Figure — Disk scheduling — FCFS, SCAN, C-SCAN, LOOK

Why the topic needs it: once rings are numbers on a line, "how far did the head move?" becomes plain subtraction. That is what makes the whole subject computable.


3. The head — the moving arm

The picture: on the number-line, the head is a single marker sitting on one dot. To serve a request elsewhere, the marker must walk along the line to that dot — it cannot teleport (except in C-SCAN's return jump, which is still a real physical sweep).

Why the topic needs it: there is only one head. It cannot be in two places at once, so requests must be served in some order, one after another. That constraint is the entire reason "scheduling" exists.


4. The symbol — the service order

The parent note writes things like . Let us earn every piece.

The picture: on the number line, drop a labelled flag at each stop in the order the head reaches them: flag at the start dot, then , , … A different algorithm simply plants the same flags in a different order.


5. Absolute value — "distance, ignore direction"

The parent's core formula is stuffed with vertical bars, . Here is what they mean, from zero.

Why we need it here — the WHY of choosing this tool: the head moving from cylinder down to covers cylinders. But moving from up to gives too — wait, but . A negative distance is meaningless for physical travel; the arm slides cylinders either way. Absolute value is exactly the tool that says "I care how far, not which way." We chose it (not plain subtraction) precisely because direction must be discarded when totalling travel.

Figure — Disk scheduling — FCFS, SCAN, C-SCAN, LOOK

6. Summation — "add up all the steps"

The picture: each step of the head is a coloured segment on the number line. just means lay all those segments end to end and measure the total length.


7. "Direction" and "the boundary" — the last two ingredients

The picture: on the number line, mark the two walls at and . "Direction" is an arrow pointing left or right; "boundary" is hitting a wall.


Prerequisite map

Disk platters have rings

Ring = track = cylinder

Number the rings 0 to max

Flatten rings into a number line

One head marker on the line

Service order h0 h1 ... hn

Absolute value = distance ignore sign

Summation adds all steps

Direction up or down and boundaries

Total head movement

Disk scheduling FCFS SCAN C-SCAN LOOK

Read it bottom to top as a build: rings → numbers → a line → a moving marker → an order of stops, plus the distance and sum tools, plus direction and edges — all feeding the single quantity total head movement, which is what every algorithm in the parent note competes to shrink.


Where this feeds next

  • The why-it's-slow half of the story lives in Seek time vs Rotational latency — this page counts cylinders; that page turns cylinders into milliseconds.
  • The "many requests waiting, pick an order" pattern is the same one behind Process Scheduling — FCFS, SJF, Round Robin and the greedy cousin SSTF (Shortest Seek Time First).
  • Why a fair order matters at all: Starvation and Fairness in OS.
  • Where these requests come from in the first place: I/O Subsystem and Device Drivers.

Equipment checklist

You are ready for the parent note once you can answer each of these out loud:

What does a cylinder physically correspond to?
One concentric ring (track) of data on the platter stack; for scheduling it is just a numbered position.
Why do we flatten the rings into a number line?
Because then "how far did the head move?" becomes plain subtraction between cylinder numbers.
How many read/write heads serve requests at once, and why does that matter?
One — so requests must be served in some order, which is the whole reason scheduling exists.
In , what does the subscript mean?
A step counter: is the start, the first stop, …, the last stop — it records the order.
What does compute and why the bars?
The distance of one head move; the bars discard direction because physical travel is never negative.
What does instruct you to do?
Let run to , compute each term, and add them all — here, add every step's distance.
What are the two inputs people forget besides the request list?
The head's start position and the chosen direction (up or down).
What is the boundary, and which algorithm ignores it?
The physical edges and ; LOOK never visits an edge, SCAN and C-SCAN do.