Reading a Set of Disk Pages
Bernhard Seeger, Per-Åke Larson, Ron McFayden · 1993
The problem studied in this paper is as follows. Consider a file stored in contiguous space on disk. Given a list of pages to be retrieved from the file, what is the fastest way of retrieving them? It is assumed that adjacent pages on disk can be read with a single read request. The straightforward solution is to read the desired pages one by one. However, if two or more pages are located close to each other it may be faster to read them with a single read request, possibly even reading some intervening "empty" pages. It is shown that finding an optimal read schedule is equivalent to finding the shortest path in a certain graph. A very simple approximate algorithm is then introduced and (experimentally) shown to produce schedules that are close to optimal. The expected cost of schedules produced by this algorithm is derived. It is found that significant speed-up can be achieved by the simple mechanism of using additional buffer space and issuing "large reads" whenever it is advantageous to do so.