31
2018-2019 Canale si schimb de mesaje Capitolul 6
2018-2019
Canale si schimb de mesaje
Capitolul 6
2018-2019
Comunicatie intre procese
• Procesele pot interschimba informatie prin:
– Memorie comuna
– Comunicare prin transfer de mesaje (engl. message passing)
• Tipuri de comunicare intre procese:
– Comunicatie sincrona: in acest caz schimbul de mesaje este o actiune
atomica ce implica participarea ambelor procese: transmitator sau
expeditor (engl. sender) si receptor sau destinatar (engl. receiver).
• Daca transmitatorul este gata sa transmita un mesaj inainte ca receptorul sa fie
gata sa-l primeasca, transmitatorul se blocheaza.
• Daca receptorul este gata sa primeasca un mesaj, dar transmitatorul nu e gata sa-l
transmita, receptorul se blocheaza
– Comunicatie asincrona: in acest caz transmitatorul nu se va bloca daca
receptorul nu este gata sa primeasca mesajul. In acest caz, mesajul
trebuie salvat temporar pana cand receptorul ajunge in starea de a-l
putea receptiona.
2018-2019
Conventii de adresare
• In general, pentru a putea transmite un mesaj,
transmitatorul trebuie sa cunoasca adresa
receptorului.
• Exista 3 conventii standard de adresare:
– Adresare asimetrica.
– Adresare simetrica.
– Comunicatie fara adresare.
2018-2019
Adresare asimetrica
• Receptorul nu este obligat sa cunoasca adresa transmitatorului.
• Identificarea transmitatorului este posibila, dar transmitatorul
poate optional sa anuleze aceasta optiune.
• Adresarea asimetrica este preferata in modelul client-server.
Clientul trebuie sa stie ce serviciu sa apeleze, iar serverul poate
fi programat fara sa stie clientii care il vor apela. Daca e
necesar, identitatea unui client se poate incapsula in mesajele
transmise de client serverului.
2018-2019
Adresare simetrica
• Este preferata cand procesele coopereaza pentru
rezolvarea unei probleme, in modelul P2P.
• Schema se poate implementa prin definirea unor canale
ce pot fi numite (engl. named channels).
• O pereche sau grup de procese pot partaja un canal,
prin numele acestuia.
2018-2019
Comunicatie fara adresare
• Adresarea se face implicit prin identificarea unor
sabloane in continutul mesajului (engl. pattern
matching).
– (i) rutarea mesajului catre destinatar se poate face functie de
continut sau
– (ii) mesajul poate fi receptionat de toate procesele sau de un
grup de procese
2018-2019
Producator-consumator cu canale
channel of integer ch
producator consumator
integer x
loop forever
p1: x produce
p2: ch x
integer y
loop forever
c1: ch y
c2: consume(y)
Producator-consumator cu canale
Sursa: M.Ben-Ari, 2006
• Un canal conecteaza un proces transmitator cu un proces receptor.
• De obicei un canal are asociat un tip care descrie tipul mesajelor care pot fi
transportate de canalul respectiv.
• Un canal este sincron. In exemplu, transferul de date va avea loc cand
contorul de program al transmitatorului se afla in p2 si al receptorului la c1.
2018-2019
Problema filosofilor cu canale
• Furculitele se implementeaza prin procese separate ce comunica prin canale cu
filosofii. Filosofi comunica cu Furculitai prin canalul forksi si cu Furculitai+1
prin canalul forksi+1.
• Fiecare Filosofi asteapta mesaje de la furculitele adiacente Furculitai si
Furculitai+1 pe canalele forksi si forksi+1. Valorile mesajelor nu au importanta, se
vor folosi valori boolene egale cu true. Cand mesajele sosesc, inseamna ca
furculitele sunt libere si filosoful le va folosi. Apoi le elibereaza, trimitand cate
un mesaj pe canalele respective.
• Fiecare Furculitai transmite un mesaj prin canalul forksi. Cand acest mesaj este
transmis, furculita poate fi folosita. Apoi asteapta un mesaj pe canalul forksi.
Cand acest mesaj este receptionat, furnculita este eliberata.
Furci
Fili Fili-1
Furci-1 Furci+1
forki forki-1 forki+1
2018-2019
Problema filosofilor cu canale
channel of boolean forks[5]
Filosof i Furculita i
boolean dummy
loop forever
p1: think
p2: forks[i] dummy
p3: forks[i+1] dummy
p4: eat
p5: forks[i] true
p6: forks[i+1] true
boolean dummy
loop forever
q1: forks[i] true
q2: forks[i] dummy
Pseudocod pentru problema filosofilor cu canale
Sursa: M.Ben-Ari, 2006
2018-2019
Canale in Promela
• Promela permite definirea:
– Canalelor sincrone
– Canalelor asincrone de capacitate fixa
• Mesajele pot fi:
– De un singur tip, sau
– De o secventa de tipuri (de exemplu int urmat de bool)
• Se pot defini vectori de canale.
• Exemplu de canal sincron: chan ch = [0] of { int }
• Exemplu de vector de canale asincrone: chan charray[4] = [10] of { int; bool }
2018-2019
Operatii cu canale in Promela
• Receptionarea de valori din canalul ch si stocarea lor
in variabilele vari.
ch ? var1, var2, … varn;
• Testarea unor valori receptionate. Instructiunea este
executabila numai daca componentele primului mesajul
din canal se evalueaza la consti.
ch ? const1, const2, … constn;
• Transmiterea unui mesaj pe un canal.
ch ! expr1, expr2, … exprn;
2018-2019
Procesare concurenta pe flux: problema Conway
• Se considera secventa de caractere primita de la un proces extern, care trebuie procesata astfel:
– Secvente de 2 n 9 caractere consecutive se inlocuiesc prin cifra corespunzatoare lui n, urmata de caracterul respectiv
– Dupa fiecare k caractere ale acestei transforamri se insereaza un caracter sfarsit de linie
• Cele doua transformari se vor implementa in doua procese separate Compress si Output, conectate prin canalul pipe.
• La acestea se adauga procesul Generator care genereaza secventa de intrare si procesul Printer care afiseaza rezultatul.
pipe
Compress Output inC outC
Generator Printer
2018-2019
Problema Conway in Promela: procesul Compress #include "for.h"
#define K 4
#define MAXN 9
chan inC, pipe, outC = [2] of { byte };
active proctype Compress() {
byte previous, count = 0, c;
inC ? previous;
end:do
:: inC ? c ->
if
:: (c == previous) && (count < MAXN-1) -> count++
:: else ->
if
:: count > 0 ->
pipe ! count+1;
count = 0
:: else
fi;
pipe ! previous;
previous = c;
fi
od
}
Eticheta end ne asigura ca o stare terminala in
care serverul este blocat la o instructiune de
receptie nu e considerata invalida
2018-2019
Problema Conway in Promela: procesul Output
active proctype Output() {
byte c, count = 0;
end:do
:: pipe ? c;
outC ! c;
count++;
if
:: count >= K ->
outC ! '\n';
count = 0
:: else
fi
od
}
2018-2019
Procesele Generator si Printer active proctype Generator() {
for (I,1,50)
if
:: inC ! 'a'
:: inC ! 'b'
:: inC ! 'c'
:: inC ! 'd'
fi
rof (I)
}
active proctype Printer() {
byte c;
end:do
:: outC ? c;
if
:: c == '\n' -> printf("\n")
:: (c >= 2) && (c <= 9) -> printf("%d", c)
:: else -> printf("%c", c)
fi;
od
}
Generarea nedeterminista a unei
litere din multimea {„a‟, „b‟, „c‟, „d‟}
2018-2019
Comunicatie sincrona in Java
• Presupune implementarea unei clase Channel<T> care ofera operatiile send si receive, definite astfel:
– send trimite un mesaj de tip T pe canal. Transmitatorul se blocheaza pana cand mesajul este receptionat de pe canal de receptor.
void send(T mes)
– receive preia un mesaj de tip T de pe canal. Receptorul se blocheaza pana cand mesajul este trimis pe canal de transmitator.
T receive()
• Pentru implementare se foloseste sincronizarea pe conditii:
– send instiinteaza receptorii ca un mesaj este ready pe canal, apoi asteapta ca mesajul sa fie preluat de un receptor (canalul sa redevina null)
– receive asteapta ca un mesaj sa fie ready pe canal, copiaza mesajul, elibereaza canalul (acesta va deveni null, iar ready va deveni false) si instiinteaza potentialii transmitatori ca, canalul este liber.
2018-2019
Implementarea comunicatiei sincrone in Java I
public class Channel<T> {
private T chan = null;
int ready = 0;
public synchronized void send(T mes)
throws InterruptedException {
// Copiaza mesajul pe canal
chan = mes;
// Instiinteaza receptorii potentiali facand
// ready = 1
++ready;
notifyAll();
// Asteapta ca mesajul sa fie preluat de receptor,
// canalul devenind vid
while (chan != null) wait();
}
2018-2019
Implementarea comunicatiei sincrone in Java II
public synchronized T receive()
throws InterruptedException {
// Asteapta ca un mesaj sa fie disponibil pe canal,
// cand ready = 1
while (ready==0) wait();
// Copiaza mesajul local, elibereaza canalul si
// instiinteaza potentialii transmitatori
--ready;
T tmp = chan; chan = null;
notifyAll();
return(tmp);
}
}
2018-2019
Comunicatie asincrona
• In comunicatia asincrona operatia send nu blocheaza transmitatorul pana la primirea mesajului de catre destinatar. Operatia reuseste imediat, iar transmitatorul continua fara blocare.
• Mesajele transmise, dar inca nereceptionate sunt stocate temporar intr-o coada. Expeditorul adauga mesaje la sfarsitul cozii, iar destinatarul preia mesajele de la inceputul cozii.
Sursa: Magee & Kramer, 2006
• Pentru comunicatia asincrona se foloseste conceptul de port.
• Un port este reprezentat de o coada teoretic infinita de mesaje.
• Observatie: un port este similar cu tamponul din problema producator - consumator. Tamponul este infinit dpdv conceptual, deci producatorul nu mai asteapta ca tamponul sa nu fie plin inainte de a depune un mesaj.
2018-2019
Comunicatie asincrona in Java
• Se poate implementa dupa modelul producator – consumator.
• Expeditorul este producator.
• Destinatarul este consumator.
• Se va considera ca avem o coada potential infinita. Pentru aceasta se pot folosi structuri de date predefinite in Java. public class Port<T> {
Queue<T> queue = new LinkedList<T>();
int ready = 0;
public synchronized void send(T v) {
queue.add(v);
++ready;
notifyAll();
}
public synchronized T receive() throws InterruptedException {
while (ready==0) wait();
--ready;
return queue.remove();
}
}
2018-2019
Rendezvouz
• Conceptul de rendezvouz este un precursor al modelului client-server din SD.
• Este inspirat din modul in care decurge o intalnire intre doua persoane:
– Persoanele stabilesc de comun acord un punct de intalnire
– Prima persoana care ajunge la intalnire o asteapta pe cealalta
• Procesele din cadrul modelului rendezvouz au doua roluri:
– Rolul acceptor (engl. accepting). In acest model, locatia de rendevouz apartine procesului acceptor si se numeste intrare (engl. entry).
– Rolul apelant (engl. calling). El trebuie sa cunoasca atat identitatea acceptorului, cat si a locatiei de rendevouz.
• Se observa ca rolurile de acceptor si apelant corespund indeaproape rolurilor de server si client ale modelului client-server din SD.
2018-2019
Client – server cu rendevouz
Client Server
dataType param, result
loop forever
p1: param ...
p2: server.service(param,result)
p3: use(result)
dataType p, r
loop forever
q1: ...
q2: accept service(p, r)
q3: r do service(p)
Client – server cu rendevouz
La t1 apelantul asteapta
acceptarea apelului.
La t2 se transfera parametrii
de la apelant la acceptor.
La t3 s-a terminat de
executat apelul si se transfera
rezultatul la apelant.
Sursa: M.Ben-Ari, 2006
2018-2019
• O intrare se reprezinta prin clasa Entry<R,P> ce implementeaza urmatoarele metode:
– P call(R req) ce primeste ca parametru o cerere req de tip R si intoarce un rezultat de tip P. Aceasta metoda este invocata de procesul apelant.
– R accept() ce intoarce o cerere de tip R. Ea este utilizata de procesul acceptor si intoarce catre acest proces o cerere primita de la procesul apelant.
– void reply(P res) ce primeste ca parametru un rezultat de tip P. Metoda este invocata de procesul apelant si are ca efect transmiterea (returnarea) raspunsului res catre apelant.
• O intrare incapsuleaza:
– Un obiect care reprezinta un port pentru primirea de mesaj de apel de la client. Mesajele de apel sunt reprezentate prin clasa CallMsg<R,P>, astfel ca portul se va reprezenta prin clasa Port<CallMsg<R,P>>.
Rendezvouz in Java
2018-2019
Protocol cerere-raspuns pentru rendezvouz in Java
Sursa: Magee & Kramer, 2006
2018-2019
public class Entry<R,P> {
private CallMsg<R,P> cm;
private Port<CallMsg<R,P>> cp = new Port<CallMsg<R,P>>();
public P call(R req) throws InterruptedException {
Channel<P> clientChan = new Channel<P>();
cp.send(new CallMsg<R,P>(req,clientChan));
return clientChan.receive();
}
public R accept() throws InterruptedException {
cm = cp.receive();
return cm.request;
}
public void reply(P res) throws InterruptedException {
cm.replychan.send(res);
}
private class CallMsg<R1,P1> {
R1 request;
Channel<P1> replychan;
CallMsg(R1 m, Channel<P1> c) {
request = m;
replychan = c;
}
}
}
Punct de rendezvouz in Java
2018-2019
public class Caller implements Runnable {
private Entry<String,String> entry;
private String id;
public Caller(Entry<String,String> e, String s) {
entry = e; id = s;
}
public void run() {
try {
for (int i=0;i<10;i++) {
System.out.println("Caller "+id+" parameter: "+id);
String result = entry.call(id);
System.out.println("Caller "+id+" result: "+result);
}
}
catch (InterruptedException e){}
}
}
Apelant de rendezvouz in Java
2018-2019
public class Accepter implements Runnable {
private int c = 0;
private Entry<String,String> entry;
public Accepter(Entry<String,String> e) {
entry = e;
}
public void run() {
try {
while(true) {
String request = entry.accept();
System.out.println("Accepter request"+": "+request);
String result = request+(++c);
System.out.println("Accepter result"+": "+result);
entry.reply(result);
}
} catch (InterruptedException e){}
}
}
Acceptor de rendezvouz in Java
2018-2019
public class Main {
static Entry<String,String> e = new Entry<String,String>();
static Caller ionel = new Caller(e,"Ionel");
static Caller gigel = new Caller(e,"Gigel");
static Accepter maria = new Accepter(e);
public static void main(String[] args) {
Thread tIonel = new Thread(ionel);
Thread tGigel = new Thread(gigel);
Thread tMaria = new Thread(maria);
tIonel.start();
tGigel.start();
tMaria.start();
}
}
Test rendezvouz in Java
2018-2019
Thread 1
Object 1
Object 2
Thread 2
Exchanger
Rendezvouz folosind clasa Exchanger
• Clasa java.util.concurrent.Exchanger<V> defineste un punct de rendezvouz unde doua fire pot interschimba doua obiecte.
• Aceasta clasa dispune de metoda: V exchange(V x)
Apelul asteapta un alt fir sa ajunga la punctul de rendezvouz, ii transfera
obiectul x si apoi ii returneaza un obiect receptionat de la celalalt fir.
• Apelul are si o versiune cu timeout, definita astfel: V exchange(V x, long timeout, TimeUnit unit)
• Tema: sa se implementeze exemplul cu Ionel, Gigel si Maria folosind clasa Exchanger.
2018-2019
Receptie selectiva
• Se refera la posibilitatea ca un proces sa astepte intrari nu doar
de pe un singur canal, ci pe o multime de canale:
either cond1 and ch1 var1
S1
or cond1 and ch2 var2
S2
….
or condn and chn varn
Sn
[else Sn+1]
• In acest fel asteptarea are loc “in paralel” pe toate canalele.
Daca este prezenta clauza “else” atunci asteptarea este fara
blocare.
2018-2019
Receptie selectiva in Promela
• Receptia selectiva se poate implementa folosind comenzi cu garzi. In
acest caz, alegerile vor contine si instructiuni de receptionare de pe canale.
• Spre exemplu, se considera o parcare in care sosesc si pleaca masini.
Numarul de locuri libere se reprezinta prin variabila spaces. Pentru
semnalarea sosirilor si plecarilor, procesul Parking primeste mesaje pe
canalele arrivals si departures de la masinile care sosesc sau pleaca.
do
:: (spaces>0) && (departures ? car) ->
printf(“Car %d arrived\n”,car); --spaces;
:: (spaces<N) && (arrivals ? car) ->
printf(“Car %d departed\n”,car); ++spaces;
od
