An Optimal Drum Scheduling Algorithm.
Abstract
Suppose there is a set of N records which must be read or written from a drum, fixed-head disk, or similar storage unit of a computing system. The records are of varying length and arbitrarily located on the surface of the drum. An algorithm is developed which will schedule the processing of these records so as to minimize the total amount of rotational latency (access time), taking into account the current position of the drum. This algorithm has the attractive property of exhibiting a computational complexity on the order of N/logN. The general approach taken by the algorithm is to consider the schedule for processing the records as a single cycle permutation over the set of records. It first finds a permutation that minimizes the total latency time, regardless of the number of disjoint cycles in the permutation. The algorithm then transforms the minimal latency time permutation into a single cycle permutation while increasing the latency time of the schedule as little as possible. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Apr 01, 1971
- Accession Number
- AD0726215
Entities
People
- Samuel H. Fuller
Organizations
- Stanford University