A continuum of disk scheduling algorithms

Reviewer: Samuel T. Chanson

The authors presented a disk scheduling algorithm, V(R), that services requests according to increasing order of the effective distance of the requests from the read/write head. The effective distance is defined to be the number of cylinders (physical distance) if the request is in the same direction as the current scan direction. The effective distance in the opposite direction is the physical distance plus R * (total number of cylinders on the disk). Thus, when R = 0, the algorithm becomes the Shortest Seek Time First (SSTF); when R = 1, it is the SCAN algorithm. Intermediate values of R essentially define a scan window of size R * (total number of cylinders on the disk), outside of which SSTF is invoked. With performance taken to be a linear combination of the mean (&mgr;) and standard deviation (&sgr;) of the wait time, the authors' simulation results show the algorithm is uniformly superior to both SSTF and SCAN for intermediate values of R. The algorithm has been implemented on a small UNIX system, and measurement results support the simulation results. The proposed algorithm is intuitively simple and fairly easy to implement. Depending on the importance one places on &mgr; or &sgr;, one can select a value of R to reflect that in the scheduling algorithm. Nevertheless, there is overhead associated with running this algorithm over both SCAN and SSTF. Thus, each must decide whether it is worthwhile to implement this algorithm. The paper is well written and very easy to read.