Hardware assisted method and system for scheduling time critical tasks

• US 9,135,062 B2
• Filed: 04/09/2013
• Issued: 09/15/2015
• Est. Priority Date: 04/09/2013
• Status: Active Grant

• Current Assignee: National Instruments Corporation (Emerson Electric Company)
• Original Assignee: National Instruments Corporation (Emerson Electric Company)
• Inventors: Chandhoke, Sundeep, Salmon, Herbert K. IV
• Primary Examiner(s): Puente, Emerson
• Assistant Examiner(s): DO, STEVEN M
• Application Number:
  US13/859,030
• Publication Number:
  US 20140304709A1
• Time in Patent Office: 889 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 2209/486 Scheduler internals
• CPC Class Codes: G06F 9/4825 Interrupt from clock, e.g. time of day
• CPC Class Codes: G06F 9/4887 involving deadlines, e.g. rate based, periodic

Abstract

A method and system for scheduling a time critical task. The system may include a processing unit, a hardware assist scheduler, and a memory coupled to both the processing unit and the hardware assist scheduler. The method may include receiving timing information for executing the time critical task, the time critical task executing program instructions via a thread on a core of a processing unit and scheduling the time critical task based on the received timing information. The method may further include programming a lateness timer, waiting for a wakeup time to obtain and notifying the processing unit of the scheduling. Additionally, the method may include executing, on the core of the processing unit, the time critical task in accordance with the scheduling, monitoring the lateness timer, and asserting a thread execution interrupt in response to the lateness timer expiring, thereby suspending execution of the time critical task.

Claims

1. A method for monitoring a time critical task, the method comprising:

receiving timing information for executing the time critical task, wherein the time critical task executes program instructions via a thread on a core of a processing unit;

scheduling the time critical task, wherein said scheduling comprises determining, based on the received timing information, a wakeup time, a thread cycle time, an overall thread deadline, and a time critical task deadline;

wherein the time critical task deadline is a function of the overall thread deadline and a specified thread bandwidth, wherein the specified thread bandwidth indicates a fraction of the thread cycle time reserved for the time critical task;

programming a lateness timer based on the wakeup time and the time critical task deadline;

waiting for the wakeup time to obtain;

notifying the processing unit of said scheduling, wherein said notifying indicates to the processing unit that the thread is in an idle state, wherein the idle state indicates that the thread is awake and ready to resume execution and execute the time critical task in accordance with said scheduling;

executing, on the core of the processing unit, the time critical task in accordance with said scheduling;

monitoring the lateness timer; and

asserting a thread interrupt in response to the lateness timer expiring, wherein said asserting interrupts said executing, thereby suspending execution of the time critical task.

2. The method of claim 1, wherein said notifying comprises a memory write to a memory of the processing unit, wherein the method further comprises:

monitoring the memory, by the processing unit, for the memory write to indicate said notifying.

3. The method of claim 1, wherein said notifying comprises a timed thread execution, wherein the timed thread execution comprises:

synchronizing, via a time monitor circuit, a clock of the processing unit with a global clock; and

monitoring, by the processing unit via the time monitor circuit, the clock of the processing unit with respect to the wakeup time; and

determining that the wakeup time obtains; and

wherein the method further comprises;

resuming the execution of the thread in response to said determining that the wakeup time obtains.

4. The method of claim 1, wherein the overall thread deadline is the difference between the thread cycle time and a system dependent suspend latency.

5. The method of claim 1, wherein said suspending execution of the time critical task comprises:

suspending execution of the thread; and

returning the thread to the idle state, thereby ensuring a timely wakeup of the thread for execution of another cycle of the time critical task.

6. The method of claim 1, wherein the thread comprises a multiplexed thread, wherein the multiplexed thread is executed on the core of the processing unit, wherein the multiplexed thread comprises a plurality of time critical tasks including the time critical task, wherein each of the plurality of time critical tasks has respective timing information, and wherein each of the plurality of time critical tasks is executed in accordance with the respective timing information.

7. The method of claim 1, wherein the thread comprises a multiplexed thread, wherein the multiplexed thread is executed on the core of the processing unit, wherein the multiplexed thread comprises:

one or more time critical tasks; and

a best effort task.

8. The method of claim 7, further comprising:

waking up the best effort task in response to the lateness timer expiring;

executing the best effort task until the overall thread deadline obtains;

resetting the lateness timer;

suspending the thread; and

returning the thread to the idle state, thereby ensuring a timely wakeup of the thread for execution of another cycle of the time critical task.

9. The method of claim 8, further comprising:

receiving timing information for executing the best effort task; and

scheduling the best effort task, wherein said scheduling the best effort task comprises;

determining, based on the received timing information, a start time for the best effort task, wherein the start time is later than the time critical task deadline.

10. A system for scheduling a time critical task, the system comprising:

a processing unit;

a device configured as a hardware assist scheduler; and

a memory coupled to the processing unit and the hardware assist scheduler;

wherein the hardware assist scheduler is configured to;

receive timing information for executing the time critical task, wherein the time critical task executes program instructions via a thread on a core of the processing unit;

schedule the time critical task, wherein to schedule the time critical task, the device determines, based on the received timing information, a wakeup time, a thread cycle time, an overall thread deadline, and a time critical task deadline;

wherein the time critical task deadline is a function of the overall thread deadline and a specified thread bandwidth, wherein the specified thread bandwidth indicates a fraction of the thread cycle time reserved for the time critical task;

program a lateness timer based on the wakeup time and the time critical task deadline;

wait for the wakeup time to obtain;

notify the processing unit of the schedule, wherein to notify, the hardware assist scheduler is configured to indicate to the processing unit that the thread is in an idle state, wherein the idle state indicates that the thread is awake and ready to resume execution and execute the time critical task in accordance with the schedule;

monitor the lateness timer; and

assert a thread interrupt in response to the lateness timer expiring, wherein to assert the thread interrupt, the hardware assist scheduler is configured to interrupt execution of the thread on the core of the processing unit, thereby suspending execution of the time critical task; and

wherein the processing unit is configured to;

resume execution of the thread upon notification that the thread is in the idle state; and

execute the time critical task on the thread.

11. The system of claim 10, wherein, to notify the processing unit of the schedule, the hardware assist scheduler is further configured to perform a memory write to the memory, and wherein the processing unit is further configured to monitor the memory for the memory write.

12. The system of claim 10, wherein, to notify the processing unit of the schedule, the hardware assist scheduler is further configured to provide a global clock signal, and wherein the processing unit is further configured to:

perform a timed thread execution, wherein, to perform the timed thread execution, the processing unit is configured to;

synchronize, via a time monitor circuit, a clock of the processing unit with the global clock;

monitor, via the time monitor circuit, the clock of the processing unit with respect to the wakeup time; and

determine that the wakeup time obtains; and

resume the execution of the thread in response to the wakeup time obtaining.

13. The system of claim 10, wherein the overall thread deadline is the difference between the thread cycle time and a system dependent suspend latency.

14. The system of claim 10, wherein, to suspend execution of the time critical task, the hardware assist scheduler is further configured to:

suspend execution of the thread; and

return the thread to the idle state, thereby ensuring a timely wakeup of the thread for execution of another cycle of the time critical task.

15. The system of claim 10, wherein the thread comprises a multiplexed thread, wherein the multiplexed thread is executed on the core of the processing unit, wherein the multiplexed thread comprises a plurality of time critical tasks including the time critical task, wherein each of the plurality of time critical tasks has respective timing information, and wherein each of the plurality of time critical tasks is executed in accordance with the respective timing information.

16. The system of claim 10, wherein the thread comprises a multiplexed thread, wherein the multiplexed thread is executed on the core of the processing unit, wherein the multiplexed thread comprises:

one or more time critical tasks; and

a best effort task.

17. The system of claim 16, wherein the hardware assist scheduler is further configured to:

wake up the best effort task in response to the lateness timer expiring; and

notify the processing unit that the best effort task is awake and ready to be executed;

reset the lateness timer;

suspend the thread; and

return the thread to the idle state, thereby ensuring a timely wakeup of the thread for execution of another cycle of the time critical task.

18. The system of claim 17, wherein the hardware assist scheduler is further configured to:

receive timing information for executing the best effort task; and

schedule the best effort task, wherein, to schedule the best effort task, the hardware assist scheduler is configured to;

determine, based on the received timing information, a start time for the best effort task, wherein the start time is later than the time critical task deadline.

19. The system of claim 10, wherein the processing unit comprises a plurality of cores, wherein the hardware assist scheduler comprises a core of the plurality of cores of the processing unit, and wherein the time critical tasks execute on at least one other core of the plurality of cores of the processing unit.

20. The system of claim 10, wherein the processing unit is a first processing unit, and wherein the hardware assist scheduler comprises a second processing unit.

21. The system of claim 10, wherein the system further comprises:

an interconnect, wherein the interconnect communicatively couples the hardware assist scheduler to the memory and to the processing unit.

22. The system of claim 21, wherein the interconnect comprises a high speed interconnect.

23. The system of claim 21, wherein the interconnect comprises a photonics interconnect.