Una rete di Petri (conosciuta anche come rete posto/transizione o rete P/T) è una delle varie rappresentazioni matematiche di un sistema distribuito discreto. Come un linguaggio di modellazione, esso descrive la struttura di un sistema distribuito come un grafo bipartito con delle annotazioni.
La rete di Petri deve il suo nome al matematico tedesco Carl Adam Petri, il quale ne enunciò le caratteristiche per la prima volta nel 1962 tramite la pubblicazione della propria tesi di dottorato, intitolata Kommunikation mit Automaten. Come rivelato dallo stesso Petri nel 2007, l'idea alla base della rete di Petri fu da lui concepita già nell'agosto 1939 (quando aveva 13 anni) per memorizzare in maniera più efficace i processi chimici.
Descrizione Concetti base Una rete di Petri PT (Place/Transition) è un grafo orientato con due tipi di nodi, posti e transizioni, connessi da archi orientati. I posti sono rappresentati graficamente da cerchi e le transizioni da rettangoli.
Un arco può unire solamente nodi di tipo diverso, quindi possono esserci archi tra posti e transizioni - ma non tra posti e posti o transizioni e transizioni. Un posto da cui un arco parte per finire in una transizione è detto posto di input della transizione; un posto in cui un arco arriva partendo da una transizione è detto posto di output della transizione.
I posti possono contenere un certo numero di token o marche. Una distribuzione di token sull'insieme dei posti della rete è detta marcatura. Le transizioni agiscono sui token in ingresso secondo una regola, detta regola di scatto (). Una transizione è abilitata se può scattare, cioè se ci sono token in ogni posto di input. Quando una transizione scatta, essa consuma token dai suoi posti di input, esegue dei task e posiziona un numero specificato di token in ognuno dei suoi posti di uscita. Ciò avviene automaticamente, ad esempio in un singolo step non-prelazionabile. L'esecuzione delle reti di Petri è non deterministica. Ciò significa due cose: se più transizioni sono abilitate nello stesso momento, una qualsiasi di esse può scattare non è garantito che una transizione abilitata scatti; una transizione abilitata può scattare immediatamente, dopo un tempo di attesa qualsiasi (a patto che resti abilitata), o non scattare affatto. Poiché lo scatto di una transizione non è predicibile a priori, le reti di Petri sono molto adatte a modellare il comportamento di un sistema concorrente.
Definizione formale Una rete di Petri è un sistema a transizione di stati che estende una classe di reti, dette reti elementari.
Definizione 1: Una rete è una tripla dove:
è un insieme di stati chiamati posti. è un insieme di transizioni. è un insieme di flussi relazionali chiamati “archi”. Tali flussi sono possibili solamente tra posti e transizioni o viceversa.
Una rete è un grafo bipartito, dove è una partizione e è l'altra. Più precisamente, per ogni in esistono e in tali che e appartengono ad e per ogni e in se e sono in allora . In formula:
L'insieme contiene gli elementi della rete. L'insieme dei posti definisce gli stati locali della rete, tuttavia, lo stato globale di una rete può essere definito da sottoinsiemi di posti.
Definizione 2: Data una rete , una configurazione è un insieme .
Definizione 3: Una rete elementare è una rete della forma dove:
è una rete. è una configurazione.
Definizione 4: Una rete di Petri è una rete della Teoria delle reti di Petri. Le proprietà teoriche delle reti di Petri sono state studiate ampiamente. Un motivo principale per usare le reti di Petri nel modellare i sistemi concorrenti è dato dalla possibilità di delineare formalmente e decidere delle proprietà desiderabili del sistema, come la liveness (ad esempio, in un sistema che non deve mai bloccarsi) o la boundedness (ad esempio, le risorse di un sistema come la CPU sono limitate). Naturalmente, la stessa proprietà in un contesto diverso può assumere un significato completamente diverso.
Una marcatura in una rete di Petri è raggiungibile se, partendo dalla marcatura iniziale, esiste una sequenza di scatto che la produce. Una rete di Petri è bounded se c'è un limite massimo al numero di token nelle sue marcature raggiungibili.
Tipi principali
Ci sono sei tipi principali delle reti di Petri: Macchina a stati finiti (State Machine - SM) - in cui ogni transizione ha un solo arco entrante e un solo arco uscente. Ciò implica che non può esserci concorrenza ma può esserci conflitto (ovvero quando si pone la domanda: dove deve andare il token di un posto? In una o nell'altra transizione?). Matematicamente: Grafo marcato (Marked Graph - MG) - in cui ogni posto ha un solo arco entrante e un solo arco uscente. In questo caso non ci sono conflitti ma ci sono concorrenze. Matematicamente: Scelta libera (Free choice - FC) - in cui l'arco è o l'unico arco che esce da un posto oppure l'unico arco che entra in una transizione. In altre parole, ci può essere sia concorrenza sia conflitto, ma non nello stesso istante. Matematicamente: Scelta libera estesa (Extended free choice - EFC) - una rete di Petri che può essere trasformata in una FC. Scelta asimmetrica (Asymmetric choice - AC) - concorrenza e conflitto (insomma, confusion), ma non asimmetricamente. Matematicamente:
Estensioni Esistono molte estensioni delle reti di Petri. Alcune di esse sono completamente retro-compatibili (ad esempio le reti di Petri colorate) con la rete di Petri originaria, altre aggiungono proprietà che non possono essere modellate nella rete di Petri d'origine (ad esempio le reti di Petri tempificate). Se esse possono essere modellate nella rete di Petri originale, esse non sono reali estensioni ma sono modi conveniente di far vedere la stessa cosa, e possono essere trasformate con opportune formule matematiche nell'originale rete, senza perdere di significato. Le estensioni che non possono essere trasformate sono a volte rappresentazioni molto potenti, ma tipicamente perdono una quantità di tools matematici disponibili per analizzare le normali reti di Petri.
Il termine rete di Petri ad alto livello è usato per molti formalismi delle reti di Petri che estendono il formalismo base P/T. Questo include anche le reti di Petri colorate, gerarchiche e tutte le altre estensioni citate in questa sezione.
Una breve lista delle possibili estensioni:
In una rete di Petri standard, i token sono indistinguibili. In una rete di Petri colorata, ogni token ha un valore. Nei tool popolari per le reti di Petri colorate, come CPN Tool, il valore del token è tipizzato e può essere testato e manipolato con un linguaggio di programmazione funzionale. Un sussidiario delle reti di Petri colorate sono le reti di Petri well-formed, dove le espressioni degli archi e di controllo sono vincolate a rendere più semplice l'analisi della rete. Un'altra estensione popolare della rete di Petri è la gerarchia: la gerarchia nella forma di diverse viste che supportano vari livelli di rifinimento e astrazione furono studiate da Fehling. Un'altra forma di gerarchia si trova nelle cosiddette reti di Petri ad oggetti o nei sistemi ad oggetti, dove una rete di Petri può contenere diverse reti come suoi token, stabilendo una gerarchia di reti di Petri innestate che comunicano sincronizzando le transizioni su diversi livelli. Un Vector Addition System with States (VASS) può essere vista come generalizzazione di una rete di Petri (ma con qualcosa in meno). Si consideri un automa a stati finiti dove ogni transizione è tradotta in una transizione della rete di Petri. La rete di Petri segue dunque l'evoluzione dell'automa, ovvero una transizione nell'automa è eseguita allo stesso tempo nella corrispondente transizione nella rete di Petri. È possibile eseguire una transizione nell'automa solo se la corrispondente transizione nella rete è abilitata; è possibile che la transizione nella rete di Petri scatti solo se c'è una transizione dal corrente stato dell'automa etichettata da essa. Quello che gli automi a stati finiti non possono rappresentare sono le situazioni di sincronizzazioni che invece sono presenti nella rete di Petri: ad esempio, quando due posti sono in attesa su una transizione e la transizione non può scattare fin quando i due posti non rispondono entrambi ai vincoli della transizione. Le reti di Petri con priorità aggiungono meccanismi di priorità alle transizioni, in base a cui una transizione non può scattare se una transizione di priorità più alta è abilitata. Le transizioni sono divise in gruppi di priorità, ad esempio il gruppo di priorità 3 può solo scattare se tutte le transizioni nel gruppo 1 e nel gruppo 2 sono disabilitate. Con un gruppo di priorità, lo scatto è ancora non deterministico. La proprietà non-deterministica è di grande rilievo, poiché consente all'utente di astrarre un gran numero di proprietà (dipende dall'uso che bisogna fare della rete). In alcuni casi inoltre è necessario aggiungere al modello una tempificazione. Nascono così le reti di Petri temporizzate, nelle quali ci sono delle transizioni che sono temporizzate e altre che non lo sono (tipicamente le transizioni senza tempificazione hanno una priorità più alta di quelle temporizzate). Si vedano anche le reti di Petri stocastiche che aggiungono un tempo non-deterministico per rendere un concetto di casualità delle transizioni. La distribuzione casuale esponenziale è tipicamente utilizzata per "tempificare" tali reti. In questo caso, il grafo di raggiungibilità della rete diventa una catena di Markov. Le reti di Petri dualistiche (dP-Nets) sono un'estensione delle reti di Petri sviluppata da E. Dawis et al. per rappresentare meglio i processi del mondo reale. Le reti dP bilanciano la dualità di cambiamento/non cambiamento, azione/passività, tempo/spazio (di trasformazione), ecc., tra i costrutti bipartiti di trasformazione e luogo della rete di Petri, risultando nella caratteristica unica della marcatura della trasformazione, ossia quando la trasformazione è "funzionante" essa viene marcata. Ciò consente alla trasformazione di attivarsi (o essere marcata) più volte, rappresentando il comportamento nel mondo reale della portata del processo. La marcatura della trasformazione presuppone che il tempo di trasformazione debba essere maggiore di zero. Un tempo di trasformazione pari a zero, utilizzato in molte tipiche reti di Petri, può essere matematicamente attraente ma poco pratico nel rappresentare i processi del mondo reale. Le reti dP sfruttano anche la potenza dell'astrazione gerarchica delle reti di Petri per rappresentare l'architettura dei processi. I sistemi di processi complessi sono modellati come una serie di reti più semplici interconnesse attraverso vari livelli di astrazione gerarchica. È stata dimostrata l'architettura del processo di una commutazione di pacchetto, dove i requisiti di sviluppo sono organizzati attorno alla struttura del sistema progettato.
Ci sono molte altre estensioni alla rete di Petri, ma è importante ricordare che quanto più aumenta la complessità della rete in termini di proprietà estese, tanto più difficile è usare i tools standard per valutare certe proprietà della rete. Per questa ragione, è una buona idea usare il tipo di rete più semplice possibile per un dato processo di modellizzazione.
Modelli successivi di concorrenza