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

Kmeeth: Исправљена грешка у функцији за налажење десне виљушке

2023-05-11T21:36:47Z

Исправљена грешка у функцији за налажење десне виљушке

← Старија измена		Верзија на датум 11. мај 2023. у 23:36
Ред 17:		Ред 17:
	}		}
	private int right(int id) {		private int right(int id) {
	return id + 1;		return (id + 1) % id;
	}		}
	public synchronized void acquireForks(int id) {		public synchronized void acquireForks(int id) {

Fedja: kategorije zadataka

2023-02-11T02:56:53Z

kategorije zadataka

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

	== 1. задатак ==		== {{категорија\|1. задатак\|Монитори}} ==
	=== Поставка ===		=== Поставка ===
	Проблем филозофа који ручавају (''Dining Philosophers Problem''). Решити проблем филозофа који ручавају користећи мониторе са ''signal and wait'' дисциплином. Филозофи који су раније изразили жељу за храном треба раније да буду опслужени.		Проблем филозофа који ручавају (''Dining Philosophers Problem''). Решити проблем филозофа који ручавају користећи мониторе са ''signal and wait'' дисциплином. Филозофи који су раније изразили жељу за храном треба раније да буду опслужени.
Ред 44:		Ред 44:
	</syntaxhighlight>		</syntaxhighlight>

	== 2. задатак ==		== {{категорија\|2. задатак\|Региони}} ==
	=== Поставка ===		=== Поставка ===
	У берберници раде два берберина, Аца и Браца, постоји 10 столица за чекање и још петоро муштерија може да стоји и чека. Муштерије које долазе се изјашњавају да ли чекају код Аце или Браце или им је свеједно ко ће да их услужи. Ако муштерија види да нема места у берберници и не може бити услужена, одлази. Када је берберин слободан, муштерија која је најдуже чекала ће прва бити услужена (осим ако чека на другог берберина и тада тражимо следећу муштерију у низу). Када се ослободи столица за чекање, муштерија која је најдуже стајала треба да седне. Уколико је неки од берберина беспослен, он спава, и прва муштерија која код њега дође на ред треба да га пробуди и буде услужена. Користећи условне критичне регионе решити овај проблем.		У берберници раде два берберина, Аца и Браца, постоји 10 столица за чекање и још петоро муштерија може да стоји и чека. Муштерије које долазе се изјашњавају да ли чекају код Аце или Браце или им је свеједно ко ће да их услужи. Ако муштерија види да нема места у берберници и не може бити услужена, одлази. Када је берберин слободан, муштерија која је најдуже чекала ће прва бити услужена (осим ако чека на другог берберина и тада тражимо следећу муштерију у низу). Када се ослободи столица за чекање, муштерија која је најдуже стајала треба да седне. Уколико је неки од берберина беспослен, он спава, и прва муштерија која код њега дође на ред треба да га пробуди и буде услужена. Користећи условне критичне регионе решити овај проблем.

KockaAdmiralac: Rešenja oba zadatka i to je to od mene

2022-05-15T11:45:24Z

Rešenja oba zadatka i to je to od mene

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

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

== 1. задатак ==
=== Поставка ===
Проблем филозофа који ручавају (''Dining Philosophers Problem''). Решити проблем филозофа који ручавају користећи мониторе са ''signal and wait'' дисциплином. Филозофи који су раније изразили жељу за храном треба раније да буду опслужени.

=== Решење ===
<syntaxhighlight lang="java">
class DiningPhilosophers {
public static final int N = 10;
boolean forks[] = new boolean[N];
Condition queue = new Condition();
int ticket = 1;
private int left(int id) {
return id;
}
private int right(int id) {
return id + 1;
}
public synchronized void acquireForks(int id) {
if (queue.queue() || forks[left(id)] || forks[right(id)]) {
queue.wait((ticket++) * N + id);
}
forks[left(id)] = true;
forks[right(id)] = true;
signal();
}
public synchronized void releaseForks(int id) {
forks[left(id)] = false;
forks[right(id)] = false;
signal();
}
private void signal() {
if (queue.empty()) {
return;
}
int id = queue.minrank() % N;
if (!forks[left(id)] && !forks[right(id)]) {
queue.signal();
}
}
}
</syntaxhighlight>

== 2. задатак ==
=== Поставка ===
У берберници раде два берберина, Аца и Браца, постоји 10 столица за чекање и још петоро муштерија може да стоји и чека. Муштерије које долазе се изјашњавају да ли чекају код Аце или Браце или им је свеједно ко ће да их услужи. Ако муштерија види да нема места у берберници и не може бити услужена, одлази. Када је берберин слободан, муштерија која је најдуже чекала ће прва бити услужена (осим ако чека на другог берберина и тада тражимо следећу муштерију у низу). Када се ослободи столица за чекање, муштерија која је најдуже стајала треба да седне. Уколико је неки од берберина беспослен, он спава, и прва муштерија која код њега дође на ред треба да га пробуди и буде услужена. Користећи условне критичне регионе решити овај проблем.

=== Решење ===
<syntaxhighlight lang="cpp">
#include "common.h"
#include <map>
#include <queue>

using namespace std;

struct BarberShop {
// Додељивање идентификатора муштеријама по реду доласка
int ticket = 1;
// Идентификатор особе која седи у седишту, или 0 уколико нико не седи
int seat[2] = {0};
// Да ли је берберин завршио са шишањем и чека особу да плати
bool finished[2] = {false};
// std::map је подразумевано сортиран
map<int, int> waitingQueue;
// Редови чекања за муштерије код Аце, Браце и оне којима је свеједно
queue<int> barberQueue[3];
};
BarberShop shop;

const int ACA_ID = 0;
const int BRACA_ID = 1;
const int ANY_ID = 2;

void barber(int id) {
while (true) {
region (shop) {
// Спавамо док чекамо да прва особа која дође седне на столицу
await (shop.seat[id] != 0);
}
// Шишање
region (shop) {
// Завршено шишање, чекамо на плаћање
shop.finished[id] = true;
await (!shop.finished[id]);
// Узимамо следећу муштерију
if (!shop.barberQueue[id].empty()) {
shop.seat[id] = shop.barberQueue[id].front();
shop.barberQueue[id].pop();
} else if (!shop.barberQueue[ANY_ID].empty()) {
shop.seat[id] = shop.barberQueue[ANY_ID].front();
shop.barberQueue[ANY_ID].pop();
} else {
shop.seat[id] = 0;
}
}
}
}

// Да ли је седиште за шишање код одређеног берберина тренутно резервисано за неку особу
int barberEquals(int barberId, int value) {
if (barberId == ACA_ID && shop.seat[ACA_ID] == value) {
return ACA_ID;
}
if (barberId == BRACA_ID && shop.seat[BRACA_ID] == value) {
return BRACA_ID;
}
if (barberId == ANY_ID) {
if (shop.seat[ACA_ID] == value) {
return ACA_ID;
}
if (shop.seat[BRACA_ID] == value) {
return BRACA_ID;
}
}
return -1;
}

int barberFree(int barberId) {
return barberEquals(barberId, 0);
}

void client(int barberId) {
region (shop) {
if (shop.waitingQueue.size() == 15 && barberFree(barberId) == -1) {
// Особа не може бити услужена
return;
}
int myTicket = shop.ticket++;
if (barberFree(barberId) != 1) {
// Без чекања седамо на столицу за шишање
shop.seat[barberFree(barberId)] = myTicket;
} else {
shop.barberQueue[barberId].push(myTicket);
// Овиме повећавамо shop.waitingQueue.size()
shop.waitingQueue[myTicket] = shop.waitingQueue.size();
// Чекамо на столицу за чекање или шишање
await (shop.waitingQueue[myTicket] < 10 || barberEquals(barberId, myTicket) != -1);
if (barberEquals(barberId, myTicket) == -1) {
// Седамо на столицу за чекање
await (barberEquals(barberId, myTicket) != -1);
}
// Устали смо са столице и смањујемо shop.waitingQueue.size
shop.waitingQueue.erase(myTicket);
int i = 0;
for (auto& it : shop.waitingQueue) {
shop.waitingQueue[it.first] = i++;
}
}
int barber = barberEquals(barberId, myTicket);
// Чекање током шишања
await (shop.finished[barber]);
// Плаћање
shop.finished[barber] = false;
}
}
</syntaxhighlight>

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