Single-stack real-time operating system for embedded systems

• US 8,209,694 B2
• Filed: 10/12/2010
• Issued: 06/26/2012
• Est. Priority Date: 10/13/2009
• Status: Active Grant

• Current Assignee: Turck Holding GmbH
• Original Assignee: Turck Holding GmbH
• Inventors: Glistvain, Roman
• Primary Examiner(s): Puente, Emerson
• Assistant Examiner(s): KESSLER, GREGORY AARON
• Application Number:
  US12/902,596
• Publication Number:
  US 20110088037A1
• Time in Patent Office: 623 Days
• Field of Search: None
• US Class Current: 718/103
• CPC Class Codes: G06F 9/4843 by program, e.g. task dispatcher, supervisor, operating system
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

A real time operating system (RTOS) for embedded controllers having limited memory includes a continuations library, a wide range of macros that hide continuation point management, nested blocking functions, and a communications stack. The RTOS executes at least a first and second task and uses a plurality of task priorities. The tasks share only a single stack. The task scheduler switches control to the highest-priority task. The continuations library provides macros to automatically manage the continuation points. The yield function sets a first continuation point in the first task and yields control to the task scheduler, whereupon the task scheduler switches to the second task and wherein at a later time the task scheduler switches control back to the first task at the first continuation point. The nested blocking function invokes other blocking functions from within its body and yields control to the task scheduler.

Claims

1. A computer processor and memory running a real-time operating system (RTOS) for the computer processor performing a first plurality of tasks including a first task and a second task, the RTOS comprising:

a subsystem providing a plurality of task priorities such that not all of the first plurality of tasks run at the same priority, wherein the first plurality of tasks share and use only a single stack;

a plurality of task queues including a pending queue, a running queue and a blocked queue;

a task scheduler that uses the plurality of task queues including the pending queue, the running queue and the blocked queue, and that, when invoked, switches control to a highest-priority one from the pending queue of the first plurality of tasks;

a continuations library subsystem that automatically manages a plurality of continuation points including a first continuation point;

a yield function that sets the first continuation point in the first task and yields control to the task scheduler, whereupon the task scheduler switches control to the second task and wherein at a later time the task scheduler switches control back to the first task at the first continuation point; and

a nested blocking function call subsystem, that invokes a second blocking function in the second task from within a first blocking function in the second task and yields control to the task scheduler, wherein the first blocking function identifies to the RTOS which event is to be waited for, wherein the event has an associated event control block that contains a pointer to a task control block of a task that is currently blocked on the event, such that the RTOS determines from the event control block of the event which task to invoke when the event is triggered, and if there is a task is waiting for this event when the event triggers, then the pending queue of tasks is updated, else a new event state is saved in an event control block and when the task next needs to wait for the event, the task checks the event state in the event control block and determines that the task does not need to be blocked.

2. The RTOS of claim 1, wherein the continuations library subsystem includes a plurality of macros that automate management of continuation points without other input from a user of the RTOS.

3. The RTOS of claim 1, wherein the single stack is a single rewinding stack.

4. The RTOS of claim 1, further including an executing task having a first priority;

wherein the yield function includes a conditional-yield capability that yields control to the task scheduler only when at least one of the plurality of tasks has a higher priority than the first priority of the executing task.

5. The RTOS of claim 1, further including one or more event control blocks used for event handling, including a first event control block associated with a first event used in the first task to continue after a first event used in the first blocking function is triggered to restore control to the first task, and a second event control block associated with a second event used in the second task to continue after a second event used in the second blocking function is triggered to restore control to the second task.

6. The RTOS of claim 1, wherein each of the first plurality of tasks has a unique single-bit-position priority number.

7. The RTOS of claim 1, wherein, for handling reentrant blocking functions, the continuations library subsystem includes:

a compile-time allocator of resources for reentrant blocking functions;

built-in constructs for declaring local variables of reentrant blocking functions in structures;

inheritance-tree structures for creation of hierarchical storage of local and global variables used in context of reentrant blocking functions;

a binder that binds structures used for reentrant blocking functions to tasks and that stores the structures in a task control block;

a manager of hierarchical tasks to provide functionality of hierarchical scheduling; and

macros for accessing variables.

8. A computerized method of real-time operating system (RTOS) operation of a computer processor having a memory, the method comprising:

providing a single stack;

performing, in the computer processor, a first plurality of tasks including a first task and a second task, wherein not all of the first plurality of tasks run at the same priority, wherein the first plurality of tasks share and use only the single stack;

scheduling tasks using a plurality of task queues including a pending queue, a running queue and a blocked queue;

using and sharing the single stack by all of the first plurality of tasks;

automatically managing a plurality of continuation points, wherein the plurality of continuation points includes a first continuation point and a second continuation point;

creating the first continuation point in the first task and yielding control to the scheduling of tasks, wherein the scheduling of tasks includes selectively switching control to a highest-priority one of the first plurality of tasks, wherein the second task is the highest-priority one from the pending queue of the first plurality of tasks;

switching control back to the first task at the first continuation point at a later time; and

executing a first blocking function within the first task such that the scheduling of tasks switches to the second task and executing a second blocking function in the second task before continuing the first task after the first blocking function has executed, wherein the first blocking function identifies to the RTOS which event is to be waited for, wherein the event has an associated event control block that contains a pointer to a task control block of a task that is currently blocked on the event, such that the RTOS determines from the event control block of the event which task to invoke when the event is triggered, and if there is a task is waiting for this event when the event triggers, then the pending queue of tasks is updated, else a new event state is saved in an event control block and when the task next needs to wait for the event, the task checks the event state in the event control block and determines that the task does not need to be blocked.

9. The method of claim 8, wherein the creating of the first continuation point includes using a macro that automates management of the first continuation point without other input from a user of the RTOS.

10. The method of claim 8, wherein the providing of the single stack includes providing a single rewinding stack.

11. The method of claim 8, further including executing the first task having a first priority;

wherein the yielding of control to the scheduling of tasks includes conditionally yielding control to the scheduling of tasks only when at least one of the plurality of tasks has a higher priority than the first priority of the executing first task.

12. The method of claim 8, further including handling events, wherein the handling of events uses a first event control block associated with a first event used in the first task to continue after a first event used in the first blocking function is triggered to restore control to the first task, and a second event control block associated with a second event used in the second task to continue after a second event used in the second blocking function is triggered to restore control to the second task.

13. A non-transitory computer-readable medium having instructions embedded thereon, wherein the instructions, when performed on a computer processor, execute a method of real-time operating system (RTOS) operation, the method comprising:

providing a single stack;

performing, in the computer processor, a first plurality of tasks including a first task and a second task, wherein not all of the first plurality of tasks run at the same priority, wherein the first plurality of tasks share and use only the single stack;

scheduling tasks using a plurality of task queues including a pending queue, a running queue and a blocked queue;

using and sharing the single stack by all of the first plurality of tasks;

automatically managing a plurality of continuation points, wherein the plurality of continuation points includes a first continuation point and a second continuation point;

creating the first continuation point in the first task and yielding control to the scheduling of tasks, wherein the scheduling of tasks includes selectively switching control to a highest-priority one from the pending queue of the first plurality of tasks, wherein the second task is the highest-priority one of the first plurality of tasks;

switching control back to the first task at the first continuation point at a later time; and

executing a first blocking function within the first task such that the scheduling of tasks switches to the second task and executing a second blocking function in the second task before continuing the first task after the first blocking function has executed, wherein the first blocking function identifies to the RTOS which event is to be waited for, wherein the event has an associated event control block that contains a pointer to a task control block of a task that is currently blocked on the event, such that the RTOS determines from the event control block of the event which task to invoke when the event is triggered, and if there is a task is waiting for this event when the event triggers, then the pending queue of tasks is updated, else a new event state is saved in an event control block and when the task next needs to wait for the event, the task checks the event state in the event control block and determines that the task does not need to be blocked.

14. The computer-readable medium of claim 13, further comprising instructions such that the creating of the first continuation point includes using a macro that automates management of the first continuation point without other input from a user of the RTOS.

15. The computer-readable medium of claim 13, further comprising instructions such that the single stack is a single rewinding stack.

16. The computer-readable medium of claim 13, further comprising instructions such that the first task is executed at a first priority;

wherein the yielding of control to the scheduling of tasks includes conditionally yielding control to the scheduling of tasks only when at least one of the plurality of tasks has a higher priority than the first priority of the first task.

17. The computer-readable medium of claim 13, further comprising instructions such that the method further includes handling events, wherein the handling of events uses a first event control block associated with a first event used in the first task to continue after a first event used in the first blocking function is triggered to restore control to the first task, and a second event control block associated with a second event used in the second task to continue after a second event used in the second blocking function is triggered to restore control to the second task.

18. A computing apparatus including a processor and memory running a real-time operating system (RTOS), the apparatus comprising:

a single stack;

means for performing, in the computing apparatus, a first plurality of tasks including a first task and a second task, wherein not all of the first plurality of tasks run at the same priority, wherein the first plurality of tasks share and use only the single stack;

a plurality of task queues including a pending queue, a running queue and a blocked queue;

a task scheduler that uses the plurality of task queues including the pending queue, the running queue and the blocked queue;

means for using and sharing the single stack by all of the first plurality of tasks;

means for automatically managing a plurality of continuation points, wherein the plurality of continuation points includes a first continuation point and a second continuation point;

means for creating the first continuation point in the first task and for yielding control to the task scheduler;

means for selectively switching control to a highest-priority one from the pending queue of the first plurality of tasks using the task scheduler, wherein the second task is the highest-priority one of the first plurality of tasks;

means for switching control back to the first task at the first continuation point at a later time; and

means for executing a first blocking function within the first task such that the task scheduler switches to the second task and executing a second blocking function in the second task before the first task is continued after the first blocking function has executed, wherein the first blocking function identifies to the RTOS which event is to be waited for, wherein the event has an associated event control block that contains a pointer to a task control block of a task that is currently blocked on the event, such that the RTOS determines from the event control block of the event which task to invoke when the event is triggered, and if there is a task is waiting for this event when the event triggers, then the pending queue of tasks is updated, else a new event state is saved in an event control block and when the task next needs to wait for the event, the task checks the event state in the event control block and determines that the task does not need to be blocked.

19. The computing apparatus of claim 18, wherein the means for creating the first continuation point includes means for using a macro that automates management of the first continuation point without other input from a user of the RTOS.

20. The computing apparatus of claim 18, wherein the single stack is a single rewinding stack.

21. The computing apparatus of claim 18, wherein the first task is executed at a first priority;

wherein the means for yielding control to the task scheduler includes means for conditionally yielding control to the task scheduler only when at least one of the plurality of tasks has a higher priority than the first priority of the first task.

22. The computing apparatus of claim 18, further including means for handling events, wherein the means for handling of events uses a first event control block associated with a first event used in the first task to continue after a first event used in the first blocking function is triggered to restore control to the first task, and a second event control block associated with a second event used in the second task to continue after a second event used in the second blocking function is triggered to restore control to the second task.