By Kevin M. Obenland
Embedded Systems Programming
(03/15/01, 04:00:11 PM EDT)
In today's computing systems, it is becoming increasingly important to design software with an open system architecture utilizing industry-adopted standards. The need to develop open systems is driven by three major factors. First, gone are the days when a single developer could implement the entire system from scratch. Software development programs are growing in scale, requiring teams of increasing size. Second, software does not operate in isolation; it must co-exist with the vast amount of commercially available software. Last, the lifecycle of a software application is typically long, requiring numerous modifications and updates as new features are added.
An open software architecture addresses the challenges of today's software development process by defining standard software interfaces, which promote interoperability and portability. Openly published standard interfaces also reduce the cost of adding functionality in the future.
Standards are pervasive in today's computer systems. New standards are constantly being defined to address the ever-changing state of software technology. A standard will not be effective if it is not used, or if it is gone tomorrow. To be effective, a standard must be based on well-established technology and accepted by a wide portion of the industry.
The original Portable Operating System Interface for Computing Environments (POSIX) standard was first published in 1990. POSIX is based on UNIX, a well-established technology dating back to the early 1970s. POSIX defines a standard way for an application to interface to the operating system. The original POSIX standard defines interfaces to core functions such as file operations, process management, signals, and devices. Subsequent releases of POSIX have also been defined to cover real-time extensions and multi-threading.
In a perfect world, because of the previously cited advantages, one would always choose a standard. However, in the real world, a number of questions must be answered before deciding to use a standard. These include:
In this article I will discuss the usefulness of POSIX in real-time systems by looking at three factors: functionality, performance, and availability. Because real-time systems typically have stringent performance constraints, emphasis is placed on the performance of POSIX implementations.
POSIX real-time operating systems
The POSIX family of standards includes over 30 individual standards, ranging from specifications for basic operating system services to specifications for testing the conformance of an operating system to the standard. This article focuses on those standards important to the development of real-time embedded systems. In this section I discuss real-time systems as well as give a brief review of the relevant POSIX standards.
A real-time system is one where the timeliness of the result of a calculation is important., Examples include military weapons systems, factory control systems, and video and audio streaming. Real-time systems are typically categorized into two classes: 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 tracking system, if the missile is delayed, it may miss its intended target. The timing constraints in a soft real-time system are not as stringent. The result of a calculation can still be useful if it does not meet its timing deadline. Audio streaming is an example of a soft real-time system. If a packet of data is late or lost, the quality of the audio is degraded, but the stream may still be audible.
To guarantee that the timing requirements of a real-time system are met, the behavior and timing of the underlying computing system must be predictable. The time required by all operations must be bounded for the timing of the system to be called predictable. This implies that the worst case timing of all operations is known. Sometimes though, a system is called predictable only if its worst case timing is also very close to its average case timing.
POSIX real-time related standards
Of the more than 30 POSIX standards, the seven standards listed in Table 1 are especially relevant to the development of real-time and embedded systems. The first three standards-1003.1a, 1003.1b, and 1003.1c-are the most widely supported. POSIX 1003.1a defines the interface to basic operating system functions, and was the first to be adopted in 1990.1, Real-time extensions are defined in the standards 1003.1b, 1003.1d, 1003.1j, and 1003.21.,,, However, the original real-time extensions, defined by 1003.1b, are the only ones commonly implemented. Support for multiple threads in a process is provided in a separate standard, POSIX 1003.1c. POSIX also includes support for high availability in the 1003.1h standard.
Commercial support for POSIX varies widely. Because POSIX 1003.1a is based on UNIX, any UNIX-based operating system will naturally be very close to the standard. To be conformant to the POSIX standard, the operating system and hardware platform have to be certified using a suite of tests. Currently, test suites exist only for POSIX 1003.1a. Because POSIX is structured as a set of optional features, operating system vendors can choose to implement only portions of POSIX and still be POSIX compliant. Compliance only requires the vendor to state which features of POSIX are and are not implemented. This is a source of confusion because, for marketing reasons, almost all vendors report that they are POSIX compliant.
POSIX profiles. Embedded systems typically have space and resource limitations, and an operating system that includes all the features of POSIX may not be appropriate. The POSIX 1003.13 profile standard was defined to address these types of systems.13 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 summarized in Table 2.
POSIX real-time extensions. POSIX 1003.1b, as well as 1003.1d and 1003.1j, define extensions useful for development of real-time systems. Functions defined in the original real-time extension standard 1003.1b are supported across a wider number of operating systems than the other two specifications. For this reason this article focuses on POSIX 1003.1b. The following items constitute the bulk of the features defined in POSIX 1003.1b:
Listing 1 shows C code for creating and using a POSIX timer. Creating a timer consists of two steps: specifying a signal that is to be delivered at timer expiration, and creating/setting the timer itself. In this example we use the highest priority real-time signal (SIGRTMIN) to asynchronously call the timer handler routine. Two values must be specified for the timer: the initial expiration time (it_value) and the frequency (tv_sec). The structure (itimerspec) allows nanosecond time specification, however, actual resolution is dependent on the system. The POSIX call clock_getres() can be used to determine the actual resolution, typically 10ms or 1ms.
POSIX 1003.1b provides support for fixed priority preemptive scheduling. To be compliant with POSIX, an operating system must implement 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 quantum to schedule processes in a round robin fashion. The SCHED_OTHER policy is also included to handle an implementation-defined scheduling policy. Because SCHED_OTHER is implementation dependent, it is not portable across different platforms, and its use should be limited.
POSIX uses named objects for several different mechanisms including semaphores, shared memory, and message queues. These names are analogous, but independent, to names in the file system. For semaphores one process creates the semaphore and other processes can attach to the semaphore using its name. Both processes can perform signal (sem_post) or wait (sem_wait) operations.
POSIX threads. In POSIX, threads are implemented in an independent specification, which means that their specification is independent of the other real-time features.1, Because of this, a number of features from the real-time specification are carried over to the thread specification. For example, priority scheduling is done on a per-thread basis, but is handled in a manner similar to 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 and/or makes modifications to POSIX in the following areas:
POSIX coverage in operating system implementations
Table 3 shows the level of compliance to POSIX 1003.1a and the 3.1 release is compliant with all three standards. VxWorks only supports a subset of the POSIX standards because in releases prior to and including v. 5.4, VxWorks was based on a single process model that does not include task memory protection. The current release, VxWorks AE, does support memory protection; however, the protection scheme is implemented differently than in the traditional POSIX prcoess model. Linux provides good support for the base POSIX APIs and threads, but is missing features such as timers and message queues.
Operating system design
The design of an operating system can have a significant impact on its ability to be used in a real-time system. This includes the internal design of the operating system as well as the features it provides to the application programmer. This section focuses on the design of two operating systems (Solaris and LynxOS), and their suitability for use in a real-time system.
Desired features of a real-time operating system
Real-time systems are typically implemented with multiple asynchronous threads of execution. This is dictated by the need to react to external events, and control asynchronous devices. Because of this characteristic, an RTOS must support multithreading. Also, because the criticality and rates of events are different, the RTOS must support a notion of priority so that a time-critical task is not delayed because of a non-critical task. Furthermore, tasks need to communicate. Therefore, the OS must provide synchronization and communication facilities.
An RTOS also needs to support timing features like high-resolution timers and clocks. Timers are used to support periodic processing and to detect system timeout errors. Clocks are needed to keep track of time. Typical real-time applications may need to be aware of time at a granularity of micro- or milliseconds.
With respect to performance, the operating system must be predictable and add minimal overhead. As discussed previously, a real-time system must behave deterministically. This implies that the time required by all operations, including operating system functions, must be deterministic. To be deterministic an operating system must be preemptable, which means that if the OS is processing a request on behalf of a low priority task, it must be able to stop what it is doing and turn its attention to a higher priority task. This prevents a situation where a high priority task is forever delayed by the operating system.
Solaris is a general purpose UNIX operating system developed to run on SPARC and Pentium-class CPUs. Solaris has many of the features required for a real-time system. These features are:
Solaris thread implementation. Solaris implements both user-level and kernel-level threads. User-level threads are implemented as a library at the user application level, whereas kernel-level threads are the unit of execution seen by the kernel. Solaris uses the Lightweight Processes (LWP) mechanism to run kernel-level threads on processors. The mapping of user-level threads to LWPs can be done in a number of different ways. If multiple user-level threads are mapped to a single kernel-level thread, at most one of them can be active at a time. To take advantage of multiple processors, user-level threads can be mapped one-to-one to LWPs.
Figure 1 illustrates how Solaris processor sets and processor binding can be used to dedicate processors for real-time tasks., The psrset command is first used to create a pool of one or more processors. Note that all but one processor is eligible for inclusion in the processor set; one processor is needed to process lightweight processes outside the set. The psradm command can then be used to disable unbound interrupts on the processors in the processor set. The psrset command is then used to run real-time processes on the processors in the bound processor set. All other non-real-time processes and interrupts run on processors outside the real-time processor set. As will be addressed later, this mechanism has a dramatic effect on the timeliness of real-time processing.
The Solaris scheduler. To support different types of scheduling policies, Solaris runs each lightweight process in one of four priority classes. These classes are shown in Table 4. Interrupt service routines are not part of the scheduling process, but they are included in Table 4 because they run at a higher priority than all tasks, and thus can interfere with normal LWP processing. Application LWPs run in one of three classes: real-time, system, or timesharing. Interrupt threads are reserved for interrupt processing not done in the interrupt service routine.
Scheduling consists of two processes: deciding which LWP to run and performing tick processing. When the scheduler is invoked it dispatches the LWP with the highest global priority. If the machine has multiple CPUs, the scheduler can dispatch multiple LWPs.
The second aspect of scheduling is tick processing, the processing that takes place at every clock tick. The scheduler will scan all the active LWPs and update their state. For timesharing threads, the scheduler may increase the priority of a LWP if it determines that thread is not receiving a fair share of the CPU. Solaris may also promote a LWP to the system class if the LWP is holding a system resource. Because real-time threads run with a fixed priority scheduling policy, very little tick processing is done for them.
LynxOS is a UNIX-style operating system developed for real-time embedded systems. The Lynx kernel is preemptable, reentrant, and can be scaled down to a footprint as low as 97KB.
Lynx scheduling. LynxOS supports a single scheduling policy, fixed priority preemptive with 256 priority levels. The clock tick frequency is fixed at 100Hz, which limits the resolution of timers to 10 milliseconds. The scheduler is also invoked in response to asynchronous events and change in the system state.
Lynx priority tracking. LynxOS uses a mechanism called priority tracking to handle interrupt processing not done in the interrupt service routine. This is in contrast to the interrupt thread class used by Solaris. The problem with using an interrupt thread class is that interrupt processing on behalf of low priority tasks will run at higher priority than application processing of a high priority task. This creates a priority inversion. The way LynxOS solves this problem is to tie the priority of the interrupt processing to the priority of the application thread. The 256 task priorities are subdivided into 512 priorities and application threads use the 256 even priorities and interrupt threads use the 256 odd priorities. This idea is illustrated in Figure 2, where interrupt threads run a half-step above their corresponding application thread.
Interrupt threads are written as part of the device driver for a particular device, and therefore are not associated with a particular application thread. Because of this, LynxOS provides a mechanism by which the device driver can determine the priority of the thread on behalf of which it is currently running. Using this feature, the interrupt thread can adjust its priority to the appropriate level. If in the future a different application thread needs the same device, the interrupt thread is notified and can change its priority.
Testing the real-time performance of operating systems
The benchmarks used in this study are divided into two categories: those that measure the determinism of the OS and those that measure the latency of particular important operations. These benchmarks are motivated by the real-time performance requirements discussed previously. The benchmarks test core operating system capabilities and are independent of any actual application. Also because we are interested in determining the best possible real-time performance, all real-time threads are run at the maximum possible real-time priority, and the virtual memory used by the benchmarks is locked into physical memory. Table 5 summarizes the six benchmarks used in this study.
The first three benchmarks shown in Table 5, (timer jitter, response, and bintime) are designed to measure the determinism of an operating system. Because determinism implies that the time it takes to perform an operation is known under all circumstances, we typically report the worst case time for these benchmarks.
The structure of the timer jitter test is shown in Figure 3. The test creates a timer, sets it to expire at a given period, then 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 second deterministic benchmark (response) 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 last deterministic benchmark (bintime) determines the maximum kernel blocking time. The 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 final three benchmarks test the synchronization, message passing, and RT signaling capabilities of an operating system. For a real-time system it is important to minimize synchronization and communication latency. So the average latency of operations should be small to minimize the total overhead. Bounding the maximum latency is important as well-to achieve determinism.
Four different synchronization tests are shown in Figure 4. 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 process or two different processes. Measurements from the first two tests can be used to determine the context switching time by subtracting 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 system's ability to deal with priority inversion. The test sets up a classic priority inversion using semaphores. (Note: for clarity the semaphores are not shown in the picture.) The priority inversion occurs when a low priority task acquires (A) a resource needed later by a high priority task. The high priority task blocks waiting on the resource 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 is favored over the high priority task. A typical way of solving this problem is to allow the low priority task to inherit the priority of the high priority task so that it can run and release the resource (R). In the test, a fixed-duration processing loop is used for the medium priority task. If a priority inversion occurs, 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, 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 last benchmark measures the latency of POSIX real-time signals.
The benchmarks defined in the previous section were run on two different operating systems: LynxOS 3.0.1 and Solaris 8. The details of the two systems are shown in Table 6. Note that the CPU, among other hardware characteristics, differs between the two platforms. Because our benchmarks were written to test the determinism of the operating systems, and we observe the worst case time, this difference has little impact on the results. However, the speed difference should be considered when comparing the results of average timings.
Table 6 identifies three different Solaris configurations. These different configurations allow us to investigate the impact of using multiple CPUs. The first configuration uses the two processor Ultra 60 as is. For the second configuration, one of the CPUs is disabled. In the last configuration, one of the CPUs is reserved and the real-time benchmarks are run on it. Also for this configuration the reserved processor is sheltered from all unbound interrupts.
Non real-time external load
The benchmarks were run stand-alone, that is, without any other user processes running, then in combination with a non-real-time load. Typically a real-time system will run a mixture of applications, some with real-time requirements and some without. A graphical user interface is an example of a non-real-time application. Table 7 shows the types of processing used to generate the non-real-time load. The load contains CPU-intensive applications as well as applications that use interrupting I/O devices such as the file and network subsystems.
Figure 5 shows the results of the timer jitter tests for all four platforms. Without a load, shown in Figure 5 a, all platforms have acceptable jitter under 200ms. The Solaris (1 rt) configuration has the least amount of jitter. The jitter for the Lynx configuration is also quite low. Under a heavy load, shown in Figure 5 b, the jitter for the Solaris configurations that do not reserve a real-processor is out of bounds. The worst case jitter, for these configurations, is as great as 10 seconds.
Table 8 shows the worst case response results for all configurations. Without a load, all configurations have a response result very close to the calibrated value of 10 milliseconds. With a load only the Lynx and Solaris (1 rt) configuration come close to the 10-millisecond value. The worst case results for the standard Solaris platform (Solaris 2 proc) is three orders of magnitude worse than the calibrated value.
Figure 6 shows the results for the deterministic bintime benchmark for all configurations. Without a load the kernel imposes very little delay. For the Solaris (1 rt) configuration, the delay is below 10 milliseconds, and for all other configurations the delay is at or less than 100 milliseconds. Under a heavy load, the Solaris configurations without a reserved real-time processor again are very non-deterministic. The maximum delay for the single CPU Solaris configuration is close to one second.
In this section we present the results of the synchronization tests described previously.
Test 1 (Signaling within a thread). Figure 7 shows the results of the simple synchronization test for the Lynx and Solaris (1 rt) configurations. Four different types of synchronization mechanisms were tested for Lynx, and three for Solaris. As Figure 7 a shows, the worst case latency for the Solaris platform is much better than the latency for the Lynx platform. For both platforms the addition of a load has little affect on the worst case timings.
Figure 7b shows the average latencies for the same synchronization mechanisms. For Lynx, the lynx semaphores exhibit the highest latency, most likely because priority inheritance is implemented for this semaphore. For Solaris the latency of the POSIX-named semaphore is much higher than the latency of the other mechanisms. An explanation for this is that the semaphore name is kept in the file system.
Test 2 (Inter-thread signaling). Figure 8 shows the results of the inter-thread signaling test for the Lynx and the Solaris (1 rt) configurations. In all cases the average and worst case round-trip time is better for Lynx than Solaris. This result is especially significant because the Solaris test was run on a faster processor than the Lynx test. Figure 8 also shows that the latency of all types of synchronization mechanisms is roughly equal.
Test 3 (Priority inversion). The results for the priority inversion test are shown in Figure 9, for all configurations. For all cases, except the Lynx (lsem) case, a pthread mutex is used to guard the resource shared by the low and high priority tasks. Without a load, the first Lynx configuration exhibits a latency corresponding to the delay time of the medium priority task of 10 milliseconds. This is due to the fact that in LynxOS 3.0.1, priority inheritance is not implemented for pthread mutexes. This problem is not seen with Lynx semaphores. Priority inheritance is implemented in Solaris, and the latency for all Solaris configurations, without a load, is low.
Under a heavy load, only the Lynx (lsem) and Solaris (1 rt) configurations exhibit an acceptable latency. The Solaris 1rt and 2 proc configurations are affected by the heavy load, and the Lynx configuration still has a high latency, because of the lack of a priority inheritance protocol.
Context switching time. Table 9 shows context switch time for all platforms computed from the results for memory semaphores in the first two synchronization tests. The context switch time for Lynx is less than half the value of the best Solaris configuration. Also for Lynx, the process-to-process context switching time is only slightly worse than the thread-to-thread context switching time.
The context switching time for Solaris threads is more deterministic than the context switching time for processes. For the Solaris (1 rt) configuration, the maximum thread-to-thread context switching time is close to average. However, for the same configuration, the process-to-process context switching time is an order of magnitude worse than the average value. Another interesting observation is that for Solaris the context switching time between processes is slightly better than between threads. In both cases there is a context switch between LWPs, which seems to imply that the bulk of the overhead is in the scheduler.
Real-time signals. Figure 10 shows the results of the real-time signal benchmark for all configurations. The Lynx configuration has a lower signal latency than any of the Solaris configurations. Also the Solaris 1 proc and 2 proc configurations are severely affected by the addition of a non-real-time load.
Message queues. The latency and throughput of POSIX message queues for all configurations is shown in Table 10. The latency for the Lynx platform is better than the Solaris platform, but the Solaris platform has better throughput. This better throughput is most likely due to faster hardware on the Solaris platform.
In this article we have assessed the use of POSIX in the development of software for real-time and embedded systems. We discussed the features of POSIX and how well these features match those required for real-time software development. We also empirically evaluated the real-time performance characteristics of two implementations of POSIX: LynxOS 3.0.1 and Solaris 8.
The empirical evaluation showed that both LynxOS and Solaris are suitable for use in real-time systems. LynxOS exhibited a low overhead for all operations and was deterministic even under heavy loading conditions.
Solaris 8 contains a number of features that are important in real-time development, including high-resolution timers, processor partitioning, and SMP support. These last two features are key in Solaris's use as a real-time operating system. A dramatic difference is apparent between the determinism of the standard Solaris configuration and one in which all real-time tasks are run on a dedicated processor. The standard configuration is unsuitable for real-time, whereas the second configuration is very deterministic.
Although this study did not perform an exhaustive comparison of the POSIX APIs between Solaris and LynxOS, our conclusion is that the two implementations of POSIX have a great deal in common. The biggest differences are in the areas of clock resolution and number of real-time priorities. Clock resolution could pose a portability problem if a resolution of greater than 10 milliseconds is needed. Other differences that we encountered, like discrepancies in the LynxOS threads implementation, have been rectified in v. 3.1 of the operating system.
Kevin Obenland received his PhD in computer engineering from the University of Southern California in 1998. He has close to 10 years of experience in the development of embedded systems. For the past two years, he has been investigating the performance of various real-time operating systems. Obenland is also an adjunct faculty member at George Mason University in Fairfax, VA, where he teaches a course on the design and implementation of operating systems. To request the benchmarks used in this study, contact him at firstname.lastname@example.org.
The author was employed by the MITRE Corp. when this work was performed and would like to acknowledge their support.
1. IEEE/ANSI Std 1003.1: Information Technology- (POSIX)-Part 1: System Application: Program Interface (API) [C Language], includes (1003.1a, 1003.1b, and 1003.1c). 1996. Back
3. Stankovic, J.A. Misconceptions About Real-time Computing. Los Alamitos, CA: IEEE Computer. October 1988. Back
5. Stankovic, J.A. and K. Ramamritham, "What is Predictability for Real-time Systems?" Journal of Real-time Systems, 1990. Back
6. Lewine, D. POSIX Programmer's Guide. Sebastopol, CA: O'Reilly & Associates, 1991. Back
7. 1003.1d Information Technology- (POSIX)-Part 1: System Application Program Interface (API)-Amendment x: Additional Real-time Extensions. 1999. Back
8. 1003.1j-2000: Information Technology-(POSIX)-Advanced Real-time Extensions.Back
9. 1003.21, LIS D3.0: Information Technology- (POSIX) RT Distributed Composite Insulators. 1999.Back
10. Gallmeister, B.O. Programming for the Real World, POSIX.4. Sebastopol, CA: O'Reilly & Associates, 1995. Back
11. 1003.1h D5, Draft POSIX Part 1: System API Extension-RASS. 1999. Back
12. National Institute of Standards and Technology, PCTS: 151-2, POSIX Test Suite. Back
13. 1003.13-1998 IEEE Standard for Information Technology-Standardized Application Environment Profile (AEP)-POSIX Real-time Application Support. 1998. Back
14. Nichols, B., D. Buttlar, and J.P. Farrell. Pthreads Programming. Sebastopol, CA: O'Reilly & Associates, 1996.Back
15. Scalable Real-time Computing in the Solaris Operating Environment. SUN White paper. Back
16. Stallings, W. Operating Systems. Englewood Cliffs, NJ: Prentice-Hall, Inc., 1998.Back
17. Cockcroft, A. "Processor Partitioning." Performance Q&A. SunWorld. 1998. Back
18. Mauro, J. and R. McDougall. Solaris Internals: Core Kernel Architecture, 1st edition. Prentice-Hall PTR/Sun Microsystems Press, 2000. Back
21. Obenland, K., T. Frazier, J.S. Kim, and J. Kowalik. "Comparing the Real-time Performance of Windows NT to an NT Real-time Extension." Proceedings RTAS. 1999. Back
22. H.J. Curnow, B.A. Wichmann. "A Synthetic Benchmark," Computer Journal 19(1): 43-49. 1976. Back
23. L. Monk, et al. "Real-time Communications Scheduling: Final Report." MITRE MTR 97B69. 1997. Back