9.4 Optimized Traversal: LOOK & C-LOOK Disk Scheduling

Back to Operating Systems Notes

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

🎯High-Yield For:Computer Science Foundations • Systems Engineering • Storage Optimization

💡 Core Intuition

🍳 The Everyday Analogy: The Smart Delivery Van Driver

Imagine a parcel delivery van traversing a long suburban avenue numbered from House 0 to House 199:

Architecture Flow

Delivery Route Traversal Optimization Pipeline

Contrasting blind boundary trips with intelligent look-ahead stops

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

🛑The Wasteful Rule

Driving to the Dead-End Turnaround

SCAN Policy Waste

Under strict SCAN rules, the driver must drive all the way to House 0 at the end of the avenue.

→

Intelligent Check

👀The Smart Stop

Looking Ahead on the Route

LOOK Policy

At House 14, the driver checks their route sheet: 'Are there any deliveries further down?'

→

Circular Adaptation

🔄Express Shortcut

Circular Shortcut Without Edge Trips

C-LOOK Policy

When traveling outward, stop at the highest requested house (183), then take the highway directly to the lowest requested house (14).

• LOOK: Eliminates the boundary waste of SCAN by looking ahead and reversing immediately at the last pending request in the current direction.
• C-LOOK: Eliminates the boundary waste of C-SCAN by bounding the return journey strictly between the highest and lowest pending requests.

---

💻 Bridging to Computer Science

In both SCAN and C-SCAN, the read/write head mechanically travels to the physical ends of the disk platter (Cylinder $0$ and Cylinder $199$).

In real-world storage controllers, traveling to the physical end of a disk when no request is waiting there is pure wasted mechanical motion.

To optimize head motion, operating systems implement LOOK and C-LOOK:

• Before moving the actuator arm to the next cylinder, the controller looks ahead in the pending request queue.
• If no pending requests exist further along the current direction of travel, the arm reverses direction immediately without visiting the extremity.

---

📚 Core Deep-Dive & Concepts

1. The LOOK Scheduling Algorithm

Algorithm Mechanics

1. The read/write head moves in the designated direction, servicing requests along its trajectory.
2. The controller continuously checks the request queue: Are there any pending requests ahead of the current head position in the current direction?
3. As soon as the last pending request in that direction is serviced, the actuator arm reverses direction immediately!
4. The head never travels to the physical disk boundary ($0$ or $199$) unless an actual request happens to reside there.

---

2. Step-by-Step Mathematical Trace: LOOK

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

💽

LOOK Disk Head Trajectory

Bounded sweep reversing at lowest pending request (14): 53 → 37 → 14 (Reverse) → 65 → 67 → 98 → 122 → 124 → 183

Showing All 8 Traversal Legs

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

Total Head Movement208 Cylinders

Down Leg (53 → 14)39 Cylinders

Up Leg (14 → 183)169 Cylinders

Boundary TraveledNone (Saved 28 cyl)

Total Head Movement Calculation

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

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

$\mathbf{\text{Total Head Movement (LOOK)} = 39 + 169 = 208\text{ Cylinders}}$

Mechanical Distance Comparison: SCAN vs LOOK

• SCAN: Traveled from $53$ all the way to the physical boundary at $0$ ($53$ cylinders).
• LOOK: Traveled from $53$ only as far as the lowest pending request at $14$ ($39$ cylinders), saving $14$ cylinders on the downward pass and $14$ cylinders on the upward return—an immediate $28$-cylinder reduction in mechanical wear and seek latency!

---

3. Circular-LOOK (C-LOOK) Scheduling

Algorithm Mechanics

1. The head services requests monotonically in one direction (e.g. towards higher tracks).
2. It proceeds only as far as the highest requested cylinder in that direction ($183$). It does not proceed to the physical edge ($199$).
3. Once the highest requested cylinder is serviced, the head executes an express return trip directly to the lowest requested cylinder ($14$). It does not return to Cylinder $0$.
4. At the lowest requested cylinder, it resumes servicing requests in the original forward direction.

---

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

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

💽

C-LOOK (Circular LOOK) Disk Head Trajectory

Upward sweep to highest request (183) with express return to lowest request (14): 53 → 65 → 67 → 98 → 122 → 124 → 183 ⇢ 14 → 37

Showing All 8 Traversal Legs

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

Total Head Movement322 Cylinders

Up Leg (53 → 183)130 Cylinders

Express Return (183 → 14)169 Cylinders

Resume Leg (14 → 37)23 Cylinders

Total Head Movement Calculation

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

$\text{Leg 2 (Return Trip): } |183 - 14| = 169\text{ Cylinders}$

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

$\mathbf{\text{Total Head Movement (C-LOOK)} = 130 + 169 + 23 = 322\text{ Cylinders}}$

Actuator Travel Savings: C-SCAN vs C-LOOK

• C-SCAN Total Movement: $382$ Cylinders (swept to physical limits $199$ and $0$).
• C-LOOK Total Movement: $322$ Cylinders (bounded strictly by outer requests $183$ and $14$).
• Mechanical Efficiency: Immediate reduction of $60$ cylinders ($15.7\%$ less actuator movement) with zero starvation risk!

---

5. The Master 6-Algorithm Comparative Benchmark

Here is the definitive comparative summary of all six fundamental disk scheduling algorithms evaluated on the identical standard benchmark:

$\text{Initial Position: } 53, \quad \text{Direction: Toward 0}, \quad \text{Queue: } [98, 183, 37, 122, 14, 124, 65, 67]$

Algorithm	Total Head Movement (Cylinders)	Starvation Risk	Boundary Traversal to $0$ or $199$?	Performance Ranking
First-Come, First-Served (FCFS)	$\mathbf{640}$	Zero ($0\%$)	No	6th (Worst)
Circular-SCAN (C-SCAN)	$\mathbf{382}$	Zero ($0\%$)	Yes (Visits both $199$ & $0$)	5th
Circular-LOOK (C-LOOK)	$\mathbf{322}$	Zero ($0\%$)	No (Bypasses empty ends)	4th
SCAN (Elevator)	$\mathbf{236}$	Zero ($0\%$)	Yes (Visits Cylinder $0$)	2nd (Tie)
Shortest Seek Time First (SSTF)	$\mathbf{236}$	Severe Risk	No	2nd (Tie, Unstable)
LOOK (Optimized Elevator)	$\mathbf{208}$	Zero ($0\%$)	No (Reverses at request $14$)	1st (Winner!)

Key Architectural Takeaway:
LOOK achieves the absolute lowest total head movement ($208$ cylinders) while guaranteeing zero starvation, making it the premier real-world scheduling discipline for magnetic disk storage!

---

🏭 In The Real World: Production Case Study

Modern Enterprise Storage: NCQ (Native Command Queuing) in SATA / SAS

Modern enterprise storage offloads disk scheduling from the OS CPU kernel directly into on-disk DSP microcontrollers:

Native Command Queuing (NCQ) Architecture

Hardware-accelerated rotational and seek optimization inside on-disk controller firmware

Host Layer

Operating System Kernel

↓

Controller Firmware

On-Board ARM/DSP Microcontroller

↓

Mechanical Servicing

Dual Seek + Rotational Optimization (C-LOOK)

1. Why Hardware NCQ Outperforms OS Schedulers:
   • The OS only knows the cylinder number, not the exact instantaneous angular position of the spinning platter.
   • The hard drive's on-board firmware knows the exact microsecond rotational location of the heads.
2. Rotational Position Sensing (RPS):
   • NCQ evaluates both seek time AND rotational latency simultaneously. If cylinder 98 is 10 tracks away but sector 0 is about to spin under the head, the controller services cylinder 98 before cylinder 65!

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

Question 1: What is the fundamental difference between the SCAN algorithm and the LOOK algorithm? Answer:

• SCAN: The actuator arm travels all the way to the physical extremity of the disk (Cylinder $0$ or Cylinder $Max$) before reversing direction, regardless of where the last pending request is located.
• LOOK: The actuator arm travels only as far as the final pending request in the current direction, verifies no further requests exist ahead, and reverses immediately without ever visiting the unrequested physical extremity.

---

Question 2: Trace the LOOK algorithm on a disk with 200 tracks ($0\text{–}199$), starting at track $50$, moving upward towards higher tracks, with pending requests: $\mathbf{82, 170, 43, 140, 24, 16, 190}$ Calculate the total seek distance. Answer:

1. Initial State: Head at $50$, moving upward.
2. Upward Sweep:
   • Pending higher requests: 82, 140, 170, 190.
   • Head services: $50 \to 82 \to 140 \to 170 \to \mathbf{190}$.
   • At $190$, look ahead reveals no requests $> 190$. (Does NOT visit $199$!).
   • Upward distance: $|190 - 50| = \mathbf{140\text{ Cylinders}}$.
3. Downward Sweep:
   • Reverses at $190$ and travels downward:
   • Services remaining requests: $43 \to 24 \to \mathbf{16}$.
   • At $16$, look ahead reveals no requests $< 16$. (Does NOT visit $0$!).
   • Downward distance: $|190 - 16| = \mathbf{174\text{ Cylinders}}$.
4. Total Head Movement: $\text{Total Seek Distance} = 140 + 174 = \mathbf{314\text{ Cylinders}}$

Common Interview Traps

• The "Visiting Boundary" Trap in LOOK/C-LOOK: Remember: LOOK and C-LOOK NEVER visit Cylinder $0$ or $199$ unless the request queue explicitly contains $0$ or $199$! If you include $0$ or $199$ in a LOOK trace, your answer will be marked incorrect.
• The Direction Reversal Calculation Shortcut: Because LOOK sweeps monotonically in each direction, you do not need to add every single individual step: $\text{Total Distance} = (\text{Max Requested} - \text{Head}) + (\text{Max Requested} - \text{Min Requested})$ (when starting upward). This formula yields the exact answer in seconds.

---

🗺️View Complete Operating Systems Roadmap & Syllabus

← Previous Topic9.3 SCAN & C-SCAN Disk SchedulingNext Topic →10.1 File Attributes & Operations