Methods and apparatus for window-based fair priority scheduling
AssigneeOracle America, Inc.
InventorsSeth T. Proctor, David A. Jurgens, David R. Chase
Life of this patent
Estimating the term…
Abstract
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.
Claims12
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.
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.
Dependencies are inferred from the claim text.