# US 10,310,923 B1 · Probabilistic aging command sorting > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,310,923 B1 - Document ID: US10310923B1 - Status: Granted - Kind: B1 - Application number: 14/471,981 - Filed: 2014-08-28 - Granted: 2019-06-04 - Earliest claimed: 2014-08-28 - Assignees: Seagate Technology LLC - Applicants: Seagate Technology LLC - Inventors: Jeffrey Vincent DeRosa; Jon David Trantham; Mark Gaertner - Web page: https://patentgrep.com/patent/US10310923B1 ## CPC - G06F 11/0757: {by exceeding a time limit, i.e. time-out, e.g. watchdogs} - G06F 3/061: {Improving I/O performance} - G06F 3/0659: {Command handling arrangements, e.g. command buffers, queues, command scheduling} - G06F 3/0679: {Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]} - G06F 11/0727: {in a storage system, e.g. in a DASD or network based storage system (drivers for digital recording or reproducing units G06F3/06; circuits for error detection or correction within digital recording or reproducing units G11B20/18; for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS], H04L67/1097)} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Systems and methods are disclosed for probabilistic aging command sorting, including adjusting an execution order for a command based on a probability of the command reaching a time out threshold. Various example embodiments are directed to selecting a command for execution from a queue of commands awaiting execution, in which the commands have non-uniform attributes influencing their selection and a time limit within which to execute them. In some embodiments, an apparatus may comprise a circuit configured to calculate a first estimated access time to execute a selected command from a command queue, modify the first estimated access time based on a probability of the selected command reaching a time-out age threshold to determine a time out-adjusted access time, and execute the selected command in an order based on the time out-adjusted access time. ## Claims ### Claim 1 An apparatus comprising: a circuit configured to: determine a first access time to execute a selected command from a command queue; determine a numerical value representing a probability of the selected command reaching a time-out threshold, the time-out threshold representing a period within which the selected command must be executed to avoid failure of the selected command; calculate an adjusted access time by modifying the first access time based on a mathematical calculation including the first access time and the numerical value representing the probability; and execute the selected command based on the adjusted access time. ### Claim 2 (depends on 1) The apparatus of claim 1 comprising the circuit further configured to: determine the first access time as a time to execute the selected command if the selected command is placed at a selected slot in the command queue; determine a second access time for the selected command based on the probability; determine a time adjustment by comparing the first access time and the second access time; and place the selected command in the selected slot if the time adjustment indicates a net performance gain at the first access time compared to the second access time. ### Claim 3 (depends on 2) The apparatus of claim 2 comprising the circuit configured to: determine the second access time further based on a first input/output (TO) rate of accessing a data storage medium. ### Claim 4 (depends on 3) The apparatus of claim 3 comprising: the circuit configured to determine the second access time further based on a second IO rate; the first IO rate based on an estimated time to access the data storage medium when a specified number of commands are in the command queue; and the second IO rate based on an estimated time to access the data storage medium when no commands are in the command queue. ### Claim 5 (depends on 1) The apparatus of claim 1 comprising: the circuit configured to determine the probability of the selected command reaching the time-out threshold, including: multiplying a first IO rate of accessing a data storage medium by a time remaining before the selected command reaches the time-out threshold to determine a number of execution opportunities remaining; and looking up the probability in a table based on the number of execution opportunities remaining. ### Claim 6 (depends on 5) The apparatus of claim 5 further comprising: the table includes values representing odds of a command being executed before the time-out threshold multiplied by a difference between an IO rate for unqueued commands and an IO rate for queued commands. ### Claim 7 (depends on 1) The apparatus of claim 1 comprising the circuit configured to: determine the first access time based on a seek time and rotational latency to move a transducer head from an origin point of a data storage medium to a destination point for the selected command. ### Claim 8 (depends on 1) The apparatus of claim 1 further comprising: the time-out threshold includes a time limit designated by a command interface between the apparatus and a host device, the time limit indicating an amount of time in which a command is to be executed. ### Claim 9 (depends on 1) The apparatus of claim 1 comprising the circuit further configured to: determine the time-out threshold based on a priority value associated with the selected command. ### Claim 10 A method comprising: selecting a command from a queue of a storage device for execution, including: determining a first access time to execute a selected command from the queue; calculating a value representing a probability of the selected command reaching a time-out threshold, the time-out threshold representing a period within which the selected command must be executed to avoid failure of the selected command; calculating an adjusted access time by modifying the first access time based on a calculation including the first access time and the value representing the probability; and executing the selected command based on the adjusted access time. ### Claim 11 (depends on 10) The method of claim 10 further comprising: determining the first access time as a time to execute the selected command if the selected command is placed at a selected slot in the queue; determining a second access time for the selected command based on the probability and a first input/output (TO) rate of accessing a data storage medium; determining a time adjustment by comparing the first access time and the second access time; and placing the selected command in the selected slot if the time adjustment indicates a net performance gain at the first access time compared to the second access time. ### Claim 12 (depends on 11) The method of claim 11 further comprising: determining the second access time further based on a second TO rate; the first TO rate is based on an estimated time to access the data storage medium when a specified number of commands are in the queue; and the second TO rate is based on an estimated time to access the data storage medium when no commands are in the queue. ### Claim 13 (depends on 10) The method of claim 10 further comprising: calculating the value representing the probability of the selected command reaching a time-out threshold, including: multiplying a first TO rate of accessing a data storage medium by a time remaining before the selected command reaches the time-out threshold to determine a number of execution opportunities remaining; and looking up the value in a table based on the number of execution opportunities remaining. ### Claim 14 (depends on 10) The method of claim 10 further comprising: determining the first access time based on a seek time and rotational latency to move a transducer head from an origin point of a data storage medium to a destination point for the selected command. ### Claim 15 (depends on 10) The method of claim 10 further comprising: the time-out threshold includes a time limit designated by a command interface between the storage device and a host device, the time limit indicating an amount of time in which a command is to be executed. ### Claim 16 An apparatus comprising: a processor configured to sort commands for execution in an order weighted according to a probability that each command will time out before being executed, including: determine a value representing a probability of a command reaching a time limit for executing the command; calculate a probability-adjusted access time for the command based on a mathematical calculation including an attribute of the command and the value representing the probability; and execute the command based on the probability-adjusted access time. ### Claim 17 (depends on 16) The apparatus of claim 16 further comprising: the attribute of the command includes a first access time to execute the command at a selected slot in a command queue; the processor further configured to: determine a second access time for the command based on the probability and a first input/output (TO) rate of accessing a data storage medium; calculate a time adjustment by comparing the attribute and the second access time; and place the command in the selected slot if the time adjustment indicates a net performance gain at the first access time compared to the second access time. ### Claim 18 (depends on 17) The apparatus of claim 17 comprising: the processor configured to determine the second access time further based on a second TO rate; the first TO rate is based on a time to access the data storage medium when a specified number of commands are in the command queue; and the second TO rate is based on a time to access the data storage medium when no commands are in the command queue. ### Claim 19 (depends on 16) The apparatus of claim 16 comprising: the processor configured to determine the probability-adjusted access time, including: multiplying a first TO rate of accessing a data storage medium by a time remaining before the command reaches the time limit to determine a number of execution opportunities remaining; looking up the probability in a table based on the number of execution opportunities remaining; and modifying the attribute based on the probability to obtain the probability-adjusted access time. ### Claim 20 (depends on 16) The apparatus of claim 16 further comprising: the attribute includes a priority value associated with the command influencing the execution order of the command relative to other pending commands. ### Claim 21 (depends on 16) The apparatus of claim 16 comprising the processor further configured to: calculate probability-adjusted access times for a plurality of commands in a command queue including the command; and select a command for execution from the plurality of commands based on the probability-adjusted access times. ### Claim 22 (depends on 21) The apparatus of claim 21 comprising the processor further configured to: select an execution order for the plurality of commands based on the probability-adjusted access times. ### Claim 23 (depends on 21) The apparatus of claim 21 comprising the processor further configured to: select the plurality of commands to include a predetermined number of commands, or all of the commands from the command queue if all of the commands are less than the predetermined number; and select an execution order for the plurality of commands based on the probability-adjusted access times. ### Claim 24 (depends on 23) The apparatus of claim 23 comprising the processor further configured to: select the execution order by computing a shortest access time to execute each command of the plurality of commands based on the probability-adjusted access times.