Dr. Dobb's Journal December 1999
An up-and-coming trend in the real-time and embedded development environments is the move toward object technology. While object technology offers improved abstraction and encapsulation mechanisms, better reuse, and far better scalability over traditional structured methods, questions arise when applying this technology to designing and implementing predictable real-time systems. Some of the design issues to consider to get predictable real-time and embedded-system designs are the concurrency model, data sharing and task synchronization, and capturing and testing the timeliness of systems.
In the Rapid Object Oriented Process for Embedded Systems (ROPES) process model, the concurrency is specified in architectural design. In this article, we'll discusses the appropriate ways in the Unified Modeling Language (UML) for capturing concurrency models and associated parameters. We then discuss hard- and soft-schedulability analysis using Rate Monotonic Analysis (RMA) and queuing theories. Object model examples are provided to illustrate the pedagogical points of the actual application of these techniques to the construction of real-time and embedded systems.
An important aspect of embedded computing is the interaction with the external environment. In addition to logical correctness of computations, which is the main focus in desktop computing, embedded devices have various timing requirements that must be met by the deployed system. The nature of the timing requirements varies widely depending on the specific embedded device.
The metrics for real-time systems include:
As a result of strong application demand, established theories in the field of real-time systems, developed and published over a number of years, are becoming commercially available solutions. We apply one of the key theories -- Rate Monotonic Analysis -- to an example later in this article.
Consider the example of a Reaction Controller (RC) used to control the temperature within a reactor. Figure 1 represents the high-level deployment diagram. This system is responsible for responding to one process input (temperature) within the reactor. Handling multiple process inputs can be achieved using the same principles outlined here.
The temperature needs to be sampled, digitized, and filtered using a smoothing filter, and converted to engineering units suitable for further computation. The system also monitors an emergency shutdown switch, which is operated manually. A digital control action to shut down the reaction must be initiated for the following conditions within the specified times:
With UML, application requirements and design are represented at a high level using class models, use-case models, and state/activity diagrams.
Classes form the fundamental structural unit of object-oriented systems. A class is, roughly speaking, the type of an object, just as int is the type of the object "-35." Classes bind together data (represented as attributes) with operations that act on that data. The class diagrams identify the classes themselves and their arrangements into collaborations (via association relations among them) and into taxonomic hierarchies (via generalization relations among them). Figure 2 shows a class diagram for our reactive controller example.
Use-case diagrams represent the interaction of a system and/or its components with the external environment or other subsystems. The objective is to identify the external interfaces clearly. The use- case diagram looks like Figure 3. There is no direct, obvious mapping of the use- case model to the class model. In general, a use-case is realized by a collaboration of objects working together. This is complicated by the fact that an object can participate in multiple collaborations.
The ovals are the use-cases -- chunks of functionality visible to one or more actors that do not reveal or imply the internal structure necessary to implement that functionality. Actors are objects that are outside the scope of the system but that interact with the system. Behavioral models, particularly sequence diagrams, are used to elaborate the details of the system-actor interaction.
UML provides different ways to represent behavior. The behavior of reactive classes are modeled using statecharts, a visual formalism originated by David Harel. A state is a condition of existence of an object (or, more generally, of a UML metaclass, called a "classifier") that persists for a significant period of time. An object transitions among states in response to received events (occurrences in time and space that are of interest to the object). Transitions are shown by directed arcs connecting the states. Statecharts also include the ability to nest states (deal with states at multiple levels of abstraction) and to divide the behavior of an object up into independent regions called "and-states" (and-states are separated by dashed lines). Figure 4 is a statechart for the Sensor class of the control example.
Behavior of collaborations may be defined by statecharts associated with the use-case or, more commonly, scenarios shown by sequence diagrams. Figure 5 is an example sequence diagram.
Temporal models represent the system timing characteristics. Examples of such characteristics are: threads and their execution times; network messages and their propagation times; and resource and sharing requirements that have direct impact on the latencies.
The objective of temporal modeling of real-time systems is to present a consistent view of the system design such that its timing predictability can be readily determined using efficient and proven scientific techniques. These techniques include mathematical methods based upon RMA for analyzing the worst-case timing behavior of the system, and discrete-event simulation for determining the average-case behavior of the system.
A combination of these techniques presents a methodology that can be used to capture both the hardware and software characteristics of distributed real-time systems, analyze and predict the worst-case timing behavior of the system using RMA, and study the average-case behavior of the system using discrete-event simulation techniques.
The RC system is specified from the point of view of its external interfaces. A number of timing requirements are identified explicitly. The first three can be considered hard real-time requirements, because any single failure to meet any of these would result in the system failing in a potentially spectacular fashion. The remaining requirements may be considered "soft" because occasionally missing the specified requirement by a small amount is unlikely to have severe consequences.
Figure 3 shows how the requirements for the RC system might be shown on a UML use-case diagram. Figure 5 shows how the interactions of the system with the actors is depicted with a sequence diagram. The instance lines map one-to-one with the structural pieces on the use- case diagram.
Figure 5 shows messages flowing between the actors and the system, with two message pairs annotated with timing constraints. The first message pair shows the time the temperature messages from the Reactor Chamber to the System is 80 ms (required to meet the 125 Hz waveform); the second shows the end-to-end requirement that when the temperature exceeds 400 degrees C, an alarm is activated to the user within 250 ms. Because the temperature is sampled periodically at 125 Hz, the worst-case condition occurs when the temperature jumps suddenly just following a sample. Since this is 80 ms in the worst case, there are 170 ms remaining in which to process the sample, identify the alarm condition, and enunciate the alarm to the user.
Figure 2 shows a class model. The Channel Architectural Design Pattern (also known as the Pipe and Filter Pattern) is one in which data is sequentially transformed by a series of program elements. It is used as an architectural structure to encapsulate the classes together. The high-level timing requirement for alarming, identified in Figure 5, is partitioned into a sequence of class operations. Each operation in the sequence is given a time budget that becomes one of that operations unit test criteria. In Figure 2, only two threads are identified, each corresponding to a channel. (The heavy lines are the graphical icon defined in UML for the active class stereotype.) Of interest here is the SensorChannel active class. The sensor data must move through the collaborating objects to the ClosedLoopController, which has the responsibility for identifying the alarm condition and raising it. Figure 6 shows the sequence of operation calls and the time budgets allocated to the operations. The time budgets must also include the maximum blocking time.
In our Reaction Controller example, the temporal model is described in terms of the hardware and software configuration; see Figure 7. Hardware configuration defines the resources, their properties, and connectivity; software configuration describes the temporal model using concepts described in A Practitioner's Handbook for Real-Time Analysis, by Mark H. Klein, et al. (Kluwer Academic Publishers). This model uses Resources, Events, and Actions, which can potentially be UML stereotypes. The focus of the model is on describing the tasking and communication/synchronization structure of entities that consume the (processor and network) resources.
Resources represent elementary (typically, hardware) objects on which actions execute. A resource can be a physical resource (a processor, network element, backplane, and the like) or a logical resource (a buffer, semaphore, or shared memory).
Threads of execution are defined by an Event, followed by a chain of Actions, called "response." Each Action represents a single, sequential, executable segment of code (or the transmission of a data packet) that requires one physical resource (processor or network) and zero or more logical resources.
Events arrive (periodically or aperiodically) and initiate scheduling of a sequence of actions on a single resource. On a single CPU resource, these represent the arrival or ready state of a thread or process; they may also represent the arrival of an interrupt, in response to which a sequence of actions is initiated. In addition to causal events, you can also define nonintrusive, trace events to describe the flow of data through the system.
An important benefit of temporal modeling is the ability to derive design parameters for scheduling and to guarantee predictability. Scheduling deals with predictable management of a processing (or network) resource among multiple threads (or transmitting stations). Many real-time operating systems (RTOS) and other commercial operating systems support preemptive fixed priority scheduling. The Controller Area Network Bus (CanBus) also uses priority-based arbitration scheme to ensure predictability. The assignment and management of the fixed priorities is an application design issue. Priorities have to be chosen to ensure schedulability and stability under overload conditions.
The Rate Monotonic Scheduling (RMS) algorithm specifies a method of assigning the fixed priorities. The algorithm assigns higher priorities to periodic tasks with higher rates. RMS is an optimal static priority scheduling algorithm for independent periodic tasks when task deadlines are at period boundaries. The optimization of RMS is in the sense that if any static priority scheduling algorithm can schedule a set of independent periodic tasks with end of period deadlines, then RMS can also schedule the task set.
A Practitioner's Handbook for Real-Time Analysis: Guide to Rate-Monotonic Analysis for Real-Time Systems, by Mark Klein et al., provides an excellent reference on the subject. Likewise, Doing Hard Time: Developing Real-Time Systems with UML, Objects, Frameworks and Patterns, by one of the authors (Bruce Powel Douglass), provides information on the analyses in an object-oriented context.
Rate Monotonic Analysis (RMA) is a set of mathematical techniques that let you ensure that application timing requirements are being met. The approach is to manage system concurrency and timing constraints at the level of tasking and message passing. In essence, generalized RMS theory guarantees that all tasks will meet your deadlines if the total system utilization of these tasks lies below a known bound, and these tasks are scheduled using appropriate algorithms. This analytic, engineering basis makes real-time systems considerably easier to develop, modify, and maintain.
RMA began with the pioneering work of C.L. Liu and J.W. Layland (see "Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment," JACM, 1973) in which the rate-monotonic algorithm was introduced for scheduling independent periodic tasks. RMS theory has since been generalized to analyze the schedulability of aperiodic tasks with both soft and hard deadlines, interdependent tasks that must synchronize, tasks with deadlines shorter than the periods, tasks with arbitrary deadlines, and single tasks having multiple code segments with different priority assignment. An RMA-based technique allows a task set to meet its critical deadlines even under overload conditions as long as the utilization of the critical tasks is below a schedulability bound. A very efficient iterative fixed-point technique has been developed to determine the schedulability of a set of periodic tasks using any fixed-priority assignment. These techniques find practical applications in today's real-time system development.
RMA is described in detail in A Practitioner's Handbook for Real-Time Analysis. In its simplest form, it states that:
A set of n-independent periodic tasks scheduled by the rate-monotonic algorithm will always meet its deadlines, for all task phasing, if (Ci/Ti)U(n)=n(2(1/n)-1), where Ci = worst-case task execution time of taski, Ti = period of taski, and U(n) = utilization bound for n tasks.
This equation applies to the simple case of independent periodic tasks. Techniques are also presented to represent, model, and analyze many more complex real-time situations including shared resources, jitter requirements, aperiodic tasks, and the like. RMA can also be applied to real-time tasks that need to interact.
An important issue that needs to be addressed when task interactions occur is that of priority inversion. It occurs when a high-priority thread is forced to wait for potentially undetermined amount of time due to a low-priority thread locking a shared resource and other medium- priority threads continuing to execute. As described in "A Conversation with Glenn Reeves" (DDJ, November 1999), this caused problems aboard the Mars Pathfinder. RMA also describes a set of techniques (including priority inheritance protocol) for avoiding the priority inversion problem. Most real-time operating systems support this technique.
The issues of doing temporal modeling with UML are threefold:
In UML, one specifies concurrency by identifying active classes. The active class stereotype (denoted as "<<active>>") indicates that the class functions as the root of a task or thread. Such classes are normally composites of other classes and the active class delegates the functional work to its component parts. A secondary mechanism also exists for the specification of concurrency: statecharts with and- states.
The application concurrency is then specified in terms of these UML language primitives. The concurrency itself is specified via the active classes or statecharts associated with specified classes. The mechanisms for safely sharing data and control and for rendezvous among threads is typically accomplished by adding structural elements (classes) to the class model to represent message queues, named pipes, mutex semaphores, and so on. These structural design-level elements may be added by elaborating and refining the logical class model (in an elaborative development process) or by implementing those design decisions inside a model translator that feeds on the UML model and spits out an executable application. Both approaches have been successfully applied to real-time systems modeling using UML.
Additional information required to be modeled includes:
The book Real-Time UML: Developing Efficient Objects for Embedded Systems (Addison-Wesley, 1998) proposes an approach to capture this information using the standard extensions mechanisms of UML. The numeric information can be captured using UML tagged values. A tagged value is a property-value pair that may be defined by the user.
The appropriate tagged values are:
(These tagged values are implemented in Rhapsody, a UML-compliant design automation tool from I-Logix.) The arrival patterns of the messages can be captured via the stereotypes (specialized forms of existing UML constructs, denoted by the enclosure of << >>) <<periodic>> and <<aperiodic>> (or <<episodic>>). Using these constructs, the required timeliness information can easily be captured in a UML model and then exported to a suitable RMA tool.
RMA global analysis of schedulability with such information is fairly straightforward. First, once the tasks (and, therefore, the <<active>> classes) are identified, you can use the Channel or Recursive Decomposition Patterns to structure the smaller objects as component pieces of the active classes. The Recursive Decomposition Pattern is one in which high-level classes are decomposed into tightly aggregated "part" classes, hidden behind an opaque interface. This decomposition can continue with the part classes until the leaf classes are sufficiently simple to implement. (See "Real-Time Design Patterns," by Bruce Powel Douglass, UML World, March 1999, for more information.) Subsequently, you can determine the call sequence for the action chain within the threads and compute the execution time. Finally, you can apply the RMA equation described earlier to determine the utilization and whether or not the set of tasks can be guaranteed to be schedulable. When multiple interacting tasks are present, it is more efficient to use commercially available tools. Figure 7 shows the computed schedulability result of the RMA analysis, via the "Schedulability" property of the processor.
If the tasks (represented as active classes) are not independent, then the blocking terms must also be determined. This process is the same. The effort involves determining the longest time that a higher priority task can be blocked from execution because a lower priority task owns a required resource. As mentioned earlier, this may be unbounded unless the blocking is bound via a priority inheritance or similar protocol.
Modeling mutual exclusion (blocking) may be done at a couple of levels. The most common approach is to add semaphore objects explicitly to the class model. These may be developed by hand, but more commonly, they are requested from the underlying OS when required. Another approach is to create rendezvous objects and use these to control how the tasks rendezvous. (This approach is more general than simply using operating-system semaphores, but may require more work.) The rendezvous objects may then use a variety of different synchronizing state patterns to detail exactly how the rendezvous should occur. Figure 8 shows an example of what a timing analysis screen looks like.
As embedded real-time systems become more prevalent, temporal modeling needs to be more closely integrated with the object and behavioral models.
A substantial effort in this direction is made by the Object Management Group (OMG) Real-Time Analysis and Design (RTAD) working group, of which we are active participants. This group is working to bring together vendors and users representing the real-time analysis and design communities. Anticipated outcome of this process is a standard and consistent way of modeling and representing primitives to real-time systems utilizing (or extending) UML.
To arrive at this intended outcome, the OMG process requires that one or more Request For Proposals (RFPs) be issued outlining the requirements for the standards and identifying the constraints. OMG member organizations (vendors and end-user organizations alike) then produce responses to the RFPs. Vendor companies responding to the RFPs also implicitly agree to develop and commercialize products incorporating the standard.
The RFP on which the group is currently focused deals with Timeliness and Schedulability modeling. The objective is to identify how UML may be used to achieve the goals of specifying and analyzing timeliness of UML models. Submissions responding to this RFP may show how the existing UML achieves these goals or what new semantic and notational elements ought to be added to UML to simplify temporal modeling. Preference will be given to those proposals that require little or no change to UML. The RFP has been released by the OMG, with submissions due by the spring of 2000. Following that, there is an evaluation and comment period before such submissions are accepted and integrated into the existing UML metamodel.
Douglass, Bruce Powel. Doing Hard Time: Developing Real-Time Systems with UML, Objects, Frameworks, and Patterns. Addison-Wesley, 1999.
-- -- -- . Real-Time UML: Developing Efficient Objects for Embedded Systems, Second Edition. Addison-Wesley, 1999.
-- -- -- . "Real-Time Design Patterns," UML World, March 1999.
Douglass, Harel, and Trakhtenbrot. "Statecharts in Use: Structured Analysis and Object-Orientation," Lectures on Embedded Systems. Rozenberg and Vaandrager, editors. Springer-Verlag, 1998.
Harel, David. "Statecharts: a Visual Formalism for Complex Systems," Science of Computer Programming. (8)1987.
Liu, C.L. and Layland J.W. "Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment," JACM. 1973.
Sha, L., R. Rajkumar, and J.P. Lehoczky. "Priority Inheritance Protocols: An Approach to Real-Time Synchronization," IEEE Transactions on Computers. 1990.
Comments about the web site: firstname.lastname@example.org |