An analysis of schedules for performing multi-page requests

摘要

In this paper, we address the problem of efficiently reading a set of pages from a file which is kept on some cylinders of a magnetic disk. It is assumed that several pages can be read from disk in a single multi-page request without interruption by other requests. First, a simple algorithm is presented for computing a schedule how the required pages are read from disk. Then, the expected cost of the schedules is analyzed by using a pure analytical model. In addition to the disk geometry, the analysis takes into account the three major cost components (seek time, rotational delay and transfer time) which occur when pages are retrieved from magnetic disk. The derived cost function depends on two parameters: the number of required pages and the degree of clustering of the underlying file. The cost function demonstrates that significant performance improvements can be achieved by using multi-page requests when the required pages are read according to a well-computed schedule. In addition to the response time of a query exclusively performed in the system, we also examine the impact of multi-page requests on the average response time when multiple queries are concurrently performed at a time. Results of an experimental performance comparison demonstrate that the average response time can considerably be improved on a highly loaded system by several factors when multi-page requests are used in comparison to reading the required pages one at a time.