КДП/Септембар 2023

1. задатак

Поставка

Написати и објаснити CLH алгоритам за критичну секцију (coarse grain). Реализовати (fine grain) верзију алгоритма уколико би на датом процесору постојала операција SWAP која би недељиво обављала замену вердности два операнда (SWAP(var1, var2): <temp=var1; var1=var2; var2=temp;>). Објаснити зашто је то правична критична секција.

Решење

CLH алгоритам процесе уланчава у уланчану листу по редоследу којим долазе. Самим тим та листа се понаша као ред и тиме је овај алгоритам правичан јер користи FIFO принцип. Coarse-grain решење:

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 решење: Пошто су prev и new_node локални показивачи, можемо да их усмеримо на новокреирани чвор. Затим се недељиво позива функција SWAP која ће недељиво заменити вредност prev и tail показивача.

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. задатак

Поставка

Трајект за превоз аутомобила, камиона и аутобуса превози возила са обале на обалу. Трајект поседује N позиција које су линеарлно постављене једна иза друге. Камиона заузима три, аутовус две а аутомобил једну позицију. Возила чекају на трајект у реду и на њега улазе једно по једно по редоследу у ком чекају у реду, док на трајекту има места. Када нема места да се наредно возило у реду укрца и трајект није у потпуности попуњен, преко реда се укрцавају мања возила док се трајект не попуни у потпуности. Када је комплетно пун, трајект започиње превоз возила на другу обалу. На другој обали возила се искрцавају у редоследу супротном од оног у којем су се укрцала. Када се сва возила искрцају, празан трајект се враћа на почетну обалу. Написати монитор са signal and wait дисциплином који решава дати проблем.

Решење

Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.

3. задатак

Поставка

Филтерски процеси имају један улаз и један излаз и раде следеће: примају позитивне вредности на улазу и прослеђују их на излаз ако су веће од запамћеног минимума процеса. Процеси имају само две локације, за сачувани минимум и за последњу примљену вредност. Када на улаз стигне EOS, избацују минималну вредност на излаз а затим EOS. Направите проточну обраду (pipeline) од n процеса који опадајуће соритају до n улазних позитивних вредности које се убацују на почетак проточне обраде а завршавају се са EOS.

Решење

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. задатак

Поставка

Постоји N пчела и један гладан медвед (The bear and honeybees). Они користе заједничку кошницу. Кошница је иницијално празна и може да прими до N напрстака меда. Медвед спава док се кошница не напуни медом, када се напуни медом меда поједе сав мед након чега се враћа на спавање. Пчелице непрестано лете од света до света и сакупљају мед. Она пчела која је попунила кошницу буди медведа. Решити проблем користећи CSP.

Решење

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