Course contentsShow
← Computer Science
Lesson 1425 of 2,87232. File SystemsFree lesson

SCAN (Elevator) Algorithm

Moving the disk arm in one direction servicing requests, then reversing direction like an elevator.

SCAN (Elevator) Algorithm

What you'll learn: How the SCAN disk scheduling algorithm mimics an elevator's movement pattern to service disk requests efficiently.


Core Idea

The SCAN algorithm (also called the Elevator algorithm) solves the problem of inefficient disk head movement by treating the disk arm like an elevator: it moves in one direction servicing all requests along the way, then reverses direction when it reaches the end and continues servicing requests on the return trip.

Unlike SSTF (which greedily picks the closest request and can cause starvation), SCAN guarantees that every request will eventually be serviced because the disk arm sweeps across the entire disk in a predictable pattern.

How It Works

Imagine a building elevator:

  1. The elevator starts moving in one direction (say, up)
  2. It stops at every floor where someone pressed a button
  3. When it reaches the top floor, it reverses and travels downward
  4. It services all requests on the way down
  5. At the bottom, it reverses again and repeats

The SCAN disk scheduler works identically:

  • The disk arm moves toward one end (e.g., cylinder 0 or the highest cylinder)
  • Services all requests it encounters along the way
  • Reverses direction at the boundary
  • Services requests in the opposite direction

Advantages Over Previous Algorithms

  • No starvation: Unlike SSTF, every request gets serviced in bounded time
  • More predictable: Response time is more uniform than FCFS or SSTF
  • Better throughput: Reduces wild back-and-forth seeking

Trade-offs

  • Requests just missed by the passing arm must wait for a full sweep
  • Cylinders in the middle get serviced more frequently than those at the ends

Key Takeaway: SCAN moves the disk arm like an elevator—servicing requests in one direction until reaching the end, then reversing—providing fairness and predictability that SSTF lacks.