Scheduling algorithm (SCAN, LOOK) in LLD - System Design Guide

Problem Statement

When multiple requests for disk access arrive, a naive approach like First-Come-First-Serve causes the disk head to move back and forth inefficiently, increasing seek time and slowing down overall performance. This leads to longer wait times and reduced throughput, especially under heavy load.

Solution

SCAN and LOOK scheduling algorithms reduce seek time by moving the disk head in one direction servicing all requests until it reaches the end (SCAN) or the last request in that direction (LOOK), then reversing direction. This approach minimizes unnecessary head movement and balances fairness and efficiency.

Architecture

Request Queue

→Disk Scheduler

↓

SCAN / LOOK Algo

SCAN / LOOK Algo

This diagram shows how incoming disk requests enter a queue, are processed by the disk scheduler using SCAN or LOOK algorithms, which then control the disk head movement to service requests efficiently.

Trade-offs

✓ Pros

→

Reduces total seek time by servicing requests in one direction before reversing.

→

Prevents starvation by ensuring all requests are eventually serviced.

→

Balances fairness and efficiency better than simple FCFS or SSTF algorithms.

✗ Cons

→

SCAN can waste time moving to the end of the disk even if no requests exist there.

→

LOOK reduces unnecessary movement but adds complexity in tracking request boundaries.

→

Both algorithms may cause longer wait times for requests just behind the current head position.

Use when disk I/O requests are frequent and random, and reducing seek time is critical for performance, typically in systems with moderate to high disk load.

Avoid when request load is very low (under 100 requests per second) or when real-time guarantees are needed, as these algorithms do not prioritize urgent requests.

Real World Examples

Linux Kernel

Uses the LOOK algorithm variant in its elevator scheduler to optimize disk I/O by reducing seek time and improving throughput.

Windows NT

Implemented SCAN-based disk scheduling to balance fairness and efficiency in servicing disk requests.

IBM Mainframes

Applied SCAN scheduling to manage large volumes of disk requests efficiently in high-throughput environments.

Code Example

The before code shows a simple FCFS scheduler that moves the disk head to each request in arrival order, causing inefficient movement. The after code implements the LOOK algorithm, moving the head in one direction servicing all requests before reversing, reducing unnecessary head movement and improving efficiency.

LLD

### Before: Naive FCFS Disk Scheduler
class DiskSchedulerFCFS:
    def __init__(self):
        self.queue = []
        self.head = 0

    def add_request(self, request):
        self.queue.append(request)

    def process_requests(self):
        while self.queue:
            request = self.queue.pop(0)
            print(f"Moving head from {self.head} to {request}")
            self.head = request


### After: LOOK Disk Scheduler
class DiskSchedulerLOOK:
    def __init__(self):
        self.queue = []
        self.head = 0
        self.direction = 1  # 1 for up, -1 for down

    def add_request(self, request):
        self.queue.append(request)
        self.queue.sort()

    def process_requests(self):
        while self.queue:
            # Filter requests in current direction
            if self.direction == 1:
                candidates = [r for r in self.queue if r >= self.head]
                if not candidates:
                    self.direction = -1
                    continue
                next_request = candidates[0]
            else:
                candidates = [r for r in self.queue if r <= self.head]
                if not candidates:
                    self.direction = 1
                    continue
                next_request = candidates[-1]

            print(f"Moving head from {self.head} to {next_request}")
            self.head = next_request
            self.queue.remove(next_request)

Alternatives

First-Come-First-Serve (FCFS)

Services requests strictly in arrival order without optimizing head movement.

Use when: Use when simplicity is more important than performance or when request load is very low.

Shortest Seek Time First (SSTF)

Selects the request closest to the current head position, potentially causing starvation.

Use when: Use when minimizing seek time is critical and starvation can be tolerated or mitigated.

C-SCAN (Circular SCAN)

Moves the head in one direction only and jumps back to start without servicing requests on return.

Use when: Use when uniform wait times are needed and fairness is prioritized over total seek time.

Summary

SCAN and LOOK algorithms reduce disk seek time by moving the head in one direction servicing requests before reversing.

LOOK improves on SCAN by stopping at the last request in the direction, avoiding unnecessary movement.

These algorithms balance fairness and efficiency better than naive scheduling methods.

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