KDP/CSP
CSP je oblast distribuiranog programiranja iz trećeg bloka nastave i dolazi na distribuiranom delu ispita za SI i RTI.
Januar 2020, 4. zadatak
- Ovaj zadatak nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.
Postavka
U svemiru postoji N nebeskih tela koja međusobno interaguju (N Body Gravitational Problem), po Njutnovom zakonu gravitacije. Svako telo interaguje sa svakim, pri čemu razmenjuju informacije o poziciji, brzini i vektoru sile. Koristeći CSP potrebno je rešiti ovaj problem koristeći torbu poslova za dohvatanje posla i sinhronizaciju na barijeri u svakoj iteraciji. Potrebno je realizovati sledeće procese: Worker (obavlja izračunavanje), Bag (obavlja podelu posla) i Collector (obavlja prikupljanje rezultata). Broj procesa Worker nije poznat, ali je poznato da ih ima manje od N. Postoji tačno jedan proces Bag i tačno jedan proces Collector.
Rešenje
Januar 2021, 3. zadatak
Postavka
Realizujte coarse grain ticket algoritam za ulazak u kritičnu sekciju koristeći CSP.
Rešenje
Nije jasno na šta se misli pod coarse grain realizacijom u ovom slučaju, ali je ispod jedna moguća implementacija ticket algoritma za ulazak u kritičnu sekciju koristeći CSP.
[ticket::TICKET || user(i: 1..N)::USER]
TICKET::
users: (1..N) integer;
head: integer;
tail: integer;
head := 0;
tail := 0;
*[
head == tail; (i: 1..N) user(i)?enter ->
// Нема никога, па пуштамо овог корисника
user(i)!pass;
tail := (tail + 1) mod N
□
head <> tail; (i: 1..N) user(i)?enter ->
// Додајемо корисника у ред чекања
users(tail) := i;
tail := (tail + 1) mod N
□
(i: 1..N) user(i)?exit ->
head := (head + 1) mod N;
[
// Пуштамо следећег корисника, уколико га има
users(head) <> 0 ->
user(users(head))!pass;
users(head) := 0
]
□
]
USER::
ticket!enter;
ticket?pass;
// У критичној секцији
ticket!exit
Januar 2022, 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;
];
□
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;
];
Januar 2023, 3. zadatak
- Ovaj zadatak nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.
Postavka
Rešiti problem čitalaca i pisaca koristeći CSP. Rešenje treba da obezbedi da kada stigne zahtev od pisca za traženje dozvole za započinjanje pisanja ne treba prihvatati zahteve za započinjanje bilo od čitalaca bilo od pisaca dok taj pisac ne završi sa pisanjem.
Rešenje
Jul 2020, 4. zadatak
- Ovaj zadatak nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.
Postavka
Posmatra se semafor za regulaciju saobraćaja na ulici sa jednim pešačkim prelazom. Kada pešak stigne do pešačkog prelaza, ukoliko je svetlo za pešake zeleno, on prelazi ulicu. Ukoliko je u momentu njegovog dolaska svetlo za pešake crveno, on čeka da se uključi zeleno svetlo. Zeleno svetlo za pešake se uključuje ili nakon K sekundi od pojave prvog pešaka koji je zatekao crveno svetlo, ili nakon prolaska C automobila od poslednjeg aktivnog zelenog svetla za pešake. Zeleno svetlo za pešake trajanja G sekundi se pali samo ukoliko je ispunjen neki od navedenih uslova i barem jedan pešak čeka. Potrebno je u jeziku CSP napisati procese pešaka, automobila i semafora, ukoliko je poznato da u sistemu postoji N automobila i T pešaka. Dostupna je funkcija system_current_time koja vraća trenutno vreme sistema.
Rešenje
Jul 2021, 4. zadatak
Postavka
Postoji N procesa node(i:1..N) koji ili čuvaju elemente liste ili su slobodni. Svaki od njih može da čuva neku vrednost (value) i pokazivač na sledeći element u listi (next). Proces head čuva pokazivač na prvi element u listi. Prilikom brisanja elementa iz liste proces koji ga predstavlja se prebacuje na početak liste slobodnih procesa na koji ukazuje proces free. Proces start inicira brisanje elementa sa zadatom vrednošću iz liste. Realizovati procedure za sve navedene procese koristeći CSP.
Rešenje
[node(num: 1..N)::NODE, head::HEAD, free::FREE, start::START]
NODE::
value: integer;
next: integer;
free: boolean;
free := true;
[
num = N -> next := 0
□
num <> N -> next := num + 1
];
*[
free = false; start?get -> start!value(value, next)
□
free = true; start?get -> start!novalue
□
start?setNext(newNext) -> next := newNext
□
start?erase(newNext) -> free := true
// Акција постављања вредности није имплементирана
// јер није ни тражена у задатку
]
HEAD::
first: integer;
first := 0;
*[
first = 0; start?get -> start!empty
□
first <> 0; start?get -> start!first(first)
□
start?set(value) -> first := value
]
FREE::
free: integer;
free := 1;
*[
free = 0; start?get -> start!full
□
free <> 0; start?get -> start!free(free)
□
start?set(newFree) -> free := newFree
]
START::
// Претпоставимо да је задата вредност 14
value: integer;
value := 14;
prev: integer;
prev := 0;
head!get;
*[
// Вредност не постоји у листи
head?empty -> skip
□
head?first(first) -> node(first)!get
□
// Десила се нека грешка
(i: 1..N) node(i)?novalue -> skip
□
(i: 1..N) node(i)?value(nodeValue, next) -> [
nodeValue = value ->
[
prev = 0 -> head!set(next)
□
prev <> 0 -> node(prev)!setNext(next)
];
node(i)!erase;
free!get;
[
free?full -> node(i)!setNext(0)
□
free?free(nextFree) -> node(i)!setNext(nextFree)
];
free!set(i)
□
nodeValue <> value -> [
// Вредност не постоји у листи
next = 0 -> skip
□
next <> 0 -> node(next)!get
]
]
]
Septembar 2023, 4. zadatak
Postavka
Postoji N pčela i jedan gladan medved (The bear and honeybees). Oni koriste zajedničku košnicu. Košnica je inicijalno prazna i može da primi do N naprstaka meda. Medved spava dok se košnica ne napuni medom, kada se napuni medom meda pojede sav med nakon čega se vraća na spavanje. Pčelice neprestano lete od sveta do sveta i sakupljaju med. Ona pčela koja je popunila košnicu budi medveda. Rešiti problem koristeći CSP.
Rešenje
[Bee(i:1..N)::BEE || Bear::Bear || BeeHive::BeeHive]
BEE:: *[
flyAndCollect();
BeeHive!honneyCollected();
BeeHive?goBackToCollecting();
]
Bear:: * [
sleep();
BeeHive?bearEat();
BeeHive!allIsEaten();
BeeHive?okToSleep();
]
BeeHive:: [
size:integer; size:=0;
N:integer; N:=...;
*[
size < N; Bees(i)?honneyCollected() -> [
size := size + 1;
size==N -> [BeeHive!bearEat();]
[]
size < N -> [Bees(i)!goBackToCollecting();]
]
[]
size == N; BeeHive?allIsEaten() - > [
size = 0;
BeeHive!okToSleep();
]
]
]
Februar 2021, 4. zadatak
Postavka
Posmatra se jedna podzemna garaža. Postoji samo jedna rampa koja služi i za ulaz, i za izlaz iz garaže. U garaži ima N mesta za parkiranje. Automobili koji ulaze, mogu da uđu, jedan po jedan, ukoliko ima slobodnih mesta. Ukoliko slobodnog mesta nema, proverava se da li ima automobila koji hoće da izađu. Ako nakon izlaska svih automobila koji žele da izađu i ulaska automobila koji su došli pre njega za automobil neće biti mesta, on odlazi u potragu za drugom garažom. Automobili pri izlasku plaćaju usluge garaže i izlaze jedan po jedan. Automobili se opslužuju po FIFO redosledu. Rešiti zadatak koristeći CSP.
Rešenje
[ramp::RAMP, car(i: 0..2*N+1)::CAR]
RAMP::
entering: integer;
exiting: integer;
parked: integer;
// Ово је измишљена синтакса за низ структура
enterQueue: (0..N) (carId, ticket: integer);
exitQueue: (0..N) (carId, ticket: integer);
enterHead: integer;
exitHead: integer;
enterTail: integer;
exitTail: integer;
ticket := integer;
entering := 0;
exiting := 0;
parked := 0;
enterHead := 0;
exitHead := 0;
enterTail := 0;
exitTail := 0;
ticket := 0;
*[
parked - exiting + entering >= N; (i: 0..2*N+1) car(i)?enter -> car(i)!full
□
parked - exiting + entering < N; (i: 0..2*N+1) car(i)?enter ->
entering := entering + 1;
[
entering = 1; exiting = 0; parked < N -> car(i)!pass
□
entering > 1 or exiting > 0 or parked = N ->
// Ово је измишљена синтакса за убацивање структуре у низ
enterQueue(enterTail) := (i, ticket);
ticket := ticket + 1;
enterTail := (enterTail + 1) mod N
]
□
(i: 0..2*N+1) car(i)?entered ->
entering := entering - 1;
parked := parked + 1;
[
// Ово је измишљена синтакса за приступање пољу структуре
entering > 0; parked + exiting < N; enterQueue(enterHead).ticket > exitQueue(exitHead).ticket ->
car(enterQueue(enterHead).carId)!pass;
enterHead := (enterHead + 1) mod N
□
exiting > 0; parked + exiting = N or enterQueue(enterHead).ticket < exitQueue(exitHead).ticket ->
car(exitQueue(exitHead).carId)!pass;
exitHead := (exitHead + 1) mod N
]
□
(i: 0..2*N+1) car(i)?exit ->
exiting := exiting + 1;
parked := parked - 1;
[
exiting = 1; entering = 0 -> car(i)!pass
□
exiting > 1 or entering > 0 ->
// Ово је измишљена синтакса за убацивање структуре у низ
exitQueue(exitTail) := (i, ticket);
ticket := ticket + 1;
exitTail := (exitTail + 1) mod N
]
□
(i: 0..2*N+1) car(i)?exited ->
exiting := exiting - 1;
[
// Ово је измишљена синтакса за приступање пољу структуре
entering > 0; parked + exiting < N; enterQueue(enterHead).ticket > exitQueue(exitHead).ticket ->
car(enterQueue(enterHead).carId)!pass;
enterHead := (enterHead + 1) mod N
□
exiting > 0; parked + exiting = N or enterQueue(enterHead).ticket < exitQueue(exitHead).ticket ->
car(exitQueue(exitHead).carId)!pass;
exitHead := (exitHead + 1) mod N
]
]
CAR::
ramp!enter;
[
// Тражимо другу гаражу
ramp?full -> skip
□
ramp?pass ->
// Пролазимо кроз рампу
ramp!entered;
// Паркирани смо
ramp!exit;
ramp?pass;
// Пролазимо кроз рампу
ramp!exited
]
Februar 2022, 4. zadatak
Postavka
Automobili koji dolaze sa severa i juga moraju da pređu reku preko mosta (One lane bridge problem). Na mostu, na žalost, postoji samo jedna vozna traka. Znači, u bilo kom trenutku mostom može da prođe jedan ili više automobila koji dolaze iz istog smera (ali ne i iz suprotnog smera). Koristeći CSP napisati program koji rešava dati problem. Sprečiti izgladnjivanje.
Rešenje
[Bridge::BRIDGE, Car(0..N)::CAR]
BRIDGE::[
waiting: (0..2) (0..N) integer;
waitingNum: (0..2) integer := 0;
// 0 - нико, 1 - лево, 2 - десно
priority: integer := 0;
// 1 - лева страна, 2 - десна страна
currentCrossing := 0;
current: integer := 0;
*[
; (i: 0..N) Car(i)?request(side) -> [
currentCrossing = side and priority = side; -> [
// Тренутно пролази наша страна и нико није дошао са друге
current := current + 1;
Car(i)!pass;
];
□
currentCrossing = side and priority <> side; -> [
// Тренутно пролази наша страна али је неко дошао са друге
waiting(side-1, waitingNum(side-1)) := i;
waitingNum(side-1) := waitingNum(side-1) + 1;
];
□
currentCrossing <> side; -> [
// Тренутно не пролази наша страна, зауставити их како би се спречило изгладњивање
priority := side;
waiting(side-1, waitingNum(side-1)) := i;
waitingNum(side-1) := waitingNum(side-1) + 1;
];
];
□
; (i: 0..N) Car(i)?passed -> [
current := current - 1;
[
current = 0 and priority <> currentCrossing; -> [
// Нема више аутомобила који пролазе мостом али има оних који следећи имају приоритет
[
waitingNum(currentCrossing-1) == 0; -> [
// Уколико има аутомобила са стране која је досад пролазила, промени приоритет
// тако да они са друге стране који дођу после овога не могу да прођу
priority = (3 - priority);
];
];
// Промени страну која пролази и притом пусти све са друге стране
currentCrossing := (3 - currentCrossing);
(j: 0..waitingNum) Car(waiting(j, currentCrossing-1))!pass;
waitingNum := 0;
];
];
];
];
];
CAR::[
Bridge!request(side);
Bridge?pass;
// Пролазимо
Bridge!passed;
];
Februar 2023, 4. zadatak
Postavka
Na jednoj obali reke se nalazi čamac koji prevozi putnike sa jedne na drugu obalu i koji može da primi tačno deset putnika. Čamac mogu da koriste muškarci, žene i deca. Čamac može da isplovi samo ako se u njemu nalazi tačno onoliko putnika koliki mu je kapacitet, ali samo pod uslovom da se u čamcu nalaze bar dva muškarca. Deca ne smeju ući u čamac ukoliko se u njemu ne nalaze bar jedna odrasla osoba i po završetku vožnje u čamcu ne smeju da ostanu samo deca. Smatrati da će se čamac nakon iskrcavanja svih putnika odmah biti spreman da primi narednu grupu putnika. Koristeći CSP napisati program koji rešava ovaj problem.
Rešenje
Vodio sam se rešenjem istog zadatka koji je bio u delu sa regionima. Jedino za šta nisam siguran je da li treba da se šalju poruke deci ukoliko su se odrasli ukrcali i odraslima ukoliko su se deca iskrcala zbog toga što se to proverava u zaštitnim uslovima.
[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
]
]
]
Februar 2024, 4. zadatak
Postavka
Posmatra se špil od 24 karte, podeljene u 4 boje, sa po 6 različitih brojeva. Igru igraju 4 igrača, koja sede za okruglim stolom i svaki od njih inicijalno drži po 4 karte. Između sva susedna igrača se nalazi gomila sa kartama, koja može u nekom trenutku biti prazna, a inicijalno sadrži 2 karte. Igra se završava kada bar jedan igrač objavi da ima sve 4 karte istog broja, u različitim bojama, o tada svi igrači prekidaju igru. Svaki igrač, dok god nema 4 karte iste i niko nije objavio da je pobednik, izbacuje jednu kartu iz svoje ruke i stavlja je na gomilu sa svoje leve strane, potom uzima jednu kartu sa vrha iz gomile sa svoje desne strane. Pretpostaviti da su igračima inicijalno podeljene karte na slučajan način. Koristeći CSP napisati programe za igrače i gomile sa kartama.