Electrical computers and digital data processing systems: input/ – Input/output data processing – Input/output command process
Reexamination Certificate
2002-04-12
2004-11-30
Gaffin, Jeffrey (Department: 2182)
Electrical computers and digital data processing systems: input/
Input/output data processing
Input/output command process
C710S005000, C710S040000, C710S041000, C710S058000, C710S244000, C711S151000, C711S158000, C711S167000, C711S168000, C711S169000
Reexamination Certificate
active
06826630
ABSTRACT:
FIELD OF THE INVENTION
This application relates generally to command optimization in a data storage device and more particularly to effectively prioritizing read and/or write commands in a disc drive.
BACKGROUND OF THE INVENTION
Many data storage devices use microprocessors to execute commands. Typically, a data storage device can accommodate multiple microprocessor commands. For example, the microprocessor in a disc drive device may receive multiple commands to read or write data from or to media within the disc drive. When commands are received in a data storage device faster than the commands can be executed, the commands are typically buffered to await their turn for processing by the microprocessor in the data storage device. Additionally, data associated with a write command is typically held in a cache memory until the associated command is processed.
Performance in a data storage device can often be improved by executing the received commands in an order different from the order they were originally received. Ordering the commands in this manner is called command reordering. Command reordering allows for a more efficient use of the microprocessor as well as a more efficient use of the hardware being controlled by the microprocessor. For instance, a disc drive may receive commands to read and/or write data at a variety of locations on the hard discs within the disc drive. Ideally, these commands would be processed in a manner that would that would optimize user perceived performance.
There are a number of ways to order the commands in a command queue. Traditionally, disc drives have employed algorithms to sort commands in an order that minimizes seek time between the various commands. The seek time is the time required for the read/write element to radially move across or traverse cylinders between a current cylinder over which the read/write element is positioned and a target cylinder to be addressed in response to a particular command. However, seek time is only one of two components of the true access time of a command. Another component is the rotational latency time or the amount of time the disc drive spends waiting for the appropriate data to rotate under the read/write element. The rotational latency time may be a significant part of the total access time. Often, it is the dominant component of the total access time for relatively short seeks. As such, many current command ordering algorithms are optimized to reduce rotational latency, either alone or in conjunction with some form of seek time minimization.
One significant drawback associated with prior command ordering algorithms is that they do not give preference to pending commands in the reordering process. When a pending command is not given preference over non-pending commands, performance of the data storage device suffers. As used herein, a pending command is a command for which the command has not returned status. For example, a read command is pending until the host computer receives the data and status from the disc drive. As another example, a write command is pending until the disc drive notifies the host that the disc drivereceives the data and sends completion status to the host. Hence, non-pending commands are those that the host computer perceives as complete, but are not completed in the data storage device.
An example of a non-pending command in the disc drive is a ‘writeback’ command. Frequently, when a disc drive receives a write command, the associated data is not immediately written to the disc, but rather it is cached until the write becomes favorable to commit to the media. When the write data is cached and completion status is sent to the host, the write command becomes a writeback command. Writeback commands are not pending because the host computer has been given notification that the associated data has been received by the disc drive. In other words, from the host computer's perspective, the write command has been completed; however the disc drive still must execute the writeback command while it is cached.
As noted, traditional reordering algorithms do not give preference to pending commands in the reordering process. That is, these algorithms give the same priority to the pending command(s) as to the non-pending commands. Often the number of buffered non-pending commands exceeds the number of pending commands and the non-pending commands become more favorable to commit to the media. As a result, a pending command, for which the host computer requires prompt processing by the data storage device, may be delayed for a substantial amount of time while non-pending commands are processed. When pending commands are delayed, performance is reduced from the host computer's perspective. In particular, when the processing of pending commands is delayed, a computer user may perceive a lower level of data through-put between the host computer and the disc drive than if the pending commands are not delayed.
There is strong motivation in the industry to improve all aspects of performance, including through-put. Accordingly, there is a continual need for improvements in the art whereby pending commands and non-pending commands are executed in an efficient order while giving preference to pending commands, thereby reducing latency and improving performance.
SUMMARY OF THE INVENTION
Embodiments of the present invention minimize disc access latency using a unique system and method for ordering commands. More particularly, embodiments involve giving preference to pending commands in the priority queue. Still more particularly, embodiments involve identifying a pending command and processing other commands enroute to the pending command only if such processing will not delay the execution of the pending command.
An embodiment includes a method of prioritizing a plurality of commands involving storing a plurality of command nodes in memory, identifying a pending command node in the plurality of command nodes, and scheduling the pending command node for processing. More particularly, the method may employ steps of identifying intermediate command nodes in the plurality of command nodes that can be processed in addition to the pending command node within a predetermined amount of time and scheduling the intermediate command nodes before the pending command node.
The step of identifying intermediate command nodes may involve storing the plurality of command nodes in a first queue, and for each of the plurality of command nodes, determining an associated required processing time from a last scheduled command node. The method may further include sorting the plurality of command nodes according to their associated required processing times, selecting the one or more command nodes having an aggregated processing time which, when added to the processing time of the pending command, is less than the predetermined processing time.
These and various other features as well as advantages that characterize the present invention will be apparent from a reading of the following detailed description and a review of the associated drawings.
REFERENCES:
patent: 4394733 (1983-07-01), Swenson
patent: 5603063 (1997-02-01), Au
patent: 5644786 (1997-07-01), Gallagher et al.
patent: 5664143 (1997-09-01), Olbrich
patent: 5838940 (1998-11-01), Savkar et al.
patent: 5991825 (1999-11-01), Ng
patent: 6170042 (2001-01-01), Gaertner et al.
patent: 6571298 (2003-05-01), Megiddo
patent: 6574676 (2003-06-01), Megiddo
patent: 2002/0002655 (2002-01-01), Hoskins
patent: 0354931 (1996-04-01), None
Coker Kenny Troy
Cornaby Stephen R.
Hertz Mark David
Olds Edwin Scott
Nguyen Tanh Q.
Seagate Technology LLC
LandOfFree
Prioritizing commands in a data storage device does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Prioritizing commands in a data storage device, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Prioritizing commands in a data storage device will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3286216