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.
In typical designs, a task has three states: running, ready and blocked. Most tasks are blocked for 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 68,000 processor, task switch times run about 20 microseconds with two tasks ready. 100 MHz ARM CPUs switch in a few microseconds.