КДП/Фебруар 2023
Поставка овог рока може се наћи са странице предмета.
1. задатак
Поставка
Fine grain Ticket алгоритам реализован помоћу addAndGet операције. Уколико би addAndGet операција имала следећи ефекат: addAndGet(var, incr) : < var = var + incr; return(var);, да ли је могуће направити Fine grain решење, полазећи од Coarse grain решења, и ако је могуће - направите га. Написати и Coarse grain решење.
Решење
Coarse-grain решење:
int ticket = 0;
int next = 0;
void process() {
while (true) {
int myTicket=0;
< myTicket=ticket++; >
< await(myTicket==next); >
/* критична секција */
next++;
/* некритична секција */
}
}
Fine-grain решење:
int ticket = 0;
int next = 0;
void process() {
while (true) {
int myTicket=0;
myTicket = addAndGet(ticket, 1) - 1;
while(myTicket != next) skip();
/* критична секција */
next++;
/* некритична секција */
}
}
2. задатак
- Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.
Поставка
Племе људождера једе заједничку вечеру из казана који може да прими M порција куваних мисионара (The Dining Savages Problem). Када људождер пожели да руча онда се он сам послужи из заједничког казана, уколико казан није празан. Уколико је казан празан људождер буди кувара и сачека док кувар не напуни казан и онда узима своју порцију, а тек након тога преостали могу јести. Није дозвољено будити кувара уколико се налази бар мало хране у казану. Написати монитор са signal and continue дисциплином који решава дати проблем.
Решење
3. задатак
Поставка
Користећи активне мониторе решити проблем филозофа који ручавају (The Dining Philosophers). Филозофи могу да комуницирају искључиво са процесом координатором (централизовано решење). Обезбедити да филозоф који је пре затражио да једе пре и започиње са јелом. Написати код за филозофе и за процес координатор.
Решење
- Исти задатак дошао је у јулу 2020. године. Ипак, аутор је одлучио да постави своје решење које је добило максималан број бодова.
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)
}
}
4. задатак
- Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.
Поставка
На једној обали реке се налази чамац који превози путнике са једне на другу обалу и који може да прими тачно десет путника. Чамац могу да користе мушкарци, жене и деца. Чамац може да исплови само ако се у њему налази тачно онолико путника колики му је капацитет, али само под условом да се у чамцу налазе бар два мушкарца. Деца не смеју ући у чамац уколико се у њему не налазе бар једна одрасла особа и по завршетку вожње у чамцу не смеју да остану само деца. Сматрати да ће се чамац након искрцавања свих путника одмах бити спреман да прими наредну групу путника. Користећи CSP написати програм који решава овај проблем.
Решење
Водио сам се решењем истог задатка који је био у делу са регионима. Једино за шта нисам сигуран је да ли треба да се шаљу поруке деци уколико су се одрасли укрцали и одраслима уколико су се деца искрцала због тога што се то проверава у заштитним условима.
[Man(i:1..N)::MAN || Woman(i:1..N)::WOMAN || Child(i:1..N)::CHILD || Boat::BOAT]
BOAT::
[
capacity:integer; capacity:=0;
boarding:integer; boarding:=1;
onBoard:integer; onBoard:=0;
onBoardMen:integer; onBoardMen:=0;
onBoardWomen:integer; onBoardWomen:=0;
onBoardChildren:integer; onBoardChildren:=0;
*[
boarding==1 ->
[
onBoard == capacity, Man(i:1..N) Man(i)?enter -> Man(i)!boatFull;
[]
onBoard < capacity; Man(i:1..N) Man(i)?enter ->
[
onBoard:=onBoard+1;
onBoardMen:=onBoardMen+1;
Man(i)!boarded;
onBoard==capacity -> boarding:=0;
]
[]
onBoard == capacity, Woman(i:1..N) Woman(i)?enter -> Woman(i)!boatFull;
[]
onBoard < capacity and onBoard-onBoardMen <= 7, Woman(i:1..N) Woman(i)?enter ->
[
onBoard:=onBoard+1;
onBoardWomen:=onBoardWomen+1;
Woman(i)!boarded;
onBoard==capacity -> boarding:=0;
]
[]
onBoard == capacity, Child(i:1..N) Child(i)?enter -> Child(i)!boatFull;
[]
onBoard == 0, Child(i:1..N) Child(i)?enter -> Child(i)!waitForAdult;
[]
onBoard-onBoardMen <= 7, Child(i:1..N) Child(i)?enter ->
[
onBoard:=onBoard+1;
onBoardChildren:=onBoardChildren+1;
Child(i)!boarded;
onBoard==capacity -> boarding:=0;
]
]
[]
boarding==0 ->
[
onBoardMen+onBoardWomen==1 and onBoardChildren > 0, Man(i)?exit -> Man(i)!waitForChildrenToExit;
[]
(onBoardMen+onBoardWomen>1 and onBoardChildren > 0) or onBoardChildren==0, Man(i)?exit ->
[
onBoard:=onBoard-1;
onBoardMen:=onBoardMen-1;
Man(i)!exited;
onBoard == 0 -> boarding:=1;
]
[]
onBoardMen+onBoardWomen==1 and onBoardChildren > 0, Woman(i)?exit -> Woman(i)!waitForChildrenToExit;
[]
(onBoardMen+onBoardWomen>1 and onBoardChildren > 0) or onBoardChildren==0, Woman(i)?exit ->
[
onBoard:=onBoard-1;
onBoardWomen:=onBoardWomen-1;
Woman(i)!exited;
onBoard == 0 -> boarding:=1;
]
[]
Child(i)?exit ->
[
onBoard:=onBoard - 1;
onBoardChildren:= onBoardChildren -1;
Child!exited;
]
]
]
]
MAN::
[
Man!enter;
[
Man?boatFull -> waitForReturnTrip;
[]
Man?boarded ->
[
Man!exit;
[
Man?waitForChildrenToExit -> wait;
[]
Man(i)?exited; //iskrcao se muskarac
]
]
]
]
WOMAN::
[
Woman!enter;
[
Woman?boatFull -> waitForReturnTrip;
[]
Woman?boarded ->
[
Woman!exit;
[
Woman?waitForChildrenToExit -> wait;
[]
Woman(i)?exited; //iskrcala se zena
]
]
]
]
CHILD::
[
Child!enter;
[
Child?boatFull -> waitForReturnTrip;
[]
Child?waitForAdult -> wait;
[]
Child?boarded ->
[
Child!exit;
Child?exited; //iskrcalo se dete
]
]
]