Task scheduling method and apparatus

• US 8,438,572 B2
• Filed: 03/15/2006
• Issued: 05/07/2013
• 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:
  US12/282,489
• Publication Number:
  US 20090031319A1
• Time in Patent Office: 2,610 Days
• Field of Search: None
• 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 execution of a task that is scheduled for execution after the processor has completed the current task, the method comprising:

executing by the processor a current task;

scheduling a next task for execution by the processor;

after scheduling the next task, determining whether there is a high priority task to be executed by the processor; and

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

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

if the processor has not begun loading the data for execution of 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; and

if the processor has begun loading the data for execution of the next task into the processor memory, maintaining the next task as scheduled for execution after the processor has completed the current task.

2. A method according to claim 1, in which each task of the tasks has an associated priority and determining whether there is a high priority task comprises determining whether there is a task having a higher priority than the next task.

3. A method according to claim 1, wherein:

the loading into the processor memory of the data for execution of the task that is scheduled for execution after the processor has completed the current task is by a direct-memory-access process.

4. The method of claim 1, wherein;

the processor has a first buffer and a second buffer;

data for execution of the current task is stored in the first buffer; and

the data for execution of the next task is stored in the second buffer.

5. The method of claim 1, further comprising if the processor maintains the next task as scheduled for execution after the processor has completed the current task, beginning execution of an auxiliary operation of the high priority task before the processor has completed execution of the next task, wherein the auxiliary operation of the high priority task is selected from a group consisting 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.

6. The method of claim 1, wherein:

the plurality of tasks comprises a plurality of periodic tasks; and

the method further comprises;

adopting a method of scheduling non-periodic tasks,

determining whether a task is periodic; and

if the task is determined to be non-periodic, scheduling the task by the adopted method of scheduling non-periodic tasks.

7. The method of claim 6, wherein:

determining whether a task is periodic comprises determining that task management tasks are non-periodic; and

the method further comprises assigning a lowest priority to task management tasks.

8. The method of claim 1, wherein determining that there is a high priority task is not based upon whether the processor has begun loading the data for execution of the next task into the processor memory.

9. The method of claim 1, further comprising scheduling the high priority task for execution after the processor has completed the next task if the processor has begun loading the data for execution of the next task into the processor memory.

10. An apparatus for scheduling execution of a plurality of tasks by a processor, the apparatus comprising:

the processor, having a processor memory, to execute a current task and to load into the processor memory, during execution of a current task, data for execution of a next task, wherein the scheduled execution of the next task is after the completion of the current task;

a scheduler to schedule the next task for execution by the processor and to determine, after scheduling the next task for execution, whether there is a high priority task to be executed by the processor, wherein the scheduler, if there is a high priority task to be executed by the processor, is to;

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

if the processor has not begun loading the data for execution of 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; and

if the processor has begun loading the data for execution of the next task into the processor memory, to maintain the next task as scheduled for execution after the processor has completed the current task.

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

12. An apparatus according to claim 10, in which each task of the tasks has an associated priority and the scheduler is to determine whether there is a high priority task by determining whether there is a task of the tasks having a higher priority than the next task.

13. The apparatus of claim 10, wherein:

the processor memory has a first buffer and a second buffer;

data for execution of the current task is stored in the first buffer; and

the data for execution of the next task is stored in the second buffer.

14. The apparatus of claim 10, wherein the loading data for execution of the next task into the processor memory during execution of the current task is loading by a direct-memory-access process.

15. The apparatus of claim 10, wherein, if the processor maintains the next task as scheduled for execution after the processor has completed the current task, the processor is further to begin execution of an auxiliary operation of the high priority task before the processor has completed execution of the next task, wherein the auxiliary operation of the high priority task is selected from a group consisting 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.

16. The apparatus of claim 10, wherein:

the plurality of tasks comprises a plurality of periodic tasks and a plurality of non-periodic tasks; and

the scheduler is to;

adopt a method of scheduling non-periodic tasks,

determine whether a task is periodic; and

if the task is determined to be non-periodic, schedule the task by the adopted method of scheduling non-periodic tasks.

17. The apparatus of claim 16, wherein:

determining whether a task is periodic comprises determining that task management tasks are non-periodic; and

the scheduler is to assign a lowest priority to task management tasks.

18. A non-transitory computer-readable medium comprising a plurality of instructions to manipulate one or more processors on one or more computing devices, the plurality of instructions comprising:

instructions to execute a current task by a processor of the one or more processors;

instructions to schedule a next task for execution by the processor;

instructions to determine whether there is a high priority task to be executed by the processor, the determination to be made after the scheduling the next task;

instructions to determine whether the processor has begun loading data for execution of the next task into a memory of the processor memory, if there is a high priority task to be executed by the processor;

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

instructions to maintain the next task as scheduled for execution after the processor has completed the current task if there is a high priority task to be executed by the processor and if the processor has begun loading the data for execution of the next task into the processor memory.

19. The computer-readable medium of claim 18, wherein:

the next task has a priority; and

determining whether there is a high priority task comprises determining whether there is a task having a higher priority than the next task.

20. The computer-readable medium of claim 18, further comprising instructions to begin execution of an auxiliary operation of the high priority task before the processor has completed execution of the next task, if the processor maintains the next task as scheduled for execution after the processor has completed the current task, wherein the auxiliary operation of the high priority task is selected from a group consisting 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.