Home

Federica EU

1/13

Adriano Peron » 7.FSM e Parallelismo – seconda parte

Parallelismo e comunicazione asincrona mediante canali

La forma di comunicazione tra le componenti parallele è uno-a-uno asincrona.
Il canale viene implementato da una coda di capacità limitata.
La limitatezza della capacità della coda è essenziale per garantire che il formalismo mantenga la finitezza dell’insieme degli stati.

Sia $\Psi = \{(Z_1,n_1), \ldots ,(Z_k,n_k)\}$ l’insieme delle code. Per ogni coda $(Z_i,n_i)$ ,

$Z_i$ indica l’alfabeto dei simboli che possono essere ospitati nella coda;
$n_i$ indica la capacità massima della coda.

Gli alfabeti delle code sono mutuamente disgiunti ( $Z_i\cap Z_j =\emptyset\mbox{ per ogni }i\neq j$ ).

Per ogni simbolo $a \in \bigcup_h Z_h$ è univoca la coda di riferimento..

Parallelismo e comunicazione asincrona mediante canali (segue)

Fissato un insieme $\Psi$ , un automa parallelo ha la forma $A_1 \| A_2 \| \ldots \| A_n \mbox{ con }$

$A_1=\langle\Sigma_i ,Q_1, q_{0,i}, \delta_i \rangle\mbox{, per } 0\leq i\leq n \mbox{ dove}$

$\Sigma_i = \bigcup_{h \in H} Z_h \cup \{\epsilon_i\} \cup \{[z] : z \in Z_h\} \mbox{ per qualche } H \subseteq \{1,..,z\}$ ;

$\delta_i \subseteq Q_i \times \Sigma_i \times \Sigma_i \times Q_i$ .

Canali:

Le comunicazioni sono con valore (si inseriscono e tolgono valori).

L’ $A_i$ vede l’ insieme di canali $H_i=\{h:Z_h\cap\Sigma_i\neq\emptyset\}$ .

$\epsilon_i$ viene usata per un check di coda vuota sull’iesima coda.

$[z]$ viene usata per un check di presenza del simbolo z in testa alla coda d’appartenenza.

Parallelismo e comunicazione asincrona mediante canali (segue)

Operazioni sui Canali (con side effect):

Le transizioni vengono decorate con una coppia di simboli (in, out):

Il simbolo in viene tolto dalla testa della coda $h \mbox$ tale che $in\inZ_h$ ;
se la coda h è vuota o in testa il simbolo è diverso da in la transizione non può scattare;
Il simbolo out viene inserito nella coda $h \mbox{ tale che } out \in Z_h$ ;
se la coda h è piena la transizione non può scattare;
$(\tau,\tau)$ indica una transizione interna;
$(in,\tau)$ indica operazione di sola estrazione senza inserimento (sola ricezione);
$(\tau, out)$ indica operazione di solo inserimento senza estrazione (sola trasmissione);
$(in, out)$ indica operazione di estrazione ed inserimento (ricezione-trasmissione); la ricezione avviene prima dell’invio.

Parallelismo e comunicazione asincrona mediante canali (segue)

Operazioni di controllo sui Canali (senza side effect):

$(\epsilon_i, \tau)$ indica operazione di check di coda vuota sulla coda i.
$([in],\tau)$ indica l’operazione di controllo della presenza del simbolo in sulla coda i.

In entrambi i casi, le operazioni con associate operazioni di controllo permettono all’automa di transire di stato senza alterare il contenuto dello stack.

Semantica

La semantica è data dall’LTS $\langle S,S_0,\Delta \rangle,\mbox{dove}$

$S = Q_1 \times \ldots \times Q_n \times Z^{\leq n_1}_1 , \times , \ldots , \times Z^{\leq n_k}_k$ .

Oltre allo stato delle singole componenti occorre tener traccia del contenuto delle code;

Il contenuto di una coda h è una stringa di simboli di lunghezza al più $n_h$ ;

$S_0=\{(q_{0,1},\ldots,q_{0,n},\epsilon\ldots\epsilon)\}$ ;

Le code nello stato iniziale sono vuote.

Semantica (segue)

$\Delta$ è l’unione dei seguenti insiemi di transizioni:

(Azione interna senza side effect sulle code)

$\{(q_1, \dots ,q_i, \ldots,q_n,\sigma_1, \ldots , \sigma_k),\tau,\tau,(q_1, \dots ,q'_i, \ldots ,q_n,\sigma_1, \ldots , \sigma_k) :$
$(q_i,\tau ,\tau, q'_i) \in \delta_i \mbox{ per } 1\leq i \leq n\}$ ;

(Transizione con sola ricezione)

$\{(q_1, \dots ,q_i, \ldots ,q_n,\sigma_1, \ldots ,a\cdot \sigma_j,\ldots, \sigma_k),a,\tau ,(q_1, \dots ,q'_i, \ldots ,q_n,\sigma_1, \ldots ,\sigma_j,\ldots, \sigma_k) :$
$a\in Z_j,(q_i,a,\tau,q'_i) \in \delta_i \mbox{ per } 1\leq i \leq n \}$ ;

(Transizione con sola trasmissione)

$\{(q_1, \dots ,q_i, \ldots,q_n,\sigma_1, \ldots ,\sigma_j,\ldots, \sigma_k),\tau,a ,(q_1, \dots ,q'_i, \ldots ,q_n,\sigma_1, \ldots ,\sigma_j\cdot a,\ldots, \sigma_k)$
$a\in Z_j, (q_i,\tau,a,q'_i) \in \delta_i \mbox{ per } 1\leq i \leq n \}$

Semantica (segue)

(Transizione con ricezione e trasmissione sulla stessa coda)

$\{(q_1,\dots ,q_i, \ldots,q_n,\sigma_1,\ldots ,a\cdot\sigma_j,\ldots,\sigma_k),a,b,(q_1,\dots ,q'_i,\ldots ,q_n,\sigma_1,\ldots ,\sigma_j\cdot b,\ldots,\sigma_k):$

$a,b\in Z_j,(q_i,a,b,q'_i)\in\delta_i\mbox{per}1\leq i\leq n\}$

(Transizione con ricezione e trasmissione su code diverse)

$\{(q_1,\dots ,q_i,\ldots, q_n,\sigma_1,\ldots,a\cdot\sigma_i,\ldots,\sigma_j,\ldots,\sigma_k),a,b,(q_1, \dots ,q'_i,\ldots ,q_n,\sigma_1,\ldots ,\sigma_i,\ldots,\sigma_j\cdot b,\ldots,\sigma_k):$

$a,b\in Z_j,(q_i,a,b,q'_i)\in\delta_i\mbox{per}1\leq i\leq n\}$

(si aggiunga anche uno schema con i ruoli invertiti di i (coda di trasmissione) e j (coda di ricezione).

Semantica (segue)

(Transizione con check di coda vuota; senza side effect)

$\{(q_1,\dots,q_i,\ldots,q_n,\sigma_1,\ldots,\sigma_j,\ldots,\sigma_k),\epsilon_j,\tau,(q_1,\dots ,q'_i, \ldots ,q_n,\sigma_1,\ldots,\sigma_j,\ldots,\sigma_k):$

$\sigma_j=\epsilon,(q_i,\epsilon_j,\tau,q'_i)\in\delta_i\mbox{per}1\leq i\leq n\}$

(Transizione con check di presenza di simbolo; senza side effect)

$\{(q_1,\dots ,q_i,\ldots,q_n,\sigma_1,\ldots ,a\cdot\sigma_j,\ldots,\sigma_k),\epsilon_j,\tau,(q_1,\dots ,q'_i,\ldots ,q_n,\sigma_1,\ldots ,a\cdot\sigma_j,\ldots,\sigma_k) :$

$a \in Z_j,(q_i,[a],\tau,q'_i)\in\delta_i\mbox{per}1\leq i\leq n\}$

Esempio di specifica

Accesso ad una risorsa codivisa con politica di locking (ad esempio: accesso delle transazioni alle tabelle di un database)

Le richieste sono r_lock (lettura), w_lock (scrittura), unlock (rilascio).
La politica è descritta nella tabella in figura.
Una coda di priorità memorizza le richieste di accesso.
La richiesta non è memorizzata se il numero di richieste pendenti eccede la capacità della coda.
Richieste multiple di lettura possono essere servite.
Letture e scritture sono in mutua esclusione.
Quando una transazione rilascia una risorsa bloccata in lettura, la risorsa è disponibile solo se non è ancora bloccata da altre transazioni.

Fig.1 Politica di locking.

Specifica

Automi

Un automa sequenziale per ogni transazione.
Un automa sequenziale per ogni risorsa.

Canali utilizzati per ciascuna risorsa

Un canale per le richieste r-lock e w-lock con alfabeto $Z_1=T \times \{r,w\}$ dove T è un insieme di nomi di transazioni e $n_1$ pari al numero massimo di transazioni in attesa; (canale comune a tutte le transazioni).
Un canale per la comunicazione degli ack alle transazioni con alfabeto $Z_2= T\times\{ack\}$ e $n_2$ pari al numero massimo di richieste di lettura simultanea permesse; (canale comune a tutte le transazioni).
Un canale per le richieste unlock $Z_3= T \times \{u\}$ e $n_3$ pari a $n_2$ ; (canale comune a tutte le transazioni).
Un canale di servizio per tener traccia del numero di r-lock attivi correntemente con alfabeto $Z_4=\{c\}$ e $n_4$ pari a $n_2$ .

Esempio di specifica

Automa per il gestore della risorsa per due transazioni t e t’.

F stato free, R stato R_locked, W stato W_locked.

Il numero di stati è costante.
Il numero delle transazioni è lineare rispetto al numero delle transazioni.

Problemi della specifica
a) Un numero di richieste di lettura superiore alla capacita della coda $Z_4$ può portare a malfunzionamenti (viene inviato l’ack ma non è possibile inserire il simbolo di conteggio in coda).
b) Non viene verificato che la transazione che rilascia la risorsa sia la transazione affidataria.

Fig.2 Automa per la gestione di una risorsa.

Esempio di specifica (segue)

Modifica della specifica di Fig.2 per tener conto del problema a):
Un numero di richieste di lettura superiore alla capacita della coda $Z_4$ può portare a malfunzionamenti (viene inviato l’ack ma non è possibile inserire il simbolo di conteggio in coda).

La nuova versione della specifica prima aggiorna la coda di conteggio e poi fornisce l’ack (si usa il check senza side effect sulla coda delle richieste).

Se non è possibile effettuare l’inserimento nella coda di conteggio si ritorna allo stato di ricezione mediante una azione interna.

Fig.3 Automa per la gestione di una risorsa.

Esempio di specifica (segue)

Modifica della specifica di Fig.2 per tener conto del problema b):

Non viene verificato che la transazione che rilascia la risorsa sia la transazione affidataria.

Per la gestione dei lock in lettura occorre codificare nello stato il sottoinsieme delle transazioni a cui è assegnata la risorsa.

Il numero degli stati e delle transizioni è esponenziale nel numero delle transazioni (serve codificare l’insieme delle parti dell’insieme delle transazioni).