METHOD AND SYSTEM FOR HEURISTICS-BASED TASK SCHEDULING

• US 20100333113A1
• Filed: 06/29/2009
• Published: 12/30/2010
• Est. Priority Date: 06/29/2009
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Johnson, Darrin P., Saxe, Eric C.
• Granted Patent: US 8,261,275 B2
• Time in Patent Office: Days
• US Class Current: 719/318
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/542 Event management; Broadcasting; Multicasting; Notifications
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

A computer readable storage medium including executable instructions for heuristics-based task scheduling. Instructions include receiving a first event notification associated with a first event, where the first event is determined from the first event notification. Instructions further include determining whether a predicate for an action is satisfied by the first event, where the action predicate, the action, and an action parameter are associated with a task object in a task pool. Instructions further include obtaining the action parameter when the action predicate is satisfied by the first event, where a priority is assigned using a heuristics policy to the task object based on the action parameter. Instructions further include inserting the task object into a task queue using the assigned priority. The action associated with the task object is performed by an execution thread. The performance of the action is a second event associated with a second event notification.

Claims

1. A computer readable medium comprising executable instructions for heuristics-based task scheduling, wherein executable instructions comprise instructions to:

receive a first event notification at a task engine, wherein the first event notification is associated with a first event;

determine the first event using the first event notification;

determine whether a first predicate for a first action is satisfied by the first event, wherein the first predicate for the first action, the first action, a first action parameter for the first action are associated with a first task object in a task pool;

obtain the first action parameter using the first task object when the first predicate for the first action is satisfied by the first event;

assign the first task object a priority using a heuristics policy based on the first action parameter; and

insert the first task object into a task queue using the assigned priority, wherein the task queue comprises a plurality of task objects, and wherein the plurality of task objects are ordered according to priority,

wherein the first action associated with the first task object is performed by an execution thread when the first task object is obtained from the task queue, wherein the performance of the first action is a second event, and wherein the second event is associated with a second event notification sent to the task engine.

2. The computer readable medium of claim 1, wherein executable instructions further comprise instructions to:

receive a request at the task engine;

determine the first task corresponding to the request using a request-to-task mapping;

obtain a first task entry corresponding with the first task from a task store, wherein the first task entry associates the first task with the first action, the first predicate for performing the first action, and the first action parameter for the first action; and

create the first task object in the task pool.

3. The computer readable medium of claim 2, wherein the request is one selected from a group consisting of a request generated by a user-level application, a request generated by an operating system, and a request generated by a hardware resource.

4. The computer readable medium of claim 3, wherein the request generated by the user-level application is sent using a Task Request Application Programming Interface (API).

5. The computer readable medium of claim 1, wherein executable instructions further comprise instructions to:

receive a third event notification at the task engine, wherein the third event notification is associated with a third event;

determine the first task corresponding to the third event using an event-to-task mapping;

obtain a first task entry corresponding with the first task from a task store, wherein the first task entry associates the first task with the first action and the first predicate for performing the first action; and

create the first task object in the task pool.

6. The computer readable medium of claim 1, wherein executable instructions further comprise instructions to:

remove the first task object from the task pool when the first predicate for the first action is satisfied by the first event.

7. The computer readable medium of claim 1, wherein the heuristics policy used to assign the priority to the first task object is one of a plurality of heuristics policies stored in a heuristics policy store.

8. The computer readable medium of claim 7, wherein a determination of the heuristics policy from the plurality of heuristics policies is made using one selected from a group consisting of a user selection, an operational setting the system upon which the first action is performed, and a hardware configuration of the system upon which the first action is performed.

9. The computer readable medium of claim 5, wherein the request-to-task mapping, the event-to-task mapping, and the first task request entry are created when a user makes a request using a Task Management API.

10. A system for heuristics-based task scheduling, comprising:

a processor;

an operating system executing on, wherein the operating system comprises;

a task engine, configured to;

receive a request;

determine a first task corresponding with the request using a request-to-task mapping;

obtain a first task entry corresponding with the first task from a task store, wherein the first task entry associates the first task with a first action, a first predicate for performing the first action, and a first action parameter for the first action;

create a first task object in a task pool using the first task entry, wherein the first task object is associated with the first action, the first predicate, and the first action parameter;

receive a first event notification, wherein the first event notification is associated with a first event;

determine the first event using the first event notification;

determine whether the first predicate for performing the first action is satisfied by the first event;

send the first task object to a task scheduler when the first predicate for performing the first action is satisfied by the first event;

the task store, configured to;

store the first task entry;

the task pool, configured to;

store the first task object when the first predicate for the first action has not yet been satisfied;

a heuristics policy store, configured to;

store a heuristics policy for assigning a first priority to a task object;

the task scheduler, configured to;

obtain the first action parameter using the first task object when the first predicate for the first action is satisfied by the first event;

assign the first task object the first priority using the heuristics policy based on the first action parameter;

insert the first task object into a task queue using the first priority, wherein the task queue comprises a plurality of task objects, and wherein the plurality of task objects are ordered according to priority;

the task queue, configured to;

store the first task object when the first predicate for the first action has been satisfied and the first task object has been assigned the first priority by the task scheduler;

a dispatcher, configured to;

obtain the first task object from the task queue;

determine the first action using the first task object;

determine a first execution thread for performing the first action; and

dispatch the first execution thread for performing the first action;

wherein the operating system is configured to create a second event notification for sending to the task engine when the first execution thread has completed performing the first action, and wherein the completion of the first action is a second event associated with the second event notification.

11. The system of claim 10, wherein

the task engine is further configured to:

receive a third event notification, wherein the third event notification is associated with a third event;

determine a second task corresponding with the third event using an event-to-task mapping;

obtain a second task entry corresponding with the second task from the task store, wherein the second task entry associates the second task with a second action, a second predicate for performing the second action, and a second action parameter;

create a second task object in the task pool using the second task entry, wherein the second task object is associated with the second action, the second predicate, and the second action parameter;

receive a fourth event notification, wherein the fourth event notification is associated with a fourth event;

determine the fourth event using the fourth event notification;

determine whether the second predicate for performing the second action is satisfied by the fourth event; and

send the second task object to the task scheduler when the second predicate for performing the second action is satisfied by the fourth event;

the task store is further configured to;

store the second task entry;

the task pool is further configured to;

store the second task object when the second predicate for the second action has not yet been satisfied;

the task scheduler, further configured to;

obtain the second action parameter using the second task object when the second predicate for the second action is satisfied by the second event;

assign the second task object the second priority using the heuristics policy based on the second action parameter;

insert the second task object into the task queue using the second priority;

the task queue is further configured to;

store the second task object when the second predicate for the second action has been satisfied and the second task object has been assigned a second priority by the task scheduler;

the dispatcher, configured to;

obtain the second task object from the task queue;

determine the second action using the second task object;

determine a second execution thread for performing the second action; and

dispatch the second execution thread for performing the second action;

wherein the operating system is configured to create a fifth event notification for sending to the task engine when the second execution thread has completed performing the second action, and wherein the completion of the second action is a fifth event associated with the fifth event notification.

12. The system of claim 10, wherein the first request is one selected from a group consisting of a request generated by a user-level application, a request generated by an operating system, and a request generated by a hardware resource.

13. The system of claim 12, wherein the request generated by the user-level application is sent using a Task Request API.

14. The system of claim 11, wherein the task engine is further configured to:

remove the first task object from the task pool when the first predicate for the first action is satisfied by the first event; and

remove the second task object from the task pool when the second predicate for the second action is satisfied by the fourth event.

15. The system of claim 10, wherein the heuristics policy is one of a plurality of heuristics policies stored in the heuristics policy store.

16. The system of claim 15, wherein a determination of the heuristics policy from the plurality of heuristics policies is made using one selected from a group consisting of a user selection, an operational setting the system upon which the first action is performed, and a hardware configuration of the system upon which the first action is performed.

17. The system of claim 11, wherein the request-to-task mapping, the event-to-task mapping, the first task entry, and the second task entry are created when a user makes a request using a Task Management API.