Method and system for scheduling the use of a computer system resource using a resource planner and a resource provider

• US 6,003,061 A
• Filed: 12/07/1995
• Issued: 12/14/1999
• Est. Priority Date: 12/07/1995
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Jones, Michael B., Leach, Paul J., Rashid, Richard F., Fitzgerald, Robert P., Levi, Steven P., Draves, Richard P. Jr., Barrera, Joseph S. III
• Primary Examiner(s): Banankhah, Majid A.
• Application Number:
  US08/569,048
• Time in Patent Office: 1,468 Days
• Field of Search: 395/674, 395/200, 395/672, 395/680, 395/200.55, 395/830, 395/200.49, 370/455, 709/102, 709/103, 709/104
• US Class Current: 718/104
• CPC Class Codes: G06F 2209/5014 Reservation
• CPC Class Codes: G06F 9/50 Allocation of resources, e.g. of the central processing unit [CPU]

Abstract

A method and system for scheduling the use of a computer system resource using a resource planner and a resource provider is provided. In a preferred embodiment, a resource is scheduled for use by a plurality of consumer entities. Each consumer entity may request the commitment of a share of the resource. The method and system utilizes representations of resource usage policy, present commitments of shares of the resource, and present commitments of specified amounts of the resource over specified period of time. The method and system first receives a request from a consumer entity for the commitment of a specified share of the resource. In response, the method and system determines whether the specified share of the resource should be committed to the requesting consumer entity. This determination is based on the representations of resource usage policy and present commitments of shares of the resource. If it is determined that the specified share of the resource should be committed to the requesting consumer entity, then the method and system modifies the representation of present commitments of shares of the resource to commit the specified share of the resource to the requesting consumer entity. The method and system then schedules the use of the resource by the plurality of consumer entity based on the modified representation of present commitments of shares of the resource.

Claims

1. A method in a computer system for managing the use of a resource of the computer system by a plurality of consumer entities, wherein each consumer entity may request the commitment of a share of the resource, and wherein the method utilizes representations of resource usage policy, present commitments of shares of the resource, and present commitments of specified amounts of the resource over specified periods of time, the method including the steps of:

(a) receiving a request from a requesting consumer entity for a commitment of a specified share of the resource;

(b) in response to step (a), based on the specified share of the resource, the representations of resource usage policy, and present commitments of shares of the resource, determining whether the specified share of the resource should be committed to the requesting consumer entity;

(c) if it is determined in step (b) that the specified share of the resource should be committed to the requesting consumer entity, modifying the representation of present commitments of shares of the resource to commit the specified share of the resource to the requesting consumer entity; and

(d) scheduling the use of the resource by the plurality of consumer entities in accordance with the modified representation of present commitments of shares of the resource.

2. The method of claim 1 wherein each entity may further request the commitment of a specified amount of the resource over a specified period of time, further including the steps of:

(e) receiving a request from the requesting consumer entity for a commitment of a specified amount of the resource over a specified period of time; and

(f) in response to step (e), modifying the representation of present commitments of specified amounts of the resource over specified periods of time to commit the specified amount of the resource to the requesting consumer entity over the specified period of time, and wherein step (d) includes the step of scheduling the use of the resource by the plurality of consumer entities based on the modified representation of present commitments of specified amounts of the resource over specified periods of time.

3. The method of claim 1, further including the step of, based on the modified representation of present commitments of shares of the resource, determining whether the specified amount of the resource over the specified period of time should be committed to the requesting consumer entity, and wherein step (f) is performed only if it is determined that the specified amount of the resource over the specified period of time should be committed to the requesting consumer entity.

4. The method of claim 1, further including the steps of, if it is determined in step (b) that the specified share of the resource should not be committed to the requesting consumer entity:

omitting to modify the representation of present commitments of shares of the resource to commit the specified share of the resource to the requesting consumer entity;

determining an alternate share of the resource that could be committed to the requesting consumer entity based on the representations of resource usage policy and present commitments of shares of the resource; and

communicating the determined alternate share of the resource to the requesting consumer entity.

5. The method of claim 1 wherein the request received from the requesting consumer entity for a commitment of a specified share of the resource in step (a) specifies a plurality of alternative shares of the resource, and wherein step (b) includes the step of selecting one of the specified alternative shares of the resource that may be committed to the requesting consumer entity in view of the representations of resource usage policy and present commitments of shares of the resource.

6. The method of claim 5, further including the step of identifying the selected alternative shares of the resource to the requesting consumer entity.

7. The method of claim 1 wherein each consumer entity is an application program.

8. The method of claim 1 wherein each consumer entity is an activity comprised of one or more threads.

9. The method of claim 1 wherein each consumer entity is a thread.

10. The method of claim 1 wherein the resource is a single microprocessor module.

11. The method of claim 1 wherein the resource is a microprocessor array containing a plurality of microprocessors.

12. A method in a computer system for managing, the use of a resource of the computer system by a plurality of consumer entities, wherein each consumer entity may request the commitment of a specified amount of the resource over a specified period of time, and wherein the method utilizes representations of present commitments of shares of the resource and present commitments of specified amounts of the resource over specified periods of time, the method including the steps of:

(a) receiving a request from the requesting consumer entity for a commitment of a specified amount of the resource over a specified period of time;

(b) in response to step (a), modifying the representation of present commitments of specified amounts of the resource over specified periods of time to commit the specified amount of the resource to the requesting consumer entity over the specified period of time; and

(c) scheduling the use of the resource by the plurality of consumer entities in accordance with the representation of present commitments of shares of the resource and on the modified representation of present commitments of specified amounts of the resource over specified periods of time.

13. The method of claim 12, further including the step of, based on the representation of present commitments of shares of the resource, determining whether the specified amount of the resource over the specified period of time should be committed to the requesting consumer entity, and wherein step (b) is performed only if it is determined that the specified amount of the resource over the specified period of time should be committed to the requesting consumer entity.

14. The method of claim 12 wherein each consumer entity is an application program.

15. The method of claim 12 wherein each consumer entity is an activity comprised of one or more threads.

16. The method of claim 12 wherein each consumer entity is a thread.

17. The method of claim 12 wherein the resource is a single microprocessor module.

18. The method of claim 12 wherein the resource is a microprocessor array containing a plurality of microprocessors.

19. An apparatus for managing the use of a resource of a computer system by a plurality of consumer entities, comprising:

a resource planner module for processing requests for reservations for shares of the resource each received from one of the plurality of consumer entities, comprising;

a policy module for determining, for each received reservation request, whether approving the reservation request would be consistent with resource usage policies encoded in the policy module,

a capacity module for determining, for each received reservation request, whether the resource has sufficient unreserved capacity to approve the reservation request, and

a request discriminator that, for each received reservation request, based on the determinations made by the policy module and capacity module for the reservation request, approves or denies the reservation request, and, for approved reservation requests, forwards an indication of the approved reservation request to a resource provider module; and

the resource provider module for granting use of the resource to up to a maximum number of consumer entities at one time based upon the reservations managed by the resource planner module, comprising;

a reservation receiver for receiving the indications of approved reservation requests forwarded by the resource planner module, and

a scheduler module for scheduling the use of the resource by consumer entities among the plurality of consumer entities in a manner that comports with approved reservation requests identified by the indications received by the reservation receiver.

20. The apparatus of claim 19 wherein the resource provider module further provides a capacity interface that may be used to determine the unreserved capacity of the resource, and wherein the capacity module of the resource planner module utilizes the capacity interface of the resource provider module to determine the unreserved capacity of the resource.

21. The apparatus of claim 19 wherein the resource provider module further comprises a usage request receiver for receiving from resource consumers requests for use of the resource, and wherein the scheduler module further schedules the use of the resource by consumer entities among the plurality of consumer entities in a manner designed to satisfy usage requests received by the usage request receiver.

22. The apparatus of claim 21 wherein the usage request receiver is a time specific scheduling constraint receiver for receiving from consumer entities time specific scheduling constraints each specifying a deadline and a quantity of resource usage to be scheduled by the deadline for the consumer entity from which the time specific scheduling constraint was received, and wherein the scheduler module schedules use of the resource by consumer entities among the plurality of consumer entities in a manner that, for each time specific scheduling constraint received by the time specific scheduling constraint receiver, enables the consumer entity from which the time specific scheduling constraint was received to use the quantity of the resource specified by the time specific scheduling constraint by the deadline specified by the time specific scheduling constraint.

23. The apparatus of claim 21 wherein the resource provider module further comprises:

an overload detection module that identifies received usage requests whose satisfaction would cause the scheduled use of the resource by the consumer entity from which the usage request was received to exceed the approved reservation for the consumer entity from which the usage request was received; and

a usage request discriminator that prevents the resource provider module from immediately scheduling the use of the resource in accordance with usage requests identified by the overload detection module.

24. The apparatus of claim 21 wherein the resource provider module further comprises:

an overload detection module that identifies received usage requests whose satisfaction would cause the scheduled use of the resource by the consumer entity from which the usage request was received to exceed the approved reservation for the consumer entity from which the usage request was received; and

an overload notification module that, for each usage request identified by the overload detection module, notifies the resource planner module that the consumer entity from which the usage request was received has exceeded its approved reservation.

25. The apparatus of claim 19 wherein the managed resource is a microprocessor, and wherein the resource provider module grants use of the microprocessor to a maximum of one consumer entity at one time.

26. The apparatus of claim 19 wherein the managed resource is a microprocessor array containing a plurality of microprocessors, and wherein the resource provider module grants use of the microprocessor array at one time to up to a maximum number of consumer entities equal to the number of microprocessors contained in the microprocessor array.

27. The apparatus of claim 19, further including a network for transmitting data between the computer system and other computer systems, and wherein the managed resource is bandwidth of the network.

28. The apparatus of claim 19, further including a data bus for transmitting data within the computer system, and wherein the managed resource is bandwidth of the data bus.

29. The apparatus of claim 19, further including a memory for storing information, and wherein the managed resource is the memory.

30. The apparatus of claim 19, further including a storage device and a storage device communication bus for transmitting data between the storage device and the rest of the computer system, and wherein the managed resource is bandwidth of the storage device communication bus.

31. The apparatus of claim 19 wherein the consumer entities are each a thread.

32. The apparatus of claim 19 wherein the consumer entities are each an activity comprised of one or more threads.

33. The apparatus of claim 19 wherein the consumer entities are each an application program.

34. In a computer system having resources including a processor contained in the computer system, a resource planner for granting reservations of the resources to activities, and a scheduler for scheduling threads to execute on the computer system, a method comprising the computer-implemented steps of:

providing a program for execution on the computer system wherein the program uses at least some of the resources, the program including a plurality of threads and the program performing one or more activities that require use of at least a portion of the resources;

for at least a selected one of the activities performed by the program, requesting a reservation from the resource planner for amounts of resources that are used by the selected activity;

with the resource planner, granting the program a reservation for the amounts of the resources that are used by the selected activity including the processor;

specifying scheduling constraints for the execution of one or more threads in the selected activity, said scheduling constraints indicating the relative immediate urgency of scheduling the execution of each thread; and

with the scheduler, scheduling execution of the threads of the selected activity using both the reservation for the processor resource granted by the resource planner and the scheduling constraints specified for the threads in the selected activity.

35. The computer system of claim 34 wherein the resource planner is comprised of:

a policy module for implementing a policy for arbitrating among requests to reserve resources; and

an independent planning engine that is separate from the policy module but that implements the policy of the policy module in granting reservations to the programs to use shares of at least some of the resources.

36. The method of claim 35 wherein the resource planner includes a different policy module for implementing a second policy for arbitrating among requests to reserve resources and wherein the method further comprises the step of using the second policy in the independent planning engine.

37. The method of claim 35 wherein the resource planner is an object and the policy module is an interface supported by the resource planner.

38. The method of claim 34 wherein the requesting step is performed with the program.

39. The method of claim 34 wherein the requesting step is performed with a default reservation subsystem when no reservation is requested with the program.

40. The method of claim 39 wherein the default reservation system is part of the scheduler.

41. The computer system of claim 34 wherein each resource has a maximum capacity, and wherein at least one of the resources has unreserved capacity corresponding to the difference between the maximum capacity of the resource and the sum of the shares of the resource reserved by the resource planner module, and wherein the scheduler further schedules any unreserved capacity of each resource without regard for the reservations issued by the resource planner module.

42. The computer system of claim 34 wherein portions of the resources whose use is scheduled by the scheduler may be either used or unused by the non-real-time-programs or real-time programs for whose use the resources are scheduled by the scheduler module, and wherein the scheduler further reschedules the use of any unused portions of the resources without regard for the reservations issued by the resource planner module.

43. A computer-readable medium whose contents cause a computer system to manage the use of a resource of the computer system by a plurality of consumer entities, wherein each consumer entity may request the commitment of a share of the resource and wherein the method utilizes representations of resource usage policy, present commitments of shares of the resource, and present commitments of specified amounts of the resource over specified periods of time by performing the steps of:

(a) receiving a request from a requesting consumer entity for a commitment of a specified share of the resource;

(b) in response to step (a), based on the specified share of the resource representations of resource usage policy and present commitments of shares of the resource, determining whether the specified share of the resource should be committed to the requesting consumer entity;

(c) if it is determined in step (b) that the specified share of the resource should be committed to the requesting consumer entity, modifying the representation of present commitments of shares of the resource to commit the specified share of the resource to the requesting consumer entity; and

(d) scheduling the use of the resource by the plurality of consumer entities based on the modified representation of present commitments of shares of the resource.

44. A computer-readable medium whose contents cause a computer system to manage the use of a resource of the computer system by a plurality of consumer entities, wherein each consumer entity may request the commitment of a specified amount of the resource over a specified period of time, and wherein the method utilizes representations of present commitments of shares of the resource and present commitments of specified amounts of the resource over specified periods of time, by performing the steps of:

(a) receiving a request from the requesting consumer entity for a commitment of a specified amount of the resource over a specified period of time;

(b) in response to step (a), modifying the representation of present commitments of specified amounts of the resource over specified periods of time to commit the specified amount of the resource to the requesting consumer entity over the specified period of time; and

(c) scheduling the use of the resource by the plurality of consumer entities based both on the representation of present commitments of shares of the resource and on the modified representation of present commitments of specified amounts of the resource over specified periods of time.