SCHEDULING COLLECTIONS IN A SCHEDULER

• US 20090288087A1
• Filed: 05/16/2008
• Published: 11/19/2009
• Est. Priority Date: 05/16/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Fernandes, Genevieve, Gustafsson, Niklas, Ringseth, Paul F., Molloy, Rick
• Granted Patent: US 8,561,072 B2
• Time in Patent Office: Days
• US Class Current: 718/102
• CPC Class Codes: G06F 2209/483 Multiproc
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

A scheduler in a process of a computer system includes a respective scheduling collection for each scheduling node in the scheduler. The scheduling collections are mapped into at least a partial search order based on one or more execution metrics. When a processing resource in a scheduling node becomes available, the processing resource first attempts to locate a task to execute in a scheduling collection corresponding to the scheduling node before searching other scheduling collections in an order specified by the search order.

Claims

1. A method performed by a scheduler in a process of a computer system, the method comprising:

in response to one of a first plurality of processing resources in a first scheduling node becoming available, searching for a first task to execute in a first scheduling collection corresponding to the first scheduling node; and

in response to finding no first task to execute in the first schedule collection, executing, with the one of the first plurality of processing resources, a second task from a second scheduling collection corresponding to a second scheduling node that includes a second plurality of processing resources.

2. The method of claim 1 further comprising:

in response to finding the first task in the first scheduling collection, executing the first task with the one of the first plurality of processing resources.

3. The method of claim 1 further comprising:

searching a first set of schedule groups for the first task in the first scheduling collection.

4. The method of claim 3 further comprising:

searching a second set of schedule groups for the second task in the second scheduling collection.

5. The method of claim 1 wherein the one of the first plurality of processing resources includes a first virtual processor and a first hardware thread.

6. The method of claim 1 further comprising:

in response to finding no first task to execute in the first schedule collection, searching for the second task in the second scheduling collection based on at least one execution metric that relates the first scheduling node to the second scheduling node.

7. The method of claim 1 further comprising:

searching for a third task to execute in a local collection corresponding to the one of the first plurality of processing resources; and

in response to finding the third task to execute in the local collection, executing the third task with the one of the first plurality of processing resources.

8. The method of claim 1 wherein searching for the first task in the first scheduling collection further comprising:

searching for a realized task in a set of schedule groups in the first scheduling collection; and

in response to finding no realized task to execute in the set of schedule groups, searching for an unrealized task in the set of schedule groups.

9. A method comprising:

identifying first and second scheduling nodes for a scheduler in a process executing on a computer system;

creating first and second scheduling collections corresponding to the first and the second scheduling nodes, respectively; and

populating the first and the second scheduling collections with first and second sets of tasks, respectively.

10. The method of claim 9 further comprising:

mapping the first and the second scheduling collections into at least a partial search order.

11. The method of claim 10 wherein the partial search order is based on one or more execution metrics associated with the first and the second scheduling nodes.

12. The method of claim 9 wherein the first and the second scheduling nodes include respective first and second sets of processing resources allocated by a resource management layer.

13. The method of claim 12 wherein first and second memories correspond to the first and the second sets of processing resources, wherein access to the first memory by the first set of processing resources is faster than access to the second memory by the first set of processing resources, and wherein access to the second memory by the second set of processing resources is faster than access to the first memory by the second set of processing resources.

14. A computer readable storage medium storing computer-executable instructions that, when executed by a computer system, perform a method comprising:

creating, in a process executing on the computer system, a scheduler with at least first and second scheduling collections corresponding to respective first and second scheduling nodes that include respective first and second pluralities of processing resources; and

executing a first realized task from the first scheduling collection with one of the first plurality of processing resource in response to the first realized task being found in the first scheduling collection; and

executing a second realized task from the second scheduling collection with the one of the first plurality of processing resource in response to the first realized task not being found in the first scheduling collection.

15. The computer readable storage medium of claim 14, the method further comprising:

searching a first plurality of schedule groups in the first scheduling collection to determine whether the first realized task is found in the first scheduling collection.

16. The computer readable storage medium of claim 15, the method further comprising:

searching a second plurality of schedule groups in the second scheduling collection to determine whether the second realized task is present in the second scheduling collection.

17. The computer readable storage medium of claim 14, the method further comprising:

executing a first unrealized task from the second scheduling collection with the one of the first plurality of processing resource in response to the first realized task not being found in the first scheduling collection and the second realized task not being found in the second scheduling collection.

18. The computer readable storage medium of claim 14, the method further comprising:

mapping the first and the second scheduling collections into at least a partial search order.

19. The computer readable storage medium of claim 14, the method further comprising:

identifying the first and the second scheduling nodes based on an execution metric.

20. The computer readable storage medium of claim 19 wherein the execution metric includes a non-uniform memory access (NUMA) distance.