Hoppa till innehållet

Petrinät

Från Wikipedia
Exempel på ett petrinät under körning. Producent till vänster och konsument till höger. De är sammankopplade med en buffert.

Petrinät är ett formellt och grafiskt språk för att modellera och beskriva distribuerade system med samtidighet och resurshantering. Petrinät är riktade bipartita grafer där de två nodmängderna är platser (ritas som cirklar) och övergångar (ritas som tvärstreck eller rektanglar). De riktade bågarna går från en plats till en övergång eller vice versa och påvisar flödesriktningen.

När bågen går från en plats till en övergång kallas platsen för inmatningsplats (input place) och när bågen går från en övergång till en plats kallas platsen för utmatningsplats (output place).

Platserna kan innehålla ett antal markeringar (ritas som prickar), även kallade tokens. En fördelning av markeringar i nätets platser kallas för en märkning eller för en konfiguration av nätet.

En övergång kan avfyra om det finns tillräckligt med markeringar på dess inmatningsplatser och kallas då för aktiverbar. När en övergång avfyrar konsumerar den dessa markeringar och producerar markeringar på utmatningsplatserna. En avfyrning är en atomär händelse, den kan inte avbrytas.

Körning av ett petrinät är inte deterministiskt eftersom en övergång inte behöver avfyra bara för att den är aktiverbar.

En övergång säges vara levande (på engelska alive; liveness) om den kan inträffa någon gång i framtiden utifrån en given märkning.

Nåbarhet (på engelska reachability) säger om en viss märkning kan nås utifrån en annan given märkning.

Ett petrinät säges vara begränsat (på engelska bounded; boundedness) om det finns en övre begränsning på antalet markeringar i varje plats.

Externa länkar

[redigera | redigera wikitext]