HP Labs Technical Reports

Hamiltonian Paths Algorithms for Disk Scheduling

Gallo, Giorgio; Malucelli, Federico; Marre, Martina

HPL-95-71

Keyword(s):

Abstract: The problem of optimally scheduling the read/write requests in a disk storage system is considered. A new class of algorithms for the disk scheduling problem is presented, and the relations between this problem and the shortest Hamiltonian path problem on asymmetric graphs are investigated. The problem of deriving realistic upper bounds for the disk utilization factor, one of the main performance measures for the disk scheduling algorithms, is also addressed.

Back to Index