Previous UML Classes Table of Contents UML Packages Next


15.3.12 StateMachine

BehaviorStateMachines


   State machines can be used to express the behavior of part of a system. Behavior is modeled as a traversal of a graph of state nodes interconnected by one or more joined transition arcs that are triggered by the dispatching of series of (event) occurrences. During this traversal, the state machine executes a series of activities associated with various elements of the state machine.

*Generalizations

   • Behavior (from BasicBehaviors ) on page 447

   Description

   A state machine owns one or more regions, which in turn own vertices and transitions.

   The behaviored classifier context owning a state machine defines which signal and call triggers are defined for the state machine, and which attributes and operations are available in activities of the state machine. Signal triggers and call triggers for the state machine are defined according to the receptions and operations of this classifier.

   As a kind of behavior, a state machine may have an associated behavioral feature (specification) and be the method of this behavioral feature. In this case the state machine specifies the behavior of this behavioral feature. The parameters of the state machine in this case match the parameters of the behavioral feature and provide the means for accessing (within the state machine) the behavioral feature parameters.

   A state machine without a context classifier may use triggers that are independent of receptions or operations of a classifier, i.e., either just signal triggers or call triggers based upon operation template parameters of the (parameterized) statemachine.

   Attributes

   No additional attributes

   Associations

Issue 8433 -add subsets constraint 9091 -same as above

   • extendedStateMachine: StateMachine[*] The state machines of which this is an extension. {Subsets RedefineableElement::redefinedElement}

   Constraints

   [1] The classifier context of a state machine cannot be an interface.

   context->notEmpty() implies not context.oclIsKindOf(Interface)

   [2] The context classifier of the method state machine of a behavioral feature must be the classifier that owns the behavioral feature.

   specification->notEmpty() implies (context->notEmpty() and specification->featuringClassifier->exists (c | c = context))

   [3] The connection points of a state machine are pseudostates of kind entry point or exit point.

   conectionPoint->forAll (c | c.kind = #entryPoint or c.kind = #exitPoint)

   [4] A state machine as the method for a behavioral feature cannot have entry/exit connection points.

   specification->notEmpty() implies connectionPoint->isEmpty()

   Additional Operations

   [1] The operation LCA(s1,s2) returns an orthogonal state or region that is the least common ancestor of states s1 and s2, based on the statemachine containment hierarchy.

   [2] The query ancestor(s1, s2) checks whether s2 is an ancestor state of state s1.

   context StateMachine::ancestor (s1 : State, s2 : State) : Boolean

   result = if (s2 = s1) thentrueelse if (s1.container->isEmpty) thentrueelse if (s2.container->isEmpty) thenfalse

Issue 6725 - Adding closing parenthesis.

   else (ancestor (s1, s2.container))

   [3] The query isRedefinitionContextValid() specifies whether the redefinition contexts of a statemachine are properly related to the redefinition contexts of the specified statemachine to allow this element to redefine the other. The containing classifier of a redefining statemachine must redefine the containing classifier of the redefined statemachine.

   [4] The query isConsistentWith() specifies that a redefining state machine is consistent with a redefined state machine provided that the redefining state machine is an extension of the redefined state machine: Region s are inherited and regions can be added, inherited regions can be redefined. In case of multiple redefining state machines, extension implies that the redefining state machine gets orthogonal regions for each of the redefined state machines.

*Semantics

   The event pool for the state machine is the event pool of the instance according to the behaviored context classifier, or the classifier owning the behavioral feature for which the state machine is a method.

   Event processing - run-to-completion step

   Event occurrences are detected, dispatched, and then processed by the state machine, one at a time. The order of dequeuing is not defined, leaving open the possibility of modeling different priority-based schemes.

   The semantics of event occurrence processing is based on the run-to-completion assumption, interpreted as run-tocompletion processing. Run-to-completion processing means that an event occurrence can only be taken from the pool and dispatched if the processing of the previous current occurrence is fully completed.

   Run-to-completion may be implemented in various ways. For active classes, it may be realized by an event-loop running in its own thread, and that reads event occurrences from a pool. For passive classes it may be implemented as a monitor.

   The processing of a single event occurrence by a state machine is known as a run-to-completion step. Before commencing on a run-to-completion step, a state machine is in a stable state configuration with all entry/exit/internal activities (but not necessarily state (do) activities) completed. The same conditions apply after the run-to-completion step is completed. Thus, an event occurrence will never be processed while the state machine is in some intermediate and inconsistent situation. The run-to-completion step is the passage between two state configurations of the state machine.

   The run-to-completion assumption simplifies the transition function of the state machine, since concurrency conflicts are avoided during the processing of event, allowing the state machine to safely complete its run-to-completion step.

   When an event occurrence is detected and dispatched, it may result in one or more transitions being enabled for firing. If no transition is enabled and the event (type) is not in the deferred event list of the current state configuration, the event occurrence is discarded and the run-to-completion step is completed.

   In the presence of orthogonal regions it is possible to fire multiple transitions as a result of the same event occurrence — as many as one transition in each region in the current state configuration. In case where one or more transitions are enabled, the state machine selects a subset and fires them. Which of the enabled transitions actually fire is determined by the transition selection algorithm described below. The order in which selected transitions fire is not defined.

   Each orthogonal region in the active state configuration that is not decomposed into orthogonal regions (i.e., bottomlevel region) can fire at most one transition as a result of the current event occurrence. When all orthogonal regions have finished executing the transition, the current event occurrence is fully consumed, and the run-to-completion step is completed.

Issue 8433 -replace ‘complete’ with ‘completes’

   During a transition, a number of actions may be executed. If such an action is a synchronous operation invocation on an object executing a state machine, then the transition step is not completed until the invoked object completes its run-tocompletion step.

   Run-to-completion and concurrency

   It is possible to define state machine semantics by allowing the run-to-completion steps to be applied orthogonally to the orthogonal regions of a composite state, rather than to the whole state machine. This would allow the event serialization constraint to be relaxed. However, such semantics are quite subtle and difficult to implement. Therefore, the dynamic semantics defined in this document are based on the premise that a single run-to-completion step applies to the entire state machine and includes the steps taken by orthogonal regions in the active state configuration.

   In case of active objects, where each object has its own thread of execution, it is very important to clearly distinguish the notion of run to completion from the concept of thread pre-emption. Namely, run-to-completion event handling is performed by a thread that, in principle, can be pre-empted and its execution suspended in favor of another thread executing on the same processing node. (This is determined by the scheduling policy of the underlying thread environment — no assumptions are made about this policy.) When the suspended thread is assigned processor time again, it resumes its event processing from the point of pre-emption and, eventually, completes its event processing.

   Conflicting transitions

   It was already noted that it is possible for more than one transition to be enabled within a state machine. If that happens, then such transitions may be in conflict with each other. For example, consider the case of two transitions originating from the same state, triggered by the same event, but with different guards. If that event occurs and both guard conditions are true, then only one transition will fire. In other words, in case of conflicting transitions, only one of them will fire in a single run-to-completion step.

   Two transitions are said to conflict if they both exit the same state, or, more precisely, that the intersection of the set of states they exit is non-empty. Only transitions that occur in mutually orthogonal regions may be fired simultaneously. This constraint guarantees that the new active state configuration resulting from executing the set of transitions is well formed.

   An internal transition in a state conflicts only with transitions that cause an exit from that state.

   Firing priorities

   In situations where there are conflicting transitions, the selection of which transitions will fire is based in part on an implicit priority. These priorities resolve some transition conflicts, but not all of them. The priorities of conflicting transitions are based on their relative position in the state hierarchy. By definition, a transition originating from a substate has higher priority than a conflicting transition originating from any of its containing states.

   The priority of a transition is defined based on its source state. The priority of joined transitions is based on the priority of the transition with the most transitively nested source state.

   In general, if t1 is a transition whose source state is s1, and t2 has source s2, then:

   Transition selection algorithm

   The set of transitions that will fire is a maximal set of transitions that satisfies the following conditions:

   This can be easily implemented by a greedy selection algorithm, with a straightforward traversal of the active state configuration. States in the active state configuration are traversed starting with the innermost nested simple states and working outwards. For each state at a given level, all originating transitions are evaluated to determine if they are enabled. This traversal guarantees that the priority principle is not violated. The only non-trivial issue is resolving transition conflicts across orthogonal states on all levels. This is resolved by terminating the search in each orthogonal state once a transition inside any one of its components is fired.

   StateMachine extension

   A state machine is generalizable. A specialized state machine is an extension of the general state machine, in that regions, vertices, and transitions may be added; regions and states may be redefined (extended: simple states to composite states and composite states by adding states and transitions); and transitions can be redefined.

   As part of a classifier generalization, the classifierBehavior state machine of the general classifier and the method state machines of behavioral features of the general classifier can be redefined (by other state machines). These state machines may be specializations (extensions) of the corresponding state machines of the general classifier or of its behavioral features.

   A specialized state machine will have all the elements of the general state machine, and it may have additional elements. Region s may be added. Inherited regions may be redefined by extension: States and vertices are inherited, and states and transitions of the regions of the state machine may be redefined.

   A simple state can be redefined (extended) to a composite state, by adding one or more regions.

   A composite state can be redefined (extended) by either extending inherited regions or by adding regions as well as by adding entry and exit points. A region is extended by adding vertices, states, and transitions and by redefining states and transitions.

   A submachine state may be redefined. The submachine state machine may be replaced by another submachine state machine, provided that it has the same entry/exit points as the redefined submachine state machine, but it may add entry/ exit points.

Issue 8433 -replace ‘is’ by ‘are’

   Transitions can have their content and target state replaced, while the source state and trigger are preserved.

   In case of multiple general classifiers, extension implies that the extension state machine gets orthogonal regions for each of the state machines of the general classifiers in addition to the one of the specific classifier.

   Notation

   A state machine diagram is a graph that represents a state machine. States and various other types of vertices (pseudostates) in the state machine graph are rendered by appropriate state and pseudostate symbols, while transitions are generally rendered by directed arcs that connect them or by control icons representing the actions of the behavior on the transition (page 599).

   The association between a state machine and its context classifier or behavioral feature does not have a special notation.

   A state machine that is an extension of the state machine in a general classifier will have the keyword «extended» associated with the name of the state machine.

   The default notation for classifier is used for denoting state machines. The keyword is «statemachine».

   Inherited states are drawn with dashed lines or gary-toned lines.

   Presentation option

   Inherited states are drawn with gray-toned lines.

   Examples

    Figure 15.41 is an example statemachine diagram for the state machine for simple telephone object. In addition to the initial state, the state machine has an entry point called activeEntry, and in addition to the final state, it has an exit point called aborted.


   


terminate


   abort

   aborted


   Figure 15.41 - State machine diagram representing a state machine

   As an example of state machine specialization, the states VerifyCard, OutOfService, and VerifyTransaction in the ATM state machine in Figure 15.42 have been specified as {final}, which means that they cannot be redefined (i.e., extended) in specializations of ATM. The other states can be redefined. The (verifyTransaction,releaseCard) transition has also been specified as {final}, meaning that the effect behavior and the target state cannot be redefined.

Figure 15.42 - A general state machine

   In Figure 15.43 a specialized ATM (which is the statemachine of a class that is a specialization of the class with the ATM statemachine of Figure 15.42 ) is defined by extending the composite state by adding a state and a transition, so that users can enter the desired amount. In addition a transition is added from an inherited state to the newly introduced state.




   





Figure 15.43 - An extended state machine

   




   Rationale

   The rationale for statemachine extension is that it shall be possible to define the redefined behavior of a special classifier as an extension of the behavior of the general classifier.

   Changes from previous UML

Issue 8433 -clarify

   State machine extension is an extension of 1.x. In 1.x, state machine generalization is only explained informally discussed as a non-normative practice.

   Rationale

   State machines are used for the definition of behavior (for example, classes that are generalizable). As part of the specialization of a class it is desirable also to specialize the behavior definition.