An efficient algorithm for allocating paged, drum-like storage

E. G. Coffman, Donald B. Johnson, Joseph Y.T. Leung

Research output: Contribution to journalArticlepeer-review

Abstract

Cody and Coffman have studied the problem of distributing a set of a equal-size records among the sectors of a drum-like storage device so as to minimize the average rotational latency cost. This paper is an extension of that work. We employ the same model but a different latency delay function. Motivated by the NP-completeness of the general problem and the fact that an arbitrary assignment can have an expected latency cost almost twice that of an optimal assignment, we propose and analyze a fast heuristic whose performance compares favorably with that of an optimal algorithm.

Original languageEnglish (US)
Pages (from-to)52-66
Number of pages15
JournalBIT
Volume18
Issue number1
DOIs
StatePublished - Mar 1978

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Graphics and Computer-Aided Design
  • Computational Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'An efficient algorithm for allocating paged, drum-like storage'. Together they form a unique fingerprint.

Cite this