Ingegneria del software - Appunti

ETI DI ETRI

La teoria delle reti di Petri (definita nei primi anni Sessanta dal tedesco Carl Adam Petri) riguarda un formalismo

per la descrizione concettuale (attraverso grafi bipartiti) e matematica del comportamento dei sistemi

(distribuiti).

Si tratta, sostanzialmente, di un’estensione del modello degli automi a stati finiti, che meglio si presta alla

rappresentazione dei processi che caratterizzano un sistema, degli eventi e delle variazioni di stato che ne

determinano l’evoluzione e il comportamento esibito.

Il modello delle reti di Petri, articolato in posti (o stati) e transizioni (o eventi), ben evidenzia il comportamento

sequenziale delle componenti di un sistema e la natura concorrenziale di quest’ultimo nel complesso.

4.1 Reti e Net System

Una rete (orientata) è definita come una tripla di elementi tali che:

L’elemento rappresenta l’insieme dei posti, l’insieme delle transizioni, l’insieme delle relazioni di flusso che

collegano i posti alle transizioni e le transizioni ai posti.

NOTA - Nella rappresentazione grafica delle reti di Petri, i posti e le transizioni costituiscono i vertici del grafo bipartito,

mentre le relazioni di flusso corrispondono agli archi.

Si definisce Net System una tupla di elementi , cioè una rete alla quale è associato un

caso iniziale , corrispondente alle condizioni (ai posti) che sono verificate all’inizio dell’evoluzione di un

sistema.

I Net System corrispondono, essenzialmente, alle possibili implementazioni di una particolare rete di Petri.

Si definiscono Elementary Net System (o EN System) i sistemi che associano ai posti una condizione booleana,

per cui ognuno può essere verificato o non verificato.

NOTA - Altre classi di sistemi introducono un concetto di molteplicità, per cui a ciascun posto possono corrispondere più

marcature.

4.2 Casi, precondizioni e postcondizioni

In generale, si definisce l’insieme dei casi possibili di un sistema, perciò .

Come è bene illustrato dalla rappresentazione grafica degli EN System, un caso corrisponde a uno stato

particolare del sistema e, a sua volta, comprende gli stati (locali) delle sue singole componenti.

2

posto

s transizione (evento)

t relazione di flusso

s t stato locale (marcatura)

•

Figura 1 Elementi per la rappresentazione delle reti di Petri

Data una transizione , si definisce o l’insieme delle precondizioni di , cioè l’insieme degli stati (locali)

che devono essere verificati affinché la transizione possa avvenire.

Si definisce, invece, o l’insieme delle postcondizioni di , cioè l’insieme degli stati (locali) che

sussistono non appena la transizione si è verificata. |

{ }

|

{ }

4.3 Purezza, semplicità e principio di estensionalità

Una rete di Petri si definisce pura se e solo se per ogni sua transizione gli insiemi delle precondizioni e delle

postcondizioni di sono disgiunti. In altre parole, una rete è pura se non comprende anelli che ricolleghino uno

stesso posto alla medesima transizione, sia in ingresso, sia in uscita.

NOTA - Le violazioni della proprietà di purezza si definiscono side condition (vedi Contatto).

Una rete di Petri rispetta il requisito di semplicità se non comprende transizioni con le stesse precondizioni e

postcondizioni. ( ) ( )

NOTA 1 - Le proprietà di purezza e semplicità fanno riferimento alle reti di Petri, non ai Net System che da esse sono derivati.

NOTA 2 - Le reti che soddisfano le proprietà di purezza e semplicità danno luogo a sistemi classificati come Condition/Event

System, nei quali le transizioni sono completamente identificate dalle rispettive precondizioni e postcondizioni.

In generale, le reti di Petri devono essere tali da garantire l’osservabilità di ciascun evento attraverso la variazione

di stato che produce. Una rete non pura, ad esempio, viola questo requisito, chiamato principio di estensionalità.

Figura 2 Violazioni del requisito di purezza (a) e di semplicità (b)

4.4 Matrice di incidenza

Le reti di Petri ammettono una rappresentazione matriciale, particolarmente utile per la loro implementazione

attraverso il calcolatore.

Data una rete generica si definiscono la matrice di ingresso (di input) e la matrice di uscita

| | | |

(di output) aventi un numero di righe e di colonne pari, rispettivamente, alla cardinalità dell’insieme dei

| | | |

posti e dell’insieme delle transizioni .

La matrice di ingresso mostra la corrispondenza tra i posti e le transizioni delle quali i posti sono precondizioni.

La matrice di uscita mostra la corrispondenza tra i posti e le transizioni delle quali i posti sono postcondizioni.

È anche possibile costruire un’unica matrice di incidenza che sovrappone le matrici di ingresso e di uscita

indicando gli input con il segno meno e gli output con il segno più.

NOTA - La matrice di incidenza sintetizza le informazioni contenute nelle matrici di ingresso e di uscita esclusivamente

rispetto alle reti pure. Solo in questo caso, infatti, gli elementi non nulli di tali matrici si trovano in posizioni esclusive.

3 [ ]

Figura 3 Matrice di incidenza per un sistema Produttore || Consumatore

4.5 Concessione e scatto

Le reti di Petri (quindi i Net System derivati), forniscono una rappresentazione atemporale dei sistemi.

In altre parole, non è possibile determinare con esattezza l’evoluzione di un sistema, ma solo gli stati ai quali esso

può pervenire in virtù della sua struttura. Per questa ragione, è particolarmente utile stabilire in modo formale le

regole che presiedono all’evoluzione di un sistema, cioè le regole di concessione (o abilitazione) e scatto.

NOTA - La regola di scatto definisce la semantica dei Net System.

Dato un EN System e l’insieme dei suoi casi possibili .

La generica transizione è abilitata (può verificarsi) se e solo se tutte le precondizioni di sono soddisfatte e le

postcondizioni non lo sono. In simboli:

Non appena una transizione abilitata si verifica, ha luogo una variazione di stato (scatto) che porta il sistema da

una condizione a una nuova condizione : le precondizioni della transizione non sono più verificate, mentre

lo sono le postcondizioni. ( )

4.6 Situazioni fondamentali

4.6.1 Concorrenza

Lo scatto di una transizione produce una variazione di stato locale nel sistema e, naturalmente, non influisce

sugli stati che non riguardano in qualità di precondizioni o postcondizioni. D’altra parte, tali stati possono

abilitare altre transizioni e queste (per la regola di scatto) possono verificarsi contemporaneamente alla prima e in

numero variabile.

Ciò definisce una situazione di concorrenza, per cui occorre estendere la formulazione delle regole di concessione

e scatto a un insieme indeterminato di transizioni. { }

Un generico insieme di transizioni concorrenti è abilitato se e solo se tutte le transizioni in

sono abilitate e indipendenti tra loro.

La relazione di indipendenza sussiste se le precondizioni e le postcondizioni di ciascuna transizione in

sono distinte. In altre parole: | ( ) ( ( ) ( ))

NOTA - Il criterio di indipendenza di precondizioni e postcondizioni è fondamentale per rendere conto delle situazioni

particolari che possono caratterizzare l’evoluzione di un sistema.

Quanto allo scatto di un insieme di transizioni, esso produce una variazione di stato globale nel sistema (step)

ed è definito come nel caso locale: ( )

4.6.2 Conflitto

Una generica precondizione può contribuire all’abilitazione di più eventi, che, in questo caso, si escludono a

vicenda (entrambi possono avvenire, ma il verificarsi dell’uno inabilita l’altro).

Si tratta di una circostanza nota come situazione di conflitto e non rappresenta necessariamente un

comportamento indesiderato: un conflitto è, semplicemente, una situazione non deterministica nell’evoluzione di

un sistema. 4

Formalmente, date due transizioni distinte e , si ha una situazione di conflitto relativamente a un caso se,

in base alla regola di concessione (per una singola transizione e per un insieme di eventi), , ma non

{ } . Figura 4 Situazione di conflitto

4.6.3 Contatto

Se un particolare caso comprende sia precondizioni, sia postcondizioni di una stessa transizione , lo stato

locale corrispondente del sistema non può evolvere, in quanto la regola di concessione non è soddisfatta.

Tale circostanza è detta situazione di contatto.

Si definisce contact-free (libero da contatto) qualunque sistema nel quale una situazione di contatto non può mai

avvenire. In simboli, un sistema è contact-free se e solo se:

NOTA 1 - La particolare situazione nella quale uno stesso posto è sia precondizione, sia postcondizione di una transizione

si definisce side condition - - e, graficamente, corrisponde a un anello.

NOTA 2 - Talvolta, le situazioni di contatto sono prodotte volontariamente per ottenere comportamenti particolari, ma in

generale rispecchiano un errore di astrazione.

4.6.4 Confusione

La situazione di confusione risulta dalla “sovrapposizione” delle condizioni di concorrenza e conflitto, i cui effetti

concomitanti possono alterare in modo significativo l’evoluzione di un sistema. { }

{ }

Dato l’EN System in Figura 5, nel caso tale che , , , possono verificarsi tre

diverse sequenze di eventi: { } { };

1. le transizioni e avvengono contemporaneamente, perciò { } { };

2. si verifica la transizione , quindi la transizione , perciò { } { }

3. si verifica la transizione , quindi il conflitto tra le transizioni e , perciò

{ } { }.

oppure

Per via della confusione, l’evoluzione del sistema dipende sostanzialmente dall’ordine in cui si verificano gli eventi

e il comportamento esibito cambia (anche radicalmente) di caso in caso.

NOTA - In altre parole, la confusione determina la differenza tra l’evoluzione del sistema a step (a eventi concorrenti) e a

singole transizioni.

Nel caso 1, la concorrenza delle transizioni e evita il conflitto tra le transizioni e . Lo stesso accade nel

caso 2, con il verificarsi della transizione . Nel caso 3, invece, lo scatto della transizione porta il sistema nella

situazione non deterministica di conflitto, per cui gli eventi e sono in mutua esclusione.

Figura 5 Situazione di confusione

5

A seguito degli eventi, il sistema può raggiungere lo stesso caso finale per effetto di condizioni intermedie diverse,

oppure, attraverso il conflitto, può approdare a uno stato globale differente.

4.7 Grafo dei casi

Dato un generico EN System , si definisce Case Graph (o grafo dei casi) la rappresentazione degli stati globali che

il sistema può raggiungere a partire da un caso iniziale , per effetto delle diverse variazioni di stato locali

possibili (ossia delle transizioni). P2, C1

prd con

P1, C1 P2, C2

acq c