Prioritizing commands in a data storage device

A unique system and method for ordering commands may reduce disc access latency while giving preference to pending commands. The method and system involves giving preference to pending commands in a set of priority queues. The method and system involve identifying a pending command and processing other non-pending commands in route to the pending command if performance will not be penalized in doing so. The method and system include a list of command node references referring to a list of sorted command nodes that are to be scheduled for processing.

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 drive receives 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 throughput 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 throughput. 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.

DETAILED DESCRIPTION

Embodiments of the present invention are described with reference to a series of figures. Generally, embodiments of the present invention relate to systems and methods incorporated in a data storage device for receiving commands from an attached host computer, ordering the commands according to the methods described herein, and processing the commands in a determined order. The systems and methods utilize a number of queues and a list of command node references to receive and sort command nodes and synchronize the processing of commands with the disc rotation to optimize performance as perceived by the host.

A disc drive100constructed in accordance with a preferred embodiment of the present invention is shown inFIG. 1. The disc drive100includes a base102to which various components of the disc drive100are mounted. A top cover104, shown partially cut away, cooperates with the base102to form an internal, sealed environment for the disc drive in a conventional manner. The components include a spindle motor106that rotates one or more discs108at a constant high speed. Information is written to and read from tracks on the discs108through the use of an actuator assembly110, which rotates during a seek operation about a bearing shaft assembly112positioned adjacent the discs108. The actuator assembly110includes a plurality of actuator arms114that extend towards the discs108, with one or more flexures116extending from each of the actuator arms114. Mounted at the distal end of each of the flexures116is a head118that includes an air bearing slider enabling the head118to fly in close proximity above the corresponding surface of the associated disc108.

During a seek operation, the track position of the heads118is controlled through the use of a voice coil motor (VCM)124, which typically includes a coil126attached to the actuator assembly110, as well as one or more permanent magnets128that establish a magnetic field in which the coil126is immersed. The controlled application of current to the coil126causes magnetic interaction between the permanent magnets128and the coil126so that the coil126moves in accordance with the well-known Lorentz relationship. As the coil126moves, the actuator assembly110pivots about the bearing shaft assembly112, and the heads118are caused to move across the surfaces of the discs108. The heads118are positioned over one or more tracks120containing data and servo information for controlling the position of the heads118.

A flex assembly130provides the requisite electrical connection paths for the actuator assembly110while allowing pivotal movement of the actuator assembly110during operation. The flex assembly includes a printed circuit board132to which head wires (not shown) are connected; the head wires being routed along the actuator arms114and the flexures116to the heads118. The printed circuit board132typically includes circuitry for controlling the write currents applied to the heads118during a write operation and a preamplifier for amplifying read signals generated by the heads118during a read operation. The flex assembly terminates at a flex bracket134for communication through the base deck102to a disc drive printed circuit board (not shown) mounted to the bottom side of the disc drive100.

FIG. 2is a functional block diagram of the disc drive100ofFIG. 1, generally showing the main functional circuits that may be resident on a disc drive printed circuit board for controlling the operation of the disc drive100. As shown inFIG. 2, a host computer200is operably connected206to an interface application specific integrated circuit (interface)202. The interface202typically includes an associated buffer210that facilitates high speed data transfer between the host computer200and the disc drive100. The buffer210is a cache memory for caching commands and/or data to reduce disc access time. Data to be written to the disc drive100are passed from the host computer to the interface202and then to a read/write channel212, which encodes and serializes the data and provides the requisite write current signals to the heads118. To retrieve data that has been previously stored by the disc drive100, read signals are generated by the heads118and provided to the read/write channel212, which performs decoding and error detection and correction operations and outputs the retrieved data to the interface202for subsequent transfer to the host computer100. Such operations of the disc drive100are well known in the art and are discussed, for example, in U.S. Pat. No. 5,276,662 to Shaver et al.

As also shown inFIG. 2, a microprocessor216is operably connected220to the interface202. The microprocessor216provides top level communication and control for the disc drive100in conjunction with programming for the microprocessor216, which may be stored in a non-volatile microprocessor memory (MEM)224. The MEM224may include random access memory (RAM), read only memory (ROM) and other sources of resident memory for the microprocessor216. Additionally, the microprocessor216provides control signals for spindle control226and servo control228. The embodiment illustrated inFIG. 2includes a pending command prioritization module (PCPM)232being executed by the microprocessor216. The PCPM232is executable code initially resident in the MEM224and read and executed by the microprocessor216to perform unique operations to prioritize commands giving preference to pending commands.

In operation, the host computer200sends commands to the disc drive100instructing the disc drive100to read or write data from or to the discs108. A “write” command typically includes data to be written to the discs108along with a logical address indicating where the data is to be written and the number of bytes to write. A “read” command typically includes a logical address indicating the location or locations of data to be read, and a size indicator indicating the number of bytes to be read. The commands are received by the interface202, where they may be processed immediately or stored for later processing. The interface202may store the commands and their associated data and/or addresses so that the commands can be sorted, ordered, or prioritized in such a way that disc drive100performance may be improved. In one embodiment, the commands received from the host200are first sorted according to required processing time irrespective of command type. In this embodiment, the commands are subsequently prioritized based on command type with preference to pending commands.

As used herein, pending commands are commands that are recognized by the host computer200as not yet processed by the disc drive100. An example of a pending command is a pending read command. During a typical read operation, the host computer200sends a command to the disc drive100requesting the disc drive100to send the host200data that has been written to the disc drive100. The host200then waits for the disc drive to return the requested data. As such, until the requested data is delivered to the host200from the disc drive100, the command is pending. In contrast to a pending read command, a ‘writeback’ command is a command that is not considered a pending command. A writeback command is a command that is internal to the disc drive100that prompts the disc drive100to write previously cached data to the discs108. A writeback command is not pending from the host computer200perspective, because the host computer200considers the data associated with the writeback command to have already been written.

To improve performance, it is often desirable to process the host commands in an order different from the order in which they are received. As is described below, embodiments of the present invention include unique methods and systems of prioritizing commands depending on the type of command, and giving pending commands a higher priority than non-pending commands.

Methods of prioritizing commands with preference to pending commands to improve disc drive100performance are described in detail below with reference toFIGS. 4-7. In one embodiment (illustrated inFIG. 2), the microprocessor216executes software resident in the memory224to carry out the methods. In another embodiment, the methods are performed by the interface202. Many other embodiments not shown herein will be readily apparent to those skilled in the art to implement the various embodiments and features of the present invention. As will be understood, the various embodiments of the methods described herein may be implemented in any combination of hardware, software, or firmware.

In the various embodiments described herein, commands from the host computer200are represented in the disc drive100by “command nodes.” When a command is received by the disc drive100, a command node is created that has information (described in detail below) including references to other command node(s) for logically arranging command nodes in an order that optimizes disc drive100performance. Command nodes are maintained and ordered in one or more command node queues. Commands from the host200, and hence command nodes, have associated disc locations that are to be accessed to read or write data from and to the discs108. Ordering the command nodes in the queues is based in part on the disc locations, because the disc locations largely determine the time required to process the command nodes.

FIG. 3is an elevation view of a disc108showing disc locations that may be accessed in response to commands using a rotational position sorting (RPS) algorithm to sort commands in a command node queue. Six exemplary disc locations, last disc position (LDP)302, D304, C306, G308, E310, and F312, are illustrated at various positions around a disc108. To illustrate, it is assumed that disc locations D304, C306, G308, and E310, are associated with writeback commands (i.e., non-pending commands). It is further assumed that disc location F312is associated with a read command (i.e., a pending command). Using basic RPS, the read command associated with the disc location F312, is not given any preference in the prioritization process. Rather, the basic RPS algorithm gives all of the commands the same relative priority, without regard to a command's status as pending or non-pending. The basic RPS algorithm schedules disc accesses based solely on the time latency to access the locations associated with the commands. As a result, the writeback commands associated with disc locations D304, C,306, G308, and E310, are scheduled prior to the read command associated with disc location F312, as is indicated by sequencing arrows320.

The exemplary situation illustrated inFIG. 3is not optimal, primarily because the read command associated with location F312is delayed in time in favor of the writeback commands, even though the host200considers the read command to be pending and does not consider the writeback commands to be pending. In other words, the writeback commands associated with locations D304, C306, G308, and E310, are considered to have been completed from the host computer's perspective, whereas the read command associated with disc location with F312has not been completed. Because the basic RPS algorithm does not base command priority on the type of command (pending or non-pending), disc drive performance is adversely impacted as, as described above. Embodiments described inFIGS. 4-7base command prioritization on disc location as well as command type to prioritize command nodes in queues of the disc drive100.

FIG. 4illustrates a set of queues that are utilized by the pending command prioritization module232to prioritize commands with preference to pending commands in an embodiment of the present invention. In this exemplary embodiment, an ‘A’ queue402holds new command nodes404representing commands that have recently been received from the host200(FIG. 2). As is discussed in more detail below, a ‘B’ queue416holds command nodes408while they are sorted and selected for scheduling. As is also discussed in more detail below, a ‘C’ queue412holds command nodes406that are scheduled for disc access. Before describing in detail how the A, B, and C queues (402,416, and412, respectively) are used by the pending command prioritization module232, the content and format of command nodes (e.g.,404,406, and408) will now be described.

As described, commands are represented in the disc drive100by command nodes, such as the command node404. For illustrative purposes, the content and format of command node404are described here, but the described content and format of command nodes404applies equally to the command nodes406and408. Command nodes404typically include a number of fields containing data relevant to specific commands and specific systems. For example, a command node for a disc drive, such as disc drive100, may include fields that specify the buffer address of the information to be transferred, the transfer length of the information to be transferred, the start of the logical block address (LBA) issued or requested by the host computer200(FIG. 2), the start of the physical cylinder where data is to be written/read, the start of the physical head, the start of the physical sector/starting wedge where data is to be written/read, the end of the physical cylinder where data is to be written/read, the end of the physical head, the end of the physical sector/starting wedge where data is to be written/read, and the end of the physical cylinder where data is to be written/read. Additionally, each command node404preferably includes fields for a previous link pointer and fields for a next link pointer. In one embodiment, the logical order of the command nodes404is defined by the previous link and next link pointers. For example, in one embodiment, the queue402is arranged as a doubly linked list of command nodes404.

A command node404will also typically include a field for specifying what type of command (read, write, etc.) is to be executed in relationship to the command node404. For example, the command node404may include a field for control flags that specify the command associated with the command node404. The structure of the command node404, that is, the number of fields and the types of data that are required in the fields, is dependent on the types of commands executed by the system and by the type of system employing the pending command prioritization module232, such as a SCSI device or an AT device. The structure of the command node404is preferably set at the compile time of the pending command prioritization module232. It should be understood that the command node404illustrates but one example of the configuration and contents of a command node for a disc drive device. Any number of different command node configurations and contents may be used in accordance with the various embodiments described herein, depending on the environment or application in which or for which the pending command prioritization system may be used or employed.

When a new command is sent from the host computer200to the disc drive100, it is assigned a command node404in the A queue402. Command nodes in the A queue402will be routed to the B queue416where they will be sorted and prioritized.

Data associated with write commands is received from the host computer and cached before the write command node is put in the B queue416. While the data associated with the write command is being received and cached, the write command node is temporarily buffered. In one embodiment, the write command is temporarily buffered in the C queue412. In another embodiment, the write command node is temporarily buffered in another memory independent from the A, B, and C queues (402,412, and416). While a write command node is temporarily buffered, data associated with a write command node is transferred from the host200to the buffer210(FIG. 2). After data associated with the write command node is transferred from the host200to the buffer210, the write command node is moved to the B queue416and the disc drive100notifies the host200that the write command has been completed. After the host200is notified of the completion, the write command node is no longer a pending command and is referred to as a writeback command node. As previously described, the term ‘writeback’ indicates that the data associated with a write command still resides in the buffer210that must be written to the disc108.

The command nodes404that get routed directly from the A queue402to the B queue416represent commands for which no interim processing is required, and can be immediately sorted for scheduling. Examples of command nodes that are routed directly from the A queue402to the B queue416are write command nodes with no cache (i.e., non-cache write command nodes) and read command nodes. All command nodes408(e.g., read, write, and writeback command nodes) in the B queue416will be sorted and selected for scheduling based both on the disc locations associated with the command nodes and the type of command node408. Command nodes408in the B queue416are sorted according to the required processing time from a last scheduled command in the C queue412. In one embodiment, the command nodes408in the B queue are sorted using a basic RPS sort algorithm.

After commands nodes408in the B queue416are sorted, one or more of the command nodes408may be scheduled for disc access. Commands nodes408in the B queue416are scheduled by routing426them to the C queue412. When a scheduled command node406is in the C queue412, the command node406is executed in the order it was scheduled. After the scheduled command node406is executed, the command node406is removed from the C queue412. For example, if the command node406represents a writeback command, after the associated writeback data in the buffer210is written to the disc108, the writeback command node406is eliminated from the C queue412.

The A queue402and the C queue412are preferably first-in-first-out (FIFO) buffers storing sequences of new command nodes404and scheduled command nodes406, respectively. The commands nodes are ordered in the queues logically, and it is to be understood that the commands nodes may be physically located anywhere in memory in the disc drive100. The commands nodes may be logically arranged in the queues using any means known in the art, including arrays and/or linked lists.

FIG. 5is an operational flow500illustrating various operations that are implemented by the PCPM232in carrying out command prioritization in accordance with an embodiment of the present invention. Generally, the operational flow500schedules queued command nodes based both on command type (e.g., pending and non-pending) as well as disc locations associated with the command nodes. More particularly, the operational flow500schedules a pending command node along with any other command nodes that can be performed in an allowable time before the pending command node. The operational flow500utilizes one or more queues, such as the A, B, and C queues (402,416, and412, respectively ofFIG. 4).

As shown inFIG. 5, following a start operation501of the operation flow500, a querying operation502determines whether any pending commands exist. Preferably, the querying operation502checks any command nodes in the B queue416to determine if they are pending. If it is determined by the querying operation502that no pending commands exist, an RPS sort operation504executes a basic Rotational Position Sort (RPS).

In the RPS sort operation504, the buffered command nodes are sorted according to their positions on the disc108(FIG. 2). The RPS sort operation504may use any RPS algorithm known in the art. The RPS sort operation504generally determines how long it will take to process the commands in the B queue416, taking into account a number of latencies, including, but not limited to, the rotational latency, the seek time, and the disc access time. After completion of the RPS sort is operation504, the operational flow500ends. The querying and performing operations,502and504, generally save processing time in the operational flow500, by avoiding subsequently described steps if there are no pending commands in the B queue416. As such, these operations are performed in a preferred embodiment. However, in other embodiments, the querying and performing operations,502and504, may not be included and the operational flow500may begin at determining operation505rather than querying operation502.

If it is determined in the querying operation502that pending commands do exist in the B queue416, or if the querying and performing operations502and504are omitted from the operational flow500, a determining operation505determines a processing time required to process each command in the B queue408from the last scheduled command node406in the C queue412. A sorting operation506then sorts the commands in the B queue416according to the determined processing times calculated in the determining operation505. The processing times determined in the sorting operation506may be based on a multitude of latency values, including, but not limited to, the rotational latency, seek time, sequencer latency, and disc access time. The processing time associated with a waiting command node408is generally a function of the node's associated position (e.g., disc location F312ofFIG. 7) to be accessed on the disc108, as well as a previously accessed position (e.g., the LDP302ofFIG. 7) on the disc108. The LDP302is the last sector, in a set of sectors, of the last scheduled command node406(FIG. 4) in the C queue412(FIG. 4). In addition, the processing time depends on mechanical and electrical tolerances of the components in the disc drive100(FIG. 1), and thus will vary from model to model. Any sorting algorithm known in the art may be used in the sorting operation506, including a basic RPS.

Generally, the determining operation505iteratively steps through each command node408in the B queue416and determines a processing time associated with each wait command node408. The processing time is generally the amount of time to process the command node408after processing the last scheduled command node406in the C queue412. The sorting operation506then compares the determined processing time with the processing time of an adjacent waiting command node408. If the first processing time is greater than the next processing time, the sorting operation506swaps the queue position of the first command node408in the B queue416with the queue position of the adjacent command node408in the B queue416. Many other algorithms are envisioned that fall within the scope of the determining operation505and the sorting operation506.

After the command nodes in the B queue304are sorted in the sorting operation506, an identifying operation508identifies a first pending command in the B queue416. The identifying operation508checks each command node in the B queue416for its associated command type. The identifying operation508may be an iterative looping process, wherein each command node of the B queue416is iteratively tested for its command type, and the location of the first command node that is of a pending command type is stored in a ‘pendstart’ variable for future use in the operational flow500. In one embodiment, if the associated command type is either a write command with no cache or a read command, the command is identified as a pending command. Because the command type may be frequently checked during the operational flow500, the command type is preferably stored in a format that is quickly accessible and testable. In one embodiment, each of the command types is defined as a word with a unique bit asserted (e.g., set to a value of ‘1’). In this format, testing the command type can be implemented quickly in a bit masking operation, which is relatively fast for the microprocessor216. Other formats will be readily apparent to those skilled in the art.

After the first pending command is identified by the identifying operation508, an obtaining operation510obtains the disc location associated with the last scheduled command node406. The last scheduled command node406is the most recently scheduled command node in the C queue412. The obtaining operation510uses the last scheduled command node406to determine an associated physical location on the disc108. For example, if the last scheduled command node406represents a read command, the location (e.g., LDP302inFIG. 7) to be read on the disc108is determined. In the example, the determination may be made by reading a Logical Block Address (LBA) value associated with the read command node406, and/or determining an associated Cylinder Head Sector (CHS) position on a disc108. The obtaining operation510obtains the calculated CHS value and may store it to be used later in the operational flow500. Following the obtaining operation510, an initializing operation512then initializes an indicator variable that is used to index the command nodes in the B queue416. In the initializing operation512, the indicator variable is set to ‘point to’ the first command node in the B queue412.

In one embodiment, a command node reference list, called a “GO List”, is utilized to schedule command nodes in the B queue416to the C queue412. How the “GO List” is used is discussed in more detail in the description ofFIG. 6. Referring to the initializing operation512, the “GO List” is initialized along with a “GO List” counter, and an accumulated “GO List” processing time value. As is discussed below in further detail, the “GO List” is a temporary array or buffer that holds references to the command nodes that will be scheduled for disc access. Preferably the initialization operation512clears the “GO List” of any command node references and sets a “GO List” counter equal to zero in preparation for an iterative process of identifying commands in the B queue416that can be processed in an allowable time. The accumulated “GO List” processing time value is set equal to zero in the initializing operation512. The commands that can be processed in the predetermined allowable time will be scheduled using the “GO List.” After the indicator variable and the “GO List” data are initialized, a querying operation514determines whether the command node indexed, or pointed to, by the indicator is a pending command. To determine whether the command node is a pending command, the command type is tested. In one embodiment, the command type is tested using bit-masking techniques described with respect to the identifying operation508.

In another embodiment of the querying operation514, the indicator variable is compared to the ‘pendstart’ variable that was stored in the identifying operation508. If it is determined that the indicator is pointing to a pending command node, a creating operation516creates a reference to the pending command node in the “GO List.” In the creating operation516, a reference to the pending command node is stored in the “GO List.” An incrementing operation518then increments by one to keep track of the number of command node references in the “GO List.” A scheduling operation520then schedules the command nodes that are referenced by the “GO List.” The scheduling operation520copies any command nodes referenced by the “GO List” from the B queue416into the C queue412at a position following the last scheduled command node406in the C queue412.

If there is only one command node (i.e., the pending command node) referenced by the “Go List”, the command node is copied into the C queue412from the B queue416. As will be shown, the “GO List” may contain command node references (e.g., reference620inFIG. 6) in addition to the pending command node reference. If there is more than one command node reference in the “GO List” (i.e., non-pending command nodes ahead of the pending command node), the scheduling operation520schedules the pending command node last. After the command nodes referenced by the “GO List” are scheduled, the operational flow500ends at ending operation532.

If, in the querying operation514, it is determined that the command indicator is not referencing a pending command, a calculating operation521calculates how long it will take to process the pending command (identified in the identifying operation508) from the last scheduled command. The calculating operation521preferably sums the seek time, rotational latency, disc access time, and all other relevant latencies associated with moving from the disc location associated with the last scheduled command to process the pending command.

In one embodiment, the GO List processing time includes the processing time from the tail of the last scheduled command through the last command referenced in the GO List. The calculating operation521first calculates the time to service the identified command from the tail of the last command in the GO list (or last scheduled disc access if the GO list is empty). The calculating operation521then calculates the time to service the pending command from the tail of the identified command. The calculating operation521then adds to the existing GO list processing time to the two processing times previously calculated to obtain a total processing time if the indicated command is processed before the pending command. After the calculating operation521, another querying operation522determines whether the indicated command, the pending command, and all the commands referenced by the GO List can be processed within a predetermined allowed time. If the total processing time is greater than the allowed time value, the command will not be scheduled prior to the pending command. However, if the total command processing time is not greater than the predetermined allowed time, the command will be scheduled prior to the pending command.

In one embodiment, the predetermined allowed time used in the querying operation522is selected when the disc drive100is designed and/or manufactured. The allowed time value is based on the desired level of performance of the disc drive100. In particular, the throughput of the disc drive will largely depend on the selected allowed time. In one embodiment, the allowed time value is represented by a number of allowable “skipped revolutions.” In this embodiment, the total processing time is also represented in “skipped revolutions” for ease of comparison in the querying operation522. The number of skipped revolutions associated with a command refers to the number of disc108rotations that will occur before the command can be executed (i.e., before the disc location associated with the command can be accessed). Generally, a higher number of skipped revolutions for a command corresponds to a higher rotational latency. Therefore, a designer may reduce rotational latency by selecting a lower value (a minimum of zero) for the allowed skipped revolutions.

In one embodiment, the predetermined allowed time is a user selectable option through a mode page that is dependent upon the type of workload that the disc drive100is operating under. In this embodiment, the user is able to adjust the predetermined allowed time based on perceived performance in order to improve performance. In another embodiment, the predetermined allowed time is an automatically set value based on workload. The disc drive100in this embodiment is operable to calculate performance or recognize a particular mode of disc access and automatically change the predetermined allowed time accordingly to optimize performance.

If, in the querying operation522, it is determined that the total command processing time is greater than the allowed time, an incrementing operation524increments the command indicator to reference the next command node in the B queue416. In a preferred embodiment, the command nodes are retained in an array indexable by the command indicator. In this embodiment, the next command node may be referenced simply by incrementing the command indicator by one. After the incrementing operation524updates the command indicator, the querying operation514again determines if the command indicator is referencing a pending command as described above.

If it is determined in the querying operation522that the indicated, pending, and GO List commands can be processed within the allowed time, a creating operation526creates a reference to the indicated command node in the “GO List.” After the command node reference is stored in the “GO List,” an incrementing operation528increments a “GO List” counter that monitors the number of command node references in the “GO List.” After the “GO List” counter is incremented, an accumulating operation529updates the accumulated processing time value (initialized in the initializing operation512) that holds the accumulated processing time of all command nodes referenced in the “GO List” up to the indicated command. The accumulating operation529adds the command node processing time of the reference just created in the “GO List” to the accumulated processing time value that was initialized in the initializing operation512.

After the accumulating operation529, the incrementing operation524increments to the next command node in the B queue416. The operational flow500iterates through the loop of operations514,521,522,526,528, and524to create a “GO List” that contains at least one pending command node reference. The “GO List” may also contain one or more non-pending command node references. When the scheduling operation520moves the command nodes from the B queue416to the C queue412, the non-pending command nodes are placed ahead of the pending command node in the C queue412.

The operational flow500is executed repeatedly during operation of the disc drive100(FIG. 1). The frequency of execution is implementation specific. In one embodiment, the operational flow500is a task that is scheduled and executed by an operating system running on the microprocessor216(FIG. 2). In another embodiment, the operational flow500is interrupt driven, wherein the frequency of interrupts is determined by an external source, such as receipt of a command from the host200. In another embodiment, an interrupt may be generated when a new command node is inserted in the B queue416. Other implementations are envisioned that fall within the scope of embodiments of the present invention.

Turing now toFIG. 6, depicted therein are exemplary command nodes in the B queue416being scheduled and routed to the C queue412utilizing an embodiment of the operational flow500illustrated inFIG. 5. For illustrative purposes,FIG. 6is described in conjunction withFIG. 7, which shows exemplary disc locations associated with the command nodes ofFIG. 6. Each command node604,606,608,612,614, and616has a corresponding disc location304,302,306,312,308, and310(FIG. 7), respectively. The C queue412has scheduled command nodes406that are scheduled to be executed (and their corresponding disc locations accessed). The waiting command nodes408in the B queue416are sorted according to a sorting operation, such as the sorting operation506, and selectively scheduled. The C queue412has an LDP command node606corresponding to the disc location302(FIG. 7) accessed by the last scheduled command. For illustrative purposes it is assumed that command nodes604,608,614, and616are ‘writeback’ (non-pending) commands, and command node F612is a read (pending) command.

The waiting command nodes408are sorted according to required processing time relative to the LDP command node606and its LDP302. The waiting command nodes406are sorted irrespective of the type of command. During sorting, for example, it is determined that command node D604requires the least amount of processing time starting from the LDP302. Command node C608requires the next least amount of processing time starting from the LDP302, and so on.

After the waiting command nodes408have been sorted, they are selectively scheduled using a “GO List”618. The process of selectively scheduling command nodes depends on the command type associated with each waiting command node408. It is first determined that the command node F612represents a read command, and is thus a pending command node. A command node F reference624to the command node F612is created in the “GO List”618. The processing time for command node D604plus the processing time for the command node F612is not greater than a predetermined maximum processing time. Therefore, it is determined that command node D604can be processed in route to processing command node F612, and a command node D reference620to command node D604is created in the “GO List”618. When the processing time of command node C608is added to the processing time of command nodes F and D,604and612, and compared to the predetermined allowed time, it is determined that the total processing time is greater than the allowed processing time. Therefore, a reference to command node C608is not created in the “GO List”618. The process then continues to F612and determines that the command is a pending command. The creating, incrementing and scheduling operations516,518, and520(FIG. 5) then respectively create a pending command reference in the “GO List,” increment the count in the “GO List”, and schedule all the referenced nodes of the “GO List.”

The process of selectively scheduling the waiting command nodes408next involves using the command node references620and624in the “GO List”618to move the corresponding command nodes604and612to the C queue412. The ‘writeback’ command node D604is scheduled by moving640it to the C queue412at a logical position immediately after the LDP command node606. The read command node F612is scheduled by moving642it to the C queue412after the command node D630. In operation, after the LDP command node606is processed (and disc location302is accessed), the command node D630will be processed (and cached data will be written to the disc location304). After the command node D630is processed, the read command node F632will be processed by reading data from the disc location312.

The logical operations of the various embodiments of the present invention are implemented (1) as a sequence of computer implemented acts or program modules running on a computing system and/or (2) as interconnected machine logic circuits or circuit modules within the computing system. The implementation is a matter of choice dependent on the performance requirements of the computing system implementing the invention. Accordingly, the logical operations making up the embodiments of the present invention described herein are referred to variously as operations, structural devices, acts, or modules. It will be recognized by one skilled in the art that these operations, structural devices, acts and modules may be implemented in software, in firmware, in special purpose digital logic, and any combination thereof without deviating from the spirit and scope of the present invention as recited within the claims attached hereto. The algorithms and/or operations illustrated and discussed herein may be implemented in microprocessor executable software. Any software language known in the art may be used, including, but not limited to, Visual Basic, C, C++, Fortran, Assembler, etc. The choice of software language may be dependent on the type of microprocessor216as well as other design parameters.

In summary, embodiments of the present invention may be viewed as a method of prioritizing a plurality of commands by storing (such as422) a plurality of command nodes (such as408) in memory (such as210), identifying (such as514) a pending command node (such as408) in the plurality of command nodes (such as408), and scheduling (such as520,516) the pending command node (such as408) for processing. The method may further include identifying (such as514,522) intermediate command nodes (such as408) in the plurality of command nodes (such as408) that can be processed in addition to the pending command node within a predetermined amount of time, scheduling (such as520,526) the intermediate command nodes for processing prior to the pending command node.

Still further, identifying (such as514,522) intermediate command nodes that can be processed prior to the pending command node in a predetermined amount of time may include storing (such as422) the plurality of command nodes in a first queue (such as416), determining (such as521) an associated required processing time from the last scheduled command node (such as406), sorting (such as506) the plurality of command nodes (such as408) according to their associated required processing times, selecting (such as526) 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. The predetermined amount of time may be given in terms of a number of disc revolutions and in one embodiment the predetermined processing time is zero disc revolutions.

Embodiments may be viewed as a command prioritization module (such as232) that receives a pending command (such as612) and non-pending commands (such as604,608), and schedules the pending command (such as612) and one or more of the non-pending commands (such as604,608) if processing time associated with all the one or more non-pending command(s) (such as604,608) and the pending command (such as612) is less than a predetermined allowed time. The command prioritization module (such as232) may include a first command queue (such as402) having command nodes (such as404) associated with a set of most recently received commands, a second command queue (such as416) having one or more command nodes (such as406) to be scheduled, a third command queue (such as412) having one or more scheduled command nodes (such as406). Executable software or a state machine may sort (such as506) all of the pending and non-pending command nodes in the second command queue (such as416) according to processing time from a last scheduled command, identify a pending command (such as612) in the second command queue (such as416), calculate (such as521) a total processing time for one or more of the plurality of non-pending commands and pending command, and schedule (such as520) the pending command and one or more of the non-pending commands if the total processing time is less than the predetermined allowed time.

Further yet, an embodiment may be viewed as a prioritization module (such as232) for a data storage device (such as100) including a set of queues (such as402,416,412) holding command nodes (such as406) representing commands received by the data storage device (such as100), and a means (such as216,224,202) for prioritizing command nodes giving preference to one or more pending command(s). The queues (such as402,416,412) of the prioritization module (such as232) may include a first queue (such as402) holding command nodes representing new commands received by the data storage device, a second queue (such as416) receiving the command nodes from the first queue (such as402), a third queue (such as412) holding pending command nodes received from the second queue (such as416).

It will be clear that the present invention is well adapted to attain the ends and advantages mentioned as well as those inherent therein. While a presently preferred embodiment has been described for purposes of this disclosure, various changes and modifications may be made that are well within the scope of the present invention. For example, the scheduling operation520may initialize the “GO List” and “GO List” counter after the scheduling, so that upon reentry into the operational flow500, the “GO List” is already initialized. Numerous other changes may be made that will readily suggest themselves to those skilled in the art and that are encompassed in the spirit of the invention disclosed and as defined in the appended claims.