Methods and apparatus for window-based fair priority scheduling
A system provides a task scheduler to define a priority queue with at least one window and a queue-window key. Each window is an ordered collection of tasks in a task pool of the priority queue and is identified by the queue-window key. The task scheduler sets a task-window key equal to a user-window key when the user-window key is greater than the minimum queue-window key. The task scheduler can further set the task-window key equal to the minimum queue-window key when the user-window key is less than the minimum queue-window key. A maximum task limit per user for each window and a priority increment for the user-window key are further applied to ensure fair scheduling.
1. A computer implemented method comprising:
defining at least one task with a task window key, the at least one task associated with a user;
defining a single priority queue as a task pool to hold at least one task awaiting execution;
defining a queue-window key for the priority queue to describe a window of tasks within the task pool;
defining the window as a collection of tasks within the task pool of the priority queue, each task in the window having a same task-window key;
defining at least one user-window key for the user;
comparing the user-window key to a minimum queue-window key to queue a task associated with the user, the minimum queue-window key representing a current value of the queue-window key; and
extracting at least one task with a highest priority from the priority queue to be executed, wherein extracting comprises
identifying the window described by the minimum queue-window key,
sending every task in the window described by the minimum queue-window key from the priority queue for execution, and
incrementing the minimum queue-window key.
2. The computer implemented method as in claim 1 further comprising defining a timestamp for a task.
3. The computer implemented method as in claim 1 further comprising:
defining an available window key to describe a window that does not satisfy a maximum task limit for the user, the available window key further defined as a value that is most proximate to and greater than the user-window key.
4. The computer implemented method as in claim 1 further comprising:
defining a priority increment for the user-window key as an aggregate of at least one of a number value, a task performance metric, a task cost metric, a task volume metric, a task execution metric or a timestamp weight.
5. The computer implemented method as in claim 1 , wherein comparing the user-window key to a minimum queue-window key to queue the task comprises:
setting the task-window key of the task as equal to the user-window key when: the user-window key describes a window that does not satisfy the maximum task limit for the user and the user-window key is greater than the minimum queue-window key and further setting the user-window key to an aggregate of the user-window key and the priority increment; and
setting the task-window key of the task as equal to the available window key when: the user-window key describes a window that satisfies the maximum task limit for the user and the user-window key is greater than the minimum queue-window key and further setting the user-window key to an aggregate of the available window key and the priority increment.
6. The computer implemented method as in claim 1 , wherein comparing the user-window key to a minimum queue-window key to queue the task comprises:
setting the task-window key of the task as equal to the minimum queue-window key when the user-window key is less than the minimum queue-window key and further setting the user-window key to an aggregate of the minimum queue-window key and the priority increment.
7. A non-transitory computer readable medium comprising executable instructions stored thereon operable on a computerized device to perform processing comprising:
defining at least one task with a task window key, the at least one task associated with a user;
defining a single priority queue as a task pool to hold at least one task awaiting execution;
defining a queue-window key for the priority queue to describe a window of tasks within the task pool;
defining the window as a collection of tasks within the task pool of the priority queue, each task in the window having a same task-window key;
defining at least one user-window key for the user;
comparing the user-window key to a minimum queue-window key to queue a task associated with the user, the minimum queue-window key representing a current value of the queue-window key; and
extracting at least one task with a highest priority from the priority queue to be executed, wherein extracting comprises
identifying the window described by the minimum queue-window key,
sending every task in the window described by the minimum queue-window key from the priority queue for execution, and
incrementing the minimum queue-window key.
8. The computer readable medium as in claim 7 further comprising instructions to perform processing comprising defining a timestamp for a task.
9. The computer readable medium as in claim 7 further comprising instructions to perform processing comprising:
defining an available window key to describe a window that does not satisfy a maximum task limit for the user, the available window key further defined as a value that is most proximate to and greater than the user-window key.
10. The computer readable medium as in claim 7 further comprising instructions to perform processing comprising:
defining a priority increment for the user-window key as an aggregate of at least one of a number value, a task performance metric, a task cost metric, a task volume metric, a task execution metric or a timestamp weight.
11. The computer readable medium as in claim 7 , wherein the instructions for comparing the user-window key to a minimum queue-window key to queue the task comprise instructions for:
setting the task-window key of the task as equal to the user-window key when: the user-window key describes a window that does not satisfy the maximum task limit for the user and the user-window key is greater than the minimum queue-window key and further setting the user-window key to an aggregate of the user-window key and the priority increment; and
setting the task-window key of the task as equal to the available window key when: the user-window key describes a window that satisfies the maximum task limit for the user and the user-window key is greater than the minimum queue-window key and further setting the user-window key to an aggregate of the available window key and the priority increment.
12. The computer readable medium as in claim 7 , wherein the instructions for comparing the user-window key to a minimum queue-window key to queue to task comprise instructions for:
setting the task-window key of the task as equal to the minimum queue-window key when the user-window key is less than the minimum queue-window key and further setting the user-window key to an aggregate of the minimum queue-window key and the priority increment.