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, 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)

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