Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
2000-08-14
2004-04-20
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
Reexamination Certificate
active
06725327
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to the data processing field, and more particularly, relates to a space-efficient access time algorithm, method and apparatus for hard disk drive command queue ordering.
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, 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.
A need exists for an improved method and apparatus for hard disk drive command queue ordering. To implement a SATF algorithm, the latency between the current position and the target position must be analyzed. The command having the shortest access time and an acceptable probability of success is chosen by the algorithm. 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. Using the probability of success to calculate an expected value is preferred.
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 that efficiently and effectively facilitates hard disk drive command queue ordering while enabling memory space efficiency and while maintaining expected access time accuracy; 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. For each command in the hard disk drive command queue, an expected access time is calculated including a probability of success calculation. A command in the hard disk drive command queue having a minimum calculated expected access time is identified. Then the identified command having a minimum calculated expected access time is executed.
In accordance with features of the invention, for an estimated seek time of less than a time for one full revolution, a probability of a miss multiplied by a time of one extra revolution is calculated and the result is added to an estimated seek time to provide the expected access time. For an estimated seek time of greater than a time for one full revolution, a probability of a make multiplied by a time of one extra revolution is calculated and the result is subtracted from an estimated seek time to provide the expected access time.
REFERENCES:
patent: 6571298 (2003-05-01), Megiddo
The local disk controller. Gilbert E. Houtekamer, ACM SIGMETRICS Performance Evaluation Review , Proceedings of the 198 ACM SIGMETRICS conference on Measurement and modeling of computer systems. Aug. 1985, vol. 13 Iss 2.
Espeseth Adam Michael
Hall David Robison
Mosser James Joseph
Smith Steven Glenn
Anderson Matthew D.
Kim Matthew
Pennington Joan
LandOfFree
Space-efficient expected access time algorithm for hard disk... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Space-efficient expected access time algorithm for hard disk..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Space-efficient expected access time algorithm for hard disk... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3209554