Dynamic Placement of Records in Linear Storage
A. C. McKellar, Carmen Wong · Journal of the ACM · 1978
This paper considers allocation of space in a hnear storage medium when space must be allocated dynamically as customers arrive A heuristic is proposed for this problem and for a simple model of the resultmg reference sequence, we show that the average distance between consecutive references is asymptotically 7n/30, where n is the size of the storage For optimal static placement where one waits for all arrivals before any space allocation, the average distance is shown to be asymptotically 7n/30 For random placement, the average distance is asymptotically n/3 Thus, the heuristic is asymptotically optimal in a strong sense For reasonable values of n, we demonstrate that the heuristic is nearly as good as optimal static placement and much better than random placement KEY WORDS AND PHRASES minimization of disk seek time, minidisks, linear store, dynamic allocation of storage space, concrete complexity, optimal algorithms, asymptotically optimal algorithms, analysts of algorithms, heuristics CR CATEGORIES 4 35, 5 25 Notational ConventionsWe must deal with a set of n users who arrive at n distinct points in time, and who are General permission to make fair use in teachmg or research of all or part of this material is granted to individual readers and to nonprofit libraries acting for them provided that ACM's copyright notice ts given and that reference is made to the publication, to its date of issue, and to the fact that reprinting privileges were granted by