18 September 2009
Setting your priorities
The increasing complexity of today's microcontroller systems is making ever greater demands on the embedded software engineers that bring them to life. At the same time, the latest microcontrollers are achieving higher performance than ever, with more complex peripherals and larger embedded memories.
To harness this extra performance and integration – while taming the complexity of modern applications – the use of a real time operating system (RTOS) is becoming more commonplace. A key feature of an RTOS is that of multitasking. A multitasking environment allows a program to be broken down into multiple tasks with each one 'thinking' it has the cpu to itself. It is like having multiple cpus.
A modern RTOS will use priority based scheduling of tasks and this article will discuss how scheduling is undertaken. One aspect of scheduling in a priority based system is the allocation of priorities to the various tasks. Often, what is deemed the most important task will be given the highest priority, but this isn't necessarily the most efficient method of priority allocation. Schemes for assigning priorities and determining whether a system can meet its scheduling deadlines will also be discussed.
RTOS scheduling
The scheduler is the part of the RTOS that decides which task should be running on the cpu at any given time. In normal execution, a task performs the functionality of the user's application and will then make a blocking call of some sort; for example, an OS derived time delay or waiting for a semaphore or other signal from an interrupt service routine (ISR) or another task. A blocked task will be suspended by the operating system and another task run. When the time delay expires or the event occurs, the task unblocks and can be scheduled to run by the OS. If a low priority task is running on the cpu and a high priority task becomes ready to run in a pre emptive priority based system, a context switch will occur – the low priority task will suspended and the high priority task will be given the cpu. The low priority task is said to be pre empted by the high priority task.
Assigning task priorities
The majority of RTOSs implement pre emptive priority based scheduling as this is well suited to embedded systems requiring fast response to real time events. But how does the engineer actually assign priorities to tasks in the system? Giving the most important task in the system the highest priority may not have the desired effect.
There are a number of methods of assigning priorities, including: Earliest Deadline First; Deadline-Monotonic Scheduling; and Rate-Monotonic Scheduling.
Earliest Deadline First (EDF) scheduling uses a queue of tasks in order of priority. When a task blocks, the RTOS searches the queue for the task closest to its deadline and selects it as the next to run. This is a useful scheme as it is possible to guarantee all task deadlines are met at high levels of cpu utilisation. However, there is a cost in terms of complexity and execution time of the RTOS scheduler code.
Deadline-Monotonic Scheduling is a fixed priority pre emptive priority allocation scheme where priorities are assigned by giving the task with shortest deadline the highest priority. This assignment scheme is suited to tasks which have deadlines equal to or less than their periods and have worst case execution times equal to or less than their deadlines.
Rate-Monotonic Scheduling (RMS), meanwhile, is a fixed priority pre emptive priority allocation scheme gaining in popularity. Being a fixed priority scheme, no special modification to the RTOS is necessary. With RMS, it is possible to guarantee that a key set of tasks will meet their deadlines and that the system is schedulable. A further benefit is that system performance degrades gracefully during overload conditions, with the lowest priority tasks missing deadlines.
RMS assumes:
* All tasks are periodic
* All tasks have deterministic deadlines equal to their periods
* Tasks do not share resources; for example, no blocking semaphores
* Tasks have fixed priorities and the highest priority task will always run
* Tasks with shortest deadlines (periods) have the highest priorities
* Context switches and RTOS operations use no cpu resources
The key point here is that the highest priority is allocated to the task with the shortest period. The next highest priority is assigned to the task with the next shortest period and so on. Using Rate-Monotonic Analysis (RMA), it is possible to determine whether a system with task priorities allocated in this way can be scheduled or, in other words, whether critical tasks will miss any deadlines.
Under RMA, the second point above is relaxed and tasks no longer need to have equal periods and deadlines, so long as the deadline is less than or equal to the period. For example, a task may have a period (T) of 150ms and a computation time (C) of 50ms. This means the task must be able to run for 50ms every 150ms. This allows us to calculate the utilisation (U) of the cpu using the following equation:
U = ? Ci/Ti
The total utilisation of the CPU is the sum of all the individual task utilisations. There are utilisation limits dependent upon the number of tasks, n, in the system, as given by a second equation:
n(nv2 -1)
As n grows, the utilisation limit tends towards logn2, so the cpu utilisation limit for n tasks is 0.693, or 69.3%. Providing the cpu utilisation is less than 69.3%, the system can meet all deadlines. The remaining 30% can be utilised for other tasks without hard real-time deadlines.
Consider the following example of a three task system:
Task A: period = 150ms, computation time = 20ms
Task B: period = 80ms, computation time = 30ms
Task C: period = 15ms, computation time = 2ms
The task utilisations will therefore be:
Task A: 13.33% [(20/150) x 100%]
Task B: 37.5% [(30/80) x 100%]
Task C: 13.33% [(2/15) x 100%]
The total utilisation becomes 64.16%. As long as the priorities are assigned in the ascending order Task C > Task B > Task A, the system will be schedulable as the utilisation value is less than 69.3%.
It is possible to extend RMA further to take into account context switching time and to modify the system when non periodic tasks are used and when shared resources are part of the system.
To help embedded electronics engineers gather more information and experience using real time operating systems, Renesas has produced the RTOS Evaluator. For more information, click here.
Author
Ian Hall, Renesas Technology Europe
Supporting Information
Websites
http://www.renesas.eu
Companies
Renesas Electronics Europe Ltd
This material is protected by Findlay Media copyright
See Terms
and Conditions.
One-off usage is permitted but bulk copying is not.
For multiple copies contact the
sales team.