The protocol machines included in this document are specified
using the modelling technique proposed by David Harel and implemented
by the software engineering tool Statemate (see
Statemate provides a complete software engineering tool including analyser and simulation, documenter and prototyper. The definitions provided in this document reflect only a subset of the Statemate semantics that have actually been used for RPC protocol machine specifications.
The logical semantics of statecharts are based on classical state transition diagrams using the specification technique of finite state machines. Statecharts introduce a number of significant extensions to overcome a major drawback of traditional finite state machines, which is their inherently flat and sequential nature. The complex behaviour of reactive systems such as protocol machines can be better expressed with statecharts. The most significant extensions are as follows:
The RPC protocol specification assumes knowledge of the semantics of traditional finite state machines. This chapter only describes the statechart extensions.
Similar to state transition diagrams, statecharts describe the following elements:
States are represented graphically as rounded rectangles.
Triggers represented graphically as directed graphs (arrows), connecting two states.
Events are represented as a alphanumeric labels on transition lines or in the On field in state definitions.
Conditions are represented as alphanumeric labels on transition lines, enclosed in brackets in the form event[condition], or in the Trigger field in state definitions.
Actions are represented as alphanumeric labels on the transition lines, separated by a slash in the form event[condition]/action, or in the Action field in state definitions. When an action is a sequence of actions, the actions that make it up are separated by semicolons.
Activities are not represented graphically in statecharts. They may appear as part of other element definitions.
Data items are not represented graphically in statecharts. They may appear as part of other element definitions.
Statecharts allow states to be nested to an arbitrarily deep level. Substates are represented graphically as states (rounded rectangles) within the parent state. Parent states are the superordinates or higher-level states. This hierarchical decomposition can be viewed as either clustering of logical groups of states (the bottom-up approach) or as refinement (the top-down approach).
If one substate is active, all its ancestor states are also active at the same time; and if a state containing substates (not a basic state) becomes active, one of the substates will also become active. A substate can transition out to any higher or lower-level state, including its immediate parent state.
Leaf states in this hierarchical structure are basic states,
while all other states, which contain at least one descendent, are
non-basic states. Any valid state transition must always affect
a lowest level basic state or a set of basic states. (For the case of
AND decomposition, see
Conventional state transition diagrams are purely sequential, because only one state can be active in the system at any given time. Permissible states can thus be modelled as a logical exclusive OR (XOR) of the possible states, or by regarding flow control as synchronous.
A state in the hierarchy of statecharts may contain an XOR decomposition of its substates, but statecharts also permit orthogonality. This is the dual of the XOR decomposition; in essence it is an AND decomposition. Such orthogonality introduces the notion of concurrency or asynchronous control.
AND states are multiple states that are active during the same time interval. When transitioning into one of the states in an AND decomposition, all other states become active simultaneously. Analogously, if a transition exits out of one of these orthogonal AND states, all other orthogonal states are deactivated as well. Hence, the concurrent states in an AND decomposition are always synchronously triggered.
As long as the concurrent states are active, substates in these states behave independently, asynchronously. Substate transitions do not affect the other active AND states in the system. However, synchronisation between these can be triggered through events; for example, they can be internally generated in one of the other AND states.
Orthogonal AND states are represented graphically as rounded rectangles (parent state) divided by dashed lines.
The following sections describe several additional graphic elements that support the semantics outlined before and provide for de-cluttering of statecharts. They are mainly introduced to improve the readability of statecharts.
To prevent non-determinism for transitions into substates and orthogonal AND states, a default transition line must be applied to all these sets. These default entries determine which states become active initially unless some other directed transition is valid.
Default entries are represented graphically as a arrows emanating from dots. Default transitions are usually represented without transition labels.
Condition connectors are syntactical graphic elements that are used to economise on arrows and declutter the chart. They are represented graphically as circles containing the letter C. Events, conditions and actions are labelled accordingly on inbound and outbound transition arrows. If distinct conditions apply to the outbound transition arrows, they must be exclusive in order to prevent nondeterminism.
Terminal connectors are syntactical graphic elements that are used to express the termination of a statechart. They are drawn as circles containing the letter T. These T-connectors are considered as a final state; in particular, they have no exits. Upon entering this connector the statechart becomes deactivated.
In order to determine the exact behaviour of the extended semantics applied to statecharts, the precise rules and dynamic control characteristics have to be defined. In most cases, knowledge of the functional behaviour of traditional finite state machines will be sufficient to read and understand statecharts, but, in particular, the concurrency model and state hierarchies require familiarity with the concepts described in the following sections:
Transition arrows can be drawn between any two states in the system, including a loop back to the same state. This section defines how a transition-expressed by an arrow or a set of arrows connected by a conditional connector-is defined and performed. In general, a transition is to be considered as a compound transition, evaluating all attached events and conditions, and performing the entire set of effected actions.
In taking a transition from a source to a target, the transition will, in general, pass through different levels of the state hierarchy. Hence, the question arises as to which non-basic states are exited and entered in the process of taking a transition. This is especially important due to actions that may be called for when exiting and entering states.
To analyse this behaviour, the notion of the scope of a transition is introduced. The scope of a transition is the lowest XOR state in the hierarchy of states that is a proper common ancestor of all the sources and targets of a transition, including non-basic states that are explicit sources or targets of transition arrows appearing in the transition.
When a transition is taken, all proper descendants of the scope in which the system resides at the beginning of the step are exited, and all proper descendants of that scope in which the system will reside as a result of executing the transition are entered. Thus, the scope is the lowest state in which the system stays, without exiting and re-entering, when taking the transition.
Conflicting transitions are those that can lead the system into distinct states. Conflicting transitions are detected if there is a common state in their source sets; therefore, concurrent transitions across orthogonal states do not conflict. Multiple transitions that can occur at the same time step in a given scope have the same priority. Priority is given to the transition with the higher scope.
Conflicting states at the same priority must resolve non-determinism to be legal. Non-determinism occurs in cases where several different transitions are enabled at the same step (for example, a state with multiple outbound transition lines), usually leading to several different statuses.
The system described in a statechart changes state and executes actions based on execution steps. These execution steps determine a sequence of dynamic changes. They are logical intervals, and are not associated with a particular time. In other words, steps are a series of snapshots of the system's situation, where these snapshots represent the status at the given point of time; changes caused by evaluating a snapshot will be sensed at the next snapshot.
Since statecharts express a reactive system, steps are event-driven, or to be more precise, driven by triggers: events, conditions or a combination thereof. Asynchronous external triggers can cause some reactions in the system (for example, state transitions), which in turn may cause an ordered chain of internal reactions, such as generating events, actions and state transitions as if they were a series of synchronous steps.
At any given step n, the system evaluates the events that were generated and identifies the values of data items and conditions that are present at the occurrence of step n. Actions are carried out simultaneously after an enabling trigger is detected at step n. Action-based calculations are based on status and values at the beginning of a step. The enabling trigger and associated actions that lead into a compound transition are taken and completed at step n. All the changes caused by the execution of a transition (step n) are sensed in the following step. Analogously, static reactions sensed within a state will be carried out at the next step.
For example, an event that was generated by an action at step n will be sensed only in the following step n+1. Note that internally generated events have a lifetime of one step only; they are not remembered beyond step n+1. Similarly, if an action is defined based on entering (or exiting) a state, or if an activity is to be started within a state, only the step following the transition into the given state detects these. Note that this does not apply to the notion of performing an activity throughout a state. In this case, the activity will be started at the transition step entering the state and respectively deactivated at the exiting step.
The fact that the results of an action are only sensed at the
following step implies that a state cannot be entered and exited at
the same step. However, for a self-looping transition, a state can be
exited and reentered in one step.
Since a transition can perform a set of actions simultaneously in an arbitrary order, and multiple transitions can be enabled at a single step, due to orthogonal states, race conditions and synchronisation must be considered.
Race conditions arise when the value of an element (condition or data item) is modified more than once, or is both modified and used, in a single step.
If an element is both modified and used in the same step, the value that the element had at the beginning of the step is used to evaluate all expressions that depend on it. A modified result is never used to evaluate expressions in the same step as the modification. Thus, the race condition is resolved.
If an element is to be modified multiple times during a single step (for example, by different assignments to the same data items in concurrent transitions in orthogonal states), the system cannot resolve this non-determinism and is in an illegal state. The design of the system must prevent these cases.
As defined in
| Event | Occurs when: | Notes |
|---|---|---|
| en(S) | State S is entered. | - |
| ex(S) | State S is exited. | - |
| entering | State is entered. | This applies only to the static reactions field in the state definition. |
| exiting | State is exited. | This applies only to the static reactions field in the state definition. |
| st(A) | Activity A is started. | - |
| sp(A) | Activity A is stopped. | - |
| ch(V) | The value of data item expression is changed. | V is a string or numeric expression. |
| tr(C) | The value of condition C is set to TRUE (from FALSE). | - |
| fs(C) | The value of condition C is set to FALSE(from TRUE). | - |
| rd(V) | Data item V is read. | - |
| wr(V) | Data item V is written. | V is a primitive data item. |
| tm(E,N) | N clock units passed from last time event E occurred. | N is a numeric expression. Unless noted otherwise, the real timeout value is implementation or policy-dependent. |
| Event | Occurs when: |
|---|---|
| E[C] | E has occurred and condition C is TRUE. |
| not E | E did not occur. |
| E1 and E2 | E1 and E2 occurred simultaneously. |
| E1 or E2 | E1 or E2, or both occurred. |
The operations are presented in descending priority order. Parentheses are used to alter the evaluation order.
| Condition | TRUE when: | Notes |
|---|---|---|
| in(S) | System is in state S. | - |
| ac(A) | Activity A is active. | - |
| hg(A) | Activity A is suspended. | - |
| EXP1 R EXP2 | The value of the expression EXP1 and EXP2 satisfy the relation R. | When expressions are numeric, R may be: =, /=, > or <. When they are strings, R may be: = or /=. |
| Condition | TRUE when: |
|---|---|
| not C | C is not TRUE. |
| C1 and C2 | Both C1 and C2 are TRUE. |
| C1 or C2 | C1 or C2, or both are TRUE. |
The operations are presented in descending priority order. Parentheses are used to alter the evaluation order.
| Action | Performs: | Notes |
|---|---|---|
| E | Generate the event E. | E is a primitive event. |
| tr!(C) | Assign TRUE to the condition C. | C is a primitive. |
| fs!(C) | Assign FALSE to the condition C. | C is a primitive. |
| V:=EXP | Assign the value of EXP to the data item V. | V is a primitive (numeric or string) data item. |
| st!(A) | Activate the activity A. | - |
| sp!(A) | Terminate the activity A. | - |
| sd!(A) | Suspend the activity A. | - |
| rs!(A) | Resume the activity A. | - |
| rd!(V) | Read the value of data item V. | V is a primitive data item. |
| wr!(V) | Write the value of data item V. | V is a primitive data item. |
| Action | Performs: | Notes |
|---|---|---|
| A1; A2 | Simultaneously perform the actions A1 and A2. | - |
| If C then A1 else A2 end if | If condition C is TRUE, perform action A1, otherwise perform A2. | The else part is optional. |
| When E then A1 else A2 end when | If event E occurred when the action is issued, perform action A1, otherwise perform A2. | The else part is optional. |
Atomic numeric expressions may be one of the following:
The following compound numeric expression may appear in state charts:
The operations are presented in descending priority order. Parentheses may be used to alter the evaluation order.
String expressions may be one of the following:
Please note that the html version of this specification may contain formatting aberrations. The definitive version is available as an electronic publication on CD-ROM from The Open Group.
| Contents | Next section | Index |