Selective descheduling of idling guests running on a host computer system

• US 8,352,944 B2
• Filed: 06/16/2010
• Issued: 01/08/2013
• Est. Priority Date: 12/17/2003
• Status: Active Grant

• Current Assignee: Vmware LLC (Broadcom, Inc.)
• Original Assignee: VMware, Inc. (Broadcom, Inc.)
• Inventors: Weissman, Boris, Budko, Dmitriy
• Primary Examiner(s): An, Meng
• Assistant Examiner(s): Arcos, Caroline H
• Application Number:
  US12/816,494
• Publication Number:
  US 20100257524A1
• Time in Patent Office: 937 Days
• Field of Search: None
• US Class Current: 718/100
• 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 a PAUSE instruction in the received instructions; and

inserting a descheduling instruction block in the outgoing stream of instructions to deschedule the virtual machine based upon detection of the PAUSE instruction, wherein the descheduling instruction block inserted in the outgoing stream of instructions is to measure how long the PAUSE instruction has been executed, and to deschedule the virtual machine if the execution time of the PAUSE instruction is longer than a threshold period.

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

3. A method as in claim 1, further comprising measuring a frequency at which instructions received for binary translation are within a fixed instruction address range, and wherein the descheduling instruction block is inserted if the frequency exceeds a threshold frequency.

4. A method as in claim 1, further comprising:

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 an idling loop have been detected when the frequency exceeds a threshold frequency.

5. A method as in claim 1, further comprising determining that a sequence of a plurality of instructions issued by the virtual machine match an idling pattern.

6. A method as in claim 1, wherein the detecting and the 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.

9. A method as in claim 1, wherein the PAUSE instruction is detected at a first time, and further comprising if the PAUSE instruction is not detected within a predetermined interval after the first time then clearing a status associated with having detected the PAUSE instruction.

10. A method as in claim 1, wherein the received instructions are to be executed by a guest operating system of the virtual machine.

11. A method as in claim 1, further comprising:

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.

8. A method of scheduling virtual machines running on at least one processor, the 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 an idling loop in the received instructions; and

inserting a descheduling instruction block in the outgoing stream of instructions to deschedule the virtual machine if an instruction associated with an atomic memory access is detected within the idling loop, wherein the descheduling instruction block inserted in the outgoing stream of instructions is to deschedule the virtual machine if an execution duration of the idling loop meets or exceeds a threshold.

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

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

detecting a PAUSE instruction in the at least some instructions;

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

emitting a descheduling code block in the translated instruction stream for at least one of the at least some instructions if the PAUSE instruction is detected, wherein the descheduling code block, when executed by the at least one processor, performs operations of;

measuring a time period for which an idling loop containing the PAUSE instruction has been executed, and

descheduling the virtual machine if the time period for which the idling loop has executed exceeds the threshold period.

13. A method as in claim 12, wherein the PAUSE instruction is a first PAUSE instruction, and the descheduling code block further causes the at least one processor to perform a second PAUSE instruction every time the first PAUSE instruction is detected.

14. A method as in claim 12, further comprising:

starting a timer to measure a time period of the idling loop when beginning execution of the idling loop is detected, and

setting a flag that indicates a spinning state.

15. A computer system comprising:

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

at least one virtual machine to issue instructions for execution on the at least one hardware processor;

a system layer to mediate access by the virtual machine for hardware resources, the hardware resources including the at least one hardware processor;

an interface layer to observe the instructions issued by the at least one virtual machine to be executed on the at least one hardware processor;

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

a detection module to detect instructions forming an idling loop by identifying instruction pointers within one or more instruction pointer ranges within the instructions issued by the virtual machine; and

a scheduling module within the system layer to deschedule the virtual machine;

in which;

the detection module is incorporated into the binary translator and is further to emit a descheduling code block in the translated instruction stream for at least one of the instructions issued by the at least one virtual machine, wherein the descheduling code block is to measure how long the idling loop has executed, and is to indicate descheduling to the scheduling module if the execution time of the idling loop is longer than a threshold period.

25. A system as in claim 15, wherein the detection module further detects the idling loop by identifying an instruction having a LOCK prefix within respective instructions identified by the one or more instruction pointer ranges.

26. A system as in claim 15, wherein the detection module further detects the idling loop by identifying an XCHG instruction within respective instructions identified by the one or more instruction pointer ranges.

16. A computer-readable non-propagating storage medium comprising a set of instructions which, when executed, cause at least one processor to at least:

detect instructions forming an idling loop in instructions of a virtual machine by detecting respective instruction pointers in one or more instruction pointer ranges, the instructions being received 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;

insert instructions in the outgoing stream of instructions for descheduling the virtual machine in association with the instructions forming the idling loop; and

adjust a threshold period as a function of workload on the at least one processor.

19. A computer-readable non-propagating storage medium as in claim 16, further comprising instructions which, when executed, cause the machine to determine that a sequence of a plurality of instructions issued by the virtual machine pattern-match an idling pattern.

20. A computer-readable non-propagating storage medium as in claim 16, wherein the inserted instructions include a descheduling code block which, when executed, cause the machine to at least:

measure a time period for which an idling loop has executed; and

deschedule the virtual machine if the time period for which the idling loop has executed exceeds the threshold period.

21. A computer-readable non-propagating storage medium as in claim 16, further comprising instructions which, when executed, cause the machine to identify a characteristic instruction in the idling loop, the characteristic instruction being an instruction that is indicative of idling loops.

22. A computer-readable non-propagating storage medium as in claim 21, wherein the characteristic instruction is a PAUSE instruction.

23. A computer-readable non-propagating storage medium as in claim 21, wherein the characteristic instruction is an instruction associated with an atomic memory access.

24. A computer-readable non-propagating storage medium as in claim 16, wherein the instructions forming the idling loop are executed by a guest operating system of the virtual machine.

27. A computer-readable non-propagating storage medium as in claim 16, further comprising instructions which, when executed, cause the machine to detect the idling loop by detecting an instruction having a LOCK prefix within respective instructions identified by the one or more instruction pointer ranges.

28. A computer-readable non-propagating storage medium as in claim 16, further comprising instructions which, when executed, cause the machine to detect the idling loop by detecting an XCHG instruction within respective instructions identified by the one or more instruction pointer ranges.

17. A computer-readable non-propagating storage medium comprising a set of instructions which, when executed, cause a machine to at least:

detect instructions forming an idling loop in instructions of a virtual machine by detecting respective instruction pointers in one or more instruction pointer ranges, the instructions being received for binary translation at a binary translation layer, the binary translation layer generating an outgoing stream of instructions for execution on the machine;

insert instructions in the outgoing stream of instructions for descheduling the virtual machine in association with the instructions forming the idling loop; and

measure 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.

18. A computer-readable non-propagating storage medium comprising a set of instructions which, when executed, cause a machine to at least:

detect instructions forming an idling loop in instructions of a virtual machine by detecting respective instruction pointers in one or more instruction pointer ranges, the instructions being received for binary translation at a binary translation layer, the binary translation layer generating an outgoing stream of instructions for execution on the machine;

insert instructions in the outgoing stream of instructions for descheduling the virtual machine in association with the instructions forming the idling loop;

sample the instructions received for binary translation;

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

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