Real Time Systems & POSIX

Real Time Systems


A real-time system is one where the timeliness of the result of a calculation is important for example defense weapons systems, Internet video and audio streaming. There are two categories of real time systems: hard and soft. In a hard real-time system the time deadlines must be met or the result of a calculation is invalid. For example in a missile guidance system, if the missile is delayed it may miss its target. The timing constraints in a soft real-time system are not as stringent and there is still some utility of the result of the calculations if it does not meet its timing deadline. For example, in Internet audio/video streaming if a packet of data is late or lost the quality of the audio/video is degraded, but the stream can still be audible / viewed.
Hard real-time systems, despite having a high reliability, are very inflexible and more resource expensive. On the other hand soft real time systems trade predictability for efficiency. They can easily adapt to system changes, are less resource consumptive and can tolerate overloads in a smoother way. So it is not necessary that hard real time systems have a much higher degree of performance than soft ones. They just are more tuned on certain critical applications.
To guarantee that the timing requirements of a real-time system are met, the timing and  behavior of the underlying computing system must be predictable. The time required by all processes must be bounded to guarantee the predictability of  the whole system . This necessitates that the worst case timing of all processes are known. Typically though a system is called predictable only if its worst case timing is very close to its average case timing. 

 Real Time Systems Vs Embedded Systems


Embedded systems are small, built for a special purpose, very efficient in performing the task they are built for and rarely need an external intervention. For example MP3 players, smart-phones, anti-lock braking systems, LAN routers, airplane autopilot systems  etc. Real Time systems is a sub class of embedded systems which in addition compute a task it in a limited or predictable amount of time. This predictable deadline has nothing to do with speed. The response has to be within a known limited amount of time, which can be a microsecond, an hour, a day or even a month. Non-real time embedded systems are not time bounded. They keep the embedded characteristics of little or no user intervention, being small (small memory, limited number of peripherals), executing a limited number of tasks. For example a weather station at places where human presence is less accessible. This system just performs single function: read information from several sensors and transmit them via a network link to a base station. This embedded system is required to provide information on a fixed pre-established time frame. Embedded system may or may not  include RTOS depending n the requirements. For sequential execution, RTOS ia not needed. If the system demands the parallel execution of events, as in real time systems, then RTOS is needed.

POSIX Standard
 
Both C and C++ lack support for developing real-time systems, mainly because they don’t offer services for programming concurrent software with predictable timing behavior. An open software architecture addresses the challenges of today’s software development process by defining standard software interfaces. It is important that the services offered by the RTOS follow a standard API that allows the application to be ported to different platforms, even from different vendors. One of these APIs that has support for real-time systems, is supported by major RTOS vendors and is approved as an international standard is POSIX. The original Portable Operating System Interface for Computing Environments (POSIX) standard was first published in 1990, which defined interfaces for core functions such as: file operations, process management, signals, and devices. The standard describes the services that the OS must provide, and the syntax and semantics of their interfaces, in terms of data types and function prototypes. The actual implementation of those services is not specified by the standard, and is left to the open competition among OS vendors. Since the standard defines the interfaces at the source code level, the portability achieved is also for the source code. Binary level portability is outside the scope of the standard because it requires the use of a unified processor (or virtual processor) architecture. Subsequent releases of POSIX have also been defined to cover real-time extensions and multi-threading etc. The table below shows important POSIX standards, the first three standards (1003.1a,1b,1c) being the most widely supported

Standard	Name	Description
1003.1a	OS Definition	Basic OS interfaces; includes support for: (single process, multi process, job control, signals, user groups, file system, file attributes, file device management, file locking, device I/O, device specific, system database, pipes, FIFO, and C language
1003.1b	Real-time Extensions	Functions needed for real-time systems; includes support for: real-time signals, priority scheduling, timers, asynchronous I/O, prioritized I/O, synchronized I/O, file sync, mapped files, memory locking, memory protection, message passing, semaphores, and shared memory
1003.1c	Threads	Functions to support multiple threads within a process; includes support for: thread control, thread attributes, priority scheduling, mutexes, mutex priority inheritance, mutex priority ceiling, and condition variables
1003.1d	Additional Real-time Extensions	Additional interfaces; includes support for: new process create semantics (spawn), sporadic server scheduling, execution time monitoring of processes and threads, I/O advisory information, timeouts on blocking functions, device control, and interrupt control.
1003.1j	Advanced Real-time Extensions	More real-time functions including support for: typed memory, nanosleep improvements, barrier synchronization, reader/writer locks, spin locks, and persistent notification for message queues
1003.21	Distributed Real-time	Functions to support real-time distributed communication; includes support for: buffer management, send control blocks, asynchronous and synchronous operations, bounded blocking, message priorities, message labels, and implementation protocols
1003.1h	High Availability	Services for Reliable, Available, and Serviceable Systems (SRASS); includes support for: logging, core dump control, shutdown/reboot, and reconfiguration

 To be POSIX conformant, the operating system, and hardware platform, has to be certified using a suite of tests, which currently exist only for POSIX 1003.1a. POSIX Compliance only requires the vendor to state which features of POSIX are and are not implemented. Almost all vendors report that they are POSIX compliant.

POSIX Profiles


POSIX 1003.13 does not contain any additional features; instead it groups the functions from existing POSIX standards into units of functionality. The profiles are based on whether or not an operating system supports more than one process and a file system. The four current profiles are

Profile	Number of Processes	Threads	File System
54	Multiple	Yes	Yes
53	Multiple	Yes	No
52	Single	Yes	Yes
51	Single	Yes	No

POSIX Real Time Extensions

POSIX 1003.1b, 1003.1d and 1003.1j define extensions useful for development of real-time systems. The features are 

• Timers: Periodic timers, delivery is accomplished using POSIX signals 
• Priority scheduling: Fixed priority preemptive scheduling with a minimum of 32 priority levels
• Real-time signals: Additional signals with multiple levels of priority
• Semaphores: Named and memory counting semaphores
• Memory queues: Message passing using named queues
• Shared memory: Named memory regions shared between multiple processes 
• Memory locking: Functions to prevent virtual memory swapping of physical memory pages

To be compliant with POSIX an operating system must contain at least 32 priorities. POSIX defines three scheduling policies to handle processes running at the same priority. For SCHED_FIFO processes are scheduled first in first out, and run until completion. For SCHED_RR the scheduler uses a time quanta to schedule processes in a round robin fashion. SCHED_OTHER is implementation dependent and is not portable. 

 POSIX Threads

In POSIX, threads are implemented independent of the other real-time features. There are a number of features from the real-time specification that are carried over to the thread specification. For example priority scheduling is done on a per-thread basis, but is handled in a similar manner as scheduling in POSIX 1003.1b. A thread’s priority and scheduling policy is typically specified when it is created. The POSIX thread specification defines functionality in the following areas:

• Thread control: Creation, deletion and management of individual threads 
•  Priority scheduling: POSIX real-time scheduling extended to include scheduling on a per thread basis; the scheduling scope is either done globally across all threads in all processes, or performed locally within each process
• Mutexes: Used to guard critical sections of code; mutexes also include support for priority inheritanc and priority ceiling protocols to help prevent priority inversions
• Condition variables: Used in conjunction with mutexes, condition variables can be used to create a monitor synchronization structure 
• Signals: Ability to deliver signals to individual threads 

 POSIX Coverage in OS

Real-time OS must support multithreading (need to react to external events, and control asynchronous devices.), preemptive priority scheduling ( a time critical task is not delayed because of a non-critical task preventing thereby a situation where a high priority task is forever delayed by the operating system.), synchronization and communication interfaces, high resolution timers and clocks (at a granularity of micro or milliseconds to support periodic processing and to detect system timeout errors), predictability and determinism. Linux provides good support for the base POSIX APIs and threads, but is missing real-time features such as timers and message queues. The RTOS 

• performs few tasks, ensuring their completion within the deadline
• drops or reduces tasks when they cannot be executed within the time constraint.
• monitors input consistently and in a timely manner
• monitors resources and can interrupt background processes as needed for completion within deadline
• keeps track of how much of each resource (CPU, RAM, communications bandwidth, etc.) might be needed in the worst-case and blocks a task unless it "fits" in the remaining un-allocated resources.

An RTOS may be either event-driven or time-sharing. An event-driven RTOS is a system that changes state only in response to an incoming event. A time-sharing RTOS is a system that changes state as a function of time.

Linux systems were typically non real-time and large and POSIX is not primarily intended for real-time systems but real-time services have been added into the POSIX standard to ensure that the timing behaviour
of the system can be made predictable. It is possible to develop portable real-time embedded applications using the C language and an RTOS that follows one of the POSIX real-time systems profiles meeting two fundamental requirements: the ability to create concurrent programs with multiple cooperative tasks, and the ability to bound the response time of the OS services and to predict the timing behaviour of the application.  At thread level following primitives are supported

• Concurrency: The two mechanisms for concurrency are processes (have independent memory address space)  and threads (share memory address space so memory management overhead is minimized).
• Fixed Priority Scheduling: Three policies based on preemptive fixed priority namely FIFO, Round Robin and server side.
• Mutual Exclusion Synchronization: Mutexes, Priority Protection and Priority inheritance to avoid priority inversion problem which may lead to unpredictability.
• Signal-Wait Synchronization: Two mechanisms viz Condition variable (allows a task to wait until a condition is true and in turn can be protected by mutexes) and Semaphores (to synchronize an application thread with an interrupt service routine or a signal handler)
• Asynchronous Notification: Signals (Delivery and Signal handlers are invoked after interception)
• Message passing: Message Queues (Variable size messages and Polling, waiing and blocking on messages is possible)
• Timing Services: Logical Clocks (Real time , monotonic and execution time clocks, periodic timers and sleeping on timers is possible)
• Memory Management: Virtual logical memory and locking of parts of physical memory for predictability is possible

 Testing the Real Time Performance of RTOS 

There are two kinds of benchmarks, those that measure the determinism of the OS and those that measure the latency of particular important operations. The benchmarks test core operating system capabilities and are independent of any actual application.

Benchmark	Description	Aspect tested	Parameters
Timer Jitter	Create a periodic thread and measure the deviation between desired and actual expiration	Measures the response time of the operating system	Timer period: (1,10,100 ms)
Response	Execute a fixed processing load and measure its execution time over a number of runs	Determine if a thread can respond in a deterministic fashion	Type of processing: (add,copy,whetstone)
Bintime	Call a time of day clock and measure interval between calls	Measures the maximum kernel blocking time	None
Sync	Measure the latency of thread to thread or process to process synchronization	Measures the context switching time between threads and processes	Type of semaphore: (POSIX named/unnamed semaphore, pthread mutex, lynx semaphore); process to process or thread to thread
Message passing	Measure the latency of sending data form thread to thread or from process to process	Measures the possible throughput of data between processes and threads	Data buffer size; process to process or thread to thread
RT Signals	Measure the latency of real-time signals between two processes	Measures the latency of POSIX real-time signals	None

The first three, Timer Jitter, Response, and Bintime are benchmarks for determinism i.e to test that the time it takes to perform an operation is known under all circumstances (worst case time). The Timer Jitter test creates a timer, sets it to expire at a given period, and then when it expires determines the actual expiration time. The jitter is then defined as the deviation between the actual and desired expiration times. Most current CPUs include a stamp counter that is updated on every CPU cycle. The POSIX clock_gettime function in most operating systems uses this stamp counter, giving a high precision time of day clock. The Response benchmark measures the actual execution time of a 10 millisecond fixed block of processing. The actual execution time over a number of separate runs is calculated to determine whether or not application response time is deterministic. The fixed processing is generated with a loop consisting of one of three different types of operations: additions (add), memory copies (copy), or the synthetic Whetstone benchmark (whet). The Bintime benchmark  determines the maximum kernel blocking time. This benchmark uses a high priority real-time thread to repeatedly call a time of day clock and calculate the time required by each call. The time required by each call consists of the time to perform the system call and any time spent blocked in the kernel. Since the time to perform the system call should be constant, the deviation between the maximum time reported by the benchmark and the average time gives a good indication of the maximum time spent blocked in the kernel.
The last three benchmarks test the synchronization, message passing, and RT signaling capabilities of an
operating system. It is important that the average latency of operations is small and maximum latency is bounded. The Synchronization benchmark consists of three tests. In the first test a single thread signals (S) and then waits (W) on a semaphore. This test measures the latency of semaphore system calls. The second test uses semaphores to signal between two threads. The threads are either in a single, or two different processes. Measurements from the first two tests can be used to determine the context switching time by subtracting off the system call overhead, obtained in test one, from half of the roundtrip signaling time, obtained in test two. The last test assesses an operating systems ability to deal with priority inversion. The test sets up a classic priority inversion using semaphores. The priority inversion occurs when a low priority task (thread)  acquires a resource R (locks the mutex)  needed later by a high priority task. The high priority task blocks waiting on the resource (locked mutex) and is delayed indefinitely because an independent medium priority task is monopolizing the CPU. This is a priority inversion because now the medium priority task (thread) is favored over the high priority task. One typical way of solving this problem is to allow the low priority task to inherit the priority (by pthread_mutexattr_setprotocol, which has three options- the dafault PTHREAD_PRIO_NONE,  PTHREAD_PRIO_INHERIT for priority inheritance if higher priority thread is blocked and  PTHREAD_PRIO_PROTECT for priority inheritance irrespective of the blocked thread) 
of the high priority task (thread) so that it can run and release the resource R (mutex) and its priority is reduced back to its previous level and the high-priority thread acquires the mutex. . In the test a fixed-duration processing loop is used for the medium priority task. If a priority inversion occurs then the time between when the low priority task acquires the resource and when the high priority task receives it will be at least the time in this fixed-duration of processing. If the OS synchronization mechanism prevents a priority inversion then this time will be negligible. The message passing benchmark uses POSIX message queues to measure the latency and throughput of data transfers between two threads in the same process or in different processes. The RT signals benchmark measures the latency of POSIX real-time signals.

Processes and Threads in POSIX

Processes must be kept separate, and POSIX assumes that each process resides in a different name space and has its own symbols tables. The Memory Management Unit (MMU) is used to physically isolate processes from each anotherin the memory. Two symbols defined globally will not conflict if they are located in two different processes. Each process is assigned its own private memory anywhere in the RAM. The addresses used within programs are virtual addresses, which are translated at run time to the real memory locations. The translations are private to a process. The set of virtual addresses that a process can access are called the process's virtual address space, which is composed of segments:

• The text segment contains the program instructions.
• The data segment contains global data and dynamically allocated data.
• The stack segment contains the stacks owned by each thread.
• Additional segments that are defined later.

The MMU translates the virtual addresses into physical addresses. If a process attempts to address a page that is not currently mapped to it, the MMU generates an exception. The exception sends a signal to the offending thread in which the default action is to terminate the process. Alteratively, the thread may catch the signal for user-defined actions, if desired.

Threads are schedulable entities that run within a process. Each process will have one main thread, and it may also have several more threads . Threads in the same process share the same virtual address space. They can communicate and share data using globals. Any thread created within a process can terminate itself or can read the exit status of any other thread. If any thread calls exit(), the process terminates. All threads in the process are then terminated.. POSIX.1b specifies real-time signals and can carry data, are queued (delivery to a specific thread is guaranteed), and can be prioritized (as opposite to Linux Threads)

Simple introduction  of POSIX programming