Efficient detection and response to spin waits in multi-processor virtual machines | Patent Publication Number 20160154666
US 20160154666 A1Arun Kishan
Rene Antonio Vega
John Te-Jui Sheu
Yau Ning Chin
Various aspects are disclosed herein for attenuating spin waiting in a virtual machine environment comprising a plurality of virtual machines and virtual processors. Selected virtual processors can be given time slice extensions in order to prevent such virtual processors from becoming de-scheduled (and hence causing other virtual processors to have to spin wait). Selected virtual processors can also be expressly scheduled so that they can be given higher priority to resources, resulting in reduced spin waits for other virtual processors waiting on such selected virtual processors. Finally, various spin wait detection techniques can be incorporated into the time slice extension and express scheduling mechanisms, in order to identify potential and existing spin waiting scenarios.
- 1. A method for attenuating waiting times of virtual processors in a virtual machine environment, comprising:nexamining a hint source for hints to determine if a virtual processor is accessing a synchronizing section that acquires a lock on an underlying physical resource that causes any other virtual processors to wait until the virtual processor releases the lock, the synchronizing section being a region of code that determines access to resources by virtual processors; andproviding a time slice extension to the virtual processor to increase the time allotted in its assigned time slice if the virtual processor is accessing the synchronizing section.
- 8. A system for attenuating waiting times of virtual processors in a virtual machine environment, comprising:nexamining a hint source for hints to determine if a virtual processor is accessing a synchronizing section that acquires a lock on an underlying physical resource that causes any other virtual processors to spin-wait until the virtual processor releases the lock, the synchronizing section being a region of code that determines access to resources by virtual processors; andproviding a time slice extension to the virtual processor to increase the time allotted in its assigned time slice if the virtual processor is accessing the synchronizing section.
- 16. A system for attenuating waiting times of virtual processors in a virtual machine environment, comprising:nidentifying one or more virtual processors that will access a synchronizing section, wherein the one or more identified virtual processors are configured to acquire a lock on an underlying physical resource that causes any other virtual processors to wait;determining an express schedule that prioritizes the one or more identified virtual processors;selecting a virtual processor from the one or more virtual processors to run based on the prioritized express schedule; andproviding a time slice duration for the selected virtual processor.
This application is a continuation of U.S. patent application Ser. No. 12/182,971 filed on Jul. 30, 2008, the entire contents are incorporated herein by reference.
The presently disclosed subject matter relates to the field of computing, and more particularly, to computer virtualization, although virtualization is merely an exemplary and non-limiting field.
Operating system kernels provide several mechanisms to synchronize data structures in multi-threaded systems. Many of these mechanisms use a technique called spin waiting, where a thread or processor will spend time in a loop waiting for a particular event to occur before it continues execution. Spin waits are typically used in cases where wait times will be much less than the cost of re-scheduling threads or where the environment is such that the thread scheduler cannot run.
Examples of synchronization primitives that use this technique include, but are not limited to: spinlocks, queued spinlocks, reader/writer locks, and barriers. In general, well-designed operating systems will minimize the amount of time threads spend in regions of code that lead to these spin wait loops, since the time spent spin waiting is wasted time. At best, in the case of hyper-threading, some of a thread's resources are given to another hyper-thread, but such a thread is still blocked from making forward progress.
Furthermore, the assumption that spin waits will be performed only for short durations can be unintentionally broken when an operating system is running in a virtual machine environment. Consequently, the time spent spin waiting can increase greatly in virtual machine environments and can prevent a virtual machine from making forward progress.
Gang scheduling, in which all virtual processors of a virtual machine are scheduled in tandem, has been used in the past to avoid lock problems (resulting from spin waits). However, this approach often does not make efficient use of the physical system's processor(s). Gang scheduling can create un-schedulable holes where none of the sets of virtual processors from de-scheduled virtual machines will fit into given resources.
Furthermore, requiring all of the virtual processors from a virtual machine to run at the same time and for the same duration can result in cases where some of the virtual processors have no work to do but will run anyway. Both of these issues, long spin waits and gang scheduling, lead to under-utilization of system processors and significant throughput reductions. Thus, other techniques are needed in the art to solve the above described problems.
Various aspects are disclosed herein for attenuating spin waiting in a virtual machine environment comprising a plurality of virtual machines and virtual processors. Selected virtual processors can be given time slice extensions in order to prevent such virtual processors from becoming de-scheduled (and hence causing other virtual processors to have to spin wait). Selected virtual processors can also be expressly scheduled so that they can be given higher priority to resources, resulting in reduced spin waits for other virtual processors waiting on such selected virtual processors. Finally, various spin wait detection techniques can be incorporated into the time slice extension and express scheduling mechanisms, in order to identify potential and existing spin waiting scenarios.
It should be noted that this Summary is provided to introduce a selection of concepts in a simplified form that are further described below in the Detailed Description. This Summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used as an aid in determining the scope of the claimed subject matter.
The foregoing Summary, as well as the following Detailed Description, is better understood when read in conjunction with the appended drawings. In order to illustrate the present disclosure, various aspects of the disclosure are illustrated. However, the disclosure is not limited to the specific aspects shown. The following figures are included:
Spin waiting occurs when a thread (or an underlying processor configured to execute a thread) spends time in a loop waiting for a particular event to occur before it continues execution. This may happen when one thread is waiting to acquire a lock on a resource when another thread has acquired (but not yet released) the lock. In regard to virtualization, spin waiting can occur upon an attempt to enter a synchronization section that a de-scheduled virtual processor is executing.
In order to remedy such spin waiting,
It will be readily appreciated by those skilled in the art that the presently described mechanisms are not limited to typical spinlocks 210, but rather also contemplate queued spinlocks, reader/writer locks, barriers, and so on. The presently shown spin attenuation mechanisms 240 include various aspects described in more detail below, but in general terms they include: time slice extension 230, where virtual processors that have acquired spinlocks are given a time slice extension so that they can finish their task before being de-scheduled; express scheduling 232, where virtual processors can be prioritized by switching context to such virtual processors so that they can run before any other processors; and, spin wait detection mechanisms 234 that can identify or at least guess at when spin waiting might become an issue, and then engage in either time slice extension 230 and/or express scheduling 232.
Turning to
The scheduler 142 can provide 332 a time slice extension 330 to the virtual processor 110 if the virtual processor 110 is accessing 350 the synchronizing section 320. Moreover, the scheduler 142 can also limit 337 the time slice extension 330 to a predetermined period of time 336; and, it may limit 339 the granting of the time slice extension 330 to a predetermined number of times 338. This may be done in order to assure that the other virtual processors and other devices are not starved for resources. Finally, the scheduler 142 can debit 341 the time slice extension 330 granted to the virtual processor 110 from a subsequent time slice granted to the virtual processor. Thus, at the next time slice or some subsequent time slice, the virtual processor 110 can be given less time acquire a resource.
Regarding the hint source 310 itself, it can include any one of the following (or a combination thereof): (a) a task priority register 312, (b) an unenlightened guest operating system 314 state (which may include the task priority register 312), and (c) an enlightened operating system 316. The task priority register 312 is used by some operating systems to hold interrupt request levels. Since spinlocks 210 are typically acquired only at elevated interrupt request levels, examining the task priority register for elevated values provides a strong hint that virtual processors may be holding spinlocks. Alternatively, information exposed from enlightened guest operating systems, such as whether virtual processors are holding spinlocks or executing barrier sections that other virtual processors are waiting on, would be very accurate since such systems are aware of virtualization and have the resources to keep track of acquired spinlocks. Moreover, the typical unenlightened guest operating system could be examined for range of addresses where a thread holds a spinlock, user mode versus kernel mode state, various flags, and so on.
Only when the first virtual processor releases the lock 412, can the other virtual processors acquire locks: the second virtual processor will eventually acquire a lock 416 and then release it 420, and the remaining virtual processor will acquire a lock 422 and then release it 424. But, this way of scheduling virtual processors causes congestion and excessive spin waiting.
In contrast,
In the scenario when time slice extensions are granted, it is desirable to make sure that such extensions are not too long. Thus,
Next,
What
In another aspect of the presently disclosed subject matter, spin waits can be variously identified when virtual processors are run. Instructions used to pace virtual processors in virtual machines can be intercepted 910. These may include “PAUSE†instructions in certain architectures, such as x86. Information about said instructions can be recorded 912. Then, some time afterwards, a history of this information about the instructions can be examined 914 in order to detect a pattern that correlates with long spin waits. Finally, long spin waits can be indicated 916 to various modules (such as express scheduling modules referenced above) if a particular pattern from a plurality of patterns is identified.
In various exemplary implementations, the long spin waits can be indicated to a scheduler that performs context switches to the first virtual processor mentioned above (i.e. the processor that has been de-scheduled). As for the pattern, it can indicate no spin waits when the number of the instructions are below a first predetermined standard (some heuristically determined number), and where the pattern can indicate spin waits when the number of the instructions are above a second predetermined standard 918 (some other heuristically determined number). Of course, these are merely exemplary (and hence non-limiting) aspects that could be additionally supplemented or substituted by any of the other aspects discussed herein.
Any of the above mentioned aspects can be implemented in methods, systems, computer readable media, or any type of manufacture. For example, per
For example, the first subset of instructions can further comprise instructions 1020 for: accessing a hint source regarding whether a virtual processor of the plurality of virtual processors has acquired a spinlock; providing the virtual processor with a time extension in order to at least prevent the at least one processor from becoming de-scheduled; bounding the time extension to a predetermined amount of time; bounding the granting of the time extension to a predetermined number of times; and debiting the time extension from any subsequent time slices.
Again, by way of example, the second subset of instructions can further comprise instructions for: choosing a set of virtual processors from the plurality of virtual processors to run per an express schedule request; boosting priorities of the set of virtual processors resulting in the set of virtual processors running to comply with the express schedule request; bounding the express schedule request to a predetermined time slice duration; bounding the express schedule request to a predetermined number of times; and debiting any time associated with the express schedule request from any subsequent time slices of the set of virtual processors.
The second subset of instructions can further comprise instructions for: targeting the set of virtual processors that are de-scheduled virtual processors; recording information about the set of virtual processors; and retrieving information when spin waits are identified and passing any detection of the spin waits to a virtualizing layer expressly running the set of virtual processors. Moreover, the second subset of instructions can further comprise instructions for: receiving hints from a hint source when a synchronization session is accessed; and, based on such hints, prematurely end any time slice additional to time slices associated with the set of virtual processors.
Similarly to the first and second subset of instructions, the third subset of instructions can further comprise instructions for: setting intercepts for monitoring a predetermined instruction set used to pace the plurality of virtual processors; recording information regarding the predetermined instruction set; examining a history of the recorded predetermined instruction set; determining any patterns in the history; and identifying a spin wait based on the patterns. The third subset, moreover, can further comprises instructions for: receiving via hypercalls (i.e. notifications) from a virtualizing layer a recommended threshold for determining spin waits of the plurality of virtual processors; recording an iteration count of a spin wait loop; comparing the iteration count to the recommended threshold; and identifying a spin wait associated with a virtual processor from the plurality of virtual processors if the iteration count exceeds the recommended threshold. The first, second, and third subset of instructions can attenuate spin waits for a plurality of virtual processors distributed across a plurality of virtual machines and in a plurality of virtual machine environments.
Lastly, while the present disclosure has been described in connection with the preferred aspects, as illustrated in the various figures, it is understood that other similar aspects may be used or modifications and additions may be made to the described aspects for performing the same function of the present disclosure without deviating therefrom. For example, in various aspects of the disclosure, various mechanisms were disclosed for efficient detection and response to spin waits in multi-processor virtual machines. However, other equivalent mechanisms to these described aspects are also contemplated by the teachings herein. Therefore, the present disclosure should not be limited to any single aspect, but rather construed in breadth and scope in accordance with the appended claims.