Post on 03-Jan-2016
description
transcript
Petriho sítě
Pět hladových filozofů The Dining Philosophers problem
Mao Ce Tung
Karl Marx Leonardo da Vinci
Aristoteles
Sokrates
Co to jsou Petriho sítě?• Je to modelovací nástroj,• Grafický i matematický,• Vhodný pro popis a analýzu diskrétních systémů,• Další využití je popis systémů, které jsou popisovány jako synchronní, asynchronní, distribuované, paralelní,• Existuje velké množství modifikací Petriho sítí, např.:
Barevné PS, Hierarchické PS, Objektově orientované PS.
My se budeme zajímat jen o základní typ Petriho sítí, ty se někdy označují jako P/T (Place/Transitions) Petriho sítě.
Historie• Autorem Petriho sítí je Carl Adam Petri
(12.7.1926 – 2.7.2010).
• Byl prvním člověkem který jako první formálně definoval „jazyk“ Petriho sítí.
• Základem se stala jeho disertační práce s názvem Kommunikation mit Automaten, z roku 1962 na fakultě Matematiky a Fyziky, Technické Univerzity Darmstadt.
• Jeho webová stránka je : http://www.informatik.uni-hamburg.de/TGI/mitarbeiter/profs/petri_eng.html
Základní objekty P/T Petriho sítí
• Místa (Places)• Přechody (Transitions)• Hrany (Arcs), směřují–Od místa k přechodu, nebo
–Od přechodu k místu
Kapacita místa
• Kapacita (Capacity), je hodnota definována pro všechna místa v síti, udává maximální počet Značek (Tokens), které může dané místo obsahovat. Pokud místo nemá explicitně vyjádřené omezení kapacity, považuje se jeho kapacita za neomezenou.
100
Kapacita 100 Kapacita 3 Neomezená kapacita
Váha hran
• Váha (Weight), je definována pro všechny hrany v síti, udává násobnost (mohutnost) hrany. Pokud hrana nemá ohodnocení váhy, je její váha rovna jedné.
3
Váha hrany je 3 Váha hrany je 1
Aktivace přechod v Petriho sítiJestliže všechna místa předcházející přechodu
obsahují počet značek větší nebo rovný váze hrany spojující místo s přechodem dojde k Aktivaci přechodu
Příklady aktivací přechodů
Počet značekve vstupním místěP1 < váha hrany Nelze aktivovat přechod T0
Efektivní konflikt
• Chování Petriho sítě po aktivaci přechodu může být nejednoznačné (nedeterministické)
• Úkolem Petriho sítí není tento konflikt řešit
Formální definice Petriho sítěNeoznačená Petriho R síť je uspořádaná čtveřice R=(P,T,Pre,Post), kdeP = {Pi…..Pm} je konečná množina míst,T = {Ti…..Tn} je konečná množina přechodůPre je matice velikosti m x n matice obsahující celá nezáporná čísla reprezentující váhy hran jdoucích z míst do přechodů.Post je matice velikosti n x m obsahující celá nezáporná čísla reprezentující váhy hran jdoucích z přechodů do míst. M0 je počáteční značení Petriho sítě.Incidenční matice C je matice C = Post – Pre.
Post:
T1 T2 T3
P1 0 0 1
P2 1 0 0
P3 0 1 0
Pre:
T1 T2 T3
P1 1 0 0
P2 0 1 0
P3 0 0 1
M0
P1 1
P2 0
P3 0
C T1 T2 T3
P1 -1 0 1
P2 1 -1 0
P3 0 1 -1
Běh jednoduchého procesu
Modelování chemické reakce2H2H22 + O + O22 2H 2H22OO
H2
O2
H2O
t
2
2
H2
O2
H2O
t
2
2
Přístup ke kritické sekci
Producent/Konzument(neomezený buffer)
Producent/Konzument(omezený buffer)
Čtenáři/písaři
Řešení problému tří hladových filozofů
Tři paraelní procesy s jedním sdíleným zdrojem