Real-time operating system
|
|
A Real Time Operating System or RTOS is an operating system that has been developed for real-time applications. Typically used for embedded applications. Note that this type of operating system does not necessarily have 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.
Debate exists about what actually constitutes real-time.
| Contents |
Design Philosophies
There are two basic designs:
- An event-driven operating system only changes tasks when an event requires 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.
Scheduling
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. Although not fast to search, the time taken is deterministic. Most ready lists are only two or three entries long, so a sequential search is usually the fastest, because it requires 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 MHz ARM CPUs switch in a few microseconds.
Task interfaces to each other
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:
A semaphore is either locked, or unlocked. When locked a queue of tasks wait 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 lock two semaphores, but in the opposite order. This is usually solved by careful design, implementing queues, or by having floored semaphores (which 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.
Interrupt interface to the scheduler
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.
Memory allocation
Memory allocation is even more critical in a RTOS than in other operating systems.
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. Memory allocation algorithms that slowly accumulate fragmentation may work fine for desktop machines—when rebooted every month or so—but are unacceptable for embedded systems that often run for years without rebooting.
The simple "fixed-size-blocks" algorithm works astonishingly well for simple embedded systems.
See memory allocation for more details.
Use of memory in deeply embedded systems
Most embedded OSes store an entire binary code image in ROM, from which it also executes. That is, unlike PC-style operating systems, code is never stored in RAM. The reason for this is that the code is never expected to change, as embedded devices usually are dedicated to a specific purpose. The behaviour of the system is completely specified at design-time.
Example RTOSes
- BeOS
- ChorusOS
- eCos
- FreeRTOS (http://www.freertos.org)
- ITRON
- LynxOS
- MicroC/OS-II
- Nucleus
- Nut/OS (http://www.ethernut.de)
- OS-9
- OSE
- OSEK/VDX
- OSEKtime
- pSOS
- QNX
- RMX
- RSX-11
- RT-11
- RTOS-UH
- VRTX
- VxWorks
- Windows CE
- RTLinux
- RTAI
See also: List of operating systems
Various companies also sell customized versions of Linux with added real-time functionality. On October 8, 2004, Montavista submitted patches to the Linux kernel mailing list to enhance Linux as a real time operating system.
Quotation
- "If you're serious about doing real-time, why do you want an operating system?" —Anonymous
de:Echtzeitbetriebssystem
es:Sistema operativo en tiempo real
ko:실시간 운영체제
lt:Realaus laiko operacinė sistema
pl:System czasu rzeczywistego
ja:リアルタイムオペレーティングシステム
ru:Операционная система реального времени
th:ระบบปฏิบัติการแบบทันที