KDP/Prsten
Procesi raspoređeni u prsten je tip zadataka iz distribuiranog programiranja iz trećeg bloka nastave i dolazi na distribuiranom delu ispita za SI i RTI.
Jun 2020, 5. zadatak
Postavka
Realizovati prsten od n procesa, koji komuniciraju asinhronim prosleđivanjem poruka korišćenjem komunikacionih kanala i send i receive iskaza, a kod koga proces 0 generiše slučajan niz od m prirodnih brojeva u intervalu od 1 do 20.000 završen sa sentinel vrednošću EONAT (npr 20.001). Preostalih n-1 procesa odstranjuju iz niza sve pojave prvih n-1 prostih brojeva. Svaki proces ima po jedan različit prost broj za koji je zadužen. Nakon odstranjivanja prostih brojeva, modifikovan niz se distribuira svim procesima. Obezbediti maksimalnu konkurentnost.
Rešenje
const int N = ...;
const int m = ...;
const int EONAT = 20001;
chan values[N](int);
void process0(){
int array[m];
for (int i = 0; i < m; i++) array[i] = rand(1, 20000);
for (int i = 0; i < m; i++) send values[1](array[i]);
send values[1](EONAT);
bool end = false;
int temp, index = 0;
while (!end) {
receive values[0](temp);
if (temp == EONAT) end = true;
else array[index++] = temp;
}
for (int i = 0; i < index; i++) send values[1](array[i]);
send values[1](EONAT);
}
void process(int id, int myNumber) {
int array[m];
bool end = false;
int temp;
while (!end) {
receive values[id](temp);
if (temp == EONAT) end = true;
else if (temp != myNumber) send values[(id + 1) % N](temp);
}
end = false;
int index = 0;
while (!end) {
receive values[id](temp);
if (temp == EONAT) end = true;
else {
array[index++] = temp;
if (id != N-1) send values[(id + 1) % N](temp);
}
}
}
Jun 2021, 3. zadatak
Postavka
Posmatra se prsten u kome svaki čvor može da primi poruku samo od svog prethodnika i koji može da pošalje poruku smo[sic] svom sledbeniku. Svaki čvor sadrži celobrojnu vrednost. Potrebno je ostvariti interakcije između tih čvorova koristeći sinhronu komunikaciju da bi se saznalo koja je minimalna a koja je maksimalna vrednost. Svaki čvor treba da sazna koje su maksimalna i minimalna vrednost.
Rešenje
const int N = 100;
chan<pair<int, int>> values[N];
void process(int i, int v) {
int min = v;
int max = v;
pair<int, int> newPair;
if (i == 0) {
// Први процес прво шаље, прима коначни резултат и прослеђује
values[0].send({min, max});
newPair = values[N-1].receive();
} else {
// Остали процеси прво примају, израчунавају, шаљу даље, примају коначни резултат и прослеђују
newPair = values[i-1].receive();
if (newPair.first < min) {
min = newPair.first;
}
if (newPair.second > max) {
max = newPair.second;
}
values[i].send({min, max});
newPair = values[i-1].receive();
}
min = newPair.first;
max = newPair.second;
if (i != N-1) {
// Ако смо последњи процес не треба да шаљемо првом опет, јер неће примити
values[i].send({min, max});
}
}