КДП/К1 2018 - Историја измена

Fedja: kategorija zadatka

2023-02-11T17:05:08Z

kategorija zadatka

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

	== 1. задатак ==
			== {{категорија\|1. задатак\|Семафори}} ==
	=== Поставка ===		=== Поставка ===
	Потребно је урадити синхронизацију на баријери која функционише на следећи начин: постоје два процеса координатора за по половину радних процеса (претпоставити паран број радних процеса) који треба да се синхронизују на баријери. Притом, та два процеса координатора прво закључују када су сви њихови процеси стигли до њихових интерних подбаријера и кроз поступак међусобне комуникације координатора утврђују када су сви радни процеси стигли до еквивалентне јединствене баријере. Након тога оба процеса координатора треба да дозволе радним процесима да прођу баријеру. Написати кôд радних процеса и оба процеса координатора.		Потребно је урадити синхронизацију на баријери која функционише на следећи начин: постоје два процеса координатора за по половину радних процеса (претпоставити паран број радних процеса) који треба да се синхронизују на баријери. Притом, та два процеса координатора прво закључују када су сви њихови процеси стигли до њихових интерних подбаријера и кроз поступак међусобне комуникације координатора утврђују када су сви радни процеси стигли до еквивалентне јединствене баријере. Након тога оба процеса координатора треба да дозволе радним процесима да прођу баријеру. Написати кôд радних процеса и оба процеса координатора.
Ред 53:		Ред 54:
	}		}
	</syntaxhighlight>		</syntaxhighlight>


	== {{категорија\|2. задатак\|Семафори}} ==		== {{категорија\|2. задатак\|Семафори}} ==

Fedja: kategorije zadataka

2023-02-11T02:54:27Z

kategorije zadataka

← Старија измена		Верзија на датум 11. фебруар 2023. у 04:54
Ред 55:		Ред 55:


	== 2. задатак ==		== {{категорија\|2. задатак\|Семафори}} ==
	=== Поставка ===		=== Поставка ===
	Негде у Африци постоји дубок кањон на чијим литицама живе бабуни (''The Baboons Crossing Problem''). Између две литице кањона постоји лијана преко које бабуни прелазе реку. Да би се избегао сукоб између бабуна у једном тренутку на лијани смеју да се нађу само бабуни који припадају једној страни кањона. Такође, лијана може да издржи највише 5 бабуна, иначе пуца. Користећи семафоре написати програм за бабуне са обе стране кањона.		Негде у Африци постоји дубок кањон на чијим литицама живе бабуни (''The Baboons Crossing Problem''). Између две литице кањона постоји лијана преко које бабуни прелазе реку. Да би се избегао сукоб између бабуна у једном тренутку на лијани смеју да се нађу само бабуни који припадају једној страни кањона. Такође, лијана може да издржи највише 5 бабуна, иначе пуца. Користећи семафоре написати програм за бабуне са обе стране кањона.

KockaAdmiralac: Formatiranje

2023-02-09T00:15:42Z

Formatiranje

← Старија измена		Верзија на датум 9. фебруар 2023. у 02:15
Ред 1:		Ред 1:
	{{tocright}}		{{tocright}}
	Поставка овог рока може се наћи са [https://rti.etf.bg.ac.rs/rti/ir3kdp/rokovi/kdp18.zip странице предмета] (зипована).		'''Први колоквијум 2018. године''' одржан је 19. марта. Поставка овог рока може се наћи са [https://rti.etf.bg.ac.rs/rti/ir3kdp/rokovi/kdp18.zip странице предмета] (зипована).

	== 1. задатак ==		== 1. задатак ==
Ред 7:		Ред 7:

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

	<syntaxhighlight lang="cpp">		<syntaxhighlight lang="cpp">
	const int N=...;		const int N = ...;
	sem arrive[N]={0};		sem arrive[N] = {0};
	sem pass[N]={0};		sem pass[N] = {0};
	bool coordinator=false;		bool coordinator = false;
	sem coordinatorSem=0;		sem coordinatorSem = 0;
	sem mutex=1;		sem mutex = 1;

	void coordinator1(){		void coordinator1() {
	for(int i=0; i<N/2; i++) arrive[i].wait();		for (int i = 0; i < N / 2; i++) arrive[i].wait();
	mutex.wait();		mutex.wait();
	if(coordinator){		if (coordinator) {
	coordinator=false;		coordinator = false;
	mutex.signal();		mutex.signal();
	coordinatorSem.signal();		coordinatorSem.signal();
	}		} else {
	else{		coordinator = true;
	coordinator=true;
	mutex.signal();		mutex.signal();
	coordinatorSem.wait();		coordinatorSem.wait();
	}		}
	for(int i=0; i<N/2; i++) pass[i].signal();		for (int i = 0; i < N / 2; i++) pass[i].signal();
	}		}

	void coordinator2(){		void coordinator2() {
	for(int i=N/2; i<N; i++) arrive[i].wait();		for (int i = N / 2; i < N; i++) arrive[i].wait();
	mutex.wait();		mutex.wait();
	if(coordinator){		if (coordinator) {
	coordinator=false;		coordinator = false;
	mutex.signal();		mutex.signal();
	coordinatorSem.signal();		coordinatorSem.signal();
	}		} else {
	else{		coordinator = true;
	coordinator=true;
	mutex.signal();		mutex.signal();
	coordinatorSem.wait();		coordinatorSem.wait();
	}		}
	for(int i=N/2; i<N; i++) pass[i].signal();		for (int i = N / 2; i < N; i++) pass[i].signal();
	}		}

	void process(int i){		void process(int i) {
	while(true){		while (true) {
	work();		work();
	arrive[i].signal();		arrive[i].signal();
Ред 60:		Ред 57:
	== 2. задатак ==		== 2. задатак ==
	=== Поставка ===		=== Поставка ===
	Негде у Африци постоји дубок кањон на чијим литицама живе бабуни (~~<i>~~The Baboons Crossing Problem~~</i>~~). Између две литице кањона постоји лијана преко које бабуни прелазе реку. Да би се избегао сукоб између бабуна у једном тренутку на лијани смеју да се нађу само бабуни који припадају једној страни кањона. Такође, лијана може да издржи највише 5 бабуна, иначе пуца. Користећи семафоре написати програм за бабуне са обе стране кањона.		Негде у Африци постоји дубок кањон на чијим литицама живе бабуни (''The Baboons Crossing Problem''). Између две литице кањона постоји лијана преко које бабуни прелазе реку. Да би се избегао сукоб између бабуна у једном тренутку на лијани смеју да се нађу само бабуни који припадају једној страни кањона. Такође, лијана може да издржи највише 5 бабуна, иначе пуца. Користећи семафоре написати програм за бабуне са обе стране кањона.

	=== Решење ===		=== Решење ===
	<syntaxhighlight lang="cpp">		<syntaxhighlight lang="cpp">
	const int N=5;		const int N = 5;
	int baboons=0;		int baboons = 0;
	int currentSide=0;		int currentSide = 0;
	sem waiting[2]={0};		sem waiting[2] = {0};
	List<int> list;		List<int> list;
	sem mutex=0;		sem mutex=0;

	//side je 0 ili 1, u zavisnosti sa koje strane kanjona se nalazi		// side je 0 ili 1, u zavisnosti sa koje strane kanjona se nalazi
	void baboon(int side){		void baboon(int side) {
	mutex.wait();		mutex.wait();
	if(baboons==0 \|\| (currentSide==side && baboons<N && list.size()==0)){ ~~//Uslov list.size()==0 da ne bi doslo do izgladnjivanja~~		// Uslov list.size() == 0 da ne bi doslo do izgladnjivanja
			if (baboons == 0 \|\| (currentSide == side && baboons < N && list.size() == 0)) {
	currentSide=side;		currentSide=side;
	baboons++;		baboons++;
	mutex.signal();		mutex.signal();
	}		} else {
	else{
	list.add(side);		list.add(side);
	mutex.signal();		mutex.signal();
	waiting[side].wait();		waiting[side].wait();
	}		}

	cross();		cross();

	mutex.wait();		mutex.wait();
	baboons--;		baboons--;
	if(list.size()>0){		if (list.size() > 0) {
	~~if(list.get(0)==side){~~ //Ako je sledeci zablokiran kretao sa iste strane, moze da krene kada jedan babun predje na drugu stranu		// Ako je sledeci zablokiran kretao sa iste strane, moze da krene kada jedan babun predje na drugu stranu
			if (list.get(0) == side) {
	list.pop(0);		list.pop(0);
	baboons++;		baboons++;
	waiting[side].signal();		waiting[side].signal();
	}		} else if (baboons == 0) {
	else if(baboons==0){ //Ako je sledeci zablokiran kretao sa suprotne strane, moze da krene samo kada svi babuni sa prvobitne strane predju lijanu, i sa njim mozemo pustiti jos		// Ako je sledeci zablokiran kretao sa suprotne strane, moze da krene samo kada svi babuni sa prvobitne
	~~currentSide=!side; //~~ maksimalno 4(N-1) babuna sa iste strane ako su se svi zablokirali za redom		// strane predju lijanu, i sa njim mozemo pustiti jos maksimalno 4(N-1) babuna sa iste strane ako su
	while(list.get(0)==(!side) && baboons<N){		// se svi zablokirali za redom
			currentSide = !side;
			while (list.get(0) == (!side) && baboons < N) {
	list.pop(0);		list.pop(0);
	baboons++;		baboons++;

KockaAdmiralac: mutex treba da bude 1 na početku

2022-06-14T10:15:19Z

mutex treba da bude 1 na početku

← Старија измена		Верзија на датум 14. јун 2022. у 12:15
Ред 14:		Ред 14:
	bool coordinator=false;		bool coordinator=false;
	sem coordinatorSem=0;		sem coordinatorSem=0;
	sem mutex=0;		sem mutex=1;

	void coordinator1(){		void coordinator1(){

Lukahrvacevic: /* Komentari */

2022-04-01T15:14:12Z

Komentari

← Старија измена		Верзија на датум 1. април 2022. у 17:14
Ред 74:		Ред 74:
	void baboon(int side){		void baboon(int side){
	mutex.wait();		mutex.wait();
	if(baboons==0 \|\| (currentSide==side && baboons<N && list.size()==0)){		if(baboons==0 \|\| (currentSide==side && baboons<N && list.size()==0)){ //Uslov list.size()==0 da ne bi doslo do izgladnjivanja
	currentSide=side;		currentSide=side;
	baboons++;		baboons++;
Ред 90:		Ред 90:
	baboons--;		baboons--;
	if(list.size()>0){		if(list.size()>0){
	if(list.get(0)==side){		if(list.get(0)==side){ //Ako je sledeci zablokiran kretao sa iste strane, moze da krene kada jedan babun predje na drugu stranu
	list.pop(0);		list.pop(0);
	baboons++;		baboons++;
	waiting[side].signal();		waiting[side].signal();
	}		}
	else if(baboons==0){		else if(baboons==0){ //Ako je sledeci zablokiran kretao sa suprotne strane, moze da krene samo kada svi babuni sa prvobitne strane predju lijanu, i sa njim mozemo pustiti jos
	currentSide=!side;		currentSide=!side; // maksimalno 4(N-1) babuna sa iste strane ako su se svi zablokirali za redom
	while(list.get(0)==(!side) && baboons<N){		while(list.get(0)==(!side) && baboons<N){
	list.pop(0);		list.pop(0);

Lukahrvacevic: Dodata oba zadatka sa K1 2018

2022-04-01T15:04:11Z

Dodata oba zadatka sa K1 2018

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

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

== 1. задатак ==
=== Поставка ===
Потребно је урадити синхронизацију на баријери која функционише на следећи начин: постоје два процеса координатора за по половину радних процеса (претпоставити паран број радних процеса) који треба да се синхронизују на баријери. Притом, та два процеса координатора прво закључују када су сви њихови процеси стигли до њихових интерних подбаријера и кроз поступак међусобне комуникације координатора утврђују када су сви радни процеси стигли до еквивалентне јединствене баријере. Након тога оба процеса координатора треба да дозволе радним процесима да прођу баријеру. Написати кôд радних процеса и оба процеса координатора.

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

<syntaxhighlight lang="cpp">
const int N=...;
sem arrive[N]={0};
sem pass[N]={0};
bool coordinator=false;
sem coordinatorSem=0;
sem mutex=0;

void coordinator1(){
for(int i=0; i<N/2; i++) arrive[i].wait();
mutex.wait();
if(coordinator){
coordinator=false;
mutex.signal();
coordinatorSem.signal();
}
else{
coordinator=true;
mutex.signal();
coordinatorSem.wait();
}
for(int i=0; i<N/2; i++) pass[i].signal();
}

void coordinator2(){
for(int i=N/2; i<N; i++) arrive[i].wait();
mutex.wait();
if(coordinator){
coordinator=false;
mutex.signal();
coordinatorSem.signal();
}
else{
coordinator=true;
mutex.signal();
coordinatorSem.wait();
}
for(int i=N/2; i<N; i++) pass[i].signal();
}

void process(int i){
while(true){
work();
arrive[i].signal();
pass[i].wait();
}
}
</syntaxhighlight>

== 2. задатак ==
=== Поставка ===
Негде у Африци постоји дубок кањон на чијим литицама живе бабуни (<i>The Baboons Crossing Problem</i>). Између две литице кањона постоји лијана преко које бабуни прелазе реку. Да би се избегао сукоб између бабуна у једном тренутку на лијани смеју да се нађу само бабуни који припадају једној страни кањона. Такође, лијана може да издржи највише 5 бабуна, иначе пуца. Користећи семафоре написати програм за бабуне са обе стране кањона.

=== Решење ===
<syntaxhighlight lang="cpp">
const int N=5;
int baboons=0;
int currentSide=0;
sem waiting[2]={0};
List<int> list;
sem mutex=0;

//side je 0 ili 1, u zavisnosti sa koje strane kanjona se nalazi
void baboon(int side){
mutex.wait();
if(baboons==0 || (currentSide==side && baboons<N && list.size()==0)){
currentSide=side;
baboons++;
mutex.signal();
}
else{
list.add(side);
mutex.signal();
waiting[side].wait();
}

cross();

mutex.wait();
baboons--;
if(list.size()>0){
if(list.get(0)==side){
list.pop(0);
baboons++;
waiting[side].signal();
}
else if(baboons==0){
currentSide=!side;
while(list.get(0)==(!side) && baboons<N){
list.pop(0);
baboons++;
waiting[!side].signal();
}
}
}
mutex.signal();
}
</syntaxhighlight>

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