KDP/Januar 2022
Postavka ovog roka može se naći sa stranice predmeta.
1. zadatak
Postavka
Razmatra se problem sinhronizacije na barijeri (Barrier Synchronization). Sinhronizaciona barijera omogućava nitima da na njoj sačekaju dok tačno N niti ne dostigne određenu tačku u izvršavanju pre nego što bilo koja od tih niti ne nastavi sa svojim izvršavanjem. Koristeći raspodeljene binarne semafore i tehniku predaje štafetne palice rešiti ovaj problem. Omogućiti da se ista barijera može koristiti veći broj puta.
Rešenje
sem arrived = 1;
sem continued = 0;
int blocked = 0;
const int N = 100;
void work1();
void work2();
void worker() {
while (true) {
work1();
arrived.wait();
blocked++;
if (blocked != N) {
arrived.signal();
continued.wait();
}
blocked--;
if (blocked > 0) {
continued.signal();
} else {
arrived.signal();
}
work2();
}
}
2. zadatak
Postavka
U berbernici rade dva berberina, Aca i Braca, postoji 10 stolica za čekanje i dve stolice za kojima berberini rade. Mušterije koje dolaze se izjašnjavaju da li čekaju kod Ace ili Brace ili im je svejedno ko će da ih usluži. Nakon završenog brijanja, mušterija plaća i odlazi. Ako mušterija vidi da nema mesta u berbernici i ne može biti uslužena, odlazi. Kada je berberin slobodan, mušterija koja je najduže čekala će prva biti uslužena (osim ako čeka na drugog berberina i tada tražimo sledeću mušteriju u nizu). Ukoliko je neki od berberina besposlen, on spava, i prva mušterija koja kod njega dođe na red treba da ga probudi i bude uslužena. Koristeći monitore sa signal and continue disciplinom rešiti ovaj problem.
Rešenje
class Berbernica {
// Идентификатори које муштерије могу да проследе у osisajSe()
public static final int ACA_ID = 0;
public static final int BRACA_ID = 1;
public static final int BILO_KO = 2;
// Редови чекања муштерија на столицама за шишање
private Condition[] redZaSisanje = new Condition[3];
// Редови чекања берберина када спавају
private Condition[] berberinGotov = new Condition[2];
// Редови чекања муштерија док се шишају
private Condition[] cekamKrajSisanja = new Condition[2];
// Редови чекања берберина док чекају муштерију да плати и изађе
private Condition[] cekamIsplatu = new Condition[2];
// Да ли је берберин тренутно заузет
private boolean[] zauzet = new boolean[2];
// Коју муштерију берберин тренутно шиша (идентификује се по броју у реду)
private int trenutnoSisam = new int[2];
// Број преосталих столица за седење
private int stolice = 10;
// Редни број муштерије
private int red = 1;
public Berbernica() {
for (int i = 0; i < 3; ++i) {
redZaSisanje[i] = new Condition();
}
for (int i = 0; i < 2; ++i) {
berberinGotov[i] = new Condition();
cekamKrajSisanja[i] = new Condition();
cekamIsplatu[i] = new Condition();
zauzet[i] = true;
}
}
// Враћа идентификатор берберина уколико је слободан,
// или -1 уколико нема слободних берберина за задати избор
private int daLiJeZauzet(int izbor) {
switch (izbor) {
case ACA_ID:
case BRACA_ID:
return zauzet[izbor] ? -1 : izbor;
case BILO_KO:
if (!zauzet[ACA_ID]) {
return ACA_ID;
}
if (!zauzet[BRACA_ID]) {
return BRACA_ID;
}
return -1;
}
}
public synchronized boolean osisajSe(int izbor) {
int mojRed = red++;
int berberin = daLiJeZauzet(izbor);
if (berberin == -1) {
if (stolice == 0) {
return false;
}
--stolice;
redZaSisanje[izbor].wait(mojRed);
if (izbor == BILO_KO) {
if (trenutnoSisam[ACA_ID] == mojRed) {
berberin = ACA_ID;
} else {
berberin = BRACA_ID;
}
} else {
berberin = izbor;
}
++stolice;
} else {
zauzet[berberin] = true;
trenutnoSisam[berberin] = mojRed;
berberinGotov[berberin].signal();
}
// Седање на столицу се не моделује неком посебном методом
cekamKrajSisanja[berberin].wait();
// Плаћање и излазак
cekamIsplatu[berberin].signal();
return true;
}
public synchronized void sacekajMusteriju(int berberId) {
int musterija;
if (redZaSisanje[berberId].queue() && redZaSisanje[BILO_KO].queue()) {
int musterija1 = redZaSisanje[berberId].minrank();
int musterija2 = redZaSisanje[BILO_KO].minrank();
if (musterija1 < musterija2) {
musterija = musterija1;
trenutnoSisam[berberId] = musterija;
redZaSisanje[berberId].signal();
} else {
musterija = musterija2;
trenutnoSisam[berberId] = musterija;
redZaSisanje[BILO_KO].signal();
}
} else if (redZaSisanje[berberId].queue()) {
musterija = redZaSisanje[berberId].minrank();
trenutnoSisam[berberId] = musterija;
redZaSisanje[berberId].signal();
} else if (redZaSisanje[BILO_KO].queue()) {
musterija = redZaSisanje[BILO_KO].minrank();
trenutnoSisam[berberId] = musterija;
redZaSisanje[BILO_KO].signal();
} else {
zauzet[berberId] = false;
berberinGotov[berberId].wait();
}
}
public synchronized void obavestiMusteriju(int berberId) {
trenutnoSisam[berberId] = 0;
cekamKrajSisanja[berberId].signal();
cekamIsplatu[berberId].wait();
}
}
3. zadatak
Postavka
Rešiti problem filozofa koji ručavaju koristeći C-Lindu. Filozof koji je ranije izrazio želju za hranom treba ranije da budu[sic] opslužen.
Rešenje
const int N = 5;
void philosopher(int i) {
int left = i;
int right = (i + 1) % N;
while (true) {
// Мислимо
in("fifo");
in("permit");
in("fork", left);
in("fork", right);
out("fifo");
// Једемо
out("fork", right);
out("fork", left);
out("permit");
}
}
void init() {
for (int i = 0; i < N; ++i) {
out("fork", i);
eval(philosopher, i);
if (i != N-1) {
out("permit");
}
}
out("fifo");
}
4. zadatak
Postavka
Deda Mraz koji živi na severnom polu veći deo svog vremena provodi spavajući (The Santa Claus Problem). Mogu ga probuditi ili ukoliko se ispred vrata pojave svih 9 njegovih irvasa ili 3 od ukupno 10 patuljaka. Kada se Deda Mraz probudi on radi jednu od sledećih stvari: Ukoliko ga je probudila grupa irvasa odmah se sprema i kreće na put da podeli deci igračke. Kada se vrati sa puta svim irvasima daje nagradu. Ukoliko ga je probudila grupa patuljaka onda ih on uvodi u svoju kuću, razgovara sa njima i na kraju ih isprati do izlaznih vrata. Grupa irvasa treba da bude opslužena pre grupe patuljaka. Koristeći CSP napisati programe za Deda Mraza, irvase i patuljke.
Rešenje
[Santa::SANTA, Dwarf(0..10)::DWARF, Reindeer(0..9)::REINDEER]
SANTA::[
dwarf1: integer := -1;
dwarf2: integer := -1;
reindeers: integer := 0;
*[
reindeers < 8; (i: 0..9) Reindeer(i)?wakeup -> [
reindeers := reindeers + 1;
];
□
reindeers == 8; (i: 0..9) Reindeer(i)?wakeup -> [
reindeers := 0;
(j: 0..9) Reindeer(j)!ack;
// Чекамо да ирваси дођу до санки
(j: 0..9) Reindeer(j)?onboard;
// Путујемо и кад се вратимо ирвасима дамо поклон
(j: 0..9) Reindeer(j)!treat;
];
□
dwarf1 == -1; (i: 0..10) Dwarf(i)?wakeup -> [
dwarf1 := i;
];
□
dwarf1 != -1 and dwarf2 == -1; (i: 0..10) Dwarf(i)?wakeup -> [
dwarf2 := i;
];
□
dwarf1 != -1 and dwarf2 != -1; (i: 0..10) Dwarf(i)?wakeup -> [
dwarf3: integer := i;
// Отварамо капију.
Dwarf(dwarf1)!ack;
Dwarf(dwarf2)!ack;
Dwarf(dwarf3)!ack;
// Причамо са патуљцима.
Dwarf(dwarf1)?going;
Dwarf(dwarf2)?going;
Dwarf(dwarf3)?going;
// Пратимо патуљке.
Dwarf(dwarf1)!goodbye;
Dwarf(dwarf2)!goodbye;
Dwarf(dwarf3)!goodbye;
// Чекамо да патуљци оду
Dwarf(dwarf1)?gone;
Dwarf(dwarf2)?gone;
Dwarf(dwarf3)?gone;
// Враћамо се на спавање
dwarf1 := -1;
dwarf2 := -1;
];
];
];
REINDEER::*[
// Радимо нешто друго
Santa!wakeup;
Santa?ack;
// Долазимо до санки
Santa!onboard;
Santa?treat;
];
DWARF::*[
// Радимо нешто друго
Santa!wakeup;
Santa?ack;
// Причамо са Деда Мразом
Santa!going;
Santa?goodbye;
Santa!gone;
];