Изворни код странице КДП/Фебруар 2021

{{tocright}}
Поставка овог рока може се наћи са [https://rti.etf.bg.ac.rs/rti/ir3kdp/rokovi/2021/KDP_2021_feb.pdf странице предмета.]

== {{категорија|1. задатак|Синхронизациони_алгоритми}} ==
=== Поставка ===
Написати и објасните ''test and test and set'' решење за критичну секцију. Уколико би уместо TS(var) постојала операција SWAP која би недељиво обављала замену вредности два операнда (<syntaxhighlight lang="cpp" inline>SWAP(var1, var2) : < temp = var1; var1 = var2; var2 = temp; ></syntaxhighlight>), да ли је могуће направити Fine grain решење и ако је могуће – направите га.

=== Решење ===
У ''Test-and-set'' решењу при свакој провери дељене промењиве се истовремено и уписује у њу а то захтева синхронизацију кеш меморија језгара процесора и значајно окупира магистралу и не дозвољавва другим процесима да је користе. Ради боље перформансе програма потребно је што је могуће више смањити уписе у дељене промењиве. 

''Test and test and set'' решење ради баш то. Прво се процес врти у петљи док је критична секција закључана, па тек онда кад се откључа покуша да добије приступ, а ако није успео опет се врти у петљи док процес који је заузео критичну секцију пре њега не ослободи кључ.

''Fine grain'' решење користећи <syntaxhighlight lang="cpp" inline>SWAP(var1, var2) : < temp = var1; var1 = var2; var2 = temp; ></syntaxhighlight> би могло да се реши на следећи начин:

<syntaxhighlight lang="cpp">
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;  // ослободи браву 
		// некритична секција
	}
}
</syntaxhighlight>

== {{категорија|2. задатак|Штафетна_палица}} ==
{{делимично решено}}
=== Поставка ===
Посматра се семафор за регулацију саобраћаја на улици са једним пешачким прелазом. Када пешак стигне до пешачког прелаза, уколико је светло за пешаке зелено, он прелази улицу. Уколико је у моменту његовог доласка светло за пешаке црвено, он чека да се укључи зелено светло. Зелено светло за пешаке се укључује или након К секунди од појаве првог пешака који је затекао црвено светло, или након проласка C аутомобила од последњег активног зеленог светла за пешаке. Зелено светло за пешаке трајања G секунди се пали само уколико је испуњен неки од наведених услова и барем један пешак чека. Користећи расподељене бинарне семафоре и технику предаје штафетне палице написати програме за пешаке, аутомобиле и семафор за регулацију саобраћаја. Доступна је функција <code>system_time()</code> која враћа тренутно време система. Учесницима треба неко време да пређу улицу.

=== Решење ===

== {{категорија|3. задатак|Филтерски_процеси}} ==
=== Поставка ===
Филтерски процеси имају један улаз и један излаз, и до три локације за примљене бројева. Направите проточну обраду (''pipeline'') од n ових филтерских процеса која сортира па сабира до 2*n улазних реалних бројева које се убацују на почетак проточне обраде, а завршавају се са EOS. На излаз проточне обраде се шаље сума па EOS.

=== Решење ===
Када стигне EOS, уколико су се све остале вредности пропагирале кроз мрежу, ове вредности ће бити сортиране од највеће ка најмањој како се редом буде ишло кроз садржај филтерских процеса. У задатку није специфицирано на који начин треба да се види чињеница да се низ сортира, па је ово узето као претпоставка.
<syntaxhighlight lang="cpp">
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);
}
</syntaxhighlight>

== {{категорија|4. задатак|CSP}} ==
=== Поставка ===
Посматра се једна подземна гаража. Постоји само једна рампа која служи и за улаз, и за излаз из гараже. У гаражи има N места за паркирање. Аутомобили који улазе, могу да уђу, један по један, уколико има слободних места. Уколико слободног места нема, проверава се да ли има аутомобила који хоће да изађу. Ако након изласка свих аутомобила који желе да изађу и уласка аутомобила који су дошли пре њега за аутомобил неће бити места, он одлази у потрагу за другом гаражом. Аутомобили при изласку плаћају услуге гараже и излазе један по један. Аутомобили се опслужују по ФИФО редоследу. Решити задатак користећи CSP.

=== Решење ===
<syntaxhighlight lang="pascal">
[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
    ]
</syntaxhighlight>

[[Категорија:КДП]]
[[Категорија:Рокови]]