Providing service quality levels through CPU scheduling

• US 8,918,784 B1
• Filed: 12/21/2010
• Issued: 12/23/2014
• Est. Priority Date: 12/21/2010
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Lazier, Colin L., Jorgensen, Atle N., Kowalski, Marcin
• Primary Examiner(s): An, Meng
• Assistant Examiner(s): LEE, TAMMY EUNHYE
• Application Number:
  US12/975,211
• Time in Patent Office: 1,463 Days
• Field of Search: None
• US Class Current: 718/1
• CPC Class Codes: G06F 2009/4557 Distribution of virtual machine instances; Migration and load balancing
• CPC Class Codes: G06F 2009/45595 Network integration; Enabling network access in virtual machine instances
• CPC Class Codes: G06F 2209/5021 Priority
• CPC Class Codes: G06F 2209/504 Resource capping
• CPC Class Codes: G06F 9/455 Emulation; Interpretation; Software simulation, e.g. virtualisation or emulation of application or operating system execution engines
• CPC Class Codes: G06F 9/45558 Hypervisor-specific management and integration aspects
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• 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/5077 Logical partitioning of resources; Management or configuration of virtualized resources specific details on emulation or internal functioning of virtual machines G06F9/455
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

In this disclosure, a resource scheduler is described that allows virtual machine instances to earn resource credits during the low activity levels. Virtual machine instances that spend a predominant amount of time operating at low activity levels are able to quickly gain resource credits. Once these virtual machine instances acquire enough resource credits to surpass a threshold level, the resource scheduler can assign a high priority level to the virtual machine instances that provide them with priority access to CPU resources. The next time that the virtual machine instances enter a high activity level, they have a high priority level that allows them to preempt other, lower priority virtual machine instances. Thus, these virtual machine instances are able to process operations and/or respond to user requests with low latency.

Claims

1. A method for allocating computing resources in a virtualized environment, the method comprising:

by a computer system comprising one or more processors;

allocating resource credits to virtual machine instances on the computing system, wherein the resource credits associated with a particular virtual machine instance are consumed based on usage of the one or more processors;

identifying a first set of one or more virtual machine instances, wherein each virtual machine instance of the first set has a number of resource credits below a first threshold level;

limiting usage of the one or more processors by the first set of virtual machine instances to a first resource limit, wherein the first resource limit is used to determine a rate at which each virtual machine instance of the first set can utilize the one or more processors, wherein the first resource limit is associated with virtual machines having a number of resource credits below the first threshold level;

identifying a second set of virtual machine instances, wherein each virtual machine instance in the second set has a number of resource credits above the first threshold level, wherein a rate at which virtual machine instances having resource credits above the first threshold level can utilize the one or more processors is greater than the rate associated with the first resource limit; and

prioritizing usage of the one or more processors by the second set of virtual machine instances over the first set of virtual machine instances

wherein limiting usage of the one or more processors by the first set of virtual machine instances to the first resource limit creates a reserve of unallocated computing resources and wherein the reserve computing resources are allocated to the second set of virtual machine instances having resource credits above the first threshold level.

2. The method of claim 1, wherein a negative amount of resource credits is below the first threshold level.

3. The method of claim 1, wherein the first resource limit is associated with a maximum rate at which virtual machine instances having a number of resource credits below the first threshold level can utilize the one or more processors.

4. The method of claim 1, further comprising reevaluating the identification of the virtual machine instances in first set and the identification of the virtual machine instances in the second set at a periodic interval.

5. The method of claim 1, wherein limiting the processor usage by the first set of virtual machine instances further comprises forcing down the processor usage of the first set of virtual machine instances to a background usage level.

6. The method of claim 1, wherein limiting the usage of the one or more processors by the first set of virtual machine instances further comprises reducing usage of the first set of virtual machine instances asymptotically to zero over multiple processor time periods.

7. A system for allocating resources in a virtualized environment, the system comprising:

one or more processors; and

a scheduler configured to provide prioritized access to the one or more processors by virtual machines instances that utilize the one or more processors, the scheduler configured to prioritize processor access by;

allocating resource credits to the virtual machine instances;

assigning priority levels to the virtual machine instances based on the resource credits associated with each virtual machine instance;

limiting processor usage of virtual machine instances with resource credits below a threshold level;

identifying one or more priority virtual machine instances with resource credits above the threshold level; and

providing the one or more priority virtual machine instances with priority access to the one or more processors, wherein the rate at which the priority virtual machines instances can utilize the one or more processors is greater than the rate at which the virtual machines with resource credits below the threshold level can utilize the one or more processors,

wherein limiting processor usage of the virtual machine instances with resource credits below the threshold level creates a reserve of unallocated computing resources and wherein the reserve computing resources are allocated to the one or more priority virtual machine instances having resource credits above the threshold level.

8. The system of claim 7, wherein limiting the processor usage includes associating resource limits with the limited virtual machine instances.

9. The system of claim 7, wherein limiting the processor usage includes reducing a resource limit associated with a virtual machine instance.

10. The system of claim 9, wherein the resource limit is reduced asymptotically to zero over multiple processor time periods.

11. The system of claim 7, wherein the one or more priority virtual machine instances include virtual machine instances previously idling for multiple processor time periods.

12. The system of claim 7, wherein the resource credits are allocated at periodic intervals, wherein the periodic intervals are continuous.

13. The system of claim 7, wherein the resource credits are allocated at periodic intervals wherein the periodic intervals are discontinuous.

14. The system of claim 7, wherein the priority access is provided to the one or more priority virtual machine instances for a time period of at least one second.

15. A non-transitory computer-readable storage medium having stored thereon instructions that, when executed, direct a computing system to perform a method of computing resource allocation, the method comprising:

allocating resource credits to virtual machine instances of a computing system, wherein the resource credits associated with a particular virtual machine instance are consumed based on usage of computing resources by that particular virtual machine instance;

providing the computing resources to the virtual machine instances based on resource limits associated with each of the virtual machine instances, wherein the resource limit is used to prevent virtual machine instances from utilizing the computing resources at an amount higher than the resource limit, the resource limit is used to determine a rate at which each virtual machine instance can utilize the one or more processors;

lowering the resource limits associated with virtual machine instances having resource credits below a threshold amount, and

removing resource limits associated with the one or more virtual machine instances having resource credits above the threshold amount, wherein the rate at which virtual machine instances having resource credits above the threshold amount can utilize the one or more processors is greater than the rate associated with virtual machine instances having resource credits below the threshold amount; and

prioritizing access to the computing resources to the one or more virtual machine instances having resource credits above the threshold amount over virtual machine instances having resource credits below the threshold amount on the computing system,

wherein lowering the resource limit creates a reserve of unallocated computing resources and wherein the reserve computing resources are allocated to the one or more virtual machine instances having resource credits above the threshold amount.

16. The storage medium of claim 15, wherein the computing resources include processor time.

17. The storage medium of claim 15, wherein the computing resources include at least one of memory and bandwidth.

18. The storage medium of claim 15, wherein the computing resources include input or output (I/O) operations.

19. The storage medium of claim 15, further comprising selecting a virtual machine instance of the one or more virtual machine instances having resource credits above the threshold amount for priority access through a selection process.

20. The storage medium of claim 19, wherein the selection process is a round robin process.

21. The storage medium of claim 15 further comprising providing additional resource credits to one of the virtual machine instance when additional resource credits are purchased for the virtual machine instance.