MECHANISM FOR SCHEDULING EXECUTION OF THREADS FOR FAIR RESOURCE ALLOCATION IN A MULTI-THREADED AND/OR MULTI-CORE PROCESSING SYSTEM

• US 20120227042A1
• Filed: 05/16/2012
• Published: 09/06/2012
• Est. Priority Date: 12/16/2004
• Status: Active Grant

• Current Assignee: Vmware LLC (Broadcom, Inc.)
• Original Assignee: VMware, Inc. (Broadcom, Inc.)
• Inventors: ZEDLEWSKI, John R., WALDSPURGER, Carl A.
• Granted Patent: US 10,417,048 B2
• Time in Patent Office: Days
• US Class Current: 718/1
• CPC Class Codes: G06F 2209/483 Multiproc
• CPC Class Codes: G06F 2209/485 Resource constraint
• CPC Class Codes: G06F 9/5027 the resource being a machine, e.g. CPUs, Servers, Terminals

Abstract

A thread scheduling mechanism is provided that flexibly enforces performance isolation of multiple threads to alleviate the effect of anti-cooperative execution behavior with respect to a shared resource, for example, hoarding a cache or pipeline, using the hardware capabilities of simultaneous multi-threaded (SMT) or multi-core processors. Given a plurality of threads running on at least two processors in at least one functional processor group, the occurrence of a rescheduling condition indicating anti-cooperative execution behavior is sensed, and, if present, at least one of the threads is rescheduled such that the first and second threads no longer execute in the same functional processor group at the same time.

Claims

1. A virtual-machine monitor, implemented as computer instructions encoded within a data-storage subcomponent of a physical computer system that includes one or more mass-storage devices, one or more electronic memories, and one or more physical processors, the virtual-machine monitor comprising:

an interface component that schedules execution of virtual machines on logical processors that are each mapped to an execution thread executing on a physical-processor package, each physical-processor package supporting simultaneous execution of multiple execution threads; and

an accounting component that stores, in an electronic memory, indications of package seconds accumulated by each virtual machine during execution of the virtual machine within the execution environment provided by the physical computer system and virtual-machine monitor, package seconds corresponding to a relative portion of the total processing resources of a physical-processor package used by the virtual machine.

2. The virtual-machine monitor of claim 1 wherein the interface component is one or:

an interface to a host operating system; and

a virtual-machine-monitor kernel.

3. The virtual-machine monitor of claim 1 wherein a number of package seconds accumulated for a virtual-machine running alone for a number of logical seconds within a physical-processor package is twice the number of package seconds accumulated for a virtual machine running for the number of logical seconds within a physical-processor package along with another virtual machine.

4. The virtual-machine monitor of claim 1 wherein a first number of package seconds accumulated for a virtual-machine running alone for a second number of logical seconds within a physical-processor package is equal to a factor multiplied by a third number of package seconds accumulated for each of a fourth number of virtual machines running together for the first number of logical seconds within a physical-processor package, wherein the factor is equal to the fourth number.

5. A virtual-machine monitor, implemented as computer instructions encoded within a data-storage subcomponent of a physical computer system that includes one or more mass-storage devices, one or more electronic memories, and one or more physical processors, the virtual-machine monitor comprising:

an interface component that interfaces to hardware components of the computer system on behalf of the virtual-machine monitor and virtual machines and provides a virtual hardware interface to virtual machines;

a scheduler component that schedules execution of virtual machines on logical processors that are each mapped to an execution thread executing on a physical-processor package, each physical-processor package supporting simultaneous execution of multiple execution threads; and

an activity sensor within the scheduler component that continuously monitors execution performance and execution characteristics of the virtual machines to detect non-optimal mapping of logical processors to execution threads within physical-processor packages.

6. The virtual-machine monitor of claim 5 wherein the interface component is one or:

an interface to a host operating system; and

a virtual-machine-monitor kernel.

7. The virtual-machine monitor of claim 5 wherein the activity sensor monitors one or more of:

hardware performance counters; and

software performance counters.

8. The virtual-machine monitor of claim 7 wherein, by monitoring one or more of hardware performance counters and software performance counters, the activity sensor determines the execution performance and the execution characteristics by determining, at intervals, one or more of a number of specific measures, including:

a frequency of pipeline flushes;

a number of cache flushes;

a number of cache misses;

a number of failed resource accesses due to resource overflow;

a number of access to each of a number of specified hardware resources.

9. The virtual-machine monitor of claim 8 wherein the activity sensor detects non-optimal mapping of logical processors to execution threads by one or more of:

applying a set of rules to the determined execution performance and the execution characteristics; and

by comparing specific measures to threshold values to detect anti-cooperative behavior.

10. The virtual-machine monitor of claim 5 wherein the scheduler, upon a determination of non-optimal mapping of logical processors to execution threads within physical-processor packages by the activity sensor, remaps logical processors to execution threads within physical-processor packages.

11. The virtual-machine monitor of claim 10 wherein the scheduler remaps logical processors to execution threads within physical-processor packages by one of

mapping a logical processor that currently shares a physical-processor package with one or more logical processors to execute alone on a physical-processor package;

mapping a logical processor that currently shares a physical-processor package with a first set of one or more logical processors to a physical-processor package which the logical processor subsequently shares with a second set of one or more logical processors, the second set of one or more logical processors including a logical processor that is not included in the first set of logical processors.

12. A virtual-machine monitor, implemented as computer instructions encoded within a data-storage subcomponent of a physical computer system that includes one or more mass-storage devices, one or more electronic memories, and one or more physical processors, the virtual-machine monitor comprising:

an interface component that interfaces to hardware components of the computer system on behalf of the virtual-machine monitor and virtual machines and provides a virtual hardware interface to virtual machines;

a scheduler component that schedules execution of virtual machines on logical processors that are each mapped to an execution thread executing on a physical-processor package, each physical-processor package supporting simultaneous execution of multiple execution threads; and

an activity sensor within the scheduler component that continuously monitors relative execution performance and relative execution characteristics of the virtual machines to detect non-optimal mapping of logical processors to execution threads within physical-processor packages.

13. The virtual-machine monitor of claim 12 wherein the interface component is one or:

an interface to a host operating system; and

a virtual-machine-monitor kernel.

14. The virtual-machine monitor of claim 12 wherein the activity sensor monitors one or more of:

hardware performance counters; and

software performance counters.

15. The virtual-machine monitor of claim 14 wherein, by monitoring one or more of hardware performance counters and software performance counters, the activity sensor determines the relative execution performance and the relative execution characteristics by determining, at intervals, one or more of a number of specific measures, including:

a frequency of pipeline flushes;

a number of cache flushes;

a number of cache misses;

a number of failed resource accesses due to resource overflow;

a number of access to each of a number of specified hardware resources.

16. The virtual-machine monitor of claim 15 wherein the activity sensor detects non-optimal mapping of logical processors to execution threads by:

comparing specific measures for each logical processor to specific measures for other logical processors; and

comparing specific measures for each physical-processor package to specific measures for other physical-processor packages.

17. The virtual-machine monitor of claim 12 wherein the scheduler, upon a determination of non-optimal mapping of logical processors to execution threads within physical-processor packages by the activity sensor, remaps logical processors to execution threads within physical-processor packages in order to minimize differences in relative execution performance and the relative execution characteristics among logical processors and among physical-processor packages.

18. The virtual-machine monitor of claim 17 wherein the scheduler remaps logical processors to execution threads within physical-processor packages by one of:

mapping a logical processor that currently shares a physical-processor package with one or more logical processors to execute alone on a physical-processor package;

mapping a logical processor that currently shares a physical-processor package with a first set of one or more logical processors to a physical-processor package which the logical processor subsequently shares with a second set of one or more logical processors, the second set of one or more logical processors including a logical processor that is not included in the first set of logical processors.