ペトリネットとは？プレース・トランジション・トークンの意味を初心者向けにわかりやすく解説

はじめに

ペトリネットとは、複数の処理が並行して動くシステムや、処理の順序・同期・競合などを表現するためのモデルです。

特に、

• ・複数の処理を同時に実行できる
  ・ある処理が終わるまで次の処理を待つ
  ・一つの資源を複数の処理が取り合う

といった状況を図で表すのに向いています。

一言でいうと、

「処理できる状態と処理の発生を、○・棒・●を使って表現するモデル」

と考えると分かりやすいでしょう。

この記事では、

・ペトリネットとは何か
・プレース・トランジション・トークンとは何か
・トランジションが発火するとはどういう意味か
・並行処理や同期をどのように表すのか
・状態遷移図とは何が違うのか

について、会話を中心に初心者向けにわかりやすく解説します。

ペトリネットとは？

並行して動く処理を表現できるモデル

ペトリネットは、システムの状態や処理の流れを表すためのモデルだよ。特に、複数の処理が同時に進むようなシステムを表すのが得意なんだ。

フローチャートみたいなもの？

処理の流れを表すという意味では似ているけれど、ペトリネットは並行処理や同期、資源の競合なども表しやすいところが特徴だよ。

ペトリネットは、1960年代にカール・アダム・ペトリ（Carl Adam Petri）によって提案されたモデルです。

コンピュータシステムでは、一つの処理だけが順番に動くとは限りません。

例えば、

• CPUが複数の処理を実行する
• 複数の利用者から同時にアクセスされる
• 工場で複数の工程が並行して進む
• 複数の処理が同じデータや装置を利用する

といった状況があります。

こうした並行・同期・競合を含む処理を表現・分析するために、ペトリネットが利用されます。

ペトリネットをレストランで例えてみよう

「料理を作れる状態」を図で表す

レストランで料理を作る場合を考えてみよう。

例えば、お客さんから注文を受けて料理を提供するまでに、

1. ・注文を受ける
   ・料理を作る
   ・料理を提供する

という流れがあるとします。

ただし、料理を作るには、
注文が入っていること
が必要です。

注文が一件もないのに、勝手に料理を作るわけではありません。
ペトリネットでは、
「注文が待っている」
という状態と、
「料理を作る」
という処理を別々の記号で表します。

例えば、イメージとしては次のようになります。

○ 注文待ち
   ●
   ↓
│料理する│
   ↓
○ 完成

●が「注文が一件存在している」ことを表します。
その●があることで「料理する」という処理を実行できます。
処理が実行されると、●は次の場所へ移ります。

処理前

○ 注文待ち
●
 ↓
│料理する│
 ↓
○ 完成


処理後

○ 注文待ち
 ↓
│料理する│
 ↓
○ 完成
●

●が移動することで、注文待ちから料理完成に状態が変わったことを表すんだね。

そう。この●がペトリネットでは重要なんだ。

ペトリネットを構成する3つの基本要素

ペトリネットを理解するためには、まず次の3つを覚えましょう。

• ・プレース
  ・トランジション
  ・トークン

この3つが基本です。

プレースとは？

○で表す「状態」や「条件」

プレース（Place）は、一般的に○で表します。

プレースは、

• ・状態
  ・条件
  ・資源の存在場所

などを表します。

例えば、

○ 注文待ち

というプレースなら、

「注文が待っている状態」

を表します。

ほかにも、

• ・商品が倉庫にある
  ・プリンターが使用可能
  ・データを受信済み
  ・作業Aが完了
  ・CPUが利用可能

などの状態をプレースで表現できます。

トランジションとは？

棒や長方形で表す「処理」

トランジション（Transition）は、一般的に棒や長方形で表します。

例えば、

│料理する│

というトランジションなら、

「料理を作る処理」

を表します。

プレースが状態を表すのに対し、トランジションは状態を変化させる処理やイベントを表します。

トークンとは？

●で表す現在の状態

トークン（Token）は、一般的に●で表します。

トークンはプレースの中に配置され、

「現在、その状態や条件が成立している」

ことを表します。

例えば、

○ 注文待ち
●

なら、

「現在、処理を待っている注文がある」

と考えられます。

注文が2件あれば、

○ 注文待ち
●●

のように複数のトークンを置くこともできます。

プレース・トランジション・トークンを整理

○が状態、棒が処理、●が現在の状態を表すんだね。

まずはその3つを覚えれば、ペトリネットの図がかなり読みやすくなるよ。

アークとは？

プレースとトランジションは、アーク（Arc）と呼ばれる矢印で接続します。

例えば、

○ → │処理│ → ○

という形です。

アークによって、

• ・どの状態から処理を始めるのか
  ・処理後にどの状態になるのか

を表します。

基本的には、

プレース → トランジション

または、

トランジション → プレース

という形で接続します。

プレース同士やトランジション同士を直接つなぐものではありません。

マーキングとは？

トークンの配置が「現在の状態」

ペトリネットでは、各プレースにトークンがどのように配置されているかをマーキング（Marking）と呼びます。

例えば、

プレースA：●
プレースB：
プレースC：●●

という状態なら、

• プレースAに1個
  プレースBに0個
  プレースCに2個

のトークンが存在します。

このトークン配置全体が、その時点でのシステムの状態を表します。

プレースだけを見るのではなく、●がどこにあるかまで含めて現在の状態なんだね。

ペトリネットではトークンの配置が変わることで、システムの状態変化を表すんだ。

発火とは？

トランジションが実行されること

ペトリネットで重要な言葉に発火（Firing）があります。

発火とは、

トランジションが実行され、トークンの配置が変化すること

です。

例えば、

○ A
●
 ↓
│処理X│
 ↓
○ B

というペトリネットがあるとします。

処理Xが発火すると、

Aにあったトークンが消費され、Bにトークンが生成されます。

発火前

A：●
B：なし


発火後

A：なし
B：●

つまり、

「状態A → 処理X → 状態B」

という変化を表します。

トランジションはいつ発火できる？

必要なトークンがそろったとき

トランジションはいつでも発火できるの？

いや。入力側のプレースに必要なトークンがあるときだけ発火できるんだ。

例えば、

○ 材料A ● ─┐
             ├→ │組立│ → ○ 完成品
○ 材料B ● ─┘

というペトリネットを考えます。

「組立」という処理には、

• 材料A
• 材料B

の両方が必要です。

両方にトークンがある場合、

材料A：●
材料B：●

なので「組立」を実行できます。

ところが、

材料A：●
材料B：なし

の場合は材料Bが不足しているため、組立は実行できません。

このように、

入力側の条件がすべて成立したとき、トランジションが発火可能になる

と考えます。

ペトリネットで同期を表す

複数の処理が終わるまで待つ

ペトリネットが得意とする表現の一つが同期です。

例えば、

• ・書類を作成する
  ・上司の確認を受ける

という二つの作業が完了してから、申請を提出するとします。

○ 書類完成 ● ─┐
                ├→ │申請する│ → ○ 申請済み
○ 上司確認 ● ─┘

申請するには、

• ・書類が完成している
  ・上司確認が終わっている

という二つの条件が必要です。

どちらか一方だけでは申請できません。

複数の条件がそろうまで次へ進まない、という処理を表しやすいんだね。

そう。それがペトリネットの大きな特徴の一つだよ。

ペトリネットで並行処理を表す

二つの処理を同時に進められる

次のような仕事を考えてみましょう。

注文を受けた後、

• 料理を作る
• 飲み物を準備する

という二つの処理を並行して行います。

             → ○ 料理準備 → │料理する│
○ 注文受付
             → ○ 飲物準備 → │飲物を作る│

二つの処理が互いに依存していなければ、並行して進められます。

ペトリネットでは、このような並行性（Concurrency）を視覚的に表現できます。

これは、単純な一本道のフローチャートにはない重要な特徴です。

ペトリネットで競合を表す

一つの資源を取り合う場合

次は、プリンターを考えてみましょう。

一台のプリンターを、

• ・Aさん
  ・Bさん

の二人が使いたいとします。

プリンターを表すプレースに、トークンが一つだけあります。

             ┌→ │Aさん印刷│
○ プリンター ●
             └→ │Bさん印刷│

トークンが一つしかないため、AさんとBさんが同時にそのプリンターを使用することはできません。

Aさんが使えば、Bさんは待つ必要があります。

このように、一つの資源を複数の処理が取り合う状態を競合（Conflict）として表現できます。

なぜトークンが重要なの？

トークンは単に現在位置を示すだけじゃないんだね。

そう。資源の数を表すこともできるんだ。

例えば、利用できるプリンターが3台なら、

○ 利用可能プリンター
●●●

と表せます。

印刷処理を一つ開始すると、トークンを一つ消費します。

●●●
 ↓
印刷開始
 ↓
●●

印刷が終了すると、利用可能なプリンターが戻るため、トークンが再び増えます。

●●
 ↓
印刷終了
 ↓
●●●

つまりトークンは、

• ・現在の状態
  ・処理できる件数
  ・利用可能な資源

などを表すためにも利用できます。

ペトリネットの簡単な例

自動販売機でジュースを購入する場合を考えてみましょう。

○ 待機中
●
 ↓
│お金を入れる│
 ↓
○ 購入可能
●
 ↓
│ボタンを押す│
 ↓
○ 商品提供
●

最初は「待機中」にトークンがあります。

お金を入れると、

待機中 → 購入可能

へ状態が変わります。

さらにボタンを押すと、

購入可能 → 商品提供

へ変わります。

このように、トークンの移動によってシステムの状態を表現できます。

トークンがない場合はどうなる？

例えば、

○ 購入可能
 ↓
│商品を出す│

という構造があっても、「購入可能」にトークンがなければ商品を出す処理は発火できません。

つまり、

「その処理を実行するための条件が成立していない」

状態です。

ペトリネットでは、

トークンがあるかどうか

を見ることで、その処理が実行できるか判断できます。

ペトリネットでデッドロックを表せる

お互いが相手の資源を待ってしまう

ペトリネットは、デッドロック（Deadlock）の分析にも利用できます。

デッドロックとは、複数の処理がお互いに必要な資源を待ち続け、どの処理も先へ進めなくなる状態です。

例えば、

• ・処理Aはプリンターを持っていて、スキャナーを待つ
  ・処理Bはスキャナーを持っていて、プリンターを待つ

という状態です。

処理A
プリンター確保
     ↓
スキャナー待ち


処理B
スキャナー確保
     ↓
プリンター待ち

どちらも相手が持っている資源を待っているため、永久に進めなくなる可能性があります。

ペトリネットでは、トークンの配置と発火可能なトランジションを調べることで、

「どの処理も発火できない状態にならないか」

を分析できます。

ペトリネットと状態遷移図の違い

どちらも状態変化を表すが得意分野が違う

状態を表すなら、状態遷移図でもいいんじゃないの？

単純な状態変化なら状態遷移図で十分なことも多いよ。ただ、並行処理や同期を表すならペトリネットが便利なんだ。

状態遷移図は、

一つの状態から別の状態へどのように移るか

を表すのに向いています。

例えば、

停止 → 起動中 → 稼働中 → 停止

という状態変化です。

一方、ペトリネットでは、

• ・複数状態が同時に成立する
  ・複数処理が並行して動く
  ・複数条件がそろってから処理する
• 同じ資源を複数処理で共有する

といった状況を表しやすくなっています。

ペトリネットとアクティビティ図の違い

UMLのアクティビティ図も、処理の流れや並行処理を表現できます。

そのため、ペトリネットと似て見えることがあります。

ペトリネットは単なる図ではなく、数学的なモデルとして分析できる点が特徴です。

まとめ

ペトリネットとは、複数の処理が並行して動くシステムや、同期・競合・資源共有などを表現・分析するためのモデルです。

主に、

• ・プレース
  ・トランジション
  ・トークン
  ・アーク

を使ってシステムを表現します。

プレースは状態や条件を表し、トランジションは処理やイベントを表します。
そして、プレースの中に置かれるトークンによって、現在どの状態が成立しているのかを表します。

トランジションの入力側に必要なトークンがそろうと、そのトランジションは発火できます。
発火すると、入力側のトークンが消費され、出力側のプレースへトークンが生成されます。

ペトリネットが特に得意なのは、

• ・並行処理
  ・同期
  ・資源の競合
  ・デッドロック

などを表現することです。

「○＝プレース、棒＝トランジション、●＝トークン」

「必要なトークンがそろうとトランジションが発火する」

という基本ルールを理解しておきましょう。

ペトリネットって難しそうだったけど、○・棒・●の意味が分かれば読みやすいね。

そう。○がプレース、棒がトランジション、●がトークンだよ。

トークンが必要な場所にそろったら、トランジションが発火して次のプレースへ移るんだね。

そうだね。

それなら、二つの作業が終わるまで待つ同期や、一台のプリンターを取り合う競合も表せるわけか。

バッチリ。ペトリネットは「処理の順番を見る図」というより、複数の状態や処理がどう関係して動くかを見る図と考えると分かりやすいよ。

試験ではまず「○＝状態、棒＝処理、●＝トークン」を覚えておけばよさそうだね。

うん。そこに「必要な●がそろったら発火する」を加えれば、基本問題にはかなり対応しやすくなるよ。

クマノくらげ

X

難しいIT用語やビジネス用語を、できるだけ身近な例えで解説するブログです。 「専門用語を見ると眠くなる人」でも読めるように、画像や会話形式を多めにしています。 AWS12冠達成済み。