КДП/Јануар 2022
Поставка овог рока може се наћи са странице предмета.
1. задатак
Поставка
Разматра се проблем синхронизације на баријери (Barrier Synchronization). Синхронизациона баријера омогућава нитима да на њој сачекају док тачно N нити не достигне одређену тачку у извршавању пре него што било која од тих нити не настави са својим извршавањем. Користећи расподељене бинарне семафоре и технику предаје штафетне палице решити овај проблем. Омогућити да се иста баријера може користити већи број пута.
Решење
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. задатак
Поставка
У берберници раде два берберина, Аца и Браца, постоји 10 столица за чекање и две столице за којима берберини раде. Муштерије које долазе се изјашњавају да ли чекају код Аце или Браце или им је свеједно ко ће да их услужи. Након завршеног бријања, муштерија плаћа и одлази. Ако муштерија види да нема места у берберници и не може бити услужена, одлази. Када је берберин слободан, муштерија која је најдуже чекала ће прва бити услужена (осим ако чека на другог берберина и тада тражимо следећу муштерију у низу). Уколико је неки од берберина беспослен, он спава, и прва муштерија која код њега дође на ред треба да га пробуди и буде услужена. Користећи мониторе са signal and continue дисциплином решити овај проблем.
Решење
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. задатак
Поставка
Решити проблем филозофа који ручавају користећи C-Lindu. Филозоф који је раније изразио жељу за храном треба раније да буду[sic] опслужен.
Решење
const int N = 5;
void philosopher(int i) {
int left = i;
int right = (i + 1) % N;
int ticket;
while (true) {
// Мислимо
in("ticket", &ticket);
out("ticket", ticket + 1);
in("current", ticket);
in("fork", left);
in("fork", right);
out("current", ticket + 1);
// Једемо
out("fork", right);
out("fork", left);
}
}
void init() {
for (int i = 0; i < N; ++i) {
out("fork", i);
eval(philosopher, i);
}
out("ticket", 0);
out("current", 0);
}
4. задатак
Поставка
Деда Мраз који живи на северном полу већи део свог времена проводи спавајући (The Santa Claus Problem). Могу га пробудити или уколико се испред врата појаве свих 9 његових ирваса или 3 од укупно 10 патуљака. Када се Деда Мраз пробуди он ради једну од следећих ствари: Уколико га је пробудила група ирваса одмах се спрема и креће на пут да подели деци играчке. Када се врати са пута свим ирвасима даје награду. Уколико га је пробудила група патуљака онда их он уводи у своју кућу, разговара са њима и на крају их испрати до излазних врата. Група ирваса треба да буде опслужена пре групе патуљака. Користећи CSP написати програме за Деда Мраза, ирвасе и патуљке.
Решење
[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;
];
□
reindeers <> 9 and 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;
];