Resource-based scheduler

• US 20080086734A1
• Filed: 10/10/2006
• Published: 04/10/2008
• Est. Priority Date: 10/10/2006
• Status: Active Grant

• Current Assignee: InvisiTasking, LLC (Condusiv Technologies Corporation)
• Original Assignee: InvisiTasking, LLC (Condusiv Technologies Corporation)
• Inventors: Jensen, Craig, Staffer, Andrew, Cadruvi, Richard, Thomas, Basil
• Granted Patent: US 9,588,809 B2
• Time in Patent Office: Days
• US Class Current: 718/104
• CPC Class Codes: G06F 2209/485 Resource constraint
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

Resource-based scheduling of computer jobs is disclosed. A computer job is scheduled based on utilization of a resource and a utilization criterion that the computer job has pertaining to the resource, in accordance with an embodiment of the present invention.

Claims

1. A machine-implemented method comprising the steps:

based on utilization of a particular resource and a utilization criterion pertaining to the particular resource and associated with a particular computer job, determining whether to schedule the particular computer job to utilize the particular resource.

2. The method of claim 1, further comprising:

determining expected utilization of the particular resource by the computer job, wherein the utilization criterion is based on the expected utilization.

3. The method of claim 2, wherein the step of determining expected utilization comprises examining instructions in the computer job.

4. The method of claim 2, wherein the step of determining expected utilization comprises:

accessing a value that describes previous utilization of the particular resource by the computer job; and

basing the expected utilization on the stored value that describes previous utilization.

5. The method of claim 1, further comprising receiving the utilization criterion from an application program owning the computer job.

6. The method of claim 1, further comprising placing the computer job on at least one of a plurality of resource-based scheduling worklists.

7. The method of claim 1, further comprising:

for each of a plurality of computer jobs to be scheduled for execution, placing the computer job on at least one of a plurality of resource-based scheduling worklists that correspond to a plurality of computer resources, and wherein a given resource-based scheduling worklist comprises computer jobs that are waiting to utilize the given computer resource.

8. The method of claim 7, further comprising:

selecting a particular computer resource to be utilized by one of the plurality of computer jobs.

9. The method of claim 1, wherein determining whether to schedule the particular computer job to utilize the particular resource is performed by an operating system.

10. The method of claim 1, wherein determining whether to schedule the particular computer job to utilize the particular resource is performed by a resource-based scheduler outside of an operating system.

11. The method of claim 1, further comprising determining the utilization of the particular resource.

12. The method of claim 1, further comprising estimating projected utilization of the particular resource over an interval.

13. The method of claim 12, wherein determining whether to schedule the particular computer job to utilize the particular resource is based on the projected utilization of the particular resource over the interval and the utilization criteria.

14. The method of claim 1, wherein the step of determining whether to schedule the particular computer job to utilize the particular resource is further based on utilization of another resource and a utilization criterion associated with the particular computer job that pertains to the other resource.

15. The method of claim 1, wherein the utilization of the particular resource is based on an amount of time of utilization of the particular resource.

16. The method of claim 1, wherein the utilization of the particular resource is based on a number of requests to use the particular resource.

17. A machine-implemented method comprising the steps:

placing each of a plurality of computer jobs on at least one of a plurality of resource-based scheduling worklists that correspond to a plurality of computer resources, wherein a given resource-based scheduling worklist comprises computer jobs each having a utilization criterion pertaining to the given resource;

selecting a particular computer resource to be utilized by one of the plurality of computer jobs; and

based on utilization of the particular computer resource and the utilization criterion of at least one of the computer jobs on the worklist for the particular computer resource, selecting one of the computer jobs to utilize the particular computer resource.

18. The method of claim 17, further comprising assigning a priority to each of the plurality of computer resources.

19. The method of claim 18, wherein the step of selecting a particular computer resource to be utilized by one of the plurality of computer jobs is based on the priority assigned to each of the plurality of computer resources.

20. The method of claim 18, wherein assigning a priority to the plurality of computer resources is based on relative speed of the plurality of computer resources.

21. The method of claim 17, wherein the step of selecting one of the computer jobs to utilize the particular computer resource is further based on a priority at least one of the computer jobs on the worklist for the particular computer resource.

22. The method of claim 17, wherein selecting one of the computer jobs to utilize the particular computer resource during the interval comprises:

identifying one of the computer jobs on the worklist for the particular resource; and

if the estimated utilization of the particular resource indicates sufficient available capacity to satisfy the utilization criterion of the particular computer job, scheduling the particular computer job for execution using the particular resource.

23. The method of claim 17, further comprising:

determining expected utilization of the particular resource by a first computer job, wherein the utilization criterion for first computer job is based on the expected utilization.

24. The method of claim 23, wherein the step of determining expected utilization comprises examining instructions in the first computer job.

25. The method of claim 23, wherein the step of determining expected utilization comprises:

accessing a value that describes previous utilization of the particular resource by the first computer job; and

basing the expected utilization on the stored value that describes previous utilization.

26. The method of claim 17, further comprising receiving the utilization criterion from an application that owns the first computer job.

27. The method of claim 17, wherein selecting one of the computer jobs to utilize the particular computer resource is performed by an operating system.

28. The method of claim 17, wherein the step of selecting one of the computer jobs to utilize the particular computer resource is performed by a resource-based scheduler outside of an operating system.

29. The method of claim 17, further comprising determining the utilization of the particular resource.

30. The method of claim 17, wherein the step of determining whether to schedule the particular computer job to utilize the particular resource is further based on utilization of another resource and a utilization criterion associated with the particular computer job that pertains to the other resource.

31. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more computer processors, cause the one or more computer processors to carry out the steps of:

based on utilization of a particular resource and a utilization criterion pertaining to the particular resource and associated with a particular computer job, determining whether to schedule the particular computer job to utilize the particular resource.

32. The method of claim 31, wherein the step of determining whether to schedule the particular computer job to utilize the particular resource is further based on utilization of another resource and a utilization criterion associated with the particular computer job that pertains to the other resource.

33. A system, comprising:

one or more computer processors, and;

a computer-readable medium communicatively coupled to the one or more computer processors, wherein the computer-readable medium has stored thereon one or more stored sequences of instructions which, when executed by the one or more computer processors, cause the one or more computer processors to perform;

based on utilization of a particular resource and a utilization criterion pertaining to the particular resource and associated with a particular computer job, determining whether to schedule the particular computer job to utilize the particular resource.

34. The method of claim 33, wherein the step of determining whether to schedule the particular computer job to utilize the particular resource is further based on utilization of another resource and a utilization criterion associated with the particular computer job that pertains to the other resource.

35. A machine-implemented method comprising the steps:

receiving requests from a plurality of computer jobs, wherein each request requires utilization of a particular resource to satisfy the request, and

based on utilization of the particular resource and utilization criterion that each of the computer jobs have pertaining to the particular resource, determining a scheduling order for the computer jobs to utilize the particular resource.

36. The method of claim 35, wherein at least a portion of the requests require utilization of another resource to satisfy the request;

and wherein the step of determining a scheduling order for the computer jobs to utilize the particular resource is further based on utilization criterion that the computer jobs associated with the portion of requests have pertaining to the other resource.

37. The method of claim 35, wherein the utilization of the particular resource is based on an amount of time of utilization of the particular resource.

38. The method of claim 35, wherein the utilization of the particular resource is based on the number of requests that require utilization of the particular resource to satisfy the request.

39. The method of claim 35, wherein determining a scheduling order for the computer jobs to utilize the particular resource is performed by an operating system.

40. The method of claim 35, wherein determining a scheduling order for the computer jobs to utilize the particular resource is performed by a resource-based scheduler outside of an operating system.

41. A machine-implemented method comprising the steps:

receiving requests from a plurality of computer jobs, wherein each request requires utilization of one or more of a plurality of resources to satisfy the request,

selecting a particular resource to have a computer job scheduled to utilize; and

based on utilization of the particular resource and utilization criterion that each of the computer jobs that require utilization of the particular resource have pertaining to the particular resource, determining a scheduling order for the computer jobs that require utilization of the particular resource.