Browse Prior Art Database

Cylinder Elevator Algorithm

IP.com Disclosure Number: IPCOM000121920D
Original Publication Date: 1991-Oct-01
Included in the Prior Art Database: 2005-Apr-04
Document File: 5 page(s) / 129K

Publishing Venue

IBM

Related People

Arndt, RL: AUTHOR [+2]

Abstract

Disclosed is an elevator algorithm for processing DASD (Direct Access Storage Device) I/O requests that minimizes expensive cylinder head switches, while providing fairness to all I/O requests.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 63% of the total text.

Cylinder Elevator Algorithm

      Disclosed is an elevator algorithm for processing DASD
(Direct Access Storage Device) I/O requests that minimizes expensive
cylinder head switches, while providing fairness to all I/O requests.

      The analogy of an elevator is used to describe the typical
algorithm used for seek optimization when processing I/O requests for
a DASD.  The idea is that the physical arm, or actuator of the DASD,
represents an elevator as it moves "up" and "down" across LBAs
(Logical Block Addresses) of the physical disk platter.  Just as an
elevator lets off passengers depending on the current "floor" and
destination of its passengers, so does this algorithm process
requests depending on the physical sweep of the arm.  The objective
is to process requests in an order that would keep the arm moving in
the same direction, therefore avoiding unnecessary and time-consuming
seeks.

      The disclosed algorithm goes one step further in minimizing
seek delay.  With the typical bidirectional elevator algorithm
(processes requests on both the up and down sweep of the arm as
opposed to just the up sweep), due to the mechanics of the DASD, the
"down" sweep is sometimes worse than if the requests had been
processed in random order.  The reason is that if a request spans 2
cylinders, the cylinder boundary will be crossed 3 times.  Once to
locate the starting cylinder, once in the process of servicing the
request, and then once to process the next "dow...