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

Fedja: kategorija zadatka

2023-02-11T17:05:43Z

kategorija zadatka

← Старија измена		Верзија на датум 11. фебруар 2023. у 19:05
Ред 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. задатак\|Синхронизациони_алгоритми}} ==
	=== Поставка ===		=== Поставка ===
	Написати и објасните<sup>[sic]</sup> ''CLH'' алгоритам за критичну секцију (''coarse grain''). Реализовати (''fine grain'') верзију алгоритма уколико би на датом процесору постојала операција SWAP која би недељиво обављала замену вредности два операнда (<code>SWAP(var1, var2): < temp = var1; var1 = var2; var2 = temp; ></code>). Објаснити зашто је то правична (''fair'') критична секција.		Написати и објасните<sup>[sic]</sup> ''CLH'' алгоритам за критичну секцију (''coarse grain''). Реализовати (''fine grain'') верзију алгоритма уколико би на датом процесору постојала операција SWAP која би недељиво обављала замену вредности два операнда (<code>SWAP(var1, var2): < temp = var1; var1 = var2; var2 = temp; ></code>). Објаснити зашто је то правична (''fair'') критична секција.

Fedja: kategorije zadataka

2023-02-11T02:55:33Z

kategorije zadataka

← Старија измена		Верзија на датум 11. фебруар 2023. у 04:55
Ред 42:		Ред 42:
	Ова критична секција је правична јер ће први процес који уради замену (изврши SWAP инструкцију) бити први који ће ући у критичну секцију.		Ова критична секција је правична јер ће први процес који уради замену (изврши SWAP инструкцију) бити први који ће ући у критичну секцију.

	== 2. задатак ==		== {{категорија\|2. задатак\|Семафори}} ==
	=== Поставка ===		=== Поставка ===
	Посматра се један паркинг. Постоји само једна рампа која служи и за улаз на паркинг, и за излаз са паркинга, кроз коју може пролазити само један аутомобил у једном тренутку. На паркингу има N места за паркирање. Аутомобили који улазе, могу да уђу, један по један, уколико има слободних места. Уколико нема слободног места, проверава се да ли има аутомобила који хоће да изађу. Ако након изласка свих аутомобила који желе да изађу и уласка аутомобила који су дошли пре њега за аутомобил неће бити места, он одлази у потрагу за другим паркингом. Аутомобили при изласку плаћају услуге паркинга и излазе један по један. На почетку предност на рампи имају аутомобили који излазе са паркинга. Након што кроз рампу изађе K узастопних аутомобила, приоритет се мења (додељује се већи приоритет онима који улазе). Након проласка K узастопних аутомобила који улазе, приоритет се поново мења. Ако нема аутомобила из смера који има приоритет, аутомобили који немају приоритетни смер смеју да пролазе кроз рампу. Коришћењем једног низа од 2N + 1 семафора направити методе за тражење дозвола за улаз и излаз и обавештавање о уласку и изласку аутомобила са паркинга. Није дозвољено користити помоћне структуре података ни додатне елементе за синхронизацију процеса. Аутомобили не смеју да се претичу.		Посматра се један паркинг. Постоји само једна рампа која служи и за улаз на паркинг, и за излаз са паркинга, кроз коју може пролазити само један аутомобил у једном тренутку. На паркингу има N места за паркирање. Аутомобили који улазе, могу да уђу, један по један, уколико има слободних места. Уколико нема слободног места, проверава се да ли има аутомобила који хоће да изађу. Ако након изласка свих аутомобила који желе да изађу и уласка аутомобила који су дошли пре њега за аутомобил неће бити места, он одлази у потрагу за другим паркингом. Аутомобили при изласку плаћају услуге паркинга и излазе један по један. На почетку предност на рампи имају аутомобили који излазе са паркинга. Након што кроз рампу изађе K узастопних аутомобила, приоритет се мења (додељује се већи приоритет онима који улазе). Након проласка K узастопних аутомобила који улазе, приоритет се поново мења. Ако нема аутомобила из смера који има приоритет, аутомобили који немају приоритетни смер смеју да пролазе кроз рампу. Коришћењем једног низа од 2N + 1 семафора направити методе за тражење дозвола за улаз и излаз и обавештавање о уласку и изласку аутомобила са паркинга. Није дозвољено користити помоћне структуре података ни додатне елементе за синхронизацију процеса. Аутомобили не смеју да се претичу.

Lukahrvacevic: /* Prepravka indeksa semafora u signal() */

2022-04-01T11:54:38Z

Prepravka indeksa semafora u signal()

← Старија измена		Верзија на датум 1. април 2022. у 13:54
Ред 117:		Ред 117:
	bool signalEnter = (entering > 0 && hasCapacity) && (!priority \|\| exiting == 0);		bool signalEnter = (entering > 0 && hasCapacity) && (!priority \|\| exiting == 0);
	if (signalExit) {		if (signalExit) {
	semIndex = exitHead;		semIndex = exitHead + N;
	exitHead = (exitHead + 1) % N;		exitHead = (exitHead + 1) % N;
	} else if (signalEnter) {		} else if (signalEnter) {
	semIndex = enterHead;		semIndex = enterHead;
	~~exitHead~~ = (enterHead + 1) % N;		enterHead = (enterHead + 1) % N;
	}		}
	if (semIndex >= 0) {		if (semIndex >= 0) {

KockaAdmiralac: Ispravka uslova za odlazak automobila

2022-04-01T08:22:01Z

Ispravka uslova za odlazak automobila

← Старија измена		Верзија на датум 1. април 2022. у 10:22
Ред 52:		Ред 52:

	sem sems[2 * N + 1];		sem sems[2 * N + 1];
			// Број слободних места на паркингу (аутомобили који чекају излаз су ослободили своје место)
	int capacity = N;		int capacity = N;
			// Број аутомобила који чекају на улазу
	int entering = 0;		int entering = 0;
			// Број аутомобила који чекају на излазу
	int exiting = 0;		int exiting = 0;
	int enterTail = 0;		int enterTail = 0;
Ред 65:		Ред 68:
	bool requestEntrance() {		bool requestEntrance() {
	mutex.wait();		mutex.wait();
	if (capacity - entering ~~+ exiting~~ <= 0) {		if (capacity - entering <= 0) {
	mutex.signal();		mutex.signal();
	return false;		return false;

KockaAdmiralac: Nema potrebe za klasom ovde

2022-03-31T14:12:14Z

Nema potrebe za klasom ovde

Прикажи измене

KockaAdmiralac: Moja rešenja K1 2020

2022-03-31T13:51:22Z

Moja rešenja K1 2020

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

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

== 1. задатак ==
=== Поставка ===
Написати и објасните<sup>[sic]</sup> ''CLH'' алгоритам за критичну секцију (''coarse grain''). Реализовати (''fine grain'') верзију алгоритма уколико би на датом процесору постојала операција SWAP која би недељиво обављала замену вредности два операнда (<code>SWAP(var1, var2): < temp = var1; var1 = var2; var2 = temp; ></code>). Објаснити зашто је то правична (''fair'') критична секција.

=== Решење ===
''CLH'' алгоритам уланчава процесе који желе да уђу у критичну секцију у неку врсту уланчане листе, тако да сваки проверава да ли је онај пре њега и даље закључан и у тренутку када више не буде закључан улази у критичну секцију.
<syntaxhighlight lang="cpp">
Node* tail = nullptr;

void worker() {
while (true) {
Node* node = new Node();
node->locked = true;
< prev = tail; tail = node; >
< await (prev == nullptr || !prev->locked); >
// Критична секција
node->locked = false;
// Некритична секција
}
}
</syntaxhighlight>
Пошто је <code>prev</code> овде локална променљива и ту нема критичне референце, <code>await</code> се може заменити обичном петљом. Са друге стране, за атомску акцију <code>prev = tail; tail = node;</code> потребна нам је поменута SWAP инструкција:
<syntaxhighlight lang="cpp">
Node* tail = nullptr;

void worker() {
while (true) {
Node* node = new Node();
node->locked = true;
Node* prev = node;
SWAP(prev, tail);
while (prev != nullptr && prev->locked) skip();
// Критична секција
node->locked = false;
// Некритична секција
}
}
</syntaxhighlight>
Ова критична секција је правична јер ће први процес који уради замену (изврши SWAP инструкцију) бити први који ће ући у критичну секцију.

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

=== Решење ===
<syntaxhighlight lang="cpp">
const int N = 100;
const int K = 50;

class Car {
sem sems[2 * N + 1];
int capacity = N;
int entering = 0;
int exiting = 0;
int enterTail = 0;
int enterHead = 0;
int exitTail = 0;
int exitHead = 0;
// true - излаз, false - улаз
bool priority = true;
int passed = 0;
sem& mutex = sems[2 * N];
public:
bool requestEntrance() {
mutex.wait();
if (capacity - entering + exiting <= 0) {
mutex.signal();
return false;
}
++entering;
if (entering == 1 && exiting == 0) {
// Слободан пролаз
mutex.signal();
return true;
}
int semIndex = enterTail;
enterTail = (enterTail + 1) % N;
mutex.signal();
sems[semIndex].wait();
return true;
}
void requestExit() {
mutex.wait();
++capacity;
++exiting;
if (entering == 0 && exiting == 1) {
// Слободан пролаз
mutex.signal();
return;
}
int semIndex = exitTail + N;
exitTail = (exitTail + 1) % N;
mutex.signal();
sems[semIndex].wait();
}
void entered() {
mutex.wait();
--entering;
--capacity;
signal();
mutex.signal();
}
void exited() {
mutex.wait();
--exiting;
signal();
mutex.signal();
}
void signal() {
int semIndex = -1;
bool hasCapacity = (capacity - exiting) < N;
bool signalExit = (exiting > 0) && (priority || !hasCapacity || entering == 0);
bool signalEnter = (entering > 0 && hasCapacity) && (!priority || exiting == 0);
if (signalExit) {
semIndex = exitHead;
exitHead = (exitHead + 1) % N;
} else if (signalEnter) {
semIndex = enterHead;
exitHead = (enterHead + 1) % N;
}
if (semIndex >= 0) {
if (priority != signalExit) {
// Ако сада није изашао аутомобил из реда који је имао приоритет,
// ресетује се бројач узастопних аутомобила
passed = 0;
} else {
++passed;
}
if (passed == K) {
passed = 0;
priority = !priority;
}
sems[semIndex].signal();
}
}
void run() {
while (true) {
if (requestEntrance()) {
entered();
// ...
requestExit();
// pay();
exited();
}
}
}
};
</syntaxhighlight>

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