Goal-oriented predictive scheduling in a grid environment

• US 20050283534A1
• Filed: 06/17/2004
• Published: 12/22/2005
• Est. Priority Date: 06/17/2004
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: Platform Computing Corporation
• Inventors: Pang, James, Bigagli, David, Yuan, Shutao
• Granted Patent: US 7,844,969 B2
• Time in Patent Office: Days
• US Class Current: 709/229
• CPC Class Codes: G06F 2209/506 Constraint
• CPC Class Codes: G06F 8/65 Updates security arrangements therefor G06F21/57
• CPC Class Codes: G06F 9/5038 considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration scheduling strategies G06F9/4881 and subgroups
• CPC Class Codes: G06F 9/5072 Grid computing

Abstract

A method for scheduling jobs in a networked computing grid is described. The method includes scheduling jobs to meet goals related to execution of the jobs within the computing grid. The jobs may be scheduled by evaluating job execution goals against available resource slots provided by the computing grid. Also disclosed are related methods for scheduling jobs in which the jobs are submitted to service classes having defined job execution goals, and wherein the jobs are scheduled according to the job execution goals of the service classes.

Claims

1. A method for scheduling one or more jobs having one or more goals in a networked computing grid having available resource slots, the method comprising:

determining the available resource slots in the networked computing grid;

receiving the one or more goals for the one or more jobs;

evaluating the one or more goals in view of the determined available resource slots; and

scheduling the one or more jobs to one or more resource slots of the available resource slots to meet the one or more goals.

2. The method of claim 1 wherein receiving the one or more goals comprises receiving a deadline for the one or more jobs, and wherein scheduling the one or more jobs comprises scheduling the one or more jobs to be executed prior to the expiration of the deadline.

3. The method of claim 1 wherein receiving the one or more goals comprises receiving an execution velocity for the one or more jobs, and wherein scheduling the one or more jobs comprises scheduling the one or more jobs to be executed according to the execution velocity.

4. The method of claim 1 wherein receiving the one or more goals comprises receiving an execution throughput for the one or more jobs, and wherein scheduling the one or more jobs comprises scheduling the one or more jobs to be executed according to the execution throughput.

5. The method of claim 1 wherein receiving the one or more goals comprises receiving a queue time for the one or more jobs, and wherein scheduling the one or more jobs comprises scheduling the one or more jobs to be executed prior to the expiration of the queue time.

6. A method for scheduling jobs in a networked computing grid, comprising:

creating one or more service classes having defined job execution goals;

submitting jobs to the one or more service classes; and

scheduling the jobs according to the job execution goals.

7. The method of claim 6 further comprising defining a service class name for the one or more service classes.

8. The method of claim 6 further comprising defining a service class priority for the one or more service classes, the jobs associated with the one or more service classes being executed according to the service class priority.

9. The method of claim 6 further comprising defining a user group parameter for the one or more service classes, the user group being provided to limit access to the one or more service classes.

10. The method of claim 6 further comprising defining a control action parameter for the one or more service classes, the control action being invoked if job execution according to the job execution goal requirements is delayed.

11. The method of claim 6 wherein the job execution goals are active only during specified time windows.

12. A method for scheduling one or more jobs in a networked computing grid having available resource slots, comprising:

receiving one or more job execution goals for the one or more jobs; and

evaluating the one or more job execution goals against one or more of the available resource slots to determine whether the one or more jobs can be executed to meet the one or more job execution goals; and

scheduling the one or more jobs to one or more of the available resource slots if the one or more jobs can be executed to meet the one or more job execution goals.

13. The method of claim 12 further comprising notifying an administrator if the one or more jobs cannot be executed to meet the one or more job execution goals.

14. The method of claim 12 further comprising searching for additional resource slots if the one or more jobs cannot be executed to meet the one or more job execution goals.

15. The method of claim 12 wherein receiving one or more job execution goals comprises receiving a deadline for the one or more jobs, and wherein scheduling the one or more jobs comprises scheduling the one or more jobs to be executed prior to the expiration of the deadline.

16. The method of claim 12 wherein receiving one or more job execution goals comprises receiving an execution velocity for the one or more jobs, and wherein scheduling the one or more jobs comprises scheduling the one or more jobs to be executed according to the execution velocity.

17. The method of claim 12 wherein receiving one or more job execution goals comprises receiving an execution throughput for the one or more jobs, and wherein scheduling the one or more jobs comprises scheduling the one or more jobs to be executed according to the execution throughput.

18. The method of claim 12 wherein receiving one or more job execution goals comprises receiving a queue time for the one or more jobs, and wherein scheduling the one or more jobs comprise scheduling the one or more jobs to be executed prior to the expiration of the queue time.

19. The method of claim 12 wherein evaluating the one or more job execution goals comprises solving a mathematical model representative of the one or more job execution goals and the available resource slots.

20. The method of claim 12 wherein evaluating the one or more goal requirements comprises solving a generally non-linear constrained optimization problem representative of the one or more job execution goals and the available resource slots.