Grid non-deterministic job scheduling

• US 8,276,146 B2
• Filed: 07/14/2008
• Issued: 09/25/2012
• Est. Priority Date: 05/20/2004
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Dawson, Christopher James, Fellenstein, Craig William, Hamilton, Rick Allen II, Joseph, Joshy
• Primary Examiner(s): TO, JENNIFER N
• Application Number:
  US12/172,584
• Publication Number:
  US 20090049448A1
• Time in Patent Office: 1,534 Days
• Field of Search: 718/102
• US Class Current: 718/102
• CPC Class Codes: G06F 9/5027 the resource being a machine, e.g. CPUs, Servers, Terminals
• CPC Class Codes: G06F 9/5072 Grid computing

Abstract

The present invention is method for scheduling jobs in a grid computing environment without having to monitor the state of the resource on the gird comprising a Global Scheduling Program (GSP) and a Local Scheduling Program (LSP). The GSP receives jobs submitted to the grid and distributes the job to the closest resource. The resource then runs the LSP to determine if the resource can execute the job under the conditions specified in the job. The LSP either rejects or accepts the job based on the current state of the resource properties and informs the GSP of the acceptance or rejection. If the job is rejected, the GSP randomly selects another resource to send the job to using a resource table. The resource table contains the state-independent properties of every resource on the grid.

Claims

1. A method for scheduling a job on a grid wherein a scheduler does not have to keep track of a plurality of state dependent resource properties, the method comprising:

a computer receiving notification that the job has been submitted to the grid from a submitting computer;

the computer determining whether the submitting computer is a resource of the grid;

responsive to the determination that the submitting computer is not the resource, the computer sending the job to a resource closest to the submitting computer;

running a local scheduling program at a resource with the job;

the computer determining whether the resource with the job accepted the job;

responsive to the determination that the resource with the job did not accept the job, adding the resource with the job to an attempted resources list, determining the remaining resources capable of executing the job using a resource table, removing from consideration the resource on the attempted resources list;

the computer determining if any remaining resources remain after removing from consideration the resource on the attempted resources list; and

responsive to the determination that remaining resources remain, randomly selecting a second resource from a plurality of remaining resources and sending the job to the second resource; and

responsive to the determination that remaining resources do not remain, determining if a preset number of iterations have been reached;

responsive to the determination that the preset number of iterations have been reached, clearing the attempted resources list, waiting a specified amount of time, and re-determining the remaining resources capable of executing the job using the resource table.

2. The method of claim 1 further comprising:

responsive to the determination that the preset number of iterations has been reached, notifying the submitting computer that the job has failed.

3. The method of claim 1 wherein the resource table consists of a plurality of state independent resource properties.

4. The method of claim 1 wherein running the local scheduling program comprises:

determining whether the resource with the job can execute the job;

responsive to the determination that the resource with the job can execute the job, indicating that the resource with the job has accepted the job; and

executing the job at the resource with the job.

5. The method of claim 4 wherein running the local scheduling program further comprises:

responsive to the determination that the resource with the job cannot execute the job, indicating that the resource with the job has not accepted the job.

6. The method of claim 4 wherein the job is placed in an execution queue prior to being executed.

7. The method of claim 1 wherein the local scheduling program determines whether the resource can execute the job by examining the state dependent resource properties.

8. The method of claim 1 wherein any computer connected to the grid can accept the job.

9. The method of claim 1 wherein any computer connected to the grid can schedule the job.

10. A method for scheduling a job on a grid wherein a resource determines whether to accept the job, the method comprising:

a computer receiving notification that the job has been submitted to the grid from a submitting computer;

the computer determining whether the submitting computer is a resource of the grid;

responsive to the determination that the submitting computer is not the resource, the computer sending the job to a resource closest to the submitting computer;

running a local scheduling program at a resource with the job;

the computer determining whether the resource with the job can execute the job;

responsive to the determination that the resource with the job cannot execute the job, adding the resource with the job to an attempted resources list, determining the remaining resources capable of executing the job using a resource table, removing from consideration the resource on the attempted resources list, and determining if any remaining resources remain after removing from consideration the resource on the attempted resources list;

responsive to the determination that remaining resources remain, randomly selecting a second resource from a plurality of remaining resources and sending the job to the second resource; and

responsive to the determination that remaining resources do not remain, determining if a preset number of iterations have been reached;

responsive to the determination that the preset number of iterations has been reached, clearing the attempted resources list, waiting a specified amount of time, and re-determining the remaining resources capable of executing the job using the resource table.

11. The method of claim 10 further comprising:

responsive to the determination that the preset number of iterations has been reached, the computer notifying the submitting computer that the job has failed.

12. The method of claim 10 wherein the resource table consists of a plurality of state independent resource properties.

13. The method of claim 10 wherein any computer connected to the grid can accept the job.

14. The method of claim 10 wherein any computer connected to the grid can schedule the job.

15. A computer program product for scheduling a job on a grid wherein a scheduler does not have to keep track of a plurality of state dependent resource properties, the computer program product comprising:

one or more computer-readable, tangible storage devices;

program instructions, stored on at least one of the one or more storage devices, to receive notification that the job has been submitted to the grid from a submitting computer;

program instructions, stored on at least one of the one or more storage devices, to determine whether the submitting computer is a resource of the grid;

program instructions, stored on at least one of the one or more storage devices, responsive to the determination that the submitting computer is not the resource, to send the job to a resource closest to the submitting computer;

program instructions, stored on at least one of the one or more storage devices, to run a local scheduling program at a resource with the job;

program instructions, stored on at least one of the one or more storage devices, to determine whether the resource with the job accepted the job;

program instructions, stored on at least one of the one or more storage devices, responsive to the determination that the resource with the job did not accept the job, to add the resource with the job to an attempted resources list;

program instructions, stored on at least one of the one or more storage devices, to determine the remaining resources capable of executing the job using a resource table, to remove from consideration the resource on the attempted resources list;

program instructions, stored on at least one of the one or more storage devices, to determine if any remaining resources remain after removing from consideration the resource on the attempted resources list; and

responsive to the determination that remaining resources remain, randomly selecting a second resource from a plurality of remaining resources and sending the job to the second resource;

program instructions, stored on at least one of the one or more storage devices, responsive to the determination that remaining resources do not remain, to determine if a preset number of iterations has been reached;

program instructions, stored on at least one of the one or more storage devices, responsive to the determination that the preset number of iterations has been reached, to clear the attempted resources list, waiting a specified amount of time, and to re-determine the remaining resources capable of executing the job using the resource table; and

program instructions, stored on at least one of the one or more storage devices, responsive to the determination that the preset number of iterations has been reached, to notify an originating computer that the job has failed.

16. The computer program product of claim 15 wherein the resource table consists of a plurality of state independent resource properties.

17. The computer program product of claim 15 wherein the local scheduling program comprises:

program instructions, stored on at least one of the one or more storage devices, to determine whether the resource can execute the job;

program instructions, stored on at least one of the one or more storage devices, responsive to the determination that the resource can execute the job, to indicate that the resource has accepted the job; and

program instructions, stored on at least one of the one or more storage devices, to execute the job at the resource.

18. The computer program product of claim 15 wherein the local scheduling program further comprises:

program instructions, stored on at least one of the one or more storage devices, responsive to the determination that the resource cannot execute the job, to indicate that the resource has not accepted the job.

19. The computer program product of claim 15 wherein the job is placed in an execution queue prior to being executed.

20. The computer program product of claim 15 wherein the local scheduling program determines whether the resource can execute the job by examining the state dependent resource properties.

21. The computer program product of claim 15 wherein any computer connected to the grid can accept the job.

22. The computer program product of claim 15 wherein any computer connected to the grid can schedule the job.

23. A computer program product for scheduling a job on a grid wherein a resource determines whether to accept the job, the computer program product comprising:

one or more computer-readable, tangible storage devices;

program instructions, stored on at least one of the one or more storage devices, to receive notification that the job has been submitted to the grid from a submitting computer;

program instructions, stored on at least one of the one or more storage devices, to determine whether the submitting computer is a resource of the grid;

program instructions, stored on at least one of the one or more storage devices, responsive to the determination that the submitting computer is not the resource, to send the job to a resource closest to the submitting computer;

program instructions, stored on at least one of the one or more storage devices, to run a local scheduling program at a resource with the job;

program instructions, stored on at least one of the one or more storage devices, to determine whether the resource with the job can execute the job;

program instructions, stored on at least one of the one or more storage devices, responsive to the determination that the resource with the job can not execute the job, to add the resource with the job to an attempted resources list;

program instructions, stored on at least one of the one or more storage devices, to determine the remaining resources capable of executing the job using a resource table, to remove from consideration the resource on the attempted resources list;

program instructions, stored on at least one of the one or more storage devices, to determine if any remaining resources remain after removing from consideration the resource on the attempted resources list; and

responsive to the determination that remaining resources remain, randomly selecting a second resource from a plurality of remaining resources and sending the job to the second resource;

program instructions, stored on at least one of the one or more storage devices, responsive to the determination that remaining resources do not remain, to determine if a preset number of iterations has been reached;

program instructions, stored on at least one of the one or more storage devices, responsive to the determination that the preset number of iterations has been reached, to clear the attempted resources list, waiting a specified amount of time, and to re-determine the remaining resources capable of executing the job using the resource table; and

program instructions, stored on at least one of the one or more storage devices, responsive to the determination that the preset number of iterations has been reached, to notify an originating computer that the job has failed.

24. The computer program product of claim 23 further comprising:

responsive to the determination that the preset number of iterations have not been reached, notifying an originating computer that the job has failed.

25. The computer program product of claim 23 wherein the resource table consists of a plurality of state independent resource properties.

26. The computer program product of claim 23 wherein any computer connected to the grid can accept the job.

27. The computer program product of claim 23 wherein any computer connected to the grid can schedule the job.