Resource sharing with sliding constraints

• US 20020082856A1
• Filed: 08/21/2001
• Published: 06/27/2002
• Est. Priority Date: 08/25/2000
• Status: Active Grant

• Current Assignee: RingCentral Incorporated
• Original Assignee: Mitel Networks Corporation
• Inventors: Weiss, Michael, Gray, Thomas
• Granted Patent: US 7,222,345 B2
• Time in Patent Office: Days
• US Class Current: 705/1
• CPC Class Codes: G06F 2209/5021 Priority
• CPC Class Codes: G06F 9/50 Allocation of resources, e.g. of the central processing unit [CPU]

Abstract

The resource sharing system according to the present invention dynamically adjusts the priorities at which requests from applications in different request classes (or classes of service) for a shared resource, are processed. The dynamic priority of a request class is based in part on the average resource allocation to requests in this request class, and in part on settings for the minimum and maximum allocations to the request class. The average resource allocation is the proportion of time the shared resource has been assigned to requests of this class relative to other classes. The dynamic adjustment of priorities uses “sliding constraints” whereby the priorities are caused to “slide” with the average resource allocation, and the priority imposes a constraint on when the requests of a resource class can be satisfied: namely, when there are no other requests from higher-priority request classes waiting for the resource.

Claims

1. A method of sharing at least one resource amongst a plurality of applications issuing requests in different request classes, comprising the steps of:

i) dynamically assigning a priority to each of a plurality of request queues associated with respective ones of said request classes, in accordance with a moving average resource allocation to each of said respective request classes;

ii) receiving and queuing said requests from said applications in said plurality of queues in accordance with said respective request classes;

iii) allocating said at least one resource to one of said applications whose request has been queued longest in a highest priority one of said queues, and in response to said one of said applications relinquishing said resource;

then

iv) repeating steps i) to iii).

2. The method of claim 1, wherein said step of dynamically assigning said priority to each of said plurality of request queues is implemented as follows:

p_i=1.0 if u_i<

=min_ip_i=1.0−

(u_i−

min_i)/(max_i−

min_i) if min_i<

u_i<

=max_ip_i=0.0 if u_i>

=max_i

where p_i is the priority assigned to the i^th one of said queues associate with the i^th one of said request classes, and u_i is the moving average allocated to said i^th one of said request classes.

3. The method of claim 2, further including the step of updating said moving average of each of said request classes immediately upon allocating said resource in the event of multiple resources.

4. The method of claim 1, wherein the priority assigned to each of said plurality of request queues in accordance with said moving average resource allocation conforms to a predetermined shape of priority function.

5. The method of claim 4, wherein said shape of said priority function is linear with respect to said moving average resource allocation.

6. The method of claim 4, wherein said shape of said priority function is exponential with respect to said moving average resource allocation.

7. The method of claim 4, wherein said shape of said priority function is a step function with respect to said moving average resource allocation, with steps of varying size.