Real-time operating system

A Real Time Operating System (RTOS) is an operating system that has been developed for real-time applications. It is typically used for embedded applications, such as mobile telephones, industrial robots, or scientific research equipment.

An RTOS facilitates the creation of real-time systems, but does not guarantee that they are real-time; this requires correct development of the system level software. Nor does an RTOS necessarily have high throughput — rather they allow though specialized scheduling algorithms and deterministic behavior the guarantee that system deadlines can be met. That is, an RTOS is valued more for how quickly it can respond to an event than for the total amount of work it can do. Key factors in evaluating an RTOS are therefore maximal interrupt and thread latency.

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 computing.

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, but gives better multitasking, the illusion that a user has sole use of a machine.

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:

• Semaphores
• Message passing

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

Open source:

• eCos
• FreeRTOS
• Nut/OS [1]
• Prex
• RTAI
• RTEMS [2]
• RTLinux
• SHaRK [3]
• TRON Project
• Fiasco (L4 clone) [4]

Proprietary:

• BeOS
• ChorusOS
• ITRON
• LynxOS
• MicroC/OS-II
• Nucleus
• OS-9
• OSE
• OSEK/VDX
• OSEKtime
• pSOS
• QNX
• RMX
• RSX-11
• RT-11
• RTOS-UH
• VRTX
• VxWorks
• Windows CE
• µnOS
• RTX - Windows Real-time Extension
• Phar Lap ETS

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.

See also

• Synchronous programming language