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

Fedja: test za indikator rešenosti

2023-07-08T19:10:07Z

test za indikator rešenosti

← Старија измена		Верзија на датум 8. јул 2023. у 21:10
Ред 194:		Ред 194:

	== {{категорија\|4. задатак\|CSP}} ==		== {{категорија\|4. задатак\|CSP}} ==
	{{~~делимично решено~~}}		{{delimično rešeno}}
	=== Поставка ===		=== Поставка ===
	У свемиру постоји N небеских тела која међусобно интерагују (''N Body Gravitational Problem''), по Њутновом закону гравитације. Свако тело интерагује са сваким, при чему размењују информације о позицији, брзини и вектору силе. Користећи CSP потребно је решити овај проблем користећи торбу послова за дохватање посла и синхронизацију на баријери у свакој итерацији. Потребно је реализовати следеће процесе: ''Worker'' (обавља израчунавање), ''Bag'' (обавља поделу посла) и ''Collector'' (обавља прикупљање резултата). Број процеса ''Worker'' није познат, али је познато да их има мање од N. Постоји тачно један процес ''Bag'' и тачно један процес ''Collector''.		У свемиру постоји N небеских тела која међусобно интерагују (''N Body Gravitational Problem''), по Њутновом закону гравитације. Свако тело интерагује са сваким, при чему размењују информације о позицији, брзини и вектору силе. Користећи CSP потребно је решити овај проблем користећи торбу послова за дохватање посла и синхронизацију на баријери у свакој итерацији. Потребно је реализовати следеће процесе: ''Worker'' (обавља израчунавање), ''Bag'' (обавља поделу посла) и ''Collector'' (обавља прикупљање резултата). Број процеса ''Worker'' није познат, али је познато да их има мање од N. Постоји тачно један процес ''Bag'' и тачно један процес ''Collector''.

Fedja: kategorije zadataka

2023-02-11T02:30:55Z

kategorije zadataka

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

	== 1. задатак ==		== {{категорија\|1. задатак\|Монитори}} ==
	: ''Сличан задатак дошао је у [[КДП/Август 2021#1. zadatak\|августу 2021. године]] са ''Signal and Continue'' дисциплином.''		: ''Сличан задатак дошао је у [[КДП/Август 2021#1. zadatak\|августу 2021. године]] са ''Signal and Continue'' дисциплином.''
	=== Поставка ===		=== Поставка ===
Ред 44:		Ред 44:
	</syntaxhighlight>		</syntaxhighlight>

	== 2. задатак ==		== {{категорија\|2. задатак\|Семафори}} ==
	=== Поставка ===		=== Поставка ===
	Користећи семафоре написати програм који решава проблем путовања лифтом. Путник позива лифт са произвољног спрата. Када лифт стигне на неки спрат сви путници који су изразили жељу да сиђу на том спрату обавезно изађу. Након изласка путника сви путници који су чекали на улазак уђу у лифт и кажу на који спрат желе да пређу. Тек када се сви изјасне лифт прелази даље. Лифт редом обилази спратове и стаје само на оне где има путника који улазе или излазе. Може се претпоставити да постоји N спратова.		Користећи семафоре написати програм који решава проблем путовања лифтом. Путник позива лифт са произвољног спрата. Када лифт стигне на неки спрат сви путници који су изразили жељу да сиђу на том спрату обавезно изађу. Након изласка путника сви путници који су чекали на улазак уђу у лифт и кажу на који спрат желе да пређу. Тек када се сви изјасне лифт прелази даље. Лифт редом обилази спратове и стаје само на оне где има путника који улазе или излазе. Може се претпоставити да постоји N спратова.
Ред 139:		Ред 139:
	</syntaxhighlight>		</syntaxhighlight>

	== 3. задатак ==		== {{категорија\|3. задатак\|Активни_монитори}} ==
	=== Поставка ===		=== Поставка ===
	Користећи технику активних монитора потребно је реализовати семафор који поред стандардних атомских операција ''signal()'' и ''wait()'' има и атомске операције ''signal(n)'' и ''wait(n)'' која интерну семафорску променљиву атомски увећава односно умањује за ''n'' уколико је то могуће, уколико није чека док не буде били могуће. Процес који је раније упутио захтев треба раније да обави своју операцију.		Користећи технику активних монитора потребно је реализовати семафор који поред стандардних атомских операција ''signal()'' и ''wait()'' има и атомске операције ''signal(n)'' и ''wait(n)'' која интерну семафорску променљиву атомски увећава односно умањује за ''n'' уколико је то могуће, уколико није чека док не буде били могуће. Процес који је раније упутио захтев треба раније да обави своју операцију.
Ред 193:		Ред 193:
	</syntaxhighlight>		</syntaxhighlight>

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

KockaAdmiralac: Formatiranje

2023-02-08T19:51:42Z

Formatiranje

← Старија измена		Верзија на датум 8. фебруар 2023. у 21:51
Ред 145:		Ред 145:
	=== Решење ===		=== Решење ===
	<syntaxhighlight lang="cpp">		<syntaxhighlight lang="cpp">
	enum op_kind{WAIT,SIGNAL,WAITN,SIGNALN};		enum op_kind { WAIT, SIGNAL, WAITN, SIGNALN };
	chan request(int, op_kind, int);		chan request(int, op_kind, int);
	chan reply[n](bool);		chan reply[n](bool);

	class Semaphore{		class Semaphore {
	public:		public:
			void run() {
	void run(){		int clientID;
	int clientID;		op_kind kind;
	op_kind kind;		int n;
	int n;		int tokens = 0;
	int tokens = 0;		queue<pair<int,int>> pending;
	queue<pair<int,int>> pending;		while (true) {
	while(true){
	receive request(clientID, kind, n);		receive request(clientID, kind, n);
	if(kind == WAIT){		if (kind == WAIT) {
	if(tokens<=0){		if (tokens <= 0) {
	pending.push(make_pair(clientID, 1));		pending.push(make_pair(clientID, 1));
	}		} else {
	else{		tokens--;
	tokens--;		send reply[clientID](true);
	send reply[clientID](true);		}
	}		} else if (kind == WAITN) {
			if (tokens <= n-1) {
			pending.push(make_pair(clientID, n));
			} else {
			tokens = tokens-n;
			send reply[clientID](true);
			}
			} else if (kind == SIGNAL) {
			tokens++;
			if (!pending.empty() && pending.front().second == tokens) {
			tokens = 0;
			send reply[pending.front().first](true);
			pending.pop();
			}
			} else if (kind == SIGNALN) {
			tokens += n;
			while (!pending.empty() && pending.front().second <= tokens) {
			tokens -= pending.front().second;
			send reply[pending.front().first](true);
			pending.pop();
			}
	}		}
	~~else if(kind == WAITN){~~		}
	~~if(tokens<=n-1){~~		}
	~~pending.push(make_pair(clientID, n));~~
	}
	~~else{~~
	~~tokens = tokens-n;~~
	~~send reply[clientID](true);~~
	}
	}
	~~else if(kind == SIGNAL){~~
	~~tokens++;~~
	~~if(!pending.empty() && pending.front().second == tokens){~~
	~~tokens = 0;~~
	~~send reply[pending.front().first](true);~~
	~~pending.pop();~~
	}
	}
	~~else if(kind == SIGNALN){~~
	~~tokens += n;~~
	~~while(!pending.empty() && pending.front().second <= tokens){~~
	~~tokens -= pending.front().second;~~
	~~send reply[pending.front().first](true);~~
	~~pending.pop();~~
	}
	}
	}
	}
	}		}
	</syntaxhighlight>		</syntaxhighlight>

Lukahrvacevic: /* Ne treba da stoje imena argumenata kod kanala */

2022-07-16T16:09:57Z

Ne treba da stoje imena argumenata kod kanala

← Старија измена		Верзија на датум 16. јул 2022. у 18:09
Ред 146:		Ред 146:
	<syntaxhighlight lang="cpp">		<syntaxhighlight lang="cpp">
	enum op_kind{WAIT,SIGNAL,WAITN,SIGNALN};		enum op_kind{WAIT,SIGNAL,WAITN,SIGNALN};
	chan request(int ~~clientID~~, op_kind ~~kind~~, int n);		chan request(int, op_kind, int);
	chan reply[n](bool);		chan reply[n](bool);

KockaAdmiralac: -{{делимично решено}}

2022-07-16T16:07:21Z

-{{делимично решено}}

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

	== 3. задатак ==		== 3. задатак ==
	~~{{делимично решено}}~~
	=== Поставка ===		=== Поставка ===
	Користећи технику активних монитора потребно је реализовати семафор који поред стандардних атомских операција ''signal()'' и ''wait()'' има и атомске операције ''signal(n)'' и ''wait(n)'' која интерну семафорску променљиву атомски увећава односно умањује за ''n'' уколико је то могуће, уколико није чека док не буде били могуће. Процес који је раније упутио захтев треба раније да обави своју операцију.		Користећи технику активних монитора потребно је реализовати семафор који поред стандардних атомских операција ''signal()'' и ''wait()'' има и атомске операције ''signal(n)'' и ''wait(n)'' која интерну семафорску променљиву атомски увећава односно умањује за ''n'' уколико је то могуће, уколико није чека док не буде били могуће. Процес који је раније упутио захтев треба раније да обави своју операцију.

Lukahrvacevic: /* Решење */

2022-07-16T16:06:41Z

Решење

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

	=== Решење ===		=== Решење ===
			<syntaxhighlight lang="cpp">
			enum op_kind{WAIT,SIGNAL,WAITN,SIGNALN};
			chan request(int clientID, op_kind kind, int n);
			chan reply[n](bool);

			class Semaphore{
			public:

			void run(){
			int clientID;
			op_kind kind;
			int n;
			int tokens = 0;
			queue<pair<int,int>> pending;
			while(true){
			receive request(clientID, kind, n);
			if(kind == WAIT){
			if(tokens<=0){
			pending.push(make_pair(clientID, 1));
			}
			else{
			tokens--;
			send reply[clientID](true);
			}
			}
			else if(kind == WAITN){
			if(tokens<=n-1){
			pending.push(make_pair(clientID, n));
			}
			else{
			tokens = tokens-n;
			send reply[clientID](true);
			}
			}
			else if(kind == SIGNAL){
			tokens++;
			if(!pending.empty() && pending.front().second == tokens){
			tokens = 0;
			send reply[pending.front().first](true);
			pending.pop();
			}
			}
			else if(kind == SIGNALN){
			tokens += n;
			while(!pending.empty() && pending.front().second <= tokens){
			tokens -= pending.front().second;
			send reply[pending.front().first](true);
			pending.pop();
			}
			}
			}
			}
			}
			</syntaxhighlight>

	== 4. задатак ==		== 4. задатак ==

KockaAdmiralac: Latinica

2022-05-15T08:11:11Z

Latinica

← Старија измена		Верзија на датум 15. мај 2022. у 10:11
Ред 3:		Ред 3:

	== 1. задатак ==		== 1. задатак ==
	: ''Сличан задатак дошао је у [[КДП/Август 2021#1. zadatak\|августу 2021. године]] sa ''Signal and Continue'' дисциплином.''		: ''Сличан задатак дошао је у [[КДП/Август 2021#1. zadatak\|августу 2021. године]] са ''Signal and Continue'' дисциплином.''
	=== Поставка ===		=== Поставка ===
	Потребно је реализовати семафор који поред стандардних атомских операција ''signal()'' и ''wait()'' има и атомске операције ''signal(n)'' и ''wait(n)'' која интерну семафорску променљиву атомски увећава односно умањује за ''n'' уколико је то могуће, уколико није чека док не буде били могуће. Потребно је решити проблем користећи мониторе који имају ''Signal and Wait'' дисциплину. Процес који је раније упутио захтев треба раније да обави своју операцију. Број процеса и максимална вредност ''n'' нису унапред познати. Условне променљиве су ''FIFO'' према тренутку доласка и немају приоритетну методу ''wait''.		Потребно је реализовати семафор који поред стандардних атомских операција ''signal()'' и ''wait()'' има и атомске операције ''signal(n)'' и ''wait(n)'' која интерну семафорску променљиву атомски увећава односно умањује за ''n'' уколико је то могуће, уколико није чека док не буде били могуће. Потребно је решити проблем користећи мониторе који имају ''Signal and Wait'' дисциплину. Процес који је раније упутио захтев треба раније да обави своју операцију. Број процеса и максимална вредност ''n'' нису унапред познати. Условне променљиве су ''FIFO'' према тренутку доласка и немају приоритетну методу ''wait''.

KockaAdmiralac: Rešenje prvog zadatka

2022-05-15T06:25:51Z

Rešenje prvog zadatka

@@ Ред 1: / Ред 1: @@
 {{tocright}}
-Поставка овог рока може се наћи са [https://rti.etf.bg.ac.rs/rti/ir3kdp/rokovi/kdp20.zip странице предмета] (зипована).
+'''Јануарски испит 2020. године''' одржан је 18. јануара. Поставка овог рока може се наћи са [https://rti.etf.bg.ac.rs/rti/ir3kdp/rokovi/kdp20.zip странице предмета] (зипована).
 == 1. задатак ==
-{{делимично решено}}
+: ''Сличан задатак дошао је у [[КДП/Август 2021#1. zadatak|августу 2021. године]] sa ''Signal and Continue'' дисциплином.''
 === Поставка ===
 Потребно је реализовати семафор који поред стандардних атомских операција ''signal()'' и ''wait()'' има и атомске операције ''signal(n)'' и ''wait(n)'' која интерну семафорску променљиву атомски увећава односно умањује за ''n'' уколико је то могуће, уколико није чека док не буде били могуће. Потребно је решити проблем користећи мониторе који имају ''Signal and Wait'' дисциплину. Процес који је раније упутио захтев треба раније да обави своју операцију. Број процеса и максимална вредност ''n'' нису унапред познати. Условне променљиве су ''FIFO'' према тренутку доласка и немају приоритетну методу ''wait''.
 === Решење ===
+<syntaxhighlight lang="java">
 == 2. задатак ==
 === Поставка ===
 Користећи семафоре написати програм који решава проблем путовања лифтом. Путник позива лифт са произвољног спрата. Када лифт стигне на неки спрат сви путници који су изразили жељу да сиђу на том спрату обавезно изађу. Након изласка путника сви путници који су чекали на улазак уђу у лифт и кажу на који спрат желе да пређу. Тек када се сви изјасне лифт прелази даље. Лифт редом обилази спратове и стаје само на оне где има путника који улазе или излазе. Може се претпоставити да постоји N спратова.

KockaAdmiralac: nextFloor se ne postavlja

2022-04-01T12:01:37Z

nextFloor se ne postavlja

← Старија измена		Верзија на датум 1. април 2022. у 14:01
Ред 60:		Ред 60:
	// Одређивање следећег спрата		// Одређивање следећег спрата
	// Претпоставка: лифт све време иде горе-доле, без обзира да ли га је неко звао		// Претпоставка: лифт све време иде горе-доле, без обзира да ли га је неко звао
	~~int nextFloor;~~
	if (goingUp) {		if (goingUp) {
	if (++currentFloorIndex == N-1) {		if (++currentFloorIndex == N-1) {
Ред 70:		Ред 69:
	}		}
	}		}
	Floor& floor = floors[~~nextFloor~~];		Floor& floor = floors[currentFloorIndex];
	// Не морамо да чекамо на mutexExiting, јер се он заузима само када путници улазе		// Не морамо да чекамо на mutexExiting, јер се он заузима само када путници улазе
	// што тренутно није случај		// што тренутно није случај

KockaAdmiralac: Rešenje drugog zadatka

2022-03-31T15:38:13Z

Rešenje drugog zadatka

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

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

== 1. задатак ==
{{делимично решено}}
=== Поставка ===
Потребно је реализовати семафор који поред стандардних атомских операција ''signal()'' и ''wait()'' има и атомске операције ''signal(n)'' и ''wait(n)'' која интерну семафорску променљиву атомски увећава односно умањује за ''n'' уколико је то могуће, уколико није чека док не буде били могуће. Потребно је решити проблем користећи мониторе који имају ''Signal and Wait'' дисциплину. Процес који је раније упутио захтев треба раније да обави своју операцију. Број процеса и максимална вредност ''n'' нису унапред познати. Условне променљиве су ''FIFO'' према тренутку доласка и немају приоритетну методу ''wait''.

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

== 2. задатак ==
{{делимично решено}}
=== Поставка ===
Користећи семафоре написати програм који решава проблем путовања лифтом. Путник позива лифт са произвољног спрата. Када лифт стигне на неки спрат сви путници који су изразили жељу да сиђу на том спрату обавезно изађу. Након изласка путника сви путници који су чекали на улазак уђу у лифт и кажу на који спрат желе да пређу. Тек када се сви изјасне лифт прелази даље. Лифт редом обилази спратове и стаје само на оне где има путника који улазе или излазе. Може се претпоставити да постоји N спратова.

=== Решење ===
<syntaxhighlight lang="cpp">
struct Floor {
list<sem*> peopleEntering;
sem mutexEntering = 1;
list<sem*> peopleExiting;
sem mutexExiting = 1;
};

const int N = 10;
Floor floors[N];
sem liftSem = 0;

void person() {
sem personSem = 0;
int currentFloorIndex = rand() % N;
while (true) {
// Особа може да каже да хоће да изађе на истом спрату као тренутном
// Претпоставка: особа није глупа
int nextFloorIndex = rand() % N;
Floor& currentFloor = floors[currentFloorIndex];
Floor& nextFloor = floors[nextFloorIndex];
currentFloor.mutexEntering.wait();
currentFloor.peopleEntering.push_back(&personSem);
currentFloor.mutexEntering.signal();
// Чекамо да дође лифт
personSem.wait();
// Улазимо у лифт и бирамо на којем спрату стајемо
nextFloor.mutexExiting.wait();
nextFloor.peopleExiting.push_back(&personSem);
nextFloor.mutexExiting.signal();
liftSem.signal();
// Чекамо да лифт стигне на наш спрат
personSem.wait();
// Излазимо из лифта
liftSem.signal();
}
}

void lift() {
int currentFloorIndex = 0;
bool goingUp = true;
while (true) {
// Одређивање следећег спрата
// Претпоставка: лифт све време иде горе-доле, без обзира да ли га је неко звао
int nextFloor;
if (goingUp) {
if (++currentFloorIndex == N-1) {
goingUp = false;
}
} else {
if (--currentFloorIndex == 0) {
goingUp = true;
}
}
Floor& floor = floors[nextFloor];
// Не морамо да чекамо на mutexExiting, јер се он заузима само када путници улазе
// што тренутно није случај
int countPeopleExiting = floor.peopleExiting.size();
// Задржавамо mutexEntering док не испразнимо листу, како нам не би ушао неочекивани путник
floor.mutexEntering.wait();
int countPeopleEntering = floor.peopleEntering.size();
if (countPeopleExiting == 0 && countPeopleEntering == 0) {
// Не стајемо на овом спрату
floor.mutexEntering.signal();
continue;
}
// Стајемо на овом спрату
// Пуштамо људе да изађу
for (int i = 0; i < countPeopleExiting; ++i) {
sem* personSem = floor.peopleExiting.front();
personSem->signal();
floor.peopleExiting.pop_front();
}
for (int i = 0; i < countPeopleExiting; ++i) {
liftSem.wait();
}
// Пуштамо људе да уђу
for (int i = 0; i < countPeopleEntering; ++i) {
sem* personSem = floor.peopleEntering.front();
personSem->signal();
floor.peopleEntering.pop_front();
}
for (int i = 0; i < countPeopleEntering; ++i) {
liftSem.wait();
}
floor.mutexEntering.signal();
// Настављамо на следећи спрат
}
}
</syntaxhighlight>

== 3. задатак ==
{{делимично решено}}
=== Поставка ===
Користећи технику активних монитора потребно је реализовати семафор који поред стандардних атомских операција ''signal()'' и ''wait()'' има и атомске операције ''signal(n)'' и ''wait(n)'' која интерну семафорску променљиву атомски увећава односно умањује за ''n'' уколико је то могуће, уколико није чека док не буде били могуће. Процес који је раније упутио захтев треба раније да обави своју операцију.

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

== 4. задатак ==
{{делимично решено}}
=== Поставка ===
У свемиру постоји N небеских тела која међусобно интерагују (''N Body Gravitational Problem''), по Њутновом закону гравитације. Свако тело интерагује са сваким, при чему размењују информације о позицији, брзини и вектору силе. Користећи CSP потребно је решити овај проблем користећи торбу послова за дохватање посла и синхронизацију на баријери у свакој итерацији. Потребно је реализовати следеће процесе: ''Worker'' (обавља израчунавање), ''Bag'' (обавља поделу посла) и ''Collector'' (обавља прикупљање резултата). Број процеса ''Worker'' није познат, али је познато да их има мање од N. Постоји тачно један процес ''Bag'' и тачно један процес ''Collector''.

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

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