КДП/Јун 2020 - Историја измена

Fedja: kategorija zadatka

2023-02-11T17:00:21Z

kategorija zadatka

← Старија измена		Верзија на датум 11. фебруар 2023. у 19:00
Ред 2:		Ред 2:
	Поставка овог рока може се наћи са [https://rti.etf.bg.ac.rs/rti/ir3kdp/rokovi/kdp20.zip странице предмета] (зипована).		Поставка овог рока може се наћи са [https://rti.etf.bg.ac.rs/rti/ir3kdp/rokovi/kdp20.zip странице предмета] (зипована).

	== 1. задатак ==		== {{категорија\|1. задатак\|Синхронизациони_алгоритми}} ==
	=== Поставка ===		=== Поставка ===
	Андерсенов алгоритам за N процеса реализован помоћу ''addAndGet'' операције. Уколико би ''addAndGet'' операција имала следећи ефекат: <code>addAndGet(var, incr) : < var = var + incr; return(var); ></code>, да ли је могуће направити ''Fine grain'' решење, полазећи од ''Coarse grain'' решења (написати га), и ако је могуће – направите га.		Андерсенов алгоритам за N процеса реализован помоћу ''addAndGet'' операције. Уколико би ''addAndGet'' операција имала следећи ефекат: <code>addAndGet(var, incr) : < var = var + incr; return(var); ></code>, да ли је могуће направити ''Fine grain'' решење, полазећи од ''Coarse grain'' решења (написати га), и ако је могуће – направите га.

Fedja: kategorije zadataka

2023-02-11T02:42:36Z

kategorije zadataka

← Старија измена		Верзија на датум 11. фебруар 2023. у 04:42
Ред 42:		Ред 42:
	</syntaxhighlight>		</syntaxhighlight>

	== 2. задатак ==		== {{категорија\|2. задатак\|Семафори}} ==
	=== Поставка ===		=== Поставка ===
	Посматра се острво на коме људи могу да разгледају музеј о диносаурусима и парк за живим примерцима (''The Jurassic Park Problem''). У парку постоји N безбедних возила која могу да приме по једног путника. У парк може долазити произвољан број посетилаца. На почетку посетилац слободно разгледа музеј са експонатима. Када заврши разгледање, прелази на део са живим диносаурусима, тако што сачека да се појави прво сигурно возило које ће га провести кроз парк. Када наиђе слободно возило, посетилац прелази на вожњу по парку која траје неко време. На крају вожње посетилац напушта парк (може некад да се врати), а возило се враћа да прими следећег посетиоца. Уколико су сва возила заузета, посетилац који жели да иде у обилазак чека слободно возило. Уколико постоји слободно возило, али не и посетилац који тренутно чека да уђе, онда возило чека. Користећи семафоре написати програме за посетиоце и возила, као и код за иницијализацију.		Посматра се острво на коме људи могу да разгледају музеј о диносаурусима и парк за живим примерцима (''The Jurassic Park Problem''). У парку постоји N безбедних возила која могу да приме по једног путника. У парк може долазити произвољан број посетилаца. На почетку посетилац слободно разгледа музеј са експонатима. Када заврши разгледање, прелази на део са живим диносаурусима, тако што сачека да се појави прво сигурно возило које ће га провести кроз парк. Када наиђе слободно возило, посетилац прелази на вожњу по парку која траје неко време. На крају вожње посетилац напушта парк (може некад да се врати), а возило се враћа да прими следећег посетиоца. Уколико су сва возила заузета, посетилац који жели да иде у обилазак чека слободно возило. Уколико постоји слободно возило, али не и посетилац који тренутно чека да уђе, онда возило чека. Користећи семафоре написати програме за посетиоце и возила, као и код за иницијализацију.
Ред 90:		Ред 90:
	</syntaxhighlight>		</syntaxhighlight>

	== 3. задатак ==		== {{категорија\|3. задатак\|Монитори}} ==
	{{делимично решено}}		{{делимично решено}}
	=== Поставка ===		=== Поставка ===
Ред 97:		Ред 97:
	=== Решење ===		=== Решење ===

	== 4. задатак ==		== {{категорија\|4. задатак\|Региони}} ==
	{{делимично решено}}		{{делимично решено}}
	=== Поставка ===		=== Поставка ===
Ред 104:		Ред 104:
	=== Решење ===		=== Решење ===

	== 5. задатак ==		== {{категорија\|5. задатак\|Прстен}} ==
	=== Поставка ===		=== Поставка ===
	Реализовати прстен од n процеса, који комуницирају асинхроним прослеђивањем порука коришћењем комуникационих канала и ''send'' и ''receive'' исказа, а код кога процес 0 генерише случајан низ од m природних бројева у интервалу од 1 до 20.000 завршен са ''sentinel'' вредношћу ''EONAT'' (нпр 20.001). Преосталих n-1 процеса одстрањују из низа све појаве првих n-1 простих бројева. Сваки процес има по један различит прост број за који је задужен. Након одстрањивања простих бројева, модификован низ се дистрибуира свим процесима. Обезбедити максималну конкурентност.		Реализовати прстен од n процеса, који комуницирају асинхроним прослеђивањем порука коришћењем комуникационих канала и ''send'' и ''receive'' исказа, а код кога процес 0 генерише случајан низ од m природних бројева у интервалу од 1 до 20.000 завршен са ''sentinel'' вредношћу ''EONAT'' (нпр 20.001). Преосталих n-1 процеса одстрањују из низа све појаве првих n-1 простих бројева. Сваки процес има по један различит прост број за који је задужен. Након одстрањивања простих бројева, модификован низ се дистрибуира свим процесима. Обезбедити максималну конкурентност.
Ред 153:		Ред 153:
	</syntaxhighlight>		</syntaxhighlight>

	== 6. задатак ==		== {{категорија\|6. задатак\|C-Linda}} ==
	{{делимично решено}}		{{делимично решено}}
	=== Поставка ===		=== Поставка ===

KockaAdmiralac: Formatiranje

2023-02-08T19:46:15Z

Formatiranje

← Старија измена		Верзија на датум 8. фебруар 2023. у 21:46
Ред 109:		Ред 109:

	=== Решење ===		=== Решење ===

	<syntaxhighlight lang="cpp">		<syntaxhighlight lang="cpp">
	const int N = ...;		const int N = ...;
Ред 116:		Ред 115:
	chan values[N](int);		chan values[N](int);

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

	for(int i=0; i<index; i++) send values[1](array[i]);
	send values[1](EONAT);
	}		}

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


	</syntaxhighlight>		</syntaxhighlight>

Lukahrvacevic: Skidanje taga delimicno reseno

2022-07-16T16:56:38Z

Skidanje taga delimicno reseno

← Старија измена		Верзија на датум 16. јул 2022. у 18:56
Ред 105:		Ред 105:

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

Lukahrvacevic: /* 5. задатак */

2022-07-16T16:56:23Z

5. задатак

← Старија измена		Верзија на датум 16. јул 2022. у 18:56
Ред 110:		Ред 110:

	=== Решење ===		=== Решење ===

			<syntaxhighlight lang="cpp">
			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);
			}
			}
			}


			</syntaxhighlight>

	== 6. задатак ==		== 6. задатак ==

KockaAdmiralac: Rešenje prvog i drugog zadatka

2022-03-31T19:51:28Z

Rešenje prvog i drugog zadatka

Нова страница

{{tocright}}
Поставка овог рока може се наћи са [https://rti.etf.bg.ac.rs/rti/ir3kdp/rokovi/kdp20.zip странице предмета] (зипована).

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

=== Решење ===
''Coarse-grain'' решење:
<syntaxhighlight lang="cpp">
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;
/* некритична секција */
}
}
</syntaxhighlight>
''Fine-grain'' решење:
<syntaxhighlight lang="cpp">
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;
/* некритична секција */
}
}
</syntaxhighlight>

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

=== Решење ===
<syntaxhighlight lang="cpp">
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();
// Посетилац је напустио парк и можда се некад врати
}
}
</syntaxhighlight>

== 3. задатак ==
{{делимично решено}}
=== Поставка ===
Објасните како се реализује монитор са ''Signal and Continue'' дисциплином, код кога је дозвољено да се из једне мониторске методе позива друга мониторска метода користећи семафоре. За сваку каракеристичну<sup>[sic]</sup> ситуацију (5 ситуацијa) дати основне компоненте кôда (као са предавања) и објасните функцију делова тог кôда. За сваку ситуацију посебно навести који семафори се користе, и од чега зависи број тих семафора.

=== Решење ===

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

=== Решење ===

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

=== Решење ===

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

=== Решење ===

[[Категорија:КДП]]
[[Категорија:Рокови]]