SELECTING EXECUTING REQUESTS TO PREEMPT

• US 20100192153A1
• Filed: 01/29/2009
• Published: 07/29/2010
• Est. Priority Date: 01/29/2009
• Status: Active Grant

• Current Assignee: Valtrus Innovations Limited (f/k/a Dolya Holdco 9 Limited) (Key Patent Innovations Limited)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Uysal, Mustafa, Merchant, Arif A., Trastour, David
• Granted Patent: US 8,677,375 B2
• Time in Patent Office: Days
• US Class Current: 718/103
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system

Abstract

Requests that are executing when an application is determined to be in an overload condition are preempted. To select the executing requests to preempt, a value for each executing request is determined. Then, executing requests are selected for preemption based on the values.

Claims

1. A computer readable medium including code that when executed by a computer system performs a method of selecting application requests that are executing to preempt, the method comprising:

determining whether an application is in an overload condition;

in response to determining the application is in an overload condition, identifying each request that is being executed by the application;

determining a value for each request that is executing; and

selecting executing requests to preempt based on the values for the requests.

2. The computer readable medium of claim 1, wherein the method further comprises:

preempting the selected requests.

3. The computer readable medium of claim 2, wherein preempting comprises suspending or terminating the selected requests.

4. The computer readable medium of claim 3, wherein the method further comprises:

determining whether to terminate or suspend a selected executing request based on a type of the request.

5. The computer readable medium of claim 1, wherein determining a value for each request that is executing comprises:

determining a value for each request that is executing based on one or more of a calculated utility measure for each executing request, a residual lifetime for each executing request, and an amount of executing time.

6. The computer readable medium of claim 5, wherein determining a value for each request that is executing further comprises:

determining a probability distribution of a residual lifetime of the request; and

determining a mean utility per resource consumed to complete the request based on the probability distribution as the value.

7. The computer readable medium of claim 1, wherein determining a value for each request that is executing comprises:

determining a value for each request that is executing based on residual lifetimes for the requests, consumed resources or execution time of each request, and load levels at multiple tiers of the application.

8. The computer readable medium of claim 1, wherein each request includes requests being executed by the application on a computer system and requests being executed by one or more other applications running on the computer system.

9. The computer readable medium of claim 1, wherein determining whether an application is in overload condition further comprises:

determining whether an application is in overload condition based on predetermined service levels.

10. The computer readable medium of claim 1, wherein a request that is executing comprises a request that leaves an admission queue for the application and enters a processing state.

11. A computer system comprising:

a processor executing requests for an application;

an overload detector detecting when the application is in an overload condition;

a request valuer determining a value for each request that is executing when the overload detector detects the overload condition; and

a request preemption selector selecting one or more of the executing requests to preempt based on the values for the executing requests.

12. The computer system of claim 11, further comprising:

a request preemptor suspending or terminating the selected requests.

13. The computer system of claim 11, wherein the request valuer determines the value for each request that is executing based on one or more of a calculated utility measure, a residual lifetime, and an amount of executing time.

14. The computer system of claim 11, wherein the request valuer determines a probability distribution of a residual lifetime of the request, and determines a mean utility per resource consumed to complete the request based on the probability distribution as the value.

15. A computer readable medium including code that when executed by a computer system performs a method of selecting application requests that are executing to preempt, the method comprising:

determining whether an application is in an overload condition based on service levels specified in a service level agreement;

in response to determining the application is in an overload condition, identifying each request that is being executed by the application, wherein a request that is being executed is a request that leaves an admission queue and enters a processing state;

determining a value for each request that is executing; and

selecting executing requests to suspend or terminate based on the values for the requests.