Selecting executing requests to preempt

• US 8,677,375 B2
• Filed: 01/29/2009
• Issued: 03/18/2014
• 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
• Primary Examiner(s): Caldwell, Andrew
• Assistant Examiner(s): Giroux, George
• Application Number:
  US12/362,202
• Publication Number:
  US 20100192153A1
• Time in Patent Office: 1,874 Days
• Field of Search: None
• US Class Current: 718/105
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system

Abstract

Systems, methods, and computer-readable and executable instructions are provided for selecting executing requests to preempt. Selecting executing requests to preempt can include determining whether an application is in an overload condition. Selecting executing requests can also include in response to determining the application is in an overload condition, identifying each request that is being executed by the application. Selecting executing requests can also include determining a value for each request that is executing. Furthermore, selecting executing requests can also include selecting executing requests to preempt based on the values for the requests.

Claims

1. A non-transitory 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, wherein determining the value comprises calculating a utility measure, calculating an amount of executing time, and estimating a probability distribution of a residual lifetime for each request;

utilizing the probability distribution for estimating a utility per unit consumed by each request and utilizing the probability distribution for estimating a mean utility per additional resource consumed, wherein the mean utility per additional resource consumed includes a quantity of financial resource per additional resource consumed;

determining a mean utility per resource consumed to complete the request based on the probability distribution as the value; 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 residual lifetimes for the requests, consumed resources or execution time of each request, and load levels at multiple tiers of the application.

6. 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.

7. 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.

8. 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.

9. 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, wherein determining the value comprises calculating a utility measure, calculating an amount of executing time, estimating a probability distribution of a residual lifetime for each request, utilizing the probability distribution for estimating a utility per unit consumed by each request and utilizing the probability distribution for estimating a mean utility per additional resource consumed, wherein the mean utility per additional resource consumed includes a quantity of financial resource per additional resource consumed, wherein the request valuer determines a mean utility per resource consumed to complete the request based on the probability distribution as the value; and

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

10. The computer system of claim 9, further comprising:

a request preemptor suspending or terminating the selected requests.

11. A non-transitory 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, wherein determining the value comprises calculating a utility measure, calculating an amount of executing time, and estimating a probability distribution of a residual lifetime for each request;

utilizing the probability distribution for estimating a utility per unit consumed by each request and utilizing the probability distribution for estimating a mean utility per additional resource consumed, wherein the mean utility per additional resource consumed includes a quantity of financial resource per additional resource consumed;

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

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