Grid Non-Deterministic Job Scheduling

• US 20090049448A1
• Filed: 07/14/2008
• Published: 02/19/2009
• Est. Priority Date: 05/20/2004
• Status: Active Grant

• Current Assignee: Christopher James Dawson, Craig William Fellenstein, Joshy Joseph, Rick A. Hamilton II
• Original Assignee: Christopher James Dawson, Craig William Fellenstein, Joshy Joseph, Rick A. Hamilton II
• Inventors: Hamilton, Rick Allen II, Joseph, Joshy, Dawson, Christopher James, Fellenstein, Craig William
• Granted Patent: US 8,276,146 B2
• Time in Patent Office: Days
• US Class Current: 718/104
• 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.

2. The method of claim 1 comprising first steps comprising:

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

determining whether the resource accepted the job;

responsive to the determination that the resource did not accept the job, performing second steps comprising;

randomly selecting a second resource from a plurality of remaining resources;

and

sending the job to the second resource and repeating the steps in claim 2.

3. The method of claim 2 wherein the first steps further comprise:

receiving notification that the job has been submitted to the grid.

4. The method of claim 3 wherein the first steps further comprise:

determining whether a submitting computer is the resource; and

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

5. The method of claim 4 wherein the second steps further comprise:

adding the resource to an attempted resources list.

6. The method of claim 5 wherein the second steps further comprise:

determining the remaining resources capable of executing the job using a resource table;

removing from consideration the resource on the attempted resources list;

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, performing the randomly selecting a second resource from a plurality of remaining resources step.

7. The method of claim 6 wherein the second steps further comprise:

responsive to the determination that remaining resources 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 and waiting a specified amount of time; and

responsive to the determination that the preset number of iterations have been reached, repeating the steps in claim 6.

8. The method of claim 7 wherein the second steps further comprise:

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

9. The method of claim 8 wherein the resource table consists of a plurality of state independent resource properties.

10. The method of claim 9 wherein the local scheduling program comprises:

determining whether the resource can execute the job;

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

executing the job at the resource.

11. The method of claim 10 wherein the local scheduling program further comprises:

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

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

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

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

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

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

determining whether the resource can execute the job;

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

executing the job at the resource.

17. The method of claim 16 further comprising:

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

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

19. The method of claim 18 wherein the resource determines whether the resource can execute the job by examining a plurality of state dependent resource properties.

20. The method of claim 19 wherein a scheduler does not have to keep track of the state dependent resource properties.

21. The method of claim 20 further comprising:

determining whether the resource accepted the job;

responsive to the determination that the resource did not accept the job, performing additional steps comprising;

randomly selecting a second resource from a plurality of remaining resources;

and

sending the job to the second resource and repeating the steps in claim 16.

22. The method of claim 21 further comprising:

receiving notification that the job has been submitted to the grid.

23. The method of claim 22 further comprising:

determining whether a submitting computer is the resource; and

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

24. The method of claim 23 wherein the additional steps further comprise:

adding the resource to an attempted resources list.

25. The method of claim 24 wherein the additional steps further comprise:

determining the remaining resources capable of executing the job using a resource table;

removing from consideration the resource on the attempted resources list;

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, performing the randomly selecting a second resource from a plurality of remaining resources step.

26. The method of claim 25 wherein the additional steps further comprise:

responsive to the determination that remaining resources 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 and waiting a specified amount of time; and

responsive to the determination that the preset number of iterations have been reached, repeating the steps in claim 25.

27. The method of claim 26 wherein the additional steps further comprise:

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

28. The method of claim 27 wherein the resource table consists of a plurality of state independent resource properties.

29. The method of claim 28 wherein any computer connected to the grid can accept the job.

30. The method of claim 29 wherein any computer connected to the grid can schedule the job.

31. A 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 program product comprising:

a memory;

wherein the memory contains instructions for a processor to implement first steps comprising;

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

determining whether the resource accepted the job;

responsive to the determination that the resource did not accept the job, the processor implements second steps comprising;

randomly selecting a second resource from a plurality of remaining resources; and

sending the job to the second resource and repeating the steps in claim 31.

32. The program product of claim 31 wherein the first steps further comprise:

receiving notification that the job has been submitted to the grid.

33. The program product of claim 31 wherein the first steps further comprise:

determining whether a submitting computer is the resource; and

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

34. The program product of claim 31 wherein the second steps further comprise:

adding the resource to an attempted resources list.

35. The program product of claim 31 wherein the second steps further comprise:

determining the remaining resources capable of executing the job using a resource table;

removing from consideration the resource on the attempted resources list;

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, performing the randomly selecting a second resource from a plurality of remaining resources step.

36. The program product of claim 31 wherein the second steps further comprise:

responsive to the determination that remaining resources 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 and waiting a specified amount of time; and

responsive to the determination that the preset number of iterations have been reached, repeating the steps in claim 31.

37. The program product of claim 31 wherein the second steps further comprise:

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

38. The program product of claim 31 wherein the resource table consists of a plurality of state independent resource properties.

39. The program product of claim 31 wherein the local scheduling program comprises:

determining whether the resource can execute the job;

responsive to the determination that the resource can execute the job,

indicating that the resource has accepted the job; and

executing the job at the resource.

40. The program product of claim 31 wherein the local scheduling program further comprises:

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

41. The program product of claim 31 wherein the job is placed in an execution queue prior to being executed.

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

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

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

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

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

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

a memory;

wherein the memory contains instructions for a processor to implement steps comprising;

determining whether the resource can execute the job;

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

and

executing the job at the resource.

46. The program product of claim 45 wherein the steps further comprise:

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

47. The program product of claim 45 wherein the job is placed in an execution queue prior to being executed.

48. The program product of claim 45 wherein the resource determines whether the resource can execute the job by examining a plurality of state dependent resource properties.

49. The program product of claim 45 wherein a scheduler does not have to keep track of the state dependent resource properties.

50. The program product of claim 45 wherein the steps further comprise:

determining whether the resource accepted the job;

responsive to the determination that the resource did not accept the job, performing additional steps comprising;

randomly selecting a second resource from a plurality of remaining resources;

and

sending the job to the second resource and repeating the steps in claim 45.

51. The program product of claim 45 wherein the steps further comprise:

receiving notification that the job has been submitted to the grid.

52. The program product of claim 45 wherein the steps further comprise:

determining whether a submitting computer is the resource; and

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

53. The program product of claim 50 wherein the additional steps further comprise:

adding the resource to an attempted resources list.

54. The program product of claim 50 wherein the additional steps further comprise:

determining the remaining resources capable of executing the job using a resource table;

removing from consideration the resource on the attempted resources list;

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, performing the randomly selecting a second resource from a plurality of remaining resources step.

55. The program product of claim 50 wherein the additional steps further comprise:

responsive to the determination that remaining resources 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 and waiting a specified amount of time; and

responsive to the determination that the preset number of iterations have been reached, repeating the steps in claim 50.

56. The program product of claim 50 wherein the additional steps further comprise:

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

57. The program product of claim 50 wherein the resource table consists of a plurality of state independent resource properties.

60. An apparatus 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 apparatus comprising:

means for receiving notification that the job has been submitted to the grid;

means for determining whether a submitting computer is a resource;

responsive to the determination that the submitting computer is not the resource,

means for sending the job to the closest resource to the submitting computer;

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

means for determining whether the resource accepted the job;

responsive to the determination that the resource did not accept the job, means for performing second steps comprising;

adding the resource 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;

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, 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 and waiting a specified amount of time;

responsive to the determination that the preset number of iterations have been reached, repeating the steps above;

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

responsive to the determination that remaining resources remain, performing the randomly selecting a second resource from a plurality of remaining resources step;

sending the job to the second resource and repeating the steps above;

wherein the resource table consists of a plurality of state independent resource properties.

wherein the local scheduling program comprises;

means for determining whether the resource can execute the job;

responsive to the determination that the resource can execute the job, means for indicating that the resource has accepted the job;

means for executing the job at the resource;

responsive to the determination that the resource cannot execute the job,

means for indicating that the resource has not accepted the job;

wherein the job is placed in an execution queue prior to being executed;

wherein the local scheduling program determines whether the resource can execute the job by examining the state dependent resource properties;

wherein any computer connected to the grid can accept the job; and

wherein any computer connected to the grid can schedule the job.