КДП/Фебруар 2021
Поставка овог рока може се наћи са странице предмета.
1. задатак
Поставка
Написати и објасните test and test and set решење за критичну секцију. Уколико би уместо TS(var) постојала операција SWAP која би недељиво обављала замену вредности два операнда (SWAP(var1, var2) : < temp = var1; var1 = var2; var2 = temp; >), да ли је могуће направити Fine grain решење и ако је могуће – направите га.
Решење
У Test-and-set решењу при свакој провери дељене промењиве се истовремено и уписује у њу а то захтева синхронизацију кеш меморија језгара процесора и значајно окупира магистралу и не дозвољавва другим процесима да је користе. Ради боље перформансе програма потребно је што је могуће више смањити уписе у дељене промењиве.
Test and test and set решење ради баш то. Прво се процес црти у петљи док је критична секција закључана, па тек онда кад се откључа покуша да добије приступ, а ако није успео опет се врти у петљи док процес који је заузео критичну секцију пре њега не ослободи кључ.
Fine grain решење користећи SWAP(var1, var2) : < temp = var1; var1 = var2; var2 = temp; > би могло да се реши на следећи начин:
bool lock = false;
void process(int id) {
bool initialLock = true; // У lock треба да се недељиво упише true, а ако је брава ослобођена у initialLock ће се уписати false након замене а ко није ослобођена остаће иста вредност
while (true) {
while (lock == true) skip; // врти се lock true, тј. док је брава заузета
SWAP(lock, initialLock) //замени вредност браве и initialLock;
while (initialLock == true) {
while (lock == true) skip; // врти се поново ако ниси успео, tj. ако је неко други заузео критичну секцију
}
// критична секција
lock = false; // ослободи браву
// некритична секција
}
}
2. задатак
- Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.
Поставка
Посматра се семафор за регулацију саобраћаја на улици са једним пешачким прелазом. Када пешак стигне до пешачког прелаза, уколико је светло за пешаке зелено, он прелази улицу. Уколико је у моменту његовог доласка светло за пешаке црвено, он чека да се укључи зелено светло. Зелено светло за пешаке се укључује или након К секунди од појаве првог пешака који је затекао црвено светло, или након проласка C аутомобила од последњег активног зеленог светла за пешаке. Зелено светло за пешаке трајања G секунди се пали само уколико је испуњен неки од наведених услова и барем један пешак чека. Користећи расподељене бинарне семафоре и технику предаје штафетне палице написати програме за пешаке, аутомобиле и семафор за регулацију саобраћаја. Доступна је функција system_time() која враћа тренутно време система. Учесницима треба неко време да пређу улицу.
Решење
3. задатак
Поставка
Филтерски процеси имају један улаз и један излаз, и до три локације за примљене бројева. Направите проточну обраду (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
]