An Optimal Drum Scheduling Algorithm.
STANFORD UNIV CALIF STANFORD ELECTRONICS LABS
Pagination or Media Count:
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 NlogN. 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
- Operations Research
- Computer Hardware
- Recording and Playback Devices