Scheduling algorithm (SCAN, LOOK) in LLD - Deep Dive

Overview - Scheduling algorithm (SCAN, LOOK)

What is it?

Scheduling algorithms like SCAN and LOOK decide the order in which tasks or requests are handled, especially in systems like disk drives. They help organize work so that the system can be efficient and fair. SCAN moves in one direction servicing requests until it reaches the end, then reverses. LOOK is similar but stops earlier if no more requests are in that direction.

Why it matters

Without these algorithms, systems would waste time jumping back and forth randomly, causing delays and inefficiency. For example, a disk drive would spend extra time moving its read/write head unnecessarily, slowing down data access. Using SCAN or LOOK improves speed and fairness, making devices and systems feel faster and more reliable.

Where it fits

Before learning SCAN and LOOK, you should understand basic scheduling concepts and why order matters in processing tasks. After this, you can explore more advanced algorithms like C-SCAN or real-time scheduling, and how these fit into operating systems or hardware controllers.

Mental Model

Core Idea

Scheduling algorithms like SCAN and LOOK organize work by moving in one direction to serve requests, then reversing, to reduce wasted movement and improve efficiency.

Think of it like...

Imagine a librarian walking along a shelf to pick up books requested by readers. Instead of running back and forth randomly, the librarian walks in one direction picking all needed books, then turns around and picks the rest on the way back.

Disk Head Movement
┌───────────────┐
│               │
│  Requests:    │
│  • •   • • •  │
│               │
│  SCAN: Head → │
│  moves to end │
│  then reverses│
│               │
│  LOOK: Head → │
│  moves until  │
│  last request │
└───────────────┘

Build-Up - 7 Steps

1

Foundation

Understanding Basic Scheduling

Concept: Scheduling decides the order of tasks to improve system performance.

Imagine many tasks waiting to be done. If you do them randomly, you waste time switching between tasks. Scheduling helps by choosing a good order to reduce waiting and improve speed.

Result

Tasks get done faster and more fairly.

Understanding scheduling basics is key to grasping why SCAN and LOOK improve efficiency.

2

Foundation

Disk Head Movement Problem

Concept: Disk drives have a read/write head that moves to different tracks to access data.

The head moves over tracks like a finger on piano keys. Moving the head takes time, so the order of requests affects speed. Random movement wastes time.

Result

Realizing that reducing head movement saves time.

Knowing the physical cost of movement explains why scheduling algorithms matter.

3

Intermediate

SCAN Algorithm Explained

🤔Before reading on: do you think SCAN moves the head back immediately after each request or after reaching the end? Commit to your answer.

Concept: SCAN moves the head in one direction servicing all requests until the end, then reverses direction.

Imagine the head moving from the lowest to highest track, servicing requests on the way. When it reaches the last track, it reverses and services requests on the way back.

Result

Head movement is more organized, reducing unnecessary jumps.

Understanding SCAN shows how moving in one direction reduces wasted movement.

4

Intermediate

LOOK Algorithm Variation

🤔Before reading on: does LOOK always go to the end of the disk like SCAN, or does it stop earlier? Commit to your answer.

Concept: LOOK is like SCAN but stops moving in a direction once there are no more requests ahead.

Instead of going to the last track, LOOK stops at the furthest request in the current direction, then reverses. This saves time by not going to empty tracks.

Result

Even less wasted movement compared to SCAN.

Knowing LOOK's optimization helps understand trade-offs in scheduling.

5

Intermediate

Comparing SCAN and LOOK

Concept: Both reduce head movement but differ in how far they travel before reversing.

SCAN always goes to the disk's end before reversing, while LOOK stops at the last request. LOOK can be faster if requests are clustered.

Result

Choosing between SCAN and LOOK depends on request patterns.

Recognizing differences helps pick the right algorithm for a system.

6

Advanced

Handling Starvation and Fairness

🤔Before reading on: do you think SCAN and LOOK can cause some requests to wait forever? Commit to yes or no.

Concept: Scheduling must avoid starving requests that wait too long.

SCAN and LOOK reduce starvation by moving in both directions, ensuring all requests get served eventually. However, if new requests keep coming on one side, some may wait longer.

Result

Understanding fairness limitations guides improvements.

Knowing starvation risks helps design better scheduling policies.

7

Expert

Optimizing Scheduling in Real Systems

🤔Before reading on: do you think real disk schedulers use pure SCAN/LOOK or combine them with other techniques? Commit to your answer.

Concept: Real systems combine SCAN/LOOK with other methods for better performance.

Operating systems often use variants like C-SCAN or add priority handling. They also consider request arrival times and system load to optimize throughput and latency.

Result

Scheduling adapts dynamically to workload for best results.

Understanding real-world adaptations reveals the complexity behind simple algorithms.

Under the Hood

Internally, SCAN and LOOK maintain a queue of pending requests sorted by track number. The disk head moves in one direction, servicing requests in order. When it reaches the end (SCAN) or last request (LOOK), it reverses direction. This reduces seek time by minimizing back-and-forth movement. The algorithms rely on sorting and direction flags to track movement.

Why designed this way?

Early disk drives had slow mechanical heads. Random access caused long delays. SCAN was designed to mimic an elevator's movement to reduce wasted travel. LOOK improved on SCAN by avoiding unnecessary travel to empty ends, saving time. Alternatives like FCFS were simpler but less efficient.

Request Queue (sorted by track):
[10] [22] [35] [40] [50] [70] [90]

Head Direction: →

SCAN:
Head moves from low to high (10→90), servicing all.
Then reverses (90→10).

LOOK:
Head moves from low to highest request (10→90),
then reverses without going beyond 90.

Myth Busters - 4 Common Misconceptions

Quick: Does LOOK always go to the last track on the disk? Commit yes or no.

Common Belief: LOOK always moves the head to the last track like SCAN.

Reality: LOOK stops at the last request in the current direction, not the last track.

Why it matters: Believing this causes overestimating LOOK's movement and missing its efficiency benefits.

Quick: Can SCAN cause some requests to wait forever? Commit yes or no.

Common Belief: SCAN guarantees all requests are served quickly without starvation.

Reality: If new requests keep arriving on one side, some on the other side may wait longer, causing potential starvation.

Why it matters: Ignoring starvation risks can lead to unfair systems and poor user experience.

Quick: Is SCAN always better than simpler algorithms like FCFS? Commit yes or no.

Common Belief: SCAN is always the best scheduling algorithm for disks.

Reality: SCAN improves efficiency but may add complexity and overhead; sometimes simpler algorithms suffice for light workloads.

Why it matters: Assuming SCAN is always best can lead to over-engineering and wasted resources.

Quick: Does LOOK eliminate all unnecessary head movement? Commit yes or no.

Common Belief: LOOK completely removes wasted head movement.

Reality: LOOK reduces but does not eliminate all unnecessary movement, especially with scattered requests.

Why it matters: Overestimating LOOK's efficiency may cause ignoring other optimization opportunities.

Expert Zone

1

SCAN and LOOK's efficiency depends heavily on request distribution; clustered requests benefit more.

2

The choice between SCAN and LOOK affects latency variance, not just average seek time.

3

Real implementations often combine these algorithms with request merging and prioritization for better throughput.

When NOT to use

Avoid SCAN and LOOK in systems with highly random or real-time requests where latency guarantees matter. Instead, use algorithms like Shortest Seek Time First (SSTF) or deadline-based schedulers.

Production Patterns

Operating systems use variants like C-SCAN for fairness and predictability. Disk controllers may implement LOOK-like algorithms combined with caching and request reordering to optimize performance.

Connections

Elevator Control Systems

SCAN scheduling is inspired by elevator movement patterns.

Understanding elevator logic helps grasp how SCAN reduces back-and-forth movement in disks.

Real-Time Operating Systems

Scheduling algorithms balance efficiency and fairness, similar to real-time task scheduling.

Knowing disk scheduling aids understanding of how real-time systems prioritize tasks under constraints.

Supply Chain Logistics

Both involve optimizing routes to minimize travel and waiting times.

Recognizing this connection shows how scheduling principles apply beyond computing to physical systems.

Common Pitfalls

#1 Assuming LOOK always goes to the disk's end.

Wrong approach:

Implementing LOOK to always move head to max track regardless of requests.

Correct approach:

Implement LOOK to move head only up to the furthest pending request in the current direction.

Root cause:

Misunderstanding LOOK's optimization over SCAN.

#2 Ignoring starvation possibility in SCAN.

Wrong approach:

Using SCAN without monitoring request arrival patterns, causing some requests to wait indefinitely.

Correct approach:

Implement mechanisms to detect and prioritize long-waiting requests to prevent starvation.

Root cause:

Belief that SCAN inherently prevents starvation.

#3 Using SCAN/LOOK for all workloads blindly.

Wrong approach:

Applying SCAN in systems with very low or real-time workloads without considering simpler or specialized algorithms.

Correct approach:

Choose scheduling based on workload characteristics, possibly simpler FCFS or deadline schedulers.

Root cause:

Overgeneralizing SCAN/LOOK benefits.

Key Takeaways

Scheduling algorithms like SCAN and LOOK organize work to reduce wasted movement and improve efficiency.

SCAN moves the disk head to the end before reversing, while LOOK stops earlier at the last request, saving time.

Both algorithms reduce delays but can still cause some requests to wait longer if not managed carefully.

Real-world systems adapt these algorithms with additional techniques for fairness and performance.

Understanding these algorithms helps design better systems and reveals connections to other fields like elevators and logistics.

Practice

1. What is the main difference between the SCAN and LOOK disk scheduling algorithms?

easy

A. SCAN stops at the last request in the direction, LOOK goes to the disk edge

B. LOOK moves the head randomly, SCAN moves sequentially

C. LOOK stops at the last request in the direction, SCAN goes to the disk edge

D. SCAN only moves in one direction, LOOK moves back and forth

Solution

1. Step 1: Understand SCAN behavior

   SCAN moves the disk head to the end of the disk in one direction, servicing requests along the way.

2. Step 2: Understand LOOK behavior

   LOOK moves the disk head only as far as the last request in the current direction, then reverses.

3. Final Answer:

   LOOK stops at the last request in the direction, SCAN goes to the disk edge -> Option C

4. Quick Check:

   LOOK stops early, SCAN goes to edge [OK]

Hint: LOOK stops at last request, SCAN goes to disk edge [OK]

Common Mistakes:

• Confusing which algorithm stops at disk edge
• Thinking LOOK moves randomly
• Assuming SCAN moves only one way

2. Which of the following is the correct order of servicing requests using the SCAN algorithm if the head starts at 50 and requests are at [10, 20, 35, 70, 90] with disk size 100?

easy

A. 50 -> 70 -> 90 -> 35 -> 20 -> 10

B. 50 -> 70 -> 90 -> 100 -> 35 -> 20 -> 10

C. 50 -> 35 -> 20 -> 10 -> 0 -> 70 -> 90

D. 50 -> 90 -> 70 -> 35 -> 20 -> 10

Solution

1. Step 1: SCAN moves towards higher end first

   Starting at 50, SCAN moves up servicing 70 and 90, then reaches disk edge 100.

2. Step 2: SCAN reverses direction

   After reaching 100, it moves down servicing 35, 20, and 10.

3. Final Answer:

   50 -> 70 -> 90 -> 100 -> 35 -> 20 -> 10 -> Option B

4. Quick Check:

   SCAN goes to edge 100 before reversing [OK]

Hint: SCAN always goes to disk edge before reversing [OK]

Common Mistakes:

• Not including disk edge in the path
• Reversing direction too early
• Skipping requests on the way

3. Given the LOOK algorithm with head starting at 40 and requests at [10, 20, 35, 70, 90], what is the order of servicing requests if the head moves towards higher track numbers first?

medium

A. [40, 90, 70, 35, 20, 10]

B. [40, 70, 90, 100, 35, 20, 10]

C. [40, 35, 20, 10, 70, 90]

D. [40, 70, 90, 35, 20, 10]

Solution

1. Step 1: LOOK moves towards higher requests first

   Starting at 40, it services 70 and 90, stopping at last request 90.

2. Step 2: LOOK reverses direction

   Then it moves down servicing 35, 20, and 10, stopping at last request in that direction.

3. Final Answer:

   [40, 70, 90, 35, 20, 10] -> Option D

4. Quick Check:

   LOOK stops at last request, no disk edge [OK]

Hint: LOOK stops at last request, no disk edge [OK]

Common Mistakes:

• Including disk edge in LOOK path
• Reversing direction too early
• Skipping requests on the way

4. Identify the error in this SCAN algorithm implementation snippet where the head moves from 30 to 90 with requests at [20, 40, 60, 80]:

requests = [20, 40, 60, 80]
head = 30
for track in range(head, 100):
    if track in requests:
        print(f"Servicing {track}")
for track in range(head-1, -1, -1):
    if track in requests:
        print(f"Servicing {track}")

medium

A. The first loop should go to 101, not 100

B. The first loop should include the head position

C. The second loop should start from head, not head-1

D. The second loop should start from 99, not head-1

Solution

1. Step 1: Check range end in first loop

   range(head, 100) goes from 30 to 99 (exclusive end), missing disk edge at 100.

2. Step 2: Confirm disk convention

   As per standard problems (disk size 100 includes edge 100), first loop should be range(head, 101) to reach 100.

3. Final Answer:

   The first loop should go to 101, not 100 -> Option A

4. Quick Check:

   range exclusive, edge 100 needs 101 [OK]

Hint: Range end exclusive, use 101 for disk edge 100 [OK]

Common Mistakes:

• Confusing inclusive vs exclusive range ends
• Starting second loop incorrectly
• Assuming head position is included twice

5. You have a disk with size 200 tracks and requests at [10, 50, 120, 180]. The head is at 100 and moves using LOOK algorithm. What is the total head movement if the head moves towards lower track numbers first?

hard

A. 260 tracks

B. 160 tracks

C. 180 tracks

D. 120 tracks

Solution

1. Step 1: Initial direction to lower tracks

   Lower requests: 50, 10. Path: 100 -> 50 (50 tracks), 50 -> 10 (40 tracks). Subtotal: 90.

2. Step 2: Reverse direction to higher tracks

   Higher requests: 120, 180. Path: 10 -> 120 (110 tracks), 120 -> 180 (60 tracks). Subtotal: 170.

3. Step 3: Total head movement

   90 + 170 = 260 tracks.

4. Final Answer:

   260 tracks -> Option A

5. Quick Check:

   Sum of |current - next| over servicing sequence [OK]

Hint: Sum distances in servicing order: 100-50-10-120-180 [OK]

Common Mistakes:

• Including disk edges in LOOK movement
• Adding extra distances beyond last requests
• Misordering request servicing