A virtual machine is a self-contained execution environment that behaves as if it is a separate computer and which can run its own operating system. Virtual machines (VMs) provide virtual CPUs (vCPUs) to clients or “guests”, and each VCPU runs on a dedicated physical CPU. A vCPU is a representation of a physical processor within a Virtual Machine. In conventional systems, the mapping between virtual and physical CPUs is static.
A scheduler is a component that schedules requests for the vCPUs assigned to a Virtual Machine to the physical CPUs. When a Virtual Machine uses its vCPU, it has to find a free physical CPU for the Virtual Machine to use. Typically, the number of vCPUs outnumbers the number of physical CPUs. As a result, the Virtual Machines are competing to use the limited number of available physical CPUs. The scheduler's task is to find CPU time for all the Virtual Machines that are requesting it, and to do it in a balanced way in order to prevent performance losses for any of the Virtual Machines. This can be difficult, particularly when Virtual Machines are assigned multiple vCPUs (Symmetric MultiProcessing Virtual Machines, SMP VMs).
Examples of SMP Virtual Machine scheduling are described at the following http webpages: cs.gmu.edu/˜hfoxwell/cs671projects/southern_v12n.pdf, communities.vmware.com/docs/DOC-4960, and xen.org/files/xensummitboston08/LHP.pdf.
A typical use case is the following. A Virtual Machine Monitor (VMM) is running on a platform having two physical CPUs, namely CPU0 and CPU1, and provides two Virtual Machines VM (A) and VM (B). VM (A) is assigned to CPU0 and runs a high priority (mono-processor) Real-Time Operating System (RTOS). VM (B) is assigned to CPU0 and CPU1 and runs a lower priority (multi-processor) General Purpose Operating System (GPOS). Such a configuration allows the RTOS to use unlimited CPU0 resource, and when the RTOS is idle, the CPU0 resource can be provided to the GPOS.
Based on this use case, the following scheduler requirements can be formulated:                REQ 1: It should be possible to share a physical CPU among multiple VMs using either a priority or fair-share based policy.        REQ 2: It should be possible to run a lower priority SMP guest on physical CPUs which can be shared with a higher priority (SMP or UP (uniprocessor)) guest.        
While some conventional schedulers meet the first requirement REQ1 allowing the physical CPU to be shared among multiple guests, the second, SMP-specific requirement REQ 2 is quite challenging. Two main issues should be resolved in order to avoid undesirable side effects in the multi-processor OS which can be caused by a vCPU pre-emption:                1. A vCPU pre-emption can cause a useless busy loop in another vCPU. This typically happens when a vCPU is trying to obtain a spin lock owned by another vCPU which has been pre-empted.        2. A vCPU pre-emption is not taken into account by the guest OS scheduler and therefore it is possible for a task to be executing on a vCPU which has been pre-empted while some other vCPUs are idle.        
The present invention aims to address this and other problems of conventional schedulers.