Method and apparatus for selecting enqueued data access operations for execution in a disk drive data storage device
View Patent ↗In accordance with one aspect of the present invention, a seek profile table used by a disk controller contains multiple profiles for seek operations, and is accessed by a separate index table containing, for each permutation of key parameters, an index to a corresponding profile. In operation, the estimated seek time for an enqueued data access operation is obtained by accessing the applicable index table entry, using the value of the index entry to determine the corresponding profile, and using the profile to estimate the access time. Preferably, a “time-based relocation expected access time” algorithm is used, in which a nominal seek time is established, and profile table entries express a probability that an operation with a given latency above the nominal seek time will complete within the latency period. The expected access time is the latency plus the product of this probability and the time cost of a miss, i.e., the time of a single disk revolution.
1. A rotating magnetic disk drive data storage device, comprising:
a disk drive base;
a rotatably mounted disk and spindle assembly, said disk and spindle assembly comprising at least one rigid disk for recording magnetically encoded data on at least one surface of said at least one rigid disk;
a movable actuator supporting at least one transducer head, said actuator positioning said at least one transducer head to access said magnetically encoded data on said at least one surface of said at least one rigid disk;
a controller for controlling the operation of said disk drive data storage device, said controller maintaining a queue of data access operations and selecting operations for execution from said queue according to an estimated access time of the respective operations, said controller accessing a seek profile table and an index table, said seek profile table containing a plurality of entries, each entry corresponding to a respective seek profile, and said index table containing a plurality of entries, each entry corresponding to a respective set of access operation parameter values and containing a value indexing an entry in said seek profile table corresponding to said respective set of access operation parameter values;
wherein said controller estimates said access time of a data access operation by: (a) accessing the index table entry corresponding to the respective set of access operation parameter values, (b) using the value of the index entry to determine the corresponding seek profile table entry, and (c) using the corresponding seek profile table entry to estimate the access time.
2. The rotating magnetic disk drive data storage device of claim 1 , wherein said moveable actuator supports a plurality of transducer heads, each head accessing magnetically encoded data on a respective surface of said at least one rigid disk, and wherein each said set of access operation parameter values includes a value corresponding to a transducer head for performing the corresponding data access operation.
3. The rotating magnetic disk drive data storage device of claim 1 , wherein each said set of access operation parameter values includes a value corresponding to a direction of actuator motion of a seek operation for the corresponding data access operation.
4. The rotating magnetic disk drive data storage device of claim 1 , wherein each said set of access operation parameter values includes a type of data access operation.
5. The rotating magnetic disk drive data storage device of claim 1 , wherein each said set of access operation parameter values includes a temperature of said rotating magnetic disk drive data storage device.
6. The rotating magnetic disk drive data storage device of claim 1 , wherein said controller dynamically updates values in said index table.
7. The rotating magnetic disk drive data storage device of claim 1 , wherein said controller estimates said access time by further (d) determining a seek distance and a required latency, (e) determining a nominal seek time corresponding to said seek distance, and (f) determining an excess seek time as a difference between said required latency and said nominal seek time, wherein said excess seek time is used when using the corresponding seek profile table entry to estimate the access time.
8. The rotating magnetic disk drive data storage device of claim 7 , wherein said controller estimates the access time according to a time-based relocation expected access time algorithm.
9. A method of operating a disk drive data storage device, comprising:
maintaining a queue of data access operations for execution;
for a plurality of data access operations on said queue, determining a respective estimated access time by:
(a) accessing a respective entry in an index table corresponding to a set of access operation parameter values of the corresponding data access operation on said queue, said index table containing a plurality of entries, each entry corresponding to a respective set of access operation parameter values and containing a value indexing an entry in a seek profile table, each ently in said seek profile table containing a respective seek profile;
(b) using the value of the index entry to determine the corresponding seek profile table entry, and
(c) using the corresponding seek profile table entry to estimate the access time of the corresponding data access operation; and selecting one of said plurality of data access operations on said queue for execution based on said estimated access time of the data access operation.
10. The method of operating a disk drive data storage device of claim 9 , wherein said disk drive includes a moveable actuator supporting a plurality of transducer heads, each head accessing magnetically encoded data on a respective disk surface of said disk drive, and wherein each said set of access operation parameter values includes a value corresponding to a transducer head for performing the corresponding data access operation.
11. The method of operating a disk drive data storage device of claim 9 , further comprising the step of dynamically updating values in said index table.
12. The method of operating a disk drive data storage device of claim 11 , wherein said step of dynamically updating values in said index table comprises:
(a) selecting sets of access operation parameter values for use in dynamic update of an expansion table;
(b) dynamically determining a respective seek profile in said expansion table for each respective set of access operation parameter values selected by said step of selecting sets of access operation parameter values;
(c) matching each dynamically determined seek profile in said expansion table with a corresponding seek profile in said seek profile table; and
(d) updating entries in said index table corresponding to each respective set of access operation parameter values selected by said step of selecting sets of access operation parameter values to index the respective corresponding seek profile in said seek profile table.
13. The method of operating a disk drive data storage device of claim 12 , wherein said step of selecting sets of access operation parameter values for dynamic update comprises selecting sets of access operation parameter values based on frequency of executed data access operations corresponding to the respective sets of access operation parameter values.
14. The method of operating a disk drive data storage device of claim 11 , wherein said step of dynamically updating values in said index table comprises dynamically determining respective seek profiles corresponding to selected sets of access operation parameter values by convergence of operationally collected data on each respective seek profile.
15. The method of operating a disk drive data storage device of claim 9 , wherein said step of, for a plurality of data access operations on said queue, determining a respective estimated access time, further comprises the steps of:
(d) determining a seek distance and a required latency;
(e) determining a nominal seek time corresponding to said seek distance; and
(f) determining an excess seek time as a difference between said required latency and said nominal seek time, wherein said excess seek time is used when performing said step of using the corresponding seek profile table entry to estimate the access time of the corresponding data access operation.
16. The method of operating a disk drive data storage device of claim 15 , wherein said step of using the corresponding seek profile table entry to estimate the access time estimates the access time according to a time-based relocation expected access time algorithm.
17. A control program product for a disk drive data storage device, comprising:
a plurality of processor-executable instructions recorded on signal-bearing media, wherein said instructions, when executed by a processor of said disk drive, cause the drive to perform the steps of:
maintaining a queue of data access operations for execution;
for a plurality of data access operations on said queue, determining a respective estimated access time by:
(a) accessing a respective entry in an index table corresponding to a set of access operation parameter values of the corresponding data access operation on said queue, said index table containing a plurality of entries, each entry corresponding to a respective set of access operation parameter values and containing a value indexing an entry in a seek profile table, each entry in said seek profile table containing a respective seek profile;
(b) using the value of the index entry to determine the corresponding seek profile table entry, and
(c) using the corresponding seek profile table entry to estimate the access time of the corresponding data access operation; and
selecting one of said plurality of data access operations on said queue for execution based on said estimated access time of the data access operation.