Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
I corsi di Scienze Matematiche Fisiche e Naturali
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

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.

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.

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.

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).

Fig.4 Automa per la gestione di una risorsa.

Fig.4 Automa per la gestione di una risorsa.


  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion