Possibili estensione delle reti di Petri
Fissare il numero massimo di token ammissibili in un posto.
Posso farlo senza bisogno di nuove regole: aggiungo un "posto complementare", lo collego alle transizioni del posto originale invertendo gli archi. Metto nel complementare tanti gettoni quanti sono i posti massimi meno il numero di gettoni che ci sono già nel posto ordinario.
Archi inibitori
La transazione scatta se NON ci sono gettoni nel posto collegato con l'arco inibitore. (arco con pallino bianco)
Anche in questo caso posso ricondurre ad una rete di Petri standard (a patto che il numero di posti sia limitato). Basta che creo un P1 complementare con 1 gettone e collego questo P1 complementare con doppio arco a T0 (ci dovrà essere 1 gettone in P1Comp, ma potrà essercene al massimo 1 tra P1 e P1comp!).
Un esempio del problema di sincronizzazione lettori/scrittori con gli archi inibitori:
Tentare di togliere il peso degli archi:
Archi uscenti: posso introdurre un "posto globale" che ha una connessione a doppio senso con qualsiasi transizione eccetto che con la transizione interessata. Creo un posto ed una transizione "bis" e collego l'arco di ritorno al posto globale dalla transizione bis (figura). In tal caso l'unica transizione che potrà scattare dopo T0 e proprio T0bis!!!
Archi entranti:
E' molto più complesso... Il problema non é fare scattare con 2 gettoni, ma fare in modo che non scatti prima che ci siano 2 gettoni!!! Questo é un esempio (ma non automatizzabile con 3 o 4 o N gettoni!!!) (quindi ben venga il formalismo dei pesi degli archi)
Reti condizioni eventi (C/E)
Archi peso 1
Posti capacità 1
I posti si comportano da variabili booleane
Esiste sempre un'equivalente C/E di una rete P/T purché sia limitata: basta estenderla
Reti conservative
Una rete P/T con marcatura M si dice conservativa rispetto ad una funzione di pesi P se per ogni marcatura M1 raggiungibile da M la sommatoria di tutti i gettoni non varia!
Copribilità
Relazione tra marcature
M copre M1 se e solo se per ogni posto P il numero di gettoni é sempre maggiore-uguale in M1 che in M
M1 é copribile da M se esiste una marcatura (M2) raggiungibile da M che copre M1. Ovvero la copribilità non deve essere per forza diretta!
Definita M la marcatura minima (con il minimo numero di token) per attivare la transizione t allora t é morta solo se M non é raggiungibile dalla marcatura corrente
Se M copre M1 allora tutte le transizioni abilitate in M1 lo sono anche in M (più potrebbero esserlo delle altre!)
Albero di copertura
Ovvero ridurre una rete infita in un albero (e grafo) (quindi finito)!
...nel caso in cui abbia una marcatura che copre se stessa (si può ripresentare simile, ma con uno o più posti incrementati) posso mettere w (omega: significa infinito) nel posto della marcatura che viene incrementato...
Proprietà degli alberi di copertura:
- Una rete di Petri é: limitata se w (omega) non compare in nessun nodo dell'albero di copertura
- Una rete di Petri é: binaria se compaiono solo 0 e 1
- Una transizione é morta (0-live) se non compare nell'albero di copertura
- Condizione necessaria affinché una marcatura M sia raggiungibile é che esista un nodo etichettato con una marcatura che copre M
- Non c'é modo di capire dall'albero se una rete é viva (dimostrato nei primi 10 minuti della lezione del 21 aprile: esistono reti morte che possono avere lo stesso grafo di reti vive (bastava aggiungere un arco da P3 a T4: potenzialmente si possono esaurire quindi i P3 (quindi uno stato di (0;1;0) che é preso in considerazione nell'albero come (0;1;w), ma in realtà é un deadlock!)
Nessun commento:
Posta un commento