First Come First Served: This is the simplest algorithm but also the least efficient. Access requests are simply processed in the order in which they are received. Batches are irrelevant for this algorithm. Despite its inefficiency, this is the disk scheduling algorithm of choice for many modern systems because the fact that there is no overhead in maintaining an ordered list of access requests may more than offset the poor performance of the algorithm.
Shortest Seek Time First: In this algorithm, the next request to be serviced is chosen solely on the basis of what request will necessitate the smallest amount of read/write head travel. Because of this, the algorithm ignores batches--it doesn't care if the nearest request came in a nanosecond ago or 5 seconds (an eternity in computer time) ago. Although this algorithm often provides the highest throughput, it can lead to starvation. Requests that are far from the initial position of the read/write head may take a very long time to be processed, even if they arrived early. This is often reflected in the statistics by a high variance and standard deviation. This algorithm is ideally suited for environments that are not interactive or real-time where throughput is the most important concern.
SCAN: This algorithm is sometimes referred to as the 'elevator algorithm' because it processes requests in a way similar to the way an elevator picks up passengers. Requests are set up in batches according to the time they arrived. The read/write head starts with the request in the first batch that is the farthest in or out--let's take the example where the head moves to the request that is farthest from the center. It then moves in, servicing all requests in the first batch in the order that it comes to them. When it arrives at the innermost request in that batch, it processes the next batch, moving from the innermost to the outermost request. It continues like this, alternating inward and outward sweeps. This algorithm is quite efficient and eliminates most of the bias against distant tracks found in Shortest Seek Time First. This algorithm often produces throughput almost as good as that of Shortest Seek Time First with considerably lower variance and standard deviation.
C-SCAN: C-SCAN is very similar to SCAN except that all of the sweeps where requests are being serviced are performed in the same direction. Like SCAN, it arranges requests in batches. The read/write head moves to the outermost request of the first batch and then moves in, processing requests in the order it reaches them. When it comes to the innermost request in the first batch, it moves immediately to the outermost request in the second batch and begins another inward sweep to process these requests. At first glance, this outward sweep without servicing any requests seems inefficient but there are two important things to remember. First, there is still a bias against certain disk areas in SCAN, although much less than in Shortest Seek Time First. For example, a request for data from the innermost track might be processed first on even numbered batches but last on odd numbered batches with SCAN. C-SCAN eliminates this bias and the inconsistency of response times that it produces by always servicing requests in the same direction. Second, the movement of the read write head between batches is very fast and thus costs little in terms of time. Since this program and paper and pencil simulations of disk scheduling tend to focus on the physical distance the read/write head travels, C-SCAN may often appear to be slightly worse in terms of throughput and variance than SCAN but, in real life, C-SCAN is the best algorithm for most situations.
|