UML Statecharts -

UML Statecharts

Here is an examination of statechart development using the Unified Modeling Language. The author describes the event metamodel in the UML and some of the more interesting features of statecharts, including nested states and orthogonal regions.

PDF of original article

One of the crucial aspects of the Unified Modeling Language (UML) that makes it so valuable for real-time and embedded systems is its heavy reliance on and support for finite state machines. State machines are critical in the construction of executable models that can effectively react to incoming events in a timely fashion. The UML state machine model represents the current state of the art in state machine theory and notation, all based on David Harel's statecharts.

In the context of an object-oriented design language, such as the UML, the “things” that have state behavior are objects. Objects have both structure and behavior. Object behavior may be viewed solely within the context of individual objects, or in the larger context of object collaborations. Objects work together in these collaborations to implement (realize, in UML-speak) higher-order behaviors defined by use cases. I find it useful to partition behavior into three types: simple, state, or continuous. These different types of behavior are distinguished on the basis of how they treat the object's history over time. Simple behavior does not depend on the history of the object whatsoever. State behavior divides up the behavioral space of the object into nonoverlapping chunks called states. Continuous behavior depends on the object's time history, but does so in ways that cannot be easily divided into disjoint states.

Both state and continuous behavior constrain the overall behavior of their context. For example, an object might have five different states, each of which accepts a different set of events, performs different actions, and can reach a different set of subsequent states. Such an object might have 15 different operations defined, suitably constrained by the object's state machine, limiting both the sequence of those operations and the conditions under which they may be executed. This can vastly simplify the overall dynamic behavior of the object by providing a set of rules which govern how and when those operations can be invoked. Similarly, a continuous object, such as one that might implement a feedback control system, operates by applying differential equations (in their discrete formulation as difference equations). The equations, which map somehow to operations defined on the class, execute in a particular sequence in response to incoming data and previous results. This again results in simpler behaviorthat is an equally rich but unconstrained application of those operations.

State machines are the primary means within the UML for capturing complex dynamic behavior. The UML is a third-generation state-of-the-art object modeling language that defines a comprehensive set of notations, and, more importantly, defines the semantics (meaning) of those language elements. The UML is an inherently discrete language — meaning that it emphasizes discrete representations of dynamic behavior, such as state machines, over continuous representations. Although many object systems do, in fact, perform continuous control functions and do it well, the UML provides special support in the area of finite state machines. In this article, I will explore the underlying semantics and notation of state behavior as defined by the UML.

I'll start off by answering two questions: first, what exactly is a finite state machine, and second, to what kinds of structural pieces of the object model do they apply? It turns out that there are many answers to the first question, using different vocabularies and addressing different concerns. For example, a relatively formal definition follows.

A finite state machine (M ) is an abstract model consisting of:

  • A finite state set (S )
  • A starting state (s 0 )
  • An input alphabet (∑)
  • A mapping function δ = ∑ x SS
  • An input sequence acceptance function
    β = S → {0, 1} such that M = (S , ∑, s 0 , δ , β)

A graph-theoretic definition would define a state machine in terms of nodes and edges. However, I'm more interested in a definition that emphasizes the practical applications of state machines (while keeping in mind that somewhere in the closet, there's a bunch of mathematics if and when I need it). Therefore, I'll use the following definition:

A finite state machine is an abstract machine that defines a finite set of conditions of existence (called “states”), a set of behaviors or actions performed in each of those states, and a set of events that cause changes in states according to a finite and well-defined rule set.

This definition makes very clear the notion of a finite state machine as something that constrains object behavior. When this “abstract machine” is in one state, it performs only a certain subset of actions, it accepts only a certain set of incoming events, and it can change state directly to only a subset of all possible states. A traffic light system is a common example of a state machine. It might have states such as “Green,” “Yellow,” “Red,” “Flashing Yellow,” and “Flashing Red.” (Some countries even have a “Flashing Green” state to keep you on your toes). These states cannot be entered except in particular, well-defined sequences. This definition of a state machine maps well to Bertrand Meyer's idea of object contracts, which consist of preconditional invariants (predecessor states and triggering events), event signatures, and postconditional invariants (actions performed).

So, what sort of things exhibit state behavior? In functionally decomposed systems, it is usually some vaguely defined set of operations that act on some set of shared data variables. In object-oriented (OO) systems, the boundary is rather more crisp: objects are things that exhibit state behavior. In the UML metamodel (model of the UML itself), Classifiers are metaclasses that can be associated with state machines. Classifiers include such things as classes, interfaces, datatypes, use cases, components, and subsystems. Instances of these things (objects are instances of classes, for example) have their own individual machine executing that defined state behavior. The most common things in the UML to model with explicit state machines are classes and use cases.

A use case is a named piece of functionality that is visible in a context, and that returns a result visible to one or more objects in that context (called actors ). Use cases define pieces of magic that some aspect of the context performs without implying any specific design or implementation. This magic can be expressed with multiple scenarios of interaction between the thing in that context and the associated actors.

Note that if you're building functionally designed systems today rather than OO systems, that does not imply that state machines are inappropriate or cannot be used. Rather than apply the state machines to specific objects, the state machines will apply to a set of independently defined functions and the data that they share. State machines are a powerful formalism that transcends the notions of functional and OO design. Nevertheless, state machines map very clearly and obviously to objects, which accounts for much of their popularity in object-oriented designs.

Basic semantics and notation of state machines
The UML provides two different kinds of state machine formalisms: statecharts and activity diagrams. These formalisms differ in the kinds of situations in which they are applied. Statecharts are used when the transition from state to state takes place primarily when an event of interest occurs. Activity diagrams are appropriate when the object (or operation) changes state primarily upon completion of the activities executed within the state, rather than the asynchronous occurrence of events. We will limit our discussion here to the much more commonly used form — statecharts. The use of activity diagrams is covered in several of the references.

Statecharts consist of three primary items: states, transitions, and actions. States are distinguishable conditions of existence that persist for a significant period of time. Transitions are the means by which objects change states in respond to events. State machines also execute actions — atomic behaviors — at various points in a state machine, such as when an event triggers a transition, when a state is entered, or when a state is exited. Actions may be simple statements, such as a++ or they can invoke operations defined within the context object or other objects.

An example: reliable communication service
Let's consider a simple example: the communication between sender and receiver objects, mediated by a communications controller. The sender can specify the quality of service (QoS) on a per-message basis. The system supports three qualities of services:

At most once — this QoS can be thought of as “send and forget.” If the message gets lost or garbled, then the receiver won't get it, but that's okay. The receiver receives the message no more than one time.

At least once — this QoS sends a message and waits for an explicit ACK message from the receiver. If the sender side doesn't receive an ACK within a reasonable time, then the sender side resends the message. This can repeat until some maximum retry count is reached. This QoS is called “At least once” because if the returning ACK is the message lost or garbled, rather than the informational message, then the receiver may get that message more than once.

Exactly once —At least once QoS works fine for informational messages that send absolute values (like “Speed = 60”), but it fails for incremental messages (such as “Increment Count”). For this reason, the communications systems supports a QoS that ensures that if multiple copies of a message are received, the duplicates will be quietly discarded.

An object model that addresses this problem is shown in Figure 1. The Comm_Controller object gets a Send(msg) message from the sender and, if appropriate, creates a message Send_Transaction object that manages sending the message, waiting for the returning ACK, and resending the message, if necessary. This model alone handles the At least once QoS requirement. The state machine for this is shown in Figure 2.

The statechart for the Send_ Transaction is fairly straightforward. States are represented by the rounded rectangles while transitions are depicted as directed lines. The object starts life in the Idle state, as indicated with the initial pseudostate (the transition with a ball at one end). Then the object receives the evSend event, and it performs an action to set one of its attributes called sendCount to zero. The object then resides in the Sending state until the message is done being sent. Then the object transitions to the Waiting state.

In the Waiting state, two different things of interest can happen. First, the Send_Transaction could receive an evValidACK in response to receiving a valid ACK from the sender. In that case, the object transitions to the terminal pseudostate (shown with the circumscribed “T”). The terminal pseudostate indicates that the object stops receiving events and is destroyed.

The other event of interest in the Waiting state is the elapse of a timeout. This indicates that the ACK hasn't been received within the appropriate time window. But two possibilities exist in this case. If we have exceeded the number of retries we're willing to make, then we should notify the sender and proceed to the terminal pseudostate. On the other hand, if we haven't exceeded the maximum retry count, then we ought to go to the Sending state and try again. This selection is done by transitioning on the timeout event (shown by the special tm( ) event) to a conditional pseuodostate. The two different possibilities exiting the pseudostate are distinguished by having different guards, or selection criteria.

The Receive_Transaction works somewhat differently. (Figure 3.) It's created when the receiving Comm_ Controller receives a message that has a QoS of Exactly once. Each new message received with this QoS results in the creation of a Receive_Transaction object. The Receive_Transaction stores the message ID of that message and waits. When another message comes, the Comm_Controller asks each Receive_Transaction object if it is waiting for a message with that particular ID. If the answer is yes, the object responds to the message with a transition-to-self (i.e., transition in which the source and target states are the same). This response has the semantic effect of resetting any timeout transitions exiting that state. The other event of interest is the elapsing of a period of time since the last time that message was received. When this latter event occurs, the Receiver_Transaction object is destroyed and the receiver side forgets that it ever received a message with that particular message ID.

The basic notation
States. Figure 4 shows all the basic elements of statecharts: states, transitions, actions, and a variety of different pseudostates. In the figure, the high-level states are S0, S1, and S2. These states are called or-states because within their context, the object must be in one and only one of these states at any given time. The initial state is indicated by the initial state pseudostate on the left and its associated transition to state S0. This indicates that when the object is created, it enters state S0 initially before processing any events.

Some but not all of these states have substates nested within them. S0, for example, has nested states S0_1 and S0_2. This is another way of saying “when the object is in state S0, it must be in either of two more specific conditions.” For example, when a device might have high-level states of {off , on } and when it is in the on state it can be in any other following substates {booting , operating , shutting down }. Substates can be nested arbitrarily deep. For example the booting state might be decomposed into sub-substates of {BIOS test , RAM test , ROM test , identifying peripherals , configuring system }. In Figure 4, state S2 has three substates, one of which is broken down into substates of its own.

If an object's behavior is defined by a state machine (such an object is said to be reactive ), then it spends all of its time in one state or another. It must always be within exactly one or-state within the level of context. Thus, the machine shown in Figure 4 must be in either state S0, S1 or S2. If it is in state S2, then it must be in one of its substates S2_1, S2_2, or S2_3. If it is in state S2_3, then it must also be in either state S23_1 or S23_2. States can be referenced by a unique name, such as S23_1 or by referencing its owner state, as in S2.S2_3.S23_1.

Transitions. As I previously mentioned, transitions indicate that the state machine responds to an event while in certain states. For example, if you look in state S0, you'll see that while the state machine is in state S0_1 it accepts an event e0 and when that occurs, the object transitions to state S0_2. Similarly, while in state S0_2, if an e2 event occurs, the state machine transitions to state S0_1.

Transitions affecting a superstate apply at all levels of nesting within that superstate. While in state S0, if an e1 event occurs, the system transitions to state S1. Since the object must be in either state S0_1 or S0_2 while in state S0, this means that this event transition applies to both substates of S0. This is one of the benefits of nesting states—you can show multiple state transitions to a common target state with a single transition by simply nesting those states to which the transition applies. In general, a transition exiting a superstate applies to all substates within it, regardless of how deeply they are nested. The transitions triggered by event e3, for example, apply to all substates of state S2, including the deeply nested substates S23_1 and S23_2.

Transitions are modeled as taking approximately zero time to execute,1 as implied by the statement that an object spends all of its time in states. If a transition can take a significant amount of time, then the object should be decomposed into more states so that eventually, the time taken to get from a predecessor state to a subsequent state is insignificant. State machine execution itself is said to proceed in discrete time units called run-to-completion (RTC) model steps . An RTC step is the period of time in which events are accepted and acted upon. Processing an event always completes within a single model step, including exiting the source state, executing any associated actions, and entering the target state.

Transitions represent the response of a state machine to events. Any event that isn't explicitly listed as causing an event to occur in a given state is quietly discarded should it occur. For example, in state S0_1, only three events result in a state transition: e0, e1, and e5. Event e0 causes a transition to state S0_2. Event e1 causes the object to leave S0_1 and its enclosing superstate S0 and transition to state S1. Event e5 works the same way, but it ends on a conditional pseudostate which selects the target state on the basis of guards.

A guard is a Boolean condition that returns a TRUE or FALSE value that controls whether or not a transition is taken following the receipt of a triggering event. A transition with a guard is only taken if the triggering event occurs and the guard evaluates to TRUE. For example, look at the transition from the state S2 to the terminal pseudostate in Figure 4. It is called an anonymous or null transition because it has no triggering event. It becomes enabled as soon as the object enters state S2. However, it has a guard—the action isDone(). If this function returns TRUE, then the object transitions to the terminal pseudostate (and ceases to respond to any further events). Because there is no triggering event in this case, if the guard evaluates to FALSE, then the transition is not reevaluated until and unless the source state is exited and reentered. If there were a triggering event, then whenever that event reoccurred while the source state was active, the guard would be reevaluated. As long as the guard evaluated to FALSE, the triggering event would be discarded and the transition would not be taken.

Another place in the figure that you see guards is on transition segments exiting the conditional pseudostate (shown as a circumscribed “C” in the middle of the figure). Conditional pseudostates are a notational shorthand for multiple exiting transitions all triggered by the same event but each having different guards. In this case, the triggering event is e5. The resulting state differs depending on the evaluation of the guards. In this case if a<0, then the resulting state is S1. If a>0, the object transitions to the terminal pseudostate. The “else” guard handles all other conditions and transitions to the S2 state. In this case the inclusion of an else guard means that whenever event e5 occurs, the transition will be taken. If you removed the else clause and neither remaining guard returned TRUE, the triggering event would be discarded.

So far, we've discussed two kinds of triggers. The first is a named trigger—that means that some named event results in a transition being taken. The other is the null transition, meaning that the transition is evaluated only once upon entrance to the source state. If it has no guard, or if the guard evaluates to TRUE, then the transition is taken immediately. Another kind of trigger is shown in state S2, the tm(x) event. This indicates a timeout event which fires some specified period of time after the state is entered. The UML doesn't define the units, but commonly they are milliseconds or microseconds. The timeout event is cancelled if the source state is exited prior to the timeout. Also, if another event triggers a transition-to-self (a transition in which the source and target states are the same), any timeout transitions leaving that state are reinitialized. This is the case for event e7 applied to state S23_3. The timeout interval represented by the tm(660) event transition (shown at the bottom of the state) is restarted from scratch whenever the object is in state S2_3 and an e7 event occurs.

The UML defines four different kinds of events:

  • Signal Event—an event due to some external asynchronous process
  • Call Event—an event due to the execution of an operation within the object
  • Change Event—an event due to the change in value of an attribute
  • Time Event—an event due to the lapse of an interval of time

Signal Events are by far the most common in practice, but time events are also frequently used. A Signal Event is associated with a Signal, which is a type of Classifier in the UML metamodel, similar to a Class or a Use Case. Events can have zero or more parameters, allowing the event to convey not only the occurrence of some interesting incident in space and time but also qualitative and quantitative information regarding that occurrence, such as the number of knob clicks, the airspeed determined by polling the sensor, or the level of hazardous radiation due to the occurrence of a leak in the reactor core.

In the UML, events are generalizable, which means that they can be members of a generalization taxonomy. The practical implication of this is that a transition triggered by any event e will also be triggered by any subclass of that event. This is sometimes called polymorphic event triggering .

The general syntax for a transition is:

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

All of these fields are optional, as I mentioned previously. If a transition is totally unnamed, then it activates as soon as its source state becomes active and completes its activities (if it has any). Once again, this is called a null trigger or anonymous event.

The event-name is the name of the event triggering the transition. The same event may trigger multiple transitions in a state machine. They can be unguarded if they apply to different source states, or they may be guarded (in which case they may apply to the same source state). For example, in Figure 4, the e1 event triggers a transition between states S0 Æ S1, but the same event also triggers a transition between states S23_1 Æ S23_2. Should this event occur while the object is in any other state, it would be discarded.

Similarly, the event e5 triggers three transitions from the S0 source state. The target state is selected according to the guard that evaluates to TRUE. If no guard evaluates to TRUE, the event is discarded. However, if more than one guard evaluates to true, then the model is ill-formed. In such a case, the statechart semantics stipulate that only one of the transitions will be taken, but you can't predict which one it will be.

The parameter list, when present, is enclosed within parentheses, just as you would function parameters. They may include types, if desired. Guards are enclosed within square brackets. A guard must return a boolean, but it can be an arbitrarily complex expression, including logical operators such as AND and OR. Guards should not have side effects because a guard may be evaluated many times prior without actually taking the transition. So using a guard such as:

[++a == TIME_TO_MOVE]

is a bad idea.

Action lists consist of zero or more actions, which can be simple program statements, such as a++ or calls to operation defined within the object or messages sent to other objects. Action-lists are also preceded by a slash (/). The transition label can also include an event-list. Event-lists are always preceded with a carat (^), and have a list of events that are generated as a result of taking the transition. Events generated in this way are called propagated events . Both the execution of a transition's action-list and the generation of the propagated events in the event-list are only done if and when the transition is actually taken. If the event occurs but the transition isn't taken (due, for example, to a guard evaluating to FALSE), then the actions are not executed and the propagated events are not generated. A propagated event is shown in the figure attached to the timeout transition-to-self for state S2_3.

It should be noted that there are those within the OMG UML RTF and OMG RTAD working groups that think that propagation of events is really just a special form of an action, and it would be better to use an action within the action-list, such as GEN(FlameOn) rather than have a separate event-list clause. Time will tell who wins out, but in the meantime, a carat is used to indicate an event-list in the UML standard (individual tools vary in their compliance with this notation).

Actions and Activities . Actions are small atomic behaviors executed at specified points in a state machine. They are assumed to take an insignificant amount of time to execute and are non-interruptible. Actions are separated from the event-name and guard with a slash (/). The action-list clause may contain zero or more actions. The exact syntax of the action expressions isn't defined by the UML, so many people use either structured English or expressions in an implementation language such as C++ or Java. In statecharts, actions may be placed in any of three places: on a transition, on a state entry, or on a state exit.

Figure 4 shows many examples of actions in all three positions. Notice, for example, the text /setupAction() next to the outermost initial pseudostate ÆS0. This is a null transition (you should never specify a triggering event for an initial transition) but it does specify an action. This means that prior to entering the state S0 when the object is first created, execute the setupAction() operation. The transition triggered by e1 between S0 ÆS1 has two actions named: action1() and action2(). The actions are only executed if the transition is taken (e5 occurs and isOk() evaluates to TRUE). Note that the actions can be associated with different transition segments, as with the transition triggered by event e5. A common action (action1()) is executed, followed by the action executed by the conditional segment branch taken.

Actions associated with states may be shown on the statechart, or may be hidden inside a pop-up “features” dialog. When shown on the state, the keyword entry indicates the entry action list and exit indicates the exit action list. These are the actions taken when the state is entered and exited, respectively. As a rule of thumb, actions that are always executed when a state is en

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.