US6003061A — Method and system for scheduling the use of a com…

Claim 1

Independent Claim 212 words

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.

Claim 2

Independent Claim 212 words

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.

Claim 3

Dependent Claim 138 words

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.

Claim 4

Dependent Claim 77 words

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.

Claim 5

Dependent Claim 105 words

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.

Claim 6

Dependent Claim 80 words

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.

Claim 7

Dependent Claim 23 words

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

Claim 8

Dependent Claim 13 words

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

Claim 9

Dependent Claim 18 words

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

Claim 10

Dependent Claim 12 words

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

Claim 11

Dependent Claim 13 words

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

Claim 12

Dependent Claim 17 words

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

Claim 13

Independent Claim 191 words

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.

Claim 14

Independent Claim 191 words

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.

Claim 15

Dependent Claim 76 words

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.

Claim 16

Dependent Claim 13 words

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

Claim 17

Dependent Claim 18 words

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

Claim 18

Dependent Claim 12 words

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

Claim 19

Dependent Claim 13 words

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

Claim 20

Dependent Claim 17 words

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

Claim 21

Independent Claim 233 words

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.

Claim 22

Independent Claim 233 words

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.

Claim 23

Dependent Claim 54 words

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.

Claim 24

Dependent Claim 62 words

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.

Claim 25

Dependent Claim 129 words

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.

Claim 26

Dependent Claim 88 words

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.

Claim 27

Dependent Claim 95 words

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.

Claim 28

Dependent Claim 33 words

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.

Claim 29

Dependent Claim 53 words

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.

Claim 30

Dependent Claim 30 words

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.

Claim 31

Dependent Claim 28 words

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.

Claim 32

Dependent Claim 20 words

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

Claim 33

Dependent Claim 43 words

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.

Claim 34

Dependent Claim 13 words

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

Claim 35

Dependent Claim 19 words

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

Claim 36

Dependent Claim 14 words

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

Claim 37

Dependent Claim 213 words

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.

Claim 38

Dependent Claim 213 words

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.

Claim 39

Dependent Claim 64 words

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.

Claim 40

Dependent Claim 44 words

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.

Claim 41

Dependent Claim 24 words

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

Claim 42

Dependent Claim 14 words

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

Claim 43

Dependent Claim 24 words

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

Claim 44

Dependent Claim 15 words

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

Claim 45

Dependent Claim 73 words

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.

Claim 46

Dependent Claim 67 words

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.

Claim 47

Dependent Claim 212 words

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.

Claim 48

Dependent Claim 212 words

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.

Claim 49

Dependent Claim 193 words

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.

Claim 50

Dependent Claim 193 words

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.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2002-12-13	2003-06-14	2003-12-14	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2006-12-13	2007-06-14	2007-12-14	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2010-12-13	2011-06-14	2011-12-14	$7700.00	Window Closed / Lapsed

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

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag