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.