Real Time UML: Advances in the UML for Real-Time Systems (3rd Edition)

In state machines designed by traditional structured methods, the portion of the system exhibiting the state behavior is not clearly defined. Some set of functions and data collaborate together in a way that lends itself to finite state modeling, but generally this set is only vaguely defined. In object-oriented methods, the programmatic unit exhibiting state behavior is clear only Classifiers, such as systems, subsystems, components, classes, and use cases, can define state models, and only instances of those Classifiers can execute state machines.

The two fundamental concepts of statecharts are State and Transition. A State is a condition of existence of an instance that is distinguishable from other such conditions. States that are disjoint are called or-states because the object must be in one such state or another.

Figure 3-2 shows a simple class diagram for a PBX telephone system. We see that Telephones associate with Lines, which in turn associate with Connections and Call Routers. The lower part of the figure shows the statechart for the relatively simple class Telephone.

3.4.1 Basic Statechart Elements

States are shown as rounded rectangles. As mentioned earlier, states are conditions of existence of the class they define. In this case, the instances of the Telephone class may be in the or-state of "On Hook" or "Off Hook." These are or-states because the Telephone must be in one of them but cannot be in both of them. While the Telephone is in the On Hook state, it may be either in an Idle state or in a Incoming Ringing state (because a remote caller is calling). These are also or-states but are nested within the composite state On Hook. When the Telephone is in the On Hook state, it must be in one of these nested substates, and so these nested states are also or-states, but their context is the enclosing composite state.

Nesting of states is a very straightforward idea. If you were at the Embedded Systems Conference^[5] in San Francisco and I called you and asked you if you were in California, you'd say "Yes" because you are in the state of California. If I ask if you were in San Francisco, you might say "Yes, but next week I'll be in LA, so I'll still be in California." What you're saying is that you're in the nested state "San Francisco" now but later you'll be in the nested state "LA." In both cases you'll be in the state of California. Statecharts have a built-in operator IN() (sometimes called IS_IN()) that you can apply to a stateful object, and it will return TRUE if the object is in that state when the operation is invoked. Thus, if the Telephone is in the state of Incoming Ringing, IN(Incoming Ringing) will return TRUE, but so will IN(On Hook). IN(Idle) and IN(Off Hook) will both return FALSE in this case.

^[5] A highly recommended state to be in!

Similar to the On Hook state, the Off Hook state also has nested substates. While the Telephone is Off Hook, it can be in one (at a time) of its nested states it may be in a Dialing, Outgoing Ringing, Busy, or Connected state. Note that when the instance is in the Off Hook state, if a Hang Up event is received, then the object transitions to the On Hook state regardless of which substate of Off Hook was active. This is one of the ways that nested simplifies state machines, because in a "flat" state machine this transition would have to be drawn four times to have the same semantics, one from each of the states nested within Off Hook.

3.4.1.1 State Features

The object may execute actions when a state is entered or exited, when an event is received (although a transition isn't taken), or when a transition is taken. Figure 3-3 shows actions on both state entry and exit for the Ready state. This is shown with the key word entry, followed by a slash (/) and a list of the actions. The actions may be any kind of action defined in the UML call actions (to invoke a method defined in this or another object), event generation, or even the execution of a primitive action statement such as ++x. Entry actions are executed whenever the Ready state is entered, regardless of which transition path was taken to get there, whether it is the transition invoked by the event evToReady or the transition-to-self invoked by the event evRedo. The Ready state also has exit actions that are executed whenever the object leaves this state regardless of which transition path is taken to exit the state. The syntax is the same as for entry actions except for the key word exit.

Notice in Figure 3-2 that the associated Line object is notified when the phone transitions from the Off Hook to the On Hook state by the generation of a DisconnectSignal event. This action is executed whenever the object leaves the Off Hook state regardless of which transition path is taken. Note that transitions among the internal nested states of Off Hook don't cause this action to execute because the object doesn't leave the enclosing composite state Off Hook until it transitions to the On Hook state.

Internal transitions are similar to "transitions to self" that is, transitions that begin and end on the same state. However, with a transition to self, both the exit and entry actions are performed in addition to the actions specified on the transition itself. In the case of the transition to self initiated by the event evRedo in Figure 3-3, the order of execution of actions is

• Exit actions, such as x; y = cos(sqrt(x))

• Transition actions, such as cout << "redoing..." << endl

• Entry actions, such as ++x; y = foo(x^2)

An internal transition executes neither the exit nor the entry actions of the state; in response to the specified event, it executes only the particular actions identified for the internal transition. In Figure 3-3, state Ready has two internal transitions, one of the event keyPress and another on the event knobTurn. If either of these events occur when the object is in that state, then only their respective actions are performed, not the entry and exit actions for the state.

The activities (and their nested actions) defined for state entry or exit, or specified on transitions, are simple run-to-completion behaviors. States may also specify do activities, as discussed in the previous section. Such activities are not run-to completion; in fact, when such an activity is executing in a state and the object receives an incoming event that is processed while in that state, the activity aborts and the specified transition is taken. Do activities are specified with the syntax

do activity-name

where activity-name is the name of the activity to be executed. Such activities may be only specified within states and begin after the completion of that state's entry actions. In practice, activities are only rarely used in statecharts, and most of the primitive behavior executed by a statechart is expressed in various actions.

Sometimes an object may be in a state where processing an event would be inappropriate, but you'd like that object to remember that the event occurred and process once it transitions to the next state. The defer clause allows you to specify exactly that. Following the key word defer is a list of events to be deferred. The semantics of the defer clause are that, should one of the deferred events occur, it will not be processed but it will be remembered. As long as the object transitions to states where that event is in a defer clause, the event will continue to be remembered. As soon as the object transitions to state where the event is no longer deferred then it will be processed; that is, it will either fire a transition, fire an internal transition, or be discarded.

3.4.1.2 Transitions

Transitions are directed arcs beginning at the starting state and finishing at the target state. Transitions usually have named event triggers optionally followed by actions (i.e., executable statements or operations) that are executed when the transition is taken. The event signature for a transition is of the form

event-name '(' parameter-list ')' '[' guard-expression ']' '/' action-list

All of these fields are optional. A transition without an event signature fires as soon as the state is entered (i.e., its entry actions have completed) or, if there are do activities defined within the state, as soon as those activities complete. That having been said, most transitions do specify at least the event-name. Table 3-1 details the fields of the event signature.

3.4.1.3 Events

The UML defines four kinds of events:

• SignalEvent: An event associated with a Signal. A Signal is a specification of an asynchronous communication, so a SignalEvent is an event associated with an asynchronously received signal.

• CallEvent: An event associated with a Call. A Call is a specification of a synchronous communication, so a CallEvent allows one object to affect the state of another by invoking one of its methods directly.

• TimeEvent: An event associated with the passage of time, usually indicated with either tm(<duration>) or after(<duration>). Almost all TimeEvents are relative time; that is, they specify that the event will occur after the object has been in the specified state for at least <duration> time units. If the object leaves that state before the timeout has elapsed, then the logical timer associated with that duration disappears without creating the timeout event.

• ChangeEvent: An event associated with the change in value for an attribute. It is rarely used in software applications; however, when a state attribute is memory mapped onto a piece of hardware, it can be used to indicate that the memory address changed value.

Events may specify formal parameter lists, meaning that events may carry actual parameters. In Figure 3-2, for example, we could have show the digit event pass a value indicating which key was pressed, such as 0 or #, by using the transition

digit(key: keyType)/ show(key)

Some tools use alternative notations, such as not referring explicitly to the parameter in the parameter list but using a special pointer called params to point to the passed parameters. In this case, the full transition might be something like this:

digit/show(params->key)

In either case, the action show accepts the parameter key and displays it on the screen. In order to generate this event from another object, you might use a helper macro in a tool such as Rhapsody with

GEN(digit(EnterKey))

where EnterKey is of the same type as params->key. Alternatively, if the event is synchronous, you might just a method on the object to send a CallEvent, as in

myTelephone->digit(key)

which dereferences a pointer called myTelephone to an instance of class Telephone, and calls a method called digit passing the appropriate parameter.

Sometimes a transition will appear without a named event in its signature. This is called an anonymous transition or a completion event. Such a transition fires when the predecessor state is entered; that is, when the state's entry actions have completed and the activities, if any, have completed. If there are no activities defined within the state, then the anonymous transition fires as soon as the state's entry actions have completed. If there are activities, and another event that fires another transition comes in before the activities complete, then the activities are aborted and the named transition is taken. This is the primary difference between actions (which are run-to-completion) and activities (which are interruptible).

Some examples of legal transitions are

1. E1

2. E1 [x < mySensor->Value)]

3. E1 (x: float) / y = filter(x*100)

4. E1 (x: float, y:long) [abs(x) > abs(y^2) > 0] / result = x / y

5. [mySensor->IS_IN(Has_Data)] / value =filter( mySensor->get Value())

6. / y = sqrt(x^2 + y^2); z = 2*y - 3

The first transition specifies only an event. The second specifies an event with a guard. The third passes a parameter and then uses the value of that parameter in an assignment computation. The fourth combines a named event with two passed parameters, a guard, and an action. The fifth has no named event trigger but does have a guard and an action. The sixth just specifies an action list (containing two actions) but not a named event or a guard.

3.4.1.4 Guards

The guard expression is a Boolean expression, enclosed between square brackets, that must evaluate to either true or false. Care must be taken to ensure that guards do not have any side effects, such as changing an attribute's value. Typical guards will specify invariants that should be true before a transition is taken, such as [x>0] (returning TRUE that the object's attribute x has a value of greater than zero) or [myLine->IS_IN(Idle)] (TRUE when the associated object referred to via the myLine pointer is currently in the Idle state). Guards are a very simple way to ensure preconditions are met, such as that the door is closed before powering the emitter in a microwave oven (an important consideration for repeat business!).

3.4.1.5 Action Execution Order

Actions do the real work of a state machine. The state machine is important because it defines the possible set of sequences of action executions under a (possible large) set of circumstances. Nevertheless, the actions are where the object actually does something interesting in the real world.

The order of execution of actions is important. The basic rule is exit-transition-entry. That is, the exit action of the predecessor state is executed first, followed by the actions on the transition, followed by the entry actions of the subsequent state. In the presence of nesting, exit actions are executed in an inner-to-outer fashion, while entry actions are executed from outer-to-inner. In the example of Figure 3-2, when taking the transition "pick up" while the object is in the state IncomingRinging the order of action execution would be

1. IncomingRinging exit actions

2. On Hook exit actions

3. Pick up transition actions

4. Off Hook entry actions

5. Connected entry actions

3.4.2 And-States

We have already discussed the semantics of or-states; if A and B define the set of possible or-states of a specific context, then the object must be either A or B at all times. It cannot be in both and it cannot be in neither. The UML also has the notion of and-states to model conditions that must be simultaneously true and independent.

Statecharts provide a very clear yet succinct representation of and-states, as shown in the simple Microwave Oven object example in Figure 3-4. This object exhibits four independent state aspects cooking, timing, display, and door monitoring. Obviously, for safe and effective operation, all these activities must go on simultaneously. These independent state aspects are called and-states and are separated with dashed lines. The and-states are often referred to as regions, or orthogonal regions. And-states are always substates of an enclosing composite state.

Each of the and-states is named and operates independently of the others, as if they are concurrent and in an important sense they are. What do we mean by concurrent in this case? Basically the same as in other cases that the processing within an and-state proceeds independently from processing in other, peer and-states, and you cannot in principle predict which and-state will process an event first. Each active and-state basically receives its own personal copy of any event received by the object and is free to independently process or discard that event, as appropriate. This means (and we'll see why this is important in a moment), that multiple and-states may process the same event when an event is received by the object.

The complete "state" of the object is the cross-product of all of its currently active and-states. The Microwave Oven may be, for example, in the state of [Emitting, DisplayingCookTime, DoorClosed, and Waiting ForTick], or it may be in the state of [EmitterIdle, DisplayingTimeOf Day, DoorOpen, and WaitingForTick]. And-states make the specification of independent aspects of a stateful object much more parsimonious as compared with normally Mealy-Moore (M&M) state machines. M&Ms don't have the notion of and-states and so must display the state space as an explicit enumerated list, giving rise to states named "Emitting-DisplayingCookTime-DoorClosed-WaitingForTick," "NotEmitting-DisplayingCookTime-DoorClosed-WaitingForTick," and so on. This is obviously a long list, making the creation of the state diagram in Figure 3-4 with M&Ms a daunting task.^[6]

^[6] Exercise left to the reader.

The addition of and-states to your state-modeling paradigm is very powerful, but it also creates new questions. For example, how do I synchronize and communicate among peer and-states when necessary?

There are four primary ways that and-states can communicate, synchronize, and collaborate. Remember, first of all, that it is the object and not the state that receives incoming events. When an object receives an event, it is acted upon by all of its active and-states and that action may be to take a transition, execute an "internal transition" (execute a set of actions without changing state), or discard it. It is as if each active and-state receives its own copy of the incoming event to do with as it pleases, independently of all the other and-states. This is a kind of contained "broadcast" in that all active and-states receive each event as it is received by the object.

The second means for and-state collaboration are propagated events. Propagated events are events that are sent as the result of a transition being taken in one and-state or object. Remember, the UML defines two different kinds of actions that can be used to create such events Send Actions (resulting in SignalEvents) and CallActions (resulting in CallEvents). Call actions must be used carefully as propagated events as they execute in the same run-to-completion step as the initiating event.

Another means for and-state collaboration is with the IS_IN( ),^[7] which returns TRUE if another and-state is currently in the specified nested state. This allows for and-state coordination. In Figure 3-4, we see the IS_IN() operator used in guards; for example in the Cooking region the evCook transition is protected with an IS_IN(DoorClosed) guard to ensure that we don't cook the chiefs!

^[7] IN( ) is another common form for this operator.

3.4.3 Pseudostates

The UML defines a number of different pseudostates, as shown in Figure 3-5. Pseudostates indicate the use of special semantics; they are not in any way states, but they are used as annotations of some defined special state chart behaviors. The UML 2.0 has removed a few of the lesser used pseudostates, such as the synch pseudostate, and replaced the stub pseudostate with the entry point and exit point pseudostates.

Briefly, these pseudostates are as follows:

• Initial or default: Within a composite state context, the initial pseudostate indicates which substate is initially entered as a default. The initial pseudostate may be overridden, either by transitioning directly to a different nested state or with the history pseudostate.

• Terminal or final: The final state indicates that the enclosing composite state is terminated. If the final state appears in the outermost level of nesting, it indicates that the object no longer accepts any event, usually because it is about to be destroyed.

• Junction: Vertices used to join together multiple transitions, or to divide a transition into a set of sequential transition segments. Regardless of the number of transition segments connected, they all execute in a single run-to-completion step.

• Branch or conditional:^[8] The branch pseudostate indicates a set of possible target or-states, one of which will be selected on the basis of a guarding condition. The branch pseudostate is nothing more than a junction with guards on exiting transition segments. However, it was called out in previous versions of the UML with a special icon (usually a ©) and is still indicated using an independent icon by many modeling tools so it is separately identified here.

  ^[8] This pseudostate was removed in the 1.3 revision of the UML, after it was noted to be just a kind of the junction pseudostate. However, since it is still widely used in tools, I have continued to use it here.

• Choice point: A choice point is a kind of junction that executes its action list before going on to the next transition segment. This allows actions bound to the first transition segment to execute prior to the evaluation of subsequent guards.

• Shallow history: This pseudostate indicates that the default state of a composite state is the last state visited of that composite state, not including nested substates.

• Deep history: This pseudostate indicates that the default state of a composite is the last state visited of that composite state, including substates nested arbitrarily deeply.

• Join: A connector that joins multiple incoming transitions from peer and-states into a single transition. This is not the same as a junction. (And-states are discussed in Section 3.4.2.)

• Fork: A connector that branches into multiple transitions, each entering a different and-state, from a single input transition. This is not the same as a branch because in a branch only a single transition activates; in a fork, all outgoing transition segments activate.

• Entry point: An entry point is used in conjunction with a composite state to serve as a connector between its nested states and its peer states. It is usually not used unless the nested states are hidden and put on a separate state diagram.

• Exit point: An entry point is used in conjunction with a composite state to serve as a connector between its nested states and its peer states. It is usually not used unless the nested states are hidden and put on a separate state diagram.

3.4.3.1 Initial Pseudostate

Whenever a class defines a statechart there is always the question of what state the object starts in when it is created. This is indicated with the initial (or default) pseudostates. This special annotation is a transition with a ball at one end. In Figure 3-2, the Telephone enters the state On Hook when it is first created. Because composite states have states nested inside, it must also contain an indication as to which nested state is the default (Idle, in this case; Dialing, in the case of the Off Hook state). When a transition terminates on the composite state, the default pseudostates inside the composite state indicate which nested state is entered initially. The default nested state can be bypassed by drawing a transition directly to a different nested state if desired, as illustrated by the transition from the Incoming_Ringing state to the Connected state.

To be well formed, a statechart must have an initial pseudostate to specify the starting state when an object is created. Additionally, each composite state must indicate the initial pseudostate for its nested states, and each and-state region must have an initial pseudostate as well.

3.4.3.2 Branches and Junctions

Transitions may be broken up into segments with the junction pseudostate. A complete transition path may have only a single event associated with triggering it, but they may join, to share actions. Junctions may have multiple incoming transitions as illustrated in junction pseudostate 1 in Figure 3-6. Both transitions share the common branch of the exiting transition. Junction pseudostates may also have multiple exiting transitions, provided they are all guarded, as shown with junction pseudostate 2 in the same figure. The guard selects which transition path will be taken. It is important to note that if all the guards evaluate to FALSE, then no transition will be taken from the originating state the state machine must have a complete, valid path to a subsequent state before an event may trigger a transition. Note that in the figure, if state 1 is the current state and the event ev2 occurs, at least one of the guards exiting junction pseudostate 2 must evaluate to TRUE or the event will be discarded without executing any action; that is, before any actions will be taken, z must either be greater than 10 or less than 1.

Older UML use the conditional pseudostate (©) to indicate conditional branching; however, in later revisions of the UML, the junction pseudostate included the conditional pseudostate because any junction may have multiple guarded exiting transitions. The figure shows a typical use of the conditional pseudostate as well as a semantic trap. Can you spot it?

The question is, starting in state 0, when the event ev1 is received, to what state will the object transition? Most people think (incorrectly) that the object will transition to state 2 because of the preincrement of x in the event signature action list. However, the guard is evaluated prior to the execution of any actions; therefore the else clause (which evaluates to TRUE when all the other exiting branches all evaluate to FALSE) is taken because at the time of evaluation of the guards, the value of the attribute x is zero.

Another interesting question is what happens if multiple guards evaluate to true. The UML specifies that one of the true branches will be taken, but which one is indeterminate? After all, whichever branch is taken will have a TRUE guard condition. Normally, when multiple exiting transitions fire, it indicates a modeling error, and the model is said to be ill-formed. Don't let this happen to you!^[9]

^[9] In the general case, this is very difficult to automatically check for, because the guards may invoke operations that have nested operations. Therefore, modeling tools don't usually check for this kind of error.

3.4.3.3 Choice Points

Because actions are only executed if a transition is taken, they are not executed before the guards are evaluated. This is because the guards must be evaluated prior to the execution of the actions. Sometimes this is an inconvenient thing to do. In these cases, you should use choice points instead. A choice point is a specialized form of junction used when the result of an action executed during a transition is to be used in a guard. In this case, the actions on the initial segment of a compound transition are executed before checking the guard. The notation for a choice point is a diamond, but otherwise it looks like a conditional pseudostate.

Choice points are dangerous in use because the actions are executed before the guards are evaluated. If the guards should all evaluate to FALSE, then the object is no longer in a valid state. Because of the likelihood of this happening, I recommend that you not use choice points, but use junctions (or conditionals) instead. If you stick with junctions, then the object will always remain in a valid state when the guards evaluate to FALSE.

3.4.3.4 History

As we have seen, composite states are decomposed into nested states. The default nested state for a composite state is indicated with an initial pseudostate. When the composite state is exited and later reentered, the same nested state is again reentered. But what if the semantics you want are not to reenter the same nested state but to instead reenter the last active nested state?

The statechart answer is history. The history pseudostate is a letter "H" in a circle. Figure 3-7 shows the different aspects of the history pseudostate. To be activated, the transition must terminate on it, as with the transition from state 0, labeled e1, and the transition labeled e2 from state 1. Both of these transitions terminate on the history pseudostate. The transition labeled e0 from state 0 does not, so the normal default (to nested state a1) is activated whenever that transition is taken. However, if the active state is state a2 when transition e1 is taken, followed by transition labeled e2, then, the object reenters state a2. Of course, when the object is in state a2, it must also be in one of its nested states. Because of the kind of history used for composite state A, the default nested state for state a2 will always be reentered even if the last active nested state was state a24.

There is another kind of history as well deep history. Deep history differs in that while shallow history only applies to the immediate level of nested and no deeper, deep history applies through all levels of nesting no matter how deep. Deep history is indicated with a circumscribed H*, and is shown in composite state B. When the current state is state b23, and the object receives an event f1 (taking it to the default state of composite state A) followed by an event f0, the object reenters the state b23. As before, transitions that do not terminate on the history pseudostate don't activate the history semantics.

3.4.3.5 Forks and Joins

When a composite state with and-state regions is entered, the default state for each of the regions is entered. But what if you want to bypass those default states under some circumstances? As with many of the other pseudostates, there are special pseudostates for explicitly doing nondefault behavior. In the case of and-states, these are the fork and join pseudostates.

If you want to bypass the default for a normal (or-) composite state you simply draw the transition directly to the desired nested state. However, in the case of entering and-state regions you have multiple branches you'd need to specify. That is exactly what the fork pseudo state does. Unlike with or-states, where multiple branches indicate selection (since only one branch can be taken), the multiple transitions exiting a fork indicate concurrency, at least in the logical sense, because all branches are taken, essentially at the same time. Figure 3-8 shows a fork in use. The default nested states are the InitTool and the InitArm states, and these states are entered when the transition labeled evGo is taken. However, when the transition labeled evContCmd is taken, then these defaults are bypassed and the states orientTool and calculatingPath are taken instead.

Conversely, the evError transition exits the Moving state, regardless of which of the states nested within the and-state regions are active. If you want to specify a single nested state in one and-state and the other and-states are "don't cares," then you can initiate a transition from the (single) desired substate, as is done with the evMovementDetect transition leaving the moveArm state; it doesn't matter what nested state is active in the other and-state, when moveArm is active and the object receives the evMovementDetect event, the transition is taken. When you want to specify multiple predecessor states, then you must specify which ones you mean this means joining multiple branches. That is the purpose of the join pseudostate. In the figure, both positionTool and MoveArm must be active for the transition labeled evDone to be taken. If either of those states is not active when that event is received, then the event is simply discarded. The join can only be initiated by a single event; that is, you cannot join transitions resulting from the receipt of multiple events.

3.4.3.6 Submachines, Entry, and Exit Points

Previously, we've seen that or-states and and-states can be nested within other states. In most cases, the entire state machine will be specified on a single statechart, using whatever level of nesting is called for. In large, complex statecharts, this can lead to diagrams that are difficult to decipher. For this reason, the internal state decomposition of a superstate can be defined on a separate statechart called a submachine. Figure 3-9a shows the same state machine from Figure 3-2, now hiding the internal structures of the OnHook and OffHook composite states. As long as transitions initiate or terminate on the border of the composite state, the defaults are used. For transitions terminating on the composite state, the initial state will be entered; for transitions initiating on the composite state, the transition will be taken regardless of what nested state of the composite is currently active. But what if a transition initiates only from a specific nested or terminates on a nondefault state? How can this be shown?

The answer is to use entry and exit points. These are the circles on the state boundaries shown in Figure 3-9. The empty circles are entry points they indicate that a transition terminating (from outside the composite state) on the entry point will be delegated to a specific, but not-shown state inside the composite. The circles containing a cross are called exit points. A transition originating from that pseudostate arises from some specific, but not-shown nested state inside the composite.

Figures 3-9b and 3-9c show the internals of the composite states from Figure 9-9a. The entry and exit points are explicitly named so they can clearly specify which transition paths they define. I have used the name of the initiating or terminating state in the name of the entry and exit point labels, but any meaningful label may be used.

3.4.4 Inherited State Models

UML 1.x was a bit vague on how to interpret the inheritance of state machines when a stateful class was specialized. UML 2.0 is more precise on this matter. In order to ensure compliance with the Liskov Substitution Principle (that instances of subclasses must be freely substitutable for instances of their superclass) some rules must govern the modifications that can be made to an inherited state model:

• New states and transitions may be freely added in the child class.

• States and transitions defined by the parent cannot be deleted (the subclass must accept all events and messages that can be accepted by the parent).

• Action and activity lists may be changed (actions and activities may be added or removed) for each transition and state.

• Actions and activities may be specialized in the subclass (i.e., actions may be polymorphic).

• Substates may not alter their enclosing superstate (including adding a new one).

• Transitions may be retargeted to different states.

• Orthogonal components may be added to inherited states.

A simple example of inherited state models is provided in Figure 3-10. The class model is shown at the upper left of the figure. The class Blower has a simple on-off state model (shown at the upper right). The evSwitch On transition has a single action in its action list, the function powerMotor(). The Dual Speed Blower class extends the Blower class by adding Low and High speed substates to the On state. Note that the action for the evSwitchOn transition is now changed to the execution of the functions LED(ON) and setPower(LOW). Additionally, the Off state now has an entry action and the action for the evSwitchOff transition has been changed. The Dual Speed Multiheat Blower class continues the specialization by adding three heat settings as an orthogonal component to the Low and High states added by the previous subclass. Also action lists have been changed. Nevertheless, the generalization taxonomy is clear from the statecharts that a Dual Speed Multiheat Blower is still a kind of Dual Speed Blower, and a Dual Speed Blower is, in fact, a kind of Blower.

3.4.5 Ill-Formed Statecharts

A wise man once said that any language rich enough to say all the things you want also provides the ability to state nonsense.^[10] Statecharts are certainly no exception. When a statechart makes a nonsensical statement, we say that it is ill-formed. Figure 3-11 shows some ways in which we can use statecharts to say things we probably didn't mean to say.

^[10] It's one of Douglass's Laws. See [2].

The first thing to notice about the statechart in the figure is that we didn't define the default state for the class. Is it state_0? State_10? Maybe state_7? We also didn't identify the default state in the lower and-state region of state_0.

Less obvious are the two race conditions specified in the and-states. The first is activated by the event e1. In one and-state, the action modifies the attribute x by augmenting it by one; the second multiplies it by three. The answer we get after the event is processed by the object depends on the order of execution of these actions but it is not possible, in principle, to determine what that order is. This is the classic definition of a race condition a situation in which a computational result depends on an execution order, which is inherently unknowable. Not that using the same event in more than one and-state is inappropriate in fact, it is a common way for synchronization of and-states when required. However, care must be taken that race conditions are avoided.

The second race condition is perhaps a bit more obvious. The e6 event causes two things to occur which are mutually exclusive. In the upper and-state region, it causes a transition to the state_1 nested state, while in the lower and-state region it leaves the composite state altogether. While this is obvious bad and not "computable," there are more subtle versions of this. Suppose event evSub is a subclass of event e6 and it is this event that appears on the transition to state_10 in the figure. If an evSub6 occurs, then the state machine is still ill-formed because evSub is a kind of e6; therefore, when evSub6 occurs, all active transitions with e6 event triggers also fire.

At the bottom of the figure we see overlapping guard conditions. In this case, it is obvious that if x has the value 25, that both guards evaluate to TRUE. One could conceive of a tool that would find such overlapping conditions. Nevertheless, finding the general case of overlapping guards is NP-hard. Using simple guards will allow you to detect these conditions more easily.

On the right side of the figure we see a reasonable-looking transition: CoinDrop with an action to add the value of the coin to an attribute called "amount." The problem lies in that the guards subsequent to that event signature use the amount attribute in the guard. What is probably meant is that the updated value of amount should be used in the guard execution; however, what is actually done is that guards are evaluated before any actions are taken. Therefore the value of amount examined is prior to adding in the value of the coin. There are a couple of common solutions to this. One is to use a choice point, although I personally don't recommend it for the reasons discussed previously. Another solution is to use more elaborate guard expressions such as [amount + coin>0], taking into account that it has not yet been augmented. Another solution is to add a state between the CoinDrop transition segment and the guards. This will force the completion of the action before the guards (now exiting the new state) are evaluated.

The last error on the diagram is that transitions with different events enter into a join. A join brings together transition segments from different and-states and must be triggered by a single event. Event responses are handled one at a time, in a run-to-completion fashion. Different events cannot be joined together.

3.4.6 Cardiac Pacemaker Example

A cardiac pacemaker is an excellent example of a system in which most objects use finite state machines. The problem statement below will be developed into a class model that will allow us to see how the various statechart features can be used in a real system.

This short problem statement can be represented by a simple class model, as in Figure 3-12. The pacemaker itself is shown as a structured class containing the three subsystems Communications, PacingEngine, and Power. These subsystems contain the objects that collaborate to do meet the required functionality required of the subsystems.

The Communications subsystem, shown in Figure 3-13, contains instances of various classes that enable it to do its primary communications functionality. The ReedSwitch, CoilDriver, and Communications Manager and associated MessageQueues and Messages form the Communications subsystem. Note that the Communications Manager associates with two MessageQueues one to hold messages waiting to be transmitted, and one to hold messages received via telemetry. The Communications Manager has an association with the PacingEngine subsystem to enable it to send the commands that change the pacing parameters, such as pulse width, pulse amplitude, pacing rate, and operational mode.

The PacingEngine subsystem internal structure is shown in Figure 3-14. This subsystem is straightforward. The Chamber Model defines the basic behavior for pacing a heart chamber, including associations to a PaceOutput object (providing an interface to the stimulation hardware) and a VoltageSensor object (providing an interface to the monitoring hardware). As an aside, the operations shown for the Pace Output and VoltageSensor classes are standard method calls, while the operation shown for the pacing classes (Chamber Model, Atrial Model, and Ventricular Model) are event receptors that show which events are received and processed by instances of the class. This is a bit more obvious on the state machines than on the class diagrams. Note also that the class diagram follows the common idiom of only showing the new operations (or events receptions) defined in the subclass and not those inherited from the superclass. These inherited operations are defined (in the superclass), but not shown in the subclass on the diagram.

A statement about the generalization relationships in the pacing subsystem is in order. The Chamber Model class defines the basic behavioral model for pacing a cardiac chamber so it seems as though the Atrial Model and Ventricular Model ought to be instances of the Chamber Model class rather than different subclasses. If, in fact, the behavior of the two chambers differed only in their context, then a single class Chamber Model would be appropriate. However, we are going to specialize the Chamber Model class in how the two cardiac chambers define their behavior in AVI mode. This will allow us to define the basic behavior in the superclass and specialize it for the two subclasses.

Now that we have seen the structure of the Cardionada pacemaker, let's look at the behavioral model defined with the statecharts. The classes on the class diagram that have a state machine have a small icon in their upper righthand corner. Starting with the Communications Subsystem, we see that the reactive classes are the ReedSwitch, CoilDriver, and CommunicationsManager.

The ReedSwitch has simple on-off state behavior, as we see in Figure 3-15. It propagates events to other classes communication subsystem to enable and disable communications via the GEN() macro specifically the ReedSwitch sends the RS_Close and RS_Open events to both the CoilDriver and CommunicationsGnome.

The CoilDriver class has more elaborate behavior (see Figure 3-16). The default initial state is Disabled. When the Reed Switch closes, it propagates an RS_Close event to the CoilDriver and the CoilDriver enters the Idle substate. The CoilDriver supports half-duplex operation that is, it can either send or receive at any given time, but not both at the same time. In the Idle state, if an incoming pulse on the coil is detected, then it enters the ReceivingMsg state. The CoilDriver starts counting the pulses until it gets a timeout [shown as tm(BIT_TM)]. The number of pulses receives is then decoded into a bit value with the decode() action and then the next bit is retrieved. Once we receive all the bits in a byte, we add the byte into the message we are constructing and we wait for the next byte. At some point, we have received all the bytes [as indicated by the elapse of the timeout tm(MSG_TM)], and we now have a complete message. The message is then sent to the Communications Manager and the CoilDriver returns to the Idle state.

Transmission is begun when the CoilDriver receives a Send event with a message to send from the Communications Manager. The process to send is basically the reverse of the process to receive it. The first byte of the message is extracted, and then each bit, in turn, is extracted and is used to send the appropriate number of pulses out through the Coil.

The Communications Manager oversees the bidirectional communication process for the pacemaker. Figure 3-17 shows that the Communications Manager has four and-states: Receiving, CmdProcessing, MsgSending, and Queuing. These and-states proceed more or less independently except for synchronization points. The Receiving and-state validates messages that it receives from the CoilDriver and then either enqueues it from processing and responds to the programming device with an ACK message (if valid) or discards it and sends a NAK message if not. Validation is done via the isValid operation, which presumably checks the command ID, the message length, and a CRC.

The cmdProcessing state is decomposed into a submachine, which is shown in Figure 3-17. The Dump command tells the pacemaker to start sending the queued messages, while the Set command sets the parameters or mode for the pacing engine.

The PacingEngine is where the pacing behavior occurs (see Figure 3-18). It changes mode only when commanded by the external programmer. When the Communication Manager receives a command to set the pacing mode, it validates the command and, if valid, processes it. The PacingEngine decides how to deal with these Set commands. For example, when a Set command that commands the pacemaker into VVI mode is received, the PacingEngine must send a ToIdle event to the Atrial Model instance and a ToInhibiting event to the Ventricular Model. To enter the AVI mode, the PacingEngine must send toAVI events to both the Atrial Model and Ventricular Model objects.

Most of the pacing behavior is defined in the Chamber Model statechart in Figure 3-19. If the Atrial Model is in the SelfInhibiting state and the Ventricular Model is in the Idle state, the pacemaker is said to be in AAI mode; if the Atrial Model is in the Idle State and the Ventricular model is in the Triggering mode, then the pacemaker is said to be in VVT mode. And if both objects are in the AVI state, then the pacemaker is in the AVI mode.

The next two figures (Figures 3-20 and 3-21) specialize the AVI state using the inherited state model rules given previously. By comparing the two specialized versions of the AVI state, you can see how the two objects communicate to coordinate their state machines. The Atrial Model and the Ventricular Model coordinate their activities by propagating events back and forth to ensure the behavior is correct in the AVI mode. The AVI mode is defined to be when the electrical activity in the ventricle is used to determine whether or not pacing should occur; the pacing is actually performed by stimulating the atrium of the heart. Further, if the ventricle beats on its own fast enough, then the pacing of the atrium should be inhibited.

3.4.7 Protocol State Machines

The state machines we dealt with in the previous section are called behavioral state machines because they specify how instances of a classifier respond to incoming events. There is another use of state machines, which is to define usage protocols for interfaces and ports; such state machines are called protocol state machines because they define the events and allowed sequences of events in usage protocols for classifiers. A protocol state machine defines which operations of a classifier may be called in which state and the pre- and postconditions for the execution of the operations.

As with behavioral state machines, protocol state machines must be "complete" in the sense that all the transitions that can result in the change of state and execution of operations must be captured. On the other hand, operations that do not affect the state machine are not represented on the protocol state machine. The purpose of the protocol state machine, once again, is to formalize the protocol of interaction (i.e., preconditions having to do with sequencing) for the classifier.

Protocol state machines differ from behavioral state machines in the following ways:

• The key word "protocol" is used in the statechart.

• Preconditions and postconditions are shown on the transitions as guards.

• Actions are not permitted.

• States may not have entry or exit actions or activities.

Figure 3-22 shows two examples of protocol state machines for the door management of an elevator.

3.4.8 Activity Diagrams

Activity diagrams in UML 1.x were semantically equivalent to statecharts and shared a common metamodel. In UML 2.0, activity diagrams are given their own semantic basis independent from statecharts. In UML 2.0, there are multiple levels of activity diagrams: basic, intermediate, complete, and so on. The UML 2.0 activity diagrams are (mostly) compatible with the UML 1.x activity diagrams. In practice, the use of activity diagrams as "concurrent flowcharts" remains its most important usage in the real-time and embedded domains. Activity diagrams are usually used to specify the behaviors of operations and use cases and other classifiers. In usage, the difference between activity diagrams and statecharts is that statecharts are used when the classifier progresses primarily from state to state upon receipt of events of interest, whereas activity diagrams are used when the classifier progresses from state to state primarily when the actions done in the predecessor state have completed.

This is primarily because activity diagram semantics are based on the notion of token flow, from Petri nets, where a token contains an object, datum, or locus of control. The activity diagram is said to be in a state (or "node") when that state contains a token. Tokens flow from node to node when the input edges connect to nodes that contain tokens. In the case of simple sequence flow, the transition between them fires when the predecessor node (activity) has completed its work. In the case of a join, there must be tokens in all the predecessor nodes before the subsequent node becomes active. Conversely, with a fork, when the incoming transition fires, a token is placed in all subsequent nodes.

In practice, statecharts are used to model the reactive behavior of classes and use cases, when they proceed via the reception of events. Activity charts are used to model control flow behavior of operations, activities on states (entry, exit, transition, and do activities) and use cases, and less often, classes. Note that entry, exit, and transition activities run according to run-to-completion semantics that is, the object providing the context for these actions will not accept or process any event until those activities, and their nested actions have completed. Do activities are not run-to-completion and may accept events to terminate their execution. The common use of activity diagrams in the real-time and embedded domain is to show computational algorithms.

The model shown in Figure 3-23 shows how an activity diagram can model the behavior of an operation. In this case, the activity receives incoming data SourceID and processes the data into two concurrent flows, emanating from the fork pseudostate. The input data "appears" to the activity diagram on an input activity parameter node (a kind of object node, analogous to an input pin on an action). The computation result appears on an output activity parameter node (analogous to an output pin on an action). One of the concurrent flows initializes the sensor and acquires the data. The other readies the filter. Once this is done, the join then brings together the concurrent flows and filters the data and returns it. Remember that the output flow from the join fires only when control tokens appear on all of its predecessor nodes. This is just a fancy way of saying that it fires only when both threads feeding into it have completed their processing.

Note the use of a "class box" to represent data, whether it is a class or just an ADT (abstract data type). The Datum is shown using the "object in state" notation (the name of the current state shown inside square brackets), making the state of the Datum visible as that datum is processed in the activity. Note also the use of preconditions and postconditions to clarify the processing requirements of the activity.

There are some additional notations available for activity diagrams. In Figure 3-24 we see special symbols that can be shown for event reception. In the example, a Proximity Alert might be created when a beam of light is broken (such as when a human arm crosses its path). In the activity diagram, this event causes the behavior in the interruptible segment (indicated with the dashed rounded rectangle) to abort, and the control path to the Emergency Stop activity is taken. The use of explicit "interrupting edges" is an important departure from UML 1.x activity diagrams; in its earlier incarnation, UML allowed a flow on an activity diagram to be triggered by an event.

Swim lanes define partitions in the activity diagram that can be bound to objects or object roles. This provides activity diagrams with the ability to represent interactions of objects during the execution of the activity flow. Swim lanes enable the depiction of interactions of multiple objects during the execution of an algorithm. In addition, activity states themselves can also be decomposed on the same or on different diagrams. This is crucial for the scalability of the notation to model complex algorithms. The official notation used to indicate that an activity is decomposed on a separate diagram is an inverted three-pronged fork.