KDP/Aktivni monitori
Aktivni monitori su koncept distribuiranog programiranja iz trećeg bloka nastave i dolaze na distribuiranom delu ispita za SI i RTI.
Januar 2020, 3. zadatak
Postavka
Koristeći tehniku aktivnih monitora potrebno je realizovati semafor koji pored standardnih atomskih operacija signal() i wait() ima i atomske operacije signal(n) i wait(n) koja internu semaforsku promenljivu atomski uvećava odnosno umanjuje za n ukoliko je to moguće, ukoliko nije čeka dok ne bude bili moguće. Proces koji je ranije uputio zahtev treba ranije da obavi svoju operaciju.
Rešenje
enum op_kind { WAIT, SIGNAL, WAITN, SIGNALN };
chan request(int, op_kind, int);
chan reply[n](bool);
class Semaphore {
public:
void run() {
int clientID;
op_kind kind;
int n;
int tokens = 0;
queue<pair<int,int>> pending;
while (true) {
receive request(clientID, kind, n);
if (kind == WAIT) {
if (tokens <= 0) {
pending.push(make_pair(clientID, 1));
} else {
tokens--;
send reply[clientID](true);
}
} else if (kind == WAITN) {
if (tokens <= n-1) {
pending.push(make_pair(clientID, n));
} else {
tokens = tokens-n;
send reply[clientID](true);
}
} else if (kind == SIGNAL) {
tokens++;
if (!pending.empty() && pending.front().second == tokens) {
tokens = 0;
send reply[pending.front().first](true);
pending.pop();
}
} else if (kind == SIGNALN) {
tokens += n;
while (!pending.empty() && pending.front().second <= tokens) {
tokens -= pending.front().second;
send reply[pending.front().first](true);
pending.pop();
}
}
}
}
}
Jul 2020, 3. zadatak
Postavka
Koristeći aktivne monitore rešiti problem filozofa koji ručavaju (The Dining Philosophers). Filozofi mogu da komuniciraju isključivo sa procesom koordinatorom (centralizovano rešenje). Obezbediti da filozof koji je pre zatražio da jede pre i započinje sa jelom. Napisati kod za filozofe i za proces koordinator
Rešenje
Napomena: Zbog zahteva da filozof koji je pre zatražio da jede pre i započne sa jelom ide se po strogo FIFO redosledu, i filozofi koji su se zablokirali na čekanju viljuške neće je dobiti sve dok svi filozofi koji su zatražili viljušku pre njih ne dobiju svoju, i iz tog razloga je potrebna while petlja kod otpuštanja viljuške.
const int N = ...;
enum op_kind{REQUEST,RELEASE};
// Poslednji parametar ukazuje na to da li filozof trazi levu ili desnu viljusku
chan request(int, op_kind kind, bool);
chan reply[N](bool);
class Coordinator {
public:
void run() {
int philosopher;
op_kind kind;
bool left;
queue<pair<int,int>> waiting;
int forks[N] = {};
while (true) {
receive request(philosopher, kind, left);
int fork = left ? philosopher : (philosopher + 1) % N;
if (kind == REQUEST) {
if (forks[fork] == 0) {
forks[fork] = 1;
send reply[philosopher](true);
} else {
waiting.push(make_pair(philosopher, fork));
}
} else if (kind == RELEASE) {
forks[fork] = 0;
while (!waiting.empty() && forks[waiting.front().second] == 0){
send reply[waiting.front().first](true);
waiting.pop();
}
}
}
}
}
void philosopher(int id) {
bool status;
while(true) {
// Think
send request(id, REQUEST, id != 0);
receive reply[id](status);
send request(id, REQUEST, id == 0);
receive reply[id](status);
// Eat
send request(id, RELEASE, id != 0);
send request(id, RELEASE, id == 0);
}
}
Avgust 2021, 4. zadatak
- Ovaj zadatak nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.
Postavka
Postoji jedan proizvođač i N potrošača koji dele zajednički bafer kapaciteta B (Atomic broadcast problem). Proizvođač ubacuje proizvod u bafer i to samo u slobodne slotove na koji čekaju svih N potrošača. Svaki potrošač mora da primi proizvod u tačno onom redosledu u kome su proizvedeni, mada različiti potrošači mogu u isto vreme da uzimaju različite proizvode. Proizvođači i potrošači mogu da komuniciraju isključivo sa procesom koordinatorom (centralizovano rešenje) koji ima samo jedan tok kontrole i ponaša se kao aktivni monitor. Svaki proces ima samo jedno sanduče iz koga može da čita, i iz svakog sandučeta može da čita samo jedan proces dok veći broj može da upisuje. Napisati kod za proizvođače, potrošače i za proces koordinator.
Rešenje
Februar 2023, 3. zadatak
Postavka
Koristeći aktivne monitore rešiti problem filozofa koji ručavaju (The Dining Philosophers). Filozofi mogu da komuniciraju isključivo sa procesom koordinatorom (centralizovano rešenje). Obezbediti da filozof koji je pre zatražio da jede pre i započinje sa jelom. Napisati kod za filozofe i za proces koordinator.
Rešenje
- Isti zadatak došao je u julu 2020. godine. Ipak, autor je odlučio da postavi svoje rešenje koje je dobilo maksimalan broj bodova.
const int N = ...;
enum op_kind{REQUEST,RELEASE};
chan request(int, op_kind);
chan reply[N](bool);
class Coordinator {
public:
void run() {
int id;
op_kind op;
queue<int> waiting;
int forks[N] = {true};
while (true) {
receive request(id, op);
int left = id, right = (id + 1) % N;
if (op == REQUEST) {
if (forks[left] && forks[right]) {
forks[left] = forks[right] = false;
send reply[id](OK);
} else {
waiting.push(id);
}
} else if (op == RELEASE) {
forks[left] = forks[right] = true;
send reply[id](OK);
while (!waiting.empty()) {
id = waiting.top();
left = id, right = (id + 1) % N;
if (forks[left] && forks[right]) {
forks[left] = forks[right] = false;
waiting.pop();
send reply[id](OK);
} else break;
}
}
}
}
}
void philosopher(int id) {
bool status;
while (true) {
// Think
send request(id, REQUEST);
receive reply[id](status);
// Eat
send request(id, RELEASE);
receive reply[id](status)
}
}
Februar 2024, 3. zadatak
Postavka
Rešiti problem čitalaca i pisaca (Readers-Writers problem) koristeći aktivne monitore. Obezbediti da proces koji je pre uputio zahtev za pristup resursu pre treba da bude opslužen.
Rešenje
const int N = ...; //broj citalaca + broj pisaca
chan s(int, int); //id, op
chan r[N](int, int);
// 0 - start read
// 1 - end read
// 2 - start write
// 3 - end write
void reader(int id) {
bool status;
while(true) {
send s(id, 0);
receive r[id](status);
//read
send s(id, 1);
receive r[id](status);
}
}
void writer(int id) {
bool status;
while(true) {
send s(id, 2);
receive r[id](status);
//write
send s(id, 3);
receive r[id](status);
}
}
void monitor() {
int id, op, numR = 0;
queue buffer(int, int);
while(true) {
if(buffer.isNotEmpty()) id, op = buffer.get();
else receive s(id, op);
if(op == 0) {
numR++;
send r[id](true);
} else if(op == 1) {
numR--;
send r[id](true);
} else if(op == 2) {
int id2, op2;
while(numR > 0) {
receive s(id2, op2);
if(op2 == 0 || op2 == 2) buffer.put(id2, op2);
else if(op2 == 1) {
numR--;
send r[id2](true);
}
}
send r[id](true);
while(true) {
receive s(id2, op2);
if(op2 == 0 || op2 == 2) buffer.put(id2, op2);
else if(op2 == 3) {
send r[id2](true);
break;
}
}
}
}
}