# US 2005/0097556 A1 · Intelligent scheduler for multi-level exhaustive scheduling

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

- Number: US 2005/0097556 A1
- Document ID: US20050097556A1
- Status: Published application
- Kind: A1
- Application number: 10/695,953
- Filed: 2003-10-30
- Published: 2005-05-05
- Earliest claimed: 2003-10-30
- Assignees: Alcatel
- Inventors: Sean Code; Aaron MacDonald
- Web page: https://patentgrep.com/patent/US20050097556A1

## 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 apparatus are provided for scheduling tasks within a computing device such as a communication switch. When a task is to be scheduled, other tasks in the work queue are analyzed to see if any can be executed simultaneously with the task to be scheduled. If so, the two tasks are combined to form a combined task, and the combined task is placed within the job queue. In addition, if the computing device has insufficient resources to execute the task to be scheduled, the task is placed back into the work queue for future scheduling. This is done in a way which avoids immediate reselection of the task for scheduling. Task processing efficiency is increased, since combining tasks reduces the waiting time for lower priority tasks, and tasks for which there are insufficient resources are delayed only a short while before a new scheduling attempt, rather than rejecting the task altogether.

## Claims

### Claim 1

A method of scheduling a first task within a computing device, comprising the steps of:
a. maintaining a work queue of a plurality of waiting tasks awaiting scheduling;
b. attempting to locate at least one selected task from within the work queue which is capable of being executed simultaneously with the first task; and
c. if at least one selected task is located, combining the at least one selected task with the first task to form a combined task, and scheduling the combined task.

### Claim 2 (depends on 1)

The method of claim 1 wherein each task has an associated priority, and wherein the method comprises the further step of selecting as the first task a waiting task for which no other waiting task has a higher priority.

### Claim 3 (depends on 2)

The method of claim 2 wherein the step of attempting to locate at least one selected task considers only waiting tasks having a priority equal to that of the first task.

### Claim 4

A processor for scheduling a first task within a computing device, comprising:
a. instructions for accessing a work queue of a plurality of waiting tasks awaiting scheduling;
b. instructions for attempting to locate at least one selected task from within the work queue which is capable of being executed simultaneously with the first task; and
c. instructions for combining the at least one selected task with the first task to form a combined task and scheduling the combined task, in the event that at least one selected task is located

### Claim 5 (depends on 4)

The processor of claim 4 wherein each task has an associated priority, and wherein the processor further comprises instructions for selecting as the first task a waiting task for which no other waiting task has a higher priority.

### Claim 6 (depends on 5)

The processor of claim 5 wherein the instructions for attempting to locate at least one selected task comprise instructions for considering only waiting tasks having a priority equal to that of the first task.

### Claim 7

A software-readable medium containing instructions for scheduling a first task within a computing device, comprising:
a. instructions for accessing a work queue of a plurality of waiting tasks awaiting scheduling;
b. instructions for attempting to locate at least one selected task from within the work queue which is capable of being executed simultaneously with the first task; and
c. instructions for combining the at least one selected task with the first task to form a combined task and scheduling the combined task, in the event that at least one selected task is located

### Claim 8 (depends on 7)

The software-readable medium of claim 7 wherein each task has an associated priority, and wherein the processor further comprises instructions for selecting as the first task a waiting task for which no other waiting task has a higher priority.

### Claim 9 (depends on 8)

The software-readable medium of claim 8 wherein the instructions for attempting to locate at least one selected task comprise instructions for considering only waiting tasks having a priority equal to that of the first task.

### Claim 10

A method of scheduling a first task within a computing device, comprising the steps of:
a. maintaining a work queue of a plurality of waiting tasks awaiting scheduling;
b. determining whether the computing device has sufficient resources to execute the first task; and
c. if the computing device has sufficient resources to execute the first task, the further steps of:
d. attempting to locate at least one selected task from within the work queue which is capable of being executed simultaneously with the first task; and
e. if at least one selected task is located, combining the at least one selected task with the first task to form a combined task, and scheduling the combined task.

### Claim 11 (depends on 10)

The method of claim 10 further comprising the steps of:
a. if the computing device does not have sufficient resources to execute the first task, the further steps of:
b. determining whether the first task is time sensitive;
c. if the first task is time sensitive, rejecting the first task; and
d. if the first task is not time sensitive, attempting to schedule a second task before attempting to schedule the first task.

### Claim 12

A processor for scheduling a first task within a computing device, comprising:
a. instructions for accessing a work queue of a plurality of waiting tasks awaiting scheduling;
b. instructions for determining whether the computing device has sufficient resources to execute the first task;
c. instructions for attempting to locate at least one selected task from within the work queue which is capable of being executed simultaneously with the first task, in the event that the computing device has sufficient resources to execute the first task; and
d. instructions for combining the at least one selected task with the first task to form a combined task and scheduling the combined task, in the event that the computing device has sufficient resources to execute the first task and that at least one selected task is located.

### Claim 13 (depends on 12)

The processor of claim 12 further comprising:
a. instructions for determining whether the first task is time sensitive, in the event that the computing device does not have sufficient resources to execute the first task;
b. instructions for rejecting the first task, in the event that the computing device does not have sufficient resources to execute the first task and that the first task is time sensitive; and
c. instructions for attempting to schedule a second task before attempting to schedule the first task, in the event that the computing device does not have sufficient resources to execute the first task and that the first task is not time sensitive.

### Claim 14

A software-readable medium comprising instructions for scheduling a first task within a computing device, comprising:
a. instructions for accessing a work queue of a plurality of waiting tasks awaiting scheduling;
b. instructions for determining whether the computing device has sufficient resources to execute the first task;
c. instructions for attempting to locate at least one selected task from within the work queue which is capable of being executed simultaneously with the first task, in the event that the computing device has sufficient resources to execute the first task; and
d. instructions for combining the at least one selected task with the first task to form a combined task and scheduling the combined task, in the event that the computing device has sufficient resources to execute the first task and that at least one selected task is located.

### Claim 15 (depends on 14)

The software-readable medium of claim 14 further comprising:
a. instructions for determining whether the first task is time sensitive, in the event that the computing device does not have sufficient resources to execute the first task;
b. instructions for rejecting the first task, in the event that the computing device does not have sufficient resources to execute the first task and that the first task is time sensitive; and
c. instructions for attempting to schedule a second task before attempting to schedule the first task, in the event that the computing device does not have sufficient resources to execute the first task and that the first task is not time sensitive.
