КДП/Јун 2020

Поставка овог рока може се наћи са странице предмета (зипована).

1. задатак

Поставка

Андерсенов алгоритам за N процеса реализован помоћу addAndGet операције. Уколико би addAndGet операција имала следећи ефекат: addAndGet(var, incr) : < var = var + incr; return(var); >, да ли је могуће направити Fine grain решење, полазећи од Coarse grain решења (написати га), и ако је могуће – направите га.

Решење

Coarse-grain решење:

const int N = 100;
bool flag[N];
int tail = 0;

void worker() {
    while (true) {
        < int index = tail; tail = (tail + 1) % N; >
        < await(flag[index]); >
        /* критична секција */
        flag[index] = false;
        flag[(index + 1) % N] = true;
        /* некритична секција */
    }
}

Fine-grain решење:

const int N = 100;
bool flag[N];
int tail = 0;

void worker() {
    while (true) {
        int index = (addAndGet(tail, 1) - 1) % N;
        while (!flag[index]) skip();
        /* критична секција */
        flag[index] = false;
        flag[(index + 1) % N] = true;
        /* некритична секција */
    }
}

2. задатак

Поставка

Посматра се острво на коме људи могу да разгледају музеј о диносаурусима и парк за живим примерцима (The Jurassic Park Problem). У парку постоји N безбедних возила која могу да приме по једног путника. У парк може долазити произвољан број посетилаца. На почетку посетилац слободно разгледа музеј са експонатима. Када заврши разгледање, прелази на део са живим диносаурусима, тако што сачека да се појави прво сигурно возило које ће га провести кроз парк. Када наиђе слободно возило, посетилац прелази на вожњу по парку која траје неко време. На крају вожње посетилац напушта парк (може некад да се врати), а возило се враћа да прими следећег посетиоца. Уколико су сва возила заузета, посетилац који жели да иде у обилазак чека слободно возило. Уколико постоји слободно возило, али не и посетилац који тренутно чека да уђе, онда возило чека. Користећи семафоре написати програме за посетиоце и возила, као и код за иницијализацију.

Решење

const int N = 100;

sem carCount = N;
list<pair<sem*, sem*>> freeCars;
sem carMutex = 1;

void car() {
    sem carSem = 0;
    sem visitorSem = 0;
    while (true) {
        // Враћамо се назад на место (први пут, ово служи за иницијализацију)
        carMutex.wait();
        freeCars.push_back({&carSem, &visitorSem});
        carMutex.signal();
        carCount.signal();
        carSem.wait();
        // Посетилац се вози по парку
        visitorSem.signal();
        // Готова вожња по парку
        carSem.wait();
    }
}

void visitor() {
    while (true) {
        // Обилазак музеја
        carCount.wait();
        carMutex.wait();
        sem* carSem = freeCars.front().first;
        sem* visitorSem = freeCars.front().second;
        freeCars.pop_front();
        carSem->signal();
        carMutex.signal();
        // Вожња по парку
        visitorSem->wait();
        // Готова вожња по парку
        carSem->signal();
        // Посетилац је напустио парк и можда се некад врати
    }
}

3. задатак

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

Поставка

Објасните како се реализује монитор са Signal and Continue дисциплином, код кога је дозвољено да се из једне мониторске методе позива друга мониторска метода користећи семафоре. За сваку каракеристичну^[sic] ситуацију (5 ситуацијa) дати основне компоненте кôда (као са предавања) и објасните функцију делова тог кôда. За сваку ситуацију посебно навести који семафори се користе, и од чега зависи број тих семафора.

4. задатак

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

Поставка

У неком обданишту постоји правило које каже да се на свака три детета мора наћи барем једна васпитачица (The Child Care Problem). Родитељ доводи једно или више деце у обданиште и чека све док се не појави место, како би оставио сву децу одједном и отишао. Родитељ такође може да одведе једно или више деце, такође одједном. Васпитачица долази на посао и сме да напусти обданиште само уколико то не нарушава правило. Мора се поштовати редослед доласка родитеља који остављају децу и васпитачица које одлазе са посла. Користећи условне критичне регионе, написати процедуре за родитеље који доводе децу, родитеље који одводе децу, васпитачице које долазе на посао и васпитачице које одлазе са посла. Иницијализовати почетне услове.

5. задатак

Поставка

Реализовати прстен од n процеса, који комуницирају асинхроним прослеђивањем порука коришћењем комуникационих канала и send и receive исказа, а код кога процес 0 генерише случајан низ од m природних бројева у интервалу од 1 до 20.000 завршен са sentinel вредношћу EONAT (нпр 20.001). Преосталих n-1 процеса одстрањују из низа све појаве првих n-1 простих бројева. Сваки процес има по један различит прост број за који је задужен. Након одстрањивања простих бројева, модификован низ се дистрибуира свим процесима. Обезбедити максималну конкурентност.

Решење

const int N = ...;
const int m = ...;
const int EONAT = 20001;
chan values[N](int);

void proccess0(){
	int array[m];
	
	for(int i=0; i<m; i++) array[i] = rand(1,20000);
	
	for(int i=0; i<m; i++) send values[1](array[i]);
	send values[1](EONAT);
	
	bool end = false;
	int temp,index = 0;
	while(!end){
		receive values[0](temp);
		if(temp == EONAT) end = true;
		else array[index++] = temp;
	}
	
	for(int i=0; i<index; i++) send values[1](array[i]);
	send values[1](EONAT);
}

void proccess(int id, int myNumber){
	int array[m];
	
	bool end = false;
	int temp;
	while(!end){
		receive values[id](temp);
		if(temp == EONAT) end = true;
		else if(temp != myNumber) send values[(id+1)%N](temp);
	}
	
	end = false;
	int index = 0;
	while(!end){
		receive values[id](temp);
		if(temp == EONAT) end = true;
		else{
			array[index++] = temp;
			if(id != N-1) send values[(id+1)%N](temp);
		}
	}
}

6. задатак

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

Поставка

Посматра се скуп чворова у графу који могу да комуницирају само са својим суседима (Distributed Pairing Problem). Сваки чвор треба да нађе чвор са којим ће се упарити. На крају поступка упаривања сваки чвор ће или имати свог пара, или остати неупарен, али тако да ни једна два суседна чвора не остану неупарена. Написати програм за чвор користећи библиотеку C-Linda.