SCAN (elevator algorithm) in Operating Systems - Full Explanation

Introduction

Imagine a busy elevator in a tall building that needs to pick up and drop off passengers efficiently. The problem is how to serve requests in a way that reduces waiting time and avoids unnecessary back-and-forth movement. The SCAN algorithm solves this problem for disk scheduling by moving the disk arm in one direction, servicing requests along the way, then reversing direction at the end.

Explanation

Movement Direction

The SCAN algorithm moves the disk arm in one fixed direction, either towards the highest or lowest track number. It services all requests in that direction until it reaches the end of the disk. Then, it reverses direction and services requests on the way back.

SCAN moves the disk arm like an elevator, sweeping in one direction before reversing.

Request Servicing

As the disk arm moves, it picks up all pending requests on its path in order. This reduces the total movement compared to jumping back and forth randomly. Requests are handled in sequence based on their position along the disk tracks.

Requests are serviced in order along the arm's path, minimizing unnecessary movement.

End of Disk Behavior

When the disk arm reaches the last track in its current direction, it reverses and starts servicing requests in the opposite direction. This ensures no requests are missed and the arm continuously moves back and forth like an elevator.

The arm reverses direction only at the disk's ends, ensuring continuous sweeping.

Advantages Over Other Algorithms

SCAN reduces the average waiting time compared to simpler methods like First-Come-First-Serve by avoiding long delays for requests far from the current arm position. It also prevents starvation, where some requests might never get serviced.

SCAN balances efficiency and fairness by servicing requests in a sweeping pattern.

Real World Analogy

Imagine an elevator in a tall building that moves up, stopping at every floor where someone wants to get on or off. When it reaches the top floor, it reverses and moves down, again stopping at requested floors. This way, the elevator doesn't waste time going up and down randomly but follows a clear path.

Movement Direction → Elevator moving steadily up or down without skipping floors

Request Servicing → Elevator stopping at each floor where passengers want to get on or off

End of Disk Behavior → Elevator reversing direction when it reaches the top or bottom floor

Advantages Over Other Algorithms → Elevator avoiding unnecessary trips and long waits by following a predictable route

Diagram

Diagram

┌─────────────────────────────┐
│ Disk Tracks (0 to Max Track)│
├─────────────────────────────┤
│ ↑                           │
│ │  ●   ●     ●   ●          │
│ │  ↑→→→→→→→→→→→→→→→→→→→→→→ │
│ │                           │
│ │                           │
│ │                           │
│ │                           │
│ │                           │
│ ↓                           │
│ ←←←←←←←←←←←←←←←←←←←←←←←←←←← │
└─────────────────────────────┘

The diagram shows the disk arm moving up servicing requests, then reversing direction at the end and moving down, similar to an elevator's path.

Key Facts

SCAN Algorithm → A disk scheduling method where the arm moves in one direction servicing requests, then reverses at the disk's end.

Disk Arm Movement → The physical movement of the read/write head across disk tracks to access data.

Request Queue → The list of pending disk access requests waiting to be serviced.

Starvation → A situation where some requests never get serviced due to scheduling unfairness.

Elevator Algorithm → Another name for the SCAN algorithm, inspired by elevator movement.

Common Confusions

Believing SCAN always moves the arm to the closest request next.

Believing SCAN always moves the arm to the closest request next. SCAN moves the arm in one fixed direction servicing all requests along the way, not necessarily the closest next request.

Thinking SCAN skips requests if they are behind the current arm direction.

Thinking SCAN skips requests if they are behind the current arm direction. SCAN will service all requests but only when the arm reverses direction and passes their track.

Summary

SCAN moves the disk arm in one direction, servicing requests along the way, then reverses at the disk's end.

This method reduces waiting time and avoids unnecessary arm movement compared to simpler scheduling.

It works like an elevator, continuously sweeping back and forth to serve all requests fairly.