A Real Time Operating System or RTOS is an operating system that has been developed for real-time applications. Typically used for embedded applications they usually have the following characteristics:
Many real-time operating systems have scheduler and hardware driver designs that minimize the periods for which interrupts are disabled, a number sometimes called the interrupt latency.
Many also include special forms of memory management that limit the possibility of memory fragmentation, and assure a minimal upper bound on memory allocation and deallocation times.
It is a fallacy to believe that this type of operating system is "efficient" in the sense of having high throughput. The specialized scheduling algorithm and a high clock-interrupt rate can both interfere with throughput.
An early example of a large-scale real-time operating system was the so-called "control program" developed by American Airlines and IBM for the Sabre Airline Reservations System.
| Table of contents |
|
1.1 Scheduling
2 Example RTOSes1.2 Task interfaces to each other 1.3 Interrupt interface to the scheduler 1.4 Memory allocation 3 Quotation |
There are two basic designs. An event-driven operating system only changes tasks when an event requries service. A time-sharing design switches tasks on a clock interrupt, as well as on events.
The time-sharing design wastes more CPU time on unnecessary task-switches. However it also gives a better illusion of multitasking.
In typical designs, a task has three states: running, ready and blocked. Most tasks are blocked, most of the time. Only one task per CPU is running. The ready list is usually short, two or three tasks at most.
The real trick is designing the scheduler. Usually the data structure of the ready list in the scheduler is designed so that search, insertion and deletion require locking interrupts only for small periods of time, when looking at precisely defined parts of the list.
This means that other tasks can operate on the list asynchronously, while it is being searched. A typical successful schedule is a bidirectional linked list of ready tasks, sorted in order by priority. Note that this is not fast to search, but it is deterministic. Most ready lists are only two or three entries long, so a sequential search is usually the fastest, because it requries so little set-up time.
The critical response time, sometimes called the flyback time is the time it takes to queue a new ready task, and restore the state of the highest priority task.
In a well-designed RTOS, readying a new task will take 3-20 instructions per ready queue entry, and restoration of the highest-priority ready task will take 5-30 instructions.
On a 20MHz 68000 processor, task switch times run about 20 microseconds with two tasks ready. 100 MIP ARM CPUs switch in a few microseconds.
The only multitasking problem that multitasked systems have to solve is that they cannot use the same data or hardware at the same time. There are two notably successful designs for coping with this problem.
One design uses semaphores. Basically, a semaphore is either locked, or unlocked. When locked a queue of tasks are waiting for the semaphore.
Problems with semaphore designs are well known: priority inversion and deadlocks.
In priority inversion, a high priority task waits because a low priority task has a semaphore. A typical solution is to have the task that has a semaphore run at the priority of the highest waiting task.
In a deadlock, two tasks get two semaphores, but in the opposite order. This is usually solved by careful design, implementing queues, or having floored semaphores, that pass control of a semaphore to the higher priority task on defined conditions.
The other solution is to have tasks send messages to each other. These have exactly the same problems: Priority inversion occurs when a task is working on a low-priority message, and ignores a higher-priority message in its in-box. Deadlocks happen when two tasks wait for the other to respond.
Although their real-time behavior is less crisp than semaphore systems, message-based systems usually unstick themselves, and are generally better-behaved than semaphore systems.
Typically, the interrupt does a few things that it must do to keep the electronics happy, then it unlocks a semaphore blocking a driver task, or sends a message to a waiting driver task.
There are two problems with memory allocation in a RTOS.
Firstly, speed of allocation is important. A standard memory allocation scheme scans a linked list of indeterminate length to find a suitable free memory block; however this is unacceptable as memory allocation has to occur in a fixed time in a RTOS.
Secondly, memory can become fragmented as free regions become separated by regions that are in-use. This can cause a program to stall, unable to get memory, even though there is theoretically enough available.
One solution is to have a LIFO linked list of fixed size blocks of memory. This works astonishingly well for a simple system.
Another solution is to have a binary buddy block allocator. In this system, memory is allocated from a large block of memory that is a power of two in size. If the block is more than twice as large as desired, it is broken in two. One of the halves is selected, and the process repeats (checking the size again and splitting if needed) until the block is just large enough.
All the buddies of a particular size are kept in a sorted linked list or tree. When a block is freed, it is compared to its buddy. If they are both free, they are combined and placed in the next-largest size buddy-block list. (When a block is allocated, the allocator will start with the smallest sufficiently large block avoiding needlessly breaking blocks)
Note that buddy block allocators are not unique to RTOS's, they are also used in conventional operating systems (such as the Linux kernel).
Design Philosophies
Scheduling
Task interfaces to each other
Interrupt interface to the scheduler
Memory allocation
Example RTOSes
Various companies also sell customised versions of Linux with added real time functionality.