Operating System - SCAN Disk Scheduling Algorithm (Elevator Algorithm)

Definition:

The SCAN disk scheduling algorithm, also known as the Elevator Algorithm, moves the disk arm in one direction, servicing all the requests until it reaches the end of the disk, then reverses direction and continues servicing requests on the return path.

Key Idea:

The disk arm works like an elevator, going in one direction and servicing requests along the way, then reversing and doing the same in the opposite direction.

How It Works:

  1. Start at the initial head position.

  2. Move in a given direction (say increasing cylinder numbers).

  3. Service all requests in that direction.

  4. Once the end is reached, reverse direction and service remaining requests.

Example:

  • Disk Range: 0 – 199

  • Initial Head Position: 53

  • Requests: 98, 183, 37, 122, 14, 124, 65, 67

  • Direction: Toward higher cylinders (right)

Sorted Requests:

14, 37, 53, 65, 67, 98, 122, 124, 183

SCAN Execution Order (Right then Left):

  1. From 53 → move right and service:
    65, 67, 98, 122, 124, 183

  2. Reverse direction, go left and service:
    37, 14

Serviced Order:

65 → 67 → 98 → 122 → 124 → 183 → 37 → 14

Head Movements:

  • 53 → 65 → 67 → 98 → 122 → 124 → 183

    • Movement = 183 - 53 = 130

  • 183 → 37 → 14

    • Movement = 183 - 14 = 169

Total Head Movement = 130 + 169 = 299 cylinders

Visualization:

SCAN (Elevator) Disk Scheduling Algorithms - GeeksforGeeks

  • More efficient than FCFS and SSTF in reducing starvation.

  • Serves all requests fairly in both directions.

Disadvantages:

  • May not be optimal if all requests are on one side.

  • Reaches the end even if there are no requests — unnecessary movement.