IntelliWizard© - UML StateWizard

A UML StateChart open-source framework and IDE tools under a dual licensing model.

Features

Users & Partners

Visual Modeling of Complex Reactive Systems with Harel UML StateChart

Harel StateCharts are gaining widespread usage since a variant has become part of the Unified Modeling Language. The diagram type allows the modeling of superstates, concurrent states, and activities as part of a state.

Problems with Conventional Finite State Machines

In general, a state machine is any device that stores the status of something at a given time and can operate on input to change the status and/or cause an action or output to take place for any given change. In practice, however, state machines are used to develop and describe specific device or program interactions.

To summarize it, a state machine can be described as:

• A set of states
• An initial state or record of something stored someplace
• A set of input events
• A set of output events
• A set of actions or output events that maps states and input to output (which is called a state event handler)
• A set of actions or output events that maps states and inputs to states (which is called a state transition)

Finite state machine

A finite state machine is one that has a limited or finite number of possible states. A finite state machine can be used both as a development tool for approaching and solving problems and as a formal way of describing the solution for later developers and system maintainers.

Classic Mealy-Moore state machine modelling techniques require the creation of distinct nodes for every valid combination of parameters that define the state. This can lead to a very large number of nodes and transitions between nodes for all but the simplest of systems. This complexity reduces the readability of the state diagram.
Another of the limitations of modelling a computer system as a conventional state machine is the lack of support for concurrent constructs. Traditional state machine modelling is based on sequential transitions from one state to the next. Concurrent systems cannot be modelled in this manner as various aspects of the system may be in different states.

It is seen that the limitations inherent in state machine models include the inherent complexity which occurs as the number of states increases, and also the modelling of concurrent systems.

This article presents a commercial-grade cross-platform Harel UML Statechart open-source application framework named StateWizard for concurrent, distributed and real-time reactive system development with simplicity, efficiency and scalability. The following sections describe the ways to solve complex, reactive system problems with the following Harel Statechart features:

• Hierachical state machines
• Support large scale state machines with hundreds of states through separating a state tree definitions to several C/C++ files.
• State history information and history transitions
• Guarded transitions on event handling
• Conditional pseudo-states
• Join pseudo-states
• Orthogonal states
• Built-in state timers

States

State is an abstract view. A state has same active behaviors and same responses to the same events.

UML defines three types of states:

Simple States (Leaf States):

Simplest of all states, they have no sub-states.

Composite States:

Have one or more regions for substates. A region is simply a container for substates.

A composite state is a state that consists of sub-states. A composite state can be decomposed using and-relationships into two or more concurrent regions which are containers for sub-states, or using or-relationships into mutually exclusive disjoint sub-states.

Orthogonal State:

If a composite state which can be decomposed using and-relationships into two or more concurrent regions, is called Orthogonal State.

Submachine States:

Semantically equalent to composite states, submachine states have substates that are contained within a substate machine. Unlike composite states, submachine states are intended to group states, so you can reuse them.

The systems' overall behavior can be broken down into individual states. For example, a tape recorder can be on or off. These are two distinct states.

A state can be as brief as a fraction of a second, or extend to several seconds, minutes or hours. Each state, no matter how brief, is a distinct unit within the system's life cycle. State Machine allows you to depict all the states of a system, as they occur in real-life.

What is more, each state is a collection of several actions which State Machine performs when the state is active. These actions take place upon entry into the state, or upon exit from the state.

The StateWizard allows developers to model complex behavior via composite state with more than one hierarchy level:

• Similar sub-states are grouped into a composite state (nesting hierarchy is a tree);
• Composite states can have transitions, entry/exit actions, . . .(transitions can connect states from different nesting levels);
• Sub-states "inherit" from the composite state;
• Active state denotes a path from a top-level state to a leaf node in the state hierarchy;
• There must be an initial sub-state in every composite state. On entering a compose state or sub-state, both of them are activated. Order of the entry functions is from top to down.
• On exiting a composite state, exit active sub-state as well. Order of the exit functions is from down to top.

The state machine state hierarchy is based on a parent-child relationship, which is depicted by the arrangement of the tree branches. For example, in the following Figure: State Hierarchy in Tree Form, node Application in state tree below is a root state which has two children: PowerDown and PowerUp. Meanwhile, the node PowerUp is also a parent of three children and these children are referred as sibling states among them.

This hierarchical organization means that when a transition from state PowerDown to PowerUp is triggered, State Machine de-activates state PowerDown and its children (if any) and activates On and one or more of its children (if any).

Player

• PowerDown (Init)
• PowerUp
  • Playing (Init)
  • Pause
  • Record

Figure: State Hierarchy in Tree Form

Using the StateWizard application framework API set which is defined in sme.h , the Player state machine is defined as below:

/* The definition of the Player composite root state. */

#define SME_CURR_DEFAULT_PARENT Player

SME_BEGIN_ROOT_COMP_STATE_DEF(Player, PlayerEntry, PlayerExit)
SME_ON_INIT_STATE(SME_NULL_ACTION, PowerDown)
SME_END_STATE_DEF

SME_BEGIN_LEAF_STATE_DEF_P(PowerDown, PowerDownEntry, PowerDownExit)
SME_ON_EVENT(EXT_EVENT_ID_POWER, OnPowerDownEXT_EVENT_ID_POWER, PowerUp)
SME_END_STATE_DEF

SME_BEGIN_SUB_STATE_DEF_P(PowerUp)
SME_ON_EVENT(EXT_EVENT_ID_POWER,OnPowerUpEXT_EVENT_ID_POWER,PowerDown)
SME_END_STATE_DEF

/* The definition of the PowerUp composite root state. */

#define SME_CURR_DEFAULT_PARENT PowerUp

SME_BEGIN_COMP_STATE_DEF(PowerUp, Player, PowerUpEntry, PowerUpExit)
SME_ON_INIT_STATE(OnPowerUpInitChild, Playing)
SME_END_STATE_DEF

SME_BEGIN_LEAF_STATE_DEF_P(Playing, PlayingEntry, PlayingExit)
SME_ON_EVENT(EXT_EVENT_ID_PAUSE_RESUME,OnPlayingEXT_EVENT_ID_PAUSE_RESUME,Pause)
SME_END_STATE_DEF

SME_BEGIN_LEAF_STATE_DEF_P(Pause, PauseEntry, PauseExit)
SME_ON_EVENT(EXT_EVENT_ID_PAUSE_RESUME,OnPauseEXT_EVENT_ID_PAUSE_RESUME,Playing)
SME_END_STATE_DEF

SME_BEGIN_LEAF_STATE_DEF_P(Record, RecordEntry, RecordExit)
SME_ON_EVENT(EXT_EVENT_ID_STOP_RECORD,OnRecordEXT_EVENT_ID_STOP_RECORD,PowerDown)
SME_END_STATE_DEF

Root State

is the uppermost state, bearing the application name. As you add states, the state tree grows downwards from the root state.

For example, the Player composite state is the root state of the Player state machine. It is defined as below. The PlayerEntry and PlayerExit are the function pointers to the actions on the root state entry and exit respectively.

SME_BEGIN_ROOT_COMP_STATE_DEF(Player, PlayerEntry, PlayerExit)

Parent State

is a state that branches into one or more child states. A parent can have several children, but a child has only one parent.

For example, the PowerUp composite state's parent state is the state Player. Define the PowerUp state as below.

SME_BEGIN_COMP_STATE_DEF(PowerUp, Player, PowerUpEntry, PowerUpExit)

Initial Child State

identifies the initial state for state machines that have substates. This child is must occur if and only if the machine has one or more state or parallel children.

For example, an initial child state: Playing of the PowerUp composite state is defined as below. The OnPowerUpInitChild is a function pointer to the initial child state entry action.

SME_BEGIN_COMP_STATE_DEF(PowerUp, Player, PowerUpEntry, PowerUpExit)
SME_ON_INIT_STATE(OnPowerUpInitChild, Playing)
SME_END_STATE_DEF

Sibling States

are the child states with a common parent.

Using the StateWizard application framework API set, the sibling states under a parent state are defined below a composite state declaration. For example, the children sibling states: Playing, Pause and Record of the PowerUp composite state are defined as below:

SME_BEGIN_COMP_STATE_DEF(PowerUp, Player, PowerUpEntry, PowerUpExit)
SME_ON_INIT_STATE(OnPowerUpInitChild, Playing)
SME_END_STATE_DEF

SME_BEGIN_LEAF_STATE_DEF_P(Playing, PlayingEntry, PlayingExit)
SME_ON_EVENT(EXT_EVENT_ID_PAUSE_RESUME,OnPlayingEXT_EVENT_ID_PAUSE_RESUME,Pause)
SME_END_STATE_DEF

SME_BEGIN_LEAF_STATE_DEF_P(Pause, PauseEntry, PauseExit)
SME_ON_EVENT(EXT_EVENT_ID_PAUSE_RESUME,OnPauseEXT_EVENT_ID_PAUSE_RESUME,Playing)
SME_END_STATE_DEF

SME_BEGIN_LEAF_STATE_DEF_P(Record, RecordEntry, RecordExit)
SME_ON_EVENT(EXT_EVENT_ID_STOP_RECORD,OnRecordEXT_EVENT_ID_STOP_RECORD,PowerDown)
SME_END_STATE_DEF

Another way to represent the same hierarchy is in nested chart form. In this format, the hierarchy among states are shown by nesting child states within their parent state.

Figure: State Hierarchy in Chart Form

PseudoStates

A PseudoState is an abstraction of different types of nodes in the state machine graph which represent transient points in transition paths from one state to another (e.g., branch and fork points). Pseudo states are used to construct complex transitions from simple transitions. For example, by combining a transition entering a fork pseudo state with a set of transitions exiting the fork pseudo state, we get a complex transition that leads to a set of target states.

Conditional (Fork) PseudoStates

are a notational shorthand for multiple exiting transitions all triggered by the same event
but each having different guards.

Join PseudoState:

a state with several incoming transitions and a single outgoing one.

Using the StateWizard application framework API set which is defined in sme.h , a Conditional PseudoState : Cond1 and a Join PseudoState: Join1 are defined as below. The Cond1 pseudo state has three forks: COND1, COND2 and COND_ELSE. The exit destination state is dependent on the return value of the function: Cond1_func. The action on entry to the Join1 pseudo state is the JoinAct function.

/* The definition of the Player composite root state. */

SME_BEGIN_ROOT_COMP_STATE_DEF(Player, PlayerEntry, PlayerExit)
SME_ON_INIT_STATE(SME_NULL_ACTION, PowerDown)
SME_END_STATE_DEF

....

SME_BEGIN_COND_STATE_DEF_P(Cond1, Cond1_func)
SME_ON_EVENT(COND_EV_COND1, CondAct1, Playing)
SME_ON_EVENT(COND_EV_COND2, CondAct2, Pause)
SME_ON_EVENT(SME_EVENT_COND_ELSE, CondActElse, PowerUp)
SME_END_STATE_DEF

SME_BEGIN_JOIN_STATE_DEF_P(Join1)
SME_ON_JOIN_TRAN(JoinAct, Cond1)
SME_END_STATE_DEF

Events

An event is an object that takes place at certain point of time. An event may contain some data.

Transition describes change from one state to another state.

A transition is comprised of:

A destination: the state which state machine activates when the transition takes place.
A trigger: certain condition within the application that initiates the transition.

In addition, a transition can also contain one or more actions to be executed when the transition is triggered.

The order of operations during transition will be
1) source state exit function,
2) event handler function if available
3) and then destination state entry function.

Transitions

A transition shows the relationship, or path, between two states or pesudostates. It represents the actual change in the configuration of a state machine as it heads from one state to the next. Each transition can have a guard condition that indicates if the transition can even be considered (enabled), a trigger that causes the transition to execute if it is enabled, and effect the transition may have when is occurs.
Transitions are shown as a line between two states, with an arrowhead pointing to the destination state. You specify the details of the transition using the following syntax:

trigger [guard] / actions

where:

trigger:

Indicates what condition may cuase this transition to occur. The trigger is typically the name of an event, though it may be more complex.

guard:

Is a constraint that is evaluated when an even tis fired by the state machine to determine if the tranistion should be enabled. Guards should not have any side effects and must evalate to a boolean. Guards will always be evaluated before a transition is fired.

actions:

In addition, a transition can also contain one or more actions to be executed when the transition is triggered.

For example, in the Pause state, on an event EXT_EVENT_ID_PAUSE_RESUME, the OnPauseEXT_EVENT_ID_PAUSE_RESUME() action will be called and transits to the Playing state.

SME_BEGIN_LEAF_STATE_DEF_P(Pause, PauseEntry, PauseExit)
SME_ON_EVENT(EXT_EVENT_ID_PAUSE_RESUME,OnPauseEXT_EVENT_ID_PAUSE_RESUME,Playing)
SME_END_STATE_DEF

For example, in the Playing state, on an timeout event SME_EVENT_TIMER, check the guard which is defined at GuardTimer_func() function. If the evalation of the guard is true, fire the internal tranistion and call the action OnTimerProc.

SME_BEGIN_LEAF_STATE_DEF_P(Playing, PlayingEntry, PlayingExit)
SME_ON_INTERNAL_TRAN_WITH_GUARD(SME_EVENT_TIMER,GuardTimer_func,OnTimerProc)
SME_END_STATE_DEF

The order of operations during transition will be
1) source state exit function,
2) event handler function if available
3) and then destination state entry function.

If a transition is triggered between different hierarchy levels, or the source state and the destination state are not sibling states, the operation sequence during transition will be more complex.

Figure: State Transition

Transition types

UML defines several specific types of transitions. These are described in the following list. There are no special symbols associated with transition types. They are defined only for clarity and common vocabulary.

Compound Transition

A representation of the change from one complete state machine configuration to another. Compound transitions are a set of transitions, choices, forks, and joins leading to a set of target states.

High-level Transition

A transition from a composite state. If the destination of the transition is outside the composite state, all the substates are exited, and their exit activities are run, followed by the exit activity of the composite. If the transition ends with a target inside the composite state, the exit activity of the composite state isn’t run.

The example is a state machine belonging to a player machine. The default transition from PowerDown to PowerUp will change to the initial sub-state: Playing of the composite state: PowerUp.

Player Application

• PowerDown (Init)
• PowerUp
  • Stop (Init)
  • Playing
  • Record

Figure: High-level Transition

Using the framework API set, the high-level transition from the PowerDown state to the PowerUp state is defined as below:

SME_BEGIN_LEAF_STATE_DEF_P(PowerDown, PowerDownEntry, PowerDownExit)
SME_ON_EVENT(EXT_EVENT_ID_POWER, OnPowerDownEXT_EVENT_ID_POWER, PowerUp)
SME_END_STATE_DEF

Internal Transition

The internal transition is different from the self transition. The internal transitions allow execution of actions that are triggered by events without leaving the state. The state entry and exit actions are not dispatched.

History Transition

A History State is used to remember the previous state of a state machine when it was interrupted.

Player Application

• PowerDown (Init)
• PowerUp (H)
  • Stop (Init)
  • Playing
  • Record

Figure: History Transition

Take the above palyer state machine as example. In this state machine, when a Palyer machine is running at Record state. If there is a power cut, the player machine will stop running and will go to the Power Down state. Then when the power is restored, a history transition from Power Down to Power Up triggers. The running state is entered at the history state Record meaning that it should resume where it last left-off.

The default transition from PowerDown to PowerUp will change to the default sub-state: Stop of the composite state: PowerUp.

Transitions and composite states

A transition from an external state to the border of a composite state is called default entry. The entry activity of the composite state is executed, and then the default transition to a substate occurs.

A transition from an external state to a specific substate of a composite state is called explicit entry. The entry activity for the composite state is executed before the substate becomes active.

Whenever a state machine transitions to an orthogonal composite state ( a composite state with two or more regions), each region is entered either explicitly or by default. If the composite state is entered through an explicit entry, any other region is entered using its default transition.

State Machine Applications

An application is an instance of a state machine or an instance of an region which is an orthogonal part of either a composite state or a state machine. Applications can have one of two modes: active or inactive. Active applications the ones running on the state machine at a given time whereas inactive applications are not. In other words, only active applications can handle events. A State machine engine is responsible for managing these applications and dispatching events to specific applications.

The following macro defines an application instance Player1 based on the Player state machine.

SME_APPLICATION_DEF(Player1, Player)

Orthogonal State

The following macros defines an Orthogonal state named OrthoState as a child of the Player parent state.The state enry/exit actions are OrthoStateEntry and OrthoStateExit respectively. The orthogonal state is composed of three regions:

• PlayerReg1 as an instance of the Player state machine, running at the same thread as its parent with 0 priority.
• PlayerReg2 as an instance of the Player state machine, running at a separate thread with 0 priority.
• PlayerReg3 as an instance of the Player state machine, running at a separate thread with 0 priority.

SME_BEGIN_ROOT_COMP_STATE_DEF(Player, PlayerEntry, PlayerExit)
SME_ON_INIT_STATE(SME_NULL_ACTION, PowerDown)
SME_END_STATE_DEF

SME_BEGIN_ORTHO_SUB_STATE_DEF_P(OrthoState)
SME_ON_EVENT(EXT_EVENT_ID_POWER, OnPowerDownEXT_EVENT_ID_POWER, Join1)
SME_END_STATE_DEF

SME_BEGIN_ORTHO_COMP_STATE_DEF(OrthoState, Player, OrthoStateEntry, OrthoStateExit)
SME_REGION_DEF(PlayerReg1,Player,SME_RUN_MODE_PARENT_THREAD,0)
SME_REGION_DEF(PlayerReg2,Player,SME_RUN_MODE_SEPARATE_THREAD,0)
SME_REGION_DEF(PlayerReg3,Player,SME_RUN_MODE_SEPARATE_THREAD,0)
SME_END_ORTHO_STATE_DEF

In the StateWizard, you may define a transition from/to an Orthogonal state, using SME_BEGIN_ORTHO_SUB_STATE_DEF(). However, you can not define an explicit entry to one of child state of a region. And all regions work in form of applications which run concurrently. On an Orthogonal state entry, all regions will activate automatically. And on state exit, all regions will de-activate automatically. If several regions run at their separate threads, the Orthogonal state will post SME_EVENT_EXIT_LOOP events to these regions and wait for these threads to exit.

State Built-in Timer

The engine support 2 kinds of timers, state-built-in timers and regular timers.

State-built-in timers work tightly with state machine. They are managed by the engine. On a state entry, automatically start the built-in timer, if it is available. On a state exit, stop it. On timeout, they trigger SME_EVENT_STATE_TIMER events. The engine will take actions based on the state machie definition using SME_ON_STATE_TIMEOUT.

Regular timers are explicit timers. Developers have to start or stop them using API call. On timeout, they trigger SME_EVENT_TIMER events. The engien provides two kinds of handling modes, callback function call or event handling which is defined as below:

enum {SME_TIMER_TYPE_CALLBACK, SME_TIMER_TYPE_EVENT};

An explicit callback function should be defined for a callback function mode timer. This mode is independent from state machine definitions. For an timer event mode, SME_ON_EVENT(SME_EVENT_TIMER, handler, new state) should be defined to handle timeout event.

The following sample defines a 3000-ms timer in the Player state and a 9000-ms timer in the Playing state. On timeout, PowerUpTimeOut action will be invoked. On Playing state entry, start it. On timeout, transit to the Pause state automaticaly with PlayingTimeOut action execution.

SME_BEGIN_COMP_STATE_DEF(PowerUp, Player, PowerUpEntry, PowerUpExit)
SME_ON_INIT_STATE(OnPowerUpInitChild, Playing)
SME_ON_STATE_TIMEOUT_INTERNAL_TRAN(3000, PowerUpTimeOut)
SME_END_STATE_DEF

SME_BEGIN_LEAF_STATE_DEF_P(Playing, PlayingEntry, PlayingExit)
SME_ON_EVENT(EXT_EVENT_ID_PAUSE_RESUME,OnPlayingEXT_EVENT_ID_PAUSE_RESUME,Pause)
SME_ON_INTERNAL_TRAN_WITH_GUARD(SME_EVENT_TIMER,GuardTimer2_func,OnTimer2Proc) /* Regular timer event */
SME_ON_STATE_TIMEOUT(9000, PlayingTimeOut, Pause) /* Go to Pause state if 9 sec is timeout. */
SME_END_STATE_DEF

SME_BEGIN_LEAF_STATE_DEF_P(Pause, PauseEntry, PauseExit)
SME_ON_EVENT(EXT_EVENT_ID_PAUSE_RESUME,OnPauseEXT_EVENT_ID_PAUSE_RESUME,Playing)
SME_END_STATE_DEF

Copyright 2009 IntelliWizard Inc. All Rights Reserved.
EMail : info@intelliwizard.com