Method for determining command execution dependencies within command queue reordering process

Claim 1

A method of managing a command queue within a storage device defining a multiplicity of block addresses for storing user data blocks and receiving into the command queue a group of presently unexecuted input/output (I/O) commands for the device from a host system, the method comprising the steps: maintaining a sequential ordering of said group of commands within the command queue; maintaining command execution dependency relation information for each command of said group, each dependency relation indicating an overlap of block addresses between a given command and other commands within the group; identifying a set of independent commands within the group as having no block address overlap relative to other commands within the group; and selecting one of said independent commands for promotion to a command execution position within the command queue, said selected independent command determined by the device to be a least-latent one of said independent commands relative to a head-of-queue command presently being executed within the storage device.

Claim 2

A method of managing a command queue within a storage device defining a multiplicity of block addresses for storing user data blocks and receiving into the command queue a group of presently unexecuted input/output (I/O) commands for the device from a host system, the method comprising the steps: maintaining a sequential ordering of said group of commands within the command queue; maintaining command execution dependency relation information for each command of said group, each dependency relation indicating an overlap of block addresses between a given command and other commands within the group; identifying a set of independent commands within the group as having no block address overlap relative to other commands within the group; and selecting one of said independent commands for promotion to a command execution position within the command queue, said selected independent command determined by the device to be a least-latent one of said independent commands relative to a head-of-queue command presently being executed within the storage device.

Claim 4

A method of managing a command queue within an addressable storage device receiving input/output (I/O) commands from a host for retrieving and writing user data blocks, the addressable storage device having multiple block addresses for storing blocks of user data, the method comprising the steps: maintaining a sequential ordering of said commands received from the host within the command queue wherein each new command is appended to a rearmost position of said sequential ordering and a command under execution is maintained at a forward most position of said sequential ordering until said command under execution completes execution, a next executed position of said sequential ordering being immediately rearward of said forward most position and indicating a command to be next executed following completion of the command under execution; maintaining an execution dependency relation record for each command in said sequential ordering within the command queue, each execution dependency relation record indicating an overlap of block addresses between a given command and a more forward command in said sequential ordering; identifying from said execution dependency relation record a set of independent commands as those commands within the command queue having no execution dependency relative to a more forward command within the command queue; and selecting one of said independent commands for promotion to said next executed position, said selected independent command being a least-latent one of said independent commands relative to said command under execution.

Claim 5

A method of managing a command queue within an addressable storage device receiving input/output (I/O) commands from a host for retrieving and writing user data blocks, the addressable storage device having multiple block addresses for storing blocks of user data, the method comprising the steps: maintaining a sequential ordering of said commands received from the host within the command queue wherein each new command is appended to a rearmost position of said sequential ordering and a command under execution is maintained at a forward most position of said sequential ordering until said command under execution completes execution, a next executed position of said sequential ordering being immediately rearward of said forward most position and indicating a command to be next executed following completion of the command under execution; maintaining an execution dependency relation record for each command in said sequential ordering within the command queue, each execution dependency relation record indicating an overlap of block addresses between a given command and a more forward command in said sequential ordering; identifying from said execution dependency relation record a set of independent commands as those commands within the command queue having no execution dependency relative to a more forward command within the command queue; and selecting one of said independent commands for promotion to said next executed position, said selected independent command being a least-latent one of said independent commands relative to said command under execution.

Claim 11

A method for reordering presently unexecuted user data block access commands in relation to detected execution dependencies therebetween in a command queue within a data storage device providing a multiplicity of logical block address (LBA) storage locations for storing blocks of user data, the method comprising during execution of a head-of-queue command the steps of: maintaining a plurality of user data block access command records, a particular record representing a particular command of the user data block access command queue, and the particular record including an LBA range, a dependency flag field, a queue pointer field, and a dependency list, the dependency list representing rearward members of the command queue having execution dependency upon the particular command, the queue pointer field maintaining position of the particular command within the command queue, the dependency flag indicating an execution dependency of the particular command upon a more forward command in the command queue, and reordering the command queue by: first clearing all dependency flags of records of the commands therein, traversing the plurality of command records, and calculating execution latency values for the commands therein in relation to the head-of-queue command, setting the dependency flags of the records of rearward members having execution dependencies upon each record traversed, restricting command reordering to a next-to-head-of-queue position to those commands having records with command dependency flags clear, and promoting one of those command determined to have a least execution latency value to the next-to-head-of-queue position within the command queue.

Claim 12

A method for reordering presently unexecuted user data block access commands in relation to detected execution dependencies therebetween in a command queue within a data storage device providing a multiplicity of logical block address (LBA) storage locations for storing blocks of user data, the method comprising during execution of a head-of-queue command the steps of: maintaining a plurality of user data block access command records, a particular record representing a particular command of the user data block access command queue, and the particular record including an LBA range, a dependency flag field, a queue pointer field, and a dependency list, the dependency list representing rearward members of the command queue having execution dependency upon the particular command, the queue pointer field maintaining position of the particular command within the command queue, the dependency flag indicating an execution dependency of the particular command upon a more forward command in the command queue, and reordering the command queue by: first clearing all dependency flags of records of the commands therein, traversing the plurality of command records, and calculating execution latency values for the commands therein in relation to the head-of-queue command, setting the dependency flags of the records of rearward members having execution dependencies upon each record traversed, restricting command reordering to a next-to-head-of-queue position to those commands having records with command dependency flags clear, and promoting one of those command determined to have a least execution latency value to the next-to-head-of-queue position within the command queue.

Claim 13

A method for reordering presently unexecuted user data block access commands in relation to detected execution dependencies therebetween in a command queue within a data storage device providing a multiplicity of logical block address (LBA) storage locations for storing blocks of user data, the method comprising the steps of: maintaining a plurality of user data block access command records, a particular record representing a particular command of the user data block access command queue, and the particular record including an LBA range, a dependency flag field, a queue pointer field, and a dependency list, the dependency list representing rearward members of the command queue having execution dependency upon the particular command, the queue pointer field maintaining position of the particular command within the command queue, the dependency flag indicating an execution dependency of the particular command upon a more forward command in the command queue, and reordering the command queue by: first clearing all dependency flags of records of the commands therein, traversing the plurality of command records, and calculating execution latency values for the commands therein in relation to the head-of-queue command, setting the dependency flags of the records of rearward members having execution dependencies upon each record traversed, restricting command reordering to a next-to-head-of-queue position to those commands having records with command dependency flags clear, and promoting one of those command determined to have a least execution latency value to the next-to-head-of-queue position within the command queue building dependency lists of each record for each member of said command queue as new records are appended to said plurality of user data block access command records; and deleting a record representing the top-of-queue command from said plurality of user data block access command records upon completion of execution of the top-of-queue command and thereby automatically removing dependency upon the executed command from the dependency lists of all other records remaining in the plurality of user data block access command records.

Claim 14

A method for reordering presently unexecuted user data block access commands in relation to detected execution dependencies therebetween in a command queue within a data storage device providing a multiplicity of logical block address (LBA) storage locations for storing blocks of user data, the method comprising the steps of: maintaining a plurality of user data block access command records, a particular record representing a particular command of the user data block access command queue, and the particular record including an LBA range, a dependency flag field, a queue pointer field, and a dependency list, the dependency list representing rearward members of the command queue having execution dependency upon the particular command, the queue pointer field maintaining position of the particular command within the command queue, the dependency flag indicating an execution dependency of the particular command upon a more forward command in the command queue, and reordering the command queue by: first clearing all dependency flags of records of the commands therein, traversing the plurality of command records, and calculating execution latency values for the commands therein in relation to the head-of-queue command, setting the dependency flags of the records of rearward members having execution dependencies upon each record traversed, restricting command reordering to a next-to-head-of-queue position to those commands having records with command dependency flags clear, and promoting one of those command determined to have a least execution latency value to the next-to-head-of-queue position within the command queue building dependency lists of each record for each member of said command queue as new records are appended to said plurality of user data block access command records; and deleting a record representing the top-of-queue command from said plurality of user data block access command records upon completion of execution of the top-of-queue command and thereby automatically removing dependency upon the executed command from the dependency lists of all other records remaining in the plurality of user data block access command records.