The Design and Performance of a Real-time CORBA Object Event Service

Timothy H. Harrison, David L. Levine, and Douglas C. Schmidt

{harrison, levine, schmidt}@cs.wustl.edu
Department of Computer Science
Washington University,
St Louis, MO 63130,
(TEL) (314) 935-4215
(FAX) (314) 935-7302

The final version of this paper appeared in the Proceedings of the OOPSLA '97 conference, Atlanta, Georgia, October, 1997.

Abstract

The CORBA Event Service provides a flexible model for asynchronous communication among objects. However, the standard CORBA Event Service specification lacks important features required by real-time applications. For instance, operational flight programs for fighter aircraft have complex real-time processing requirements. This paper describes the design and performance of an object-oriented, real-time implementation of the CORBA Event Service that is designed to meet these requirements.

This paper makes three contributions to the design and performance measurement of object-oriented real-time systems. First, it illustrates how to extend the CORBA Event Service so that it is suitable for real-time systems. These extensions support periodic rate-based event processing and efficient event filtering and correlation. Second, it describes how to develop object-oriented event dispatching and scheduling mechanisms that can provide real-time guarantees. Finally, the paper presents benchmarks that demonstrate the performance tradeoffs of alternative concurrent dispatching mechanisms for real-time Event Services.

1. Introduction

There is a widespread belief in the embedded systems community that object-oriented (OO) techniques are not suitable for real-time systems. In particular, the dynamic binding properties of OO programming languages seem antithetical to real-time systems, which require deterministic execution behavior and low latency. However, many real-time application domains (such as avionics, telecommunications, process control, and distributed interactive simulation) can benefit from flexible and open distributed object computing architectures, such as those defined in the CORBA specification [OMG:95a].

1.1. Overview of CORBA

CORBA is a distributed object computing middleware standard being defined by the Object Management Group (OMG). CORBA is designed to support the development of flexible and reusable distributed services and applications by (1) separating interfaces from remote implementations and (2) automating many common network programming tasks (such as object registration, location, and activation; request demultiplexing; framing and error-handling; parameter marshalling and demarshalling; and operation dispatching).

Figure 1 illustrates the primary components in the OMG Reference Model architecture [Vinoski:97]:

Figure 1. OMG Reference Model Architecture.

At the heart of the OMG reference model is the Object Request Broker (ORB). ORBs allow clients to invoke operations on target object implementations without concern for where the object resides, what language the object is written in, the OS/hardware platform, or the type of communication protocols and networks used to interconnect distributed objects [Schmidt:97].

This paper focuses on the CORBA Event Service, which is defined within the CORBA Object Services (COS) component in Figure 1. The COS specification [OMG:95b] presents architectural models and interfaces that factor out common services for developing distributed applications.

Many distributed applications exchange asynchronous requests using event-based execution models [Rajkumar:95]. To support these common use-cases, the CORBA Event Service defines supplier and consumer participants. Suppliers generate events and consumers process events received from suppliers. In addition, the CORBA Event Service defines an Event Channel, which is a mediator [Gamma:95] that propagates events to consumers on behalf of suppliers.

The OMG Event Service model simplifies application software by allowing decoupled suppliers and consumers, asynchronous event delivery, and distributed group communication [Maffeis:95a]. In theory, this model seems to address many common needs of event-based, real-time applications. In practice, however, the standard CORBA Event Service specification lacks other important features required by real-time applications such as real-time event dispatching and scheduling, periodic event processing, and efficient event filtering and correlation mechanisms.

To alleviate the limitations with the standard COS Event Service, we have developed a Real-time Event Service (RT Event Service) as part of the TAO project [Schmidt:97] at Washington University. TAO is a real-time ORB endsystem that provides end-to-end quality of service guarantees to applications by vertically integrating CORBA middleware with OS I/O subsystems, communication protocols, and network interfaces. Figure 2 illustrates the key architectural components in TAO and their relationship to the real-time Event Service.

Figure 2. TAO: An ORB Endsystem Architecture for High-Performance, Real-time CORBA.

TAO's RT Event Service augments the CORBA Event Service model by providing source-based and type-based filtering, event correlations, and real-time dispatching. To facilitate real-time scheduling (e.g., rate monotonic [LiuLayland:73]), TAO's RT Event Channels can be configured to support various strategies for priority-based event dispatching and preemption. This functionality is implemented using a real-time dispatching mechanism that coordinates with a system-wide real-time Scheduling Service.

TAO's RT Event Service runs on real-time OS platforms (e.g., VxWorks and Solaris 2.x) that provide real-time scheduling guarantees to application threads. Windows NT also provides real-time threads, though it lacks certain features required for hard real-time systems [Jensen:97].

1.2. Related Work

Conventional approaches to QoS enforcement have typically adopted existing solutions from the domain of real-time scheduling, [Liu:73], fair queuing in network routers [Zhang:90b], or OS support for continuous media applications [Blair:95]. In addition, there have been efforts to implement new concurrency mechanisms for real-time processing (such as the real-time threads of Mach [Tokuda:90] and real-time CPU scheduling priorities of Solaris [Khanna:92]).

However, QoS research at the network and OS layers has not necessarily addressed key requirements and usage characteristics of distributed object computing middleware. For instance, research on QoS for network infrastructure has focused largely on policies for allocating bandwidth on a per-connection basis. Likewise, research on real-time operating systems has focused largely on avoiding priority inversions and non-determinism in synchronization and scheduling mechanisms. In contrast, the programming model for developers of OO middleware focuses on invoking remote operations on distributed objects. Determining how to map the results from the network and OS layers to OO middleware is a major focus of our research.

There are several commercial CORBA-compliant Event Service implementations available from multiple vendors (such as Expersoft, Iona, Sun Systems, and Visigenic Software). Iona also sells OrbixTalk, which is a messaging technology based on IP multicast. Unfortunately, since the CORBA Event Service specification does not address issues critical for real-time applications, these implementations are not acceptable solutions for many domains.

The OMG has issued a request for proposals (RFP) on a new Notification Service [OMG:97a] that has generated several responses [OMG:97b]. The RFP specifies that a proposed Notification Service must be a superset of the COS Event Service with interfaces for the following features: event filtering, event delivery semantics (e.g., at least once, at most once, etc), security, event channel federations, and event delivery Quality of Service (QoS). The organizations contributing to this effort have done some excellent work in addressing many of the shortcomings of the CORBA Event Service [Schmidt:97b]. However, the OMG RFP documents do not address the implementation issues related to the Notification Service.

Although there has been research on formalisms for real-time objects [Satoh:95], relatively little published research on the design and performance of real-time OO systems exists. Our approach is based on emerging distributed object computing standards (i.e., CORBA) -- we focus on the design and performance of various strategies for implementing Quality of Service (QoS) in real-time ORBs [Schmidt:97].

The QuO project at BBN [QuO:97] has defined a model for communicating changes in QoS characteristics between applications, middleware, and the underlying endsystems and network. The QuO architecture differs from our work on RT Event Channels, however, since QuO does not provide hard real-time guarantees of ORB endsystem CPU scheduling. SunSoft [Aahlad:96] describes techniques for optimizing the performance of CORBA Event Service implementations. As with QuO, their focus also was not on guaranteeing CPU processing for events with hard real-time deadlines.

[Rajkumar:95] describes a real-time publisher/subscriber prototype developed CMU SEI. Their Publisher/Subscriber model is functionally similar to the COS Event Service, though it uses real-time threads to prevent priority inversion within the communication framework. One interesting aspect of the CMU model is their separatiion of priorities for subscription and event transfer so that these activities can be handled by different threads with different priorities. However, their model does not utilize any QoS specifications from publishers (suppliers) or subscribers (consumers). As a result, their message delivery mechanism cannot distinguish participants with higher priorities. In contrast, the TAO Event Service utilizes QoS parameters from suppliers and consumers to guarantee the event delivery semantics determined by a real-time scheduling service.

1.3. Organization

This paper is organized as follows: Section 2 describes how the CORBA Event Service model can help to simplify application development in real-time domains like avionics; Section 3 discusses the real-time extensions we added to the CORBA Event Service; Section 4 outlines the OO framework for real-time event dispatching and scheduling that forms the core of TAO's Real-time Event Service; Section 5 shows how different implementations of the dispatching and scheduling mechanisms perform under different workloads on VxWorks running real-time threads; Section 6 discusses our experiences using OO techniques in a real-time context; and Section 7 presents concluding remarks.


2. Overview of the OMG CORBA Event Service

2.1. Background

The standard CORBA operation invocation model supports twoway, oneway, and deferred synchronous interactions between clients and servers. The primary strength of the twoway model is its intuitive mapping onto the object->operation() paradigm supported by OO languages. In principle, twoway invocations simplify the development of distributed applications by supporting an implicit request/response protocol that makes remote operation invocations transparent to the client. In practice, however, the standard CORBA operation invocation models is too restrictive for real-time applications. In particular, these models lack asynchronous message delivery, do not support timed invocations or group communication, and can lead to excessive polling by clients. Moreover, standard oneway invocations might not implement reliable delivery and deferred synchronous invocations require the use of the CORBA Dynamic Invocation Interface (DII), which yields excessive overhead for most real-time applications [Schmidt:96].

The Event Service is a CORBA Object Service (COS) that is designed to alleviate some of the restrictions with standard CORBA invocation models. In particular, the COS Event Service supports asynchronous message delivery and allows one or more suppliers to send messages to one or more consumers. Event data can be delivered from suppliers to consumers without requiring these participants to know about each other explicitly.

2.2. Structure and Participants for the COS Event Service

Figure 3 shows the key participants in the COS Event Service architecture:

Figure 3. Participants in the COS Event Channel Architecture.

The role of each participant is outlined below:

Suppliers use Event Channels to push data to consumers. Likewise, consumers can explicitly pull data from suppliers. The push and pull semantics of event propagation help to free consumers and suppliers from the overly restrictive synchronous semantics of the standard CORBA twoway communication model. In addition, Event Channels can implement group communication by serving as a replicator, broadcaster, or multicaster that forward events from one or more suppliers to multiple consumers.

There are two models (i.e., push vs. pull) of participant collaborations in the COS Event Service architecture. This paper focuses on real-time enhancements to the push model, which allows suppliers of events to initiate the transfer of event data to consumers. Suppliers push events to the Event Channel, which in turn pushes the events to consumers.

2.3. Applying TAO's Real-time Event Service to Real-time Avionics Systems

Modern avionics systems are characterized by processing tasks with deterministic and statistical real-time deadlines, periodic processing requirements, and complex data dependencies. Building flexible application software and OO middleware that meets these requirements is challenging because the need for determinism and predictability often results in tightly coupled designs. For instance, conventional avionics mission control applications consist of closely integrated responsibilities that manage sensors, navigate the airplane's course, and control weapon release.

Tight coupling often yields highly efficient custom implementations. As the example below shows, however, the inflexibility of tightly coupled software can substantially increase the effort and cost of integrating new and improved avionics features. For example, navigation suites are a source of continual change, both across platforms and over time. The specific components that make up the navigation suite change frequently to improve accuracy and availability. Many conventional avionics systems treat each implementation as a ``point solution,'' with built-in dependencies on particular components. This tight coupling requires expensive and time consuming development effort to port systems to newer and more powerful navigation technologies.

2.3.1. Overview of Conventional Avionics Application Architectures

Figure 4 shows a conventional architecture for distributing periodic I/O events throughout an avionics application:

Figure 4. Example Avionics Mission Control Application.

This example has the following participants:

The push-driven model described above is commonly used in many real-time environments, such as industrial process control systems and military command/control systems. One positive consequence of this push-driven model is the efficient and predictable execution of operations. For instance, I/O Facades only execute when their event dependencies are satisfied (i.e., when they are called by Sensor Proxies).

In contrast, using a pull-driven model to design the mission control application would require I/O Facades that actively acquire data from the Sensor Proxies. If the data was not available to be pulled, the calling I/O Facade would need to block awaiting a result. In order for the I/O Facade to pull, the system must allocate additional threads to allow the application to make progress while the I/O Facade task is blocked. However, adding threads to the system has many negative consequences (such as increased context switching overhead, synchronization complexity, and complex real-time thread scheduling policies). Conversely, by using the push model, blocking is largely alleviated, which reduces the need for additional threads. Therefore, this paper focuses on the push model.

2.3.2. Drawbacks with Conventional Avionics Architectures

A disadvantage to the architecture shown in Figure 4 is the strong coupling between suppliers (Sensor Proxies) and consumers (I/O Facades). For instance, in order to call back to I/O Facades, each Sensor Proxy must know which I/O Facades depend on its data. As a result, changes to the I/O Facade layer (e.g., addition/removal of a consumer) require the modification of Sensor Proxies. Likewise, consumers that register for callbacks are tightly coupled with suppliers. If the availability of new hardware (such as Forward Looking Infared Radar) requires a new Sensor Proxy, I/O Facades must be altered to take advantage of the new technology.

2.3.3. Alleviating Drawbacks with Conventional Avionics Architectures

Figure 5 shows how an Event Channel can alleviate the disadvantages of the tightly coupled consumers and suppliers shown above in Figure 4.

Figure 5. Example Avionics Application with Event Channel.

In Figure 5, Sensor Proxy objects are suppliers of I/O events that are propagated by an Event Channel to I/O Facades, which consume the demarshalled I/O data. Sensor Proxies push I/O events to the channel without having to know which I/O Facades depend on the data. The benefit of using the Event Channel is that Sensor Proxies are unaffected when I/O Facades are added or removed. This architectural decoupling is described concisely by the Observer pattern [Gamma:95].

Another benefit of an Event Channel-based architecture is that an I/O Facade need not know which Sensor Proxies supply its data. Since the channel mediates on behalf of the Sensor Proxies, I/O Facades can register for certain types of events (e.g., GPS and/or INS data arrival) without knowing which Sensor Proxies actually supply these types of events (Section 3.2 discusses type-based filtering). Once again, the use of an Event Channel makes it possible to add or remove Sensor Proxies without changing I/O Facades.


3. Overview of the Real-time Event Service

3.1. Motivation

As shown in the previous section, the CORBA COS Event Service provides a flexible model for transmitting asynchronous events among objects. For example, it removes several restrictions inherent in synchronous twoway communication. Moreover, it frees application programmers from the tedious and error-prone details of handling registrations from multiple consumers and suppliers. In addition, the COS Event Service interfaces are fairly intuitive and the consumer/supplier connections and event delivery models are symmetrical and straightforward.

However, the standard COS Event Service Specification lacks several important features required by real-time applications. Chief among these missing features include real-time event dispatching and scheduling, periodic event processing, and centralized event filtering and correlations. To resolve these limitations, we have developed a Real-time Event Service (RT Event Service) as part of the TAO project [Schmidt:97]. TAO's RT Event Service extends the COS Event Service specification to satisfy the quality of service (QoS) needs of real-time applications in domains like avionics, telecommunications, and process control.

The following list summarizes the features missing in the COS Event Service and outlines how TAO's Real-time Event Service supports them:

3.2. RT Event Service Architecture

Figure 6 shows the high-level architecture of TAO's RT Event Service implementation.

Figure 6. RT Event Service Architecture.

The role of each component in the RT Event Service is outlined below:

3.3. Static and Dynamic Event Channel Configuration

The performance requirements of an RT Event Service may vary for different types of real-time applications. The primary motivation for basing the internal architecture of the TAO Event Channel on the ACE Streams Framework is to allow static and dynamic channel configurations. Each module shown in the Figure 7 may contain multiple ``pluggable'' strategies, each optimized for different requirements. The Streams-based architecture allows independent processing modules to be added, removed, or modified without requiring changes to other modules.

TAO's Event Channel can be configured in the following ways to support different event dispatching, filtering, and dependency semantics:

In static real-time environments (such as conventional avionics systems), the configuration of an Event Channel is generally performed off-line to reduce startup overhead. In dynamic real-time environments (such as telecommunication call-processing), however, component policies may require alteration at run-time. In these contexts, it may be unacceptable to completely terminate a running Event Channel when a scheduling or concurrency policy is updated. In general, therefore, an RT Event Channel framework must support dynamic reconfiguration of policies without interruption while continuing to service communication operations [Stefani:96]. Basing TAO's RT Event Channel on the ACE Streams framework supports both static and dynamic (re)configuration.


4. An Object-Oriented Framework for Real-time Event Service Dispatching and Scheduling

Applications and middleware components using a real-time Event Service have deterministic and statistical deadlines. As a result, TAO's RT Event Channel utilizes a real-time Scheduling Service to ensure that events are processed before deadlines are missed. Most real-time scheduling policies (such as rate monotonic and earliest deadline first) require priority-based event dispatching and preemption. To maximize reuse and allow flexibility between multiple scheduling policies, TAO's Event Channel framework separates the dispatching mechanism from the scheduling policy. The dispatching mechanism implements priority-based dispatching and preemption, but consults a Run-time Scheduler to determine the priorities of objects and events.

This section discusses the Dispatching Module and Scheduling Service in TAO's RT Event Channel.

4.1. The Dispatching Module

The Dispatching Module is responsible for implementing priority-based event dispatching and preemption. When the Dispatching Module receives a set of supplier events from the Event Correlation Module, it queries the Run-time Scheduler to determine the priority of the consumers that the events are destined for. With that information, the Dispatching Module can either (1) insert the events in the appropriate priority queues (which are dispatched at a later time) or (2) preempt a running thread to dispatch the new events immediately.

The following figure shows the structure and dynamics of the Dispatching Module in the context of the Event Channel:

Figure 8. Event Channel Dispatching.

The participants in Figure 8 include the following:

Figure 9. Dispatcher Implementations.

4.1.1. Dispatcher Preemption Strategies

An important responsibility of the Event Channel's Dispatcher mechanism is preemption. Most real-time scheduling policies require preemption. For example, if consumer A with a priority of 2 is executing when consumer B with a priority of 1 becomes runnable, consumer A should be preempted so that B can run until it completes or is itself preempted by a consumer with a priority of 0. As shown in Figure 9, TAO's Event Channel Dispatching Module supports several levels of preemption via the following strategies:

The current design of the Dispatching Module is motivated largely from need to support a single host, real-time event propagation mechanism. To allow all CORBA applications to utilize the ORB's real-time scheduling and dispatching features, we are integrating the role of the Dispatching Module into TAO's real-time Object Adapter [Schmidt:97]. However, this paper focuses on an implementation that integrates real-time dispatching into TAO's Real-time Event Service.

4.1.2. Scheduling Enforcement

The real-time scheduling for the version of TAO's Event Channel described in this paper is performed off-line. Therefore, no mechanisms for enforcing component behavior are provided. Consequently, tasks that overrun their allotted resource allocations can cause other tasks to miss their deadlines. An advantage of this ``trusting'' policy is there is no overhead incurred by QoS enforcement mechanisms that would otherwise be necessary to monitor and enforce the scheduling behavior at run-time. A disadvantage is that all components must behave properly, i.e., they must use only the resources allotted to them. Though the architecture of our Event Service framework supports QoS enforcement, the decision not to include this mechanism in the Event Channel is motivated by the static scheduling characteristics and stringent performance requirements of real-time avionics applications.

4.1.3. Visualization of Dispatching Module Implementations

To visualize the semantic differences between the four Dispatching Module implementations outlined in Section 4.1.1, we implemented a timeline visualization tool in Java. The timeline tool reads event logs from RT Event Service test runs and displays a timeline of supplier and consumer activity. Figures 10, 11, and 12 show timelines from multi-threaded, single-threaded, and the EFD implementations of the Dispatching Module, respectively Each test run consists of 3 suppliers and 3 consumers, which are listed on the y-axis. Supplier2 and consumer2 run at the highest frequency (40 Hz), supplier1 and consumer1 run at the next highest frequency (20 Hz), and supplier0 and consumer0 run at the lowest frequency (10 Hz).

The x-axis denotes time in microseconds. Each consumer and supplier outputs a point when it receives an event from the Event Channel. Another point is output when it finishes processing the event. Suppliers receive timeouts and generate a single event for each timeout. Each consumer registers for events from a single supplier. A horizontal line indicates the time span when the respective consumer or supplier runs on the CPU.

Each figure is explained below:

4.2. Real-time Scheduling Service

The RT Event Service must guarantee that consumers receive and process events with sufficient time to meet their deadlines. To accomplish this, we have developed a Real-time Scheduling Service. The two primary components in the Real-time Scheduling Service are the Run-time Scheduler and the Off-line Scheduler. Although a complete discussion of these components is beyond the scope of this paper, their responsibilities are summarized below ([Schmidt:RFI] describes these components in detail).

4.2.1. Run-time Scheduler

The Run-time Scheduler associates priorities with target object implementation operations at run-time. The implementation of the Real-time Scheduling Service described in this paper uses a static scheduling policy. Therefore, thread priorities are determined prior to run-time by the Off-line Scheduler.

Our Real-time Scheduling Service requires that all operations export RT_Info data structures that describe the execution properties of the operation. During scheduling configuration runs (described in the Off-line Scheduler section below), RT_Infos contain execution times and rate requirements. At run-time, the static Scheduler need not know any information about an operation's execution characteristics. Only the operation's priority is needed, so the scheduler can determine how the operation should be dispatched. Thus, at run-time, each operation's RT_Info need only contain priority values for the operation.

At run-time, the Dispatching Module queries the Run-time Scheduler for the priority of a consumer's push operation. The Run-time Scheduler uses a static repository that identifies the execution requirements (including priority) of each operation. The Event Channel's Dispatching Module uses the operation priority returned by the Run-time Scheduler to determine which priority queue an event/consumer tuple should be inserted onto.

All scheduling and priority computation is performed off-line. This allows priorities to be computed rapidly (i.e., looked up in O(1) time) at run-time. Thus, TAO's Run-time Scheduler simply provides an interface to the results of the Off-line Scheduler, discussed below.

4.2.2. Off-line Scheduler

The Off-line Scheduler has two responsiblities. First, it assigns priorities to object operations. Second, it determines whether a current system configuration is schedulable given the available resources and the execution requirements of supplier and consumer operations. Both responsibilities require that operationg interdependencies be calculated by a Task Interdependency Compilation process during during a configuration run. Task Interdependency Compilation builds a repository that records which objects' operations call each other. This can be visualized as a directed graph where the nodes in the graph are object operations and directed edges indicate that one operation calls another, as shown in Figure 13.

Figure 13. Scheduling Service Internal Repository.

Once Task Interdependency Compilation is complete, the Off-line Scheduler assigns priorities to each object operation. The implementation of the Event Service described in this paper utilizes a rate monotonic scheduling (RMS) policy. Therefore, priorities are assigned based on task rates, i.e., higher priorities are assigned to threads with faster rates. For instance, a task that needs to execute at 30 Hz would be assigned to a thread with a higher priority than a task that needs to execute at 15 Hz.

Most operating systems that support real-time threads guarantee higher priority threads will (1) preempt lower priority threads and (2) run to completion (or until higher priority threads preempt them). Therefore, object operations with higher priorities will preempt object operations with lower priorities. These priority values are computed by the Off-line Scheduler and are stored in a table that is queried by the Run-time Scheduler at execution time.


5. Performance Tests

5.1. Utilization Measurements

For non-real-time Event Channels (e.g., EFD-based), correctness implies that consumers receive events when their dependencies are met (i.e., source/type subscriptions and correlations). Conversely, for real-time Event Channels (e.g., RTUs and real-time threads), correctness implies that deadlines are met. Therefore, correct RT Event Service behavior requires that (1) consumers receive events when their dependencies are satisfied and (2) consumers receive these events in time to meet their deadlines.

An important metric for evaluating the performance of the RT Event Service is the Schedulable Bound. The schedulable bound of a real-time schedule is the maximum resource utilization possible without deadlines being missed [Gopal:96]. Likewise, the schedulable bound of the RT Event Service is the maximum CPU utilization that supplier and consumers can achieve without missing deadlines.

For TAO's Real-time Scheduling Service to guarantee the schedulability of a system (i.e., all tasks meet their deadlines), high priority tasks must preempt lower priority tasks. Thus, in RMS terminology, higher rate tasks preempt lower rate tasks.

Each of the RT Event Channel's Dispatching Module strategies support varying degrees of preemption. The EFD and Single-Threaded implementations support no preemption; the RTU implementation supports deferred preemptions; and the multi-threaded version uses OS support for ``immediate'' preemption. The goal of the benchmarks described below is to measure the utilization implications of each approach.

The performance tests discussed below were conducted on a single-CPU Pentium Pro 200 MHz workstation with 128 MB RAM running Windows NT 4.0. Test configurations included 3 suppliers and 3 consumers. As shown in Figure 14, the Timeline tool can zoom out to show the periodic nature of the test participants.

Figure 14. Wide view of test run.

The view in Figure 14 shows the relative frequencies of the participants. Supplier2 generates events for consumer2 at the highest frequency (40 Hz). Likewise, supplier1 generates events for consumer1 at 20 Hz, and supplier0 generates events for consumer0 at 10 Hz.

Figure 15 shows the total CPU utilization achieved (y-axis) by each Event Channel implementation (i.e., multi-threaded, RTU, single-threaded, and EFD), as the workload configuration was changed (x-axis).

Figure 15. CPU Utilization for RTU, Multi-Threaded, Single-Threaded, and EFD channel implementation.

More specifically, the x-axis in Figure 15 represents the percentage workload given to the 40 Hz supplier and consumer. For instance, at the 10% x-axis column, the 40 Hz supplier and consumer were given relatively small amounts of work (10% of the total possible) to perform each iteration (40 times second). Then the workload for the 20 Hz and 10 Hz participants was repeatedly increased (thus increasing overall cpu utilization) until deadlines started to be missed. The maximum utilization achieved was then plotted relative to the y-axis.

As the values along the x-axis increase, the workload of the 40 Hz participants increases and the workload of the 20 Hz and 10 Hz participants decreases. Likewise, for lower values on the x-axis, the workload of the 20 Hz and 10 Hz participants are larger. For each value on the x-axis, the maximum utilization achieved without any missed deadlines was then plotted on the y-axis. The graph in Figure 15 illustrates how the utilization of different channel implementations can vary as the configuration of the system changes.

The results of our performance benchmarks show that the RTU and multi-threaded implementations of the channel achieve approximately 95% utilization for all workload configurations. That these implementations fell 5% behind the maximum utilization results from the overhead imposed by the Event Channel. Although the RTU and multi-threaded implementations performed consistently for all configurations, utilizations for the single-threaded and EFD implementations vary significantly as the workload configurations change. These results show how the increased support for preemption provide greater stability across workloads.

The differences between the single-threaded and EFD channels can be accounted for by the fact that the single-threaded channel provides minimal support for preemption. After each event is propagated to a consumer in the single-threaded channel, the channel's thread (in the Dispatching Module) dispatches the next highest priority event/consumer tuple. Thus, if while an event is being dispatched, a higher priority event/consumer tuple arrives in the channel (e.g., a timeout for a high priority consumer), the new tuple will be dispatched as soon as the currently running event completes.

Alternatively, when a supplier generates an event in the EFD channel, it is dispatched immediately to all consumers. If the EFD channel is dispatching an event to consumers when a timeout occurs for a higher priority consumer, the timeout will not be dispatched until all other consumers have completed. In the single-threaded channel, the timeout would be dispatched after the next consumer completed. The EFD's semantics increase the chances of missed deadlines and consequently reduce utilization.

It is also instructive to note that the single-threaded implementation performs optimally when the workload of 40 Hz participants is the greatest. For higher x-axis values, the workload of the 20 Hz and 10 Hz participants is lower. This reduces the demand for preemption since lower priority suppliers and consumers only use the thread of control for a very short time (since they are doing less work). Therefore, the graph shows that as the demand for preemption decreases (x values become greater), the lack of support for preemption becomes less crucial.

5.2. Latency Measurements

Another important measure of Event Channel performance is the latency it introduces between suppliers and consumers. To determine Event Channel latency, we developed the Event Latency Test shown in Figure XYZ. This test timestamps each event as it originates in the supplier and then subtracts that time from the arrival time at the consumer to obtain the supplier-to-consumer latency. The consumer does not do anything with the event other than to keep track of the minimum, maximum, and average latencies.

The Minimum Event Spacing Test looks at the average event delivery time for all of the events that a supplier delivers to its consumers. As before, consumers do not do anything with events that are pushed to them. The average event delivery time includes the event interval (spacing) and Event Channel overhead. Ideally, it should be as close as possible to the event interval. As the event interval is reduced, however, the event channel overhead starts to become significant. This test finds that minimum event interval.

These tests were run on a Sun Ultra 2 with (2) 167 Mhz CPUs, running SunOS 5.5.1. The Event Channel and test applications were built with g++ 2.7.2 with -02 optimization. Consumers, suppliers, and the Event Channel were all in the same process, so there was no ORB remote communication overhead. Furthermore, there was no other significant activity on the workstation during testing. All tests were run in the Solaris real-time scheduling class, so they had the highest software priority (but below hardware interrupts).

With the single-threaded Event Channel, we measured a best-case supplier-to-consumer latency of about 140 microsec. ``Best-case'' refers to a single supplier and single consumer registered with Event Channel. The supplier received a timeout every 250 milliseconds and then sent a timestamped event to the consumer. As the number of suppliers and/or consumers was increased, the latency increased as well. With 50 suppliers and 1 consumer, the latency was about 1,136 microseconds. With 1 supplier and 50 consumers, it was about 1,303 microseconds. And with 50 suppliers and 50 consumers, equally distributed amongst the suppliers, it was about 1,283 microseconds.

Under these conditions, the average event delivery time was comparable to the event timeout interval of 250 milliseconds. The supplier timeout value was progressively reduced to find the point at which the Event Channel overhead significantly affected the average delivery time. That timeout interval was ~20 msec; below that value, the average event delivery time increased significantly.

We are currently investigating opportunities for enhancing our first implementation of the Event Channel to improve these performance numbers.


6. Evaluating the Use of OO for Real-time Systems

While applying OO technologies to real-time systems we encountered two issues regarding polymorphism that threatened to compromise the predictability and performance of our systems. This section briefly discusses each of the issues and how our systems address the potential problems.

6.1. The Cost of Dynamic Binding Mechanisms

Since our systems are developed using C++, dynamic binding is implemented via virtual function tables (VFTs). As a result, compilers can implement highly optimized virtual function mechanisms that impose constant-time overhead. These algorithms typically involve loading the this pointer, the this pointer adjustment (for multiple inheritance), the VFT, and virtual function address before invoking the function. However, these steps still have bounded completion times allowing predictable virtual function call performance regardless of the degree of inheritance used by applications.

6.2. The Cost of Polymorphism

Polymorphism facilitates run-time changes in object behavior. Real-time systems often require predictable behavior of all components. Initially, the flexibility of polymorphism seems to be at odds with the requirement for real-time predictability. We resolved this issue using the Off-line Scheduler discussed in Section 4.2. Since scheduling is performed off-line, all objects and operations must be known in advance. Therefore, it is the responsibility of the Off-line Scheduler to determine whether a particular system configuration will meet all of its deadlines. As a result, when a virtual function is called at run-time, the system is not concerned with the actual implementation being invoked. The Off-line Scheduler has already guaranteed that its deadline will be met, based on the published parameters of each schedulable operation.

One advantage of our approach is that operation invocations only pay the overhead of the C++ virtual function call. If the schedule was not determined off-line, a run-time (dynamic) scheduler would need to intercede before any abstract operation was invoked, which incurs additional overhead. For instance, if a Rate Monotonic scheduling policy is used, the scheduler must determine the rate of each object in order to calculate the object's priority. Furthermore, this type of dynamic scheduler must make some type of guarantee, either weak or strong, that deadlines will be met.

One way a scheduler could make strong guarantees is to perform admission control, which permits operations to execute when the necessary resources are available. Admission control requires that object operations export execution properties such as worst-case execution time. Alternatively, the scheduler might implement a weaker, ``best-effort'' admission policy. For example, if an Earliest Deadline First policy is used, object operations with the nearest deadlines are given priority over operations with later deadlines. Such a policy would require that object operation deadlines be exported or calculated by the scheduler.

In general, dynamic scheduling can incur significant overhead, decrease resource utilization, and fail to work correct when faced with system overload. As a result, dynamic scheduling solutions may not be viable solutions for systems with hard deadlines and constrained resources.

Since all objects and operations in TAO's Real-time Event Service are determined off-line, one could argue that no real polymorphism exists. Although this is true to a certain extent, there are more benefits to dynamic binding than just change behavior at run-time. In particular, we found that the ability to develop components independently of applications that use them significantly increases the potential for reuse in the avionics domain. The Event Channel pushes to abstract PushConsumer interfaces. Although the number and type of PushConsumers is determined off-line, the code for the Event Channel remains decoupled from application consumer objects.


7. Concluding Remarks

The CORBA COS Event Service provides a flexible OO model where Event Channels dispatch events to consumers on behalf of suppliers. TAO'S Real-time Event Service described in this paper augments this model with Event Channels that support source and type-based filtering, event correlations, and real-time event dispatching. TAO's Event Channels can be configured with multiple scheduling policies (e.g., rate monotonic scheduling and earliest deadline first) by configurating different Run-time Scheduler strategies. Similarly, channels can be built with varying levels of support for preemption by configuring different Dispatcher preemption strategies (e.g., EFD, single-threaded, RTU, and real-time thread Dispatchers). This flexibility allows applications to adapt their scheduling and dispatching policies to obtain optimal utilization for different application requirements and platform resource characteristics.

Our performance results demonstrate that dispatching mechanisms with finer-grained support for preemption yield more consistent CPU utilization across different application configurations. These results also indicate that the dynamic binding mechanisms used by our C++ compilers are not fundamentally at odds with the deterministic execution behavior required by real-time applications. In addition, our results illustrate that it is feasible to apply CORBA Object Services to develop real-time systems. TAO's Real-time Scheduling Service architecture was submitted as a response to the OMG Real-time Special Interest Group Request for Information on Real-time CORBA [Schmidt:RFI].

The current implementation of TAO's Real-time Event Service is written in C++ using components from the ACE framework [Schmidt:94b]. ACE is a widely used communication framework that contains a rich set of high-performance components. These components automate common communication software tasks such as connection establishment, event demultiplexing and event handler dispatching, message routing, dynamic configuration of services, and flexible concurrency control for network services. ACE has been ported to a variety of real-time OS platforms including VxWorks, Solaris, Win32, and most POSIX 1003.1c implementations.

The RT Event Service is currently deployed at McDonnell Douglas (now Boeing) in St. Louis, MO, where it is being used to develop operation flight programs for next-generation avionics systems.


Acknowledgments

This work was funded in part by McDonnell Douglas Aerospace (MDA). We gratefully acknowledge the support and direction of the MDA Principal Investigator, Bryan Doerr. In addition, we would like to thank Seth Widoff for building the Java visualization tool that generated the time lines shown in Section 4.


References

[Aahlad:96] Y. Aahlad, B. Martin, M. Marathe, and C. Lee. ``Asynchronous Notification Among Distributed Objects,'' Proceedings of the 2nd Conference on Object-Oriented Technologies, USENIX , Toronto, Canada, June, 1996.

[Barkley:88] Ronald E. Barkley and T. Paul Lee, ``A Heap-Based Callout Implementation to Meet Real-time Needs,'' Proceedings of the USENIX Summer Conference, June, 1988, pp. 213--222.

[Blair:95] Geoff Coulson, Gordon Blair, Jean-Bernard Stefani, F. Horn, and L. Hazard, ``Supporting the Real-time Requirements of Continuous Media in Open Distributed Processing,'' Computer Networks and ISDN Systems, pages 1231-1246, 1995.

[Gopal:96] R. Gopalakrishnan and Gurudatta M. Parulkar, ``Bringing Real-time Scheduling Theory and Practice Closer for Multimedia Computing,'' appeared in ACM SIGMETRICS Conference, Philadelphia, May 1996.

[Khanna:92] S. Khanna and et. al., ``Realtime Scheduling in SunOS5.0,'' in Proceedings of the USENIX Winter Conference, pp. 375--390, USENIX Association, 1992.

[LiuLayland:73] C. L. Liu and J. W. Layland, ``Scheduling Algorithms for Multiprogramming in a Hard Realtime Environment,'' JACM 20 (1), pages 46-61, 1973.

[Maffeis:95a] Silvano Maffeis, ``Adding Group Communication and Fault-Tolerance to CORBA,'' Proceedings of the 1st USENIX Conference on Object-Oriented Technologies, Monterey, CA, June, 1995.

[OMG:95a] Common Object Request Broker Architecture, OMG, July, 1995.

[OMG:95b] Common Object Services Specification, OMG 95-3-31, 1995

[OMG:97a] OMG document telecom/97-01-03, Notification Service RFP, FrameMaker, PDF, PostScript

[OMG:97b] OMG document page (search for "Notification Service").

[Porat] Compiler Optimization of C++ Virtual Function Calls, Proceedings of the Second USENIX Conference on Object-Oriented Technologies and Systems, Toronto, Canada, June, 1996.

[Rajkumar:95] Ragunathan Rajkumar, Mike Gagliardi, and Lui Sha, " "The Real-Time Publisher/Subscriber Inter-Process Communication Model for Distributed Real-Time Systems: Design and Implementation," First IEEE Real-Time Technology and Applications Symposium, May 1995.

[QuO:97] John A. Zinky and David E. Bakken and Richard Schantz, ``Architectural Support for Quality of Service for CORBA Objects,'' Theory and Practice of Object Systems, Volume 3, No. 1, 1997.

[RMA_Handbook:93] Mark H. Klein, Thomas Ralya, Bill Pollak, Ray Obenza, and Michael González Harbour, ``A Practitioner's Handbook for Real-time Analysis: Guide to Rate Monotonic Analysis for Real-time Systems,'' Kluwer Academic Publishers, 1993.

[Satoh:95] Ichiro Satoh and Mario Tokoro, ``Time and Asynchrony in Interactions among Distributed Real-Time Objects,'' Proceedings of 9th European Conference on Object-Oriented Programming, August 1995.

[Schmidt:94] Douglas C. Schmidt ``ACE: an Object-Oriented Framework for Developing Distributed Applications,'' Proceedings of the 6th USENIX C++ Technical Conference, Cambridge, MA, April, 1994.

[Schmidt:96] Aniruddha Gokhale and Douglas C. Schmidt, ``Performance of the CORBA Dynamic Invocation Interface over ATM Networks,'' IEEE GLOBECOM, London, England, November, 1996.

[Schmidt:97] Douglas C. Schmidt, Aniruddha Gokhale, Tim Harrison, and Guru Parulkar, ``A High-performance Endsystem Architecture for Real-time CORBA,'' IEEE Communications Magazine, February, 1997.

[Schmidt:RFI] Douglas C. Schmidt, David L. Levine, and Timothy H. Harrison, ``An ORB Endsystem Architecture for Hard Real-Time Scheduling,'' response to the OMG RFI ORBOS/96-09-02, February, 1997.

[Schmidt:97b] Douglas C. Schmidt and Steve Vinoski, "Object Interconnections: Overcoming Drawbacks in the OMG Events Service" C++ Report, June, 1997.

[ShaLehoczkyRamamritham:92] Lui Sha, Ragunathan Rajkumar, John Lehoczky, and Krithi Ramamritham, ``Mode Change Protocols for Priority-Driven Preemptive Scheduling,'' J. Real-Time Systems, Vol. 1, 1989, pp. 243-264, Reprinted in John A. Stankovic and Krithi Ramamritham, Advances in Real-Time Systems, IEEE Computer Society Press, 1992.

[Stefani:96] Jean-Bernard Stefani et al., ``Requirements for a Real-time ORB.'' ReTINA Technical Report, 1996.

[Tokuda:90] Tokuda, H. and Nakajima, T. and Rao, P., ``Real-Time Mach: Towards Predictable Real-time Systems,'' USENIX Mach Workshop," 1990.

[Zhang:90b] Lixia Zhang, ``VirtualClock: A New Traffic Control Algorithm for Packet Switched Networks,'' Proceedings of the Symposium on Communications Architectures and Protocols (SIGCOMM), 1990.

[Vinoski:97] Steve Vinoski, CORBA: Integrating Diverse Applications Within Distributed Heterogeneous Environments, IEEE Communications Magazine, February, 1997.

[Gamma:95] Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides, "Design Patterns: Elements of Reusable Software Architecture", Addison-Wesley, 1995.

[Jensen:97].

[Schmidt:94b] Douglas C. Schmidt, ASX: an Object-Oriented Framework for Developing Distributed Applications, 6th USENIX C++ Conference, April 1994.