Finite State Machines

Description

Definition from Wikipedia:

A finite-state machine (FSM) or finite-state automaton (plural: automata), or simply a state machine, is a mathematical model used to design computer programs and digital logic circuits. It is conceived as an abstract machine that can be in one of a finite number of states. The machine is in only one state at a time; the state it is in at any given time is called the current state. It can change from one state to another when initiated by a triggering event or condition, this is called a transition. A particular FSM is defined by a list of the possible states it can transition to from each state, and the triggering condition for each transition.

In ROOM each actor class can implement its behavior using a state machine. Events occurring at the end ports of an actor will be forwarded to and processed by the state machine. Events possibly trigger state transitions.

Motivation

For event driven systems a finite state machine is ideal for processing the stream of events. Typically during processing new events are produced which are sent to peer actors.

We distinguish flat and hierarchical state machines.

Semantics

State machine execution begins at the top level by traversal of the initial transition. During traversal of a transition its (optional) action code is executed.

So called triggered transitions start at a state or a transition point. The simple most trigger is a pair of port (or SAP) and message.

For the following we will discuss hierarchical finite state machines, which include flat state machines as a special case.

Assume the state machine is in an arbitrary leaf state (states with no nested state machines). Then when an event occurs, a transition with a matching trigger is searched. This is done level by level from the state graph of the current state to the top level state graph. First all outgoing transitions are considered, then handler transitions. If no match was found this is repeated one level higher and so on to the top level. If no match is found at all, the event is discarded.

Then the transition which was triggered is traversed.

For any transition it can continue in several ways:

• If it starts from a state or is a continuation after an entry or exit point
  • and ends at a leaf state, the state machine will assume this state
  • and ends at a state with sub graph, it is called a transition to history and the last active state inside the target state is assumed
  • and ends at a choice point, the choice point branch conditions are evaluated (in arbitrary order). The first transition whose condition is met will be traversed or else the default branch is taken
• if it starts in a transition point, then in any case the current state is left, thereby executing all exit codes until the level of the transition point
  • and ends in the same transition point then the transition is traversed and the current state is activated again, thereby executing all entry codes
  • else the transition is traversed and processing continues
  • eTrice specific variant (not contained in ROOM): the transition point can be a handler. In this case no entry and exit codes of states are executed
• if the transition ends in an entry or exit point the traversal is continued on the other side of this point, entering or leaving the subgraph resp.

All this is looped until the new leaf state is reached.

Notation

We distinguish flat finite state machines (with just one level of hierarchy) and hierarchical ones.

Flat Finite State Machine

The simpler flat finite state machines are composed of the elements shown following table:

Element	Graphical Notation	Textual Notation
State		State SomeState
InitialPoint		implicit
TransitionPoint		TransitionPoint tp
ChoicePoint		ChoicePoint cp
Initial Transition		Transition init: initial -> Initial { }
Triggered Transition		Transition tr0: initial -> DoingThis { triggers { <doThis: fct> } }

Hierarchical Finite State Machine

The hierarchical finite state machine adds the notion of a sub state machine nested in a state. A few modeling elements listed in table below are added to the set listed above.

Element	Graphical Notation	Textual Notation
State with sub state machine	Parent State	Sub state machine State Running { subgraph { Transition init: initial -> Process {} State Process } }
Entry Point	In sub state machine	EntryPoint reInit
Exit Point		ExitPoint tp0

Examples