CA e Connector Coloring

Dalla creazione di Reo ad oggi, sono stati sviluppati diversi modelli formali volti a catturarne la semantica, ad esempio [5], [12] e [43], ciascuno concepito per un preciso scopo. Nel corso della presente sezione presenteremo due dei modelli semantici principali che definiscono la semantica del linguaggio di

coordinamento Reo: la Connector Coloring (colorazione di connettori) [33] ed i Constraint Automata (includendo alcune varianti) [16].

Entrambi i modelli che descriveremo riescono a catturare correttamente la semantica del linguaggio, concentrandosi sugli aspetti specifici per cui sono stati concepiti.

Connector Coloring

Il modello semantico basato su colorazione di connettori, `e stato presentato per la prima volta nel 2006 [33]. La creazione di questo modello `e stata ispi- rata dall’idea di creare uno schema che permettesse di illustrare in maniera relativamente semplice le alternative di instradamento di un flusso all’interno di un connettore Reo.

Effettivamente, se si astrae dalla direzione del flusso (che `e comunque deduci- bile dai vincoli imposti da ciascun canale) e dalle trasformazioni che vengono realizzate sui dati che circolano all’interno del connettore, allora la semanti- ca di un circuito Reo pu`o essere modellata attraverso le possibili alternative di instradamento del flusso di dati. Dunque la colorazione di connettori si presenta come un adeguato meccanismo per specificare in quali parti di un connettore esista flusso in un certo istante.

La colorazione viene definita a partire dagli elementi base del linguaggio: i canali. La semantica di un connettore verr`a ottenuta attraverso un ap- proccio composizionale, dunque in base alla semantica degli elementi che lo costituiscono. In Figura 4.19 viene illustrato il connettore router esclusivo, che abbiamo gi`a introdotto in precedenza, composto da tre diverse tipologie di canali: Sync, LossySync e SyncDrain.

Fig. 4.19: Connettore Reo per instradamento esclusivo

Ricordiamo che il router esclusivo implementa uno XOR sul flusso in entrata, dunque instrada il flusso ricevuto dal nodo di input A esclusivamente ad uno dei due nodi di output F e G. In caso di conflitto, i canali Sync in entrata al nodo E ed il canale SyncDrain garantiscono che il flusso verr`a indirizzato ad esattamente uno dei nodi C o D, e di conseguenza potr`a confluire solo su uno dei due nodi di output.

Il concetto di colorazione di connettori `e descritto in maniera estremamente intuitiva se associato ad un’opportuna rappresentazione visuale. Ad esempio, un modo informale per esprimere il possibile instradamento del flusso `e rap- presentare graficamente la colorazione delle parti in cui il flusso pu`o scorrere (cio`e quelle parti che soddisfano i vincoli imposti dai canali). In Figura 4.20

si illustra la “Tavola delle Colorazioni” di un connettore XOR, ovvero l’insie- me delle sue possibili colorazioni: le porzioni marcate con una linea spessa indicano le parti in cui il flusso pu`o scorrere, mentre le porzioni che non ven- gono marcate sono quelle in cui non pu`o esserci passaggio di flusso. Come abbiamo gi`a commentato, il flusso di dati pu`o essere instradato in maniera esclusiva verso F (caso “a” della Figura 4.20) o verso G (caso “b”), in base alla disponibilit`a di ciascuno dei due nodi a ricevere il flusso. In realt`a la tavola per il connettore XOR comprende tre diverse colorazioni, una delle quali non `

e rappresentata in figura. La colorazione mancante `e quella in cui l’intero connettore non viene marcato dalla linea solida, che modella il caso in cui i nodi di input/output non siano disposti ad inviare o accettare il flusso, che di conseguenza non potr`a essere instradato in alcun canale del connettore. Il modello si basa sull’utilizzo di colori diversi per esprimere la presenza o l’assenza di flusso, dunque ciascuna colorazione completa di un connettore rappresenta una possibile soluzione ai vincoli di sincronizzazione imposti dai canali e dai nodi.

La semantica basata su colorazione viene impiegata per la creazione di ani- mazioni di connettori Reo, implementata in uno strumento integrato nella toolbox ECT, che descriveremo nella sezione 4.2.2.2.

Constraint Automata

Un Constraint Automaton (automa con vincoli) [16] `e un particolare automa a stati finiti in cui le transizioni rappresentano un insieme di operazioni di input/output realizzate su un insieme di porte. La modalit`a con cui i dati fluiscono tra le porte viene specificata attraverso delle condizioni guardia e lo

scorrimento del flusso `e regolato dalle transizioni dell’automa, che vengono innescate nel momento in cui le porte coinvolte diventano “attive”, ovvero sono pronte ad eseguire operazioni di input/output. Se i dati presenti in una determinata porta non innescano alcuna transizione, allora i dati in questione vengono rifiutati.

I Constraint Automata (CA), costituiscono un formalismo per la cattura del comportamento e dell’instradamento del flusso di dati all’interno di un mo- dello di coordinamento tra componenti blackbox. [16] propone un modello

Fig. 4.21: Constraint Automata di alcuni canali Reo

operazionale per catturare la semantica del linguaggio Reo attraverso un ap- proccio composizionale: vengono definiti i CA relativi agli elementi primitivi del linguaggio e degli operatori per CA che implementano le operazioni di join e hide (a cui abbiamo accennato nella sezione 4.2.1). In questo modo, utilizzando l’approccio composizionale usato per la creazione di connettori attraverso gli elementi primitivi e le operazioni di base, `e possibile creare i CA equivalenti con strumenti formali analoghi.

Fig. 4.22: Connettore Reo per la successione di Fibonacci

La teoria dei CA costituisce una base per verifiche formali di modelli di coor- dinamento di componenti. In effetti la trasformazione di connettori Reo in CA viene utilizzata per verifiche quali model checking via LTL o equivalence checking, implementate in tool che discuteremo nella sezione 4.2.2.2.

La semantica operazionale di Reo pu`o quindi essere definita per mezzo di CA con le seguenti caratteristiche: gli stati dell’automa modellano le possi- bili configurazioni (ad esempio il contenuto dei buffer), mentre le transizioni rappresentano il cambiamento del flusso di dati (da un certo istante a quello successivo) e i suoi effetti sulla configurazione attuale. In Figura 4.21 vengono

Fig. 4.23: CA per la successione di Fibonacci

presentati gli automi corrispondenti ad alcuni dei canali elementari disponi- bili in Reo. Come abbiamo specificato in precedenza, una transizione di stato

viene innescata solo se i dati osservati sulle porte coinvolte soddisfano i vin- coli sui dati. In tal caso la transizione pu`o alterare lo stato dell’automa. Un esempio non banale, tratto da [16], mostra un connettore (si veda la Fi- gura 4.22) che implementa la Successione di Fibonacci ed il CA equivalente (si veda la Figura 4.23).

Quantitative Constraint Automata

I CA rappresentano un valido modello per esprimere la semantica dei connet- tori Reo, tuttavia non sono sufficientemente potenti da riuscire a rappresen- tare alcune caratteristiche tipiche dei sistemi reali. In particolare, attraverso l’utilizzo di un CA non `e possibile catturare informazioni relative alla qualit`a dei canali quali il livello di affidabilit`a, il ritardo di trasmissione dei dati, th- roughput, etc. Per riuscire ad ovviare a questo inconveniente, in [7] vengono presentati i Quantitative Constraint Automata (QCA), un’estensione dei CA creata per poter specificare e discutere questioni di tipo QoS di connettori Reo.

In un QCA, ciascun arco `e etichettato con una tripla (P, g, C) i cui elementi hanno il seguente significato:

• P `e l’insieme di porte su cui `e presente flusso nello stesso istante; • g `e la guardia che stabilisce la condizione sui dati presenti sulle porte; • C `e l’insieme dei costi, ovvero dei valori delle metriche QoS che si

vogliono studiare.

Dunque la principale differenza di notazione rispetto ai CA `e data dalla pre- senza dei valori che modellano le caratteristiche QoS interessanti. In Figura

Fig. 4.24: Connettore Reo di ordinamento (a) e relativo QCA (b) 4.24 possiamo osservare un connettore che impone un ordinamento sul flusso di dati (che viene inviato al nodo C) ed il relativo QCA. Nell’esempio le me- triche modellate sono: tempo minimo di trasmissione dei dati (t), costo della memoria allocata per la trasmissione dei dati (c) e probabilit`a di trasmissione corretta dei dati (p).

Notiamo che il canale FIFO utilizzato `e caratterizzato da due triple di valori QoS, una relativa all’operazione di memorizzazione dei dati nel buffer, l’altra relativa all’operazione di recupero dei dati dal buffer.

Quantitative Intentional Automata

L’adozione dei QCA permette di catturare aspetti non strettamente legati al coordinamento imposto da un connettore. Tali aspetti qualitativi, tuttavia, non sono l’unico fattore che pu`o influenzare la performance di un sistema, in- fatti essa pu`o dipendere da fattori di contesto che non riguardano la struttura interna del connettore o dei componenti. Dunque, sebbene i QCA forniscano un strumento ricco per la modellazione di servizi composti, non prendono in considerazione informazioni contestuali spesso molto rilevanti quali ad esem- pio la frequenza delle richieste di I/O. I cosiddetti Quantitative Intentional

Automata (QIA) [8] nascono come estensione dei CA e sono concepiti per riuscire a prendere in considerazione tanto i dettagli interni di un sistema quanto l’influenza esercitata dall’ambiente esterno.

Se nei CA le transizioni descrivevano cambiamenti di configurazioni del siste- ma, con i QIA alle transizioni vengono aggiunte informazioni sullo stato delle operazioni pendenti nel sistema. Lo stato delle operazioni pendenti viene mo- dificato in seguito all’arrivo di dati o richieste di dati, o alla sincronizzazione di nodi.

I QIA costituiscono un modello per catturare la semantica di una versione stocastica di Reo (Stochastic Reo), in cui i canali e le loro estremit`a so- no arricchiti con delle annotazioni relative a propriet`a stocastiche quali le frequenze di arrivo o di richiesta di dati alle estremit`a, o il ritardo di elabo- razione nei canali. I canali Reo (in versione stocastica) possono contenere annotazioni di due tipi:

• ritardi dei canali: i tempi necessari perch´e un canale inoltri o perda i dati;

• arrivi ai nodi: l’intervallo tra due richieste consecutive di lettura o scrittura alle estremit`a dei nodi dipende dai processi stocastici associati ai connettori.

In Figura 4.25 possiamo osservare alcuni canali primitivi di Stochastic Reo. Il modello semantico costituito dai QIA conserva le propriet`a composizionali che erano state introdotte con i CA, dunque anche il QIA associato ad un connettore `e ottenibile attraverso la composizione dei QIA associati ai canali che compongono il connettore.

Fig. 4.25: Canali principali Reo in versione stocastica

Come discuteremo nella sezione 4.2.2.2, i QIA rappresentano uno degli stru- menti impiegati per la realizzazione di simulazioni di connettori Reo, fina- lizzati all’analisi di specifiche propriet`a non funzionali, ad esempio di tipo Quality of Service.