SCAN scheduling and N step-SCAN scheduling algorithms
SCAN Scheduling:
To overcome the high variance in response time in the SSTF method, this method is devised. It operates similar to SSTF scheduling except that initially the request with shortest seek distance is preferred, that direction is the preferred direction.
- If the preferred direction is outward, the SCAN strategy chooses the shortest seek distance in the outward direction.
- It does not change direction until it reaches the outermost cylinder or until there are no further requests pending in the preferred direction.
- It can also be called as elevator algorithm, since an elevator normally continues in one direction until there are no more requests pending and then it reverses direction.
- SCAN is the most important and basis for the disk scheduling strategies actually implemented.
To overcome the high variance in response time in the above mentioned method, this method is devised. It operates similar to SSTF scheduling except that initially the request with shortest seek distance is preferred, that direction is the preferred direction.
- SCAN is also like SSTF has high throughput and less mean response time, in addition to that it provides a lower variance. It is also a cylinder-oriented strategy.
- Due to the oscillating motion of read-write heads in this method, the midrange tracks are visited more often compared to outer tracks.
The figure above depicts the operation of this scheduling.
N-Step SCAN:
Disk arm sweeps back and forth as in SCAN, but all requests that arrive during a sweep in one direction are batched and reordered for optimal service during the return sweep.
- It is a slightly modified method compared to basic SCAN.
- Here, the disk arm moves back and forth as in SCAN except that it services only those requests waiting when a particular sweep begins.
- Requests arriving during sweep are grouped together and ordered for optimum service during the return sweep. On each sweep, the first N requests are serviced.
- It avoid the possibility of indefinite postponement, if a large requests arrive for the current cylinder.
- It provides high throughput, less mean response time and lower variance of response times than all the methods mentioned above.
Figure above depicts this mechanisms.
Want to know about other scheduling algorithms? Visit again...
