Back to results
US 10,310,873 B1Granted
Probabilistic aging command sorting
AssigneeSeagate Technology LLC
InventorsJeffrey V DeRosa, LingZhi Yang, Kenneth L Barham
Life of this patent
Estimating the term…
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. The system may determine a probability of a command timing out using a lookup table for a base queue depth, modified by a scalar value obtained from a queue depth adjustment lookup table using the actual queue depth as an index. In this manner, an accurate probability of a command timing out for a given queue depth can be determine without significant computational overhead.
Claims20
An apparatus comprising:
- a hardware circuit configured to:
- determine a first access time to execute a selected command from a command queue of pending commands to be executed by performing data access operations to a data storage device;
- determine a queue depth value representing a number of pending commands in the command queue;
- determine a scaling value from a queue depth adjustment table based on the queue depth value;
- determine how likely the selected command reaching a time-out threshold is based on the scaling value and a time-out table for a base queue depth,
- the time-out threshold representing a period within which the selected command is to be executed to avoid failure of the selected command,
- the time out table storing values representing a likelihood of commands timing out at a pre-set base queue depth;
- determine an adjusted access time for the selected command by modifying the first access time, the adjusted access time representing an estimated time to execute the selected command artificially adjusted based on how likely the selected command is to time out, resulting in the adjusted access time becoming artificially lower as a likelihood of the selected command reaching the time-out threshold increases;
- manipulate a command queue selection algorithm by comparing the adjusted access time for the selected command against estimated access times for other commands in the command queue to determine a command execution order, such that the selected command is more likely to be selected for execution the more the adjusted access time is artificially lowered;
- and
- execute the selected command at the data storage device at the first access time in an order based on the command execution order.
8 more elements
An apparatus comprising:
- a disc data storage medium;
- a transducer head configured to move relative to the disc data storage medium to access data from different locations on the disc data storage medium;
- a memory storing a command queue of pending commands;
- a hardware controller circuit configured to:
- access the memory to determine a first access time to execute a selected command from the command queue, including how long it will take to move the transducer head to a target location over the disc data storage medium to perform the selected command;
- determine a scaling value from a queue depth adjustment table based on a number of pending commands in the command queue;
- determine how likely the selected command reaching a time-out threshold is based on the scaling value and a time-out table,
- the time-out threshold representing a period within which the selected command is to be executed to avoid failure of the selected command,
- the time out table storing values representing a likelihood of commands timing out at a selected queue depth;
- adjust the first access time based on how likely the selected command is to reach the time-out threshold in order to obtain an adjusted access time used for command selection from the command queue;
- compare the adjusted access time for the selected command to access times for other commands in the command queue;
- select the selected command for execution when the adjusted access time is superior to the access times of the other commands;
- and
- execute the selected command at the first access time by moving the transducer head to the target location to access the disc data storage medium.
11 more elements
A method comprising:
- determining, at a data storage device, a first access time to execute a selected command from a command queue;
- determining a queue depth value representing a number of pending commands in the command queue;
- determining a scaling value using a queue depth adjustment lookup table based on the queue depth value;
- determining how likely the selected command reaching a time-out threshold is based on the scaling value and a time-out table for a base queue depth,
- the time-out threshold representing a period within which the selected command must be executed to avoid failure of the selected command,
- the time out table storing values representing a likelihood of commands timing out at a pre-set base queue depth;
- determining an adjusted access time for the selected command by modifying the first access time based on how likely the selected command is to time out, resulting in the adjusted access time becoming artificially lower as a likelihood of the selected command reaching the time-out threshold increases;
- and
- executing the selected command in an order based on the adjusted access time.
6 more elements
Dependencies are inferred from the claim text.