KDP/Februar 2021

Postavka ovog roka može se naći sa stranice predmeta.

1. zadatak

Postavka

Napisati i objasnite test and test and set rešenje za kritičnu sekciju. Ukoliko bi umesto TS(var) postojala operacija SWAP koja bi nedeljivo obavljala zamenu vrednosti dva operanda (SWAP(var1, var2) : < temp = var1; var1 = var2; var2 = temp; >), da li je moguće napraviti Fine grain rešenje i ako je moguće – napravite ga.

Rešenje

U Test-and-set rešenju pri svakoj proveri deljene promenjive se istovremeno i upisuje u nju a to zahteva sinhronizaciju keš memorija jezgara procesora i značajno okupira magistralu i ne dozvoljavva drugim procesima da je koriste. Radi bolje performanse programa potrebno je što je moguće više smanjiti upise u deljene promenjive.

Test and test and set rešenje radi baš to. Prvo se proces vrti u petlji dok je kritična sekcija zaključana, pa tek onda kad se otključa pokuša da dobije pristup, a ako nije uspeo opet se vrti u petlji dok proces koji je zauzeo kritičnu sekciju pre njega ne oslobodi ključ.

Fine grain rešenje koristeći SWAP(var1, var2) : < temp = var1; var1 = var2; var2 = temp; > bi moglo da se reši na sledeći način:

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. 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. Koristeći raspodeljene binarne semafore i tehniku predaje štafetne palice napisati programe za pešake, automobile i semafor za regulaciju saobraćaja. Dostupna je funkcija system_time() koja vraća trenutno vreme sistema. Učesnicima treba neko vreme da pređu ulicu.

3. zadatak

Postavka

Filterski procesi imaju jedan ulaz i jedan izlaz, i do tri lokacije za primljene brojeva. Napravite protočnu obradu (pipeline) od n ovih filterskih procesa koja sortira pa sabira do 2*n ulaznih realnih brojeva koje se ubacuju na početak protočne obrade, a završavaju se sa EOS. Na izlaz protočne obrade se šalje suma pa EOS.

Rešenje

Kada stigne EOS, ukoliko su se sve ostale vrednosti propagirale kroz mrežu, ove vrednosti će biti sortirane od najveće ka najmanjoj kako se redom bude išlo kroz sadržaj filterskih procesa. U zadatku nije specificirano na koji način treba da se vidi činjenica da se niz sortira, pa je ovo uzeto kao pretpostavka.

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. 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
    ]