КДП/Фебруар 2021
Поставка овог рока може се наћи са странице предмета.
1. задатак
- Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.
Поставка
Написати и објасните test and test and set решење за критичну секцију. Уколико би уместо TS(var) постојала операција SWAP која би недељиво обављала замену вредности два операнда (SWAP(var1, var2) : < temp = var1; var1 = var2; var2 = temp; >), да ли је могуће направити Fine grain решење и ако је могуће – направите га.
Решење
2. задатак
- Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.
Поставка
Посматра се семафор за регулацију саобраћаја на улици са једним пешачким прелазом. Када пешак стигне до пешачког прелаза, уколико је светло за пешаке зелено, он прелази улицу. Уколико је у моменту његовог доласка светло за пешаке црвено, он чека да се укључи зелено светло. Зелено светло за пешаке се укључује или након К секунди од појаве првог пешака који је затекао црвено светло, или након проласка C аутомобила од последњег активног зеленог светла за пешаке. Зелено светло за пешаке трајања G секунди се пали само уколико је испуњен неки од наведених услова и барем један пешак чека. Користећи расподељене бинарне семафоре и технику предаје штафетне палице написати програме за пешаке, аутомобиле и семафор за регулацију саобраћаја. Доступна је функција system_time() која враћа тренутно време система. Учесницима треба неко време да пређу улицу.
Решење
3. задатак
- Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.
Поставка
Филтерски процеси имају један улаз и један излаз, и до три локације за примљене бројева. Направите проточну обраду (pipeline) од n ових филтерских процеса која сортира па сабира до 2*n улазних реалних бројева које се убацују на почетак проточне обраде, а завршавају се са EOS. На излаз проточне обраде се шаље сума па EOS.
Решење
Када стигне EOS, уколико су се све остале вредности пропагирале кроз мрежу, ове вредности ће бити сортиране од највеће ка најмањој како се редом буде ишло кроз садржај филтерских процеса. У задатку није специфицирано на који начин треба да се види чињеница да се низ сортира, па је ово узето као претпоставка.
void process() {
chan<int> in;
chan<int> out;
int numReceived = 0;
int input;
int mem[2];
while ((input = in.receive()) != EOS) {
if (numReceived < 2) {
mem[numReceived++] = input;
} else {
if (input <= mem[0] && input <= mem[1]) {
out.send(input);
} else if (mem[0] <= input && mem[0] <= mem[1]) {
out.send(mem[0]);
mem[0] = input;
} else {
out.send(mem[1]);
mem[1] = input;
}
}
}
out.send(mem[0] + mem[1]);
out.send(EOS);
}
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
]