L’interazione fra processi

Vi sono due motivi per cui due o più processi possono interagire: comunicare dati o sincronizzarsi. Spesso le due attività si sovrappongono all’interno di un’unica interazione. I meccanismi che Linda mette a disposizione per

"descrivere" l’interazione fra processi sono estremamente flessibili. Gli esempi che seguono intendono dimostrare questa affermazione rivelando come in Linda sia possibile implementare con facilità schemi di comunicazione e sincronizzazione caratteristici di altri modelli di

programmazione parallela. Gli stessi esempi faranno emergere, oltre alla versatilità di Linda, anche ulteriori proprietà caratterizzanti.

3.4.2.1 La comunicazione

Come punto di partenza per introdurre le tecniche di comunicazione in Linda consideriamo il meccanismo di comunicazione più intuitivo e conosciuto: lo

scambio di messaggi. In questo schema i processi comunicano inviando l’un l’altro dei messaggi. Gli strumenti a disposizione dei processi sono due

operazioni primitive: send (invia messaggio) e receive (ricevi messaggio). Normalmente l’identità del partner della comunicazione è contenuta esplicitamente in uno degli argomenti di queste primitive

(comunicazione con nomi di modulo): come

riferimento per la discussione sarà considerata questa tecnica. Se un processo mittente S ha un messaggio m per un destinatario R, allora S usa un comando del tipo send(R, m) ed R invoca receive(S, x), dove x è una variabile del tipo opportuno.

Lo scambio dei messaggi può essere di vario tipo in quanto la comunicazione gode di proprietà che possono essere istanziate in modi diversi (ad

esempio sincronia e simmetria). Analizziamo qualche esempio notevole che rivela come Linda consenta di descrivere in modo naturale tali forme di

comunicazione. Esempio 3.10

Siano le seguenti dichiarazioni:

typedef char nome_modulo[]; typedef messaggio ...;

nome_modulo mittente;

Comunicazione simmetrica e sincrona

In questa forma di comunicazione sono coinvolti due soli processi i quali si nominano reciprocamente e devono sincronizzarsi fino al completamento della comunicazione.

Si definisca una tupla-messaggio della forma:

(nome_mittente, nome_destinatario, messaggio)

Utilizzando i costrutti concorrenti di Linda questa forma di comunicazione sarà così implementata: S ::

...

m = ...;

out("S","R",m);

in("R","S","ricevuto");

/* S si sincronizza con R in attesa che questo riceva il messaggio m */

... R :: ... in("S","R",?x); out("R","S","ricevuto"); ...

Comunicazione simmetrica con rendez-vous esteso In questo caso la comunicazione è ancora sincrona, ma il messaggio di risposta del destinatario non è finalizzato soltanto alla sincronizzazione, ma contiene anche un’informazione di ritorno per il mittente. In Linda: S :: ... m = ...; out("S","R",m); in("R","S",?risultato);

/* in una situazione più generale S potrebbe ricevere il risultato anche non immediatamente dopo la sua

richiesta */ ... R :: ... in("S","R",?m); risultato=f(m,...); out("R","S",risultato); ... Comunicazione asincrona

In questa forma di comunicazione il processo mittente, una volta inviato il messaggio, non si sospende in attesa che esso sia ricevuto. Per realizzare questo schema si ha bisogno di una

qualche memoria che contenga il messaggio

non ancora ricevuto dal destinatario: in Linda questa memoria è messa a disposizione dallo spazio delle tuple.

Nel caso di comunicazione simmetrica ed asincrona avremo:

S ::

...

m1= ...;

out("S","R",m1);

/* S non si sincronizza con la ricezione da parte di R dei suoi messaggi */ ... m2 = ...; out("S","R",m2); ... R :: ... in("S","R",?x); ... in("S","R",?x); ...

Si osservi come il mittente S sia libero di inviare messaggi ad R anche se da quest’ultimo non ha ancora ricevuto suoi messaggi precedenti. In questa eventualità non possono essere fatte assunzioni sull’ordine con cui saranno ricevuti i messaggi. Affinché i messaggi siano ricevuti nello stesso ordine di invio essi dovranno essere organizzati in una struttura dati distribuita più complessa (ad esempio una coda-in con un solo produttore ed un solo consumatore).

Comunicazione asimmetrica

Questa forma di comunicazione prevede il

coinvolgimento di un numero generico di processi mittenti e destinatari.

Si parla di asimmetria in ingresso quando un

processo può ricevere un messaggio da uno fra più possibili mittenti. In questo caso l’implementazione Linda non obbliga la tupla-messaggio a contenere il nome del mittente, a meno che tale informazione sia necessaria al destinatario (di sicuro nel caso di comunicazione sincrona):

S ::

...

m = ...;

/* questa è una comunicazione

out("S","R",m); in("R","S","ricevuto"); ... R :: ... in(?mittente,"R",?x); out("R",mittente,"ricevuto");

/* R è in grado di conoscere da quale dei mittenti possibili ha ricevuto il messaggio e quindi a chi inviare la tupla di sincronizzazione */

...

Un’altra forma di asimmetria è quella in uscita: un messaggio può essere raccolto da più processi

destinatari. Per questo tipo di comunicazione si hanno due possibili semantiche:

• partner unico: la comunicazione è stabilita con uno solo uno fra più possibili destinatari. In questo caso il messaggio è contenuto in una tupla in cui non è specificato il nome del destinatario. Il reale destinatario sarà quel processo che per primo eseguirà il comando in di rimozione di tale tupla. In una situazione reale ci si aspetta che il mittente intenda eseguire una sequenza di comunicazioni di questo tipo, dove vi sarà alternanza più o meno casuale fra i processi destinatari nella ricezione dei vari messaggi. L’interazione attraverso una struttura del tipo coda-in è un caso particolare di questo tipo di comunicazione (in essa è fissato l’ordine, FIFO, di ricezione dei messaggi).

• diffusione (broadcasting): il messaggio è ricevuto da tutti i possibili destinatari. È già stata incontrata

questa forma di comunicazione in occasione della presentazione della struttura coda-read. Va

sottolineata la generalità di questo meccanismo in quanto può essere applicato anche nei casi in cui il mittente non conosca né l’identità né il numero dei possibili destinatari del suo messaggio. Il problema di questa struttura è che essa non prevede la rimozione automatica del messaggio quando esso è stato raccolto da tutti i destinatari. Qualora sia noto al mittente il numero n dei destinatari si può risolvere banalmente questo inconveniente generando una tupla-messaggio per ognuno di essi:

S ::

... {

for (i=0;i<n;i++) out(m);

} ...

È chiaro che nel caso in cui la comunicazione sia sincrona16, cioè il mittente M si sospende fino a che il messaggio non è stato ricevuto da tutti i destinatari, è necessaria un’ulteriore struttura distribuita per

implementare la "sveglia" di M (ad esempio una tupla contatore): S :: ... { short i; m = ...; out("contatore",n); for (i=0;i<n;i++) out(m); in("contatore",0);

/* S si sincronizza con la ricezione di m da parte di tutti i destinatari */ } ... R :: ... { int indice; in(?x); in("contatore",?indice); out("contatore",indice-1);

/* (indice-1) destinatari non hanno ancora ricevuto il messaggio */ }

...

Gli esempi presentati hanno dimostrato che in Linda possono essere implementate una grande varietà di forme di comunicazione. Ma qual è la forma di comunicazione più elementare e naturale in Linda? Consideriamo i comandi di base per l’invio e la ricezione di un messaggio:

out(m);

e

in(?x);

Questi costrutti sono sufficienti a stabilire lo scambio completo di un messaggio. In questo caso è

sottintesa una forma di comunicazione asincrona con asimmetria sia in ingresso che in uscita. Questa è la forma di comunicazione di base in Linda; qualsiasi altra può essere ottenuta specializzando quest’ultima.

3.4.2.1.1 Alcune proprietà del modello di

comunicazione

Una caratteristica fondamentale del modello Linda di programmazione distribuita è

l’ortogonalità della comunicazione. Da essa derivano un certo numero di proprietà caratterizzanti [Gel85].

La comunicazione in Linda è ortogonale nel senso che sia il mittente che il destinatario non hanno alcuna conoscenza dell’identità del partner. Generalmente questa caratteristica non è presente nei linguaggi di

programmazione concorrente in virtù del fatto che il mittente nomina (esplicitamente o meno) il destinatario della comunicazione.

L’ortogonalità della comunicazione ha due importanti conseguenze: il disaccoppiamento in spazio e tempo dei processi. Una terza proprietà, a sua volta, trae origine dalle prime due e prende il nome di condivisione

distribuita.

Disaccoppiamento in spazio

Questa proprietà si riferisce al fatto che una tupla contenuta nello spazio delle tuple può essere acceduta da un numero qualsiasi di processi con spazi degli indirizzi disgiunti. I linguaggi concorrenti di norma permettono in un costrutto di ricezione di "importare" dati originati in uno qualsiasi fra più spazi degli indirizzi diversi. Allo stesso modo Linda consente anche ad un mittente di inviare dei dati in uno qualsiasi fra più spazi degli indirizzi distinti.

Disaccoppiamento in tempo

Una tupla inserita nell’omonimo spazio tramite out o eval rimane in esso fino a che non è rimossa da un costrutto in corrispondente. Supponiamo che il processo mittente S termini la sua esecuzione senza che la tupla da lui generata sia stata ancora "consumata". Linda permette anche ad un processo R, la cui esecuzione ha inizio successivamente alla terminazione di S, di prelevare la tupla e quindi completare la comunicazione. In Linda è quindi possibile stabilire una comunicazione fra

processi non solo con spazi disgiunti, ma anche disgiunti in tempo.

Linda consente ad n processi con spazi degli indirizzi disgiunti di condividere una qualche variabile v memorizzando questa nello spazio delle tuple. La definizione degli operatori Linda garantisce l’atomicità e quindi la consistenza degli accessi a v. Non è quindi necessario, come nei linguaggi ad ambiente locale, che una variabile condivisa sia implementata all’interno di un processo o modulo gestore.

3.4.2.2 La sincronizzazione

Non sempre l’interazione fra processi comporta un passaggio di informazioni (dati di ingresso, risultati intermedi o finali, ecc.). Talvolta essa può essere finalizzata alla sola sincronizzazione: un processo si pone in attesa che si verifichi un certo evento la cui attuazione dipende dal comportamento di altri processi. Nei linguaggi di programmazione concorrente di norma la sincronizzazione è implementata con gli stessi strumenti messi a disposizione per la comunicazione, in quanto da un punto di vista concettuale la sincronizzazione fra processi è una comunicazione poiché comporta implicitamente il passaggio dell’informazione: "si è verificato l’evento X". Anche in Linda ritroviamo

questa filosofia: come per la comunicazione, è ancora lo spazio delle tuple l’ambiente di base per

l’implementazione della sincronizzazione.

Esempio 3.11

Sia un gruppo di n processi. In ogni processo sia definito un punto di sincronizzazione, cioè un punto del loro flusso di esecuzione sul quale essi si sospendono in attesa del verificarsi di uno stesso evento E. Sia E = "tutti i processi del gruppo hanno raggiunto il rispettivo punto di sincronizzazione". La situazione descritta si presenta frequentemente nelle applicazioni parallele; essa può essere

facilmente tradotta in codice Linda definendo una nuova struttura dati distribuita che può essere chiamata "barriera di sincronizzazione". Si tratta di una tupla contatore destinata a tenere memoria del numero di processi che ancora devono raggiungere la barriera stessa.

La tupla sarà inizializzata con:

out("barriera",n);

Raggiunto il punto di sincronizzazione, ogni processo del gruppo eseguirà il codice:

in("barriera",?val); out("barriera",val-1);

rd("barriera",0);

Si osservi come il verificarsi dell’evento E su cui ogni processo si sincronizza sia stato modellato con l’evento Linda: "introduzione di ("barriera",0) nello spazio delle tuple".