STARVATION CONTROL IN A DATA PROCESSING SYSTEM

• US 20160077870A1
• Filed: 09/16/2014
• Published: 03/17/2016
• Est. Priority Date: 09/16/2014
• Status: Active Grant

• Current Assignee: NXP USA, Inc. (NXP Semiconductors NV)
• Original Assignee: Freescale Semiconductor, Inc. (NXP Semiconductors NV)
• Inventors: Pho, Quyen, Moyer, William C.
• Granted Patent: US 9,639,396 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 data processing system, comprising:

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 a main list of ready-for-scheduling tasks and to a CPU, and

wherein the task scheduler is coupled to a starvation list of potentially-starved ready-for-scheduling tasks and to a starvation monitor,

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

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.

2. The data processing system of claim 1, 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.

3. The data processing system of claim 2, wherein the secondary scheduling scheme schedules, for execution on the CPU, a 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.

4. The data processing system of claim 3, wherein the starvation monitor includes a counter that counts the number of times that any task in the starvation list is pre-empted.

5. The data processing system of claim 1, 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 data processing system of claim 1, 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 data processing system of claim 6, wherein the main list comprises entries in a FIFO register, each entry comprising an ID of a task.

8. The 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 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 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 data processing system of claim 1, 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 a priority to each task that enters the data processing system;

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

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

populating a starvation list with the potentially-starving tasks.

13. The method of claim 12, further comprising:

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

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

14. The method of claim 13, further comprising:

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

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.

15. The method of claim 14, further comprising:

after executing on the CPU the highest priority task in the starvation list, removing such task from the starvation list and from the main list.

16. The method of claim 13, further comprising:

repeating, until there are no more tasks in the starvation list, the executing and the removing;

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

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

re-populating the starvation list with the potentially-starving tasks.

17. The method of claim 13, further comprising:

providing a counter;

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

conveying the count of the counter to a debugger.

18. 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;

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 from the starvation list after the CPU executes the scheduled task;

selecting a threshold value;

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

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 repeat steps of scheduling, removing and counting, and

if not 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 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.

19. The method of claim 18, further comprising:

providing a counter; and

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

wherein the counting each occasion that any task not in the starvation list is executed on the CPU is performed by incrementing the counter.

20. The method of claim 19, 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.