Meta-scheduler with meta-contexts

Patent metadata

Field	Value
Publication number	US-9367350-B2
Application number	US-24496608-A
Country	US
Kind code	B2
Filing date	Oct 3, 2008
Priority date	Oct 3, 2008
Publication date	Jun 14, 2016
Grant date	Jun 14, 2016

Abstract

A process in a computer system creates and uses a meta-scheduler with meta-contexts that execute on meta-virtual processors. The meta-scheduler includes a set of schedulers with scheduler-contexts that execute on virtual processors. The meta-scheduler schedules the scheduler-contexts on the meta-contexts and schedules the meta-contexts on the meta-virtual processors which execute on execution contexts associated with hardware threads.

First claim

What is claimed is:

1. A method comprising:
providing a first quantum of execution on a first meta-virtual processor to a first scheduler-context of a first scheduler in a meta-scheduler created by a process executing on a computer system; and
providing a second quantum of execution on the first meta-virtual processor to a second scheduler-context of a second scheduler in the meta-scheduler subsequent to the first quantum of execution on the first meta-virtual processor, the first and second quantum being expressed in terms of a number of tasks to be executed, the first scheduler including a first plurality of virtual processors, the second scheduler including a second plurality of virtual processors, the first scheduler excluding the second plurality of virtual processors, the second scheduler excluding the first plurality of virtual processors, the first meta-virtual processor being one of a plurality of meta-virtual processors, the plurality of meta-virtual processors, the first plurality of virtual processors, and the second plurality of virtual processors having a same cardinality.

2. The method of claim 1 wherein the first scheduler-context is attached to a first virtual processor of the first scheduler, and wherein the second scheduler-context is attached to a second virtual processor of the second scheduler.

3. The method of claim 1 further comprising:
identifying the first scheduler-context and the first scheduler in a dispatch aggregate prior to providing the first quantum of execution; and
identifying the second scheduler-context and the second scheduler in the dispatch aggregate prior to providing the second quantum of execution, the second quantum of execution being extended to allow the second scheduler to execute the second scheduler-context without cooperatively yielding to a meta-context.

4. The method of claim 1 further comprising:
providing a third quantum of execution on a second meta-virtual processor to a third scheduler-context of the first scheduler during the first quantum of execution; and
providing a fourth quantum of execution on the second meta-virtual processor to a fourth scheduler-context of the second scheduler subsequent to the first quantum of execution on the second meta-virtual processor.

5. The method of claim 4 wherein the first scheduler-context is attached to a first virtual processor of the first scheduler, wherein the third scheduler-context is attached to a second virtual processor of the first scheduler, wherein the second scheduler-context is attached to a third virtual processor of the second scheduler, and wherein the fourth scheduler-context is attached to a fourth virtual processor of the second scheduler.

6. The method of claim 1 further comprising:
detecting that a third scheduler is added to the meta-scheduler; and
adding a third scheduler-context and the third scheduler to a dispatch aggregate corresponding to the first meta-virtual processor.

7. The method of claim 6 further comprising:
providing a third quantum of execution on the first meta-virtual processor to the third scheduler-context of the third scheduler in the meta-scheduler subsequent to the second quantum of execution on the first meta-virtual processor.

8. The method of claim 1 further comprising:
subsequent to providing the first quantum of execution, detecting that a virtual processor that executes the first scheduler-context has entered an idle state; and
subsequent to providing the second quantum of execution, providing a third quantum of execution on the first meta-virtual processor to the second scheduler-context of the second scheduler in the meta-scheduler prior to providing a fourth quantum of execution on the first meta-virtual processor to the first scheduler subsequent to the first scheduler-context returning from the idle state.

9. A method performed by a process executing on a computer system, the method comprising:
creating a meta-scheduler with first and second meta-virtual processors and corresponding first and second virtual processor contexts;
creating a first scheduler with first and second virtual processors in the meta-scheduler and a second scheduler with third and fourth virtual processors in the meta-scheduler, the first scheduler including a first plurality of virtual processors, the first and second virtual processors being part of the first plurality of virtual processors, the second scheduler including a second plurality of virtual processors, the third and fourth virtual processors being part of the second plurality of virtual processors, the first scheduler excluding the second plurality of virtual processors, the second scheduler excluding the first plurality of virtual processors, the first and second meta-virtual processor being part of a plurality of meta-virtual processors, the plurality of meta-virtual processors, the first plurality of virtual processors, and the second plurality of virtual processors having a same cardinality, the first and second schedulers having different sets of scheduler policies:
providing at least one quantum of execution to the meta-scheduler, the at least one quantum of execution expressed in terms of a number of tasks to be executed; and
associating the first and the third virtual processors with the first meta-virtual processor and the second and the fourth virtual processors with the second meta-virtual processor.

10. The method of claim 9 further comprising:
executing a first scheduler-context on the first virtual processor in response to receiving a first quantum of execution from the first meta-context; and
subsequent to the first quantum of execution, executing a second scheduler-context on the third virtual processor in response to receiving a second quantum of execution from the first meta-context.

11. The method of claim 10 further comprising:
yielding to the first meta-context in response to the first quantum of execution expiring; and
receiving the second quantum of execution subsequent to yielding to the first meta-context.

12. The method of claim 10 further comprising:
during the first quantum of execution, executing a third scheduler-context on the second virtual processor in response to receiving a third quantum of execution from the second meta-context; and
subsequent the third quantum of execution, executing a fourth scheduler-context on the fourth virtual processor in response to receiving a fourth quantum of execution from the second meta-context.

13. The method of claim 12 further comprising:
yielding to the second meta-context in response to the third quantum of execution expiring; and
receiving the fourth quantum of execution subsequent to yielding to the second meta-context.

14. The method of claim 9 further comprising:
executing a first scheduler-context on the first virtual processor in response to receiving a first quantum of execution from the first meta-context;
notifying the first meta-context of a context switch from the first scheduler-context to a second scheduler-context on the first virtual processor; and
executing the second scheduler-context on the first virtual processor in response to receiving a second quantum of execution from a third meta-context.

15. The method of claim 14 further comprising:
during the first quantum of execution, executing a third scheduler-context on the second virtual processor in response to receiving a third quantum of execution from the second meta-context.

16. A computer readable storage medium comprising:
a memory storing computer-executable instructions that, when executed by a computer system, perfo

Assignees

• Ringseth Paul F
• Messmer William R
• Gustafsson Niklas
• Hellerstein Joseph L
• Microsoft Technology Licensing Llc

Inventors

• Ringseth Paul F
• Messmer William R
• Gustafsson Niklas
• Hellerstein Joseph L

Classifications

• G06F9/45533

  Hypervisors; Virtual machine monitors · CPC title

• G06F9/4881 Primary

  Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues · CPC title