КДП/К 2019

2023-11-12T21:00:56Z

Uros Velimirovic: /* Решење */

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

== {{категорија|1. задатак|Семафори}} ==
=== Поставка ===
Решити проблем читалаца и писаца (''Reader Writers Problem'') користећи семафоре. Обезбедити да процеси започињу приступ ресурсу по редоследу слања захтева. Претпоставити да у неком тренутку максимално N процеса може упутити захтев за приступ ресурсу.

=== Решење ===
<syntaxhighlight lang="cpp">
const int N = 100;
// Један више како бисмо могли да користимо проверу head == tail
// да бисмо видели да ли је листа празна
sem sems[N + 1];
bool isReader[N + 1];
int head = 0;
int tail = 0;
sem mutex;
// count == -1 => писац
int count = 0;

void read();
void write();

void reader() {
mutex.wait();
if (head == tail && count >= 0) {
// Ако је листа празна значи да сигурно немамо писаца у њој
++count;
mutex.signal();
} else {
int index = tail;
tail = (tail + 1) % (N + 1);
isReader[index] = true;
mutex.signal();
sems[index].wait();
}
read();
mutex.wait();
if (--count == 0 && head != tail) {
// Следећи мора да је писац, јер да је читалац листа би била празна
count = -1;
sems[head].signal();
head = (head + 1) % (N + 1);
}
mutex.signal();
}

void writer() {
mutex.wait();
if (head == tail && count == 0) {
// Ако нема читалаца нити писаца и листа је празна, можемо само да прођемо
--count;
mutex.signal();
} else {
int index = tail;
tail = (tail + 1) % (N + 1);
isReader[index] = false;
mutex.signal();
sems[index].wait();
}
write();
mutex.wait();
if (head == tail) {
// Нико више не чека
count = 0;
} else if (isReader[head]) {
// Чекају читаоци иза писца
count = 0;
while (isReader[head] && head != tail) {
++count;
sems[head].signal();
head = (head + 1) % (N + 1);
}
} else {
// Чека писац иза писца
sems[head].signal();
head = (head + 1) % (N + 1);
}
mutex.signal();
}
</syntaxhighlight>

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

Написати монитор са ''signal and continue'' дисциплином који има следеће методе: <syntaxhighlight lang="java" inline>boolean trazim_ulaz()</syntaxhighlight>, за тражење дозволе за улаз у гаражу, која враћа <code>true</code> ако се дозвољава улаз у гаражу, а <code>false</code> ако нема места; <syntaxhighlight lang="java" inline>void usao()</syntaxhighlight>, за обавештавање о уласку у гаражу; <syntaxhighlight lang="java" inline>void trazim_izlaz()</syntaxhighlight> за тражење дозволе за изласком из гараже; <syntaxhighlight lang="java" inline>void izasao()</syntaxhighlight> за обавештавање о изласку из гараже.

=== Решење ===
<syntaxhighlight lang="java">
class PodzemnaGaraza {
private static final int N = 100;
private int ulazi = 0;
private int izlazi = 0;
private int parkirano = 0;
private boolean rampaZauzeta = false;
private Condition ulaziRed = new Condition();
private Condition izlaziRed = new Condition();
public synchronized boolean trazim_ulaz() {
if (parkirano + ulazi == N) {
return false;
}
++ulazi;
if (!ulaziRed.queue() && !izlaziRed.queue() && !rampaZauzeta) {
// Нема никога, улазимо
rampaZauzeta = true;
return true;
}
ulaziRed.wait();
// rampaZauzeta је постављена од стране нити која сигнлизира
return true;
}
public synchronized void usao() {
++parkirano;
--ulazi;
signal();
}
public synchronized void trazim_izlaz() {
++izlazi;
--parkirano;
if (!izlaziRed.queue() && !rampaZauzeta) {
rampaZauzeta = true;
return;
}
izlaziRed.wait();
// rampaZauzeta је постављена од стране нити која сигнлизира
}
public synchronized void izasao() {
--izlazi;
signal();
}
private void signal() {
rampaZauzeta = false;
if (izlaziRed.queue()) {
rampaZauzeta = true;
izlaziRed.signal();
} else if (ulaziRed.queue() && parkirano + izlazi < N) {
rampaZauzeta = true;
ulaziRed.signal();
}
}
}
</syntaxhighlight>

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

SI Wiki - Кориснички доприноси [sr]

КДП/К 2019