# US 2012/0233623 A1 · Using a yield indicator in a hierarchical scheduler

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2012/0233623 A1
- Document ID: US20120233623A1
- Status: Published application
- Kind: A1
- Application number: 13/041,882
- Filed: 2011-03-07
- Published: 2012-09-13
- Earliest claimed: 2011-03-07
- Assignees: Red Hat, Inc.
- Inventors: Henri Han van Riel
- Web page: https://patentgrep.com/patent/US20120233623A1

## CPC

- G06F 9/4881: {Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## 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

### Claim 1

A method, implemented by a computer system programmed to perform the following, comprising:
assigning, by the computer system, 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 and the first node represents a first process that temporarily yields the CPU time;
assigning, by the computer system, 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, by the computer system, a second process to run on the computer system based on the yield indicator in the scheduling tree.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
assigning, by the computer system, a next indicator to a leaf node in the scheduling tree that represents a next process to run; and
assigning, by the computer system, 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.

### Claim 3 (depends on 2)

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

### Claim 4 (depends on 2)

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

### Claim 5 (depends on 1)

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.

### Claim 6 (depends on 1)

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 a next indicator if the priority of the node is within a predetermined range of a top priority at the level.

### Claim 7 (depends on 1)

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 a 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.

### Claim 8

A system comprising:
memory, which stores a scheduling tree that represents a hierarchy of groups and processes that share central processing unit (CPU) time; and
a processor coupled to the memory, the processor 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;
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 processor based on the yield indicator in the scheduling tree.

### Claim 9 (depends on 8)

The system of claim 8, wherein the processor 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.

### Claim 10 (depends on 9)

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

### Claim 11 (depends on 9)

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

### Claim 12 (depends on 8)

The system of claim 8, wherein each node in the scheduling tree is assigned a priority, and wherein, at each level of the scheduling tree, the processor selects a next highest priority node at the level if a top priority node at the level has the yield indicator.

### Claim 13 (depends on 8)

The system of claim 8, wherein each node in the scheduling tree is assigned a priority, and wherein, at each level of the scheduling tree, the processor selects a node with a next indicator if the priority of the node is within a predetermined range of a top priority at the level.

### Claim 14

A non-transitory computer readable storage medium including instructions that, when executed by a processing system, cause the processing system to perform a method comprising:
assigning 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 and the first node represents a first process that temporarily yields the CPU time;
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.

### Claim 15 (depends on 14)

The non-transitory computer readable medium of claim 14, further comprising:
assigning a 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.

### Claim 16 (depends on 15)

The non-transitory computer readable medium of claim 15, wherein the scheduling tree comprises an internal node, which is assigned either one of the next indicator and the yield indicator.

### Claim 17 (depends on 15)

The non-transitory computer readable medium of claim 15, wherein the scheduling tree comprises an internal node, which is assigned both of the next indicator and the yield indicator.

### Claim 18 (depends on 14)

The non-transitory computer readable medium of claim 14, 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.

### Claim 19 (depends on 14)

The non-transitory computer readable medium of claim 14, wherein each node in the scheduling tree is assigned a priority, the method further comprising:
at each level of the scheduling tree, selecting anode with a next indicator if the priority of the node is within a predetermined range of a top priority at the level.

### Claim 20 (depends on 14)

The non-transitory computer readable medium of claim 14, 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 a 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.
