| • Science | • People | • Locations | • Timeline |
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.
There are two basic designs:
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. 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 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:
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.
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.