Dynamic Storage Allocation
Original Publication Date: 1978-Apr-01
Included in the Prior Art Database: 2005-Feb-20
The problem of positioning a set of records in a linear storage medium in such a way that the expected access time is minimized has been thoroughly studied when consecutive accesses are independent and the frequencies are all known prior to the placement of the first record. Tape is the prototypical linear storage medium but, when minimization of disk seek time is of interest, it is useful to view the cylinders as forming a linear store. It is sufficient to know the relative frequency of access to the individual records, and the optimal solution is obtained by placing the most frequently accessed record and then repetitively placing the next most frequently accessed record alternating between the position immediately to the left of those already placed and the position immediately to the right.