Selective descheduling of idling guests running on a host computer system

• US 7,765,543 B1
• Filed: 06/18/2004
• Issued: 07/27/2010
• Est. Priority Date: 12/17/2003
• Status: Active Grant

• Current Assignee: Vmware LLC (Broadcom, Inc.)
• Original Assignee: VMware, Inc. (Broadcom, Inc.)
• Inventors: Budko, Dmitriy, Weissman, Boris
• Primary Examiner(s): An; Meng-Ai
• Assistant Examiner(s): ARCOS, CAROLINE H
• Application Number:
  US10/871,922
• Time in Patent Office: 2,230 Days
• Field of Search: 718/1, 718/102, 718/104, 718/105, 718/107, 718/108, 718/100, 714/48
• US Class Current: 718/1
• CPC Class Codes: G06F 11/3466 Performance evaluation by tracing or monitoring
• CPC Class Codes: G06F 2009/45575 Starting, stopping, suspending or resuming virtual machine instances
• CPC Class Codes: G06F 2201/865 Monitoring of software
• CPC Class Codes: G06F 2209/508 Monitor
• CPC Class Codes: G06F 8/52 Binary to binary
• CPC Class Codes: G06F 9/45558 Hypervisor-specific management and integration aspects
• CPC Class Codes: G06F 9/485 Task life-cycle, e.g. stopping, restarting, resuming execution G06F9/4881 takes precedence
• CPC Class Codes: G06F 9/5022 Mechanisms to release resources

Abstract

Guests, such as virtual machines, that are running on a host hardware platform are selectively descheduled when an idling condition is detected. An example of the idling condition is that the guest has been executing instructions in an idle loop for more than a threshold period. Guest instructions may be evaluated for the idling condition in conjunction with binary translation.

Claims

1. A method of scheduling virtual machines running on at least one processor, comprising:

receiving instructions of a virtual machine for binary translation at a binary translation layer, the binary translation layer generating an outgoing stream of instructions for execution on the at least one processor;

detecting instructions forming an idling loop in the received instructions; and

inserting instructions in the outgoing stream of instructions for descheduling the virtual machine based upon detection of the instructions forming the idling loop, wherein the instructions inserted include a descheduling code block which when executed by said at least one processor measures how long the idling loop has been executed and deschedules the virtual machine if the execution time of the idling loop is longer than a threshold period.

2. A method as in claim 1, further including adjusting the threshold period based on a workload on said at least one processor.

3. A method as in claim 1, wherein said detecting includes measuring a frequency at which instructions received for binary translation are within a fixed instruction address range, and wherein the instructions for descheduling the virtual machine are inserted if the frequency exceeds a threshold frequency.

4. A method as in claim 1, wherein said detecting includes:

sampling the instructions received for binary translation;

measuring a frequency at which the sampled instructions are within a fixed instruction address range, and

determining that the instructions forming the idling loop have been detected when the frequency exceeds a threshold frequency.

5. A method as in claim 1, wherein said detecting includes determining that a sequence of a plurality of instructions issued by the virtual machine pattern-match an idling pattern.

6. A method as in claim 1, wherein said detecting and said descheduling are carried out by a software layer that is between the virtual machines and a host hardware platform for the virtual machines.

7. A method as in claim 6, wherein the software layer comprises a virtual machine monitor.

8. A method as in claim 1, wherein said detecting includes identifying a characteristic instruction in the idling loop, the characteristic instruction being an instruction that is indicative of idling loops.

9. A method as in claim 8, wherein the characteristic instruction is a PAUSE instruction.

10. A method as in claim 8, wherein the characteristic instruction is an instruction associated with atomic memory accesses.

11. A method as in claim 1, wherein the instructions forming the idling loop are executed by a guest operating system of said virtual machine.

12. A method as in claim 8, further including:

if the characteristic instruction is not detected within a predetermined interval after identifying the characteristic instruction for a first time then clearing a status associated with having detected for the first time the characteristic instruction.

13. A method as in claim 1, wherein descheduling the virtual machine further includes:

assigning a processor where the virtual machine is running to a different virtual machine; and

scheduling the virtual machine after a descheduling interval period has finished.

14. A method of scheduling virtual machines running on at least one processor, comprising:

converting at least some instructions issued by a virtual machine using binary translation into respective translated instruction streams for execution on said at least one processor;

detecting instructions forming an idling loop in the virtual machine based on said at least some instructions;

determining a threshold period based on a workload of said at least one processor; and

emitting a descheduling code block as the translated instruction stream for at least one of said at least some instructions when the instructions forming the idling loop are detected, wherein the descheduling code block which when executed by said at least one processor performs operations of,

measuring how long the idling loop has been executed, and

descheduling the virtual machine if the instructions forming the idling loop are detected after the threshold period.

15. A method as in claim 14, wherein the descheduling code block further performs a pause instruction every time the instructions forming the idling loop are detected within the threshold period.

16. A method as in claim 14, wherein a first time the instructions forming an idling loop are detected the descheduling code block when executed by said at least one processor performs operations of:

starting a timer for measuring how long the idling loop has been executed, and setting a flag that indicates a spinning state.

17. A computer system comprising:

a host hardware platform, which includes at least one hardware processor;

at least one virtual machine running on the host platform by issuing instructions for execution on said at least one hardware processor, the virtual machine including at least one virtual processor and a guest operating system;

a system software layer mediating access by the virtual machine for hardware resources, including said at least one hardware processor;

a software interface layer operable to observe the instructions issued by said at least one virtual machine to be executed on said at least one hardware processor;

a binary translation sub-system within the software interface layer converting at least some of the instructions issued by said at least one virtual machine using binary translation into respective translated instruction streams for execution on said at least one hardware processor;

a detection software module comprising computer-executable code for detecting instructions forming an idling loop within the issued instructions by the virtual machine; and

a scheduling software module within the system software layer comprising computer-executable code for descheduling the virtual machine;

in which;

the detection software module is incorporated into the binary translator and is further provided for emitting a descheduling code block as the translated instruction stream for at least one of the instructions issued by said at least one virtual machine, wherein the descheduling code block comprises computer-executable code for measuring how long the idling loop has been executed, and indicating descheduling to the scheduling software module if the execution time of the idling loop is longer than a threshold period.

18. A computer-readable storage medium containing a set of instructions that causes a computer system to perform a method of scheduling virtual machines running on at least one processor, said method comprising:

receiving instructions of a virtual machine for binary translation at a binary translation layer, the binary translation layer generating an outgoing stream of instructions for execution on the at least one processor;

detecting instructions forming an idling loop in the received instructions; and

inserting instructions in the outgoing stream of instructions for descheduling the virtual machine at the instructions forming the idling loop, wherein the instructions inserted in the outgoing stream of instructions measure how long the idling loop has been executed, and deschedule the virtual machine if the execution time of the idling loop is longer than a threshold period.

19. A computer-readable storage medium containing a set of instructions as in claim 18, wherein said method further includes adjusting the threshold period as a function of workload on said at least one processor.

20. A computer-readable storage medium containing a set of instructions as in claim 18, wherein said detecting includes measuring a frequency at which instructions received for binary translation are within a fixed instruction address range, and wherein the instructions for descheduling the virtual machine are inserted if the frequency exceeds a threshold frequency.

21. A computer-readable storage medium containing a set of instructions as in claim 18, wherein said detecting includes:

sampling the instructions received for binary translation;

measuring a frequency at which the sampled instructions are within a fixed instruction address range, and

determining that the instructions forming the idling loop have been detected when the frequency exceeds a threshold frequency.

22. A computer-readable storage medium containing a set of instructions as in claim 18, wherein said detecting includes determining that a sequence of a plurality of instructions issued by the virtual machine pattern-match an idling pattern.

23. A computer-readable storage medium containing a set of instructions as in claim 18, further including:

wherein the instructions inserted include a descheduling code block which when executed by said at least one processor measures how long the idling loop has been executed and deschedules the virtual machine if the execution time of the idling loop is longer than a threshold period.

24. A computer-readable storage medium containing a set of instructions as in claim 18, wherein said detecting includes identifying a characteristic instruction in the idling loop, the characteristic instruction being an instruction that is indicative of idling loops.

25. A computer-readable storage medium containing a set of instructions as in claim 24, wherein the characteristic instruction is a PAUSE instruction.

26. A computer-readable storage medium containing a set of instructions as in claim 24, wherein the characteristic instruction is an instruction associated with atomic memory accesses.

27. A computer-readable storage medium containing a set of instructions as in claim 18, wherein the instructions forming the idling loop are executed by a guest operating system of said virtual machine.