Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
2002-01-25
2004-01-20
Sparks, Donald (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C711S111000, C711S151000, C711S158000, C711S167000, C710S006000, C710S039000, C710S040000, C710S310000
Reexamination Certificate
active
06681289
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to command queue ordering in a direct access storage device (DASD), and more particularly, relates to a method and apparatus for efficiently sorting DASD queued commands with unknown rotational latency.
DESCRIPTION OF THE RELATED ART
In random access storage devices, such as hard disk drives, when more there are 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, many known 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. This calculation has two parts, the time to perform the seek and settle operation from the current cylinder to the target cylinder and the latency between this point and when the starting sector for the command is reached. The SATF algorithm depends on accurate estimates of this access time. If the estimate is too low, the actuator may settle on track after the desired sector has already passed rotationally. This is called a miss. A miss adds one full revolution to the access time, degrading performance. If the access time estimate is too high, the optimal command candidate is not chosen for execution.
One problem with the typical SATF algorithm is that each command in the queue is classified in a binary manner. Desirable candidates are determined to be either reachable or unreachable in a given number of revolutions. Unfortunately, due to the large number of external factors affecting actual seek performance binary decisions are inadequate.
An improved method and apparatus for hard disk drive command queue ordering utilizes the SATF algorithm together with a probability of success calculation. This improved algorithm chooses the command that has the shortest access time as well as an acceptable probability of success. The probability of success is the probability that the command will be executed in the expected amount of time without one or more missed revolutions.
A problem with the known algorithms results when the current command does not complete as expected. The SATF algorithm assumes that the anticipated ending sector of the current command can be accurately determined. However, the current command can stop at a location different from that expected. For example, the executing command may be aborted early causing the actual starting point to be earlier than expected, or the executing command may be several servo IDs (SIDs) longer than assumed with the actual starting point to be later than expected. Presently if the previous process does not complete as expected the process will try to execute this command again. Unfortunately, this means that whenever the current process terminates abnormally there is a potential for performance degradation caused by adding an additional revolution of time due to a miss or executing a non-optimal candidate command choice which also slows performance.
A need exists for an improved method and apparatus for command queue ordering DASD queued commands with unknown rotational latency.
SUMMARY OF THE INVENTION
A principal object of the present invention is to provide a method and apparatus for efficiently sorting queued commands with unknown rotational latency in a direct access storage device (DASD). Other important objects of the present invention are to provide such method and apparatus for efficiently sorting DASD queued commands substantially without negative effect and that overcome many of the disadvantages of prior art arrangements.
In brief, a method and apparatus are provided for efficiently sorting queued commands with unknown rotational latency in a direct access storage device (DASD). The sequential steps start with executing a current command and simultaneously with executing the current command for each command in a DASD command queue, an initial expected access time including a probability of success calculation is calculated and stored together with a plurality of predefined variables in a respective row in a miss table. Utilizing the stored miss table, a best candidate command list for a plurality of different starting locations for a next command to be executed is calculated. When an actual starting location for the next command to be executed is identified, a command in a DASD command queue is selected utilizing the best candidate command list, based upon the actual starting location.
In accordance with features of the invention, the initial expected access time is calculated for each command in the DASD command queue using a target starting location based upon the currently executing command. The best candidate command list for a plurality of different starting locations is calculated by first sorting the stored miss table rows by increasing expected access time (EAT) values. In the sorted miss table, a first row has a lowest EAT value and a second row has the second lowest EAT value. A last row of the sorted miss table stores the currently executing command. The best candidate command list for the plurality of different starting locations is calculated by sequentially incrementing a miss time value from the target starting location value by a predefined unit of time. The expected access time (EAT) and the stored predefined variables in the first row of the sorted miss table are updated and in the second row a potential variable is adjusted. The updated EAT in the first row is compared to the adjusted potential variable in the second row. When the updated EAT in the first row is not greater than the potential variable in the second row in the sorted miss table, then the miss time value is incremented by the predefined unit of time. When the updated EAT in the first row is greater than the potential variable in the second row in the sorted miss table, then the EAT and the stored predefined variables in the second row of the sorted miss table are updated. Then the miss table rows are again sorted by increasing expected access time values and a new entry is stored in the best candidate command list. Then the miss time value is incremented by the predefined unit of time and the sequential steps continue until the currently executing command is stored in the first row of the sorted miss table.
REFERENCES:
patent: 6145052 (2000-11-01), Howe et al.
patent: 6571298 (2003-05-01), Megiddo
patent: 6574676 (2003-06-01), Megiddo
patent: 6604178 (2003-08-01), Hall
Espeseth Adam Michael
Hall David Robison
Vasoli Maile Matsui
Dinh Ngoc V
Pennington Joan
Sparks Donald
LandOfFree
System and method for efficiently sorting DASD queued... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for efficiently sorting DASD queued..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for efficiently sorting DASD queued... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3219577