КДП/CSP
CSP је област дистрибуираног програмирања из трећег блока наставе и долази на дистрибуираном делу испита за СИ и РТИ.
Јануар 2020, 4. задатак
- Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.
Поставка
У свемиру постоји N небеских тела која међусобно интерагују (N Body Gravitational Problem), по Њутновом закону гравитације. Свако тело интерагује са сваким, при чему размењују информације о позицији, брзини и вектору силе. Користећи CSP потребно је решити овај проблем користећи торбу послова за дохватање посла и синхронизацију на баријери у свакој итерацији. Потребно је реализовати следеће процесе: Worker (обавља израчунавање), Bag (обавља поделу посла) и Collector (обавља прикупљање резултата). Број процеса Worker није познат, али је познато да их има мање од N. Постоји тачно један процес Bag и тачно један процес Collector.
Решење
Јануар 2021, 3. задатак
Поставка
Реализујте coarse grain ticket алгоритам за улазак у критичну секцију користећи CSP.
Решење
Није јасно на шта се мисли под coarse grain реализацијом у овом случају, али је испод једна могућа имплементација ticket алгоритма за улазак у критичну секцију користећи 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
Јануар 2022, 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;
];
Јануар 2023, 3. задатак
- Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.
Поставка
Решити проблем читалаца и писаца користећи CSP. Решење треба да обезбеди да када стигне захтев од писца за тражење дозволе за започињање писања не треба прихватати захтеве за започињање било од читалаца било од писаца док тај писац не заврши са писањем.
Решење
Јул 2020, 4. задатак
- Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.
Поставка
Посматра се семафор за регулацију саобраћаја на улици са једним пешачким прелазом. Када пешак стигне до пешачког прелаза, уколико је светло за пешаке зелено, он прелази улицу. Уколико је у моменту његовог доласка светло за пешаке црвено, он чека да се укључи зелено светло. Зелено светло за пешаке се укључује или након К секунди од појаве првог пешака који је затекао црвено светло, или након проласка C аутомобила од последњег активног зеленог светла за пешаке. Зелено светло за пешаке трајања G секунди се пали само уколико је испуњен неки од наведених услова и барем један пешак чека. Потребно је у језику CSP написати процесе пешака, аутомобила и семафора, уколико је познато да у систему постоји N аутомобила и T пешака. Доступна је функција system_current_time која враћа тренутно време система.
Решење
Јул 2021, 4. задатак
Поставка
Постоји N процеса node(i:1..N) који или чувају елементе листе или су слободни. Сваки од њих може да чува неку вредност (value) и показивач на следећи елемент у листи (next). Процес head чува показивач на први елемент у листи. Приликом брисања елемента из листе процес који га представља се пребацује на почетак листе слободних процеса на који указује процес free. Процес start иницира брисање елемента са задатом вредношћу из листе. Реализовати процедуре за све наведене процесе користећи CSP.
Решење
[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
]
]
]
Септембар 2023, 4. задатак
Поставка
Постоји N пчела и један гладан медвед (The bear and honeybees). Они користе заједничку кошницу. Кошница је иницијално празна и може да прими до N напрстака меда. Медвед спава док се кошница не напуни медом, када се напуни медом меда поједе сав мед након чега се враћа на спавање. Пчелице непрестано лете од света до света и сакупљају мед. Она пчела која је попунила кошницу буди медведа. Решити проблем користећи CSP.
Решење
[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();
]
]
]
Фебруар 2021, 4. задатак
Поставка
Посматра се једна подземна гаража. Постоји само једна рампа која служи и за улаз, и за излаз из гараже. У гаражи има N места за паркирање. Аутомобили који улазе, могу да уђу, један по један, уколико има слободних места. Уколико слободног места нема, проверава се да ли има аутомобила који хоће да изађу. Ако након изласка свих аутомобила који желе да изађу и уласка аутомобила који су дошли пре њега за аутомобил неће бити места, он одлази у потрагу за другом гаражом. Аутомобили при изласку плаћају услуге гараже и излазе један по један. Аутомобили се опслужују по ФИФО редоследу. Решити задатак користећи CSP.
Решење
[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
]
Фебруар 2022, 4. задатак
Поставка
Аутомобили који долазе са севера и југа морају да пређу реку преко моста (One lane bridge problem). На мосту, на жалост, постоји само једна возна трака. Значи, у било ком тренутку мостом може да прође један или више аутомобила који долазе из истог смера (али не и из супротног смера). Користећи CSP написати програм који решава дати проблем. Спречити изгладњивање.
Решење
[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;
];
Фебруар 2023, 4. задатак
Поставка
На једној обали реке се налази чамац који превози путнике са једне на другу обалу и који може да прими тачно десет путника. Чамац могу да користе мушкарци, жене и деца. Чамац може да исплови само ако се у њему налази тачно онолико путника колики му је капацитет, али само под условом да се у чамцу налазе бар два мушкарца. Деца не смеју ући у чамац уколико се у њему не налазе бар једна одрасла особа и по завршетку вожње у чамцу не смеју да остану само деца. Сматрати да ће се чамац након искрцавања свих путника одмах бити спреман да прими наредну групу путника. Користећи 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
]
]
]
Фебруар 2024, 4. задатак
Поставка
Посматра се шпил од 24 карте, подељене у 4 боје, са по 6 различитих бројева. Игру играју 4 играча, која седе за округлим столом и сваки од њих иницијално држи по 4 карте. Између сва суседна играча се налази гомила са картама, која може у неком тренутку бити празна, а иницијално садржи 2 карте. Игра се завршава када бар један играч објави да има све 4 карте истог броја, у различитим бојама, о тада сви играчи прекидају игру. Сваки играч, док год нема 4 карте исте и нико није објавио да је победник, избацује једну карту из своје руке и ставља је на гомилу са своје леве стране, потом узима једну карту са врха из гомиле са своје десне стране. Претпоставити да су играчима иницијално подељене карте на случајан начин. Користећи CSP написати програме за играче и гомиле са картама.