Embedded systems use microcontrollers to perform the required actions according to the received inputs. The microcontroller offers (among others) I/O ports for interaction with the outside world and a CPU core to run the application program defined in the microcontroller software project. This project needs to include, besides the hardware dependent configuration, a task scheduler, code for peripheral control (drivers) and the actual application modules. The project can also include communication services, libraries and other components. In this article the focus is on scheduling algorithms starting from the super loop, state machine approach and, finally, OSEK/VDX schedulers.
We will refer to OSEK/VDX simply as OSEK.
The scheduler is a software module (piece of code) that manages the tasks of the application. Tasks implement one or more application functions. So the scheduler will call the defined application tasks according to the configuration. Basically, configuration of the tasks means linking each task to an event so that when the event happens, the task is executed. In more advanced schedulers, for a task, is configured also the priority and class of the task.
Note: In basic schedulers like the 'super loop' the priority and class of tasks are not configured, but are determined by the implementation of the application code. This case happens, for example, in a 'super loop' approach where somewhere in the code the call of function for task A is before call of function for task B; if the conditions for calling A and B happen in the same loop iteration, A will be called before B, so A has a higher priority than B.
Let's look at the scheduling algorithms we talked above:
This one is not really a scheduler but it is a way to run tasks. This works like this: in a WHILE(1) loop, all the conditions for running tasks are checked and task functions are called.
Pros: straight forward to implement
Cons: wastes CPU resources, the tasks are executed in an uncontrolled manner, code is hard to maintain
This method adds some structure to the application. Tasks are executed depending on the state's machine state. For more complex tasks nested state machines can be implemented.
Pros: code is easy to design and maintain
*Cons: CPU resources not used optimally, task scheduling is not an independent module (it is highly dependent on the application design)
OSEK standardises the specifications for automotive embedded systems. One of the areas comprised by OSEK specifications is the Operating System. OSEK defines the OSEK OS featuring the general event based scheduler and OSEKtime OS with the time triggered scheduler. Configuration of OSEK OS is done using standardised .oil files containing the tasks (with attributes), hooks, resources, alarms, events, messages, application modes, scheduler type, error handling.
The following items are available in the OSEK OS: tasks, events, resource management API's, alarms, messages, interrupt handling API's. Tasks are executed according to the configured priority and the scheduler preempts the currently running task if the pending task has a higher priority. At task termination, the scheduler resumes execution of the ready task with the highest priority. Task execution can be triggered in several ways: activation from another running task, expiration of an alarm counter, a configured interrupt or a message. Extended tasks can enter the waiting states where they wait for an event. When the event happens, the scheduler will resume the task if its priority is higher. Resources 'consumed' by tasks can be locked so no other task that uses the same resource can preempt the running task.
OSEK allows to run the operating system in one of several application modes (defined statically in the *.oil file). In each application mode, entirely different set of tasks (different applications) can be executed. For example: normal mode, diagnostic mode, bootloader mode ... The decision regarding the mode in which to run the software application is determined at run-time.
On errors OSEK executes the related hook routine (which can be configured by the application).
Application development starts with the system design / configuration (tasks, messages, alarms, events, application modes, etc). All configurations are stored into the files with .oil extension (OSEK implementation language). A .oil file can be created using the OSEK building tool, or manually, using the “OSEK OIL” language. To create the executable file, the .oil files should be transferred to the system generator. The system generator analyzes the .oil files and if everything is ok, it creates the source files, which together with the developer’s source code can be transferred to the compiler. This approach (using *.oil files) allows to port the software application not only to any microcontroller supported by the operating system, but also to use any OSEK-compatible operating systems.
At any given time, the scheduler selects the highest priority task from all ready tasks. If two tasks have the same priority, the scheduler selects the oldest task (i.e. activated first, FIFO principle). The next task (with the same or lower priority) is performed only after the current task is terminated or enters into waiting state. Execution of the current task can be interrupted only by the task with higher priority, otherwise the processor can only be released using the "Schedule" service. Using tasks with different types of scheduling makes sense, for example, in the software application with a mix of short and long tasks. Long tasks are more suitable for low-priority actions (memory check, I/O polling, etc.) with preemptive scheduling, while cooperative scheduling is more suitable for time-critical actions.
Every software application can be easily divided into several different tasks. Each task is executed independently and competes with all the other tasks for system resources. This approach simplifies the creation of applications (especially large), makes the application more independent from the microcontroller, simplifies product support during its life cycle (makes it easy to add new/correct old features), etc.
OSEK distinguishes two types of tasks: basic and extended. The difference between the two types of tasks is the availability in the extended tasks of the additional state, in which the task may be - waiting state. An extra state implies a separate stack for each extended task, while the basic tasks can share the same stack (it depends on the RTOS implementation). Also, unlike the extended tasks, the basic tasks may have several activations, i.e. instead of waiting for a certain event, the basic task completes its execution and when the event occurs - the task is reactivated, thus saving stack / RAM. Also, regardless of the type (basic or extended), the task can be "preemptive" or "cooperative".
OSEK is an event-driven RTOS with a fixed priority scheduling, which offers a lot of synchronization mechanisms (objects and services), which greatly simplifies the development of the software application. Every object generates a specific type of event (i.e. it transmits a specific amount of information):
The resources provided in an embedded application using OSEKtime are: the interrupts and the tasks. OSEKtime dispatches the tasks periodically according to the predefined dispatch table. The scheduler is preemptive, so, if a task must be activated while another one is running, then the scheduler will preempt the running task and start running the pending task. After finishing a task,the scheduler will resume running the preempted tasks if there are any. Some rules are limiting the preemption mechanism (like one that says that a task cannot preempt itself). Such cases are considered as anomalies and,OSEKtime OS will execute the user defined routine for such a case (like performing a CPU reset).
When a project is created, the first step is to configure one or more dispatch tables. More than one dispatch table is needed when different application modes are used in the project (like INIT mode and NORMAL mode). The user defines the tasks in each dispatch table by assigning the offset, period, deadline monitoring time and the function pointer of the task.
An OS tick time must also be configured by the user. The rule for calculating the tick time is that it must be less or equal to the greatest common divisor of all the task execution times. Also, it is recommended to use the greatest value possible so the OS will not spend too much time in the task management routine.
At run time, the OS will start running the tasks of the default application modes dispatch table. Users can request at any time the switch to another dispatch table (application mode) using a dedicated system service. The actual switch will happen at the end of the current dispatcher round (when all tasks from the current dispatch table are suspended).
Tasks are triggered at expiration of the assigned timer. The timer is reloaded with the task period at task execution. When the timer expires, the task state changes from suspended to running. If the task ends before any other task's timer expires, then the state changes from running to suspended. If another task's timer (task B) expires before ending the current task (task A), then task A state changes from running to preempted and task B state changes from suspended to running. At the end, task B changes to suspended state and task A changes from preempted to running state.
Note: the same happens if the timer of task A expires before task B ends, so for this type of scheduling we can say that there are no priority levels defined explicitly or implicitly.
The task execution time is compared with the predefined task deadline. If a task runs for more than the deadline time, then error handling is initiated by the OS. Basically, an error callback function is executed and then the OS shutdown is initiated. At OS shutdown, a second callback function is called. The user must configure / program these callback functions with the application specific actions. After returning from the second callback function, the OS reboots.
The user must configure the ISR's min recurrence time and program the ISR Handler routine. The ISR is disabled after servicing it for the min recurrence time. Inthis way, enough CPU time is ensured for running the tasks, even in cases where an ISR retriggers quickly.
Firstly, OS executes the idle task. The task content is application specific (so the user can define it). The idle task runs only in the 'free' time between the execution of the periodic tasks. It is preempted by all pending periodic tasks. One way to use the idle task is to call the 'sleep' instruction to put the CPU in idle mode.
OSEK standardizes also the communication service. Messages can be sent between tasks in the same CPU or between CPU's
by Ovidiu Mățan
by Axente Paul
by Olimpiu Pop
by Ovidiu Mățan