InnovationQ will be updated on Sunday, Jan. 21, from 9am - 11am ET. You may experience brief service interruptions during that time.
Browse Prior Art Database

Queuing Access Requests to Direct Access Storage Device

IP.com Disclosure Number: IPCOM000116011D
Original Publication Date: 1995-Jul-01
Included in the Prior Art Database: 2005-Mar-30
Document File: 4 page(s) / 187K

Publishing Venue


Related People

Butterworth, H: AUTHOR [+2]


When using layers of software to process Input/Output (I/O) requests for a device such as a disk a performance penalty is paid for making non-sequential accesses.

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

Queuing Access Requests to Direct Access Storage Device

      When using layers of software to process Input/Output (I/O)
requests for a device such as a disk a performance penalty is paid
for making non-sequential accesses.

      Sometimes it is not possible or may not be desirable to pass on
all incoming I/O requests to the layer below because some resource is
constrained.  In this case, the I/O requests which have arrived must
be queued.

      When I/O requests must be removed from the pool of queued
requests and sent to the layer below, it is more efficient in terms
of overall throughput to send them in order of increasing or
decreasing starting block number rather than the order in which they
arrived.  This reduces the proportion of time spent seeking to the
next request by the disk.

      This behavior is commonly known as elevator seeking.  Elevator
seeking may be bidirectional where the disk heads are made to follow
a roughly triangular seek pattern or unidirectional where they follow
a roughly saw tooth seek pattern.

      When the number of requests which must be queued is large, an
efficient algorithm is required to prevent the processing needed to
insert a request into or remove a request from the queue from
becoming unreasonable.  Ideally the amount of processing required to
insert or remove a queued I/O request should not be closely related
to the number of requests already queued.  Rather it should be fairly
constant even with large numbers of queued requests.

      The solution described here, for unidirectional elevator
seeking, has been developed for an AIX* environment where an I/O
request is a 'buf' struct and the starting block for the request is
the b_blkno.  Buf structs have two pointers av_forward and av_back
which may be used to point to other buf structs.  Buf structs also
have a b_work field which may be used as a pointer to a buf struct.
The sorting algorithm outlined below is designed specifically to sort
bufs into order according to their b_blknos.

      The bufs are stored in a tree structure which is like a linked
list, but each node can have up to three other nodes connected to it.
The nodes are linked in the forward direction only which means that
all searches must be done from the root node onwards.  Bufs can be
to or removed from the tree at any time provided there is never more
than one instance of either the add or the remove function running.

Concept - It is easiest to imagine the structure of the tree as a
series of layers.  The top layer is the current set of accesses, the
root node of the current layer is always the next access.  The other
layers are strung from the root node of the layer above (via its
b_work variable cast to a buf pointer) and each successive layer
represents the next set of accesses.

Queuing a buf - When one wants to queue a buf one simply decides if
it should be queued in the current set of accesses or in the next set
(or even the...