Using a yield indicator in a hierarchical scheduler

• US 8,875,144 B2
• Filed: 03/07/2011
• Issued: 10/28/2014
• Est. Priority Date: 03/07/2011
• Status: Active Grant

• Current Assignee: Red Hat, Inc. (International Business Machines Corporation)
• Original Assignee: Red Hat, Inc. (International Business Machines Corporation)
• Inventors: van Riel, Henri Han
• Primary Examiner(s): Puente, Emerson
• Assistant Examiner(s): KIM, SISLEY NAHYUN
• Application Number:
  US13/041,882
• Publication Number:
  US 20120233623A1
• Time in Patent Office: 1,331 Days
• Field of Search: None
• US Class Current: 718/102
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

A method and system for scheduling the use of CPU time among processes using a scheduling tree having a yielding indicator. A scheduling tree represents a hierarchy of groups and processes that share central processing unit (CPU) time. A computer system assigns a yield indicator to a first node of the scheduling tree, which represents a first process that temporarily yields the CPU time. The computer system also assigns the yield indicator to each ancestor node of the first node in the scheduling tree. Each ancestor node represents a group to which the first process belongs. The computer system then selects a second process to run on the computer system based on the yield indicator in the scheduling tree.

Claims

1. A method comprising:

assigning, by a processing device, a yield indicator to a first node of a scheduling tree, wherein the scheduling tree represents a hierarchy of groups and processes that share central processing unit (CPU) time, wherein the first node represents a first process that temporarily yields the CPU time, and wherein the yield indicator indicates that the first process has yielded CPU time to another process;

assigning, by the processing device, the yield indicator to each of ancestor nodes of the first node in the scheduling tree, each ancestor node representing a group to which the first process belongs;

assigning, by the processing device, a next indicator to a leaf node in the scheduling tree that represents a next process to run;

assigning, by the processing device, the next indicator to each of ancestor nodes of the leaf node in the scheduling tree, each ancestor node representing a group to which the next process belongs; and

selecting, by the processing device, the next process to run on a computer system based on the next indicator and the yield indicator in the scheduling tree.

2. The method of claim 1, wherein the scheduling tree comprises an internal node, which is assigned either one of the next indicator and the yield indicator.

3. The method of claim 1, wherein the scheduling tree comprises an internal node, which is assigned both of the next indicator and the yield indicator.

4. The method of claim 1, wherein each node in the scheduling tree is assigned a priority, the method further comprising:

at each level of the scheduling tree, selecting a next highest priority node at the level if a top priority node at the level has the yield indicator.

5. The method of claim 1, wherein each node in the scheduling tree is assigned a priority, the method further comprising:

at each level of the scheduling tree, selecting a node with the next indicator if the priority of the node is within a predetermined range of a top priority at the level.

6. The method of claim 1, wherein each node in the scheduling tree is assigned a priority, the method further comprising:

at each level of the scheduling tree, selecting an internal node with both the next indicator and the yield indicator if the priority of the internal node is within a predetermined range of a top priority at the level.

7. A system comprising:

a memory to store a scheduling tree that represents a hierarchy of groups and processes that share central processing unit (CPU) time; and

a processing device coupled to the memory, the processing device is to;

assign a yield indicator to a first node of the scheduling tree, the first node representing a first process that temporarily yields the CPU time, wherein the yield indicator indicates that the first process has yielded CPU time to another process, wherein each node in the scheduling tree is assigned a priority, and wherein, at each level of the scheduling tree, the processing device selects a next highest priority node at the level if a top priority node at the level has the yield indicator;

assign the yield indicator to each of ancestor nodes of the first node in the scheduling tree, each ancestor node representing a group to which the first process belongs; and

select a second process to run on the processing device based on the yield indicator in the scheduling tree.

8. The system of claim 7, wherein the processing device is to:

assign a next indicator to a leaf node in the scheduling tree that represents a next process to run; and

assign the next indicator to each of ancestor nodes of the leaf node in the scheduling tree, wherein each ancestor node represents a group to which the next process belongs.

9. The system of claim 8, wherein the scheduling tree comprises an internal node, which is assigned either one of the next indicator and the yield indicator.

10. The system of claim 8, wherein the scheduling tree comprises an internal node, which is assigned both of the next indicator and the yield indicator.

11. A non-transitory computer readable storage medium comprising instructions that, when executed by a processing device, cause the processing device to perform operations comprising:

assigning, by the processing device, a yield indicator to a first node of a scheduling tree, wherein the scheduling tree represents a hierarchy of groups and processes that share central processing unit (CPU) time, wherein the first node represents a first process that temporarily yields the CPU time, wherein the yield indicator indicates that the first process has yielded CPU time to another process, and wherein each node in the scheduling tree is assigned a priority;

at each level of the scheduling tree, selecting an internal node with both a next indicator and the yield indicator if the priority of the internal node is within a determined range of a top priority at the level;

assigning the yield indicator to each of ancestor nodes of the first node in the scheduling tree, each ancestor node representing a group to which the first process belongs; and

selecting a second process to run on a computer system based on the yield indicator in the scheduling tree.

12. The non-transitory computer readable medium of claim 11, the operations further comprising:

assigning the next indicator to a leaf node in the scheduling tree that represents a next process to run; and

assigning the next indicator to each of ancestor nodes of the leaf node in the scheduling tree, each ancestor node representing a group to which the next process belongs.

13. The non-transitory computer readable medium of claim 12, wherein the internal node is assigned either one of the next indicator and the yield indicator.

14. The non-transitory computer readable medium of claim 12, wherein the internal node is assigned both of the next indicator and the yield indicator.

15. The non-transitory computer readable medium of claim 11, wherein the operations further comprise:

at each level of the scheduling tree, selecting a next highest priority node at the level if a top priority node at the level has the yield indicator.