Real-time operating system: Wikis

Advertisements
  
  

Note: Many of our articles have direct quotes from sources you can cite, within the Wikipedia article! This article doesn't yet, but we're working on it! See more info or our list of citable articles.

Encyclopedia

Advertisements

From Wikipedia, the free encyclopedia

A real-time operating system (RTOS) is an operating system (OS) intended for real-time applications. Such operating systems serve application requests nearly real-time. A real-time operating system offers programmers more control over process priorities. An application's process priority level may exceed that of a system process. Real-time operating systems minimize critical sections of system code, so that the application's interruption is nearly critical.

A key characteristic of a real-time OS is the level of its consistency concerning the amount of time it takes to accept and complete an application's task; the variability is jitter. A hard real-time operating system has less jitter than a soft real-time operating system. The chief design goal is not high throughput, but rather a guarantee of a soft or hard performance category. A real-time OS that can usually or generally meet a deadline is a soft real-time OS, but if it can meet a deadline deterministically it is a hard real-time OS.

A real-time OS has an advanced algorithm for scheduling. Scheduler flexibility enables a wider, computer-system orchestration of process priorities, but a real-time OS is more frequently dedicated to a narrow set of applications. Key factors in a real-time OS are minimal interrupt latency and minimal thread switching latency, but a real-time OS is valued more for how quickly or how predictably it can respond than for the amount of work it can perform in a given period of time.

Contents

Design philosophies

Two basic designs exist:

  • Event-driven which switches tasks only when an event of higher priority needs service, called preemptive priority, or priority scheduling.
  • Time-sharing designs switch tasks on a regular clock interrupt, and on events, called round robin.

Time-sharing designs switch tasks more often than strictly needed, but give smoother, more deterministic multitasking, giving the illusion that a process or user has sole use of a machine.

Early CPU designs needed many cycles to switch tasks, during which the CPU could do nothing else useful, so early OSes tried to minimize wasting CPU time by maximally avoiding unnecessary task switching. For example, in a 20 MHz 68000 processor (typical of late 1980s), task switch times are roughly 20 microseconds. In contrast, a 100 MHz ARM CPU (from 2008) switches in less than 3 microseconds.[1][2]

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.

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 doubly 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 to running. In a well-designed RTOS, readying a new task will take 3 to 20 instructions per ready-queue entry, and restoration of the highest-priority ready task will take 5 to 30 instructions.

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.

Algorithms

Some commonly used RTOS scheduling algorithms are:

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

General-purpose operating systems usually do not allow user programs to mask (disable) interrupts, because the user program could control the CPU for as long as it wishes. Modern CPUs don't allow user mode code to disable interrupts as such control is considered a key operating system resource. Many embedded systems and RTOSs, however, allow the application itself to run in kernel mode for greater system call efficiency and also to permit the application to have greater control of the operating environment without requiring OS intervention.

On single-processor systems, if the application runs in kernel mode and can mask interrupts, often interrupt disablement is the best (lowest overhead) solution to prevent simultaneous access to a shared resource. While interrupts are masked, the current task has exclusive use of the CPU since no other task or interrupt can take control, so the critical section is 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 increases the system's maximum interrupt latency. Typically this method of protection is used only when the critical section is just a few instructions and contains no loops. This method is ideal for protecting hardware bit-mapped registers when the bits are controlled by different tasks.

Binary semaphores

When the critical section is longer than a few source code lines or involves lengthy looping, an embedded/real-time algorithm 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 typically take hundreds of CPU instructions to execute, while masking interrupts may take as few as one instruction 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, tasks must wait for the semaphore. A binary semaphore is therefore equivalent to a mutex. Typically a task can set a timeout on its wait for a semaphore. There are several well-known problems with semaphore based designs such as 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 owns 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 complex.

In a deadlock, two or more tasks lock semaphores and then wait forever (that is, no timeout) for other the other task's semaphore, 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).

Binary semaphores in existing real-time operating systems

Operating system Protocol Details
uC/OS-II Priority Calling Addresses priority inversion, but suffers from chained blocking and deadlock.

Message passing

The other approach to resource sharing is for tasks to send messages in an organized message passing scheme. 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. Although their real-time behavior is less crisp than semaphore systems, simple message-based systems avoid most protocol deadlock hazards, and are generally better-behaved than semaphore systems. In particular, a queue entry is the entire resource consumed by a waiting service request. However, problems like those of semaphores are possible: Priority inversion can occur 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 incoming message queue. Protocol deadlocks can occur when two or more tasks wait for each other to send response messages.

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.

An OS maintains catalogs of objects it manages, such as threads, mutexes, memory, and so on. Updates to this catalog must be strictly controlled. For this reason it can be problematic when an interrupt handler call an OS function while the application is in the act of also doing so. The OS function called from an interrupt handler can find the object database to be in an inconsistent state because of the application's update. In general there are two major approaches to deal with this problem: the unified architecture and the segmented architecture. RTOSs implementing the unified architecture solve the problem by simply disabling interrupts while the internal catalog is updated. The downside of this is that interrupt latency increases, potentially losing interrupts. The segmented architecture does not make direct OS calls but delegates the OS related work to a separate handler. This handler runs at a higher priority than any thread but lower than the interrupt handlers. The advantage of this architecture is that the RTOS adds very few cycles to interrupt latency. As a result, OSes which implement the segmented architecture are more predictable and can deal with higher interrupt rates compared to RTOSs implementing the unified architecture.

Memory allocation

Memory allocation is even more critical in an RTOS than in other operating systems.

First, 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.

The simple fixed-size-blocks algorithm works astonishingly well for simple embedded systems.

See memory allocation for more details.

Examples

An early example of a large-scale real-time operating system was the Transaction Processing Facility developed by American Airlines and IBM for the Sabre Airline Reservations System.

Currently the best known, most widely deployed, real-time operating systems are[citation needed]

See the list of real-time operating systems for a comprehensive list. Also, see the list of operating systems for all types of operating systems.

See also

References


Simple English

A real-time operating system (RTOS; commonly pronounced as "are-toss") is a multitasking operating system designed for real-time applications. Such applications include embedded systems, industrial robots, scientific research equipment and others.

An RTOS simplifies the creation of a real-time applications, but does not guarantee the final result will be real-time; this requires good development of the software.

Real-time operating systems use specialized scheduling algorithms in order to provide the real-time applications. An RTOS can respond more quickly and/or predictably to an event than other operating systems.

The main features of an RTOS are minimal interrupt latency and a minimal thread switching latency.

The basic two designs for RTOS are:

  • Event-driven (priority scheduling) designs: switch tasks only when an event of higher priority needs service, called pre-emptive priority.
  • Time-sharing designs: switch tasks on a clock interrupt, and on events, called round robin.

Examples

These are the best known, most widely used real-time operating systems. See List of real-time operating systems for a full list. Also, see List of operating systems for all types of operating systems.

Other pages

  • Operating system
  • BIOS
  • POSIX
  • Rate-monotonic scheduling
  • Adaptive Partition Scheduler
  • Earliest deadline first scheduling

Other websites


Advertisements






Got something to say? Make a comment.
Your name
Your email address
Message