Distributed complementary workload scheduling

• US 9,459,930 B1
• Filed: 10/27/2011
• Issued: 10/04/2016
• Est. Priority Date: 10/27/2011
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Adogla, Eden G.
• Primary Examiner(s): Puente, Emerson
• Assistant Examiner(s): Kamran, Mehran
• Application Number:
  US13/283,455
• Time in Patent Office: 1,804 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 2209/5021 Priority
• CPC Class Codes: G06F 9/5038 considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration scheduling strategies G06F9/4881 and subgroups
• CPC Class Codes: G06F 9/5044 considering hardware capabilities
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

In a multiple computer environment, workloads are classified as first-class or second-class, depending on their priorities. The workloads are profiled to determine computer capabilities that they are expected to use. Based upon this information, second-class workloads are chosen for execution alongside first-class workloads in such a way that the expected capabilities used by the first-class and second-class workloads are complementary.

Claims

1. A computer-implemented method, comprising:

under control of one or more processors configured with executable instructions,

classifying available workloads as being at least one of first-class workloads or second-class workloads based at least partly on one or more previously agreed upon service-level expectations for individual ones of the available workloads;

profiling the first-class workloads to determine first computer capabilities that are expected to be unused by the first-class workloads;

profiling the second-class workloads to determine second computer capabilities that are expected to be used by the second-class workloads;

executing a selected first-class workload of the first-class workloads on a computer;

based at least in part on the profiling of the first-class workloads and the second-class workloads, determining a selected second-class workload of the second-class workloads that is expected to use at least one first computer capability of the first computer capabilities that is expected to be unused by the selected first-class workload;

executing the selected second-class workload on the computer while executing the selected first-class workload;

determining that the execution of the selected second-class workload interferes with the selected first-class workload;

terminating execution of the selected second-class workload based at least in part on the determining that the execution of the selected second-class workload interferes with the selected first-class workload; and

modifying a capability profile of the selected first-class workload to indicate an incompatibility between the selected first-class workload and the selected second-class workload based at least in part on the determining that the execution of the selected second-class workload interferes with the selected first-class workload.

2. The method of claim 1, further comprising maintaining a pool of the second-class workloads for execution by different computers depending at least partly on the first computer capabilities that are expected to be unused when executing different first-class workloads.

3. The method of claim 1, further comprising dynamically assigning different second-class workloads to different computers depending at least partly on the first computer capabilities that are expected to be unused when executing different first-class workloads.

4. The method of claim 1, further comprising terminating execution of the selected second-class workload based at least partly on a determination that the selected second-class workload interferes with the selected first-class workload.

5. The method of claim 1, further comprising refining the profiling of the first-class workloads and the second-class workloads during the executing of the selected first-class workload and the second-class workload.

6. The method of claim 1, wherein the first-class workloads comprise one of applications or application components that are to be executed on behalf of a developer for which a fee has been paid.

7. A computer-implemented method of utilizing computer resources, comprising:

under control of one or more processors configured with executable instructions,

classifying available workloads as being at least one of first-class workloads or second-class workloads depending at least partly on service-level expectations associated with at least one of the first-class workloads or the second-class workloads;

executing a first-class workload of the first-class workloads on a computer;

determining unused capabilities of the computer that is executing the first-class workload;

maintaining a pool of the second-class workloads;

selecting the computer to execute a second-class workload of the pool of second-class workloads, wherein the second-class workload is expected to use the unused capabilities of the computer during execution of the first-class workload;

executing the second-class workload on the computer;

determining that execution of the second-class workload interferes with the first-class workload that is executing on the computer;

terminating execution of the second-class workload based at least in part on the determining that the execution of the second-class workload interferes with the first-class workload; and

modifying a capability profile of the first-class workload to indicate an incompatibility between the first-class workload and the second-class workload based at least in part on the determining that the execution of the second-class workload interferes with the first-class workload.

8. The method of claim 7, further comprising selecting different computers to execute respective second-class workloads depending at least partly on the unused capabilities of the computer and the computer capabilities expected to be used by the second-class workload.

9. The method of claim 7, further comprising profiling the pool of second-class workloads to identify the computer capabilities that are expected to be used by the second-class workload.

10. The method of claim 7, wherein the computer capabilities are first computer capabilities, and further comprising profiling the first-class workloads to identify second computer capabilities that are expected to be unused by the first-class workloads.

11. One or more non-transitory computer-readable media containing instructions executed by one or more processors to perform actions comprising:

classifying available workloads as being at least one of first-class workloads or second-class workloads depending at least partly on service-level agreements associated with at least one of the first-class workloads or the second-class workloads;

identifying first computer capabilities that are expected to be unused by individual computers of a pool of computers that are executing the first-class workloads;

identifying second computer capabilities expected to be used by individual ones of the second-class workloads of a pool of second-class workloads;

for an individual second-class workload of the pool of second-class workloads, selecting a computer of the pool of computers to execute the individual second-class workload, the computer having a first computer capability of the first computer capabilities that includes a second computer capability expected to be used by the individual second class workload;

executing the second-class workload on the computer;

terminating execution of the individual second-class workload based at least in part on determining that the execution of the individual second-class workload interferes with an individual first-class workload executing on the computer; and

modifying a capability profile of the individual first-class workload to indicate an incompatibility between the first-class workload and the second-class workload based at least in part on the determining that the execution of the individual second-class workload interferes with the individual first-class workload.

12. The one or more non-transitory computer-readable media of claim 11, the actions further comprising dynamically assigning different second-class workloads to different computers of the pool of computers depending at least partly on the second computer capabilities expected to be used by the individual ones of the second-class workloads.

13. The one or more non-transitory computer-readable media of claim 11, the actions further comprising dynamically assigning different second-class workloads to different computers of the pool of computers depending at least partly on the first computer capabilities that are expected to be unused by individual computers of the pool of computers.

14. The one or more non-transitory computer-readable media of claim 11, the actions further comprising observing the individual second-class workload during execution to further identify the second computer capability used by the individual second-class workload.

15. The one or more non-transitory computer-readable media of claim 11, the actions further comprising observing the first-class workloads during execution by the pool of computers to further identify the first computer capabilities that are expected to be unused.

16. The one or more non-transitory computer-readable media of claim 11, wherein the first-class workloads comprise one of applications or application components that are to be executed on behalf of a developer for which a fee has been paid.