Electrical computers and digital data processing systems: input/ – Input/output data processing – Input/output access regulation
Reexamination Certificate
1999-03-31
2001-08-07
Nguyen, Hiep T. (Department: 2185)
Electrical computers and digital data processing systems: input/
Input/output data processing
Input/output access regulation
C710S005000, C710S039000, C711S112000, C360S072200
Reexamination Certificate
active
06272565
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a method, system, and program for reordering a queue of input/output commands directed toward a storage medium in a manner that maximizes system throughput.
2. Description of the Related Art
A hard disk drive receives input/output (I/O) commands with respect to locations on the disk drive. The I/O commands may be received at a rate faster than they can be executed with respect to the disk drive storage medium. In such case, the I/O commands are queued.
FIG. 1
illustrates the arrangement of a recording surface of a disk drive
2
divided into concentric circular “tracks” on the disk surface. If there are multiple disks, then the vertical alignment of the tracks, on the disks aligned in parallel, together comprise a cylinder. The outer cylinder is shown as reference
4
. Each cylinder is further divided into user data sectors
6
a-h
and prerecorded servo sectors
8
a-h
. A logical block address (“LBA”) is used to address a specific location within the disk stack and is mapped by the disk drive control electronics to a cylinder or track, head number indicating a particular head in a multi-disk system, and sector.
The positioning time or total access time for an individual command can be broken-up into sequential phases, referred to as seek time and latency time. Seek time is the timer period for the servo system to position the actuator from the current head and cylinder position to the new target head and cylinder position. The latency time represents the remaining time, after seek completes, to position the head over the target sector. A “rotational time” involves the time to rotate the sector from the source or current sector location to position the target sector under the transducer read/write head. The latency time is the combination of the seek time and rotational time required to position the read/write head over the sector location that is the subject of the I/O operation.
Thus, the total access time is determined by two time movement operations, the seek time for radial positioning and the rotational access time for circumferential positioning the head over the target sector. To insure that the read/write head is positioned over the target sector at the completion of the radial and rotational positioning operations, the seek time must always be less than the rotational time. Further details of how to calculate the seek and rotational times are described in U.S. Pat. No. 5,729,718, entitled “System for Determining Lead Time Latency as Function of Head Switch, Seek, and Rotational Latencies and Utilizing Embedded Disk Drive Controller for Command Queue Reordering,” which patent is incorporated herein by reference in its entirety.
Queued I/O commands do not have to be executed in the order they are received. Thus, the queued I/O commands may be reordered to maximize throughput. One reordering method, termed “Shortest Seek Time First,” or SSTF, reorders commands such that the command with the shortest seek time with respect to the command being executed is executed next. This reordering method only considers the time to move the head in a radial position between tracks. The problem with queueing methods that consider only the seek time or time to change the radial position is that they do not consider rotational delay to spin the disk to a different circumferential position.
Current rotational position ordering (RPO) methods reorder the queue to minimize the combination of seek time and rotational time, or optimize total throughput. U.S. Pat. Nos. 5,729,718 and 5,548,795, entitled “Method for Determining Command Execution Dependencies Within Command Queue Reordering Process,” which patents are incorporated herein by reference in their entirety, describe an RPO method for queuing commands that considers both seek and rotational delay times. Each queued command includes a field to store the results in calculating the delay time with respect to a reference command, which is the command currently being executed at the head of the queue. This latency time is calculated for each queued command with respect to the command at the head of the queue, or n calculations in a queue of n I/O commands. The command having the shortest latency time is promoted to the position immediately following the head of the queue. This algorithm is then repeated and latency times are calculated with respect to the just promoted I/O command. Thus, with current RPO reordering techniques, calculations in the order of n
2
are performed to reorder the entire queue.
One problem with current RPO reordering techniques is the processor overhead needed to reorder the entire queue. Queue reordering operations can have significant affects on performance as the processing of I/O commands is delayed until the queue is reordered. Increases in the track storage capacity and number of addressable locations on the tracks results in likewise increases in the number of I/O commands directed to the storage device. It would be desirable to increase the queue length to accommodate the increase in I/O traffic associated with larger track capacity. However, one limitation on increasing the queue length is the time needed to reorder the queue. As the number of queued requests increases, the time to reorder the queue increases with the power of two. This increase in queue length in turn requires a substantial increase in the processing overhead to reorder the queue. Thus, one limitation on expanding the queue size in disk drives is the substantial increase in processor overhead needed to sort the longer queues.
Thus, there is a need in the art for an improved methodology for reordering I/O queues to accommodate increases in track capacity and the corresponding increase in queue length.
SUMMARY OF THE PREFERRED EMBODIMENTS
To overcome the limitations in the prior art described above, preferred embodiments disclose a system, method, and program for selecting an input/output (I/O) command in a queue of I/O commands. Each I/O command operates within a range of addressable locations on a storage medium. Each addressable location is defined according to a sector number and track number. The program makes use of a plurality of buckets, wherein each bucket represents a range of consecutive sector numbers. Each queued I/O command is associated with a bucket such that a sector number of an addressable location in which an I/O command operates is within the range of sectors comprising the associated bucket. A reference position is determined. A selection routine is then executed to select an I/O command. The selection routine selects a bucket including at least one I/O command and selects an I/O command within the selected bucket. The routine then determines whether the selected I/O command meets a selection criteria. The routine indicates the selected I/O command as the I/O command to process. Another iteration of the selection routine is performed after determining that the selected I/O command does not meet the selection criteria.
In further embodiments, if the disk file is not in use, then the reference position may be determined as a current position of a head with respect to an addressable location of the storage medium. If an I/O command is being executed against the storage medium, then the reference position is determined with respect to an addressable location where the head will be located at the completion of the execution of the current I/O command.
In still further embodiments, determining whether the selected I/O command meets the selection criteria would include estimating a seek time and rotational time. The seek time is the time to move from a track of the determined reference position to the track of the selected I/O command. The rotational time is the time to move from a sector number of determined reference position to the sector number of the selected I/O command. The selection criteria selects an I/O command to maximize throughput.
In yet further embodiments, determining whether the selected I/O command meets the selection cr
International Business Machines - Corporation
Kim Hong
Konrad Raynes & Victor LLP
Nguyen Hiep T.
Victor David W.
LandOfFree
Method, system, and program for reordering a queue of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method, system, and program for reordering a queue of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method, system, and program for reordering a queue of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2457371