ペトリネットについて（3）

(1)

ペトリネットについて (3)

篠沢昭二・松島俊章

先月号で.PN の基本的な解析手法である到達可能木，標号機械(略称 TM) ，および線形代数手法について述べ Tこ. 本号では，通信システムの実際例をとりあげ，その P N 記述と解析，およびタイムベトリネット(略称 TPN) による発火時間条件の考察について述べることにする.

8 .

コマンド再送機能をもっ片方向伝送本誌 7 月号第 2 節で，簡単な 2 局間データ通信，すなわちコマンドの流れ方向が一方向に固定されている片方向伝送の通信制御手順について述べ，その PN 記述を図 2 に示した.しかし，実際の通信制御手11原のモデル化として図 2 は適切であろうか? たとえば，現実には，伝送中に信号が外乱等により減衰したり消滅し，相手局にコマンドやレスポンスが達しないこともおこりうるのである.しかるに，図 2 に示した PN において，これらの事象や状態はモデル化されておらず，また仮りに，位置れあるいはれから標号が消滅することを記述したとしても，それに対する正常動作への復帰機能を記述していない.このことは，図 2 の位置 P2 あるいは h から標号が消滅したとき，図 6 に示した TMに関し図 9 の点線で示す遷移がおこり，れああるいはあ P. という停止状態に陥り，修復不能であることからも明らかであろう. そこで，実際の通信システムにおいては，このような停止状態に陥り，修復不能にならないように，片方向伝送では一般に次局側にレスポンス受信監視用タイマをもっている.そしてこの受信監視用タイマにより次局側はコマンド送信後，ある設定時間以上経過してもレスポンスが受信できない，いわゆるタイムアウトが発生したとき，コマンドの再送を行なっている[1 ].このコマンド再送機能をもっ片方向伝送の PN 記述を図 10 に示す [2

J

[3

J

.

図 10において，位置 P， -P. ，転位九 -t7 はそれぞれ，図2における位置ム -P.. 転位九 -t. と同じ意味をもっており，新たに書き加えられている PIO は，伝送路外の状態を意味している.また，転位 t8• らはそれぞれ，コマンド伝送中の信号喪失，レスポンス伝送中の信号喪失を意味し，転位 t，o はコマンドの再送信を意味している. ここで，図 10の PN の TMを書いてみると，図 11 となり，明らかに停止状態は存在せず修復可能となっている. P

,

P

,

P.

j

t

p，から標号喪失 p，から標号喪失 p，如何一ーーーーーーーーーーー-p ， p ，唾ーーー-ー一ーー"、

1

t p

,

p

,

1

t J 9 9 p h p h h d HIll--+ 町 11111V 吋 h 出‘ふ‘ p' 日'pa 日ヨ pa 込司 4F h7 、‘，、 P ‘、、戸巴司 a ，‘‘，、 pa 、、，弘、号 +i4\V\γ/ ~標一〈 j~i/ 、 i_{コ-、、，} 、 J 旬、、， \失一\\/ \喪一\、/ 7 ‘ 7h ‘』 E P 、 -sp 、 6 川旬、 444 3 t s t D t 9 t pill-+ 匹 Ill11 ， MIll--v 川・ pill-+ 4 4 1 1 p p p

,

p

,

トに標号カ入る

PIP9P" しのぎわしょうじ日本電気情報処理営業支援本部まつしまとしあき日本電気伝送通信事業部図 B 図 2 のPN で P2P6 から標号が爽失したときの TM

5

4

2

(2)

さて，以上に述べたコマンド再送を行 /一、 1, なう片方向伝送において，タイムアウト(、 12u 〉ー一一一一一時聞をどれほどに設定するか，あるいは，〆いったん設定された時間が正しいか否かを検証することは，しばしば重要な問題となる.このようなタイムアウト時間の設定に関する問題は， PN の各転位に発火時刻許容範囲を指定した TPN (7月号第 4 節参照)を用いることにより，次のように換言され明確化される.すなわち， r転位九 -t7の発火時刻j許容範囲が， t, ; ['1"，*，'1"，紳J t₂;['I"2* ，'I"2紳] t7 ; ['1"7*, '1"7紳] と知ることができるとき，転位 t，o の発火時刻許容範囲 ['1"'0*， '1"'0帥]を決定，あるいは検証せよ. J という問題となる. t

,

図 10 通信制御手順の PN 記述(コマンド再送機能有) ここで， TPN の概念を把握するために，図 10に示すのは，標号がれあるいはれに存在する聞に限られ，l.-PN の各転位に発火時刻許容範囲を付した Tのは，標号がれあるいはれに存在する聞に限られ，l.-PN においたがってら，らの発火時刻に関する制限条件はおのずとて，発火列が t， t2tat5t6t7 九としたときの発火時刻許容範算出され，次のようになる. 簡と発火時刻をタイムチャートで例示しておく. ら ['1"6ホ， '1"6料 J=[0，'I"2**J さて，図 10 の転位九~んの発火時刻許容範囲が上記の t. ; ['1".*, '1".料J=[0，'I"6帥] ように既知であるとすると，らあるいはらが発火可能なまた，タイムアウト時聞は，伝送路外に信号が喪失さ J t j t 9 町 Illi--v 円 Ill111V 叫

時

4111 ト 1vuh--ト 1+M11111申1ill--v p-p. ，但 a ， ug

3 :

0 4 F O S I r -! papA1 れド ll mAil--，知 11111V I a -o P P 1 : t p.p.p

,

P

,

P.

トんる

P

,

P

,

P. 函 11 図 10の PN の TM 1981 年 9 月号 1

,

れず正常に通信が行なわれたときの 1 次局のコマンド送信からレスポンス受信までに要する最大時間より大きく設定されねばならない.これを図 10の TPNt 上で対応させて考えると，九発火後 ρ'0 に標号が存在することなく，らが発火するまでの最大時間，すなわち位置わが標号を連続して保持する最大時聞を求め，この時間より大きな値を'l'10* とすればよいことがわかる . p，O に標号が存在せずに，あが標号を連続して保持している問の発火列としては，図 11 の TM より下記の 6 通りがあり，それぞれの場合について， P7 の標号保持最大時間を h1max， … h6maxで表わすと， ①発火列t₂t_at_st₆の場合 h, max= 'I"z柿+'I"a紳 +'1"5柿 +'1"6帥 ②発火列 t2tat， t5t6の場合

h.~.v=J h， m日 ('1"，*出向料のとき)

2 ロlRX-l

l

'1"2紳十九料 +'1"，榊 +'1"6材 ('1"，**>'1"5紳のとき) ③発火列 t2t3t5t， t6の場合 ha max=h2 max ④発火列ら t2t3t5t6の場合 h, max=r'**- 'Z"5*-'6本 -'1"7*- '1"，*+'1"2**+ '1"3**+ T 料 +'1".**5 寸-'1"6 (ただし， ".*-"5柿 -'1"6材一'1"7料 -'1"，紳註 O が必要) ⑤発火列九九九九九 t6 の場合

h5max= 'I"，**-'I"5*- 'I"6*- 'I"7本 -'1"，事 +'1"2柿+'I"a紳+

(55)

5

4

3

(3)

礼子間信する，いわゆる複合局間の両方向伝送の通信制御手)1頃について.

P N

により記述，解析を行なうことにする. 1 つの複合局は，データリンク制御に関し相互に対等の責任をもっており，片方向伝送における l 次局機能と 2 次局機能をあわせもっている.しかし，一般には，伝送路の物理的な容量の制約から，一方の局でのコマンド送信とレスポンス送信の競合は避けるようにし重要度の高いコマンドあるいはレスポンスを優先して送信するようにしている.このような重要度を判定し，優先順位を決定するのは，図 1 におけるリシクレベルより高位のレベルのプロトコルである. このような何方向伝送の伝送制御手順の PN 記述を図 13 に示す.ただし，実際には両方向伝送においてもタイムアウトによるコマンド再送を行なっているが，簡単のためにここではこの機能を記述していない.図 13 中で位置および数字添字は，それぞれ図 2 の対応する数字添字をもっ位置および転位と同じ意味をもち，図中の位置，転位の英添字 A. B は，複合局 A. 複合局 B を表わす添字である. また PlOA. Pl0B_{はそれぞれ .A 局側. B 局側のリング} レベルより高位のレベルの状態を示す位置であり，コマンドとレスポンスの競合を避け，優先順位をつける役割を果たしている. さて，この図 13 の PN のままで TMを考えてもよいのであるが，これは非常に複雑な TM となる. (興味ある読者は試みられたい.図 11 の TMに比し飛躍的に複雑になることが，おわかりいただけると思う.

)

しかるに. PN では. PN 中のあるまとまった位置や転位の集合を 1 つの位置で、置き換えたりつの転位で置き換える階層的記述 (hierarchical description) が可能である [5 J. たとえば，図 13 の PN 中の(イ)の部分を 1 つの位置 ρA に，また(ロ)の部分を位置 ρB に置き換えることができる.図 13 の PN にこのような置換を施すことにより，その TMは簡単化され図 14のようになる. 図 14から明らかなように，置換された ρA.ρB の中が活性であり，かっ有界(安全)て、あるならば，図 13 の PN は活性であり，かつ有界(安全)であることがわかる. 発火能性 /ア，1 事一--t'! ιμ 発発発発火 j< 火火発火時刻j許容範囲と発火時刻のタイムチャート例 (図 10における発火列んら ts

t

5

t

6 t，らに対して)

hfllL、ん

/I11 也、ら //11 也、お /ll 、九 /fit-h//lL 『む τt一一一一一同

.

τs τf ら発火 MM h

発火図

研 lv 火発 t'.**+料，~~-rt'6 (ただし， 1:"'*-'Z"'5榊-t'6料-t'，柿-t'1榊ミ O が必要) ⑥発火列 t， t2tSt，九九の場合 h6ffiロ =hsmax

したがって t'lO*>MAX [h1ffiax• h2回ax，ん max ，

h5ffiロ]が t10 の発火時刻に対する制限条件であり，求めるタイムアウト時聞はこの条件式より決定すればよい. 一方，図11 の TM より，図 10 の TPN が活性であり，かっ有界(安全)であることが確認できるが，参考のために付録に線形代数手法によりこの TPN の不変性，無矛盾性を示しておく. また，ここで述べた例はコマンド再送のみを考慮した PN モデノレであるが，文献 [4J には伝送路からレスポンスも喪失したときのレスポンス再送の PN モデルが述べられている. さらに，実際の通信制御手JI闘では，いくつかのコマンドが連続して送信されることもあるが，このようなコマンド列，レスポンス列の送受信を記述した PN モデルも報告されている [2].

9 .

両方向伝送の PN 記述前節では，コマンドの流れ方向が一方向に固定されている片方向伝送について. TPN による考察を行なったが，本節では，コマンドおよびレスポンスの両方を送受九発火むすぴ

(4)

pf ，ー、 I ，豆、 I~ “目、 PU; 、， A t'1

p

P

B7 t (，" B'~ _p_"

_,

図 13 両方向伝送における伝送制御手順の PN 記述 7 月号から 3 固にわたり，ベトリネットで用いられる

t

PN も TPN も，その図形表現上の差違はなく，転用語の意味，および通信制御手順を例に，ペトリネット位に発火時間条件が付されているか杏かの違いだけであの記述・解析の具体例を述べてきた. る.また，換言すると PN は，そのすべての転位の発火本文では誌面の関係で言及できなかったが，論理回路時刻許容範囲が [0 ，∞]の TPN であるといえる. のモデル化にもペトリネットは応用されている [6

J

[付録] 生起行列 [ 7].また，形式言語の研究の立場からペトリネットを

P

l

P

2 P

s

p

, P5 ρ6

P

1 P

s

P

9 P

lO 扱った論文や [8J[9J ， PN の複雑さ，到達可能性の決 c=九一 1

1

。。。。。。。定問題を，オートマトンによりアプローチした論文 [10J

t

z

o -1

。。。。

o -1

。 [11J も多い. t_s。

o -1

。。。。。筆者の考えるところ，ペトリネットの長所は，システ t, 。。

o -1

。。。。。ムの構文 (syntax) 記述能力の高さと，その形式的な解 t

₅

。。。

o -1

。。。。析が可能である点にあると思う.ペトリネットによりシ t

₆

。。。。

o -1 -1

。。ステムの意味 (semantics) を記述する試みも種々行なわ t

1

。。。。。

o -1

。。れているが，現在のところ，決定的なものはないように

t

s

o -1

。。。。。。。思われる. t. 。。。。

o -1

。。。今後，動作の順序関係の複雑なシステムのモデル化技 t

1

0

。。。。。。。

o -1

術として，さらに応用範囲が広がることが予想されるが，問(列数 )=10 η( 階数 )=7 同時に，より形式化されたペトリネットの解析法の発展基本解: (nl- r.) 伺 =3 個が期待される. (完) x1

=

(J

1 1 0 1 1 0 1 0

1)

t

(

5

7 )

5

4

5

(5)

A

!,

+pupt

/、

p勾ApPp~pPO pi'pPp叩~p~ t号。f

Communication

Protocols-Implicaｭ

t

i

o

n

o

f

a

Theoretical

Study

,I

EEE T

r

a

n

s

.

o

n

COM

,

Vo

1 .

COM

-24

,

No.9

,

p

.

1

0

3

6 -1043

,

S

e

p

t

.

1

9

7

6 〆、/、

口]嵩忠雄他:タイムペトリネットに関する判定問題一通信制御手 11債の検証への一考察一，信学論 (D) ，

Vo

1 .

J-60-D

,

No.

lO,

p

.

822-829

,

O

c

t

.

1

9

7

"pl'p~pPphpPo pfPAPPPBptop

!

1

p

'

i

pPpPpfop

P

o

〆、/、/、

plp，Bp品pll， p~p手p~pRp i'op Th p~pApPp~piÕpIt p~prp九p見

!~ I 〆、〆、」ム

ptprpBpi'op旦 ptpfpPpPp~p~ pfPAPPp~p 見 [4J 森将豪他 Time

P

e

t

r

i

Net に関する判定問題，信学技報，

AL

7

6 -

3

1 .

July 1

9

7

6 、/、〆

[

5 J J

.

L

.

Peterson :

P

e

t

r

i

Nets

,

Compuｭ

t

i

n

g

Surveys

,

Vo

1 .

9

,

No. 3

,

p

.

223-252

,

t

?

B tl' ptprprp品p品 p~ptprptop品

、〆

図 14 図 13 の PN の TM X2

=(0 0 1 1 0 0 0 0 1

O)t X8

=(0 1 1 0 1

1 ー 1

0 0

l)t 完全 p 回路たとえば， X=2X1+ X2- X8(2

1 2 1

1 1

1 2 1

I)t であり，完全 p-回路存在.したがって，不変. 生起行列の転置行列

Ct

n2( 列数 )=10 r2( 階数 )=9 基本解: (n2-r2) 個個 Yl=

(

t

1 1 1 1 1 1 1 1

l)t 完全 t 回路存在し，無矛盾参考文献

[

1 J

日本規格協会: JIS ハンドプック，情報処理 1980

[2 J P

.

M. Merlin

,

D. J

.

Farber :

Recoverability

A

!9

!~

Sept.1977

[

6 J D. Misunas :

P

e

t

r

i

Nets and Speed

Independent Design

,

Comm. ACM

,

Vo

1 .

16 ,

No. 8

,

p

.

4

7

4 -481

,

Aug.1973

[7 J A. A. Khan

,

G. S

.

Hura

,

H. Singh

,

and

N. K. Nanda :

S

t

a

t

e

Equation Representation

o

f

Logic Operations Through a P

e

t

r

i

Net

,

P

r

o

c

.

o

f

t

h

e

IEEE

,

Vo

1 .

69 ,

No. 4

,

pp.485-487

,

April 1

9

8

1 [

8 J M.

Hack :

P

e

t

r

i

n

e

t

languages

,

Computation

Structures Group Memo 124

,

P

r

o

j

e

c

t

MAC

,

M.

1 .

T. ,

June 1

9

7

5 [9J

菊野享他:ペトリネットのサプグラスの表現能力比較ーベトリネット言語による比較一，信学論

(D)

,

Vo

1 .

J

--6

0-D

,

No. 11

,

pp.975-981

,

Nov.

1

9

7

7 [

1

0 J

松浦敏雄他:セーフペトリネットに関する等価性ならびに簡単化判定問題の計算複雑さ，信学論 (D) ，

Vo

1. J-63-D

,

No.6

,

pp.501-508

,

June 1

9

8

0

[11] 嵩忠雄他:

P

e

t

r

i

net の Reachability に関する二，三の問題，信学技報，

AL

75-12

,

June 1

9

7

5