Browse Prior Art Database

RECORD ALLOCATION FOR MINIMIZING EXPECTED SEEK DELAY TIHE

IP.com Disclosure Number: IPCOM000128159D
Original Publication Date: 1979-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 18 page(s) / 39K

Publishing Venue

Software Patent Institute

Related People

U.I. Gupta: AUTHOR [+7]

Abstract

Given a set of variable length records and their access probabilities, we address the problem of allocating these records on a linear storage device so as to.minimize the expected seek time. A partial characterization of the optimal arrangement is given and the general problem of finding an optimal solution is shown to be NP-hard. Next; two heuristics are considered and performance bounds are derived for them. Although these bounds are not . very encouraging, both heuristics are found to perform well'in practice.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 14% of the total text.

Page 1 of 18

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

RECORD ALLOCATION FOR MINIMIZING EXPECTED SEEK DELAY TIHE*

U.I. Gupta , D.T. Lee ' J. Y-T. Leung J.W. Pruitt and C.K. Wong Department of Electrical Engineering and Computer Science Northwestern University No. 79-08-FC-Oit 0 0062

August, 1979

This research was supported in part by the National Science Foundation under Grant MCS-79- 04898-

t Department of Electrical Engineering and Computer Science, Northwestern University, Evanston, Illinois 60201.

tt Bell Laboratories, Naperville, Illinois 60540.

ttt Computer Sciences Department, IBM Thomas J. Watson Research Center, Yorktown Heights, New York 10598.

Abstract

Given a set of variable length records and their access probabilities, we address the problem of allocating these records on a linear storage device so as to.minimize the expected seek time. A partial characterization of the optimal arrangement is given and the general problem of finding an optimal solution is shown to be NP-hard. Next; two heuristics are considered and performance bounds are derived for them. Although these bounds are not . very encouraging, both heuristics are found to perform well'in practice.

Key Words and Phrases,: storage allocation, record assignment on secondary storage, expected seek delay time, computational complexity, NP-complete, approximation algorithm, worst-case analysis.

1. Introduction

We consider the problem of allocating a set of records on an auxiliary storage device so as to minimize the average seek delay time. The records are represented by the access probabilities (Pj,...,Plj and the correspond- ing lengths (t, The problem is formulated under the assumption that record requests.are served first-in-first-out (FIFO) and that consecutive accesses are serially independent. Storage devices applicable to our analyses include magnetic disks and tapes.

An allocation or arrangement of the records is a permutation of the indices 1 to n and is denoted by S = (s I '...'s n ), where s i is the index of the record assigned to the ith position from the left. The expected seek cost C(S) of a record access (for all requests beyond the first)

may be written as

Northwestern University Page 1 Dec 31, 1979

Page 2 of 18

RECORD ALLOCATION FOR MINIMIZING EXPECTED SEEK DELAY TIHE

(Equation Omitted)

where d(ij) is the seek delay incurred in accessing the record at pos-ition j given that the record at position i was last accessed.

Consider the problem of allocating a set of records to a magnetic tape. The length of a record represents units of distance the record occupies. The seek delay.function d T (i,j) is easily seen to be

(Equation Omitted)

for

(Equation Omitted)

Substituting (2) into (1) and simplifying, we derive the expected seek cost function C T (S) to be

(Equation Omitted)

The derivation of the above formula is included in Appendix A.

If the storage device is a magnetic disk, the length of a record represents the number of tracks (or cy...