KDP/Septembar 2023

1. zadatak

Postavka

Napisati i objasniti CLH algoritam za kritičnu sekciju (coarse grain). Realizovati (fine grain) verziju algoritma ukoliko bi na datom procesoru postojala operacija SWAP koja bi nedeljivo obavljala zamenu verdnosti dva operanda (SWAP(var1, var2): <temp=var1; var1=var2; var2=temp;>). Objasniti zašto je to pravična kritična sekcija.

Rešenje

CLH algoritam procese ulančava u ulančanu listu po redosledu kojim dolaze. Samim tim ta lista se ponaša kao red i time je ovaj algoritam pravičan jer koristi FIFO princip. Coarse-grain rešenje:

struct Node {
    bool locked;
    Node() {
        locked = true;
    }
};

Node* tail = nullptr;

void process() {
    while (true) {
        Node* new_node = new Node();
        Node* prev;
        < prev = tail; tail = new_node; >
        < await(tail == nullptr || !prev->locked); >
        /* критична секција */
        new_node->locked=false;
        /* некритична секција */
    }
}

Fine-grain rešenje: Pošto su prev i new_node lokalni pokazivači, možemo da ih usmerimo na novokreirani čvor. Zatim se nedeljivo poziva funkcija SWAP koja će nedeljivo zameniti vrednost prev i tail pokazivača.

struct Node {
    bool locked;
    Node() {
        locked = true;
    }
};

Node* tail = nullptr;

void process() {
    while (true) {
        Node* new_node = new Node();
        Node* prev = new_node;
        SWAP(prev, tail);
        while(prev!= nullptr && prev->locked) skip();
        /* критична секција */
        new_node->locked=false;
        /* некритична секција */
    }
}

2. zadatak

Postavka

Trajekt za prevoz automobila, kamiona i autobusa prevozi vozila sa obale na obalu. Trajekt poseduje N pozicija koje su linearlno postavljene jedna iza druge. Kamiona zauzima tri, autovus dve a automobil jednu poziciju. Vozila čekaju na trajekt u redu i na njega ulaze jedno po jedno po redosledu u kom čekaju u redu, dok na trajektu ima mesta. Kada nema mesta da se naredno vozilo u redu ukrca i trajekt nije u potpunosti popunjen, preko reda se ukrcavaju manja vozila dok se trajekt ne popuni u potpunosti. Kada je kompletno pun, trajekt započinje prevoz vozila na drugu obalu. Na drugoj obali vozila se iskrcavaju u redosledu suprotnom od onog u kojem su se ukrcala. Kada se sva vozila iskrcaju, prazan trajekt se vraća na početnu obalu. Napisati monitor sa signal and wait disciplinom koji rešava dati problem.

Rešenje

Ovaj zadatak nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.

3. zadatak

Postavka

Filterski procesi imaju jedan ulaz i jedan izlaz i rade sledeće: primaju pozitivne vrednosti na ulazu i prosleđuju ih na izlaz ako su veće od zapamćenog minimuma procesa. Procesi imaju samo dve lokacije, za sačuvani minimum i za poslednju primljenu vrednost. Kada na ulaz stigne EOS, izbacuju minimalnu vrednost na izlaz a zatim EOS. Napravite protočnu obradu (pipeline) od n procesa koji opadajuće soritaju do n ulaznih pozitivnih vrednosti koje se ubacuju na početak protočne obrade a završavaju se sa EOS.

Rešenje

void process() {
    chan<int> in;
    chan<int> out;
    int input;
    int min;
    while ((input = in.receive()) != EOS) {
        if (input < min) {
            out.send(min);
            min = input;
        } else out.send(input);
    out.send(min);    
    out.send(EOS);
}

4. zadatak

Postavka

Postoji N pčela i jedan gladan medved (The bear and honeybees). Oni koriste zajedničku košnicu. Košnica je inicijalno prazna i može da primi do N naprstaka meda. Medved spava dok se košnica ne napuni medom, kada se napuni medom meda pojede sav med nakon čega se vraća na spavanje. Pčelice neprestano lete od sveta do sveta i sakupljaju med. Ona pčela koja je popunila košnicu budi medveda. Rešiti problem koristeći CSP.

Rešenje

[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();
		]
	
	]
]