Methods and apparatus for interleaving priorities of a plurality of virtual processors are disclosed. A hypervisor assigns a base priority to each virtual processor and schedules one or more virtual processors to execute on one or more physical processors based on the current priority associated with each virtual processor. When the hypervisor receives an indication from one of the virtual processors that its current priority may be temporarily reduced, the hypervisor lowers the current priority of that virtual processor. The hypervisor then schedules another virtual processor to execute on a physical processor instead of the virtual processor with the temporarily reduced priority. When the hypervisor receives an interrupt for the virtual processor with the lowered priority, the hypervisor raises the priority of that virtual processor and schedules the virtual processor with the restored priority to execute on a physical processor so that processor can handle the interrupt.