In cazul programelor distribuite, determinarea momentului cand acestea s-au terminat nu este o problema simpla. Printre dificultatile care apar amintim urmatoarele: este aproape imposibil sa observam ce se intampla pe mai multe masini in exact acelasi timp; de asemenea, chiar daca toate procesele sunt inactive, mai pot exista mesaje in tranzit intre ele - deci nu putem lua decizia terminarii bazandu-ne numai pe aceasta conditie.
Exista diverse tipuri de algoritmi pentru detectia terminarii intr-un program distribuit. Prezentam mai jos doua tipuri de algoritmi:
* algoritmi bazati pe tehnica jetoanelor (token): in acesti algoritmi, se genereaza un mesaj special de tip "token", care va traversa toate legaturile dintre procese, asigurand faptul ca pe aceste legaturi nu exista mesaje in tranzit. Cea mai simpla varianta este aceea in care procesele sunt conectate intr-o topologie de tip inel, dar algoritmul se poate aplica si la o topologie generala de graf, daca se poate construi un ciclu care sa parcurga toate legaturile grafului
** algoritmi bazati pe confirmarea mesajelor: in acesti algoritmi, mesajele transmise prin legaturile grafului de procese vor fi confirmate de catre procesele destinatie (prin trimiterea unui mesaj de confirmare catre sursa); in acest fel, daca pentru toate mesajele transmise printr-un canal s-au primit confirmari, se poate trage concluzia ca acesta este gol. Un exemplu de algoritm din aceasta categorie este algoritmul Dijkstra-Scholten.
Algoritmul Dijkstra - Scholten
Algoritmul se bazeaza pe trimiterea intre procese a unor semnale de confirmare. Schema de semnalare a terminarii este separata si suplimentara fata de prelucrarea propriu-zisa pe care o realizeaza procesul. Ea urmareste informarea sursei despre terminarea colectiei de procese. Procesele pot receptiona si transmite semnale, chiar si atunci cand sunt libere, deci au terminat prelucrarea caracteristica a datelor. Semnalele se transmit in sens invers datelor, reprezentand confirmari ale prelucrarii acestora de catre destinatar.
Algoritmul rezolva problema in cazul general, in care sunt permise cicluri in graful proceselor. Rezolvarea se face prin generarea unui arbore de acoperire, pe parcursul transferului mesajelor de date: fiecare proces pastreaza o variabila prim a carei valoare este egala cu identificatorul procesului de la care s-a receptionat primul mesaj de date.
Rezolvarea implica trei faze:
# trimiterea semnalelor pe toate legaturile de intrare, cu exceptia celei de la prim;
# receptia semnalelor pe toate legaturile de iesire;
# transmiterea semnalelor spre prim.
~~~~~~~~~~~~~~~~~ aplicatie ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Intr-un graf aciclic(1) sau ciclic(2) radacina initiaza semnalul de terminare, il propaga in intreg graful/arborele iar programul se termina cu adevarat cand radacina primeste confirmari de la toti urmasii .
Aceasta afiseaza distanta dintre ea si cel mai indepartat nod.
Pentru cazul existentei unui ciclu(2), se pastreaza un vector numit primit care tine minte daca un proces i si-a aflat parintele sau nu, pentru a nu accepta primirea mesajului de la 2 parinti si astfel incurca fluxul mesajelor. Daca nu se doreste apelarea la o astfel de variabila "globala", vectorul primit se poate trimite updatat la fiecare transmisie intre procese...
======== (1) ============
#include "mpi.h"
#include "stdio.h"
/* terminarea unui prog distribuit
* ---- graf aciclic -------------
*/
int main(argc,argv)
int argc;
char *argv[]; {
int m[7][7],i,j;
for(i=0;i<=6;i++)
for(j=0;j<=6; j++)
m[i][j] = 0;
m[0][1] = m[1][0] = 1;
m[0][2] = m[2][0] = 1;
m[1][3] = m[3][1] = 1;
m[4][1] = m[1][4] = 1;
m[5][2] = m[2][5] = 1;
m[5][6] = m[6][5] = 1;
int numtasks, rank, dest, source, rc, count, tag=1;
int inmsg, outmsg=0;
MPI_Status Stat;
MPI_Request req;
MPI_Init(&argc,&argv);
MPI_Comm_size(MPI_COMM_WORLD, &numtasks);
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
if (rank == 0) {
inmsg = 0;
int nr_copii = 0;
for(i=1;i<=6;i++)
if(m[0][i]==1) {
nr_copii++;
rc = MPI_Send(&inmsg, 1, MPI_INT, i, tag, MPI_COMM_WORLD);
}
for(i=0;i<=nr_copii-1;i++) {
rc = MPI_Recv(&outmsg, 1, MPI_INT, MPI_ANY_SOURCE, tag, MPI_COMM_WORLD, &Stat);
if(outmsg > inmsg)
inmsg = outmsg;
}
printf("S-a terminat\nDistanta maxima: %d\n", inmsg);
}
else {
MPI_Status src;
rc = MPI_Recv(&inmsg, 1, MPI_INT, MPI_ANY_SOURCE, tag, MPI_COMM_WORLD, &src);
inmsg++;
int nr_copii = 0;
for(i=0; i<=6; i++)
if(m[rank][i]==1 && i!=src.MPI_SOURCE) {
nr_copii++;
rc = MPI_Send(&inmsg, 1, MPI_INT, i, tag, MPI_COMM_WORLD);
}
if(nr_copii==0) { //frunza, trimite in sus
rc = MPI_Send(&inmsg, 1, MPI_INT, src.MPI_SOURCE, tag, MPI_COMM_WORLD); }
else { // primeste de jos
for(i=0; i<=nr_copii-1; i++) {
rc = MPI_Recv(&outmsg, 1, MPI_INT, MPI_ANY_SOURCE, tag, MPI_COMM_WORLD, &Stat);
if(outmsg > inmsg)
inmsg = outmsg;
}
rc = MPI_Send(&inmsg, 1, MPI_INT, src.MPI_SOURCE, tag, MPI_COMM_WORLD);
}
}
MPI_Finalize();
}
======= (2) ========
#include "mpi.h"
#include "stdio.h"
/* terminarea unui prog distribuit
* ---- graful contine cicluri -------------
*/
int main(argc,argv)
int argc;
char *argv[]; {
int m[6][6],i,j;
for(i=0;i<=5;i++)
for(j=0;j<=5; j++)
m[i][j] = 0;
m[0][1] = m[1][0] = 1;
m[0][2] = m[2][0] = 1;
m[1][3] = m[3][1] = 1;
m[4][1] = m[1][4] = 1;
m[5][2] = m[2][5] = 1;
m[1][2] = m[2][1] = 1;
int numtasks, rank, dest, source, rc, count, tag=1;
int inmsg, outmsg=0;
MPI_Status Stat;
MPI_Request req;
MPI_Init(&argc,&argv);
MPI_Comm_size(MPI_COMM_WORLD, &numtasks);
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
int primit[6];
for(i=0;i<=5; i++)
primit[i] = 0;
if (rank == 0) {
inmsg = 0;
int nr_copii = 0;
for(i=1;i<=5;i++)
if(m[0][i]==1) {
nr_copii++;
rc = MPI_Send(&inmsg, 1, MPI_INT, i, tag, MPI_COMM_WORLD);
}
for(i=0;i<=nr_copii-1;i++) {
rc = MPI_Recv(&outmsg, 1, MPI_INT, MPI_ANY_SOURCE, tag, MPI_COMM_WORLD, &Stat);
if(outmsg > inmsg)
inmsg = outmsg;
}
printf("S-a terminat\nDistanta maxima: %d\n", inmsg);
}
else {
MPI_Status src;
rc = MPI_Recv(&inmsg, 1, MPI_INT, MPI_ANY_SOURCE, tag, MPI_COMM_WORLD, &src);
int parinte = src.MPI_SOURCE;
primit[rank] = 1;
inmsg++;
int nr_copii = 0;
for(i=0; i<=5; i++)
if(m[rank][i]==1 && i!=parinte && primit[i]==0) {
nr_copii++;
rc = MPI_Send(&inmsg, 1, MPI_INT, i, tag, MPI_COMM_WORLD);//, &req);
}
if(nr_copii==0) { //frunza, trimite in sus
rc = MPI_Send(&inmsg, 1, MPI_INT, parinte, tag, MPI_COMM_WORLD); } // &req); }
else { // primeste de jos
for(i=0; i<=nr_copii-1; i++) {
rc = MPI_Recv(&outmsg, 1, MPI_INT, MPI_ANY_SOURCE, tag, MPI_COMM_WORLD, &Stat);
if(outmsg > inmsg)
inmsg = outmsg;
}
rc = MPI_Send(&inmsg, 1, MPI_INT, parinte, tag, MPI_COMM_WORLD);
}
}
MPI_Finalize();
}
