Un algoritmo concorrente per l'analisi dei processi aziendali

(1)

U

NIVERSIT

A DEGLI

`

S

TUDI DI

P

ISA

FACOLT `A DI SCIENZE MATEMATICHE, FISICHE E NATURALI

Corso di Laurea Magistrale in Business Informatics

U

N A L G O R I T M O C O N C O R R E N T E P E R

L

’

A N A L I S I D E I P R O C E S S I A Z I E N D A L I

Candidato:

Maria Tourbanova

Relatori:

Prof. Roberto Bruni

Phd. Giorgio O. Spagnolo

(2)

Indice

1 Introduzione

4

1.1 Struttura della tesi . . . .

7

2 Modellazione di un processo

8

2.1 Lo standard BPMN . . . .

8

2.2 Esempio di modello di processo BPMN . . . 16

2.3 Reti di Petri . . . 18

2.4 Workflow Net . . . 20

2.5 Trasformazione da BPMN a reti di Petri . . . 25

2.6 Esempio di trasformazione di modello di processo in una rete di

Petri . . . 28

3 Unfolding

29

3.1 Unfolding troncato di McMillan . . . 31

3.2 BCS Unfolding . . . 32

3.3 Esempio di Unfolding . . . 34

4 Contributo originale

36

4.1 Unfolding Parallelo . . . 36

4.2 Strutture Dati . . . 37

4.3 Algoritmo BCS Unfolding parallelo . . . 38

(3)

INDICE

2

5 Esempi Pratici

47

5.1 Esempio A . . . 47

5.2 Esempio B . . . 50

5.3 Esempio Rete Giocatori

. . . 52

5.4 Esempio Rete Negozio . . . 53

6 Test e Prestazioni

55

7 Conclusioni

61 A Risultati Test

63

(4)

Sommario

L’argomento trattato in questo lavoro si colloca nell’ambito del Business Process

Management e in particolare fa riferimento alla verifica di ben formatezza di

processi e diagrammi di collaborazione modellati tramite la notazione BPMN e

analizzati mediante trasformazione in reti di Petri.

La tesi si concentra sulla tecnica di analisi delle reti di Petri che si avvale

della procedura di Unfolding troncato che permette di rappresentare in maniera

esauriente e compatta i possibili comportamenti dei processi.

Lo scopo principale di questo lavoro è stato quello di effettuare il

refac-toring del algoritmo BCS Unfolding sequenziale, proposto in un lavoro di

te-si precedente, implementato come un plugin di ProM, introducendo l’uso di

multithreading.

Le prestazioni raggiunte dall’algoritmo parallelo sono state messe a

confron-to con quelle ottenute utilizzando l’algoritmo BCS Unolding sequenziale. Tale

confronto è stato portato avanti sulla base dei tempi di computazione. I risultati

ottenuti mostrano come l’analisi che si basa sul BCS Unfolding parallelo offra

prestazioni più soddisfacenti rispetto all’analisi con BCS Unfolding sequenziale

nelle reti di grandi dimensioni.

(5)

Capitolo 1

Introduzione

Sin dagli inizi del Novecento, al termine della seconda rivoluzione industriale, la

parola d’ordine della struttura economica capitalistica occidentale è stata

otti-mizzare. Nel 1911, Taylor propose la suddivisione del lavoro in compiti

elemen-tari [1] e nel 1913 Ford mise in atto le indicazioni teoriche di Taylor realizzando

la prima catena di montaggio [2]. Da allora, l’obiettivo primario di ogni

azien-da competitiva è l’abbassamento dei costi di produzione e l’ottimizzazione delle

tempistiche. Per raggiungere questi obiettivi, le aziende hanno elaborato le più

svariate strategie, che negli ultimi decenni di globalizzazione hanno portato anche

a stravolgimenti nella struttura aziendale, come la nascita delle multinazionali.

Tuttavia, in tempi più recenti, l’attenzione è ritornata, come ai tempi di

Taylor e Ford, sull’ottimizzazione dei processi aziendali, che sono il centro

del-l’azienda stessa. Per definizione, un processo aziendale (Business Process) è

un insieme di attività parzialmente ordinate, svolte all’interno dell’azienda, che

creano valore trasformando le risorse (input del processo) in un prodotto (output

del processo) destinato ad un soggetto interno o esterno all’azienda. Il processo

punta al raggiungimento di un obiettivo aziendale, determinato durante la fase

di pianificazione se questa è presente. Tanto le risorse quanto il prodotto possono

essere beni, servizi o informazioni oppure una combinazione di questi elementi.

La trasformazione dell’input in output può essere eseguita con l’impiego di

lavo-ro umano, di macchine o di entrambi. Un plavo-rocesso è tanto più valido quanto più

(6)

5 numerose sono le sue istanze svolte dall’azienda. Per economia di scala,

risul-ta quindi evidente che l’ottimizzazione di un processo porrisul-ta necessariamente ad

un’ottimizzazione della produzione, con risparmio di tempo e denaro: il tempo o

le risorse risparmiati per un processo vengono infatti moltiplicati per il numero

delle sue istanze.

La gestione dei processi ricade nell’ambito del Business Process Management,

una disciplina che si occupa di tutte le attività utili a modellare, automatizzare,

eseguire, controllare, misurare e ottimizzare i processi di business. La fase della

modellazione (Business Process Modelling), consiste nella rappresentazione

gra-fica dei processi tramite degli appositi linguaggi di modellazione, ognuno dotato

di suoi simboli e di proprie regole. La rappresentazione grafica dei processi ne

semplifica infatti l’analisi e la comprensione.

Il Business Process Modeling Notation (BPMN) è una notazione grafica che

consente di comporre modelli di processi in modo intuitivo. Oggi è considerato lo

standard della modellazione. L’obiettivo primario del BPMN è quello di fornire

uno strumento sufficientemente espressivo, ma non eccessivamente tecnico, che

faccia da ponte tra da un lato gli analisti di business e il management aziendale,

dall’altro le figure tecniche che si occupano dell’effettiva implementazione dei

processi. Il risultato degli sforzi di standardizzazione è una notazione visuale

per indicare l’ordinamento delle attività nell’evoluzione dei processi.

Il BPMN è tuttavia una notazione grafica che presenta alcune limitazioni

come la mancanza di semantica formale che può portare a diverse interpretazioni

di modelli e a costruire diagrammi con comportamenti inattesi e non desiderati

(ad esempio, con possibilità di deadlock). La verifica formale di un modello

BPMN garantisce che esso abbia le proprietà desiderate. Una soluzione è quella

di trasformare i modelli BPMN in un linguaggio formale, le reti di Petri, ed

eseguire una verifica automatizzata su questi reti e, se possibile, riportare gli

esiti dell’analisi sul diagramma originale.

(7)

6 Le reti di Petri sono un linguaggio formale adatto a modellare il

comporta-mento dei sistemi in termini di flussi e sono supportati da strumenti di analisi,

come ProM [3], Woflan [4] e WoPed [5].

Purtroppo, in generale, l’analisi di correttezza dei processi è un problema

NP-completo e solo per opportune classi di reti diventa trattabile. La necessità

di sviluppare un nuovo algoritmo per l’analisi delle reti di Petri è nata dal fatto

che gli strumenti esistenti, basati su semantiche non concorrenti (interleaving),

non sono in grado di analizzare in tempi accettabili le reti con un numero di

elementi elevato. Tali reti spesso vengono generate dai diagrammi BPMN di

collaborazione, nei quali sono presenti più processi.

In un precedente lavoro di tesi, Daniele Cicciarella et al [15] hanno proposto

un algoritmo sequenziale, chiamato BCS Unfolding, che, sfruttando tecniche di

semantica della concorrenza, permette di analizzare diagrammi di grandi

dimen-sioni in tempi ragionevoli, molto minori rispetto ai tool esistenti. Tecnicamente,

l’analisi di una rete di Petri con BCS Unfolding si basa sulla costruzione di una

rete di occorrenze partendo dalla rete originale e sulla ricerca dei punti di Cutoff

in essa. Anche in presenza di cicli nel diagramma di partenza viene garantito

che la rete di occorrenze è finita.

Con il lavoro della presente tesi è stato effettuato un refactoring concorrente

di BCS Unfolding ed è stata proposta una sua nuova versione con l’uso dei thread.

Per rendere fruibile agli analisti il risultato della verifica formale,

l’imple-mentazione dell’algoritmo parallelo è collegata alle estensioni di altri due plugin

esistenti di ProM. Il primo trasforma un diagramma in notazione BPMN in una

rete di Petri. Il secondo proietta i punti critici (ad esempio deadlock) trovati

dall’unfolding parallelo sui nodi del diagramma BPMN di partenza e visualizza

alcune statistiche.

Durante la fase di test sono stati utilizzati più di mille diagrammi BPMN.

Per ogni diagramma è stata generata una rete di Petri e per ciascuna di queste

(8)

1.1. STRUTTURA DELLA TESI

7 sono state costruite una rete di unfolding con l’algoritmo BCS Unfolding

se-quenziale e una rete di unfolding con BCS Unfolding parallelo. A conferma della

correttezza dell’algoritmo parallelo, per ogni rete di Petri le reti di unfolding così

costruite sono risultate identiche ed entrambi gli algoritmi hanno prodotto gli

stessi risultati di analisi. Il risultato principale è che per i diagrammi le cui reti

di unfolding presentano un numero elevato di elementi, il tempo di esecuzione

dell’algoritmo parallelo è risultato minore rispetto a quello sequenziale.

1.1 Struttura della tesi

Nel Capitolo 2 vengono introdotte la notazione BPMN, le reti di Petri e le regole

di trasformazione di un diagramma BPMN in una rete di Petri.

Nel Capitolo 3 sono riassunte la tecnica di Unfolding di McMillan e

quel-la di BCS Unfolding, utili ad effettuare analisi più efficaci di quelle basate su

semantiche interleaving per le reti di Petri.

Nel Capitolo 4 sono presentati l’algoritmo BCS Unfolding parallelo e la sua

implementazione con uso dei thread. Questi costituiscono il contributo principale

del lavoro di tesi.

Nel Capitolo 5 è mostrato il funzionamento di plugin completo con il

fra-mework ProM su alcuni diagrammi BPMN.

Nel Capitolo 6 sono mostrati alcuni test effettuati su un campione

significa-tivo di reti di Petri con l’algoritmo BCS Unfolding sequenziale, BCS Unfolding

parallelo e Woflan e le loro prestazioni vengono messe a confronto.

Nel Capitolo 7 viene riassunto il contributo della tesi e vengono presentate

alcune considerazioni conclusive.

(9)

Capitolo 2

Modellazione di un processo

2.1 Lo standard BPMN

Il Business Process Model and Notation (BPMN) è uno degli standard più

uti-lizzati per la modellazione di processi di business. La notazione BPMN è stata

sviluppata dalla "Business Process Management Initiative" [6] e

successivamen-te mansuccessivamen-tenuta dal "Object Management Group" [7], associazioni no-profit che

raccolgono operatori nel campo dell’informatica e dell’analisi organizzativa.

L’obiettivo della BPMN è quello di fornire uno standard di

rappresenta-zione efficace, facile da utilizzare e da comprendere da parte degli utenti di

business interessati al problema della modellazione, progettazione ed eventuale

informatizzazione dei processi aziendali.

La versione 1.0 dello standard è stata rilasciata nel 2004, mentre dal 2011 è

disponibile la versione 2.0 [9], che è rimasta stabile negli anni successivi e per la

quale non si prevedono ulteriori estensioni in tempi brevi.

Gli elementi grafici disponibili in BPMN, sono più di cinquanta tra questi si

possono selezionare alcuni elementi grafici di base, generalmente sufficienti per

modellare una vasta casistica di processi. A questi si possono aggiungere elementi

addizionali per dare una maggiore efficacia rappresentativa nei casi di processi

molto complessi, ma senza modificare l’impostazione base della notazione usata.

Gli elementi grafici che costituiscono i diagrammi BPMN sono classificabili in

(10)

2.1. LO STANDARD BPMN

9 solo quattro categorie principali:

• Flow Objects: Events, Activities, Gateways;

• Connecting Objects: Sequence Flow, Message Flow, Association;

• Swim Lanes: Pool, Lane;

• Artifacts: Annotation, Data Object.

Flow Objects

I Flow Objects sono elementi usati per descrivere: eventi, attività e decisioni di

un processo. I Flow Objects di base sono tre: Events, Activities e Gateways.

Events

Gli events rappresentano l’interazione tra il business process e il suo ambiente.

Modellano qualcosa che accade nel mondo reale, hanno un significato di business

e non hanno una durata (al contrario delle activities). Gli events influenzano il

flusso di un processo e solitamente hanno un trigger e un impatto. In generale

richiedono o prevedono una risposta. Gli events si dividono in tre tipologie:

Start Event, Intermediate Event ed End Event.

Lo Start Event indica un evento che dà inizio ad un processo; in altri termini

indica un accadimento nel mondo reale che crea una nuova istanza del processo

di business. Lo Start Event è rappresentato graficamente nella Figura 2.1a.

Un Intermediate Event è usato per indicare un evento che accade dopo

che un processo è iniziato e prima che sia terminato. L’Intermediate Event è

rappresentato graficamente nella Figura 2.1b.

L’End Event serve ad indicare un evento che segnala la possibile conclusione

di un processo. L’End Event è rappresentato graficamente nella Figura 2.1c.

Ogni processo comprende un unico Start Event e viene concluso da uno o più

End Events.

(11)

2.1. LO STANDARD BPMN

10 (a) Start Event

(b) Itermediate Event

(c) End Event

Figura 2.1: Events BPMN

Activities

Un activity rappresenta un lavoro che è realizzato nel corso di un processo di

business. Le activities hanno una durata e impiegano e producono risorse. Un

activity può essere atomica o non atomica (composta): Task o Sub-Process.

Un Task è usato quando il lavoro rappresentato dall’activity è considerato

atomico, cioè non è scomponibile ad un ulteriore livello di dettaglio. Un task

è rappresentato genericamente da un rettangolo con gli angoli arrotondati. Il

BPMN mette a disposizione dei tipi specializzati di task rappresentati

grafica-mente (vedi Figura 2.2) con dei marker per descrivere delle attività specializzate,

come ad esempio:

• Message Task: per inviare/ricevere un messaggio a/da un partner;

• Task Manuale: è un task gestito manualmente;

(12)

2.1. LO STANDARD BPMN

11 Figura 2.2: Tasks

Gateways

I Gateways sono elementi usati per definire i controlli del flusso di lavoro e come

questi convergono o divergono in un processo; i gateways principali sono riportati

nella Figura 2.3.

Un Exclusive Gateway è usato per creare (o richiudere) dei percorsi

alter-nativi in un flusso di processo: può essere rappresentato logicamente come uno

XOR su una condizione definita sul flusso.

Un Inclusive gateway (OR) è usato per creare dei percorsi alternativi ma

anche paralleli in un flusso di processo. A differenza dell’Exclusive Gateway,

sono valutate tutte le Condition Expressions e la valutazione positiva di una

condizione non esclude la valutazione delle altre Condition Expression e quindi

possono essere attraversati più percorsi contemporaneamente.

Un Parallel Gateway è usato per sincronizzare (combinare) percorsi di

pro-cesso paralleli. Un Parallel Gateway crea percorsi paralleli senza la valutazione

di una condizione: tutti i percorsi che sono in uscita dal gateway sono

attra-versati contemporaneamente. Un Parallel Gateway con più percorsi in ingresso

indica che questi devono essere tutti percorsi prima di poter proseguire con il

flusso di processo.

(13)

2.1. LO STANDARD BPMN

12 Figura 2.3: Gateways

Connecting Objects

I connettori sono principalmente di tre tipi: Sequences, Messages e Associations.

Sequence Flow

Un Sequence Flow è usato per indicare l’ordine con cui si presentano gli eventi

e in cui le attività sono realizzate in un processo. La Figura 2.4 rappresenta

graficamente un Sequence Flow.

Figura 2.4: Sequence Flow

Message Flow

Un Message Flow rappresenta il flusso di un messaggio tra due partecipanti:

il mittente che lo invia e il destinatario che lo riceve. In BPMN, i Pool, che

saranno descritti di seguito, rappresenteranno i partecipanti. Quindi i Message

Flow non devono connettere due oggetti nello stesso Pool. Un Message Flow è

rappresentato graficamente nella Figura 2.5.

(14)

2.1. LO STANDARD BPMN

13 Association

Una Association è usata per associare dati, informazioni o Artifact ad un

elemen-to grafico del BPMN. Mediante l’uso di una freccia si può indicare una direzione:

la freccia è verso l’Artifact per indicare un output, è verso il flusso per indicare

un input; una association bidirezionale è usata per indicare che quanto associato

è sia input che output. Potrebbe non essere indicata nessuna direzione, quando

l’Artifact o il testo è associato a una sequenza o messaggio dove è già chiara la

direzione. Una Association è rappresentata graficamente nella Figura 2.6.

Figura 2.6: Association

Swim Lanes

Le Swim Lanes servono per indicare le risorse e gli attori che partecipano alle

varie attività del processo e sono di due tipi: Pool e Lane.

Pool

I Pool rappresentano i partecipanti al processo e tipicamente corrispondono ad

attori appartenenti a diverse organizzazioni: i business partner coinvolti nel

pro-cesso di business. I partecipanti possono essere ruoli (p.e.: seller e buyer), oppure

entità organizzative (p.e.: Azienda, Fornitore).

Come detto in precedenza le interazioni tra diversi Pool avvengono tramite

Message Flow. Mentre i Sequence Flow non possono attraversare i confini di un

Pool. Un Pool può avere dei dettagli interni nella forma del processo che sarà

eseguito, oppure può non avere dettagli (Collapsed Pool). In questo caso viene

visto come una black box: i dettagli del processo realizzato all’interno di quel

pool non sono noti o rilevanti.

(15)

2.1. LO STANDARD BPMN

14 Lane

Un Pool può contenere una o più Lanes per attribuirne le attività a un

respon-sabile. Spesso le Lanes rappresentano i ruoli o i dipartimenti all’interno di una

organizzazione. Se quindi i Pools rappresentano spesso della classi di risorse

che partecipano a un processo, le Lanes consentono di partizionare questi in

sotto-classi.

I Sequence Flow possono attraversare i confini delle Lane. La relazione che

può legare Message Flow, Sequence Flow, Pool e Lane è ben definita dalla Figura

2.7. Figura 2.7: Vincoli di flusso per Pools e Lanes

Artifact

Gli Artifact consentono di indicare gli elementi di business, fisici o digitalizzati, su

cui il processo lavora e di dare delle informazioni aggiuntive relative al processo.

Gli Artifacts in BPMN sono Annotations e Data Objects.

Annotation

Le Text Annotations sono un meccanismo che consente a chi modella il processo

di fornire informazioni aggiuntive a beneficio di chi leggerà il diagramma.

(16)

2.1. LO STANDARD BPMN

15 Figura 2.8: Text Annotation

Data Object

I Data Objects sono Artifacts che mostrano come dati e documenti sono usati dal

processo; in altri termini permettono di specificare quali dati il processo richiede

e/o che cosa produce. Non hanno nessuna influenza diretta su Sequence Flow

o Message Flow del processo, ma forniscono solo una informazione aggiuntiva

su come opera il processo. Un Data Object può essere usato per definire input

e output di attività e può rappresentare un singolo oggetto o una collezione

di oggetti. Ad un Data Object può essere associato uno stato che può essere

cambiato o aggiornato durante il processo. Lo stato è rappresentato da una

annotazione testuale accanto o all’interno del Data Object.

(17)

2.2. ESEMPIO DI MODELLO DI PROCESSO BPMN

16

2.2 Esempio di modello di processo BPMN

La Figura 2.10 mostra un esempio modellato con la notazione BPMN che descrive

il processo di gestione semplificata di un esame, in cui il professore consegna

l’esame allo studente, questo lo svolge e lo riconsegna al professore, il quale a

sua volta lo valuta.

Gli attori coinvolti nello scenario sono Professore e Studente e sono

rappre-sentati nel diagramma con due Pool, ognuno con il proprio processo.

Il processo Professore inizia con l’invio al processo dello Studente del esame

da svolgere, dopo di che può effettuare una scelta o terminare o continuare. Nel

secondo caso, dopo aver ricevuto l’elaborato, il Professore prosegue con la sua

correzione e quindi con la comunicazione del risultato.

Lo Studente riceve il testo d’esame, svolge il compito, poi consegna l’elaborato

e attende il risultato.

Figura 2.10: BPMN - Gestione Esame Semplificato

Nel diagramma si vede che il Professore ha un ciclo che lo Studente non

prevede. Inoltre c’è la possibilità di terminazione del Professore subito dopo

(18)

2.2. ESEMPIO DI MODELLO DI PROCESSO BPMN

17 l’invio del esame senza alcuna interazione con lo Studente. In questo caso lo

Studente non raggiungerà mai il suo End Event. In seguito riprenderemo questo

esempio per mostrare come i suoi errori evidenti vengono catturati dall’analisi

basata su unfolding.

(19)

2.3. RETI DI PETRI

18

2.3 Reti di Petri

Le Reti di Petri [11], introdotte nel 1962 da Carl Adam Petri nella sua tesi di

dottorato, sono un formalismo grafico/matematico per la modellazione di

pro-cessi concorrenti. Largamente utilizzate nel settore informatico ed organizzativo,

sono molto utili per schematizzare le nozione di "concorrenza" e di

"contempo-raneità". Una rete di Petri è rappresentabile a partire da un grafo orientato e

bipartito, detto grafo di Petri.

Definizione 2.3.1 (Grafo di Petri). Grafo di Petri è una tupla P G = (P, T, F )

dove

• P è l’insieme finito delle piazze,

• T è l’insieme finito delle transizioni tale che P ∩ T = ∅, e

• F ⊆ (P × T ) ∪ (T × P ) è la relazione di flusso che descrive due insiemi di

archi orientati da piazze a transizioni e da transizioni a piazze.

Le notazioni che saranno utili in seguito sono:

• Una piazza p ∈ P è un input place (piazza in ingresso) di una transizione

t ∈ T se e solo se esiste un arco diretto da p a t, cioè se e solo se (p, t) ∈ F .

L’insieme di input place di t, detto preset, è indicato con •t.

• Un place p è una piazza in uscita di una transizione t se e solo se esiste un

arco diretto da t a p, cioè se e solo se (t, p) ∈ F . L’insieme di output place

per una transizione t, detto postset, è indicato con t•.

• Gli insiemi di transizioni che condividono p come piazza in ingresso o piazza

in uscita sono indicati, rispettivamente, con p• e •p .

Il grafo di Petri P G descrive solo la topologia della rete; per avere una rete

di Petri occorre introdurre il suo stato con una marcatura iniziale M : P → N,

(20)

2.3. RETI DI PETRI

19 che associa ad ogni piazza un numero naturale: M (p) rappresenta la quantità di

token presenti nella piazza p. Una rete di Petri P N è quindi un grafo di Petri P G

a cui è associata una funzione di marcatura iniziale M

0 : P N = (P, T, F, M

0 ).

Figura 2.11: Una rete di Petri che rappresenta più istanze di un processo singolo

Il comportamento dinamico di una rete di Petri è presentato nella seguente

definizione:

Definizione 2.3.2. Data una rete di Petri (P, T, F, M

0 ) e una marcatura M .

Lo scatto di una transizione è rappresentato da un cambiamento di stato della

rete di Petri.

• Una transizione t è abilitata in M se •t ⊆ M .

• M

−

→ M

t

0 _{indica che, t è abilitata in M e che il firing di t cambia lo stato}

della rete di Petri da M a M

0 = (M \ •t) ∪ t•.

• M → M

0 _{indica che vi è una transizione t tale che M}

₋

_{→ M}

t

0 _.

• M

1 ∗

−

→ M

n

significa che esiste una sequenza di transizioni t

1 , t

2 , . . . t

n−1

tale

che M

i

t

i

−

→ M

i+1

, con 1 ≤ i < n.

• Uno stato M

0 _{è raggiungibile da uno stato M se e solo se M}

₋

_{→ M}

∗

0 _.

• Una transizione t è abilitata in M se esiste M

0 _{raggiungibile da M che}

abilita t.

Di seguito sono elencate alcune proprietà di una rete di Petri P N = (P, T, F, M

0 )

• Liveness: Una transizione è live se può essere abilitata a partire da un

qualsiasi stato raggiungibile dalla marcatura iniziale. Una rete è live se lo

sono tutte le sue transizioni.

(21)

2.4. WORKFLOW NET

20 La proprietà di liveness è strettamente connessa all’assenza di possibilità di

deadlock (Deadlock-freedom) nel sistema rappresentato tramite la rete

di Petri, nel senso che ogni rete live è deadlock-free (il viceversa non è vero

in generale).

• Boundedness: Una rete è k-bounded se il numero di token in ciascun

place della rete è uguale o minore dell’intero positivo k in ogni marking

raggiungibile da M

0 , cioè M (p) ≤ k per ciascun place p e per ogni marking

M raggiungibile da M

0 (incluso M

0 ).

Una rete è bounded se è k-bounded per un qualche k.

Una rete di Petri N, M

0 è safe se è "1-bounded". Una rete safe garantisce

che ogni piazza conterrà al più un token.

Una rete è unbounded se esiste una piazza che può contenere un numero

arbitrario di token.

• Free-choice: Una Petri net è free-choice se per ogni coppia di transizioni

i loro preset sono coincidenti oppure disgiunti (∀t

1 , t

2 ∈ T, si ha •t

1 = •t

2 o •t

1 ∩ •t

2 = ∅). Le reti free-choice sono interessanti perché la proprietà di

essere live e bounded è verificabile in tempo polinomiale [12].

2.4 Workflow Net

Le reti di workflow [8] sono una classe particolare delle tradizionali reti di Petri

con concetti e notazioni che facilitano la rappresentazione dei processi aziendali.

Allo stesso tempo, introducono restrizioni strutturali che si rivelano utili per i

processi aziendali.

Definizione 2.4.1 (Workflow Net). Una Petri net P N = (P, T, F ) è chiamata

Workflow net (WF-Net) se:

(22)

2.4. WORKFLOW NET

21 • esiste una piazza finale o ∈ P , tale che o• = ∅,

• ogni altra piazza e transizione si trovano su un cammino orientato che

porta da i a o.

Implicitamente si assume che M

0 = {i}.

La logica di questa definizione è la seguente: un token nella piazza iniziale i

rappresenta un’istanza di processo che deve iniziare; un token nel place o

rap-presenta un’istanza di processo conclusa. Ogni piazza e ogni transizione in una

rete di workflow possono partecipare ad un’istanza di processo, quindi devono

trovarsi in un percorso da i a o.

In generale si desidera che un processo possa sempre essere portato a

compi-mento e che tutte le attività che include abbiano la possibilità di essere utilizzate.

Un processo è chiamato sound se:

• (no dead task) non sono presenti task inutili;

• (option to complete) in ogni momento dell’esecuzione del processo deve

poter essere possibile portare il processo a compimento;

• (proper completion) non vengono lasciate attività in sospeso dopo il

completamento del intero processo.

A livello formale delle workflow nets questo si traduce nella seguente

defini-zione:

Definizione 2.4.2 (Workflow Net Sound). Una workflow net è chiamata sound

se:

• per ogni transizione t, esiste un marking M raggiungibile da i che abilita

t;

• per ogni marking M raggiungibile da i è sempre possibile raggiungere un

marking M

0 che contiene un token nella piazza o, cioè tale che (M

0 (o) ≥ 1);

(23)

2.4. WORKFLOW NET

22 • quando un token è presente nella piazza o, tutte le altre piazze sono vuote

e o contiene un solo token (M ∈ [ii con M (o) ≥ 1 =⇒ M = {o}).

N

∗

è la rete N arricchita con una transizione t

∗

, detta reset, che collega la

piazza finale o con il place iniziale i (t

∗

: o → i ).

Per verificare se una rete N è sound si usa il seguente teorema [16]:

Teorema 2.4.1 (Main Theorem). N è sound se e solo se N

∗

è live e bounded.

Questo teorema è importante perché riconduce il problema della soundness a

proprietà ben studiate nell’ambito delle reti di Petri. Si noti che nel caso N sia

free-choice anche N

∗

è free-choice e la soundness può essere verificata in tempo

polinomiale.

Alcuni task di un WF-Net possono essere attivati manualmente oppure con un

messaggio, quindi non sono automatici. Per rappresentare questo fatto devono

essere creati ed uniti insieme diversi moduli di workflow. Un modulo di workflow

è una rete di workflow arricchita con particolari piazze necessarie all’interazione.

Definizione 2.4.3 (Modulo Workflow). Un modulo di workflow consiste in un

workflow net (P, T, F ) con:

• un insieme P

I

_{di piazze entranti con un insieme di archi entranti F}

I

_⊆

(P

I

_{× T ),}

• un insiemeP

O

_{di piazze in uscita con un insieme di archi in uscita F}

O

_⊆

(T × P

O

₎

e nessuna transizione è connessa contemporaneamente ad una piazza in entrata

e in uscita.

(24)

2.4. WORKFLOW NET

23 Figura 2.12: Due moduli workflow interagenti

Quando i moduli sono combinati insieme devono essere in grado di

interagi-re. Per ogni messaggio che può essere inviato deve esistere un modulo che può

riceverlo e per ogni messaggio che può essere ricevuto deve esistere un modulo

che può inviarlo (Strong Structural Compatibility).

Per verificare che l’insieme dei moduli interagenti si comporti bene si arriva

alla costruzione di un Workflow system (WF-System).

Definizione 2.4.4 (Workflow System). Un workflow system consiste in:

• un insieme di n moduli strutturalmente compatibili (con piazze iniziali

i

1 , . . . , i

n

, e con piazze finali o

1 , . . . , o

n

),

• un place iniziale i e una transizione t

i

da i a i

1 , . . . , i

n

,

(25)

2.4. WORKFLOW NET

24 Figura 2.13: Un esempio di Workflow System: combinazione di due moduli

Per un WF-System la proprietà di soundness è troppo restrittiva, in quanto

la tecnica utilizzata per la sua modellazione prevede una progettazione separata

di moduli. Inoltre i moduli possono essere riutilizzati in diversi sistemi ed è

improbabile che ogni funzionalità che offrono sia coinvolta in ogni sistema.

Definizione 2.4.5 (Weak Sound). Un WF-System è weak sound se soddisfa le

proprietà di "option to complete" e "proper completion".

Quindi in un WF-System weak sound possono essere presenti dead task, ma

sono garantiti la proper termination e l’assenza di deadlock. Per controllare la

weak soundness non si può più sfruttare il Main Theorem, perché la liveness di

N

∗

è fortemente correlata all’assenza di deadlock in N . I tool Woped e Woflan

effettuano l’analisi di soundness ma non quella di weak soundness.

(26)

2.5. TRASFORMAZIONE DA BPMN A RETI DI PETRI

25

2.5 Trasformazione da BPMN a reti di Petri

Attualmente sono disponibili numerosi tool che consentono di analizzare i

pro-cessi mediante le Petri net, anche se la maggior parte di essi si ferma al design,

con scopi prevalentemente didattici di descrizione dei processi.

I tre principali software per l’analisi dei business process sono WoPed [5],

Woflan [4] e ProM [3].

WoPed è un software open-source, sviluppato dalla University of Cooperative

Education Karlsruhe in Germania. La caratteristica principale di WoPeD è la

semplicità, l’interazione e l’immediatezza visiva che consentono al sistema di

essere un ottimo strumento per l’insegnamento e la ricerca. WoPeD consente di

effettuare due tipi differenti di analisi la simulazione e la verifica della soundness

della rete. Woped è disponibile per i principali sistemi operativi. La versione

utilizzata per la sperimentazione è la 3.6.0.

Woflan è un tool per l’analisi delle reti di workflow originariamente disponibile

per Windows e attualmente integrato in ProM.

La piattaforma denominata ProM, è un framework polifunzionale basato su

plugin, ed è distribuita tramite licenza CPL (Common Public Licence) ed è

quindi open source, permettendo così a Ricercatori e Sviluppatori di contribuire

al suo sviluppo implementando costantemente nuovi plugin. L’ultima versione

di ProM, comprende circa 500 plugin ed è disponibile per i principali sistemi

operativi, è la 6.6. Utilizzando ProM è possibile tradurre diagrammi BPMN in

reti di Petri. Le reti così ottenute possono essere analizzate con WoPed o ProM

stesso.

Quindi per effettuare un’analisi automatizzata di un processo modellato con

BPMN questo deve essere trasformato in una rete di Petri.

Il mapping tra BPMN e workflow net è riassumibile secondo le seguenti regole

(si veda [14] per la definizione formale):

(27)

2.5. TRASFORMAZIONE DA BPMN A RETI DI PETRI

26 • Lo Start Event è trasformato in un nodo place con il post-set formato da

un nodo transizione.

• Il modulo di Petri net che corrisponde ad un End Event è un place seguito

da una transizione seguita da un altro place.

• La modellazione di un Evento Intermedio è costituita da una transition

i cui post-set e pre-set contengono ciascuno una piazza.

• Un XOR-split (Data-based decision) nella rete di Petri è trasformato in

un place il cui post-set contiene due transizioni, che hanno un proprio

output place.

• Un XOR-join corrisponde a due transizioni che condividono lo stesso place

d’uscita.

• Un Parallel Gateway viene usato per simulare una biforcazione del flusso

delle attività in attività parallele oppure, viceversa, un ricongiungimento

di attività parallele in un flusso unico. Nel primo caso (AND-split) la sua

modellazione è costituita da una transizione con un input place e due

out-put place. Nel secondo caso (AND-join) invece, questo oggetto corrisponde

ad una transition che ha come pre-set due place e come post-set un place

solo.

• Il modulo che eguaglia un Event-based decision gateway è formato da

un place con un post-set contenente due transizioni ciascuna con un output

place proprio. Le transizioni in questo caso sono quelle che modellano i

task successivi e non create ex novo.

Nella Figura 2.14 è mostrato il mapping tra gli oggetti in notazione BPMN

e i moduli di una rete di Petri. A grandi linee, ad ogni arco del processo BPMN

corrisponde una piazza della rete e ad ogni nodo una o più transizioni (ci sono

(28)

2.5. TRASFORMAZIONE DA BPMN A RETI DI PETRI

27 alcune eccezioni a questa regola, come il caso di eventi iniziali e finali o quello

dei gateway event-based).

(29)

2.6. ESEMPIO DI TRASFORMAZIONE DI MODELLO DI

PROCESSO IN UNA RETE DI PETRI

28

2.6 Esempio di trasformazione di modello di

pro-cesso in una rete di Petri

Nella Figura 2.15 è mostrata una Petri net che descrive la gestione semplificata

di un esame. Tale rete è stata ottenuta applicando il mapping sopracitato al

diagramma BPMN - Gestione Esame Semplificato (Figura 2.10). Il riquadro

rosso racchiude i nodi della workflow net Professore, mentre quello blu contiene

il workflow net dello Studente. Le piazze p6, p13 e p16 rappresentano le interfacce

dei moduli e le transizioni ti e to sono quelle aggiunte per comporli assieme.

(30)

Capitolo 3

Unfolding

In questo capitolo sarà riassunto un precedente lavoro di tesi basato su una

tecnica innovativa per analizzare le reti, anche non free-choice, in tempi trattabili

e consentendo l’analisi di weak-soundness.

La procedura di unfolding genera, a partire da una Petri net, una rete di

occorrenze etichettata. Questa rete descrive in termini strutturali, le possibili

evoluzioni della rete di partenza esplicitando tutti i possibili eventi (scatti di

transizioni) e le relazioni fra loro, quindi potrebbe essere utilizzata per effettuare

un analisi della rete originale. Il vantaggio è che nel caso di transizioni concorrenti

nell’unfolding non si devono considerare esplicitamente tutti i loro interleaving.

La rete di occorrenze è una rete di Petri con assenza di cicli, di auto-conflitti

e di conflitti backward.

Definizione 3.0.1 (Rete di Occorrenze Etichettata). Data una rete di Petri

(P, T, F ), una rete di occorrenze etichettata è una Petri net N

0 = (P

0 , T

0 , F

0 )

con la funzione di etichettatura L che mappa P

0 nell’insieme P e T

0 nell’insieme

T , preservando preset e postset, e che soddisfa le seguenti proprietà:

• Partendo da un nodo qualsiasi, tutti i percorsi a ritroso sono finiti,

rag-giungono cioè un nodo sorgente (assenza di cicli);

• Ogni posto ha al massimo un arco in ingresso(assenza di conflitti

back-ward);

(31)

30 • Nessun nodo è in conflitto con se stesso.

Un nodo x è in conflitto con sé stesso se esistono due percorsi fino a x che

partono dallo stesso place e immediatamente si divergano.

L’occurence net che deriva da unfolding è caratterizzata dalla seguente

defi-nizione.

Definizione 3.0.2 (Rete di Unfolding). Se (N, M

0 ) è una rete marcata, allora

il suo unfolding è la massima rete di occorrenze etichettata su (N, M

0 ).

Le etichette del preset e del postset di ogni transizione del unfolding sono

mappate nel preset e nel postset della corrispondente transizione nella rete

origi-nale. Le etichette delle piazze nel unfolding senza un preset mappano il marking

iniziale della rete originale.

In questo modo l’unfolding riunisce in un’unica rete tutte le possibili reti di

occorrenze associabili a N. Se la rete di partenza presenta dei cicli l’unfolding da

essa creato può essere una rete con infinite piazze e transizioni.

Nella Figura 3.1a è mostrato un esempio di una rete di Petri, mentre nella

Figura 3.1b è presente il suo unfolding. Come si vede, nell’unfolding sono presenti

due istanze della transizione t4: una dipendente dal firing di t2 e l’altra da quello

di t4.

(a) Rete di Petri

(b) Unfolding

(32)

3.1. UNFOLDING TRONCATO DI MCMILLAN

31

3.1 Unfolding troncato di McMillan

La procedura di unfolding descritta sopra può proseguire indefinitamente quando

sono presenti dei cicli, perché questi vengono srotolati. McMillan [13] nel 1991

fu il primo a presentare una nuova tecnica per costruire un unfolding troncato e

usarlo per studiare la raggiungibilità di stati.

Le definizioni che saranno introdotte di seguito hanno lo scopo di permettere

la determinazione di alcune condizioni che consentano di tracciare un prefisso

finito del unfolding, con la garanzia che questo rappresenti comunque tutte le

marcature raggiungibili e che da esso si possano trarre tutte le informazioni di

un’analisi tradizionale.

Definizione 3.1.1 (Configurazione locale). Data N

0 una rete di occorrenze

eti-chettata e t

0 ∈ T

0 _{, la configurazione locale di t}

0 _{, denotata con dt}

0 _{e, è la più piccola}

chiusura all’indietro di T

0 , rispetto a F

0 contenente t

0 .

Definizione 3.1.2 (Postset di una configurazione). Sia S una configurazione di

una rete di occorrenze N

0 . Il postset S• è l’insieme di tutte le piazze p ∈ P

0 tale

che:

• ∀t ∈ S, p /

∈ •t,

• ∀t ∈ T

0 _{− S, p /}

_{∈ t•.}

Lo stato finale di S, definito come F (S), è L

0 (S•)(il multi-insieme di etichette

che appaiono in S•).

F (S) rappresenta il marking di N raggiunto eseguendo le transizioni presenti

nella configurazione locale.

Una transizione è chiamata punto di cutoff (o cutoff) se esiste un’altra

tran-sizione la cui configurazione locale è più piccola, ma che conduce allo stesso

marking.

(33)

3.2. BCS UNFOLDING

32 Definizione 3.1.3 (Cutoff). Sia N

0 unfolding di una rete di Petri N . La

tran-sizione t

0 ∈ T

0 è un punto di cutoff di N

0 esattamente quando esiste t

00 ∈ T

0 tale

che:

• F dt

0 _{e = F dt}

00 _{e, e}

• |dt

00 _{e| < |dt}

0 _e|

dove con |dt

0 e| e |dt

00 _{e| si intende la cardinalità delle configurazioni locali di t}

0 _e

t

00 .

La chiave per ottenere un unfolding troncato, secondo McMillan, è

identifi-care i punti di cutoff in cui la costruzione si deve fermare.

Definizione 3.1.4 (Unfolding troncato). Il troncamento di N

0 è la più grande

sottorete chiusa all’indietro di N

0 che non contiene cutoff.

Il prefisso finito così costruito consente di rappresentare tutte le marcature

dell’insieme di raggiungibilità della rete originale, ma si applica solo al caso delle

reti bounded.

3.2 BCS Unfolding

Daniele Cicciarella et al [15] hanno proposto un principio di troncamento

leg-germente diverso da quello di McMillan, in quanto quest’ultimo non permette di

studiare la proprietà di soundness in maniera esatta.

Definizione 3.2.1 (BCS cutoff). Sia N

0 un unfolding di una rete di Petri N .

Una transizione t

0 ∈ T

0 è un BCS cutoff di N

0 esattamente quando esiste t

00 ∈ T

0 tale che

• F dt

0 _{e ⊆ F dt}

00 _{e, e}

(34)

3.2. BCS UNFOLDING

33 Per la Definizione 3.1.3 una transizione t

0 è un punto di cutoff se esiste un’altra

transizione t

00 con una configurazione locale più piccola che porta allo stesso

marking. Per la Definizione 3.2.1 invece il troncamento avviene quando viene

trovata una transizione t

00 , antecedente di t

0 , con una configurazione locale più

piccola.

La prima condizione permette una rappresentazione finita anche di reti

un-bounded: se un cutoff porta ad una marcatura più grande di una atraversata

in una sottoconfigurazione precedente, allora le piazze che contengono i token

in eccesso saranno unbounded. La seconda permette di interrompere l’unfolding

quando questo condurrebbe a riproporre una situazione già analizzata.

Definizione 3.2.2 (BCS unfolding). Il BCS unfolding di N è la più grande rete

di occorrenze chiusa all’indietro di N che non contiene BCS cutoff.

Da questi derivano i seguenti teoremi, che permettono di effettuare un analisi

esatta della soundness di una rete di Petri. Per la loro dimostrazione si rimanda

alla Tesi di Cicciarella [15] .

Teorema 3.2.1. BCS unfolding è sempre finito.

Teorema 3.2.2. Sia N una rete bounded e N

0 il BCS unfolding di N . M è

una marcatura raggiungibile di N se e solo se M è lo stato finale di alcune

configurazioni finite di N .

Teorema 3.2.3. Se la rete è bounded, t è una transizione dead se e solo se t

non compare nel BCS unfolding e t non è un BCS cutoff.

Teorema 3.2.4. La rete può essere deadlock se e solo se c’è una configurazione

locale in conflitto con ogni BCS cutoff.

BCS Unfolding offre prestazioni superiori per l’analisi rispetto a WoPed e

Woflan plugin e permette di trattare processi non analizzabili con altri tool.

Inoltre BCS Unfolding dà la possibilità di eseguire un analisi di weak soundness,

non disponibile con altri strumenti.

(35)

3.3. ESEMPIO DI UNFOLDING

34

3.3 Esempio di Unfolding

L’unfolding nella Figura 3.2 è stato ottenuto applicando la procedura di BCS

Unfolding alla rete di Petri - Gestione Esame Semplificato (Figura 2.15). Ogni

transizione colorata in rosso rappresenta una scelta che porta necessariamente a

un deadlock, mentre le transizioni di colore azzurro sono punti di cutoff.

Figura 3.2: Unfolding - Gestione Esame Semplificato

La Tabella 3.1 mostra alcuni passi dell’algoritmo BCS Unfolding. Ad ogni

passo dell’algoritmo sono mostrati: la transizione abilitata, la sua configurazione

locale, il marking e se è un punto di cutoff.

La transizione xorMerge è un BCS Cutoff. La transizione merge1,

antece-dente di xorMerge, ha una configurazione locale più piccola della configurazione

locale di xorMerge, entrambe hanno lo stesso marking, quindi per la Definizione

3.2.1 xorMerge è un punto di BCS Cutoff. Quindi la rete dal punto di BCS

Cutoff, dopo xorMerge, non viene estesa.

transizione

configurazione locale

marking

cutoff

ti

p2, p3

-start2

start2, ti

p5, p2

-start1

start1, ti

p4, p3

-invEsame

invEsame, start1, ti

p7, p6, p3

-merge1

merge1, invEsame, start1, ti

p8, p6, p3

-ricEsame

ricEsame, invEsame, start1, ti, start2

p9, p7

-esecEsame

esecEsame, ricEsame, invEsame, start1, ti,

start2

p12, p7

-consElab

consElab, esecEsame, ricEsame, invEsame,

start1, ti, start2

p13, p14, p7

-ricElabSplit

ricElabSplit, merge1, invEsame, start1, ti

p11, p6, p3

-split

split, merge1, invEsame, start1, ti

p10, p6, p3

-merge2

merge2, split, merge1, invEsame, start1, ti

p18, p6, p3

-xorsplit2

xorsplit2, merge2, split, merge1, invEsame,

start1, ti

p24, p6, p3

-xorsplit

xorsplit, merge2, split, merge1, invEsame,

start1, ti

(36)

-3.3. ESEMPIO DI UNFOLDING

35 endSplit

endSplit, xorsplit, merge2, split, merge1,

invEsame, start1, ti

p22, p6, p3

-xorMerge

xorMerge, xorsplit2, merge2, split, merge1,

invEsame, start1, ti

p8, p6, p3

cutoff

ricElab

ricElab,

ricElabSplit,

merge1,

invEsame,

start1, ti, consElab, esecEsame, ricEsame,

start2

p15, p14

(37)

Capitolo 4

Contributo originale

Allo stato attuale l’algoritmo, BCS Unfolding [15], lavora in maniera sequenziale

non sfruttando quindi le possibilità offerte dalle moderne CPU multicore in

ter-mini di prestazioni. Per questo motivo è stato effettuato un refactoring di BCS

Unfolding ed è stata proposta una sua nuova versione con l’uso dei thread.

4.1 Unfolding Parallelo

La rete di unfolding descrive in termini strutturali, le possibili evoluzioni della

rete di Petri di partenza esplicitando tutti i possibili scatti di transizioni e le

relazioni fra loro.

Lo scatto di una transizione è un fenomeno locale della rete, l’abilitazione di

una transizione dipende solo dalla marcatura del suo preset e lo scatto influenza

solo il suo postset. In un momento durante l’evoluzione della rete di Petri ci

possono essere abilitate più transizioni, tali transizioni possono essere

aggiun-te conaggiun-temporanemenaggiun-te alla reaggiun-te di unfolding. I loro scatti non hanno nessuna

relazione tra di loro.

Nella Figura 4.1 è mostrata una rete di Petri durante la sua evoluzione. In

particolare la transizione t3 e t4 sono abilitate nello stesso momento e quindi

possono scattare contemporanemente.

(38)

4.2. STRUTTURE DATI

37 Queste caratteristiche viengono sfruttate dall’algoritmo di Unfolding

paral-lelo.

Figura 4.1: Transizioni Abilitate

Nell’algoritmo di unfolding parallelo ad ogni piazza della rete di Petri è

asso-ciato un thread, che rappresenta lo scatto di una transizione della rete di Petri.

Quando una piazza è inserita nella rete di unfolding il thread associato ad essa

aggiunge alla rete di unfolding le transizioni abilitate del suo postset. Le

tran-sizioni abilitate sono quelle il cui preset è tutto presente nella rete di unfolding.

Per ciascuna transizione inserita, se non è un BCS Cutoff, il thread aggiunge alla

rete di unfolding anche le piazze del suo postset, risvegliando i thread associati

ad esse. Ogni thread coinvolge nella costruzione della rete di unfolding solo le

transizione del postset della piazza a cui è associato ed, eventualmente, i postset

di queste.

4.2 Strutture Dati

L’algoritmo di BCS Unfolding parallelo per trasformare una rete di Petri N =

(P, T, F ) in BCS unfolding N

0 = (P

0 , T

0 , F

0 ) usa le strutture dati di appoggio

M , BC e le variabili index e numThread.

• BC è un insieme costituito dai BCS Cutoff.

• M mappa l’insieme P su un insieme P

∗

_{, dove P}

∗

_{è un insieme dei nodi di}

(39)

4.3. ALGORITMO BCS UNFOLDING PARALLELO

38 • La variabile index è una variabile statica condivisa da tutti i thread che

indica il numero totale di piazze presenti in M meno uno. Tale variabile

permette ad un thread di associare un valore progressivo alla piazza che

esso inserisce nella rete di unfolding.

• La variabile numThread è un’altra variabile statica condivisa da tutti i

thread. numThread rappresenta il numero di thread in esecuzione. Tale

variabile è incrementata da un thread quando questo mette in esecuzione

un altro thread ed è decrementata quando un thread termina.

Per la lettura e la modifica delle variabili index e numThread sono stati creati

i metodi sincronizzati descritti nella Sezione 4.4. La struttura dati M, nel

Dia-gramma delle classi 4.4, ha il suo correspettivo in IndexNodeMap. Per avere un

corretto accesso in scrittura e in lettura da parte di più thread è stata usata una

ConcurrentHashMap.

4.3 Algoritmo BCS Unfolding parallelo

Lo pseudocodice dell’algoritmo BCS Unfolding parallelo è presente nel Listing

4.1. L’algoritmo parallelo parte con l’inserimento di un’istanza della piazza

ini-ziale p_init della rete di Petri nella rete di unfolding (unfolding). Assegna alla

piazza inserita (p_init’ ) un indice (index ) pari a zero, creando in questo modo

un p_index_init. L’index rappresenta il numero dei place inseriti nel

Unfol-ding al passo i-esimo meno uno ed è una variabile statica condivisa da tutti i

thread. A questo punto inserisce nella hashMap M la chiave p_init con il valore

p_index_init e mette in esecuzione un thread con il task threadTask(p_i, p)

passandogli come input p_index_init e p_init. Il thread creato aggiunge alla

rete di unfolding le transizioni abilitate del postset di p e, se queste transizioni

non sono un BCS Cutoff, aggiunge alla rete anche le piazze del loro postset.

(40)

4.3. ALGORITMO BCS UNFOLDING PARALLELO

39 c r e a t e p _ i n i t ’ from p _ i n i t ;

add p _ i n i t ’ t o u n f o l d i n g ;

s t a t i c i n d e x =0;

p _ i n d e x _ i n i t=a s s i g n i n d e x t o p _ i n i t ’ ;

M. put ( p _ i n i t , p _ i n d e x _ i n i t ) ;

s t a t i c numThread=1;

t h r e a d T a s k ( p_index_init , p _ i n i t ) ;

w h i l e ( numThread >1){}

t h r e a d T a s k ( p_i , p ) {

f o r t p o s t s e t o f p {

|

i f

i s E n a b l e d ( p_i , t ) {

|

c r e a t e t ’ from t ;

|

add t ’ t o u n f o l d i n g ;

|

i f

! BCSCutoff ( t ’ ) {

|

f o r p ’

p o s t s e t o f t {

|

c r e a t e p ’ ’ from p ’ ;

|

add p ’ ’ t o u n f o l d i n g ;

|

i n d e x=i n d e x +1;

|

p_index ’ ’ = a s s i g n i n d e x t o p ’ ’ ;

|

M. put ( p ’ , p_index ’ ’ ) ;

|

numThread=numThread+1;

|

t h r e a d T a s k ( p_index ’ ’ , p ’ ) ;

|

}

|

} e l s e {

|

BC. add ( t ’ ) ;

|

}

|

}

numThread=numThread −1;

}

Listing 4.1: Algoritmo Parallelo

Quando il thread inserisce una nuova piazza (p”) nella rete di unfolding,

esegue una put in M con la chiave p’ e il valore p_index”, dove p’ è il corrispettivo

di p” nella rete di Petri originale e p_index” è un indice progressivo, e mette

anche in esecuzione un nuovo thread con lo stesso task, passandogli come input

p_index” e p’.

(41)

4.3. ALGORITMO BCS UNFOLDING PARALLELO

40 ogni nodo del preset di t contiene almeno un nodo della rete di unfolding con un

indice minore di p_i.

L’algoritmo termina quando non vengono più inserite piazze nella rete di

unfolding, tale condizione viene raggiunta quando non vengono più generati

thread.

Ogni thread è responsabile della creazione di altri thread, ciascuno per ogni

piazza del postset della transizione abilitata se questa non è un BCS Cutoff.

Quindi un thread non crea un altro thread per una transizione se questa è un

BCS Cutoff, se non ha un postset oppure se non è abilitata. Per il Teorema

3.2.1, una rete di BCS unfolding ha un numero di piazze e di transizioni finito,

quindi il numero totale dei thread creato è finito.

(42)

4.4. IMPLEMENTAZIONE

41

4.4 Implementazione

In questa sezione sarà descritto il software utilizzato per l’implementazione

del-l’algoritmo di unfolding parallelo e verranno illustrate le classi che compongono

il progetto.

ProM

L’algoritmo di unfolding parallelo è stato implementato come un plugin di ProM.

ProM è un framework estensibile che supporta una vasta gamma di tecniche di

mining di processo sotto forma di plugin. È indipendente dalla piattaforma in

quanto è implementato in Java. Il software viene distribuito come pacchetto

scaricabile utilizzando la licenza open source GNU Public License (GPL). Ciò

significa che è possibile scaricare e installare ProM senza restrizioni.

Nella Figura 4.2 è visibile l’interfaccia grafica iniziale di ProM. Da questa è

possibile importare un file con una descrizione di processo, come ad esempio un

diagramma BPMN. Nell’interfaccia della Figura 4.3, invece è possibile scegliere

il tipo di analisi da effettuare sul processo, i risultati di questa analisi saranno

poi visualizzati in una tab del framework ProM mostrata nella Figura 4.4.

(43)

4.4. IMPLEMENTAZIONE

42 Figura 4.2: ProM - Interfaccia Import

(44)

4.4. IMPLEMENTAZIONE

43 Figura 4.4: ProM - Interfaccia Visualizzazione

Diagramma delle Classi

Le classi che sono state realizzate nel progetto sono visibile nel diagramma delle

classi della Figura 4.5. In verde è evidenziata la classe principale che contiene

l’implementazione dell’algoritmo parallelo.

BCSUnfolding

BCSUnfolding è la classe che contiene l’implementazione dell’algoritmo unfolding

parallelo. Le strutture dati utilizzate per l’implementazione sono:

• petri2UnfMap contiene per ogni nodo della rete di Petri uno o più nodi

della rete di unfolding;

• unf2PetriMap associa ad ogni nodo di Unfolding un nodo della rete

origi-nale;

• markingMap mappa ogni transizione della rete di unfolding con il rispettivo

marking;

(45)

4.4. IMPLEMENTAZIONE

44 Figura 4.5: Diagramma Classi

• localConfigurationMap mette insieme le transizione della rete con le

confi-gurazioni locali;

• statisticMap colleziona tutte le statistiche dell’analisi;

• indexNodeMap ha al suo interno le associazioni tra i nodi della rete originale

e gli indexNode.

(46)

4.4. IMPLEMENTAZIONE

45 Il metodo createRunnable contiene il codice che deve essere eseguito da ciascun

thread e dove sono utilizzate la maggior parte delle strutture dati sopra

descrit-te. I metodi che servono per la gestione dei thread sono incrementNumThread,

decrementNumThread e getNumThread. Tali metodi sono stati sincronizzati per

permettere il corretto accesso in lettura e in scrittura alla variabile statica

num-ThreadCreated, condivisa da tutti i thread. numThreadCreated rappresenta il

numero di thread in esecuzione creati dall’algoritmo. Quando la variabile è pari

a zero l’algoritmo termina.

Utility

La classe Utility contiene diversi metodi di utilità generica e di supporto alla

conversione delle rete di Petri in reti di unfolding. Ad esempio: i metodi getPreset

e getPostset restituiscono rispettivamente il preset e il postset di un nodo; il

metodo getMarking ritorna il marking di una configurazione locale.

LocalConfiguration

Questa classe contiene le strutture dati e i metodi che servono a rappresentare e

gestire una configurazione locale di un nodo.

LocalConfigurationMap

La HashMap di LocalConfigurationMap associa ad ogni transizione della rete la

sua configurazione locale.

IndexNode

IndexNode è la classe creata per rappresentare un place della rete di unfolding

a cui è assegnato un intero, cioè l’indice di inserimento dello stesso place nella

rete di unfolding.

(47)

4.4. IMPLEMENTAZIONE

46 IndexNodeMap

Le strutture dati di IndexNodeMap sono: una HashMap, che associa ad ogni nodo

della rete originale i rispettivi indexNode, ed un intero, maxIndex, che indica

quanti indexNode sono presenti in totale nella hashMap, quindi quanti nodi

sono stati inseriti finora nel unfolding. Questa variabile permette di associare al

place inserito nel unfolding un indice in modo progressivo.

Il metodo getArrayPetrinetNodeMinPi, dati un place p e un indexNode p_i,

restituisce tutti gli indexNode associati a p che hanno un indice minore di p_i.

Tale metodo viene usato dal algoritmo per capire se una transizione è abilitata

oppure no.

Combination

La classe Combination è usata per rappresentare tutte le possibili combinazioni

di nodi che compongono il preset di una transizione.

StatisticMap

StatisticMap rappresenta tutte le statistiche di BCS Unfolding.

Il codice realizzato estende i due plugin esistenti di ProM, già implementati

con passate tesi. Il primo trasforma un diagramma in notazione BPMN in una

rete di Petri. Il secondo proietta punti di cutoff e di deadlock trovati dal unfolding

sui nodi del diagramma BPMN di partenza e visualizza le statistiche.

(48)

Capitolo 5

Esempi Pratici

Di seguito sarà mostrato il funzionamento del plugin completo con il framework

ProM su alcuni diagrammi BPMN.

5.1 Esempio A

Nella Figura 5.1 è rappresentato il primo diagramma BPMN che si vuole

analiz-zare per mostrare il funzionamento di plugin di ProM.

Figura 5.1: Diagramma BPMN A

Una volta caricato il file .bpmn, per la selezione in BPMNDiagram deve essere

scelto il plugin denominato Select BPMN Diagram (Figura 5.2).

Si apre subito l’interfaccia, che visualizza il diagramma caricato, visibile nella

Figura 5.3.

(49)

5.1. ESEMPIO A

48 Figura 5.2: Prom - Select BPMN Diagram

Figura 5.3: Prom - BPMN Diagramma A

Dopo aver selezionato il diagramma BPMN è possibile visualizzare la sua

rete di Petri selezionando il plugin BCS BPMN to Petri net, come mostrato

nella Figura 5.4. La rete di Petri creata dal plugin del diagramma BPMN A è

visibile nella figura 5.5.

Scegliendo, invece, come si vede nella Figura 5.6, il plugin BCS BPMN to

Unfolding net è possibile vedere nella stessa interfaccia di ProM il modello BPMN

selezionato e la sua rete di unfolding (la Figura 5.7). Sul diagramma BPMN e

sulla rete di unfolding sono evidenziati eventuali problemi, come ad esempio i

deadlock e i cutoff.

(50)

5.1. ESEMPIO A

49 Figura 5.4: ProM - BCS BPMN to Petri net

Figura 5.5: ProM - Rete di Petri A

Figura 5.6: Prom - BCS BPMN to Unfolding net

La rete A, come si vede dalla Figura 5.7, non contiene punti di cutoff, ma

contiene le transizioni dead. Le transizioni dead sono proiettate sui nodi del

(51)

5.2. ESEMPIO B

50 diagramma BPMN originale e sono quelli di colore giallo. La rete non è sound,

ma è weak sound.

Figura 5.7: ProM - Unfolding Rete A

5.2 Esempio B

Di seguito è mostrata l’analisi effettuata con il plugin di ProM sul diagramma

della figura 5.8.

(52)

5.2. ESEMPIO B

51 Figura 5.9: ProM - Rete di Petri B

Figura 5.10: ProM - Unfolding Rete B

La rete B contiene sia i punti di cutoff, che rendono la rete unbounded, sia le

transizioni che conducano a deadlock. Nella Figura 5.10 è presente la schermata

di ProM che mostra il diagramma B in BPMN con la rispettiva rete di unfolding.

I nodi colorati in verde fanno parte di un percorso dallo Start Event fino ad uno

dei nodi che conducono ad un deadlock.

(53)

5.3. ESEMPIO RETE GIOCATORI

52

5.3 Esempio Rete Giocatori

Il diagramma BPMN dellla Figura 5.11 è stato creato da un studente del corso

di "Modellazione dei processi aziendali" dell’Università di Pisa, tenuto da Prof.

Roberto Bruni e modella un gioco con un conduttore e due giocatori. Il file di

riferimento per tale rete è Rete_A.bpmn. La rete di Petri generata da questo

diagramma e visibile nella Figura 5.12 è stata analizzata anche con il tool Woflan.

Il tool Woflan non è riuscito a generare un risultato in tempi ragionevoli. Mentre,

come si vede nella Figura 5.13, l’algoritmo BCS Unfolding parallelo ha costruito

la rete di unfolding relativa al diagramma BPMN Gioco ed è stato possibile

analizzare la rete.

Sono state trovate le transizioni dead, la rete non è sound, ma è weak sound.

(54)

5.4. ESEMPIO RETE NEGOZIO

53 Figura 5.12: ProM - Rete di Petri Gioco

Figura 5.13: ProM - Unfolding Rete Gioco

5.4 Esempio Rete Negozio

Un’altro diagramma BPMN, la cui rete di Petri nella Figura 5.15 non è trattabile

dal tool Woflan, è visualizzato nella Figura 5.14. Questo diagramma BPMN,

come quello dell’esempio precedente, è stato disegnato da uno studente del corso