Skip to content
Search

Real-time operating system

lastmod 2025-02-02created 2024-11-205 edits

A real-time operating system (called silsigan jojak chegye in North Korean usage), or RTOS (← Real Time Operating System), is an operating system developed for real-time applications. It is designed with a focus on the CPU time management part of the operating system's functions. A real-time operating system gives the programmer more control over process priorities. The priority of an application may even exceed the priority of system programs. Critical sections in system code are minimized, which allows processing requests from applications to be handled within a fixed time.

The key to a real-time operating system is the degree to which it can consistently maintain the time taken to process application tasks. The variation in processing time is called jitter (the time deviation between the actual signal and the reference point). RTOSes can be divided into hard real-time operating systems and soft real-time operating systems, and the former has less jitter than the latter. The main design goal of an RTOS is not high throughput but guaranteed real-time performance. An RTOS that generally meets the deadlines of a real-time system is called a soft real-time operating system, and one that meets deadlines by a deterministic algorithm is called a hard real-time operating system.

An early example of a large-scale real-time operating system was the "control program", developed by American Airlines and IBM for the Sabre airline reservation system.

Design approaches

There are two basic design approaches.

Event-driven approach
Also called priority-based scheduling or preemptive scheduling. A task switch occurs when an event with a higher priority than the currently running task requests service.
Time-sharing scheduling approach
Task switches occur when periodic events such as clock interrupts or round robin occur.

Strictly speaking, the time-sharing scheduling approach switches tasks more often than actually needed. However, thanks to this, it provides smoother and more predictable multitasking, and gives the effect of a single process or a single user having exclusive use of the device. For this reason, this approach may seem like the better multitasking approach.

Scheduling

In traditional designs, a task exists in one of three states: running, ready, or blocked. Most tasks are blocked, and only one task is running. The simpler the system, the shorter the list of ready tasks; even in busy cases it is only about 2-3.

In general, the data structure of the scheduler's ready task list is designed to minimize the time spent in the scheduler's critical section (where CPU preemption is prohibited, and in some cases all interrupts are disabled). However, the choice of data structure also depends on the maximum number of tasks that can be in the ready list.

If the structure only ever has a small number of tasks in the ready list, around 2-3, simply implementing the ready list as a doubly linked list is also efficient. On the other hand, if there are usually only a few tasks but occasionally more, the design sorts the list in advance by priority, or allows higher-priority tasks to be added to the ready list before lower-priority tasks, so that the whole list does not have to be searched repeatedly for the highest-priority task every time a task is run. In other words, CPU preemption must not be prohibited while searching the ready list, or long critical sections must be split into smaller ones. This means that even while a low-priority task is being added to the list, if an interrupt occurs that makes a high-priority task ready, the high-priority task is added to the ready list first and can run immediately.

When a new task is created, it first becomes ready. The scheduler also changes the currently running task to the ready state and puts both tasks into the ready task list. After that, it runs the highest-priority task again, and the time taken for this whole process is called the critical response time or flyback time. In a well-designed real-time operating system, making a new task ready takes 3-20 instructions, and changing the highest-priority ready task to the running state takes 5-30 instructions.

In advanced real-time operating systems, tasks that run in real time share computer resources with tasks that do not. Therefore the ready list can become quite long. In such systems, implementing the scheduler's ready list as a simple linked list is not appropriate.

Scheduling algorithms

Scheduling algorithms commonly used in RTOSes include the following.

  • Cooperative scheduling
  • Pre-emptive scheduling
    • Round-robin scheduling
    • Fixed priority pre-emptive scheduling

Intertask communication and resource sharing

A multitasking system must manage data and hardware resources shared among multiple tasks. In most cases it is dangerous for two or more tasks to access the same data or hardware resource at the same time. ("Dangerous" means that if one task is in the middle of updating multiple pieces of data, the results are inconsistent and unpredictable. Other tasks may only access this data before the update starts or after it has completely finished.) Here are three approaches commonly used to solve this problem.

Temporarily disabling interrupts

General-purpose operating systems do not let users mask (disable) interrupts. This is because a user's program could occupy the CPU, a core resource of the operating system, for too long. In other words, most CPUs in use today do not grant user-mode code the privilege to disable interrupts. However, many embedded systems and real-time operating systems allow applications to run in kernel mode as well, so that they can use system calls efficiently without interference from the operating system.

On a single-processor system, if an application is running in kernel mode and can disable interrupts, disabling interrupts is usually the best technique for preventing two or more tasks from accessing a shared resource at the same time. While interrupts are disabled, the currently running task is "exclusive" because no other task or interrupt can take control of the CPU, so the critical section is protected. When the task leaves the critical section, it must re-enable interrupts so that any pending interrupts can run. Temporarily disabling interrupts is a valid strategy when the longest path through the critical section is shorter than the interrupt latency. Otherwise, this method may increase the system's maximum interrupt latency. Therefore it can be said to be valid when the critical section consists of only a few instructions or contains no loops.

Semaphores

A semaphore is either locked or unlocked. When it is locked, a queue of tasks waits for the semaphore (to be unlocked). The problems with semaphore designs are well known: priority inversion and deadlock. Priority inversion is a situation where a high-priority task waits for a task holding a low-priority semaphore. A typical solution is to make the task holding the semaphore run at the highest priority. In a deadlock, two tasks lock two semaphores in reverse order. This is usually solved by careful design when implementing the queue, or by adding floored semaphores (which pass control of the semaphore to a higher-priority task under defined conditions).

Message passing

Another solution is to have tasks send messages to each other. This also has the same problems: priority inversion occurs when a task ignores a higher-priority message in its in-box while processing a lower-priority message. Deadlock occurs when two tasks each wait for the other's response.

Real-time behavior is less clear-cut than in semaphore systems, but message-based systems are not fixed by themselves and generally behave better than semaphore systems.

Interrupt handlers and the scheduler

An interrupt handler can interrupt even the highest-priority running task, and since real-time operating systems are designed to minimize thread latency, the functionality of interrupt handlers tends to be kept as small as possible.

Memory allocation

Memory allocation is more critical in a real-time operating system than in other operating systems.

First, for stability, there can be no memory leaks (memory that was allocated but not returned after use). The device must run indefinitely without ever needing a reboot. For this reason, dynamic memory allocation is frowned upon. Whenever possible, all required memory allocation is specified statically at compile time.

Another reason to avoid dynamic memory allocation is memory fragmentation. With fragmented allocation and the return of small chunks of memory, the available memory gets split into several sections, and a situation can arise where the RTOS cannot allocate a large enough contiguous block of memory even though there is enough free memory. Second, allocation speed matters. A typical memory allocation design scans a linked list of unpredictable length to find a suitable free memory block.[2] This is unacceptable in an RTOS, because memory allocation must happen within a guaranteed time.

Because physical disks have much longer and unpredictable response times, swapping to a disk file is not used, for the same reasons as the RAM allocation discussed above.

For simple embedded systems, a simple fixed-size block algorithm works quite well because of its low fixed overhead.

Memory use in embedded systems

Some RTOSes (embedded operating systems) support XIP (execute in place). The kernel and applications run directly from ROM without first transferring their code to RAM. This offers a trade-off between the RAM size and the ROM size the operating system needs.

Various RTOSes

  • NEOS, a real-time operating system for defense/aviation
  • BeOS
  • ChorusOS
  • CsLEOS
  • eCos
  • FreeRTOS
  • ITRON
  • LynxOS
  • MicroC/OS-II
  • Nucleus RTOS
  • OS-9
  • OSE
  • OSEK/VDX
  • pSOS
  • QNX
  • RMX
  • RSX-11
  • RT-11
  • RTOS-UH
  • ThreadX
  • VRTX
  • Velos
  • VxWorks
  • Windows CE
  • RTLinux
  • RTAI
  • RTWORKS

See also

Favorite site

author Zer0 sitemap