KDP/Februar 2023

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

1. zadatak

Postavka

Fine grain Ticket algoritam realizovan pomoću addAndGet operacije. Ukoliko bi addAndGet operacija imala sledeći efekat: addAndGet(var, incr) : < var = var + incr; return(var);, da li je moguće napraviti Fine grain rešenje, polazeći od Coarse grain rešenja, i ako je moguće - napravite ga. Napisati i Coarse grain rešenje.

Rešenje

Coarse-grain rešenje:

int ticket = 0;
int next = 0;

void process() {
    while (true) {
        int myTicket=0;
        < myTicket=ticket++; >
        < await(myTicket==next); >
        /* критична секција */
        next++;
        /* некритична секција */
    }
}

Fine-grain rešenje:

int ticket = 0;
int next = 0;

void process() {
    while (true) {
        int myTicket=0;
        myTicket = addAndGet(ticket, 1) - 1;
        while(myTicket != next) skip();
        /* критична секција */
        next++;
        /* некритична секција */
    }
}

2. zadatak

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

Postavka

Pleme ljudoždera jede zajedničku večeru iz kazana koji može da primi M porcija kuvanih misionara (The Dining Savages Problem). Kada ljudožder poželi da ruča onda se on sam posluži iz zajedničkog kazana, ukoliko kazan nije prazan. Ukoliko je kazan prazan ljudožder budi kuvara i sačeka dok kuvar ne napuni kazan i onda uzima svoju porciju, a tek nakon toga preostali mogu jesti. Nije dozvoljeno buditi kuvara ukoliko se nalazi bar malo hrane u kazanu. Napisati monitor sa signal and continue disciplinom koji rešava dati problem.

3. zadatak

Postavka

Koristeći aktivne monitore rešiti problem filozofa koji ručavaju (The Dining Philosophers). Filozofi mogu da komuniciraju isključivo sa procesom koordinatorom (centralizovano rešenje). Obezbediti da filozof koji je pre zatražio da jede pre i započinje sa jelom. Napisati kod za filozofe i za proces koordinator.

Rešenje

Isti zadatak došao je u julu 2020. godine. Ipak, autor je odlučio da postavi svoje rešenje koje je dobilo maksimalan broj bodova.

const int N = ...;
enum op_kind{REQUEST,RELEASE};
chan request(int, op_kind);
chan reply[N](bool);

class Coordinator {
public:
    void run() {
        int id;
        op_kind op;
        queue<int> waiting;
        int forks[N] = {true};
        while (true) {
            receive request(id, op);
            int left = id, right = (id + 1) % N;
            if (op == REQUEST) {
                if (forks[left] && forks[right]) {
                    forks[left] = forks[right] = false;
                    send reply[id](OK);
                } else {
                    waiting.push(id);
                }
            } else if (op == RELEASE) {
                forks[left] = forks[right] = true;
                send reply[id](OK);
                while (!waiting.empty()) {
                    id = waiting.top();
                    left = id, right = (id + 1) % N;
                    if (forks[left] && forks[right]) {
                        forks[left] = forks[right] = false;
                        waiting.pop();
                        send reply[id](OK);
                    } else break;
                }
            }
        }
    }
}

void philosopher(int id) {
    bool status;
    while (true) {
        // Think
        send request(id, REQUEST);
        receive reply[id](status);
        // Eat
        send request(id, RELEASE);
        receive reply[id](status)
    }
}

4. zadatak

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

Postavka

Na jednoj obali reke se nalazi čamac koji prevozi putnike sa jedne na drugu obalu i koji može da primi tačno deset putnika. Čamac mogu da koriste muškarci, žene i deca. Čamac može da isplovi samo ako se u njemu nalazi tačno onoliko putnika koliki mu je kapacitet, ali samo pod uslovom da se u čamcu nalaze bar dva muškarca. Deca ne smeju ući u čamac ukoliko se u njemu ne nalaze bar jedna odrasla osoba i po završetku vožnje u čamcu ne smeju da ostanu samo deca. Smatrati da će se čamac nakon iskrcavanja svih putnika odmah biti spreman da primi narednu grupu putnika. Koristeći CSP napisati program koji rešava ovaj problem.

Rešenje

Vodio sam se rešenjem istog zadatka koji je bio u delu sa regionima. Jedino za šta nisam siguran je da li treba da se šalju poruke deci ukoliko su se odrasli ukrcali i odraslima ukoliko su se deca iskrcala zbog toga što se to proverava u zaštitnim uslovima uslovima.

[Man(i:1..N)::MAN || Woman(i:1..N)::WOMAN || Child(i:1..N)::CHILD || Boat::BOAT]

BOAT:: 
[
	capacity:integer; capacity:=0;
	boarding:integer; boarding:=1;
	onBoard:integer; onBoard:=0;
	onBoardMen:integer; onBoardMen:=0;
	onBoardWomen:integer; onBoardWomen:=0;
	onBoardChildren:integer; onBoardChildren:=0;	
	
	*[
		boarding==1 -> 
		[
			onBoard == capacity, Man(i:1..N) Man(i)?enter ->  Man(i)!boatFull;
			[]
			onBoard < capacity; Man(i:1..N) Man(i)?enter -> 
			[
				
				onBoard:=onBoard+1;
				onBoardMen:=onBoardMen+1;
				
				Man(i)!boarded;
				
				onBoard==capacity -> boarding:=0;
			]
			[]
			onBoard == capacity, Woman(i:1..N) Woman(i)?enter ->  Woman(i)!boatFull;
			[]
			onBoard < capacity and onBoard-onBoardMen <= 7, Woman(i:1..N) Woman(i)?enter -> 
			[
				onBoard:=onBoard+1;
				onBoardWomen:=onBoardWomen+1;
				
				Woman(i)!boarded;
				
				onBoard==capacity -> boarding:=0;
			]
			[]
			onBoard == capacity, Child(i:1..N) Child(i)?enter ->  Child(i)!boatFull;
			[]
			onBoard == 0, Child(i:1..N) Child(i)?enter ->  Child(i)!waitForAdult;
			[]
			onBoard-onBoardMen <= 7, Child(i:1..N) Child(i)?enter -> 
			[
				onBoard:=onBoard+1;
				onBoardChildren:=onBoardChildren+1;
				
				Child(i)!boarded;
				
				onBoard==capacity -> boarding:=0;
			]
		]
		[]
		boarding==0 ->
		[
			onBoardMen+onBoardWomen==1 and onBoardChildren > 0, Man(i)?exit -> Man(i)!waitForChildrenToExit;
			[]
			(onBoardMen+onBoardWomen>1 and onBoardChildren > 0) or onBoardChildren==0, Man(i)?exit -> 
			[
				onBoard:=onBoard-1;
				onBoardMen:=onBoardMen-1;
				
				Man(i)!exited;
				
				onBoard == 0 -> boarding:=1;
			]
			[]
			onBoardMen+onBoardWomen==1 and onBoardChildren > 0, Woman(i)?exit -> Woman(i)!waitForChildrenToExit;
			[]
			(onBoardMen+onBoardWomen>1 and onBoardChildren > 0) or onBoardChildren==0, Woman(i)?exit -> 
			[
				onBoard:=onBoard-1;
				onBoardWomen:=onBoardWomen-1;
				
				Woman(i)!exited;
				
				onBoard == 0 -> boarding:=1;

			]
			[]
			Child(i)?exit -> 
			[
				onBoard:=onBoard - 1;
				onBoardChildren:= onBoardChildren -1;
				Child!exited;
			]
			
			
		]
	]
	
]

MAN:: 
[
	Man!enter;
	
	[
		Man?boatFull -> waitForReturnTrip;
		[]
		Man?boarded -> 
		[
			Man!exit;
			[
				Man?waitForChildrenToExit -> wait;
				[]
				Man(i)?exited; //iskrcao se muskarac
			]
		]
		
	]
]

WOMAN:: 
[
	Woman!enter;
	
	[
		Woman?boatFull -> waitForReturnTrip;
		[]
		Woman?boarded -> 
		[
			Woman!exit;
			[
				Woman?waitForChildrenToExit -> wait;
				[]
				Woman(i)?exited; //iskrcala se zena
			]
		]
	]
]

CHILD::
[
	Child!enter;
	
	[
		Child?boatFull -> waitForReturnTrip;
		[]
		Child?waitForAdult -> wait;
		[]
		Child?boarded ->
		[
			Child!exit;
			Child?exited; //iskrcalo se dete
		]
		
		
	]
]