Electrical computers and digital data processing systems: input/ – Input/output data processing – Input/output command process
Reexamination Certificate
2001-01-10
2003-10-28
Shin, Christopher (Department: 2182)
Electrical computers and digital data processing systems: input/
Input/output data processing
Input/output command process
C710S024000
Reexamination Certificate
active
06640258
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to the data processing field, and more particularly, relates to a method and apparatus for hard disk drive command queue ordering with a sort time reduction algorithm.
DESCRIPTION OF THE RELATED ART
In random access storage devices, such as hard disk drives, when there are more than one command to execute, the data to be accessed next is chosen from a list or a queue of outstanding commands. The hard disk drive includes firmware performing a scheduling algorithm to determine the optimal command execution order. In general, the goal of the scheduling algorithm is to minimize the average access time for its commands. Presently, hard disk drives use a Shortest-Access Time First (SATF) algorithm.
The conventional SATF algorithm works as follows: Given a set of commands in a queue, a command is chosen that can be started or accessed first. Various implementations of SATF algorithms exist, but all operate by calculating a score for every command in the queue and choosing the command with the best score for execution.
A significant problem with conventional SATF algorithms exists in workloads that have deep queues, short seeks, and short command latencies. Typically in such workloads there is not enough processor bandwidth to analyze the entire queue before the currently executing command is completed. Command queue ordering algorithms contain CPU intensive operations that take a significant amount of time to complete. If the next command is not selected by the sorting algorithm before the currently executing command is completed, performance is degraded. As a result deeper queues can actually result in slower performance as compared to smaller queues under these workloads.
This problem will become more apparent in the industry as command latencies decrease and queue depths increase. With the introduction of higher speed drives and the demand for higher supported queue depths, this problem is foreseen as a significant hurdle. One approach may be to increase the processing capabilities of the disk drive. This may include increasing the clock speed of an onboard CPU or adding other processing hardware. However, this approach adds significant cost to the disk drive.
A need exists for an improved method and apparatus for hard disk drive command queue ordering.
SUMMARY OF THE INVENTION
A principal object of the present invention is to provide an improved method and apparatus for hard disk drive command queue ordering. Other important objects of the present invention are to provide such method and apparatus for hard disk drive command queue ordering including a sort time reduction algorithm that efficiently and effectively facilitates hard disk drive command queue ordering; to provide such method and apparatus for hard disk drive command queue ordering substantially without negative effect and that overcome many of the disadvantages of prior art arrangements.
In brief, a method and apparatus are provided for hard disk drive command queue ordering. A command received from a host is placed in a rotational order command list. A fraction of the rotational order command list is analyzed. Commands are analyzed with a maximum selection probability.
In accordance with features of the invention, a maximum analysis time before the currently executing command is completed is determined. The total analysis time cannot exceed the maximum analysis time. The fraction of the rotational order command list is analyzed in a first pass. A skip-sort interval is selected based upon the maximum analysis time and a current queue depth of the rotational order command list. In a second pass, the number of commands analyzed corresponds with the number of commands that can be analyzed in the remaining available processing time.
REFERENCES:
patent: 4972364 (1990-11-01), Barrett et al.
patent: 5418971 (1995-05-01), Carlson
patent: 5426736 (1995-06-01), Guineau, III
patent: 5548795 (1996-08-01), Au
patent: 5603063 (1997-02-01), Au
patent: 5664143 (1997-09-01), Olbrich
patent: 5680539 (1997-10-01), Jones
patent: 5991825 (1999-11-01), Ng
patent: 6141707 (2000-10-01), Halligan et al.
patent: 6272565 (2001-08-01), Lamberts
patent: 6301639 (2001-10-01), Cleavinger et al.
patent: 6496877 (2002-12-01), Greenberg et al.
Espeseth Adam Michael
Hall David Robison
Hitachi Global Storage Technologies - Netherlands B.V.
Pennington Joan
Shin Christopher
LandOfFree
Method and apparatus for command queue ordering with a sort... 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 and apparatus for command queue ordering with a sort..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for command queue ordering with a sort... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3123479