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

Fedja: kategorija zadatka

2023-02-11T17:06:57Z

kategorija zadatka

← Старија измена		Верзија на датум 11. фебруар 2023. у 19:06
Ред 2:		Ред 2:
	<!-- Поставка овог рока може се наћи са [https://rti.etf.bg.ac.rs/rti/ir3kdp/rokovi/2122/KDP_2022_feb.pdf странице предмета.] -->		<!-- Поставка овог рока може се наћи са [https://rti.etf.bg.ac.rs/rti/ir3kdp/rokovi/2122/KDP_2022_feb.pdf странице предмета.] -->

	== 1. задатак ==		== {{категорија\|1. задатак\|Синхронизациони_алгоритми}} ==
	=== Поставка ===		=== Поставка ===
	Написати и објасните<sup>[sic]</sup> Андерсенов алгоритам за критичну секцију (''coarse grain''). Реализовати (''fine grain'') верзију алгоритма уколико би на датом процесору умест ''FA'' постојала операција ''Compare-And-Swap'' која би недељиво обављала (<syntaxhighlight lang="cpp" inline>CAS(a, b, c) : < if (a == c) { c = b; return true; } else { a = c; return false; } ></syntaxhighlight>).		Написати и објасните<sup>[sic]</sup> Андерсенов алгоритам за критичну секцију (''coarse grain''). Реализовати (''fine grain'') верзију алгоритма уколико би на датом процесору умест ''FA'' постојала операција ''Compare-And-Swap'' која би недељиво обављала (<syntaxhighlight lang="cpp" inline>CAS(a, b, c) : < if (a == c) { c = b; return true; } else { a = c; return false; } ></syntaxhighlight>).

Fedja: kategorije zadataka

2023-02-11T02:56:11Z

kategorije zadataka

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

	== 2. задатак ==		== {{категорија\|2. задатак\|Семафори}} ==
	=== Поставка ===		=== Поставка ===
	Посматра се забавни парк са N аутића који могу да приме по једну особу (''Bumper Cars Problem''). M особа се шета по парку и може да одлучи да се провоза. Особа која жели да се вози стаје у ред и чека слободни ауто. Када се ослободи ауто и претходни возач напусти ауто прва особа из реда добија прилику да вози ауто и да се судара са другим аутима. Након неког времена особа завршава вожњу, враћа ауто на одговарајуће место, напушта ауто и одлази да се шета по парку. Особа може више пута да дође да се вози. Уколико постоји више аута, особа бира онај који је најдуже чекао на вожњу. Уколико тренутно нема особа које желе да се возе ауто стаје у ред и чека да дође особа. Користећи семафоре написати програм који решава овај проблем.		Посматра се забавни парк са N аутића који могу да приме по једну особу (''Bumper Cars Problem''). M особа се шета по парку и може да одлучи да се провоза. Особа која жели да се вози стаје у ред и чека слободни ауто. Када се ослободи ауто и претходни возач напусти ауто прва особа из реда добија прилику да вози ауто и да се судара са другим аутима. Након неког времена особа завршава вожњу, враћа ауто на одговарајуће место, напушта ауто и одлази да се шета по парку. Особа може више пута да дође да се вози. Уколико постоји више аута, особа бира онај који је најдуже чекао на вожњу. Уколико тренутно нема особа које желе да се возе ауто стаје у ред и чека да дође особа. Користећи семафоре написати програм који решава овај проблем.

KockaAdmiralac: Moja rešenja kolokvijuma od danas

2022-04-01T21:23:47Z

Moja rešenja kolokvijuma od danas

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

{{tocright}}


== 1. задатак ==
=== Поставка ===
Написати и објасните<sup>[sic]</sup> Андерсенов алгоритам за критичну секцију (''coarse grain''). Реализовати (''fine grain'') верзију алгоритма уколико би на датом процесору умест ''FA'' постојала операција ''Compare-And-Swap'' која би недељиво обављала (<syntaxhighlight lang="cpp" inline>CAS(a, b, c) : < if (a == c) { c = b; return true; } else { a = c; return false; } ></syntaxhighlight>).

=== Решење ===
''Coarse-grain'':
<syntaxhighlight lang="cpp">
const int N = 100;
int slot = 0;
bool slots[N];

void worker(int id) {
while (true) {
< int myslot = slot; slot = slot % N + 1; >
< await (slots[myslot]); >
// Критична секција
< slots[myslot] = false;
slots[myslot % N + 1] = true; >
// Некритична секција
}
}
</syntaxhighlight>
''Fine-grain'':
<syntaxhighlight lang="cpp">
const int N = 100;
int slot = 0;
bool slots[N];

void worker(int id) {
while (true) {
int myslot = slot;
while (!CAS(myslot, myslot % N + 1, slot)) skip();
while (!slots[myslot]) skip();
// Критична секција
slots[myslot] = false;
slots[myslot % N + 1] = true;
// Некритична секција
}
}
</syntaxhighlight>

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

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

// Комуникација између аутомобила и особа
sem carSems[N];
sem peopleSems[M];
// Међусобно искључивање при приступу глобалном стању
sem mutex = 1;
// Подаци заштићени mutex-ом:
list<int> freeCars;
list<int> freePeople;
int mutexId;

void car(int carId) {
int personId;
while (true) {
mutex.wait();
if (freePeople.size() > 0) {
personId = freePeople.front();
freePeople.pop_front();
mutexId = carId;
peopleSems[personId].signal();
// Нема ослобађања mutex, чекамо да особа прочита mutexId
carSems[carId].wait();
} else {
freeCars.push_back(carId);
mutex.signal();
carSems[carId].wait();
personId = mutexId;
// Ослобађамо mutex који је особа закључала
mutex.signal();
// Обавештавамо особу да смо прочитали mutexId
peopleSems[personId].signal();
}
// Особа контролише ауто, чекамо да нас особа обавести кад заврши
carSems[carId].wait();
// Враћени смо назад
}
}

void person(int personId) {
int carId;
while (true) {
// Шетамо
mutex.wait();
if (freeCars.size() > 0) {
carId = freeCars.front();
freeCars.pop_front();
mutexId = personId;
carSems[carId].signal();
// Нема ослобађања mutex, чекамо да аутомобил прочита mutexId
peopleSems[personId].wait();
} else {
freePeople.push_back(personId);
mutex.signal();
peopleSems[personId].wait();
carId = mutexId;
// Ослобађамо mutex који је аутомобил закључао
mutex.signal();
// Обавештавамо аутомобил да смо прочитали mutexId
carSems[carId].signal();
}
// Возимо и на крају обавестимо аутомобил да смо завршили
carSems[carId].signal();
// Настављамо шетњу
}
}
</syntaxhighlight>

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