9.3 Elevator Algorithms: SCAN & C-SCAN Disk Scheduling

Back to Operating Systems Notes

📚Module 09: Storage & Disk SchedulingTopic 9.3⏱️20 min read

🎯High-Yield For:Computer Science Foundations • Systems Engineering • Disk Scheduling

💡 Core Intuition

🍳 The Everyday Analogy: The Skyscraper Elevator

Imagine a 50-story commercial skyscraper with hundreds of passengers waiting on diverse floors:

Architecture Flow

The Skyscraper Elevator Sweep Pipeline

Contrasting chaotic passenger hopping with structured directional sweeps

💡 Hover or click any card for deep-dive operational details

🛗The Problem

Chaotic Passenger Hopping

Greedy Proximity (SSTF)

The elevator stops on floor 10, then hops to floor 11, then back to floor 9.

→

The Elevator Principle

🏢Directional Sweep

The Upward Sweep

SCAN Policy

The elevator moves strictly upward, picking up everyone who wants to go up until it reaches the top floor.

→

Uniform Wait Time

🔄Circular Loop

Express Return to Ground

C-SCAN Policy

The elevator sweeps all the way to Floor 50, then rides non-stop express back to the Lobby without opening doors.

• SCAN (Elevator Algorithm): Sweeps back and forth across the disk surface, servicing requests along its current trajectory until it hits the physical extremity.
• C-SCAN (Circular SCAN): Sweeps in one direction, then immediately returns to the opposite boundary without servicing requests on the return journey, guaranteeing uniform wait times.

---

💻 Bridging to Computer Science

While Shortest Seek Time First (SSTF) achieves impressive seek reduction, its susceptibility to starvation renders it unacceptable for general-purpose multi-user operating systems.

Computer architects resolved this by implementing Elevator Algorithms:

1. SCAN: Prevents starvation by maintaining a continuous sweep across cylinders.
2. C-SCAN: Eliminates the density bias of SCAN by treating the cylinder tracks as a continuous circular loop.

---

📚 Core Deep-Dive & Concepts

1. The SCAN (Elevator) Algorithm

Algorithm Mechanics

1. The read/write head begins at its current position and travels in a designated direction (e.g., towards lower cylinders or towards higher cylinders).
2. It services all pending requests in its path as it encounters their cylinders.
3. Crucially, the arm continues traveling until it reaches the physical extremity of the disk (Cylinder $0$ or Cylinder $199$), even if the last request occurred earlier!
4. At the boundary, the actuator motor reverses direction, and the arm travels across the disk in the opposite direction, servicing pending requests.

---

2. Step-by-Step Mathematical Trace: SCAN

• Initial Head Position: 53
• Current Direction: Moving towards lower cylinders (towards 0).
• Request Queue: [ 98, 183, 37, 122, 14, 124, 65, 67 ]

💽

SCAN (Elevator) Disk Head Trajectory

Actuator sweeps down to boundary (0), reverses, and sweeps up: 53 → 37 → 14 → 0 (Boundary) → 65 → 67 → 98 → 122 → 124 → 183

Showing All 9 Traversal Legs

💡Hover over any node or click [Next Step ▶] to inspect seek displacement (Δ) and cumulative travel (Σ).

Total Head Movement236 Cylinders

Down Leg (53 → 0)53 Cylinders

Up Leg (0 → 183)183 Cylinders

Reversal PointPhysical Limit (0)

Total Head Movement Calculation

Because the motion consists of two monotonic linear sweeps, the calculation simplifies elegantly:

$\text{Down Leg: } |53 - 0| = 53\text{ Cylinders}$

$\text{Up Leg: } |183 - 0| = 183\text{ Cylinders}$

$\mathbf{\text{Total Head Movement (SCAN)} = 53 + 183 = 236\text{ Cylinders}}$

(Notice that the individual differences $|53-37| + |37-14| + |14-0| + |65-0| + \dots + |183-124|$ sum to the exact same $236$ cylinders).

Evaluation of SCAN

• Strengths: Completely eliminates starvation. Every request is serviced within at most two full sweeps of the disk.
• Weaknesses:
  • Boundary Waste: Travels all the way to Cylinder $0$ even though the last requested track was $14$.
  • Unequal Wait Times: When the head reverses at Cylinder $0$, the cylinders near $0$ have the lowest density of new requests (they were just visited!). Meanwhile, cylinders near $199$ have been waiting the longest.

---

3. Circular-SCAN (C-SCAN) Scheduling

Why C-SCAN Was Invented: Uniform Wait Times

Under SCAN, cylinders at the extremities enjoy an unfair advantage: when the head reaches an end, it reverses and immediately revisits adjacent cylinders. In contrast, cylinders in the middle of the disk must wait for the head to travel to the extremity, reverse, and travel all the way back!

C-SCAN resolves this by treating cylinders as a continuous ring:

Algorithm Mechanics

1. The head moves in one direction (e.g. towards higher tracks), servicing requests along the way.
2. Upon reaching the end of the disk (Cylinder $199$), the head immediately returns to the opposite end (Cylinder $0$) without servicing any requests on the return trip.
3. Once at Cylinder $0$, it resumes servicing requests in the original forward direction.

---

4. Step-by-Step Mathematical Trace: C-SCAN

• Initial Head Position: 53
• Current Direction: Moving towards higher cylinders (towards 199).
• Request Queue: [ 98, 183, 37, 122, 14, 124, 65, 67 ]

💽

C-SCAN (Circular Elevator) Disk Head Trajectory

Monotonic upward sweep to 199 followed by express return to 0: 53 → 65 → 67 → 98 → 122 → 124 → 183 → 199 ⇢ 0 → 14 → 37

Showing All 10 Traversal Legs

💡Hover over any node or click [Next Step ▶] to inspect seek displacement (Δ) and cumulative travel (Σ).

Total Head Movement382 Cylinders

Up Leg (53 → 199)146 Cylinders

Express Return (199 → 0)199 Cylinders

Resume Leg (0 → 37)37 Cylinders

Total Head Movement Calculation

$\text{Leg 1 (Upward Sweep): } |199 - 53| = 146\text{ Cylinders}$

$\text{Leg 2 (Return Trip): } |199 - 0| = 199\text{ Cylinders}$

$\text{Leg 3 (Resume Sweep): } |37 - 0| = 37\text{ Cylinders}$

$\mathbf{\text{Total Head Movement (C-SCAN)} = 146 + 199 + 37 = 382\text{ Cylinders}}$

(Note: In modern disk controllers with high-speed voice coil slewing, the return trip from 199 to 0 is an uninterrupted high-velocity seek that completes in a fraction of normal stepped seek time).

---

5. Architectural Comparison Matrix

Architectural Feature	First-Come First-Served (FCFS)	Shortest Seek Time First (SSTF)	SCAN (Elevator)	Circular-SCAN (C-SCAN)
Total Head Movement	Very High ($640$ cyl)	Lowest ($236$ cyl)	Moderate ($236$ cyl)	Moderate ($382$ cyl)
Starvation Potential	Zero ($0\%$)	Severe Risk	Zero ($0\%$)	Zero ($0\%$)
Wait-Time Uniformity	Moderate	Very Poor	Moderate (Favors ends)	Maximum (Optimal)
Boundary Reversal	Reverses on demand	Reverses on proximity	Reverses at disk edge	Resets to opposite edge
Implementation Complexity	Trivial ($\mathcal{O}(1)$)	Greedy scan ($\mathcal{O}(N)$)	Ordered sweep ($\mathcal{O}(\log N)$)	Ordered sweep ($\mathcal{O}(\log N)$)

---

🏭 In The Real World: Production Case Study

Linux I/O Schedulers: Anticipatory, Deadline, and BFQ

Modern enterprise Linux servers run specialized disk scheduling frameworks inside the block I/O layer:

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

Question 1: Why does C-SCAN generate more total cylinder movements than SCAN on the same benchmark, yet is often preferred in production systems? Answer:

1. C-SCAN incurs the additional seek distance of returning from the highest cylinder ($199$) back to the lowest cylinder ($0$) without servicing requests. In our trace, this increased total movement from $236$ to $382$ cylinders.
2. However, C-SCAN provides strictly uniform waiting times:
   • In SCAN, requests arriving just behind the head must wait for a full double-sweep across the entire disk before the head returns.
   • In C-SCAN, every request enjoys an almost identical expected waiting time because the head sweeps across the cylinder space cyclically in one direction.
3. Furthermore, on physical hard drives, an uninterrupted full-stroke reset across platters executes significantly faster than multiple stop-and-start seeks.

---

Question 2: Under what specific scenario does SCAN travel to a cylinder that contains NO pending request? Answer:

• SCAN always travels to the physical extremity of the disk (Cylinder $0$ or Cylinder $199$) before reversing direction.
• In our benchmark, the lowest requested cylinder was $14$.
• Despite no request existing at Cylinder $0$, SCAN still forced the actuator arm to travel all the way from $14$ down to $0$ before reversing direction. This unnecessary boundary traversal was the exact motivation for inventing the LOOK algorithm.

Common Interview Traps

• The Missing Boundary Trap in SCAN: When tracing SCAN on an exam, never forget to include the boundary cylinder ($0$ or $199$)! If the head is moving toward $0$, it must travel to $0$ before reversing. Stopping at the lowest request ($14$) is the LOOK algorithm, not SCAN!
• Direction Specification Matters: Always verify the initial direction stated in the problem statement. Tracing SCAN moving toward $199$ produces completely different intermediate steps and seek totals than tracing toward $0$.

---

🗺️View Complete Operating Systems Roadmap & Syllabus

← Previous Topic9.2 FCFS & SSTF Disk SchedulingNext Topic →9.4 LOOK & C-LOOK Disk Scheduling