Starvation control in a data processing system

• US 9,639,396 B2
• Filed: 09/16/2014
• Issued: 05/02/2017
• Est. Priority Date: 09/16/2014
• Status: Expired due to Fees

• Current Assignee: NXP USA, Inc. (NXP Semiconductors NV)
• Original Assignee: NXP USA, Inc. (NXP Semiconductors NV)
• Inventors: Pho, Quyen, Moyer, William C.
• Primary Examiner(s): ST LEGER, GEOFFREY R
• Application Number:
  US14/487,897
• Publication Number:
  US 20160077870A1
• Time in Patent Office: 959 Days
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

A data processing system (100) includes a main list (126) of tasks, main scheduling scheme, a starvation list (128) of tasks, and a secondary scheduling scheme. A method identifies tasks in the main list that are potentially-starving tasks and places the potentially-starving tasks in the starvation list. A starvation monitor (130) controls starvation of tasks in the system by determining when to use the secondary scheduling scheme to schedule, for execution on a CPU (132), a highest priority task in the starvation list prior to scheduling, pursuant to the main scheduling scheme, other tasks in the main list. The starvation monitor determines a number of times that a task in the main list is pre-empted, by other tasks in the main list, from being scheduled for execution on the CPU. A counter (131) is incremented each occasion that any task not in the starvation list is executed on the CPU.

Claims

1. A method within a data processing system, comprising:

grading each task that enters the data processing system with a priority value and with a lifetime;

populating a main list with tasks in the data processing system that are in a ready-for-scheduling state;

scheduling, for executing on a central processing unit (CPU), a task in the main list that has a highest priority value;

identifying tasks in the main list that are not scheduled for execution on the CPU;

providing a starvation list;

copying into the starvation list tasks in the main list that are not scheduled for execution on the CPU;

executing on the CPU a task in the main list that has a highest priority among the tasks currently in the main list;

removing such task from the main list and from the starvation list;

repeating, a preselected number of times, the executing and the removing;

scheduling, for execution on the CPU, a highest priority task in the starvation list prior to scheduling other tasks that are currently in the main list;

providing a counter;

counting, by the counter, each occasion that any task that is not also in the starvation list is executed on the CPU;

determining whether a current number of occasions that any task not in the starvation list is executed on the CPU is equal to a threshold value, and

if so, then schedule for execution on the CPU a highest priority task in the starvation list prior to scheduling for execution on the CPU any other task in the main list, and after completion of the execution on the CPU of the highest priority task in the starvation list, removing such task from the starvation list and from the main list, and

if not so, then perform again the steps of executing, removing and counting; and

responsive to determining that there are no tasks in the starvation list and that there is at least one task in the main list, re-copying into the starvation list tasks in the main list that are not scheduled for execution on the CPU.

2. The method within a data processing system of claim 1, wherein the data processing system includes:

a global task control subsystem; and

at least one processing subsystem coupled to the global task control subsystem, the at least one processing subsystem including;

a task scheduler coupled to the main list, to the starvation list and to the CPU, wherein the task scheduler schedules and de-schedules tasks for execution on the CPU using one of a main scheduling scheme and a secondary scheduling scheme, and

a starvation monitor, coupled to the task scheduler, wherein the starvation monitor monitors the starvation list, and, if the starvation list is empty, the starvation monitor copies into the starvation list ready-for-scheduling tasks in the main list that are not scheduled for execution on the CPU,

wherein the starvation monitor determines a number of times that any task in the starvation list is pre-empted from being scheduled for execution on the CPU as a result of another task being scheduled for execution on the CPU using the main scheduling scheme.

3. The method within a data processing system of claim 2, wherein the starvation monitor determines, using the starvation list and the number of times that any task in the starvation list is pre-empted, when to implement the secondary scheduling scheme.

4. The method within a data processing system of claim 3, wherein the secondary scheduling scheme schedules, for execution on the CPU, the highest priority task in the starvation list prior to scheduling, pursuant to the main scheduling scheme, other tasks that are currently in the main list.

5. The method within a data processing system of claim 2, wherein the at least one processing subsystem includes a task state tracker, coupled to the task scheduler, that monitors a present state of each task in the at least one processing subsystem.

6. The method within a data processing system of claim 2, wherein the global task control subsystem includes a task creator and a task terminator, each coupled to a priority record, wherein the task creator assigns a task ID and a priority to each new task that enters the system, and wherein the priority record contains at least the ID and priority of all active tasks in the system.

7. The method within a data processing system of claim 6, wherein the main list comprises entries in a first-in first-out (FIFO) register, each entry comprising an ID of a task.

8. The method within a data processing system of claim 6, wherein the starvation list comprises entries in a FIFO register, each entry comprising an ID of a task.

9. The method within a data processing system of claim 6, wherein the data processing system includes more than one processing subsystem, wherein the task creator determines on which of the more than one processing subsystem to create each task, and wherein the priority record also includes information regarding to which of the more than one processing subsystem the task is assigned.

10. The method within a data processing system of claim 6, wherein the data processing system is communicatively coupled to a data network, and wherein the task creator responds to data communication packets, which arrive via the data network.

11. The method within a data processing system of claim 2, including at least one acceleration subsystem, coupled to the global task control subsystem and to the at least one processing subsystem, wherein the acceleration subsystem interacts with the at least one processing subsystem and provides acceleration operations on behalf of tasks running on the CPU.

12. A method within a data processing system, comprising:

assigning priority information to each task that enters the data processing system;

providing storage for a main list;

populating the main list with tasks which entered the data processing system that are in a ready-for-scheduling state;

identifying tasks in the main list that are potentially-starving tasks;

providing storage for a starvation list;

populating the starvation list with the potentially-starving tasks such that the potentially-starving tasks remain in the main list;

scheduling, for executing on a CPU, a task in the main list that currently has a highest priority among tasks currently in the main list;

removing such scheduled task from the main list and, if such scheduled task is also in the starvation list, removing such scheduled task from the starvation list after the CPU executes the such scheduled task;

selecting a threshold value;

counting each occasion that any task that is not also in the starvation list is executed on the CPU;

determining whether a current number of occasions that any task not in the starvation list is executed on the CPU is equal to the threshold value, and

if so, then schedule for execution on the CPU a highest priority task in the starvation list prior to scheduling for execution on the CPU any other task in the main list, and after completion of the execution on the CPU of the highest priority task in the starvation list, removing such task from the starvation list and from the main list, and

if not so, then repeat steps of scheduling, removing and counting; and

responsive to determining that there are no tasks in the starvation list and that there is at least one task in the main list, re-populate the starvation list with tasks from the main list.

13. The method of claim 12, further comprising:

providing a counter;

setting the counter to an initial value, wherein the threshold value corresponds to a certain count of the counter; and

selectively incrementing the counter based on whether a task that is executed on the CPU is also in the starvation list.

14. The method of claim 13, further comprising:

determining whether there are tasks in the starvation list, and

if there are tasks in the starvation list, then resetting the counter to the initial value, and repeat the steps from the step of scheduling to the step of determining, and

if there are no tasks in the starvation list, then resetting the counter to another value, and repeat the steps from the step of identifying to the step of determining.

15. The method of claim 13, wherein

the counter is incremented if the task that is executed on the CPU is not also in the starvation list, and

the counter is not incremented if the task that is executed on the CPU is also in the starvation list.