マークされたグラフ

特定の種類のペトリネット

マークグラフとは、各プレイスにそれぞれ1つの入ってくるアークと1つの出ていくアークが存在するペトリネットです。 ^[1]^{: 561}これは、競合は発生しませんが、同時実行は発生する可能性があることを意味します。数学的には：。マークグラフは、主にマルチプロセッサマシンの内部プロセス状態など、同時に実行される操作を数学的に表現するために使用されます。このクラスのペトリネットは、各プレイスがエッジ、各遷移がノードとなるグラフという一般的な表現方法にちなんで名付けられています。 $\forall p\in P:|p\bullet |=|\bullet p|=1$

用途

マークされたグラフは主に、設計の特定の特性を数学的に導き出せるように、並行メカニズムを数学的に表現するために使用されます。

例

この例では、プロセスが遷移T1で分岐し、T4で同期されるマークグラフを示しています。その間に、T2とT3という2つの操作が非決定的に実行されます。実際には、ペトリネットは非常に非決定的であるため、これらの操作が全く実行されないこともあります。しかし、この非決定的な特性を持つ理由はこれではなく、並列コンピューティングではどのプロセス／スレッドが最初に完了するか、つまりどの操作が速く実行されるかを常に判断できないという現実の経験を模倣するためです。これは、現実世界での I/O待機に起因する場合もあれば、プロセス／スレッドに与えられたパラメータが異なるだけの場合もあり得ます。

参照

参考文献

^ ジョンソンバウ, リチャード; 村田忠雄 (1982年10月). 「ペトリネットとマークグラフ ― 並行計算の数学的モデル」 .アメリカ数学月刊. 89 (8): 552– 566. doi :10.1080/00029890.1982.11995494.

[1] ジョンソンバウ, リチャード; 村田忠雄 (1982年10月). 「ペトリネットとマークグラフ ― 並行計算の数学的モデル」 .アメリカ数学月刊. 89 (8): 552– 566. doi :10.1080/00029890.1982.11995494.