Adaptive command scheduling
View Patent ↗A system for enhancing command scheduling is provided. In particular embodiments, the system includes a processor and a scheduler that receives commands from the processor for accessing a storage device. The scheduler receives a set of commands, some of which have a deadline, and the scheduler is configured to determine an execution order for those commands. The scheduler is also configured to defer the execution of one or more of those commands to a later time.
1. A system comprising:
a processor; and
a scheduler that receives commands from the processor for accessing a storage device, wherein the scheduler is configured to:
determine a deadline for each of the commands; and
issue at least one of the commands to the storage device at a deferred time if the deadline for the at least one of the commands falls after a time threshold,
wherein the scheduler executes a first set of the commands in a first order if the scheduler determines that the first set of the commands have deadlines in a first scheduling time window, and wherein the scheduler executes a second set of the commands in a second order that is different than the first order if the scheduler determines that the second set of the commands have deadlines in a second scheduling time window,
wherein the scheduler is configured to execute the first set of the commands having deadlines in the first scheduling time window in earliest deadline first order, and wherein the scheduler is configured to execute the second set of the commands having deadlines in the second scheduling time window in cylinder scan order.
2. The system defined in claim 1 wherein the deferred time is based at least in part on feedback associated with at least one actual command completion time.
3. The system defined in claim 1 wherein the deferred time adapts over time to variations in actual command completion times.
4. The system defined in claim 1 wherein the time threshold is based at least in part on feedback associated with at least one actual command completion time.
5. The system defined in claim 1 wherein the time threshold adapts over time to variations in actual command completion times.
6. The system defined in claim 1 wherein the time threshold adapts over time based on command completion times of a stochastic hard disk drive model.
7. The system defined in claim 1 wherein the scheduler is configured to execute a third set of the commands having deadlines in a third scheduling time window in cylinder scan order.
8. The system defined in claim 1 wherein the commands are associated with reading and writing data from the storage device, and wherein the scheduler groups the first set of the commands into a batch, defers the first set of the commands until closer to the deadlines of the first set of the commands, and executes the first set of the commands in the batch.
9. A computer system that comprises code for a command scheduler, wherein the code is stored on a non-transitory computer readable medium, the computer system comprising:
code for determining a deadline for each command of a plurality of commands for accessing a storage device; and
code for issuing at least one of the commands to the storage device at a deferred time if the deadline for the at least one of the commands falls after a time threshold, wherein the command scheduler executes a first set of the commands in a first order if the command scheduler determines that the first set of the commands have deadlines in a first scheduling time window, and wherein the command scheduler executes a second set of the commands in a second order that is different than the first order if the command scheduler determines that the second set of the commands have deadlines in a second scheduling time window, and
wherein the command scheduler executes the first set of the commands having deadlines in the first scheduling time window in earliest deadline first order and the second set of the commands having deadlines in the second scheduling time window in cylinder scan order.
10. The computer system defined in claim 9 wherein the deferred time is based at least in part on feedback associated with at least one actual command completion time.
11. The computer system defined in claim 9 wherein the deferred time adapts over time to variations in actual command completion times.
12. The computer system defined in claim 9 wherein the time threshold is based at least in part on feedback associated with at least one actual command completion time.
13. The computer system defined in claim 9 wherein the time threshold adapts over time to variations in actual command completion times.
14. The computer system defined in claim 9 wherein the time threshold adapts over time based on command completion times of a stochastic hard disk drive model.
15. The computer system defined in claim 9 wherein the first scheduling time window is a sliding window that moves while time advances.
16. A method for a command scheduler, the method comprising:
determining a deadline for each command of a plurality of commands for accessing a storage device; and
issuing at least one of the commands to the storage device at a deferred time if the deadline for the at least one of the commands falls after a time threshold, wherein the command scheduler executes a first set of the commands in a first order if the command scheduler determines that the first set of the commands have deadlines in a first scheduling time window, and wherein the command scheduler executes a second set of the commands in a second order that is different than the first order if the command scheduler determines that the second set of the commands have deadlines in a second scheduling time window, and
wherein the command scheduler executes the first set of the commands having deadlines in the first scheduling time window in earliest deadline first order and the second set of the commands having deadlines in the second scheduling time window in cylinder scan order.
17. The method defined in claim 16 wherein the deferred time is based at least in part on feedback associated with at least one actual command completion time.
18. The method defined in claim 16 wherein the deferred time adapts over time to variations in actual command completion times.
19. The method defined in claim 16 wherein the time threshold is based at least in part on feedback associated with at least one actual command completion time.
20. The method defined in claim 16 wherein the time threshold adapts over time to variations in actual command completion times.
21. The method defined in claim 16 wherein the command scheduler executes non-real-time best-effort commands in cylinder scan order.