SCAN is a disk scheduling algorithm that moves the disk arm from one end of the disk to the other, servicing requests along the way. It then reverses direction and moves back, again servicing requests as it goes. This back-and-forth motion is similar to how elevators work, which is why SCAN is also known as the Elevator Algorithm.
How SCAN Works
In SCAN disk scheduling, the disk head starts at one end of the disk and moves toward the other end, servicing requests along the way. When it reaches the other end, it reverses direction and moves back, again servicing requests in its path.
The algorithm follows these steps:
- The disk arm moves in a particular direction (towards higher or lower cylinder numbers)
- It services all requests in its path until it reaches the end of the disk
- At the end, it reverses direction and services requests that were missed during the forward journey
- This process continues, with the arm constantly moving back and forth across the disk
Example Calculation
Let's say we have a disk with 200 cylinders (0-199), and the head is currently at position 50, moving towards higher cylinder numbers. The request queue is:
| Request Sequence | 95 | 180 | 34 | 119 | 11 | 123 | 62 |
|---|
The SCAN algorithm will sort these requests based on the current head position and direction of movement:
| Requests Sorted by SCAN Algorithm (Initial Position: 50, Direction: Increasing) | ||||||
|---|---|---|---|---|---|---|
| 62 | 95 | 119 | 123 | 180 | 34 | 11 |
The head movements will be:
| Head Movement | |50-62| | |62-95| | |95-119| | |119-123| | |123-180| | |180-199| | |199-34| | |34-11| |
|---|---|---|---|---|---|---|---|---|
| Distance | 12 | 33 | 24 | 4 | 57 | 19 | 165 | 23 |
Total head movement = 12 + 33 + 24 + 4 + 57 + 19 + 165 + 23 = 337 cylinders
Note that the head moves to the end of the disk (cylinder 199) even if there are no requests there, as per the SCAN algorithm.
Advantages
- More efficient than FCFS, providing better throughput and average response time
- Reduces the "wild swing" of the disk arm compared to FCFS
- Provides a more predictable wait time than FCFS
- Offers good performance for systems with high I/O loads
Disadvantages
- Cylinders at the edges of the disk may receive unfair service
- Requests that arrive just after the head has passed may have to wait for a full scan cycle
- The algorithm always goes to the end of the disk, even if there are no requests in that direction
- May cause starvation for some requests in high-load systems