UML 2 をベースにした pxt-mstate の設計
UML 2 の仕様 - the Unified Modeling Language (UML), revision 2
本記事は、UML仕様のver.2.5.1を参照しています。
https://www.omg.org/spec/UML/2.5.1/PDF
参考チュートリアル - UML 2 Tutorial | Sparx Systems
→ UML 2 Tutorial - State Machine Diagram
Abstract Syntax - Behavior StateMachines
必要なクラスの抜粋
pxt-mstate に必要と思われるクラスを抜粋しました。
Pseudostate クラスに関しては、 その kind が initial のみを取り扱うので、 InitialPseudostate クラスに置き換えています。
pxt-mstate のUML設計
StateMachineとRegion
pxt-mstate では、submachineの概念を省略しています。
その為、StateクラスがStateMachineクラスを集約することはありません。そこで、RegionクラスをStateMachineクラスに置き換え、Regionクラスを省略します。
FinalState
FinalStateクラスは、Transitionクラスから見て、targetにはなりますが、sourceにはなりません。そこで、FinalStateクラスの継承元をVertexクラスに変更します。同時に、pxt-mstate では、FinalStateクラスのentry、doActivity、exitが不要ですので、このように継承関係を変更するのは好都合です。
InitialPseudostate
疑似状態であるInitialPseudostateクラスは、FinalStateクラスの疑似クラスであると考えます。pxt-mstateを設計する上での補足情報として残しておきます（クラスとして存在しません）。
Transition
pxt-mstateでは、start(default)コマンドで、ステートマシンを開始します。
これをTransitionクラスで行うと考えた場合、sourceは、FinalStateクラス(InitialPseudostateクラス)であり、targetは、引数のdefaultであると考えることができます。
また、そのTransitionクラスのインスタンスでは、effect、trigger、guardが不要です。
そこで、trigger等の代わりに、start(default)コマンドで状態遷移する為のStarterTransitionクラス(疑似クラス)をpxt-mstateを設計する上での補足情報として追加します（クラスとして存在しません）。
pxt-mstateの内部構造
pxt-mstate の run-to-complition
WaitPoint で、トリガーやdoカウンターを待ち、doProcで、一連のrun-to-complitionステップを処理する。
実装上のヒント
switch-caseで、遷移元が複数ある状態（エントリーポイント）へジャンプする。
doProcでEvalTriggerへジャンプし、WaitPointになったら、一連の処理を終了し、次のdoProcを待つ。
| # | 状態 | 遷移元 | エントリーポイント |
|---|---|---|---|
| 0 | constructor | 1 | |
| 1 | WaitPoint | 2 | WaitPoint |
| 2 | EvalTrigger | 2 | EvalTrigger |
| 3 | EvalDoCounter | 1 | |
| 4 | EvalCompletion | 2 | EvalCompletion |
| 5 | Reached | 2 | Reached |
| 6 | Traversed | 1 | |
| 7 | Completed | 1 | |
| 8 | DoAtFirst | 1 |
ソースコード
mstate.defineState(StateMachines.M0, "DoAtFirst", function () {
mstate.descriptionUml("- doActivityの実行(初回:counter=0)")
mstate.declareEntry(function () {
})
mstate.declareSimpleTransition("", "EvalCompletion")
})
mstate.defineState(StateMachines.M0, "WaitPoint", function () {
mstate.declareSimpleTransition("doProc", "EvalTrigger")
mstate.descriptionUml("トリガーやdoカウンターを待つ")
})
mstate.defineState(StateMachines.M0, "EvalDoCounter", function () {
mstate.descriptionUml("- doカウンターの評価")
mstate.descriptionUml("- doActivityの実行(counter=1..)")
mstate.descriptionsUml(["実行あり", "実行なし"])
mstate.declareStateTransition("", ["EvalCompletion", "WaitPoint"], function () {
})
})
mstate.defineState(StateMachines.M0, "Reached", function () {
mstate.descriptionUml("- exitActionの実行")
mstate.declareEntry(function () {
})
mstate.declareSimpleTransition("", "Traversed")
})
mstate.defineState(StateMachines.M0, "EvalTrigger", function () {
mstate.descriptionUml("- トリガーの評価(trigger,guard)")
mstate.descriptionUml("- effectの実行と遷移先の決定")
mstate.declareEntry(function () {
})
mstate.descriptionsUml(["遷移先あり/target=遷移先", "遷移先なし"])
mstate.declareStateTransition("", ["Reached", "EvalDoCounter"], function () {
})
})
mstate.defineState(StateMachines.M0, "EvalCompletion", function () {
mstate.descriptionUml("- completion transitionの評価(gurad)")
mstate.descriptionUml("- effectの実行と遷移先の決定")
mstate.declareEntry(function () {
})
mstate.descriptionsUml(["遷移先あり/target=遷移先", "遷移先なし"])
mstate.declareStateTransition("", ["Reached", "EvalTrigger"], function () {
})
})
mstate.defineState(StateMachines.M0, "constructor", function () {
mstate.declareSimpleTransition("", "WaitPoint")
mstate.descriptionUml("- 現在状態=FinalState\\n(StarterTransition)")
})
mstate.defineState(StateMachines.M0, "Traversed", function () {
mstate.descriptionUml("- 現在状態=(target)")
mstate.descriptionUml("- doカウンターのリセット")
mstate.declareEntry(function () {
})
mstate.declareSimpleTransition("", "Completed")
})
mstate.defineState(StateMachines.M0, "Completed", function () {
mstate.descriptionUml("- entryActionの実行")
mstate.declareEntry(function () {
})
mstate.declareSimpleTransition("", "DoAtFirst")
})
mstate.exportUml(StateMachines.M0, "constructor", false, true)
completion transitionの永久ループ問題と解決策
次々と連続する状態遷移で、 completion transition が繰り返されると、 WaitPoint を経由しない 永久ループになる場合があり、 run-to-complition が途切れなくなるという問題がある。
解決策として、DoAtFirst 実行後の EvalCompletion が、WaitPoint を待ってから行われるようにすればよく、isFirst変数 で WaitPoint からの遷移先を切り替えるようにする。
ソースコード
mstate.defineState(StateMachines.M0, "DoAtFirst", function () {
mstate.descriptionUml("- doActivityの実行(初回:counter=0)")
mstate.declareEntry(function () {
})
mstate.descriptionUml("/isFirst=true, raiseRunToCompletion()")
mstate.declareSimpleTransition("", "WaitPoint")
})
mstate.defineState(StateMachines.M0, "WaitPoint", function () {
mstate.descriptionUml("isFirst=true/isFirst=false")
mstate.declareSimpleTransition("doProc", "EvalCompletion")
mstate.descriptionUml("isFirst=false")
mstate.declareSimpleTransition("doProc", "EvalTrigger")
mstate.descriptionUml("- 初回completionを待つ(isFirst)")
mstate.descriptionUml("- トリガーやdoカウンターを待つ")
})
mstate.defineState(StateMachines.M0, "EvalDoCounter", function () {
mstate.descriptionUml("- doカウンターの評価")
mstate.descriptionUml("- doActivityの実行(counter=1..)")
mstate.descriptionsUml(["実行あり", "実行なし"])
mstate.declareStateTransition("", ["EvalCompletion", "WaitPoint"], function () {
})
})
mstate.defineState(StateMachines.M0, "Reached", function () {
mstate.descriptionUml("- exitActionの実行")
mstate.declareEntry(function () {
})
mstate.declareSimpleTransition("", "Traversed")
})
mstate.defineState(StateMachines.M0, "EvalTrigger", function () {
mstate.descriptionUml("- トリガーの評価(trigger,guard)")
mstate.descriptionUml("- effectの実行と遷移先の決定")
mstate.declareEntry(function () {
})
mstate.descriptionsUml(["遷移先あり/target=遷移先", "遷移先なし"])
mstate.declareStateTransition("", ["Reached", "EvalDoCounter"], function () {
})
})
mstate.defineState(StateMachines.M0, "EvalCompletion", function () {
mstate.descriptionUml("- completion transitionの評価(gurad)")
mstate.descriptionUml("- effectの実行と遷移先の決定")
mstate.declareEntry(function () {
})
mstate.descriptionsUml(["遷移先あり/target=遷移先", "遷移先なし"])
mstate.declareStateTransition("", ["Reached", "EvalTrigger"], function () {
})
})
mstate.defineState(StateMachines.M0, "constructor", function () {
mstate.declareSimpleTransition("", "WaitPoint")
mstate.descriptionUml("- 現在状態=FinalState\\n(StarterTransition)")
mstate.descriptionUml("- isFirst=false")
})
mstate.defineState(StateMachines.M0, "Traversed", function () {
mstate.descriptionUml("- 現在状態=(target)")
mstate.descriptionUml("- doカウンターのリセット")
mstate.declareEntry(function () {
})
mstate.declareSimpleTransition("", "Completed")
})
mstate.defineState(StateMachines.M0, "Completed", function () {
mstate.descriptionUml("- entryActionの実行")
mstate.declareEntry(function () {
})
mstate.declareSimpleTransition("", "DoAtFirst")
})
mstate.exportUml(StateMachines.M0, "constructor", false, true)
同一周期で実行される振る舞い
同一の周期内で、状態遷移が繰り返されないように、WaitPointを経由するようにしました。それでも、状態遷移が起こった際には、 (遷移元の)exitActionと（遷移先の）entryAction、doActivitryが同一の周期内で連続して実行されます。
この連続した実行がどのような結果をもたらすのかを十分に考慮する必要があります。
【参考文献】ミーリ・ムーアタイプの状態遷移図
実行するアクションにより、その結果（出力）がどのように異なるのか（遅延するのか）を次の書籍で解説しています。
組み込みエンジニアのための状態遷移設計手法
引用メモ
UML 2 の仕様 - the Unified Modeling Language (UML), revision 2
UML仕様のver.2.5.1を参照しています。
https://www.omg.org/spec/UML/2.5.1/PDF
引用の( ..)φメモメモ
14 StateMachines
14 StateMachines
p.305 (347), https://www.omg.org/spec/UML/2.5.1/PDF
14.1 Summary - 概要
14.1 Summary
The StateMachines package defines a set of concepts that can be used for modeling discrete event-driven Behaviors using a finite state-machine formalism.
...
p.305 (347), https://www.omg.org/spec/UML/2.5.1/PDF
Havid Harel氏の「ハレルの状態遷移図」（ハレルチャート）
14.1 Summary
...
The specific form of finite state automata used in UML is based on an object-oriented variant of David Harel’s statecharts formalism. (However, readers who are familiar with that formalism should note that there is a small number of semantic differences that distinguish the UML version from the original.)
p.305 (347), https://www.omg.org/spec/UML/2.5.1/PDF
14.2.3.2 Regions - リージョン
14.2.3.2 Regions
p.307 (349), https://www.omg.org/spec/UML/2.5.1/PDF
It may have its own initial Pseudostate as well as its own FinalState.
| glossary | 用語 |
|---|---|
| initial Pseudostate | 開始状態（疑似） |
| FinalState | 終了状態 |
14.2.3.4 States - 状態
14.2.3.4 States
p.308 (350), https://www.omg.org/spec/UML/2.5.1/PDF
14.2.3.4.3 State entry, exit, and doActivity Behaviors - 状態の振る舞い
14.2.3.4.3 State entry, exit, and doActivity Behaviors
p.309 (351), https://www.omg.org/spec/UML/2.5.1/PDF
14.2.3.6 FinalState - 終了状態
14.2.3.6 FinalState
p.312 (354), https://www.omg.org/spec/UML/2.5.1/PDF
14.2.3.7 Pseudostate and PseudostateKind - 疑似状態
14.2.3.7 Pseudostate and PseudostateKind
p.312 (354), https://www.omg.org/spec/UML/2.5.1/PDF
| glossary | 用語 |
|---|---|
| initial | 開始状態 |
| choice | 選択状態 |
14.2.3.8 Transitions - 状態遷移
14.2.3.8 Transitions
p.314 (356), https://www.omg.org/spec/UML/2.5.1/PDF
A Transition is a single directed arc originating from a single source Vertex and terminating on a single target Vertex (the source and target may be the same Vertex), which specifies a valid fragment of a StateMachine Behavior. It may have an associated effect Behavior, which is executed when the Transition is traversed (executed).
| glossary | 用語 |
|---|---|
| Transition | 状態遷移 |
| source | 遷移元(状態) |
| target | 遷移先(状態) |
| effect | エフェクト（振る舞い） |
| traverse | 遷移する（実行する） |
Transitions are executed as part of a more complex compound transition that takes a StateMachine execution from one stable state configuration to another. The semantics of compound transitions are described below.
In the course of execution, a Transition instance is said to be:
- reached, when execution of its StateMachine execution has reached its source Vertex (i.e., its source State is in the active state configuration);
- traversed, when it is being executed (along with any associated effect Behavior); and
- completed, after it has reached its target Vertex.
| glossary | 用語 |
|---|---|
| reached | 遷移着手 |
| traversed | 遷移中 |
| completed | 遷移完了 |
14.2.3.8.3 Completion Transitions and completion events - 完了による状態遷移
14.2.3.8.3 Completion Transitions and completion events
p.314 (356), https://www.omg.org/spec/UML/2.5.1/PDF
| glossary | 用語 |
|---|---|
| Completion Transition | 完了時遷移 |
14.2.3.9 Event Processing for StateMachines - 内部のイベント処理
14.2.3.9.1 The run-to-completion paradigm - run-to-completion パラダイム
14.2.3.9.1 The run-to-completion paradigm
p.316 (358), https://www.omg.org/spec/UML/2.5.1/PDF
The processing of Event occurrences by a StateMachine execution conforms to the general semantics defined in Clause 13.
Upon creation, a StateMachine will perform its initialization during which it executes an initial compound transition prompted by the creation, after which it enters a wait point.
In case of StateMachine Behaviors, a wait point is represented by a stable state configuration.
It remains thus until an Event stored in its event pool is dispatched.
This Event is evaluated and, if it matches a valid Trigger of the StateMachine and there is at least one enabled Transition that can be triggered by that Event occurrence, a single StateMachine step is executed.
A step involves executing a compound transition and terminating on a stable state configuration (i.e., the next wait point).
This cycle then repeats until either the StateMachine completes its Behavior or until it is asynchronously terminated by some external agent.
StateMachines can respond to any of the Event types described in Clause 13 as well as to completion events (see above).
NOTE. As explained above, completion events have priority and will be dispatched ahead of any pending Event occurrences in the event pool.
Event occurrences are detected, dispatched, and processed by the StateMachine execution, one at a time.
NOTE. The order of event dispatching is left undefined, allowing for varied scheduling algorithms.
This cycle is referred to as the run-to-completion paradigm, and the corresponding StateMachine step is called a run-to-completion step.
Run-to-completion means that, in the absence of exceptions or asynchronous destruction of the context Classifier object or the StateMachine execution, a pending Event occurrence is dispatched only after the processing of the previous occurrence is completed and a stable state configuration has been reached.
That is, an Event occurrence will never be dispatched while the StateMachine execution is busy processing the previous one.
This behavioral paradigm was chosen to avoid complications arising from concurrency conflicts that may arise when a StateMachine tries to respond to multiple concurrent or overlapping events.
| glossary | 用語 |
|---|---|
| cycle, run-to-completion paradigm | パラダイム（サイクル） |
| step, 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 corresponding Event type is not in any of the deferrableTriggers lists of the active state configuration, the dispatched Event occurrence is discarded and the run-to-completion step is completed trivially.
Due to the presence of orthogonal Regions, it is possible that multiple Transitions (in different Regions) can be triggered by the same Event occurrence.
The order in which these Transitions are executed is left undefined.
Each orthogonal Region in the active state configuration that does not contain nested orthogonal Regions (i.e., a “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.
| glossary | 用語 |
|---|---|
| consumed | 消費, トリガーなどの発生イベントが全てなくなった状態 |
| completed | 完了, run-to-completionのステップが完了した状態 |
As mentioned above, it is possible for multiple mutually exclusive Transitions in a given Region to be enabled for firing by the same Event occurrence.
In those cases, only one is selected and executed. Which of the enabled Transitions is chosen is determined by the Transition selection algorithm described below.
During a Transition, a number of actions Behaviors may be executed.
If such a Behavior includes a synchronous invocation call on another object executing a StateMachine, then the Transition step is not completed until the invoked object method completes its run-to-completion step.
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 using a monitor.
IMPLEMENTATION NOTE. Run-to-completion is often mistakenly interpreted as implying that an executing StateMachine cannot be interrupted, which, of course would lead to priority inversion issues in some time-sensitive systems.
However, this is not the case; in a given implementation a thread executing a StateMachine step can be suspended, allowing higher-priority threads to run, and, once it is allocated processor time again by the underlying thread scheduler, it can safely resume its execution and complete its event processing.
13 Common Behavior
13.1 Summary
This clause specifies the core concepts underlying all behavioral modeling in UML.
Structural models of Classifiers in UML define the allowable instances that may exist at any point in time, what values their StructuralFeatures may have and how those instances may be related to each other.
Behavioral modeling, on the other hand, models how these instances may change over time.
UML provides Behavior, Event, and Trigger constructs to model the corresponding fundamental concepts of behavioral modeling.
Behavior is the basic concept for modeling dynamic change.
Behavior may be executed, either by direct invocation or through the creation of an active object that hosts the behavior.
Behavior may also be emergent, resulting from the interaction of one or more participant objects that are themselves carrying out their own individual behaviors.
Dynamic behavior results in events of interest that occur at specific points in time.
Such events may be implicit, occurring on the change of some value or the passage of some interval of time.
They may also be explicit, occurring when an operation is called or an asynchronous signal is received.
The occurrence of an event may then trigger new behavior, or change the course of already executing behavior.
Explicit events thus provide the basic mechanism for communication between behaviors, in which an action carried out in one behavior, such as calling an operation or sending a signal, can trigger a response in another behavior.
The remainder of this clause further details the fundamental UML modeling mechanisms of Behaviors, Events and Triggers.
These mechanisms then provide the framework for the specification in the following clauses of various complete UML behavioral modeling constructs.
13.2 Behaviors
13.2.1 Summary
This sub clause introduces the framework for modeling behavior in UML. The concrete subtypes of Behavior, described in subsequent clauses, then provide different mechanisms to specify behaviors.
A variety of behavioral specification mechanisms are supported by UML, including:
- StateMachines that model finite automata (see Clause 14)
- Activities defined using Petri-net-like graphs (see Clause 15)
- Interactions that model partially-ordered sequences of event occurrences (see Clause 17).
These behavioral specification mechanisms differ in their expressive power and domain of applicability.
This means that not all behaviors can be described by each of the mechanisms. Nevertheless, many behaviors can be described by one or more of the mechanisms, in which case the choice of mechanism is one of convenience, or, alternatively, multiple mechanisms can be used to provide different models of the same behavior.