TASK SCHEDULING METHOD AND APPARATUS

• US 20090031319A1
• Filed: 03/15/2006
• Published: 01/29/2009
• 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
• Granted Patent: US 8,438,572 B2
• Time in Patent Office: Days
• US Class Current: 718/103
• 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

A method of scheduling execution of a plurality of tasks by a processor, the processor having a processor memory, the processor being arranged to load into the processor memory, during execution of a current task, data for a task that is scheduled for execution after the processor has completed the current task, the method comprising the steps of scheduling a next task for execution by the processor after the processor has completed a current task, and determining whether there is a high priority task to be executed by the processor, if there is a high priority task to be executed by the processor: determining whether the processor has begun loading the data for the next task into the processor memory, and if the processor has not begun loading the data for the next task into the processor memory, scheduling the high priority task, instead of the next task, for execution by the processor after the processor has completed the current task.

Claims

1. A method of scheduling execution of a plurality of tasks by a processor, the processor having a processor memory, the processor being arranged to load into the processor memory, during execution of a current task, data for a task that is scheduled for execution after the processor has completed the current task, the method comprising the steps of:

scheduling a next task for execution by the processor after the processor has completed a current task;

determining whether there is a high priority task to be executed by the processor;

if there is a high priority task to be executed by the processor;

determining whether the processor has begun loading the data for the next task into the processor memory; and

if the processor has not begun loading the data for the next task into the processor memory, scheduling the high priority task, instead of the next task, for execution by the processor after the processor has completed the current task.

5. A method according to claim 1, in which each task has an associated priority and the step of determining whether there is a high priority task comprises determining whether there is a task having a higher priority than the next task that needs executing by the processor.

2-4. -4. (canceled)

6. A method of scheduling execution of a plurality of tasks by a processor, each of the tasks having an associated periodicity and each of the tasks to be executed by the processor periodically according to the associated periodicity, the method comprising performing, at each of a series of scheduling time points, the steps of:

updating the priorities of the tasks;

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

scheduling the tasks that need to be executed in accordance with the priorities of the tasks.

7-19. -19. (canceled)

21. A scheduling apparatus for scheduling execution of a plurality of tasks by a processor, the processor having a processor memory, the processor being arranged to load into the processor memory, during execution of a current task, data for a task that is scheduled for execution after the processor has completed the current task, the apparatus comprising:

a scheduler operable to schedule a next task for execution by the processor after the processor has completed a current task and to determine whether there is a high priority task to be executed by the processor;

wherein the scheduler is operable, if there is a high priority task to be executed by the processor, to;

determine whether the processor has begun loading the data for the next task into the processor memory; and

if the processor has not begun loading the data for the next task into the processor memory, to schedule the high priority task, instead of the next task, for execution by the processor after the processor has completed the current task.

22. An apparatus according to claim 21, in which the scheduler is operable, if there is a high priority task to be executed by the processor and if the processor has begun loading the data for the next task into the processor memory, to maintain the next task as scheduled for execution after the processor has completed the current task.

23. An apparatus according to claim 22, in which the scheduler is operable, if there is a high priority task to be executed by the processor and if the processor has begun loading the data for the next task into the processor memory, to schedule the high priority task for execution after the processor has completed the next task.

24. An apparatus according to claim 21, in which each task has an associated priority and the scheduler is operable to determine whether there is a high priority task by determining whether there is a task having a higher priority than the current task that needs executing by the processor.

25. An apparatus according to claim 21, in which each task has an associated priority and the scheduler is operable to determine whether there is a high priority task by determining whether there is a task having a higher priority than the next task that needs executing by the processor.

26. A scheduling apparatus for scheduling execution of a plurality of tasks by a processor, each of the tasks having an associated periodicity and each of the tasks to be executed by the processor periodically according to the associated periodicity, the apparatus comprising:

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

update the priorities of the tasks;

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

schedule the tasks that need to be executed in accordance with the priorities of the tasks.

27. An apparatus according to claim 26, in which the scheduler is operable to update the priorities of the 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.

28. An apparatus according to claim 27, in which the scheduler is operable to increase 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.

29. An apparatus according to claim 27 in which the scheduler is operable, upon identifying an unexecuted task, to instruct the processor to perform one or more operations of the unexecuted task which are essential to the unexecuted task.

30. An apparatus according to claim 29, in which the one or more operations of the unexecuted task that are essential to the unexecuted task include one or more 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.

31. An apparatus according to claim 26, in which the scheduler is operable to update the priorities of the tasks by:

determining whether a task is to be closed; and

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

32. An apparatus according to claim 26, in which a first task, having a smaller periodicity than a second task, has a higher priority than the second task.

33. An apparatus according to claim 26, in which the time between successive scheduling time points is determined in accordance with the periodicity of the tasks.

34. An apparatus according to claim 33, in which the time between successive scheduling time points is the greatest common divisor of the periodicities of the tasks.

35-52. -52. (canceled)

53. A data carrying medium carrying a computer program which, when executed by a computer performing the steps comprising:

scheduling a next task for execution by the processor after the processor has completed a current task;

determining whether there is a high priority task to be executed by the processor;

if there is a high priority task to be executed by the processor;

determining whether the processor has begun loading the data for the next task into the processor memory; and

if the processor has not begun loading the data for the next task into the processor memory, scheduling the high priority task, instead of the next task, for execution by the processor after the processor has completed the current task.