Information about Real Time Operating System
A real-time operating system (RTOS) is a multitasking operating system intended for real-time applications. Such applications include embedded systems (programmable thermostats, household appliance controllers, mobile telephones), industrial robots, spacecraft, industrial control (see SCADA), and scientific research equipment.
An RTOS facilitates the creation of a real-time system, but does not guarantee the final result will be real-time; this requires correct development of the software. An RTOS does not necessarily have high throughput; rather, an RTOS provides facilities which, if used properly, guarantee deadlines can be met generally (soft real-time) or deterministically (hard real-time). An RTOS will typically use specialized scheduling algorithms in order to provide the real-time developer with the tools necessary to produce deterministic behavior in the final system. An RTOS is valued more for how quickly and/or predictably it can respond to a particular event than for the given amount of work it can perform over time. Key factors in an RTOS are therefore a minimal interrupt latency and a minimal thread switching 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.
Early CPU designs needed many cycles to switch tasks, during which the CPU could do nothing useful. So early OSes tried to minimize wasting CPU time by maximally avoiding unnecessary task-switches.
More recent CPUs take far less time to switch from one task to another; the extreme case is barrel processors that switch from one task to the next in zero cycles. Newer RTOSes almost invariably implement time-sharing scheduling with priority driven pre-emptive scheduling.
The real key is designing the scheduler. Usually the data structure of the ready list in the scheduler is designed to minimize the worst-case length of time spent in the scheduler's critical section, during which preemption is inhibited, and, in some cases, all interrupts are disabled. But, the choice of data structure depends also on the maximum number of tasks that can be on the ready list.
If there are never more than a few tasks on the ready list, then a simple unsorted bidirectional linked list of ready tasks is likely optimal. If the ready list usually contains only a few tasks but occasionally contains more, then the list should be sorted by priority, so that finding the highest priority task to run does not require iterating through the entire list. Inserting a task then requires walking the ready list until reaching either the end of the list, or a task of lower priority than that of the task being inserted. Care must be taken not to inhibit preemption during this entire search; the otherwise-long critical section should probably be divided into small pieces, so that if, during the insertion of a low priority task, an interrupt occurs that makes a high priority task ready, that high priority task can be inserted and run immediately (before the low priority task is inserted).
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.
In more advanced real-time systems, real-time tasks share computing resources with many non-real-time tasks, and the ready list can be arbitrarily long. In such systems, a scheduler ready list implemented as a linked list would be inadequate.
On single-processor systems, if the application runs in kernel mode and can mask interrupts, often that is the best (lowest overhead) solution to preventing simultaneous access to a shared resource. While interrupts are masked, the current task has exclusive use of the CPU; no other task or interrupt can take control, so the critical section is effectively protected. When the task exits its critical section, it must unmask interrupts; pending interrupts, if any, will then execute. Temporarily masking interrupts should only be done when the longest path through the critical section is shorter than the desired maximum interrupt latency, or else this method will increase the system's maximum interrupt latency. Typically this method of protection is used only when the critical section is just a few source code lines long and contains no loops. This method is ideal for protecting hardware bitmapped registers when the bits are controlled by different tasks.
When the critical section is longer than a few source code lines or involves lengthy looping, an embedded/real-time programmer must resort to using mechanisms identical or similar to those available on general-purpose operating systems, such as semaphores and OS-supervised interprocess messaging. Such mechanisms involve system calls, and usually invoke the OS's dispatcher code on exit, so they can take many hundreds of CPU instructions to execute, while masking interrupts may take as few as three instructions on some processors. But for longer critical sections, there may be no choice; interrupts cannot be masked for long periods without increasing the system's interrupt latency.
A binary semaphore is either locked or unlocked. When it is locked, a queue of tasks can wait for the semaphore. Typically a task can set a timeout on its wait for a semaphore. Problems with semaphore based 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 (inherit) the priority of the highest waiting task. But this simplistic approach fails when there are multiple levels of waiting (A waits for a binary semaphore locked by B, which waits for a binary semaphore locked by C). Handling multiple levels of inheritance without introducing instability in cycles is not straightforward.
In a deadlock, two or more tasks lock a number of binary semaphores and then wait forever (no timeout) for other binary semaphores, creating a cyclic dependency graph. The simplest deadlock scenario occurs when two tasks lock two semaphores in lockstep, but in the opposite order. Deadlock is usually prevented by careful design, or by having floored semaphores (which pass control of a semaphore to the higher priority task on defined conditions).
The other approach to resource sharing is for tasks to send messages. In this paradigm, the resource is managed directly by only one task; when another task wants to interrogate or manipulate the resource, it sends a message to the managing task. This paradigm suffers from similar problems as binary semaphores: Priority inversion occurs when a task is working on a low-priority message, and ignores a higher-priority message (or a message originating indirectly from a high priority task) in its in-box. Protocol deadlocks occur when two or more tasks wait for each other to send response messages.
Although their real-time behavior is less crisp than semaphore systems, simple message-based systems usually do not have protocol deadlock hazards, and are generally better-behaved than semaphore 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 an 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.
Another real strength of fixed size blocks is for DSP systems particularly where one core is performing one section of the pipeline and the next section is being done on another core. In this case, fixed size buffer management with one core filling the buffers and another set of cores returning the buffers is very efficient. A DSP optimized RTOS like Unison Operating System or DSPnano RTOS provides these features.
See memory allocation for more details.
An RTOS facilitates the creation of a real-time system, but does not guarantee the final result will be real-time; this requires correct development of the software. An RTOS does not necessarily have high throughput; rather, an RTOS provides facilities which, if used properly, guarantee deadlines can be met generally (soft real-time) or deterministically (hard real-time). An RTOS will typically use specialized scheduling algorithms in order to provide the real-time developer with the tools necessary to produce deterministic behavior in the final system. An RTOS is valued more for how quickly and/or predictably it can respond to a particular event than for the given amount of work it can perform over time. Key factors in an RTOS are therefore a minimal interrupt latency and a minimal thread switching 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
Two basic designs exist:- Event-driven (priority scheduling) designs switch tasks only when an event of higher priority needs service, called preemptive priority.
- Time-sharing designs switch tasks on a clock interrupt, and on events, called round robin.
Early CPU designs needed many cycles to switch tasks, during which the CPU could do nothing useful. So early OSes tried to minimize wasting CPU time by maximally avoiding unnecessary task-switches.
More recent CPUs take far less time to switch from one task to another; the extreme case is barrel processors that switch from one task to the next in zero cycles. Newer RTOSes almost invariably implement time-sharing scheduling with priority driven pre-emptive scheduling.
Scheduling
In typical designs, a task has three states: 1) running, 2) ready, 3) blocked. Most tasks are blocked, most of the time. Only one task per CPU is running. In simpler systems, the ready list is usually short, two or three tasks at most.The real key is designing the scheduler. Usually the data structure of the ready list in the scheduler is designed to minimize the worst-case length of time spent in the scheduler's critical section, during which preemption is inhibited, and, in some cases, all interrupts are disabled. But, the choice of data structure depends also on the maximum number of tasks that can be on the ready list.
If there are never more than a few tasks on the ready list, then a simple unsorted bidirectional linked list of ready tasks is likely optimal. If the ready list usually contains only a few tasks but occasionally contains more, then the list should be sorted by priority, so that finding the highest priority task to run does not require iterating through the entire list. Inserting a task then requires walking the ready list until reaching either the end of the list, or a task of lower priority than that of the task being inserted. Care must be taken not to inhibit preemption during this entire search; the otherwise-long critical section should probably be divided into small pieces, so that if, during the insertion of a low priority task, an interrupt occurs that makes a high priority task ready, that high priority task can be inserted and run immediately (before the low priority task is inserted).
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.
In more advanced real-time systems, real-time tasks share computing resources with many non-real-time tasks, and the ready list can be arbitrarily long. In such systems, a scheduler ready list implemented as a linked list would be inadequate.
Intertask communication and resource sharing
Multitasking systems must manage sharing data and hardware resources among multiple tasks. It is usually "unsafe" for two tasks to access the same specific data or hardware resource simultaneously. ("Unsafe" means the results are inconsistent or unpredictable, particularly when one task is in the midst of changing a data collection. The view by another task is best done either before any change begins, or after changes are completely finished.) There are three common approaches to resolve this problem:- Temporarily masking/disabling interrupts
- Binary semaphores
- Message passing
On single-processor systems, if the application runs in kernel mode and can mask interrupts, often that is the best (lowest overhead) solution to preventing simultaneous access to a shared resource. While interrupts are masked, the current task has exclusive use of the CPU; no other task or interrupt can take control, so the critical section is effectively protected. When the task exits its critical section, it must unmask interrupts; pending interrupts, if any, will then execute. Temporarily masking interrupts should only be done when the longest path through the critical section is shorter than the desired maximum interrupt latency, or else this method will increase the system's maximum interrupt latency. Typically this method of protection is used only when the critical section is just a few source code lines long and contains no loops. This method is ideal for protecting hardware bitmapped registers when the bits are controlled by different tasks.
When the critical section is longer than a few source code lines or involves lengthy looping, an embedded/real-time programmer must resort to using mechanisms identical or similar to those available on general-purpose operating systems, such as semaphores and OS-supervised interprocess messaging. Such mechanisms involve system calls, and usually invoke the OS's dispatcher code on exit, so they can take many hundreds of CPU instructions to execute, while masking interrupts may take as few as three instructions on some processors. But for longer critical sections, there may be no choice; interrupts cannot be masked for long periods without increasing the system's interrupt latency.
A binary semaphore is either locked or unlocked. When it is locked, a queue of tasks can wait for the semaphore. Typically a task can set a timeout on its wait for a semaphore. Problems with semaphore based 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 (inherit) the priority of the highest waiting task. But this simplistic approach fails when there are multiple levels of waiting (A waits for a binary semaphore locked by B, which waits for a binary semaphore locked by C). Handling multiple levels of inheritance without introducing instability in cycles is not straightforward.
In a deadlock, two or more tasks lock a number of binary semaphores and then wait forever (no timeout) for other binary semaphores, creating a cyclic dependency graph. The simplest deadlock scenario occurs when two tasks lock two semaphores in lockstep, but in the opposite order. Deadlock is usually prevented by careful design, or by having floored semaphores (which pass control of a semaphore to the higher priority task on defined conditions).
The other approach to resource sharing is for tasks to send messages. In this paradigm, the resource is managed directly by only one task; when another task wants to interrogate or manipulate the resource, it sends a message to the managing task. This paradigm suffers from similar problems as binary semaphores: Priority inversion occurs when a task is working on a low-priority message, and ignores a higher-priority message (or a message originating indirectly from a high priority task) in its in-box. Protocol deadlocks occur when two or more tasks wait for each other to send response messages.
Although their real-time behavior is less crisp than semaphore systems, simple message-based systems usually do not have protocol deadlock hazards, and are generally better-behaved than semaphore systems.
Interrupt handlers and the scheduler
Since an interrupt handler blocks the highest priority task from running, and since real time operating systems are designed to keep thread latency to a minimum, interrupt handlers are typically kept as short as possible. The interrupt handler defers all interaction with the hardware as long as possible; typically all that is necessary is to acknowledge or disable the interrupt (so that it won't occur again when the interrupt handler returns). The interrupt handler then queues work to be done at a lower priority level, often by unblocking a driver task (through releasing a semaphore or sending a message). The scheduler often provides the ability to unblock a task from interrupt handler context.Memory allocation
Memory allocation is even more critical in an 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 an 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.
Another real strength of fixed size blocks is for DSP systems particularly where one core is performing one section of the pipeline and the next section is being done on another core. In this case, fixed size buffer management with one core filling the buffers and another set of cores returning the buffers is very efficient. A DSP optimized RTOS like Unison Operating System or DSPnano RTOS provides these features.
See memory allocation for more details.
See also
- Operating system
- Synchronous programming language
- Earliest deadline first scheduling
- Least slack time scheduling
- Rate-monotonic scheduling
- Adaptive Partition Scheduler
External links
- Alternatives to Real-Time Operating Systems
- How to Select an RTOS
- Small footprint RTOS supports 32-bit processors
- Simulation moves on a generation
- Helium Open-Source RTOS for HCS08 MCUs
- MaRTE OS - Minimal Real-Time Operating System for Embedded Applications
- HighRely Inc, - Provider of FAA Approved RTOS Certification and use of RTOS in Avionics
- - Open Source Digital Signal Processor Optimized RTOS, 16/32/64 bits
- Features of a modern commercial RTOS
- Salvo - RTOS for tiny places (a Pumpkin Inc. TM)
- FreeRTOS: A Free RTOS that runs on many architectures
- DrRtos: A Free RTOS that currently only works on ARM7
In computing, multitasking is a method by which multiple tasks, also known as processes, share common processing resources such as a CPU. In the case of a computer with a single CPU, only one task is said to be running
..... Click the link for more information.
..... Click the link for more information.
An operating system (OS) is the software that manages the sharing of the resources of a computer. An operating system processes system data and user input, and responds by allocating and managing tasks and internal system resources as a service to users and programs of the
..... Click the link for more information.
..... Click the link for more information.
real-time computing (RToC) is the study of hardware and software systems which are subject to a "real-time constraint"—i.e., operational deadlines from event to system response.
..... Click the link for more information.
..... Click the link for more information.
''
Embedded or embedding may refer to: Embedded , may refer to construction such as structural steel items embedded in a concrete pour.
..... Click the link for more information.
Embedded or embedding may refer to: Embedded , may refer to construction such as structural steel items embedded in a concrete pour.
- Embedding, one instance of some mathematical object contained within another instance
..... Click the link for more information.
mobile phone or cell phone is a long-range, portable electronic device used for mobile communication. In addition to the standard voice function of a telephone, current mobile phones can support many additional services such as SMS for text messaging, email, packet switching
..... Click the link for more information.
..... Click the link for more information.
robot is a mechanical or virtual, artificial agent . It is usually an electromechanical system, which, by its appearance or movements, conveys a sense that it has intent or agency of its own.
..... Click the link for more information.
..... Click the link for more information.
SCADA is the acronym for Supervisory Control And Data Acquisition. The term is used differently in North America from the rest of the world:
..... Click the link for more information.
- In North America; SCADA refers to a large-scale, distributed measurement and control system.
..... Click the link for more information.
throughput is the amount of digital data per time unit that is delivered over a physical or logical link, or that is passing through a certain network node. For example, it may be the amount of data that is delivered to a certain network terminal or host computer, or between two
..... Click the link for more information.
..... Click the link for more information.
Determinism is the philosophical proposition that every event, including human cognition and behavior, decision and action, is causally determined by an unbroken chain of prior occurrences.
..... Click the link for more information.
..... Click the link for more information.
Determinism is the philosophical proposition that every event, including human cognition and behavior, decision and action, is causally determined by an unbroken chain of prior occurrences.
..... Click the link for more information.
..... Click the link for more information.
Interrupt latency is the time between the generation of an interrupt by a device and the servicing of the device which generated the interrupt. For many operating systems, devices are serviced as soon as the device's interrupt handler is executed.
..... Click the link for more information.
..... Click the link for more information.
The thread switching latency is the time needed by the operating system to switch the CPU to another thread. In some operating systems running on some hardware, switching between threads belonging to the same process is much faster than switching to a thread from different process
..... Click the link for more information.
..... Click the link for more information.
AA ICAO
AAL Callsign
AMERICAN
Founded 1930 (as American Airways)
Hubs Dallas-Fort Worth International Airport
O'Hare International Airport
Miami International Airport
Lambert-St.
..... Click the link for more information.
AAL Callsign
AMERICAN
Founded 1930 (as American Airways)
Hubs Dallas-Fort Worth International Airport
O'Hare International Airport
Miami International Airport
Lambert-St.
..... Click the link for more information.
International Business Machines Corporation
Public (NYSE: IBM )
Founded 1889, incorporated 1911
Headquarters Armonk, New York, USA
Key people Samuel J.
..... Click the link for more information.
Public (NYSE: IBM )
Founded 1889, incorporated 1911
Headquarters Armonk, New York, USA
Key people Samuel J.
..... Click the link for more information.
Sabre is a computer reservations system/global distribution system (GDS) used by airlines, railways, hotels, travel agents and other travel companies. Sabre GDS is a unit of Sabre Holdings' Sabre Travel Network division.
..... Click the link for more information.
..... Click the link for more information.
real-time computing (RToC) is the study of hardware and software systems which are subject to a "real-time constraint"—i.e., operational deadlines from event to system response.
..... Click the link for more information.
..... Click the link for more information.
Round-robin is one of the simplest scheduling algorithms for processes in an operating system, which assigns time slices to each process in equal portions and in order, handling all processes without priority.
..... Click the link for more information.
..... Click the link for more information.
In computing, multitasking is a method by which multiple tasks, also known as processes, share common processing resources such as a CPU. In the case of a computer with a single CPU, only one task is said to be running
..... Click the link for more information.
..... Click the link for more information.
CPU design is the design engineering task of producing a CPU, a component of computer hardware. It is a subfield of electronics engineering and computer engineering.
..... Click the link for more information.
Overview
CPU design focuses on these areas:- Datapaths (such as ALUs and pipelines)
..... Click the link for more information.
A barrel processor is a CPU that switches between threads of execution on every cycle. This CPU design technique is also known as "interleaved" or "fine-grained" multithreading.
..... Click the link for more information.
..... Click the link for more information.
The Motorola 68000 is a CISC microprocessor core designed and marketed by Freescale Semiconductor (formerly Motorola Semiconductor Products Sector). As the first member of the successful 32-bit m68k family of microprocessors, it is generally software forward compatible with the
..... Click the link for more information.
..... Click the link for more information.
The ARM architecture (previously, the Advanced RISC Machine, and prior to that Acorn RISC Machine) is a 32-bit RISC processor architecture developed by ARM Limited that is widely used in a number of embedded designs.
..... Click the link for more information.
..... Click the link for more information.
In computing, an interrupt is an asynchronous signal from hardware indicating the need for attention or a synchronous event in software indicating the need for a change in execution.
..... Click the link for more information.
..... Click the link for more information.
semaphore is a protected variable (or abstract data type) and constitutes the classic method for restricting access to shared resources (e.g. storage) in a multiprogramming environment. It was invented by Edsger Dijkstra and first used in the THE operating system.
..... Click the link for more information.
..... Click the link for more information.
In computer science, message passing is a form of communication used in concurrent computing, parallel computing, object-oriented programming, and interprocess communication. Communication is made by the sending of messages to recipients.
..... Click the link for more information.
..... Click the link for more information.
kernel space and user space. Kernel space is strictly reserved for running the kernel, device drivers and kernel extensions. In most operating systems, kernel memory is never swapped out to disk.
..... Click the link for more information.
..... Click the link for more information.
In computing, a system call is the mechanism used by an application program to request service from the operating system.
..... Click the link for more information.
Background
In addition to processing data in its own memory space, an application program might want to use data and services provided by the system...... Click the link for more information.
In concurrent programming a critical section is a piece of code that accesses a shared resource (data structure or device) that must not be concurrently accessed by more than one thread of execution.
..... Click the link for more information.
..... Click the link for more information.
Interrupt latency is the time between the generation of an interrupt by a device and the servicing of the device which generated the interrupt. For many operating systems, devices are serviced as soon as the device's interrupt handler is executed.
..... Click the link for more information.
..... Click the link for more information.
In scheduling, priority inversion is the scenario where a low priority task holds a shared resource that is required by a high priority task. This causes the execution of the high priority task to be blocked until the low priority task has released the resource, effectively
..... Click the link for more information.
..... Click the link for more information.
This article is copied from an article on Wikipedia.org - the free encyclopedia created and edited by online user community. The text was not checked or edited by anyone on our staff. Although the vast majority of the wikipedia encyclopedia articles provide accurate and timely information please do not assume the accuracy of any particular article. This article is distributed under the terms of GNU Free Documentation License.
Herod_Archelaus
