Petri-gráfok alkalmazása véges automaták és protokollok modellezésére PAPP G Y Ö R G Y Nemzetbiztonsági Hivatal
Összefoglalás A protokollok implementálása, verifikálása és tesztelése során szükséges egy könnyen programozható, és modulárisan bővíthető matematikai modell alkalmazása. A protokollok leírására használt jelenlegi matematikai modellek nem rendelkeznek ezekkel a tulaj donságokkal. A nemzetközi szabványok például a protokollokat vé ges automatákkal definiálják. A cikk meg kívánja mutatni, hogyan transzformálható a véges automata modell a Petri-gráfos modellre, ami a fenti tulajdonságai miatt a protokollok egyik legalkalmasabb leíró modellje. Segítségével ugyanis egyszerűen valósítható meg a különböző protokoll funkciók kompozíciója. B á r m i l y e n rendszer vagy folyamat t e r v e z é s e , vizsgála ta, m ű k ö d é s é n e k t e s z t e l é s e egy alkalmas m o d e l l m e g a l k o t á s á v a l é s annak t ö b b s z i n t ű e l e m z é s é v e l v a l ó s u l meg. A v i z s g á l a t h a t é k o n y s á g a a m o d e l l o p t i m á l i s k i v á l a s z t á s á t ó l függ. A m o d e l l l é t r e h o z á s á n a k e l s ő d l e ges szempontjai, hogy h ű e n írják le a v i z s g á l a n d ó rendszert, a v i z s g á l a t h o z f e l h a s z n á l t s e g é d e s z k ö z ö k viszonylag e g y s z e r ű e n k e z e l h e t ő k , az adott rendszer p a r a m é t e r e i n e k b ő v ü l é s e i h e z , v á l t o z á s a i h o z j ó l igazo dok legyenek. I l y e n m e g f o n t o l á s b ó l a m o d e l l e k á l t a l á ban m a t e m a t i k a i m o d e l l e k szoktak l e n n i , melyeknek az e l e m z é s e s z á m í t á s t e c h n i k a i s e g é d e s z k ö z ö k k e l v a l ó s í t h a t ó meg. A p r o t o k o l l o k v e r i f i k á l á s a , i m p l e m e n t á l á s a é s tesz t e l é s e s o r á n sokszor o k o z gondot, hogy kisebb m é r t é k ű v á l t o z t a t á s a teljes p r o t o k o l l ú j r a é r t é k e l é s é t teszi s z ü k s é g e s s é . E z nagy e r ő - é s i d ő r á f o r d í t á s t i g é n y e l . I g é n y van e z é r t olyan m a t e m a t i k a i m o d e l l a l k a l m a z á sára, amelyik e g y s z e r ű e n kezelhető, k ö n n y e n gépesít h e t ő é s m o d u l á r i s a n b ő v í t h e t ő illetve s z ű k í t h e t ő . A protokollok l e í r á s á b a n jelenleg használt matema t i k a i m o d e l l e k n e k a h á t r á n y a , hogy azok n e m rendel keznek a m o d u l á r i s b ő v í t h e t ő s é g t u l a j d o n s á g á v a l é s így nehezen v e r i f i k á l h a t o k . A n e m z e t k ö z i s z a b v á n y o k p é l d á u l a p r o t o k o l l o k a t v é g e s a u t o m a t á k k a l definiál ják. A véges automata modell dinamikus vizsgálata azonban a m o d u l á r i s b ő v í t h e t ő s é g b o n y o l u l t s á g a m i a t t n e h é z k e s . A p r o t o k o l l o k s a j á t o s s á g a a l a p j á n viszont a b ő v í t h e t ő s é g r e az á l l a n d ó i g é n y szerinti i g a z o d á s é r d e k é b e n s z ü k s é g van. M é g s e m k e l l elvetni a r é g i m a t e m a t i k a i m o d e l l t , az f e l h a s z n á l h a t ó ú j a b b , az e l ő b b felsorolt t u l a j d o n s á g o k k a l r e n d e l k e z ő , alkalmasabb m o d e l l b e v a l ó á t a l a k í t á s hoz. M e g m u t a t j u k m i k é p p e n v a l ó s í t h a t ó m e g a transz f o r m á l á s . P é l d á k o n k e r e s z t ü l illusztráljuk, hogy az e g y m á s s a l k o m m u n i k á l n i t u d ó rendszerek p r o t o k o l l -
Beérkezett: 1990. III. 7. (H)
Híradástechnika,
XLI.
évfolyam,
1990. 12.
szám
PAPP
GYÖRGY
1979-ben végzett a Budapesti Műszaki Egyetem villamos mérnöki Karán, majd a Bel
ügyminisztériumban kezdett dolgozni. Kutató-fejlesztő mérnökként elsősorban mik roprocesszoros vezérlő beren dezések fejlesztésével és számí tástechnikai rendszerek kidol gozásával foglalkozott. 1986ban oklevelet szerzett a BME Távadatfeldolgozó Szakmér nöki Szakon. Azóta intenzív kutató munkát végez a számí tógépes hálózatokba történő illegális beavatkozás felfedésé nek területén. Fő kutatási té mája: a Petri hálók elemzése és a védelmi modell megte remtése.
j a i n a k l e c s e r é l é s é v e l hogyan a l a k u l á t a m o d e l l é s így az e l e m z é s t á r g y a . A P e t r i - g r á f o s m o d e l l s e g í t s é g é v e l egyszerűen megvalósítható a k ü l ö n b ö z ő típusú proto k o l l f u n k c i ó k k o m p o z í c i ó j a . B i z o n y í t j u k , hogy a p r o t o k o l l o k egyik legalkalmasabb l e í r ó m o d e l l j e a P e t r i gráf modell. A modell számítógépre viteléhez a Petri h á l ó m á t r i x a l a k j á t h a s z n á l j u k fel. A p r o t o k o l l m o d e l l j é n e k m e g a l k o t á s a s o r á n bemutatjuk milyen lépések k e l j u t u n k el egy m á r i s m e r t s z á m í t ó g é p l e í r ó mate matikai modelltől, a véges a u t o m a t á k állapot-átmenet g r á f j á n a k t r a n s z f o r m á l á s a s e g í t s é g é v e l az e g y m á s s a l k o m m u n i k á l n i képes számítógépek Petri hálós leírásá hoz. A s z á m í t ó g é p e k ö s s z e k a p c s o l á s a s o r á n az e g y m á s hoz e l k ü l d ö t t adatokat, u t a s í t á s o k a t , k é r é s e k e t , v á l a szokat v a l a m i l y e n k o m m u n i k á c i ó s f o l y a m a t b a n s z a b á l y o z z á k . E z t a k o m m u n i k á c i ó s folyamatot protokollnak nevezzük [ISO-84]. A s z á m í t ó g é p e k egymással t ö r t é n ő kommunikációja tehát a számítógépek kompozíci ójával v a l ó s u l meg. így, ha a s z á m í t ó g é p m o d e l l j é t v é ges a u t o m a t a k é n t é r t e l m e z z ü k , a p r o t o k o l l n e m m á s , m i n t a v é g e s a u t o m a t á k olyan k o m p o z í c i ó j a , a h o l a v é ges a u t o m a t á k v a l a m i l y e n t ö m e g k i s z o l g á l á s i soron, vagy h á l ó z a t o n k e r e s z t ü l k o m m u n i k á l n a k e g y m á s s a l . A s z á m í t ó g é p e k f o r m á l i s l e í r á s á n a k legalacsonyabb szintjén v é g e s a u t o m a t á v a l ( F S M F i n i t e State M a c h i n e ) m o d e l l e z z ü k a s z á m í t ó g é p e t . A v é g e s auto m a t a [ D E M - 8 5 ] a n e v é t o n n a n kapta, hogy v é g e s s z á m ú b e l s ő állapottal rendelkezik és a m ű k ö d é s e s o r á n a u t o m a t i k u s a n á t k e r ü l v a l a m i l y e n k ü l s ő folyamat ha t á s á r a az egyik b e l s ő á l l a p o t b ó l a m á s i k b e l s ő á l l a p o t ba. A v é g e s a u t o m a t á t ezek a l a p j á n á l l a p o t g é p n e k is nevezik. A k é s ő b b i e k b e n a m o d e l l e l e m e i r e hivatkoz va gyakran h a s z n á l j u k az F S M e l ő t a g o t , m e g k ü l ö n b ö z 301
tetve, hogy v é g e s a u t o m a t a e l e m r ő l van s z ó . (Pl.: FSM-állapot.) L e í r á s á h o z ö t v á l t o z ó t d e f i n i á l n a k : ( Q , 2, A , S, V), ahol; Q:
az á l l a p o t o k v é g e s halmaza?
2:
Q = { q q , . . q } m az á l l a p o t o k s z á m a . egy v é g e s b e m e n e t i á b é c é . 1 ;
2
= {^í; °i, •• n} a bemenetek száma. egy v é g e s k i m e n e t i á b é c é . A = {A,, A , .. A } k a k i m e n e t e k s z á m a Q x J - Q k ö v e t k e z ő á l l a p o t l e í r ó függvény, a m i egy a k t u á l i s á l l a p o t h o z é s egy bemenethez r e n d e l i s
A:
m
a
2
í:
R/R
n
H592-1
k
a következő állapotot.
1. ábra. Bináris számok kettes komlemensének kiszámítása véges automatán
(q» °k) = H ) i = 1 . . m , k = 1 . . n Q x*2 -> A k i m e n e t i f ü g g v é n y , a m i egy á l l a p o t h o z é s egy b e m e n e t h e z e g y é r t e l m ű e n h o z z á r e n d e l egy kimenetet. 5
T:
(q» O = ÍM i = 1 m, k = 1 .. n A v é g e s a u t o m a t a s e g í t s é g é v e l p r o t o k o l l o k a t is le t u d u n k í r n i , azonban n e m a legalkalmasabb m o d e l l i m p l e m e n t á l á s r a és verifikálására. A k o m m u n i k á l ó rendszerek t a n u l m á n y o z á s a s o r á n eljutottak ahhoz a f e l i s m e r é s h e z , hogy m á s fajta m a t e m a t i k a i m o d e l l e k s e g í t s é g é v e l lehet a p r o t o k o l l o k a t tervezni é s elemez n i . A m o d e l l e k k ö z ü l az egyik legalkalmasabbnak t ű n ő a C. P e t r i n é m e t m a t e m a t i k u s r ó l elnevezett P e t r i - g r á f m o d e l l , amelyet az 1962-ben b e n y ú j t o t t doktori disszertációjában publikált először [PETRT-62]. A P e t r i - g r á f alapfogalmait j ó n é h á n y s z e r z ő m á r ismer tette, e z é r t ezekre n e m t é r ü n k k i [ N A G Y - 7 9 ] . A t r a n s z f o r m á c i ó m i a t t azonban s z ü k s é g van a g r á f ma t e m a t i k a i l e í r á s á r a . A P e t r i - g r á f m o d e l l -elemeihez a jobb megkülönböztetés é r d e k é b e n néha P N előtagot teszünk. (Pl.: P N - g r á f p o n t , P N - á t m e n e t . ) A P e t r i h á l ó l e í r á s a egy s z á m n é g y e s s e l t ö r t é n i k : C = ( P , T, I , O), ahol r
P:
1 ;
I:
2
2
s
v é g e s automata PETRi h á l ó s modellje
H592-3
CO = {Pj» - P h } a h o l i = 1 . . r . a k i m e n ő függvény, a m i leírja, m e l y i k á t m e n e t b ő l m e l y i k g r á f p o n t b a van i r á n y í t o t t ö s s z e k ö t é s . 1
O ( t ) = { p „ .. p } a h o l k = 1 . . r. k
3. ábra. A Petri háló külvilággal való kapcsolatának általános megközelítése gráfpontokkal
r
m e l y i k g r á f p o n t b ó l van i r á n y í t o t t ö s s z e k ö t é s . O:
kimenetek
bemenetek
a P e t r i h á l ó g r á f p o n t j a i n a k halmaza. P = { p p , .. p } s a g r á f p o n t o k s z á m a . az á t m e n e t e k halmaza. T = { t t , .. t } r az á t m e n e t e k s z á m a . a b e m e n ő függvény, a m i leírja, m e l y i k á t m e n e t b e 1 ;
T:
2. ábra. Bináris számsorozat paritásának meghatározása véges au tomatán
g
kimenetek
bemenetek
v é g e s automata
PETRI hálós Véges automaták modellezése Petri hálóval modellje A véges automata leggyakoribb m o d e l l e z é s e állapot á t m e n e t gráffal t ö r t é n i k . P é l d a k é n t n é z z ü k m e g a b i n á r i s s z á m kettes k o m p l e m e n s é n e k k é p z é s é t m e g v a l ó s í t ó v é g e s a u t o m a t a á l l a p o t - á t m e n e t gráfját (1. ábra). A g r á f b a n az á l l a p o t o k a t k ö r ö k k e l á b r á z o l j u k . A z át m e n e t i r á n y í t o t t é l é n a qj á l l a p o t b ó l qj á l l a p o t b a t ö r t é -
302
H592-Z, 4. ábra. A Petri háló külvilággal való kapcsolatának alternatív megközelítése gráfpontokkal Híradástechnika,
XLI.
évfolyam,
1990. 12.
szám
n ő á t m e n e t e n s z e r e p l ő o jh, j e l e n t é s e , hogy a g é p q ál l a p o t á b a n az „a" b e m e n e t h a t á s á r a „ A " k i m e n e t i v á l a s s z a l a q^ á l l a p o t b a j u t .
A P N á t m e n e t e i t az F S M - á l l a p o t o k b c m e n c t c k Descartes szorzata alkotja: T = { t , \ q e Q é s a e 2}
F o r m á l i s a n : S ( q ^ a) = qj é s r (q^ a,) = A , . A k ü l v i l á g g a l v a l ó b e m e n ő kapcsolatokat a b e m e n ő á b é c é , a k i m e n ő kapcsolatokat a k i m e n e t i á b é c é valósítja meg. A m á s i k p é l d á b a n (2. ábra) a b e m e n e t i á b é c é k r e az á l l a p o t g é p k i s z á m o l j a a p a r i t á s t . A véges automata modellje egyszerűen átalakítható a Petri hálós m o d e l l é [PET-81a]. Először modellezni kell a Petri h á l ó külvilággal való kapcsolatát. A Petri h á l ó á l t a l á b a n z á r t s t r u k t ú r a , a k ö r n y e z e t é t ő l elszige telt. A k ü l v i l á g g a l v a l ó kapcsolat á b r á z o l á s a k é t m ó d o n t ö r t é n h e t . A b e m e n e t e k e t é s a kimeneteket vagy P e t r i g r á f p o n t o k k a l ( P N - g r á f p o n t ) vagy P e t r i á t m e n e t e k k e l ( P N - á t m e n e t ) á b r á z o l h a t j u k (3. és 4. ábra). A két modell egymással egyenértékű. A továbbiakban mi az e l s ő t í p u s t fogjuk h a s z n á l n i [ P E T - 8 1 b ] . A transzfor m á c i ó alapgondolata a P e t r i h á l ó d e f i n í c i ó j á b ó l k ö v e t kezik [ P E T - 8 1 c ] . A z á l l a p o t - á t m e n e t g r á f n a k az ö s s z e s
ahol e l e m e i n e k s z á m a : r = m * n . A PN bemenetei a rendre képzett PNátmenctckhez az FSM-állapotok és az FSMb e m e n e t e k lesznek:
;
q
é s az
FSM-
a
I(tqa) = H ó } A P N k i m e n e t e i a r e n d r e k é p z e t t á t m e n e t e k b ő l az FSM következő állapot és kimeneti függvényei lesznek: O ( t . a) = {«(q, o), T(q, a) }. A t r a n s z f o r m á c i ó s s z a b á l y a l k a l m a z á s á v a l így m á r elkészíthető a véges a u t o m a t a - p é l d á k Petri hálós modellje. A z e l s ő p é l d a , a m i n e k á l l a p o t - á t m e n e t gráf j a az 1. á b r á n l á t h a t ó , egy olyan P e t r i g r á f o t e r e d m é nyez, amely nyolc P N - g r á f p o n t b ó l é s hat P N - á t m e n e t b ő l áll (5. ábra). q
f e l t é t e l e a P N - g r á f p o n t o k a t fogja m e g h a t á r o z n i . A z a z a P N - g r á f p o n t o k a t az F S M - b e m e n e t e k , az F S M g r á f p o n t o k é s az F S M - k i m e n e t e k u n i ó j a alkotja. A P N - á t m e n e t e k e t az á l l a p o t - á t m e n e t g r á f e s e m é nyei h a t á r o z z á k meg. E s e m é n y pedig gyakorlatilag az egyik F S M - á l l a p o t b ó l egy m á s i k F S M - á l l a p o t b a j u t á s p i l l a n a t á b a n van. E z az e s e m é n y egy P N - á t m e n e t t c l a z o n o s í t h a t ó . A P N - á t m e n e t b e m e n e t e i t az e s e m é n y e l ő f e l t é t e l e i fogják m e g h a t á r o z n i . A z egyik e l ő f e l t é t e l e az adott F S M - á l l a p o t , a m á s i k e l ő f e l t é t e l e pedig egy F S M - b e m e n e t , m i v e l F S M - á t m e n e t l é t r e j ö t t é h e z egy F S M - b e m e n e t m e g j e l e n é s é r e van s z ü k s é g . A P N á t m e n e t kimeneteit pedig a véges automata k ö v e t k e z ő á l l a p o t f ü g g v é n y e v a l a m i n t a k i m e n e t f ü g g v é n y e fogja meghatározni. Ezek a l a p j á n m e g á l l a p í t h a t ó , hogy a t r a n s z f o r m á c i ó h a t á s á r a a P N - á t m e n e t e k s z á m a megegyezik az F S M á t m e n e t e k , az F S M - á l l a p o t o k é s az F S M - k i m e n e t e k s z á m a i n a k ö s s z e g é v e l . A P N - á t m e n e t e k s z á m á t pedig az F S M - á l l a p o t o k é s az F S M - b e m e n e t e k s z á m á n a k szorzata fogja e r e d m é n y e z n i , m e r t az á t m e n e t e k e t az F S M - á l l a p o t o k é s az F S M - b e m e n e t e k Descartes szorzatából kapjuk.
5. ábra. Az I übra Petri hálós változata H a s o n l ó k é p p e n a 2. á b r á n s z e r e p l ő g r á f P e t r i g r á f m e g f e l e l ő j e is e l k é s z í t h e t ő . E z t a 6. ábra s z e m l é l t e t i . Első látásra szembeötlik a két modell-típus közötti k ü l ö n b s é g . Sokkal b o n y o l u l t a b b n a k l á t s z i k ugyanan nak a p r o b l é m á n a k a m e g f o g a l m a z á s a P e t r i m o d e l l -
E z t f o r m a i l a g felírva: ( Q , 2, A , Í , r ) - (P, T , I , O ) ahol a ( Q , 2, A, 5, r ) a v é g e s a u t o m a t á t ( F S M ) , a (P, T , I , O ) a P e t r i h á l ó t ( P N ) írja le. Q elemeinek s z á m a : m 2 elemeinek s z á m a : n A elemeinek s z á m a : k
P elemeinek s z á m a : s T elemeinek s z á m a : r
A j e l ö l é s e k n é l h a s z n á l t nyíl a t r a n s z f o r m á c i ó i r á n y á t jelzi. A P N g r á f p o n t j a i n a k ö s s z e s s é g e az F S M - á l l a p o t o k , az F S M - b e m e n e t e k é s az F S M - k i m e n e t e k u n i ó j a lesz: P = 2 u Q u A ahol e l e m e i n e k s z á m a : s = m + n + k. Híradástechnika,
XLI.
évfolyam,
1990. 12.
szám
H592-6 6. ábra. A 2. ábra Petri hálós változata 303
ben, m i n t
állapot-átmenet
modellben. Vajon
mégis
m o d e l l t , s ő t l e h e t ő s é g van a kettes k o m p l e m e n s é s a p a r i t á s k é p z é s é n e k s z e k v e n c i á l i s é s p á r h u z a m o s meg
m i é r t e l ő n y ö s e b b a Petri modell? A v á l a s z h o z v i z s g á l j u n k m e g egy ö s s z e t e t t e b b fela
v a l ó s í t á s á r a is. E z e k f i g y e l h e t ő k
m e g a 8. és a 9.
datot. N e t e g y ü n k m á s t , c s u p á n ö t v ö z z ü k a fenti k é t
ábrákon.
B á r a p é l d á k e g y s z e r ű e k voltak, m é g i s l á t h a
feladatot o l y a n f o r m á b a n , hogy a b e m e n ő b i n á r i s s z á
t ó b e l ő l e a P e t r i h á l ó m o d u l á r i s jellege, é s az e b b ő l
m o k kettes k o m p l e m e n s é n e k k i s z á m í t á s á n kívül v é
s z á r m a z ó e l ő n y ö k . E z azt j e l e n t i , hogy a P e t r i m o d e l l
g e z z ü k e l a p a r i t á s k é p z é s t is. E h h e z a feladathoz, ha
v i z s g á l a t á h o z a feladatot b á r m i l y e n m é l y s é g b e n lehet
elkészítjük
t á r g y a l n i , r é s z f e l a d a t o k r a osztani.
az á l l a p o t - á t m e n e t
gráfot,
gyakorlatilág
e l ö l r ő l k e z d j ü k e l az F S M - á l l a p o t o k l é t r e h o z á s á t , é s végül (7.
megkapunk
egy l á t s z ó l a g
független
modellt
ábra). Ezzel
Ez a transzformációs szabály egyszerűen gépesíthe t ő . A l e g e g y s z e r ű b b , ha a m o d e l l e k m á t r i x alakban fel írt f o r m á i t alkalmazzuk. A v é g e s a u t o m a t a á l l a p o t - á t
szemben s o k k a l e g y s z e r ű b b a P e t r i h á l ó b ó l
k i i n d u l v a e l k é s z í t e n i az ú j a b b igényt k i e l é g í t ő P e t r i
menet
gráfja
önmagában
szemléletes,
de
nehezen
g é p e s í t h e t ő . A l k a l m a s viszont a t á b l á z a t b a n megadott f o r m a . K é t t á b l á z a t k é s z í t h e t ő e l ( a m i t gyakran egy k ö z ö s t á b l á z a t b a n szoktak á b r á z o l n i ) , az egyik az álla pot-átmeneti táblázat, a másik a kimeneti táblázat. M i n d k é t t á b l á z a t n a k az oszlopaiba a v é g e s a u t o m a t a á l l a p o t a i t , soraiba p e d i g a bemeneteit t ü n t e t i k fel. A z állapot-átmenet táblázat elemei úgy kerülnek kitöltés re, hogy az adott oszlophoz ( F S M - á l l a p o t ) t a r t o z ó sor (FSM-bemenet) keresztező helyére a következő F S M á l l a p o t o t írják. E z g y a k o r l a t i l a g azt m u t a t j a m e g , hogy egy adott F S M - á l l a p o t b a n egy adott b e m e n e t i
elem
h a t á s á r a m e l y i k F S M - á l l a p o t b a f o g j u t n i az á l l a p o t g é p . A k i m e n e t i t á b l á z a t k e r e s z t e z ő helyei pedig az
H592-7 7. ábra. A kettes komplemens és a paritás egymás utáni megvaló sítása véges automatán
e l ő z ő m i n t á j á r a a k i m e n e t i elemeket fogják tartalmaz n i , vagyis adott F S M - á l l a p o t b a n k a p o t t adott F S M - b e m e n e t h a t á s á r a m i l y e n k i m e n e t i elemet, m i l y e n választ s z o l g á l t a t az á l l a p o t g é p . A k ö z ö s t á b l á z a t b a n a k i t ö l t e n d ő helyeken k ö z ö s e n szerepel a k ö v e t k e z ő á l l a p o t é s a k i m e n e t egy " / " j e l e l v á l a s z t á s á v a l . Példa egy közös állapot-átmenet és kimeneti táblázatra 0
[H 5 9 2 - 8 | 8. ábra. A kettes komplemens és a paritás egymás utáni megvaló sítása Petri hálón
2
qi
°\
qi/Ai
°2
q /-
°S
q-i/^
qi
2
qs
qi/A
2
12/^1
ql/A
2
qs/ 3
qaAt
qi/ 2
qsAj
qa/Aj
qs/ 3
qV 2
q.i/ i
A
5
A
°1 A
qi/A
q3/A
A
A
A
táblázat
első oszlopának
6
és második
sorának
k e r e s z t e z ő h e l y é n s z e r e p l ő " - " k i m e n e t azt j e l e n t i , hogy az á l l a p o t g é p az á l l a p o t - á t m e n e t s o r á n n e m ad kimeneti választ. A
két táblázat
számítógépre viteléhez
képezzünk
k é t m á t r i x o t . A z e l s ő m á t r i x legyen az á l l a p o t - á t m e n e t m á t r i x , az ú n . Q g a m m a m á t r i x , melynek elemei legye nek e g é s z s z á m o k - é s é r t é k k é n t v e g y é k fel az á l l a p o t átmenet
táblázatban
a
megfelelő
helyen
szereplő
k ö v e t k e z ő á l l a p o t o k indexeit. A m á s o d i k m á t r i x pedig legyen a k i m e n e t i m á t r i x , Q delta m á t r i x , melyet ha s o n l ó a n , a k i m e n e t i t á b l á z a t a l a p j á n k é p e z z ü n k é s ele
TH592-9I
m e i a k i m e n e t i t á b l á z a t b a n az adott helyen l é v ő k i m e
9. ábra. A kettes komplemens és a paritás párhuzamos megvalósí tása Petri hálón
netek indexei legyenek. M i n d k é t m á t r i x m é r e t e , m i n t
304
ahogy az k ö n n y e n b e l á t h a t ó m * n . Híradástechnika,
XLI.
évfolyam,
1990. 12. szám
A z állapot á t m e n e t i mátrix és a kimeneti felépítése a következő: Q gamma állapot átmeneti mátrix
Q delta kimeneti mátrix qi
q2
a * helyére a következő ál lapot sorszáma kerül
mátrix
q2
<\i
a # helyére a kimenet sorszáma kerül
M o s t vizsgáljuk m e g a P e t r i h á l ó l e í r á s á n a k m á t r i x alakját [ A N D - 8 3 ] . D e f i n i á l j u n k i t t is k é t m á t r i x o t . A z e l s ő legyen a k i m e n e t i m á t r i x , a m i t D m í n u s z m á t r i x nak h í v u n k a k é s ő b b i e k b e n . A m á s i k m á t r i x pedig le gyen a b e m e n e t i m á t r i x , a m i t D plusz m á t r i x n a k ne v e z z ü n k . M i n d k e t t ő m á t r i x szerkezete ugyanolyan, oszlopai a P e t r i h á l ó g r á f p o n t j a i legyenek, sorai pedig a Petri háló á t m e n e t e i . E l s ő megközelítésben a követ k e z ő t állítjuk. A D m í n u s z m á t r i x ( D " ) elemeit k é p e z z ü k úgy, hogy az adott á t m e n e t s o r á n a k m i n d a z o n osz lopaiba írjuk - 1 é r t é k e t , amelyeknek o s z l o p á h o z tar t o z ó g r á f p o n t o k h o z g r á f é i é r k e z i k . A m á t r i x t ö b b i ele m e legyen n u l l a . A D plusz m á t r i x o t pedig ú g y k é p e z z ü k , hogy az adott á t m e n e t s o r á b a írjunk a + 1 é r t é k e t , amelyik oszlophoz t a r t o z ó g r á f p o n t b ő i gráféi indul k i . A t ö b b i m á t r i x elem i t t is n u l l a legyen. L á t h a t ó , m i é r t n e v e z z ü k k i m e n e t i , illetve b e m e n e t i m á t r i x n a k a D m í n u s z illetve D plusz m á t r i x o t , ugyanis D m í n u s z m á t r i x a P e t r i h á l ó k i m e n e t i függvényét fogja leírni, a D plusz m á t r i x p e d i g a b e m e n e t i függvényt. A - 1 é s a + 1 s z á m é r t é k i t t azt j e l e n t i , hogy egy adott á t m e n e t é s egy adott g r á f p o n t k ö z ö t t c s u p á n egy g r á f é i létezik. E z a m o d e l l az e g y s z e r ű P e t r i h á l ó m o dellje. A kiterjesztett P e t r i h á l ó m o d e l l b e n a g r á f é l e k s z á m a e g y n é l t ö b b is lehet. M i v e l azonban a d i n a m i kus v i z s g á l a t h o z a kiterjesztett P e t r i h á l ó e g y s z e r ű e n átalakítható egyszerű Petri h á l ó b a [ H A C K - 7 4 ] , m i ezt a m o d e l l t fogjuk a t o v á b b i a k b a n alkalmazni. A bemeneti m á t r i x é s a k i m e n e t i m á t r i x f e l é p í t é s e a következő: D plusz bemeneti mátrix .Pi
D mínusz kimeneti mátrix
P2. Pi . Pír
Pl
P2
Pi Pn
ti t
;
D =
a * helyére +1 kerül ha a p, állapotból gráféi indul tj átmenetbe, egyébként értéke 0
a # helyére - 1 kerül, ha a tj átmenetből gráféi indul Pi állapotba, egyébként értéke 0
Híradástechnika,
1990. 12.
XLI.
évfolyam,
szám
A z e g é s z h á l ó s t r u k t i i r á j á t a k é t m á t r i x ö s s z e g e fog ja l e í r n i , a m i a k é s ő b b i e k b e n a P e t r i h á l ó v i s e l k e d é s é nek s z á m í t ó g é p e s e l e m z é s é h e z alkalmas. A P e t r i h á l ó d i n a m i k u s v i z s g á l a t a emnek a m á t r i x n a k a f e l h a s z n á l á sával t ö r t é n i k , a m i csak a h á l ó f e l é p í t é s é t , s t r u k t ú r á j á t jellemzi. A m ű k ö d é s t a háló töltéseinek áramlása, és annak folyamata fogja l e í r n i . A t ö l t é s e k m o z g á s a , a g y ú j t á s o k sorozata m i n d e n j e l l e m z ő p i l l a n a t b a n meg h a t á r o z h a t ó , a m i k e t a m o d e l l b e n az ú n . j e l ö l é s e k é s a j e l ö l é s v e k t o r o k í r n a k le. [ M U R - 7 6 ] E n n e k m a t e m a t i k a i alapja k i d o l g o z o t t , az e l e m z é s a m o d e l l m á t r i x alakjának felhasználásával elvégezhető. A Petri háló d i n a m i k u s v i s e l k e d é s é n e k v i z s g á l a t á v a l ebben a cikk ben n e m foglalkozunk, c s u p á n a P e t r i h á l ó f e l é p í t é s é nek s z á m í t ó g é p r e viteli l e h e t ő s é g é t e l e m e z z ü k . A transzformáció szabályai: A P N - g r á f p o n t o k a t ú g y k a p j u k , hogy r e n d r e v e s s z ü k az F S M - b e m e n e t e k , az F S M - á l l a p o t o k é s az F S M - k i menetek u n i ó j á t : P = 2u O u A
ahol P s z á m a : s = n + m + k.
A P N - á t m e n e t e k e l ő á l l í t á s á h o z k é p e z z ü k az F S M - á l l a p o t o k é s az F S M - b e m e n e t e k Descartes s z o r z a t á t : T = {t , q
ff
| qeQésffeS)
ahol T s z á m a = n * m .
A P N b e m e n e t i f ü g g v é n y e azon F S M - á l l a p o t o k é s F S M - b e m e n e t e k halmaza, a m i k b ő l a Descartes szor zatokkal k é p e z e t t P N - á t m e n e t e k b e g r á f é i é r k e z i k : I ( t „. a ) = í q,o
}.
A P N k i m e n e t i f ü g g v é n y e azon F S M - á l l a p o t á t m e n e t i függvény é r t é k e k é s F S M - k i m e n e t i f ü g g v é n y é r t é k e k halmaza, a m i k b e a Descartes szorzattal k é p e z e t t P N á t m e n e t e k b ő l gráféi i n d u l : O ( t , o) = { * ( q , a), T(q, q
a)}.
T e k i n t s ü n k egy m á l l a p o t b ó l , n b e m e n e t b ő l é s k k i m e n e t b ő l álló v é g e s a u t o m a t á t . í g y a Q g a m m a é s a O delta m á t r i x m * n -es lesz. Q g a m m a m á t r i x e l e m e i e g é s z s z á m o k , melyek a k ö v e t k e z ő á l l a p o t s o r s z á m á v a l egyeznek m e g . í g y é r t é k k é s z l e t e q elemeinek s z á m a , azaz 1 . . m . Q delta m á t r i x elemei s z i n t é n e g é s z s z á m o k , de é r t é k e i az F S M k i m e n e t e i n e k s o r s z á m á v a l egyezik meg. T e h á t é r t é k k é s z l e t e A elemeinek s z á m a , azaz 1 . . k. A t r a n s z f o r m á c i ó a l a p j á n l é t r e hozzuk a D plusz é s a D m í n u s z m á t r i x o t . A D plusz m á t r i x a P N b e m e n e t i függvényét írja le. Oszlopai a P N g r á f p o n t j a i , sorai a P N á t m e n e t e i . így n - t - m + k s z á m ú o s z l o p b ó l é s n * m s z á m ú s o r b ó l áll. E l e m e i m í n u s z e l ő j e l l e l s z e r e p l ő annyi s z á m é r t é k , a m e n n y i az adott sorban l e v ő á t m e nethez t a r t o z ó , adott oszlopban s z e r e p l ő g r á f p o n t o k b ó l k i i n d u l ó é l e i n e k s z á m a . T e h á t m i n d a D plusz, m i n d a D m í n u s z m á t r i x s * r -es, ahol s = n + m + k é s r = n * m. 305
DATA/ERROR, ACK/ ERROR
A m á t r i x o t ú g y alkotjuk m e g a t r a n s z f o r m á c i ó alap j á n , hogy a P N g r á f p o n t j a i rendre az F S M bemenetei, az F S M á l l a p o t a i é s az F S M k i m e n e t e i legyenek: Pi»Pn» P i - - P m , Pn+m+i-Pn+m+k- A P N á t m e n e t e i t pe d i g k é p e z z ü k a Descartes szorzatnak m e g f e l c l ó ' e n úgy, hogy e l s ő n e k az F S M b e m e n e t e i t r e n d r e r e n d e l j ü k az F S M á l l a p o t a i h o z : t = {!, q } , t = {CT, q } , . . t = {a q,},..t . n+
LOGODT/ERROR LOGOUT/ LÓGOTT
n+
t
n + 1
2
2
n + 2
2
2
LOGIN/ACK
LOGIN/ERROR
2
i n + 1
u
L0G0UT/L0G0UT
DATA/ACK
n m
= K , q } • A D plusz m á t r i x sor é s oszlop k é p z é s e teljesen sonlóan történik.
LQGIN/ERROR
m
ha
'ACK/DATA
C 3j
ACK/ACK(
X
DATA/ACK A
D m í n u s z m á t r i x elemeit m e g h a t á r o z ó
mus: ( a m á t r i x sor indexe - i , oszlop indexe -
algorit
j) Bemeneti á b á é : LOGIN, DATA, ACK, LOGOUT
-1
i = e * n + j e s e t é n , ahol ee(0..m-l),je(l..n)
[i> j ]
=
és i = e * n + f ; j = e + n + 1 e s e t é n , ahol e e ( 0 . . m - l ) , fe(l..n) egyébként
0
Kimeneti ábécé-. DATA, ACK, LOGOUT, ERROR Állapotok halmaza:
H 592-10 10. ábra. Hgy egyszerű protokoll véges automatán
f o r m á l i s a n : d ( t ^ qj, vagy qj) = - 1 e g y é b k é n t 0 A D plusz m á t r i x elemeit m e g h a t á r o z ó algoritmus:
D [iJ] = +
+ 1 i = ( e - l ) * n + f; j = n + 5 ( f , e) ahol ee(l..m),fe(l..n) ési = (e-1) e * n + f; j = n + m +r(f,e), ahol ee(l..m),fe(l..n) 0 egyébként
formálisan: d (t egyébként 0 +
CTi
OFF, WAIT, DATA, TRANSFER
LOGIN on XI
ACK
UAIT
XI X2
ERROR
DATA TRANSFER X3
*'/
«/
XI , . 'ERROR
XI
Y3,
X2 ,
LOGOUT
ACK XI
X3
X3 ,
ERROR
ERROR
ACK ACK
ERROR
L0SOUT
ACK
PATA
' DATA
'LOGOUT
H592-11
, ^ S f o , q,) vagy T(p- q ^ ) = 1 0
Protokoll modellezése és transzformálása E z e k u t á n t e k i n t s ü n k egy t r a n s z f o r m á c i ó s p é l d á t . P é l d á n k b a n v e g y ü n k egy e g y s z e r ű p r o t o k o l l n a k az ál l a p o t - á t m e n e t gráfját (10. ábra). A z á b r á n f e l t ü n t e t t ü k a v é g e s a u t o m a t a b e m e n e t i - é s k i m e n e t i á b é c é eleme it, v a l a m i n t az e g y s z e r ű p r o t o k o l l á l l a p o t a i t . A 11. áb rán p e d i g a p r o t o k o l l á l l a p o t - á t m e n e t t á b l á z a t a figyel h e t ő meg. A z egyszerű protokoll F S M változói: A z FSM-állapotok: q, = o f f q = wait q = datatransfer
11. ábra. A kommunikáló véges automaták állapot-átmenet táblá zata A z FSM-kimenetek: A , = ack A = error A = logout A = data 2
3
4
az F S M á l l a p o t - á t m e n e t i m á t r i x a ( Q d e l t a ) : q. q q 2 í í 1 3 3 1 2 3 1 1 1 2
°\ °2 °i °4
3
a mátrix belsejében levő számok q azonosító in dexei
2
3
az F S M k i m e n e t i m á t r i x a ( Q g a m m a ) : q. q2 q í 2 2 2 1 1 2 1 4
3
A z FSM-bemenetek: a = login <7 = data a = ack l
2
3
°i °2 °i °4
2
3
a mátrix belsejében levő számok A azonosító in dexei
3
<7 = logOUt 4
306
Híradástechnika,
XLI.
évfolyam,
1990. 12.
szám
A transzformáció után PN mátrixai: A D plusz, PN-bemeneti mátrix:
első véges automata állapotai
Pl P2 P3 P4 P5 P6 P7 P8 P9 PlO Pll tl h t u t
,
3
D =t
5
+
6
h h tio tll
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 0 0 1 1 0 0 1
1 0 0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 1 0 0 0 1 1 0
1 0 0 0 0 1 1 0 0 1 0 0
0 1 1 1 1 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1 0 0 0 1
0 0 0 0 0 0 0 0 0 0 1 0
0 -1 0 0 0 -1 0 0 0 -1 0 0
h U h D" = t t t
6
7
8
<9
ho tll tl2
0 0 0 0 -1 0 0 -1 0 0 0 0 -1 0 0 -1 0 0 0 0 -1 0 0 -1
-1 0 -1 0 -1 0 -1 0 0 -1 0 -1 0 -1 0 -1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 -1 -1 -1 -1
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
A D m á t r i x b ó l látszik, s z e r k e z e t ü k é l e s e n e l h a t á r o l h a t ó , k i l e n c a l m á t r i x r a b o n t h a t ó . A z a l m á t r i x o k oszlop h a t á r a i t az F S M - b e m e n e t e k n e k m e g f e l e l ő p p , p é s p P N - g r á f p o n t o k , az F S M - á l l a p o t o k n a k m e g f e l e l ő p , p é s p P N - g r á f p o n t o k , v a l a m i n t az F S M - k i m e n e t e k nek m e g f e l e l ő p , p , p é s p P N - g r á f p o n t o k h ú z z á k meg. A z a l m á t r i x o k sor h a t á r a i t pedig az e l s ő F S M - á l lapothoz r e n d e l t F S M - b e m e n e t e k a l a p j á n l é t r e j ö t t t , t , t és t P N - á t m e n e t e k , a m á s o d i k F S M - á l l a p o t h o z rendelt F S M - b e m e n e t e k a l a p j á n l é t r e j ö t t p , p , p é s p P N - á t m e n t e k , valamint a harmadik F S M - á l l a p o t h o z rendelt F S M - b e m e n e t e k a l a p j á n k i a l a k u l t p , p , p és p P N - á t m e n e t e k h a t á r o z z á k meg. A D m í n u s z m á t r i x b a n így e g y s é g e s a l m á t r i x o k é s s o r m á t r i x o k ala k u l n a k k i , gyakorlatilag teljesen f ü g g e t l e n ü l a m o d e l l f e l é p í t é s é t ő l . A m o d e l l l e í r á s á b a n a D plusz m á t r i x vesz r é s z t . E z a m e g á l l a p í t á s a k é s ő b b i e k b e n haszno sítható 2
3
4
5
6
7
8
9
1 0
n
L
2
3
4
5
6
10
n
1 2
K o m m u n i k á l ó véges a u t o m a t á k modellezése A p r o t o k o l l k é t v é g e s a u t o m a t a k o m p o z í c i ó j a , ame lyek v a l a m i l y e n t ö m e g k i s z o l g á l á s i s o r o n k e r e s z t ü l k o m m u n i k á l n a k . ( Á l t a l á b a n a s z á m í t ó g é p - h á l ó z a t így m o d e l l e z h e t ő - 13. ábra). E z azt j e l e n t i , hogy a k é t Híradástechnika,
XLL
évfolyam,
1990. 12.
szám
0 ]
[
8 ]
[
[
C ]
[
B ]
A ]
[
pN2
3
e l s ő Méges automata átmenetei kommunikációs Petri háló átmenetei Második uéges autonata átnenetei
v é g e s a u t o m a t a ö s s z e k a p c s o l á s a ú g y v a l ó s u l meg, hogy az egyik a u t o m a t a egy t ö m e g k i s z o l g á l á s i s o r o n keresz t ü l adja á t adatait é s n y u g t á i t a m á s i k a u t o m a t á n a k é s f o r d í t v a . A p r o t o k o l l l e í r á s a ennek a t ö m e g k i s z o l g á l á s i folyamatnak a s z a b á l y a i t tartalmazza. A z egymással ilyenformán kommunikáló automaták m o d e l l e z é s e k ö n n y e n m e g v a l ó s í t h a t ó P e t r i h á l ó segít s é g é v e l , ugyanis ahogy ezt m á r l á t t u k a b i n á r i s s z á m kettes k o m p l e m e n s é t e r e d m é n y e z ő P e t r i m o d e l l é s a paritást k é p z ő Petri modell példák kompozícióján, a független modellek egyszerűen illeszthetők össze. A z egyik m o d e l l k i m e n e t e megfelel a m á s i k m o d e l l b e m e n e t é n e k é s f o r d í t v a . A P e t r i h á l ó s m o d e l l az ilyen i l l e s z t é s e l v é g z é s é r e k i v á l ó a n alkalmas. E b b ő l az is k ö vetkezik, hogy nagyon e g y s z e r ű e n le lehet c s e r é l n i a p r o t o k o l l t . D e ugyanilyen e g y s z e r ű e n lehet m ó d o s í t a n i a modellt újabb protokoll funkció bevezetésekor. A k o m m u n i k á l ó v é g e s a u t o m a t á k ebben a m o d e l l ben h á r o m f ü g g e t l e n m o d e l l a l a p j á n j ö n n e k l é t r e . A h á r o m modell közül k e t t ő a két véges automata mo dellje, a h a r m a d i k pedig a t ö m e g k i s z o l g á l á s t v é g z ő e g y s é g m o d e l l j e . A teljes rendszer P e t r i h á l ó j á n a k m e g v a l ó s í t á s á h o z l é p é s e n k é n t h o z z á l á t h a t u n k . Egy részt a független modellek Petri hálós modelljeinek képzésével, másrészt a külön Petri modellek összekap csolásával.
7
8
9
[
12. ábra. A kommunikáló véges automaták Petri háló mátrixának felépítése, almátrixai
0 0 0 0 0 0 0 0 0 0 0 0
u
[PNl]
H592-12
Pl P2 P3 P4 Ps P6 P7 Ps P9 PlO Pll -1 0 0 0 -1 0 0 0 -1 0 0 0
M
[ e3 [ 0]
A D mínusz, PN-kimeneti mátrix:
ti
korwuni-j ásodik k á c i ó s ' véges Petri I automata háló I állapotai állapotail
K o r á b b a n azt m u t a t t u k be, hogy a v é g e s a u t o m a t a á l l a p o t - á t m e n e t s t r u k t ú r á j a hogyan t r a n s z f o r m á l h a t ó P e t r i h á l ó b a . M o s t m e g m u t a t j u k , hogy az így k ü l ö n k ü l ö n t r a n s z f o r m á l t é s l é t r e j ö t t P e t r i h á l ó k hogyan e g y e s í t h e t ő k (12. ábra). A véges automata Petri hálós transzformációjának m á t r i x a l a k j á b a n - m i n t ahogy m á r e m l í t e t t ü k - a m á t r i x oszlopait a v é g e s a u t o m a t a b e m e n e t e i , á l l a p o tai é s k i m e n e t e i a l k o t j á k . A z egyik k o m m u n i k á l ó v é ges a u t o m a t a m e g h a t á r o z h a t ó s z á m ú k i m e n e t é t á t a d j a a másik véges a u t o m a t á n a k és fordítva. A P e t r i h á l ó b a n azonban k é t P N - g r á f p o n t k ö z v e t l e n ü l n e m k a p c s o l ó d h a t ö s s z e , e z é r t az ö s s z e t e t t m o d e l l m i n d e n k é p p e n kiegészül újabb PN-gráfpontokkal és P N - á t m e n e t e k k e l . E z a g y a k o r l a t b a n amvyit jelent, hogy a D " é s a D m á t r i x o k m e g a l k o t á s á b a n a k ö v e t +
307
k e z ő k é p p e n n é z k i a mátrixok almátrixokra bontott struktúrája: P.. 1
[PN,]
[Q]
[ A
[£]
]
[ Q 1 ahol
[ ű ] [ S ] [PN,]
[0]
[ P N j ]az e l s ő v é g e s automata Petri almátrixa, [ P N ] a m á s o d i k v é g e s automata P e t r i a l m á t r i xa, 2
P.. T.. [0] [A] [C] [B]
a k o m m u n i k á c i ó PN-gráfpontjai, a kommunikáció PN-átmenetei és 0 elemű mátrix. a P N j - e l kapcsolatot t a r t ó k o m m u n i k á c i ós almátrix a kommunikációt leíró P N almátrix a P N - e l kapcsolatot t a r t ó k o m m u n i k á ciós a l m á t r i x
13. ábra. A kommunikáló véges automaták, protokoll értelmezése
2
L á t h a t ó , hogy h i á n y z ó a l m á t r i x ( A , B , C ) elem csu p á n a k o m m u n k á c i ó P N - á t m e n e t e i n e k soraiban van, azaz csak a k o m m u n i k á c i ó P N - á t m e n e t e i k a p c s o l ó d nak a v é g e s a u t o m a t á k b e m e n e t i é s k i m e n e t i P N - g r á f pontjaihoz. E z e n t ú l a t ö b b i m á t r i x elem é r t é k e nulla lesz. E z t e r m é s z e t e s e n a b b ó l k ö v e t k e z i k , hogy a t r a n s z f o r m á c i ó s o r á n a v é g e s automata bemeneteit és kimeneteit P N - g r á f p o n t o k k a l modelleztük. A t o v á b b i a k b a n t e k i n t s ü n k m e g n é h á n y p é l d á t az ilyen m á t r i x l é t r e h o z á s á r a k o n k r é t p r o t o k o l l o k m o d e l lezésével. E l ő s z ö r v i z s g á l j u n k m e g egy e g y s z e r ű p r o t o k o l l t a k o m m u n i k á l ó véges automatákkal. Majd a protokoll, a t ö m e g k i s z o l g á l ó sor legyen egy F I F O sor. A z ú j a b b p é l d a p e d i g szemafor rendszeres p r o t o k o l l legyen. M i n d e z e k folyamatosan b e m u t a t j á k , hogy ezzel a lép é s e n k é n t i m e g v a l ó s í t á s s a l egyre b o n y o l u l t a b b é s bo n y o l u l t a b b p r o t o k o l l f u n k c i ó k is a d a p t á l h a t ó k .
H592-U l-l. ábra. Kél véges automata egyszerű kommunikációjának Petri hálós modellje P 1
P
3
P
5
P
H 3 6
^2
f
P
f
7
9
P
P 11
A l e g e g y s z e r ű b b esetben a p r o t o k o l l (14. ábra) csu p á n a b b ó l áll, hogy az egyik v é g e s automata k i m e n e t i eleme - A ^ a t , j e l ű P N - á t m e n e t e n k e r e s z t ü l kapcso lódik a másik véges automata a - j e l ű bemeneti e l e m é hez, illetve a m á s o d i k v é g e s a u t o m a t a A j e l ű k i m e n e t i eleme a t j e l ű P N - á t m e n e t t e l k ö t ő d i k az e l s ő automa ta oi b e m e n e t i e l e m é h e z . 1
P 15
^WnWM
4 8 P
15. ábra. FIFO sor Petri hálós modellje
Két véges automata egyszerű k o m m u n i k á c i ó j a
P 13
H592-15
A C almátrix üres, mert a k o m m u n i k á c i ó s rész nem tartalmaz egyetlen g r á f p o n t o t sem. í g y t e r m é s z e t e s e n a k ö z é p s ő oszlop a l m á t r i x a i sem l é t e z n e k . A z á b r a j e löléseit alkalmazva az A é s a B m á t r i x o k a k ö v e t k e z ő képpen néznek ki: Az A
2
+
és A~ almátrix:
2
N
2
H o g y a n í r h a t ó f e l az e r e d ő D plusz é s D m í n u s z m á t r i x ? A h o g y azt m á r az e l ő b b b e m u t a t t u k , e l e g e n d ő csak az A , a B , é s a Q a l m á t r i x o k a t m e g h a t á r o z n i , m e r t a t ö b b i a l m á t r i x vagy a t r a n s z f o r m á c i ó b ó l nyer h e t ő vagy n u l l a e l e m ű :
E
308
=
[PN,] [ A ] t 0 ]
[ Q ] [£] [ Q ]
[ o] [ 1 ] [PN ]
1 •• 0 A
0-
0A B
+
és B
-1
0
almátrix:
• 0 •• 0 B
+
0
A" =
+
B
=
0 ••
-1
•0-
0
=
• 1 - 0
2
Híradástechnika,
XLl.
évfolyam,
1990. 12. szám
A z a l m á t r i x o k t ö b b i eleme m i n d n u l l a lesz, m e r t a k o m m u n i k á c i ó s r é s z elemei nem k a p c s o l ó d n a k a vé ges a u t o m a t á k t ö b b i b e m e n ő é s k i m e n ő e l e m é h e z .
nincs t ö l t é s . H a az egyik v é g e s a u t o m a t a adatot k ü l d a F I F O - b a , t ö l t é s k e r ü l a tj á t m e n e t b e g y ú j t á s á n a k h a t á s á r a a p g r á f p o n t b a é s ezzel egy i d ő b e n k i ü r ü l p j . A z ú j a b b adat csak t b e g y ú j t á s a u t á n i n d u l h a t , ugyanis ú j ra t ö l t é s k e r ü l p r b e , de u g y a n e k k o r k i ü r ü l p . U g y a n így k ö v e t h e t ő v é g i g a t ö l t é s e k sorsa az ö s s z e s gráf pontban. Ez gyakorlatilag a F I F O - b a n t o v á b b v o n u l ó adat f o l y a m a t á t m u t a t j a . K ö n n y e n b e l á t h a t ó , h o g y a F I F O regisztersor a k k o r t e l i k m e g , ha t ö l t é s csak a p á ros s z á m o z á s ú g r á f p o n t o k b a n van. 2
2
3
Két véges automata F I F O sorokkal való összekapcso lásának modellezése A m i k o r a p r o t o k o l l b a n a t ö m e g k i s z o l g á l á s i sorokat F I F O s o r o k k a l v a l ó s í t j u k meg, a v é g e s a u t o m a t á k k ö z ö t t i k o m m u n i k á c i ó b a n az á t k ü l d ö t t adatok illetve ü z e n e t e k egy k o r l á t o z o t t m é r e t ű regisztersoron ke resztül jutnak el a másik véges a u t o m a t á h o z . Hogyan m o d e l l e z h e t ő ez a kapcsolat?
E z e k a l a p j á n a m o d e l l t egy nyolcas m é l y s é g ű F I F O e s e t é n a 16. ábrán l á t h a t j u k . A k o m m u n i k á c i ó s P e t r i h á l ó ö S s z e s e n tizennyolc á t m e n e t b ő l é s h a r m i n c k e t t ő g r á f p o n t b ó l áll. A v é g e s au t o m a t á k h o z csak a t U, tio é s t á t m e n e t e k k a p c s o l ó d nak, í g y é r t e l e m s z e r ű e n az a l m á t r i x o k b a n csak ezeket t ü n t e t t ü k fel, a t ö b b i elem é r t é k e n u l l a . A j e l ö l é s e k a l a p j á n az a l m á t r i x o k az a l á b b i a k sze r i n t alakulnak:
A z a d a t á t k ü l d é s csak a k k o r i n d u l h a t , ha a F I F O sor valamennyi regisztere ü r e s . V e g y ü k s z e m ü g y r e a 75. ábrát, ahol a F I F O regiszter egyfajta P e t r i m o d e l l j e látható. Kezdetben minden páratlan indexű gráfpont b a n egy t ö l t é s t a l á l h a t ó , a p á r o s i n d e x ű e k b e n pedig
A C
+
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
l s
1 8
almátrix: 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 .0 0 0 0 0
0 0 0 0 0 0 0 0 0, 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 a 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 n 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0
M e g f i g y e l h e t ő a m á t r i x o k r i t k a jellege, m e l y a s z á m í t á s m e n e t é n e k e g y s z e r ű s í t h e t ő s é g é t e r e d m é n y e z i . AC~
almátrix: -1 0 . 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Híradástechnika,
0 0 0 -1 0 0 0 -1 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
XLI.
0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 -1 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
évfolyam,
0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0. 0 0 0 0 -1 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1990. 12.
0 0 0 0 0 0 0 0 0 0 0 0 -1 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
szám
0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 -1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 • 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 -1 0 0 0 0 -1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -1 0
309
p 1
p
r
PN1
p
3
h
p
5
1
K
p p p p 11 13 15
9
K
K
K
H ^ ó U %^0% 12WW9 T0 17 Vcll^ 23 %^5hs Z? % 7^V §1
\
P
2
t l f
f
véges automata
r
P
P
f
P
f
PN2
P
5 i
A"
p 18
p
p
p
20
p p 24 26
22
p 28
p 30
véges automata
32'
76. ábra. Két véges automata FIFO regiszteren keresztüli kommunikációjának Petri hálós modellje A z A almátrixok: A'
0
0
• 1 - 0
0 - 0
A B almátrixok:
1 B
+
0
0
=
B t,
0
=:
0
0
t,:
Két véges automata szemaforokkal való összekapcso lásának modellezése
H592-17 77. ábra. P cs V szemafor rendszer Petri hálós modellje
A szemafor rendszer egy olyan s z i n k r o n i z á l á s i mecha nizmus, a h o l egy i r á n y í t ó e g y s é g s z a b á l y o z z a az adat é s n y u g t á z á s f o r g a l m a t . A szemafor rendszerben k é t m ű v e l e t , a P é s V m ű v e l e t , v a l a m i n t egy szemafor l é -
P
PN1
\
f
1 f
l0
1
f
P
2 11
f
2
P
f
f
3
P
3
U
12
T
13
tczik, a m i n e m n e g a t í v e g é s z é r t é k e t vehet f e l . A V m ű v e l e t eggyel n ö v e l i , a P m ű v e l e t eggyel c s ö k k e n t i ennek a s z á m n a k az é r t e k é t . P m ű v e l e t a k k o r k ö v e t -
4
P
5
f
f
%
5
P
f
6
6 f
1B
P
f
7 f
7
<
P
f
16
8 f
17
T
f
9 18
véges i \ automata
IS. ábra. Két véges automata szemaforos összekapcsolásának Petri hálós modellje 310
Híradástechnika,
XLI.
évfolyam,
1990, 12. szám
kezhet be, ha a szemafor é r t é k e p o z i t í v . H a a szema for é r t é k e n u l l a , a P m ű v e l e t n e k m i n d a d d i g v á r n i a k e l l , a m í g n e m k ö v e t k e z e t t be egy V m ű v e l e t . A sze mafor é r t é k é t pedig semmi m á s nem m ó d o s í t h a t j a . A 17. ábrán b e m u t a t j u k ennek P e t r i h á l ó s m o d e l l j é t . A szemafor az S j e l ű g r á f p o n t , a m i n e k é r t é k e a benne lé v ő t ö l t é s e k s z á m á v a l egyezik meg, a P é s V m ű v e l e t pedig egy-egy á t m e n e t . H a a t ö m e g k i s z o l g á l á s t regisztersorral valósítjuk meg, a k k o r a szemaforos s z i n k r o n i z á l á s egy l e h e t s é g e s m ó d j a a 18. ábrának m e g f e l e l ő e n r e a l i z á l h a t ó . A nyolc regiszteres m e g o l d á s n á l az egyik szemafor a p , - d i k g r á f p o n t , a m á s i k a p - d i k , melyeknek pontosan nyolc kezdeti t ö l t é s s e l k e l l rendelkezni, amennyi a regiszte rek s z á m a . A P m ű v e l e t e k e t a t, é s a t á t m e n e t e k a V m ű v e l e t e k e t p e d i g a t> é s a t á t m e n e t e k jelzik. A k o m m u n i k á c i ó s P e t r i h á l ó így 18x18-as a l m á t r i x o t eredményez. A véges a u t o m a t á k h o z való kapcsolódás pedig h a s o n l ó a n az e l ő b b i p é l d á k h o z csak k é t - k é t át m e n e t n é l v a l ó s u l meg: t fc,, t , é s t . 1 8
1 8
1 0
1 (
10
1 8
A z almátrixok tehát a következő m ó d o n néznek ki: A C
C = +
A C
c =
+
almátrix: 10 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 0 0 0 10 0 0 0 10 0 0 0 0 0,0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 0 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
almátrix: 0 0 0 0 0 0 0 0 -10 0 0 0 0 0 0 0-10 0 0 0 0 0 0 0-1 0 0 0 0 0 0 0 0 -10 0 0 0 0 0 0 0-10 0 0 0 0 0 0 0-10 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Híradástechnika,
XLI.
-1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -10 0 0 0 0 0 0 0 0 0-10 0 0 0 0 0 0 0 0 0-1 0 0 0 0 0 0 0 0 0 0 -10 0 0 0 0 0 0 0 0 0-10 0 0 0 0 0 0 0 0 0-1 0 0 0 0 0 0 0 0 0 0 -10 0 0 0 0 0 0 0 0 0-10 0 0 0 0 0 0 0 0 0-1
évfolyam,
1990. 12.
szám
A z A almátrixok: oj A 0 t, A
A, -1 1
k
=
ö
; A 0
A B almátrixok: 2
2
1 B = +
A„
°i •• 0
0
••
0
:
ó
••
ö
tl8
• • ó ••
-1
A k u t a t á s t o v á b b i célja, hogy e l e m z é s i m ó d s z e r e k e t dolgozzunk k i az ilyen f o r m á b a n s z á m í t ó g é p r e vitt protokollok dinamikai vizsgálatához, a Petri hálós mo dell gyújtási sorozatainak h a t é k o n y e l e m z é s é h e z . K i b ő v í t v e a kiterjesztett P e t r i h á l ó s m o d e l l e k v i z s g á l a t á val a n u m e r i k u s é s az i d ő P e t r i h á l ó k a n a l i z á l h a t ó k . E z e n kívül célja, hogy t o v á b b i l é n y e g e s p r o t o k o l l funk ciók m o d u l á r i s b e é p í t é s é h e z , ú j a b b e l ő r e n e m l á t h a t ó p r o b l é m á k é r t é k e l é s é h e z dolgozzon k i eljárásokat. Ne csak k i z á r ó l a g a m á t r i x algebra a l k a l m a z á s á v a l te remtse m e g ezeket a v i z s g á l a t o k a t , h a n e m ú j , alkalmas p r o g r a m o z á s i nyelvek k e r e s é s é v e l , f e l h a s z n á l á s á v a l . P r o t o k o l l o k s e g í t s é g é v e l , azok P e t r i h á l ó s modelljei nek e l e m z é s e a l k a l m a t t e r e m t m á s k o m m u n i k á l ó rendszer m o d e l l e z é s é r e is, p é l d á u l a s z á m í t ó g é p e s h á lózat modelljének vizsgálatára. így alkalom kínálkozik a h i e r a r c h i k u s rendszerek P e t r i m o d e l l j é n e k megalko t á s á v a l é s annak v i z s g á l a t á v a l a s z á m í t ó g é p e s h á l ó z a tok biztonsági és védelmi tulajdonságainak e l e m z é s é r e is. IRODALOM 1 [AGE-79] T. Agerwala: „Putting Petri Nets to Work", Computer Vol. 12, No. 12. December 1979. pp. 85-94. 2 [AND-83] B. Andrásfai: The Theory of Graphs, Flows and Matrices. Akadémia Kiadó, Budapest, 1983. 3 [DVM-85]Demetróvics /., Jordán D., Radiszlav P.: A számítástu domány matematikai alapjai, Tankönyvkiadó, Buda pest, 1985, pp. 170-181. 4 [HACK-74] M. Hack: „Decision Problems for Petri Nets and Vector Additien Systems", Computation Structures Group Memo 95, Project M A C , March 1974, pp. 79 5 [ISO-84] International Standard Information Processing Systems: Open System Interconnection - Basic Reference Mo dell, ISO 7498,1984. 6[MUR-76]T. Murata: „ A Method for Synthesizing Marked Graphs from Given Markings", Proceedings of the ' Tenth Annual Asilomar Conference on Circuits, Systems and Computers, November, 1976, pp. 202-206. 7 [NAGY-79] . Dr. Nagy Á.: „Modellezés Petri-gráfokkal", Infor máció-Elektronika, 1979/3. pp. 158-161. 8 [PETRI-62] C. Petri: „Kommunikation mit Automaten", Ph. D. Thesis, University of Bonn, 1962. 9[PET-77] /. L . Peterson: „Petri Nets", Ass. Comput. Match. Computing Surveys, Vol. 9, Sept. 1977, pp. 223-251. 10 [PET-81a] /. L . Peterson: „Petri Net Theory and the Modeling of Systems", Prentice-Hall, Inc., Englewood Cliffs, N. J. 1981. pp. 43-44. 11 [PET-81b] /. L . Peterson: „Petri Net Theory and the Modeling of Systems", Prentice-Hall, Inc., Englewood Cliffs, N. J. 1981. pp. 42. .12 [PET-81c] /. L . Peterson: „Petri Net Theory and the Modeling of Systems", Prentice-Hall, Inc., Englewood Cliffs, N. J. 1981. pp. 44-45. 311
