Modelová Modelování Petriho sí sítěmi • •
•
Grafický popis a analýza systémů, ve kterých se vyskytují synchronizační, komunikační a zdroje sdílející procesy. Popis paralelních jevů a konfliktních závislostí – Jednoduchost – Přehlednost – Modelování dynamiky procesů Typy Petriho sítí – C/E (Condition/Event) Petriho sítě, – P/T (Place/Transitions) Petriho sítě, – P/T Petriho sítě s inhibičními hranami, – P/T Petriho sítě s prioritami, – TPN Časované (Timed) Petriho sítě, – CPN Barevné (Coloured, barvené) Petriho sítě, – HPN Hierarchické (Hierarchical) Petriho sítě, – OOPN Objektové (Object Oriented) Petriho sítě. 1
Základní kladní pojmy • •
•
Places (místa) obsahují stavovou informaci ve formě značek (token) Transitions (přechody) vyjadřují možné změny stavů (vzory možných událostí) Arcs (orientované hrany) určují logické vazby Simulace Obsluhy zá zákazní kazníka Zákazník požaduje obsluhu
Linka pracuje Materiál
Linka je volná
Obslužný personál 2
1
Grafický popis Petriho sítí je orientovaným bipartitních multigrafem • Orientovaná hrana může spojit: – místo s přechodem – přechod s místem • Orientovanou hranou nemůžeme spojit – místo s místem – přechod s přechodem
3
Synchronizace paralelní paralelních procesů procesů
4
2
Synchronizace paralelní paralelních procesů procesů
Kritická sekce
Střídání událostí
Triviální deadlock
5
Pravidla pro uskuteč uskutečnění přechodu • •
• • •
Přítomnost značky v místě indikuje, že daný aspekt stavu je momentálně aktuální, resp. podmínka je splněna. Každý přechod má vstupní a výstupní místa – tím je určeno, které aspekty podmiňují výskyt události a jaké skutečnosti jsou výskytem této události ovlivněny. Označme z(p) počet značek v místě p. Přechod může být uskutečněn, jsou li splněny všechny vstupní podmínky, tj. z(pi)>0 pro všechna vstupní místa pi daného přechodu. Uskutečnění přechodu: u všech vstupních míst ubereme jednu značku (z´(pi) = z(pi) - 1) a u všech výstupních míst přidáme jednu značku (z´(pj) = z(pj) + 1)
6
3
Ohodnocení Ohodnocení hran a př přechodů echodů •
Místo p je určeno kapacitou c(p) maximálního počtu značek. Přechod může být uskutečněn jen pokud (současně se splněním vstupních podmínek) není překročena kapacita výstupních podmínek.
•
Počty odebíraných (umístěných) značek jsou specifikovány váhou hran. Přechod je uskutečněn jen pokud jsou vstupní hrany nasyceny, tj. pokud není počet značek ve vstupních místech daného přechodu menší než váhy příslušných hran.
2
2
2
2
2 7
Konfliktní Konfliktní přechody
•
• •
Dva současně proveditelné přechody jsou konfliktní, když provedení jednoho způsobí, že druhý přestane být proveditelný. Konfliktní přechody modelují soupeření o zdroje a vzájemnou výlučnost dvou událostí. Nezávislé přechody modelují asynchronnost a paralelismus. Nezávislé přechody
Konfliktní přechody
8
4
Definice PT sí sítí •
PT sí síť je uspoř uspořádaná daná pětice PN=(P,T, I-, I+, z0) – P = {p1,p2,…pn} je koneč konečná neprá neprázdná zdná množ množina mí míst – T ={t1,t2,…tn} je koneč konečná neprá neprázdná zdná množ množina př přechodů echodů – množ množiny P, T jsou disjunktní disjunktní – I-, I+, jsou incidenč incidenční funkce P x T ->N0 z = – z0 : P -> N0 je poč í ( z ( p1 ) , z ( p2 ) ,… , z ( pn ) ) počáteč teční ohodnocení ohodnocen 0
• •
• •
0
0
0
Pokud je I-(p,t) > 0, vede orientovaná hrana z místa p do přechodu t. Počet odebraných žetonů v místě p uskutečněním přechodu t je roven I-(p,t) . Pokud je I+(p,t) > 0, vede orientovaná hrana z přechodu t do místa p. Počet přidaných žetonů v místě p uskutečněním přechodu t je roven I+(p,t) . z = ( z ( p1 ) , z ( p2 ) ,… , z ( pn ) ) Označme aktuální ohodnocení celé sítě vektorem Přechod t nazýváme aktivní aktivní (uskutečnitelný) v daném ohodnocení z(i) , jestliže (i )
(i )
(i )
(i )
∀p ∈ P; z (i ) ( p ) ≥ I − ( p, t ) •
Ohodnocení z(i) nazýváme dosažitelné z ohodnocení z(j), jestliže existuje posloupnost uskutečněných přechodů, které převádí z(i) do z(j). (ozn ozn.. z(i) - > z(j)) 9
Struktura a vlastnosti Petriho sí sítí • • •
Petriho síť nazýváme bezpeč bezpečnou, nou jestliže pro každé její ohodnocení platí: z(p) ≤ 1. Petriho síť nazveme ohranič ohraničenou, enou jestliže ∃k ∈ N 0 ; ∀z, p; z ( p ) ≤ k Petriho síť nazýváme konzervativní konzervativní, jestliže pro každý její stav platí, že celkový počet značek je konstantní. ∀i;
∑ z( ) ( p ) = k i
j
j
•
Síť nazýváme živou, ivou, jestliže jsou živé všechny její přechody, tj., jestliže ke každému ohodnocení z existuje dosažitelné ohodnocení z´, z ->z´, které aktivuje daný přechod. ∀z ∃ z ′; z → z ′
2
2
1
1
bezpeč čnčená áensáíťsíť í síť bezpe ohranič čená á, konzervativní ohranineohranič neohrani en konzervativn
10
5
Konzervativnost sí sítě
Striktně konzervativní
Konzervativní vzhledem k váhovému vektoru (2,1,1,2).
11
z0 = ( 3, 0, 5, 4, 0 ) , I − ( p3 , t3 ) = I + ( p3 , t4 ) = 5
Příklad
T1 T2 T3
P1 1 P2 0 C − = P3 1 P4 0 P5 0
•
T4
0 0 0 0 1 1 0 1 0 0 0 5 0,C+ = 0 1 0 1 0 0 0 0 0 0 0 1
0 0 −1 1 0 0 1 −1 0 0 0 0 0 5 , C = −1 1 −5 5 0 1 0 0 −1 1 0 0 1 −1 1 0
Po uskutečnění přechodu T1 přejde počáteční ohodnocení z0 do stavu 2 1 0 1 z ′ = z0 + C = 4 0 4 0 0
•
5
5
HPSim
Po odpálení posloupnosti T1, T1, T1, T2 je výsledné ohodnocení z (4)
1 3 1 2 = z0 + C = 3 0 4 0 0
12
6
Matice incidence •
Nechť má PN n míst P={p1,p2,..pn} a m přechodů T={t1,t2,..tm}. Zpětná incidenční matice C- typu n x m je definována cij− = I − ( pi , t j ) , ∀pi ∈ P, t j ∈ T
•
analogicky dopředná incidenční matice C+ cij+ = I + ( pi , t j ) , ∀pi ∈ P, t j ∈ T
• • • •
Incidenční matice C = C+ - C− Přechod ti je v daném ohodnocení z=(z1,z2,..zn) aktivní, jestliže ∀z j ; z j ≥ c ji Uskutečněním přechodu ti přejde ohodnocení z v ohodnocení z´ z ′ = z + Cei ; Předpokládejme posloupnost odpálených přechodů ti1 , ti2 , … , tik , výpočet dosaženého stavu z(k) je dán dosazením do předcházejícího vzorce k
z ( k ) = z + C ∑ eij ; j =1
•
k
∑e j =1
ij
= Ξ Parikův obraz posloupnosti přechodů
Nutná podmínka dosažitelnosti: Je-li z´značení dosažitelné ze značení z0, potom existuje řešení Ξ rovnice
z ′ = z0 + C Ξ 13
Př: Napiš Napište matici incidence C Přechod TK se uskuteční v ohodnocení z, ∀zi ; zi ≥ c −iK T 0 T1 T 2 T 3 T 4 T 5
C − = ( I − ( pn , tm ) )
P0 2 P1 0 = P2 0 P3 0
0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 0 2 0 0 0
z ( 0)
1 2 = 0 0
0 +1 −2 0 0 +2 −1 0 −1 0 + − + − C = C − C = ( I ( pn , tm ) − I ( pn , tm ) ) = 0 +1 +1 0 −1 0 0 −2 +2 0
Odpálení přechodu T1: 0 0 0 1 0 1 0 1 0 2 −1 1 0 (0) z′ = z + C = + = 0 0 +1 1 0 0 0 0 0 14
7
P-invarianty Nechť C je matice incidence Petriho sítě. Nenulový vektor iP∈Nn se nazývá P-invariant Petriho sítě, jestliže je řešením homogenní soustavy lineárních rovnic C T iP = o Petriho síť má konzervativní komponentu právě tehdy, existuje-li nenulový P-invariant. Př: striktně konzervativní síť −1 −1 1 1 C = 0 1 −1 0 1 0 0 −1
iP = {k ⋅ (1,1,1) ; k ∈ N } 15
P-invarianty konzervativní konzervativní komponenty −1 −1 1 1 0 1 −1 0 C = 0 1 −1 0 1 0 0 −1
C T iP = o
iP = {( u , u − v, v, u ) ; u , v ∈ N , u > v} Výhodnější zápis získáme pomocí bázových vektorů prostoru řešení. Volíme-li např. u=1, v=0 dostáváme iP1=(1,1,0,1), podobně volbou u=2, v=1 dostáváme iP2=(2,1,1,2), což jsou nejmenší váhové vektory pro konzervativnost sítě.
iP = {k (1,1, 0,1) + l ( 2,1,1, 2 ) ; k , l ∈ N } 16
8
T-invarianty
Petriho síť nazveme reverzibilní reverzibilní, pokud ke každému dosažitelnému značení existuje posloupnost odpálených přechodů, ve které je počáteční značení aktivní Nechť C je matice incidence Petriho sítě. Nenulový vektor iT∈Nn se nazývá T-invariant Petriho sítě, jestliže je řešením homogenní soustavy lineárních rovnic
CiT = o Pokud je Petriho síť je reverzibilní, pak má nenulový invariant. . T-invariant je Pariků Parikův obraz posloupnosti, která přechody reprodukuje, tj. udává kolikrát je třeba provést každý přechod, abychom se vrátili k původnímu značení 17
T-invarianty Př. Reverzibilní sítě
CiT = o −1 −1 1 1 C = 0 1 −1 0 1 0 0 −1
i1 −1 −1 1 1 0 i2 0 1 −1 0 ⋅ i = 0 1 0 0 −1 3 0 i 4
iT = {k ⋅ (1, 0, 0,1) + l ⋅ ( 0,1,1, 0 ) ; k , l ∈ N }
18
9
T-invarianty Př. Reverzibilní sítě −1 −1 1 1 0 1 −1 0 C = 0 1 −1 0 1 0 0 −1
CiT = o −1 −1 1 1 i1 0 0 1 −1 0 ⋅ i2 = 0 0 1 −1 0 i3 0 1 0 0 −1 i4
iT = {k ⋅ (1, 0, 0,1) + l ⋅ ( 0,1,1, 0 ) ; k , l ∈ N }
19
Přechodová echodová funkce • Stavový prostor – množina dosažitelných značení • Přechodová echodová funkce – funkce definovaná na stavovém prostoru – určuje na základě přítomného stavu a aktivního přechodu příští stav sítě – zadána buď tabulkou, nebo orientovaným grafem.
20
10
Stavový strom (graf pokrytí pokrytí)
• Abstrakce přechodové funkce Petriho sítě. • Orientovaný kořenový strom, jehož kořenem je počáteční značení . • Jestliže v průběhu konstrukce stromu zjistíme, že jistá složka značení neomezeně roste, pak tuto složku označíme ∞ a nový vektor reprezentuje nekonečnou množinu značení, pro které tato složka nabývá libovolné nezáporné celočíselné hodnoty. Neomezená Petriho síť
(1,0) t2 (0,2) t1 (1,∞)
HPSim
t2
t1
(0,∞)
(1,∞)
(1,∞)
21
Matice př přechodu
•
Prvky matice jsou tvořeny pravděpodobnosti přechody systému z jednoho stavu do druhého 0 0 0,5 0,5 0 0 0,5 0,5 0 0 P= 0 0 0 0,5 0,5 0,5 0 0 0 0,5 0,5 0,5 0 0 0 a1 = a0 P HPSim 22
11
Síť s omezenou kapacitou mí míst
23
Inhibitory – negativní negativní testovací testovací hrany • Rozlišujeme 3 typy hran :
normá normální lní inhibitory tester
• Přechod spojený s místem inhibitorem je uskutečněn jen pokud je počet značek v místě menší než váha inhibitoru. Počet značek ve vstupním místě se nemění. • PT (places-transitions) sítě s inhibitory jsou s teoretického hlediska schopny modelovat vše, co je možné vyjádřit algoritmem.
2
2
24
12
Inhibitory, Petriho sí sítě s prioritami
T1 má vyšší prioritu než T2
•
Petriho sítě s inhibičními hranami mohou být převedeny na ekvivalentní sítě s prioritami.
25
Booleovské Booleovské operace Př: Úplný systém logických funkcí {negA, AND, OR},{NAND},{NOR} neg.A
AND
OR
NAND
NOR
A
B
A
A∧ ∧B
A∨ ∨B
(A∧ ∧B)
(A∨ ∨B)
0
0
1
0
0
1
1
0
1
1
0
1
1
0
1
0
0
0
1
1
0
1
1
0
1
1
0
0
26
13
Stochastické Stochastické časové asové Petriho sí sítě (Stochastic Petri Nets) ets) • Přechody ve SPN představují jednotlivé události(akce). • typy přechodů: 1. Okamž Okamžité ité 2. se zpož zpožděním (doba zpoždění je náhodná veličina) • SPN = (P, T, I-, I+, G, z0) P, T,, I-, I+, z0…PT Petriho síť G exponenciální funkce přiřazené přechodům
27
Dining Philosophers
HPSim
28
14
Stavový graf • •
Spojitý stochastický proces zdiskretizujeme – postupujeme v diskrétních krocích dt. Krok simulace dt zvolíme dostatečně malý (ms) tak, abychom mohli předpokládat, že za interval délky dt nastane nejvýš jedna událost. T3 P1
P3
T4
T2
P2
z0=(1,0,0)
z1=(0,1,0)
z2=(0,0,1) T1
Ze stavu z0 mohou po jednom kroku dt nastat 3 možnosti: • z1 (spuštěn přechod T1) • z2 (spuštěn přechod T4) • z0 (ani pro jeden z přechodů T1, T2)
29
Markovů Markovův řetě etězec stochastické stochastické Petriho sí sítě
•
•
•
Nechť jsou všechny přechody dány s exponenciálním rozdělením zpoždění. Pak stavový prostor (množina všech možných ohodnocení) zi tvoří Markovovský řetězec se spojitým časem- CTMC. Infinitezimální generátor Q: Intenzita výstupu qij ze stavu zi do stavu zj je součtem intenzit všech přechodů, jejichž odpálením přejde stav zi do stavu zj. Analýzou Markovova řetězce můžeme vypočítat charakteristiky systému popsaného SPN. - Nechť je π stabilizovaný stav, tj π Q = 0; ∑ π j = 1 j
Pak pravděpodobnost, že ohodnocení míst SPN je z dané podmnožiny stavů B. P[ B ] =
∑π
j z ( ) ∈B
j
30
15
Časová asová past
31
Barevné Barevné Petriho sí sítě •
Rozlišujeme různé typy žetonů a různé módy odpalů přechodů
32
16
Barevné Barevné Petriho sí sítě • •
Podmínkou efektivního zavedení barevných Petriho sítí je, aby se přechody chovaly v různých módech podobně. Pro popis odpalu přechodu zavedeme lokální proměnné, incidenční funkce zapisujeme k příslušným hranám
a b −a 0 −b 0 a − a 0 b − b 0 ; C = Ca ′ = b′ 0 0 a −a b −b 0 −• • 0 −• •
x x
x y x
x
y
x
33
Převod barevné barevné Petriho sí sítě na P/ P/T sí síť •
•
• •
Pro umístění různých barevných typů žetonů vytvoř zvláštní místa. Nechť např.v místě p je možný výskyt barev a, b, c. Pak z jednoho místa p vytvoříme tři místa pa,pb,pc. Pro každý mód odpálení přechodu vytvoř zvláštní přechod. Je-li např.možné odpálit přechod t v módu x a y, vytvoříme dva přechody tx, ty. Vytvoř nové incidenční funkce tak aby odpovídaly původním módům. Nastav počáteční ohodnocení sítě.
34
17
Dining philosophers
hl(f1) = h1+h2, hl(f2) = h2+h3, hl(f3) = h3+h4, hl(f4) = h4+h1 35
Simulace systé systémů hromadné hromadné obsluhy
•
Simulace systému M/M/1/3 FIFO, dva typy zákazníků s různou délkou obsluhy – T0 … vstup zákazníků prvního typu, – T5…vstup druhého typu. – Zákazníci prvního typu se řadí do horní řady P11, P21, P31, zákazníci druhého typu se řadí do spodní řady P12, P22, P32. 36
18
Frontové Frontové Petriho sí sítě •
•
Barevné GSPN se dvěma typy míst – Obyčejná místa – Frontová místa (fronta + zásobník obsloužených zákazníků). Zákazníci (žetony) z fronty nemohou být použity pro odpal následujících přechodů. Nejprve musí proběhnou obsluha podle předepsaného rozdělení délky obsluhy, žeton je přemístěn z frontové části do zásobníku a teprve žetony ze zásobníku mohou být použity pro odpal výstupních přechodů dle zpětných incidenčních funkcí
37
Systé Systém se ztrá ztrátami, Systé Systém s prioritami
38
19
