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