Task scheduling method and apparatus

• US 9,372,729 B2
• Filed: 03/15/2013
• Issued: 06/21/2016
• Est. Priority Date: 03/15/2006
• Status: Active Grant

• Current Assignee: NXP USA, Inc. (NXP Semiconductors NV)
• Original Assignee: Freescale Semiconductor, Inc. (NXP Semiconductors NV)
• Inventors: Fecioru, Mihai-Daniel
• Primary Examiner(s): Tang, Kenneth
• Application Number:
  US13/833,509
• Publication Number:
  US 20130212591A1
• Time in Patent Office: 1,194 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/4887 involving deadlines, e.g. rate based, periodic

Abstract

An apparatus schedules execution of a plurality of tasks by a processor. Each task has an associated periodicity and an associated priority based upon the associated periodicity. The processor executes each of the plurality of tasks periodically according to the associated periodicity of the task. A scheduler, at each of a series of scheduling time points updates the priorities of the plurality of tasks and schedules the tasks that need to be executed in accordance with their priorities. The scheduler identifies an unexecuted task which, at a preceding scheduling time point, was scheduled for execution but which, since that preceding scheduling time point, has not been executed. The scheduler sets the priority of the unexecuted task as greater than the priority of other tasks that have the same periodicity as the unexecuted task and that are not themselves unexecuted tasks.

Claims

1. An apparatus for scheduling execution of a plurality of tasks by a processor, each of the plurality of tasks having an associated periodicity and an associated priority based upon the associated periodicity comprising:

the processor to execute each of the plurality of tasks periodically according to the associated periodicity of the task; and

a scheduler, at each of a series of scheduling time points, to;

update the priorities of the plurality of tasks;

determine whether a task needs to be executed in accordance with the periodicity associated with that task;

group the plurality of tasks into a plurality of priority lists, each priority list of the plurality of priority lists has the same periodicities associated with the tasks grouped into the priority list, the plurality of priority lists includes a priority list of communication path tasks associated with communication paths that have just been closed; and

schedule the plurality of tasks that need to be executed in accordance with the priorities of the tasks, wherein the scheduler is to update the priorities of the plurality of tasks by;

identifying an unexecuted task which, at a preceding scheduling time point, was scheduled for execution but which, since that preceding scheduling time point, has not been executed; and

increasing the priority of the unexecuted task by setting the priority of the unexecuted task as greater than the priority of other tasks that have the same periodicity as the unexecuted task and that are not themselves unexecuted tasks.

2. The apparatus of claim 1, wherein the scheduler, upon identifying the unexecuted task, is to instruct the processor to perform one or more auxiliary operations of the unexecuted task wherein the one or more auxiliary operations of the unexecuted task are selected from a group that consists of:

updating a time-dependent variable;

updating a variable that is dependent on a number of scheduling time points that have passed for the unexecuted task; and

updating task statistics.

3. The apparatus of claim 1, in which a first task, having a smaller periodicity than a second task, has a higher priority than the second task.

4. The apparatus of claim 1, the scheduler further to:

schedule a periodic task of the plurality of tasks as a high priority task.

5. The apparatus of claim 4, the scheduler further to:

schedule a task execution task of the plurality of tasks as a low priority task.

6. The apparatus of claim 1, wherein the scheduler is to assign a higher priority to tasks in the priority list of communication path tasks associated with communication paths that have just been closed than to tasks in the other priority lists of the plurality of priority lists.

7. The apparatus of claim 6, wherein the scheduler is to activate tasks of the plurality of tasks that are due for execution and to identify a highest priority task from the activated tasks.

8. The apparatus of claim 7, wherein the scheduler is to activate all of the communication path tasks in a given priority list at the same time.

9. The apparatus of claim 1, wherein the scheduler is to assign a higher priority to a first task of the plurality of tasks than to a second task of the plurality of tasks based upon:

the associated periodicity of the first task equaling the associated periodicity of the second task; and

the first task constituting a data processing task and the second task constituting a voice processing task.

10. A non-transitory computer-readable medium comprising instructions to manipulate one or more processors on one or more computing devices, the instructions comprising a plug-in to an operating system, the plug-in containing:

instructions to update the priorities of a plurality of tasks, each of the plurality of tasks having an associated periodicity and each of the plurality of tasks to be executed according to the associated periodicity;

instructions to determine whether a task of the plurality of tasks needs to be executed in accordance with the periodicity associated with that task;

instructions to group the plurality of tasks into a plurality of priority lists, each priority list of the plurality of priority lists has the same periodicities associated with the tasks grouped into the priority list, the plurality of priority lists includes a priority lists of communication path tasks associated with communication paths that have just been close; and

instructions to schedule the plurality of tasks that need to be executed in order to complete them in accordance with their periodicity.

11. The computer-readable medium of claim 10, further comprising instructions of the operating system to assign communications tasks to the plug-in for scheduling.

12. The computer-readable medium of claim 10, further comprising instructions of the operating system to schedule execution of the instructions of the plug-in, wherein the instructions of the plug-in are scheduled as high priority tasks.

13. A method of scheduling execution of a plurality of tasks by a processor, each of the plurality of tasks having an associated periodicity, each of the plurality of tasks having an associated priority based upon the associated periodicity of the task, and the plurality of tasks arranged in priority queues, wherein all tasks in a priority queue have the same associated periodicity, the method comprising:

executing tasks of the plurality of tasks by the processor periodically, according to the associated periodicity of the tasks; and

at each of a series of scheduling time points;

updating the priorities of the tasks; and

scheduling the plurality of tasks that need to be executed in accordance with the priorities of the tasks, wherein the updating comprises;

searching for a task with higher priority than the scheduled tasks;

if a task with a higher priority than a scheduled task is found, attempting to replace the scheduled task with the higher priority task on a schedule of tasks;

if the attempt is not successful, increasing the priority of the task with the higher priority within the priority queue of the higher priority task; and

if the attempt to replace the scheduled task with the task with the higher priority is not successful at a scheduling time point and if the task with the higher priority has higher priority than another scheduled task at the next scheduling time point, replacing the other scheduled task with the task with the higher priority on the schedule pursuant to a policy wherein a higher priority task is not permitted to fail twice to replace a lower priority scheduled task.

14. The method of claim 13, wherein the updating comprises:

determining whether a task of the plurality of tasks is to be closed; and

if the task is to be closed, setting the priority of the task to be higher than priorities of other tasks of the plurality of tasks that are not to be closed.

15. The method of claim 13, wherein there is a fixed time interval between successive scheduling time points.

16. The method of claim 15, wherein the fixed time interval between successive scheduling time points is a greatest common divisor of the periodicities associated with the tasks.

17. The method of claim 15, wherein the updating comprises:

assigning a higher priority to a first task than to a second task based on the associated periodicity of the first task being smaller than the associated periodicity of the second task; and

assigning a higher priority to a third task than to a fourth task based on the associated periodicity of the third task being equal to the associated periodicity of the fourth task and based upon the third task constituting a data processing task and the fourth task constituting a voice processing task.