
Accession Number : AD0726215
Title : An Optimal Drum Scheduling Algorithm.
Descriptive Note : Technical rept.,
Corporate Author : STANFORD UNIV CALIF STANFORD ELECTRONICS LABS
Personal Author(s) : Fuller,Samuel H.
Report Date : APR 1971
Pagination or Media Count : 67
Abstract : Suppose there is a set of N records which must be read or written from a drum, fixedhead 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)
Descriptors : (*MEMORY DEVICES, *SCHEDULING), ALGORITHMS, PERMUTATIONS, TOPOLOGY, THEOREMS, OPTIMIZATION
Subject Categories : Operations Research
Computer Hardware
Recording and Playback Devices
Distribution Statement : APPROVED FOR PUBLIC RELEASE