Scheduling execution requests to allow partial results

Patent metadata

Field	Value
Publication number	US-9817698-B2
Application number	US-201113163399-A
Country	US
Kind code	B2
Filing date	Jun 17, 2011
Priority date	Jun 17, 2011
Publication date	Nov 14, 2017
Grant date	Nov 14, 2017

Abstract

The subject disclosure is directed towards scheduling requests using quality values that are defined for partial responses to the requests. For each request in a queue, an associated processing time is determined using a system load and/or the quality values. The associated processing time is less than or equal to a service demand, which represents an amount of time to produce a complete response.

First claim

What is claimed is:

1. In a computing environment, a method for scheduling a processor request performed at least in part on at least one computing resource, the method comprising:
retrieving the processor request from a queue of processor requests;
determining a service demand for the processor request prior to the processor request being processed, the service demand based on a resource requirement of the processor request;
computing a system load based on a plurality of service demands;
determining an associated processing time for the processor request based upon the system load and an amount of available processing time; and
determining an associated quality parameter for the processor request, such that an aggregate quality parameter associated with the computing environment is increased, the aggregate quality parameter including at least the associated quality parameter, the associated quality parameter having a non-linear relationship with the associated processing time;
determining whether the system load is at or above a predetermined threshold;
upon determining that the system load is at or above the predetermined threshold, modifying the determined associated processing time based on a request type or a source of the processor request to preserve time for executing at least one other request, based on the at least one other request's service demand, at an end of the queue of requests including the processor request for which the determined associated processing time has been modified;
executing the processor request with the modified associated processing time; and
providing a partial response upon the modified associated processing time being less than the service demand or a complete response upon the modified associated processing time being equal to the service demand.

2. The method of claim 1 , wherein determining the associated processing time is further based upon a number of requests being processed, a length of the queue comprising the at least one other request or at least one deadline associated with the at least one other request, and determining the associated quality parameter is based upon an exponential quality function that is representative of a quality for the processor request as a function of an amount of data transmitted.

3. The method of claim 1 further comprising determining the aggregate quantity parameter associated with the computing environment, wherein determining the associated processing time is further based upon one or more associated quality parameters that are defined for partial responses associated with the processor request, wherein the one or more associated quality parameters includes the associated quality parameter, and a difference between the one or more quality parameters is associated with a change in the associated processing time for the processor request.

4. The method of claim 1 further comprising processing a plurality of other requests, including determining a second associated processing time for a second request based upon the system load, wherein the second associated processing time is equal to the associated processing time.

5. The method of claim 1 , wherein determining the associated processing time comprises modifying the service demand based on one or more previously executed requests.

6. The method of claim 1 , wherein determining the associated processing time further comprises computing the associated processing time that is less than a first deadline associated with the processor request, and modifying a second associated processing time for a second request based upon the system load, such that the second associated processing time is less than a second deadline associated with the second request.

7. The method of claim 1 further comprising executing at least one request based on at least one associated processing time.

8. The method of claim 7 , wherein executing at least one request comprises selecting a parameter based on an associated processing time that controls the execution of a current request of the at least one request.

9. The method of claim 7 , wherein executing at least one request comprises interrupting the execution of a current request, including modifying an associated processing time for the current request.

10. The method of claim 1 , wherein determining the associated processing time comprises decreasing the associated quality parameter such that the aggregate quality parameter associated with the computing environment is increased.

11. The method of claim 1 , wherein determining the associated processing time comprises determining that the service demand is equal to an average service demand of one or more previously executed requests.

12. The method of claim 1 further comprising:
determining whether the computing environment is online;
upon determining that the computing environment is online, implementing a first scheduling technique; and
upon determining that the computing environment is not online, implementing a second scheduling technique.

13. The method of claim 1 wherein the service demand is either predefined or equal to a predicted service demand based on previously executed requests.

14. In a computing environment, a system, comprising:
a memory storing computer executable instructions;
a processor which, when executing the computer executable instructions, is caused to:
retrieve a processor request from a queue of processor requests;
determine a service demand for a processor request prior to the processor request being processed, the service demand based on a resource requirement of the processor request;
compute a system load based on a plurality of service demands;
determine an associated processing time for the processor request using the system load and an amount of available processing time;
determine an associated quality parameter for the processor request such that an aggregate quality parameter associated with the computing environment is increased, the aggregate quality parameter including at least the associated quality parameter, the associated quality parameter having a non-linear relationship with the associated processing time; and
determine whether the system load is at or above a predetermined threshold, and, upon determining that the system load is at or above the predetermined threshold, modify the determined associated processing time based on a request type or a source of the processor request to preserve time for executing at least one other request, based on the at least one other request's service demand, at an end of a queue of requests including the processor request for which the determined associated processing time has been modified; and

an execution mechanism for executing the processor request with the modified associated processing time partially upon the modified associated processing time being less than the service demand or completely upon the modified associated processing time being equal to the service demand.

15. The system of claim 14 , wherein the execution mechanism selects a parameter based on an associated processing time that controls the execution of a current request of the at least one request.

16. The system of claim 14 , wherein the execution mechanism interrupts the execution of a current request, including modifying an associated processing time for the current request.

17. The system of claim 14 , wherein associated processing times of each processor request of the queue of processor requests are equal in amount.

18. One or more computing devices comprising:
one or more p

Assignees

• He Yuxiong
• Elnikety Sameh
• Larus James R
• Yan Chenyu
• Microsoft Technology Licensing Llc

Inventors

• He Yuxiong
• Elnikety Sameh
• Larus James R
• Yan Chenyu

Classifications

• G06F9/50 Primary

  Allocation of resources, e.g. of the central processing unit [CPU] · CPC title

• G06F2209/5013

  Request control · CPC title