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

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

We claim:

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.

Description

TECHNICAL FIELD

The invention relates generally to the field of resource reservation and scheduling, and, more specifically, to the field of reserving and scheduling the use of one or more microprocessors.

BACKGROUND OF THE INVENTION

Conventional resource management strategies for real-time application programs have been unsatisfactory. A "real-time application program" is an application program that must execute in a predictable and timely fashion in order to operate properly. Many current efforts to provide resource management for real-time application programs may only manage a static set of resources. In other words, the resource set may not change during the course of operation of the system. Another limitation of many conventional resource management strategies is that they only accommodate one type of resource (i.e., the resources must be homogeneous). An additional limitation of many conventional resource management strategies is that they rely upon the resource or the application program to determine which application program should be allocated a resource and what quantity of the resource should be allocated. Another conventional approach has been to rely upon human experts to correctly assign priorities to tasks within the system. Unfortunately, such human experts typically cannot accurately assign priorities for a dynamic mix of real-time application programs.

The process of determining which threads to execute at which times is generally termed "scheduling" a computer system's CPU. Conventional CPU scheduling is an example of an unsatisfactory conventional resource management strategy for real-time application. A typical conventional scheduling strategy is to divide the processor time resource into "time slices" having a uniform length. At the expiration of a time slice, a conventional scheduler identifies a thread to execute during the next time slice. In a balanced allocation scheme, each ready thread receives one time slice in turn, so that the processor time is divided evenly among the ready threads. In a weighted allocation scheme, each thread specifies the percentage of total processor time it is to receive. The scheduler then uses an accounting process to keep track of the number of time slices each thread has received, and assigns the next time slice to the thread that is furthest from having received its specified percentage. Such time slice scheduling has two significant disadvantages. First, such time slice scheduling can be inefficient because it involves frequent reassignments of the processor. On the other hand, even the weighted allocation scheme does not take into account thread processor requirements finer than the overall percentage of processor time that must be used to successfully schedule multiple threads having significant processor time demands.

The way in which scheduling is performed can significantly impact a user's perception of whether individual threads are performing adequately. Modern multimedia applications, for example, often require substantial processor time, and appear to proceed slowly or jerkily if they do not receive it. To ensure adequate performance, conventional multimedia applications and other real-time applications typically secure exclusive use of the processor, to the exclusion of any other existing threads.

A hardware device connected to a computer system typically interacts with the computer system by raising an assigned one of a set of device interrupts. The computer system typically responds to the interrupt by executing an interrupt handling routine corresponding to the raised interrupt. In conventional operating systems, this device interrupt handling is typically performed preemptively by, when a device interrupt occurs, suspending the normal scheduled processing of threads while executing the interrupt processing routine. As a result, time-critical threads can be suspended for significant periods of time when their execution coincides with device interrupts.

SUMMARY OF THE INVENTION

The preferred embodiment of the present invention provides a resource management mechanism for arbitrating resource requests and resource usage among independent real-time application programs that run simultaneously on a single machine or set of machines. The resource management mechanism is adaptable to installation on a distributed system having separate computer systems by installing the mechanism on each of the computer systems within the distributed system. The resource management mechanism utilizes dynamic feedback to adapt to changing resource availability and resource requirements. In addition, the resource management mechanism is extensible so that the resource management employed in the system accounts for new resources that are added to the system and for resources that are removed from the system. The resource management mechanism separates resource management policy from resource management mechanism such that the mechanism is independent of the policy. The mechanism for implementing policy is generalized so as to facilitate any one of a number of different policies. In the preferred embodiment of the present invention, real-time application programs are resource self-aware in that they are aware of what resources they require and what quantity of those resources they require. The applications negotiate with the resource management mechanism to reserve resources and ensure predictable performance. Programs may perform one or more "activities," and reserve resources oil behalf of a particular one of their activities. Reserved resources are provided to either that activity or to threads making up the activity as a whole by resource providers.

The present invention further provides a method and system for scheduling the execution of threads using optional time-specific scheduling constraints. In a preferred embodiment, a thread scheduling software facility ("the scheduler") uses a unified urgency indicator to schedule the execution of each of a plurality of threads producing predictable performance in which the threads are scheduled to execute when needed. The scheduler maintains an urgency indicator for each thread based either on a time-specific scheduling constraint that specifies an absolute deadline for a specified quantity of work or on a time-general scheduling constraint that specifies a percentage of processor time to be dedicated to the thread, depending on which type of scheduling constraint is specified for the thread. Modern multimedia applications demand time-specific scheduling for acceptable performance, and their threads are examples of threads for which time-specific scheduling constraints are specified. Modern applications generally also specify time-general scheduling constraints for their threads, which specify the percentage of processor time to be dedicated to the execution of the thread in the long term. Many older legacy programs, on the other hand, specify only time-general scheduling constraints for their threads. If no scheduling constraints are specified for a thread, the facility, or another entity such as the operating system, preferably specifies a default time-general scheduling constraint so that the scheduler permits the thread to execute. The threads scheduled by the scheduler preferably include threads for performing device interrupt handling, so that device interrupt handling is scheduled against the tasks performed by other executing programs.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a block diagram depicting a computer system that is suitable for practicing the preferred embodiment of the present invention.

FIG. 2 is a flowchart illustrating the steps that are performed when an activity that is associated with an application program seeks to reserve resources.

FIG. 3 is a block diagram illustrating an example of an activity querying resource providers to determine resource requirements in accordance with the preferred embodiment of the present invention.

FIG. 4 is a flowchart illustrating the steps that are performed by an activity to determine its resource requirements.

FIG. 5 is a block diagram illustrating the submission of a resource set in a reservation request to a resource planner and the resulting reservation calls when the request is granted in accordance with the preferred embodiment of the present invention.

FIG. 6A is a flowchart illustrating the steps that are performed by the resource planner to implement the policy of the preferred embodiment of the present invention.

FIG. 6B is a flowchart illustrating the sub-steps that are performed to perform step 82 of FIG. 6A.

FIG. 7A shows a flowchart of the steps that are performed when an activity changes mode or execution such that its resource needs change substantially enough to warrant renegotiation.

FIG. 7B shows a flowchart of the steps that are performed when events relating to another program change resource usage.

FIG. 7C is a flowchart that illustrates the steps that are performed when a resource provider experiences persistent overload.

FIG. 8 is a block diagram depicting a distributed environment containing multiple computer systems that each contain a separate resource planner.

FIG. 9 is a flowchart illustrating the steps that are performed when an activity requests a resource reservation for a remote resource.

FIG. 10 is a high-level block diagram of the general-purpose computer system upon which the scheduler preferably operates.

FIG. 11 is a data structure diagram showing the creation and modification of a thread data structure in response to receiving a time-general and a time-specific time constraint for a sample thread.

FIG. 12 is a flow diagram showing the steps preferably performed by the scheduler to create a thread data structure when the scheduler receives a time-general scheduling constraint.

FIG. 13 is a flow diagram showing the steps preferably performed by the scheduler to modify a thread data structure when the scheduler receives a time-specific scheduling constraint.

FIG. 14 is a flow diagram showing the steps preferably performed by the scheduler to withdraw a time-specific scheduling constraint when the scheduler receives a request to do so.

FIGS. 15A-15M are data structure diagrams showing the contents of the scheduling status data structure at various times during the scheduling of two sample threads.

FIG. 16 is a flow diagram showing the steps preferably performed by the scheduler to update the scheduling status data structure.

FIG. 17 is a timing graph showing the time executed of the threads whose scheduling is shown in FIGS. 15A-15M.

FIGS. 18A-18F are data structure diagrams showing the contents of the scheduling status data structure that illustrate the inheritance of urgency from a thread that blocks on a resource to the thread that owns the resource.

FIG. 19 is a flow diagram showing the steps preferably performed by the scheduler when an executing thread blocks on a resource.

FIG. 20 is a flow diagram showing the steps preferably performed by the scheduler when an executing thread releases ownership of a resource.

FIG. 21 is a flow diagram showing the steps preferably performed by an interrupt service routine adapted for use with the scheduler.

FIG. 22 is a flow diagram showing the steps preferably performed by a dedicated interrupt service thread.

FIG. 23 is a flow diagram showing the steps preferably performed by the scheduler in the server and client threads.

FIG. 24 is a high-level block diagram showing a computer network in which the scheduler preferably performs scheduling across two individual computer systems.

FIG. 25 is a flow diagram showing the steps preferably performed by the scheduler in the server and client threads on separate computer systems.

DETAILED DESCRIPTION OF THE INVENTION

The preferred embodiment of the present invention provides a resource management mechanism for arbitrating resource requests and resource usage among independent real-time application programs that run simultaneously on a single machine or set of machines. The resource management mechanism is adaptable to installation on a distributed system having separate computer systems by installing the mechanism on each of the computer systems within the distributed system. The resource management mechanism utilizes dynamic feedback to adapt to changing resource availability and resource requirements. In addition, the resource management mechanism is extensible so that the resource management employed in the system accounts for new resources that are added to the system and for resources that are removed from the system. The resource management mechanism separates resource management policy from resource management mechanism such that the mechanism is independent of the policy. The mechanism for implementing policy is generalized so as to facilitate any one of a number of different policies. In the preferred embodiment of the present invention, real-time application programs are resource self-aware in that they are aware of what resources they require and what quantity of those resources they require. The applications negotiate with the resource management mechanism to reserve resources and ensure predictable performance.

A "resource," as used herein, refers to a limited hardware or software quantity that is provided by a machine. Examples of resources include CPU time, memory capacity, I/O bus bandwidth, network bandwidth, and devices, such as video frame buffers and sound cards. Resources may also encompass higher level software-defined resources that manage other resources. Resources are represented in the preferred embodiment of the present invention by objects that manage the resources. These objects are referred to as "resource providers." As will be described in more detail below, resource providers support operations such as allocating amounts of the resources, performing resource accounting, and providing notifications.

The preferred embodiment of the present invention also employs the notion of an "activity." An "activity" is an abstraction that serves as a generalization of a running program and is the unit of abstraction to which resources are allocated and against which resource usage is charged. Each activity is modeled by an activity object. It should be appreciated that an activity may span thread or process boundaries. Further, an activity may span address spaces and machines and may have multiple threads of control associated with it. Typically, however, each activity is associated with a single distinct executing program or application. For example, the operation of playing a video stream may constitute an activity. Similarly, the operation of recording and transmitting video for a video teleconferencing application may constitute an activity.

A "resource planner" is a program that arbitrates access to the resources of a machine amongst different activities. The resource planner tells an activity what amount of a resource, if any, is reserved for use by the activity. The resource planner is knowledgeable about all local resources. Each local resource is registered with the local resource planner. The resource planner monitors what activities are allowed to gain access to a resource and how much of the resource may be granted to each activity. The resource planner may manage multiple resources, and the resources it manages may be of different types. The set of resources managed by the resource planner may change over time. The resource planner, like other components of the resource management mechanism of the preferred embodiment, is implemented as an object.

In general, an activity seeks to reserve resources that it needs before it uses those resources. An activity reserves resources by requesting the reservation of a number of resources from the resource planner. The activity specifies the quantity of each resource it wishes to reserve. The resource planner applies a policy to the request and determines whether the resources should be granted or not in view of pending reservations. If the resources are granted to the activity, the activity may proceed to use the resources. As discussed below, the reservations are utilized in the scheduling of resources. If the request is not granted, the activity should not use the resource because the activity cannot be assured that adequate amounts of the resource will be available for the activity to run predictably.

If the request is granted, for each resource requested, the resource planner preferably conveys the identity of the activity and the amount of the resource requested to a resource provider for the resource. The resource provider then permits the activity to use the requested amount of the resource. In the case of some resources such as the processor resource which must be used on a per-thread basis, however, the resource provider does so by permitting each of the threads that make up the activity to use a portion of the requested amount of the resource. The preferred embodiment of the present invention further provides a thread scheduling software facility ("the scheduler") as a resource provider for scheduling the use of a resource corresponding to processor time. The scheduler uses a unified urgency indicator to schedule the execution of each of a plurality of threads present in a computer system. While the description that follows is directed to the use of the scheduler to schedule the use of one or more processors, it will be appreciated by those skilled in the art that the scheduler may be straightforwardly adapted to schedule the use of other resources comprised of either hardware or software. The scheduler maintains an urgency indicator for each thread based either on a time-specific scheduling constraint that specifies an absolute deadline for a specified quantity of work or on a time-general scheduling constraint that specifies a percentage of processor time to be dedicated to the thread, depending on which type of scheduling constraint is specified for the thread. Modem multimedia applications demand that particular quantities of work be consistently scheduled in a timely fashion for acceptable performance, and their threads are examples of threads for which time-specific scheduling constraints are specified. Modem applications generally also specify time-general scheduling constraints for their threads, which specify the percentage of processor time to be dedicated to the execution of the thread in the long term. Many older legacy programs, on the other hand, specify only time-general scheduling constraints for their threads. If no scheduling constraints are specified for a thread, the facility, or another entity such as the operating system, preferably specifies a default time-general scheduling constraint so that the scheduler permits the thread to execute. The threads scheduled by the scheduler preferably include threads for performing device interrupt handling, so that device interrupt handling is scheduled against the tasks performed by other executing programs.

The indications of urgency used by the scheduler to prioritize the execution of threads are time-sensitive, and reflect the importance of executing a thread at a particular time rather than solely the overall importance of a thread. The scheduler preferably utilizes "restart times" as such indications of urgency. Restart times represent urgency in a time-sensitive way by measuring the time at which a thread needs to begin exclusive execution in order to satisfy a deadline specified for the thread. Given the likelihood that a particular thread will not be allowed to execute exclusively, a thread generally must begin execution substantially before its restart time in order to successfully complete its scheduling constraints. Restart times, however, do reflect the relative priority, or time-sensitive urgency, of a number of threads-the thread with the earliest restart time is the most urgent thread, the thread with the second earliest restart time is the second most urgent thread, etc. The scheduler's use of restart times as indications of urgency is consistent with a minimum laxity first approach, in which threads with the minimum scheduling flexibility are scheduled first. The indications of urgency used by the scheduler preferably also include an indication of criticality. If a thread is critical, it is more urgent than all non-critical threads. If two threads are both critical, the thread with the earlier restart time is more urgent. Criticality is generally used by threads to identify situations in which the degradation of their performance would be unacceptable.

Instead of allocating processor time in fixed-length time slices, the scheduler preferably utilizes custom timer interrupts to assign the processor to a thread for a period of time tailored to reduce the urgency of that thread to slightly below the urgency of the next most urgent thread, or until a more urgent thread becomes ready. This aspect of the invention minimizes the processor time spent scheduling the processor, or "scheduling latency," as the facility may efficiently allocate the processor to a thread for the appropriate amount of time without having to interrupt the thread to reevaluate the schedule.

The scheduler further supports the inheritance of urgency from threads for which a service is being performed (client threads) by threads that are performing that service (server threads). Server threads can include those threads invoked by local and network remote procedure calls and those threads utilized to process device interrupts. Such inheritance may be applied in a transitive manner, such that a first thread inherits urgency from a second thread via a third thread. A thread may also inherit the urgencies of several other threads. Such inheritance has several important advantages. First, the scheduling result of such inheritance is equitable, in that all work done by or on behalf of the same thread is scheduled with the same urgency. Second, such inheritance obviates the need to specify urgencies for dedicated server threads, as such threads will always inherit the varying urgencies of their clients.

Further, in order to more quickly execute a relatively urgent thread that needs to use a resource, such as a mutex synchronization object, being used by a less urgent thread, the scheduler permits the less urgent thread to inherit the urgency of the more urgent thread until the less urgent thread releases the resource. This permits the thread that has inherited the urgency of the more urgent thread to run to the exclusion of more of the ready threads until it releases the resource, at which time the thread that has inherited the urgency of the more urgent thread loses the urgency of the more urgent thread, the more urgent thread becomes ready, and the more urgent thread replaces the less urgent thread as the new running thread.

Further, when operating in computer systems having more than one processor, the scheduler is preferably able to schedule the execution of threads on as many of the processors as desired.

FIG. 1 is a block diagram depicting a computer system 10 that is suitable for practicing the preferred embodiment of the present invention. The computer system 10 includes a central processing unit (CPU) 12 that has access to a primary memory 14 and a secondary storage 16. The primary memory 14 holds a copy of an operating system 18 that is well adapted for running real-time application programs 20 and 22. The operating system 18 provides an object-oriented environment and supports the Microsoft OLE 2.01 protocol. The operating system 18 also includes support for creating a resource planner 24. The primary memory 14 additionally holds a number of resource providers 26 corresponding to the local resources of the computer system 10. The computer system 10 may further include an input/output (I/O) device 28 and a network adapter 30 that connects the computer system 10 with a computer network 32.

Although FIG. 1 depicts a single processor computer system for practicing the preferred embodiment to the present invention, those skilled in the art will appreciate that the present invention may also be practiced in distributed environments. Moreover, the present invention may be practiced in computer systems that have configurations that differ from that depicted in FIG. 1. The depiction in FIG. 1 of the computer system 10 is intended to be merely illustrative and not limiting of the present invention. For example, more than two real-time application programs may be concurrently running on the computer system in some alternative embodiments.

As was mentioned above, in the preferred embodiment of the present invention real-time application programs are resource self-aware. The application programs 20 and 22 know what resources, as well as how much of those resources, they need to have to run properly and predictably. FIG. 2 is a flowchart illustrating the steps that are performed when an activity that is associated with an application program seeks to reserve resources. Initially, the activity determines what resources it needs (step 34 in FIG. 2). This determination involves an information gathering process. In the preferred embodiment of the present invention, the activity queries resource providers to determine what resources the activity needs. The activity is aware of what resource providers it uses, and the activity queries the resource providers it uses to determine what resources are, in turn, needed by those resource providers to perform their job and what quantities of resources are required for the resource providers to perform their job.

In order to more fully understand the information gathering process, it is helpful to understand how the resource providers are logically organized. First, it should be appreciated that the resource providers are modularized. Resource providers may be components of larger modules. An example helps to illustrate this modularity. FIG. 3 depicts an example where an activity 60 needs to exploit disk bandwidth and network bandwidth to perform a network write operation. The activity knows that it must use the file system and the network to perform such a write operation. The file system has an associated file system resource provider 50, and the network has an associated network resource provider 56. In performing the disk read operation, the file system resource provider 50 recognizes that it must call upon the SCSI disk resource provider 52 and the I/O bus resource provider 54 to perform the disk read operation. The network resource provider similarly recognizes that it must call upon the I/O bus resource provider 54 and the asynchronous transfer mode (ATM) adapter 58 to perform the network write operation. Thus, the activity 60 realizes it must use disk bandwidth and network bandwidth, but the activity 60 relies upon the file system resource provider 50 and the network resource provider 56 to determine what additional resources are required to obtain the disk bandwidth and network bandwidth, respectively.

Software components that have real-time resource requirements provide interfaces that expose those requirements to their clients. This allows the clients to query the components about the resources that are needed to perform operations that the client will use. In other words, resource providers support interfaces that allow clients of the resource providers to determine what resources are required for particular operations. An interface, as used herein, is a Microsoft OLE 2.01 interface and refers to a named group of semantically related methods. Objects that implement the code for all of the methods in an interface are said to "support" the interface. Examples of interfaces supported by resource providers that may be queried to obtain resource requirements are the IFileSys, IScsiDisk, IIOBus, INetwork and IAtmCard interfaces shown in FIG. 3.

FIG. 4 is a flowchart that illustrates the steps that arc performed to determine what resources an activity needs (step 34 in FIG. 2). The activity queries the resource providers in a modular fashion (step 64 in FIG. 4). The queries are represented in FIG. 3 by arrows 59A, 59B, 59C, 59D, 59E and 59F. The queries are implemented as calls to methods in interfaces supported by the resource providers. The activity 60 sums the resources required by each of the resource providers it calls and adds any resources required by operations that it directly implements. Thus, for example in FIG. 3, the file system resource provider 50 is a client of the SCSI disk resource provider 52 and the I/O bus resource provider 54. The resource requirements of the file system resource provider 60 to perform the network read operation requested by the activity 60 includes the resource requirements of both the SCSI disk resource provider to perform its role in the operation, the resource requirements of the I/O bus resource provider 54 to perform its role, and the separate resource requirements of the file system resource provider 50. The resource requirements of the activity 60 are the cumulative resource requirements of the file system resource provider 50 and the network resource provider 56 in performing the network read operation. The resource requirements of the file system resource provider 50 and the network resource provider 56 reflect resource requirements of the modular components that are called by those resource providers. Thus, in step 66 of FIG. 4, the resources requirements of the modules are summed along with the direct resource requirements to determine the cumulative resource requirements for the activity.

Another alternative for determining resource requirements is to empirically determine what resources are used by an activity and to use the empirical determination as the basis for the resource requirements that are later requested. Such empirical estimates may be cached by an activity 60, by the operating system 18 or even by the resource planner 62. This alternative has the benefit of using less mechanism by clients because the alternative does not require the querying that is used in the above-described approach.

The above discussion has assumed that an activity knows how to determine what resources it needs. It may be helpful, in some instances, to provide system support for assisting an activity in determining the activity's resource requirements. The operating system 18 may provide support for an activity to readily determine its resource requirements for system operations that are available in the operating system application program interface (API) set. For example, if the user requests a read operation, the operating system 18 may provide a mechanism for determining the appropriate resource requirements for such an operation. Another alternative is for the system to record what resources are utilized during a read and cache those values so that the values are returned to the activity for use in making a resource reservation request.

Once the activity determines what resources it needs and the quantity of those resources it needs, the activity sends a request for the determined quantities of resources to local resource planner to obtain a reservation (step 36 in FIG. 2). The request that is submitted by the activity holds a "resource set." The resource set specifies what resources are requested and what quantity of those resources are requested. The resource set includes a number of pairs of resources and resource amounts. More formally, each pair of a resource set includes a reference to an IResource interface supported by a particular resource along with an amount specified in terms of the units of that resource. The IResource interface will be described in more detail below.

The amount value in a resource set pair is resource specific. For example, for CPU time, which is modeled as a resource, the resource amount is specified as a number of units per second of total CPU capacity per second. The total CPU capacity is viewed as 10 million units per second.

Each resource set is implemented as an object that supports the IResource set interface. This interface is formally defined as follows:

    __________________________________________________________________________
    interface IResourceSet: IUnknown {
    import "mmtype.idl";
    import "actvty.idl";
    import "resour.idl";
    import "eresst.idl";
    SCODE AddAmount([in]IResource *Resource, [in]  RESOURCE.sub.-- AMOUNT
    Amount,
            [out]  IResourceSet **pResSetResult);
    // Adds a resource and its amount to the set. Adds the resource to
    // the set if necessary, otherwise adjusts the amount. Returns a new
    // resource set with the addition included; original is unmodifled.
     SCODE GetAmount([in]  IResource *Resource, [out]  RESOURCE.sub.--
    AMOUNT
                        *Amount);
           // Gets the amount of a particular resource in the set.
    // Returns 0.0 as the amount if the resource is not in the set.
      SCODE Add([in]  IResourceSet *Addend, [out]  IResourceSet **Result);
           // Adds the contents of the specifled set to this set and returns
    // the result. Resource amounts are added if present in both sets.
    // Returns a new resource set with the addition included; original is
    // unmodified.
       SCODE Subtract([In] IResourceSet * Subtrahend, [out]  IResourceSet
    **Result);
            // Subtracts the contents of the subtrahend from this set. Used
    // e.g. to figure out what amount of a set of resources must become
    // available to satisfy a request. Returns a new resource set with
    // the modification included; original is unmodifled.
       SCODE Enumerate([out]  IEnumResourceSet **ppenm);
            // Returns enumerator for this resource set.
       SCODE CheckFree();
            // Returns S.sub.-- TRUE if enough of each resource in the set is
    free
    // to reserve the amount associated with that resource.
       SCODE GetFree([out]  IResourceSet **Free);
            // Returns a resource set with the same resources as this one,
    with
    // the amount associated with each resource in the set equal to the
    // amount currently free.
       SCODE Reserve([in]  IActivity *Activity, [out]  IResourceSet
    **Available);
           // Tries to reserve each resource in the set, in the amount
    // associated with it. Returns S.sub.-- OK if al1 succeeded; the output
    // resource set pointer is NULL. Returns S.sub.-- FALSE otherwise; no
    // resources are allocated, and the output resource set contains the
    // amount currently available of each requested resource.
    // Note: Intended for use by the resource planner.
       SCODE Testlntersect([in]  IResourceSet *IntersectWith);
           // Return S.sub.-- TRUE if there are resources in common between
    the two
    // resource sets S.sub.-- FALSE otherwise.
    __________________________________________________________________________

    __________________________________________________________________________
    interface IResource: IUnknown {
      import "mmtype.idl";
    import "actvty.idl";
    import "respln.idl";
    SCODE Total Amount([out]  RESOURCE.sub.-- AMOUNT*Total);
            // Get the total amount of a resource.
       SCODE Reserve([in]  IActivity *Client, [in]  RESOURCE.sub.-- AMOUNT
    Amount,
                        [out]  RESOURCE.sub.-- AMOUNT *Actual);
            // Set the amount reserved of a resource for a particular
    client.
    // Upon return, return value Will be S.sub.-- TRUE if the resource
    amount
    // was granted. In this case, Actual Will return the actual amount
    // of the resource granted. If the full amount requested could not
    // be granted, return value will be FALSE and Actual will return the
    // amount of the requested resource that is currently available. If
    // the amount reserved is less than the previous reservation then
    // some of the reservation will have been given back. The amount can
    // be zero, in which case the entire existing reservation is being
    // given back.
    // Note: This operation intended for use by the resource planner.
       SCODE GetReservation([in]  IActivity *Client,
                        [out]  RESOURCE.sub.-- AMOUNT *Amount);
            // Get the amount of the resource currently reserved for the
    client.
       SCODE GetUsage([in]  IActivity *Client, [out]  RESOURCE.sub.-- AMOUNT
    *Amount)
           // Get the usage of the client since the last call to this
    method.
       SCODE GetFree([out]  RESOURCE.sub.-- AMOUNT *Amount);
           // Get the amount of the resource that is not currently reserved
    at
    // the time of the call.
    __________________________________________________________________________

    __________________________________________________________________________
    interface IResourcePlanner: IUnknown {
      import "mmtype.idl";
    import "resset.idl";
    import "actvty.idl";
    import "actnfy.idl";
    //
    // Resource plan elements currently consist of a resource set.
    // May later be extended to pass additional inforrnation to the planner.
    //
    typedef IResourceSet *PlanElement;
    SCODE RequestResources([in]  IActivity *Activity, [in]  long
    cPlanElements,
              [in, size.sub.-- is(cP1anElements)]  PlanElement PlanElements[
            ],
            [in]  IActivityNotify *NotificationInterface,
            [out]  long *Granted, [out]  IResourceSet **Actual);
      // Request resources for an activity. Upon return, if the resources
    // could not be granted, Granted will be -1 and Actual will return
    // the amounts of the requested resources that are currently
    // available. Otherwise, Granted will be the index of the plan element
    // corresponding to the resource set that was granted. In this case,
    // Actual will return the actual amount of each resource granted.
    // The plan elements requested are ordered in decreasing value to the
    // application. The activity also supplies its resource notification
    // interface pointer to the planner at this time.
      SCODE ReleaseResources([in]  IActivity *Activity);
           // Frees all resources reserved by an activity.
      SCODE CreateResourceSet(
                        [in]  IResource *Resource, [in]  RESOURCE.sub.--
            AMOUNT Amount,
            [out]  IResourceSet **ResourceSet);
           // Creates a resource set. If the resource provided is NULL then
    // an empty resource set is returned. If a resource is provided
    // then a singleton resource set with the resource and amount
    // specifled is returned.
    __________________________________________________________________________

    __________________________________________________________________________
    interface IResourcePlannerPolicy : IUnknown {
       import "mmtype.idl";
    import "resset.idl";
    import "actvty.idl";
     SCODE SetImportance([in]  IActivity *Activity, [in]  IMPORTANCE
    Importance);
     // Inform the resource planner that the indicated activity has
    // transitioned to the specified importance. This may trigger a
    // resource negotiation.
      SCODE GetImportance([in]  IActivity *Activity, [out] IMPORTANCE
    *Importance);
      // Get the current importance level for an activity.
      SCODE OnOverload([in]  IActivity *Activity,
                    [in]  IResource *Overloaded, [in]  RESOURCE.sub.-- AMOUNT
            AmountUsed);
           // Tell resource planner that an activity has consistently used
    more
    // of a resource than it has reserved.
    __________________________________________________________________________

    __________________________________________________________________________
     interface IActivityNotify: IUnknown {
      import "mmtype.idl";
    import "resset.idl";
    import "actvty.idl";
    SCODE OnOverload([in]  IActivity *Activity,
            [in]  IResource *Overloaded, [in]  RESOURCE.sub.-- AMOUNT
            AmountUsed);
           // Tell an activity that it has consistently used more of a
    // resource than it has reserved.
      SCODE OnNeed([in]  IActivity *Activity, [in]  IResourceSet *Shortage);
           // Tell an activity that other activities need a set of resources
    // more than it does. The Shortage resource set says which resources
    // are needed, and how much.
      SCODE OnAvailable([in]  IActivity *Activity, [in]  IResourceSet
    *Available);
    // Tell an activity that additional resources have become available
    // that it may wish to negotiate for. The Available resource set
    // says which additional resources are now available, and how much.
     }
    __________________________________________________________________________

• Inventors
  Jones, Michael B.; Leach, Paul J.; Draves, Jr., Richard P.; Barrera, III, Joseph S.; Levi, Steven P.; Rashid, Richard F.; Fitzgerald, Robert P.;
• Assignee
  Microsoft Corporation (Redmond, WA)
• Published
  Dec-14-1999
• Current US Classes:
  718/102
  718/104
• Application #
  569048
• International Classes
  G06F 009/00
• 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
• Examiner
  Banankhah; Majid A.
• Agent
  Seed and Berry LLP
• US Patent References:
  5303369
  5388097
  5581703
  5586264
  5640595