Information Technology Reference
In-Depth Information
2
2
3
4
4
4
3
3
2
1
1
1
6
6
6
5
7
7
7
5
5
(a) SCAN
(b) CSCAN
(c) R-CSCAN
Figure12.4: Elevator-based scheduling algorithms: (a) SCAN, (b) CSCAN, and (c) R-CSCAN.
Elevator, SCAN, and CSCAN. Elevator-based algorithms like SCAN and
CSCAN have good performance and also ensure fairness in that no request is
forced to wait for an inordinately long time. The basic approach is similar to
how an elevator works: when an elevator is going up, it keeps going up until
all pending requests to go to floors above it have been satisified; then, when an
elevator is going down, it keeps going down until all pending requests to go to
floors below it have been satisfied.
The SCAN scheduler works in the same way. The disk arm first sweeps from
Definition: SCAN
the inner to the outer tracks, servicing all requests that are between the arm's
current position and the outer edge of the disk. Then, the arm sweeps from
the outer to the inner tracks. Then the process is repeated. Figure 12.4-(a)
illustrates the SCAN algorithm travelling from outer-to-inner tracks to service
four pending requests and then travelling from inner-to-outer tracks to service
three additional requests.
The CSCAN (circular SCAN) scheduler is a slight variation on SCAN in
Definition: CSCAN
which the disk only services requests when the head is traveling in one direction
(e.g., from inner tracks to outer ones); when the last request in the direction
of travel is reached, the disk immediately seeks to where it started (e.g., the
most inner track or the most inner track with a pending request) and services
pending requests by moving the head in the same direction as the original pass
(e.g., from inner tracks to outer ones again.) Figure 12.4-(b) illustrates the
CSCAN algorithm travelling from outer-to-inner tracks to service four pending
