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

КДП/Јануар 2023

2026-06-20T08:05:32Z

Ralepop: /* {{категорија|2. задатак|Монитори}} */

{{tocright}}
'''Испит у јануарском испитном року 2023. године''' одржан је 18. јанаура. Поставка је доступна на [https://rti.etf.bg.ac.rs/rti/ir3kdp/rokovi/2223/IR3KDP_2023_jan.pdf страници предмета].

== {{категорија|1. задатак|Семафори}} ==
{{делимично решено}}
=== Поставка ===
Имплементирати и објасните основну разлику и разлоге за постојање те разлике између имплементација бафера коначног капацитета (<code>bounded buffer</code>) за случајеве 1 произвођач и 1 потрошач, као и M произвођача и N потрошача помоћу семафора. У складу са објашњењем, прикажите разлике и за случајеве M произвођача и 1 потрошач, као и 1 произвођач и N потрошача.
=== Решење ===
<syntaxhighlight lang="cpp">
// 1 произвођач и 1 потрошач
typeT buff[n];
int front = 0, rear = 0;
sem empty = n, full = 0;
// empty се користи као број празних места, а full као број попуњених места у баферу

process Producer{
while(true){
... //произведи податак
wait(empty); //чекај да бафер има празних места
buf[rear] = data; rear = (rear + 1)%n;
signal(full); //попуни једно место у баферу
...
}
}

process Consumer{
while(true){
... //потроши податак
wait(full); //чекај да бафер није празан
res = buf[front]; front = (front + 1)%n;
signal(empty); //ослободи једно место у баферу
...
}
}

//За M произвођача и N потрошача потребан нам је још један пар семафора - да се осигура да ће само један произвођач убацивати (deposit) у бафер, ерго да ће само један потрошач узимати (fetch) из бафера у било ком тренутку
typeT buff[n]; const M = ..., N = ...;
int front = 0, rear = 0;
sem empty = n, full = 0;
sem mutexD = 1, mutexF = 1; // за међусобно искључивање током deposit и fetch

process Producer[i = 1 to M]{
while(true){
... //произведи податак
wait(mutexD); wait(empty); //чекај да сам једини који убацује у бафер и да бафер има празних места
buf[rear] = data; rear = (rear + 1)%n;
signal(mutexD); signal(full); //допусти да неки други поризвођач убацује у бафер и попуни једно место у баферу
...
}
}

process Consumer[i = 1 to N]{
while(true){
... //потроши податак
wait(mutexF); wait(full);
res = buf[front]; front = (front + 1)%n;
signal(mutexF); signal(empty);
...
}
}

//За случај M произвођача и 1 потрошач није потребан семафор mutexF јер не постоји више потрошача који желе да узимају из бафера. Аналогно је за 1 произвођач и N потрошача.
</syntaxhighlight>

== {{категорија|2. задатак|Монитори}} ==
=== Поставка ===
Аутомобили који долазе са севера и југа морају да пређу реку преко неког старог моста (<code>Old Bridge problem</code>). На мосту постоји само једна возна трака, па сви аутомобили на мосту морају да се крећу у истом смеру. Због оптерећења моста које мост може да поднесе, број аутомобила који се налазе на мосту не сме да пређе K (K > 0). Написати монитор са <code>signal and continue</code> дисциплином који решава дати проблем.

=== Решење ===
<syntaxhighlight lang="cpp">
const K = ...;

monitor Bridge {
int waitingS = 0, waitingN = 0;
int cnt = 0; // тренутан број аутића на мосту
int dir = 0; // 0 - нико не чека и нико није на мосту, 1 - тренутно прелазе
// кола са севера, 2 - са југа
cond goN, goS;

void EnterNorth() {
waitingN++;
// Чекај ако прелазе кола са југа или ако је на мосту већ К аутића
while (dir == 2 || cnt == K) {
wait(goN);
}

waitingN--;
dir = 1;
cnt++;

// Ако има још места на мосту и има аутића који чекају - сигнализирај
if (cnt < K && goN.queue) {
signal(goN);
}
}

void ExitNorth() {
cnt--;
if (cnt == 0) { // мост је слободан
if (waitingS > 0) { // прво проверава супротан смер и препушта мост њима ако неко чека
dir = 2;
signal(goS);
} else if (waitingN > 0) {
dir = 1;
signal(goN);
} else {
dir = 0;
}
} else { // Мост није празан, ако неко чека на северу пропуштамо
if (waitingN > 0) {
signal(goN);
}
}
}

void EnterSouth() {
waitingS++;
while (dir == 1 || cnt == K) {
wait(goS);
}

waitingS--;
dir = 2;
cnt++;

if (cnt < K && goS.queue) {
signal(goS);
}
}

void ExitSouth() {
cnt--;
if (cnt == 0) {
if (waitingN > 0) {
dir = 1;
signal(goN);
} else if (waitingS > 0) {
dir = 2;
signal(goS);
} else {
dir = 0;
}
} else {
if (waitingS > 0) {
signal(goS);
}
}
}
}
</syntaxhighlight>

== {{категорија|3. задатак|CSP}} ==
=== Поставка ===
Решити проблем читалаца и писаца користећи ''CSP''. Решење треба да обезбеди да када стигне захтев од писца за тражење дозволе за започињање писања не треба прихватати захтеве за започињање било од читалаца било од писаца док тај писац не заврши са писањем.

=== Решење ===
<syntaxhighlight lang="pascal">
[reader(i:1..N)::READER || writer(i:1..M)::WRITER || conductor::CONDUCTOR]

READER :: *[
conductor!request
conductor!pass
// reading
conductor!done
]

WRITER :: *[
conductor!request
conductor!pass
// writing
conductor!done
]

CONDUCTOR :: [
read_count: integer = 0
write_count: integer = 0
queue: (0..C) integer
who: (0..C) char
head: integer = 0
tail: integer = 0
*[
head == tail, write_count == 0, (i:1..N) reader(i)?request ->
reader(i)!pass
read_count++
□
head == tail, write_count == 0, read_count == 0, (i:1..M) writer(i)?request ->
writer(i)!pass
write_count++
□
(head + 1) % N != tail, write_count + read_count != 0, (i:1..N) reader(i)?request ->
queue(head) = i
who(head) = 'r'
head = (head + 1) % N
□
(head + 1) % N != tail, write_count + read_count != 0, (i:1..M) writer(i)?request ->
queue(head) = i
who(head) = 'w'
head = (head + 1) % N
□
read_count == 1, (i:1..N) reader(i)?done ->
read_count--
*[
head != tail, write_count == 0, who[tail] == 'r' ->
reader(queue(tail))!pass
tail = (tail + 1) % N
read_count++
□
head != tail, write_count == 0, read_count == 0, who[tail] == 'w' ->
writer(queue(tail))!pass
tail = (tail + 1) % N
write_count++
]
□
read_count != 1, (i:1..N) reader(i)?done ->
read_count--
□
(i:1..M) writer(i)?done ->
write_count--
*[
head != tail, write_count == 0, who[tail] == 'r' ->
reader(queue(tail))!pass
tail = (tail + 1) % N
read_count++
□
head != tail, write_count == 0, read_count == 0, who[tail] == 'w' ->
writer(queue(tail))!pass
tail = (tail + 1) % N
write_count++
]
]
]
</syntaxhighlight>

== {{категорија|4. задатак|C-Linda}} ==
=== Поставка ===
Трајект за превоз возила превози возила са обале на обалу. Трајект поседује M трака од којих свака има N позиција које су линеарно постављене једна иза друге. Возило заузима једну позицију. Возило приликом доласка стаје у ред за случајно изабрану траку и чека на укрцавање. Нема могућности за престројавањем. Возила улазе у своју траку једно по једно по редоследу у којем чекају у траци, док на трајекту има места. Када је пун, трајект започиње превоз возила на другу обалу. На другој обали возила се искрцавају из своје траке у редоследу супротном од редоследа у којем су се укрцала у своју траку. Када се сва возила искрцају, празан трајект се враћа на почетну обалу. Користећи ''C-Linda'' написати програм који решава овај проблем.

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

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

КДП/Јануар 2023

2026-06-20T08:00:01Z

Ralepop: Dodate dve zasebne uslovne promenljive

{{tocright}}
'''Испит у јануарском испитном року 2023. године''' одржан је 18. јанаура. Поставка је доступна на [https://rti.etf.bg.ac.rs/rti/ir3kdp/rokovi/2223/IR3KDP_2023_jan.pdf страници предмета].

== {{категорија|1. задатак|Семафори}} ==
{{делимично решено}}
=== Поставка ===
Имплементирати и објасните основну разлику и разлоге за постојање те разлике између имплементација бафера коначног капацитета (<code>bounded buffer</code>) за случајеве 1 произвођач и 1 потрошач, као и M произвођача и N потрошача помоћу семафора. У складу са објашњењем, прикажите разлике и за случајеве M произвођача и 1 потрошач, као и 1 произвођач и N потрошача.
=== Решење ===
<syntaxhighlight lang="cpp">
// 1 произвођач и 1 потрошач
typeT buff[n];
int front = 0, rear = 0;
sem empty = n, full = 0;
// empty се користи као број празних места, а full као број попуњених места у баферу

process Producer{
while(true){
... //произведи податак
wait(empty); //чекај да бафер има празних места
buf[rear] = data; rear = (rear + 1)%n;
signal(full); //попуни једно место у баферу
...
}
}

process Consumer{
while(true){
... //потроши податак
wait(full); //чекај да бафер није празан
res = buf[front]; front = (front + 1)%n;
signal(empty); //ослободи једно место у баферу
...
}
}

//За M произвођача и N потрошача потребан нам је још један пар семафора - да се осигура да ће само један произвођач убацивати (deposit) у бафер, ерго да ће само један потрошач узимати (fetch) из бафера у било ком тренутку
typeT buff[n]; const M = ..., N = ...;
int front = 0, rear = 0;
sem empty = n, full = 0;
sem mutexD = 1, mutexF = 1; // за међусобно искључивање током deposit и fetch

process Producer[i = 1 to M]{
while(true){
... //произведи податак
wait(mutexD); wait(empty); //чекај да сам једини који убацује у бафер и да бафер има празних места
buf[rear] = data; rear = (rear + 1)%n;
signal(mutexD); signal(full); //допусти да неки други поризвођач убацује у бафер и попуни једно место у баферу
...
}
}

process Consumer[i = 1 to N]{
while(true){
... //потроши податак
wait(mutexF); wait(full);
res = buf[front]; front = (front + 1)%n;
signal(mutexF); signal(empty);
...
}
}

//За случај M произвођача и 1 потрошач није потребан семафор mutexF јер не постоји више потрошача који желе да узимају из бафера. Аналогно је за 1 произвођач и N потрошача.
</syntaxhighlight>

== {{категорија|2. задатак|Монитори}} ==
{{делимично решено}}
=== Поставка ===
Аутомобили који долазе са севера и југа морају да пређу реку преко неког старог моста (<code>Old Bridge problem</code>). На мосту постоји само једна возна трака, па сви аутомобили на мосту морају да се крећу у истом смеру. Због оптерећења моста које мост може да поднесе, број аутомобила који се налазе на мосту не сме да пређе K (K > 0). Написати монитор са <code>signal and continue</code> дисциплином који решава дати проблем.

=== Решење ===
<syntaxhighlight lang="cpp">
const K = ...;

monitor Bridge {
int waitingS = 0, waitingN = 0;
int cnt = 0; // тренутан број аутића на мосту
int dir = 0; // 0 - нико не чека и нико није на мосту, 1 - тренутно прелазе
// кола са севера, 2 - са југа
cond goN, goS;

void EnterNorth() {
waitingN++;
// Чекај ако прелазе кола са југа или ако је на мосту већ К аутића
while (dir == 2 || cnt == K) {
wait(goN);
}

waitingN--;
dir = 1;
cnt++;

// Ако има још места на мосту и има аутића који чекају - сигнализирај
if (cnt < K && goN.queue) {
signal(goN);
}
}

void ExitNorth() {
cnt--;
if (cnt == 0) { // мост је слободан
if (waitingS > 0) { // прво проверава супротан смер и препушта мост њима ако неко чека
dir = 2;
signal(goS);
} else if (waitingN > 0) {
dir = 1;
signal(goN);
} else {
dir = 0;
}
} else { // Мост није празан, ако неко чека на северу пропуштамо
if (waitingN > 0) {
signal(goN);
}
}
}

void EnterSouth() {
waitingS++;
while (dir == 1 || cnt == K) {
wait(goS);
}

waitingS--;
dir = 2;
cnt++;

if (cnt < K && goS.queue) {
signal(goS);
}
}

void ExitSouth() {
cnt--;
if (cnt == 0) {
if (waitingN > 0) {
dir = 1;
signal(goN);
} else if (waitingS > 0) {
dir = 2;
signal(goS);
} else {
dir = 0;
}
} else {
if (waitingS > 0) {
signal(goS);
}
}
}
}
</syntaxhighlight>

== {{категорија|3. задатак|CSP}} ==
=== Поставка ===
Решити проблем читалаца и писаца користећи ''CSP''. Решење треба да обезбеди да када стигне захтев од писца за тражење дозволе за започињање писања не треба прихватати захтеве за започињање било од читалаца било од писаца док тај писац не заврши са писањем.

=== Решење ===
<syntaxhighlight lang="pascal">
[reader(i:1..N)::READER || writer(i:1..M)::WRITER || conductor::CONDUCTOR]

READER :: *[
conductor!request
conductor!pass
// reading
conductor!done
]

WRITER :: *[
conductor!request
conductor!pass
// writing
conductor!done
]

CONDUCTOR :: [
read_count: integer = 0
write_count: integer = 0
queue: (0..C) integer
who: (0..C) char
head: integer = 0
tail: integer = 0
*[
head == tail, write_count == 0, (i:1..N) reader(i)?request ->
reader(i)!pass
read_count++
□
head == tail, write_count == 0, read_count == 0, (i:1..M) writer(i)?request ->
writer(i)!pass
write_count++
□
(head + 1) % N != tail, write_count + read_count != 0, (i:1..N) reader(i)?request ->
queue(head) = i
who(head) = 'r'
head = (head + 1) % N
□
(head + 1) % N != tail, write_count + read_count != 0, (i:1..M) writer(i)?request ->
queue(head) = i
who(head) = 'w'
head = (head + 1) % N
□
read_count == 1, (i:1..N) reader(i)?done ->
read_count--
*[
head != tail, write_count == 0, who[tail] == 'r' ->
reader(queue(tail))!pass
tail = (tail + 1) % N
read_count++
□
head != tail, write_count == 0, read_count == 0, who[tail] == 'w' ->
writer(queue(tail))!pass
tail = (tail + 1) % N
write_count++
]
□
read_count != 1, (i:1..N) reader(i)?done ->
read_count--
□
(i:1..M) writer(i)?done ->
write_count--
*[
head != tail, write_count == 0, who[tail] == 'r' ->
reader(queue(tail))!pass
tail = (tail + 1) % N
read_count++
□
head != tail, write_count == 0, read_count == 0, who[tail] == 'w' ->
writer(queue(tail))!pass
tail = (tail + 1) % N
write_count++
]
]
]
</syntaxhighlight>

== {{категорија|4. задатак|C-Linda}} ==
=== Поставка ===
Трајект за превоз возила превози возила са обале на обалу. Трајект поседује M трака од којих свака има N позиција које су линеарно постављене једна иза друге. Возило заузима једну позицију. Возило приликом доласка стаје у ред за случајно изабрану траку и чека на укрцавање. Нема могућности за престројавањем. Возила улазе у своју траку једно по једно по редоследу у којем чекају у траци, док на трајекту има места. Када је пун, трајект започиње превоз возила на другу обалу. На другој обали возила се искрцавају из своје траке у редоследу супротном од редоследа у којем су се укрцала у своју траку. Када се сва возила искрцају, празан трајект се враћа на почетну обалу. Користећи ''C-Linda'' написати програм који решава овај проблем.

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

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

КДП/К2 2019

2026-06-08T15:54:07Z

Ralepop: /* Решење */

{{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) % id;
}
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>

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

КДП/Лаб 1 2024

2026-06-04T11:30:13Z

Ralepop: /* Philosopher.java */

{{tocright}}

'''Прва лабораторијска вежба 2024. године''' одржана је 29. i 30. априла и носила је 10 бодова (3 бода Moodle 7 бодова задатак). Укупно је било 4 групе.

== Улазни тест Група 1 и 2 ==

=== 1. задатак ===
Уколико нит А позове a(), а нит Б позове b(), шта ће се десити са нити Б?

<syntaxhighlight lang="java">
public class A {
public synchronized void a() {
//neki kod ...
}

public synchronized void b() {
//neki kod..
}

A obj = new A();
}
</syntaxhighlight>

Одговор: <span class="spoiler" data-solution="text">Зауставиће се док се не изврши a()</span>

=== 2. задатак ===

Који од следећег су валидни начини да се иницијализује нит?

<div class="abc-list" data-solution="multiple">
# <syntaxhighlight lang="java">Runnable r = new Runnable() {
public void run(){ /*neki kod*/ }
};</syntaxhighlight>
# <syntaxhighlight lang="java" class="solution">Runnable r = new Runnable() {
public void run(){ /*neki kod*/}
};
Thread t = new Thread(r);</syntaxhighlight>
# <syntaxhighlight lang="java" class="solution">Thread t = new Thread();</syntaxhighlight>
# <syntaxhighlight lang="java" class="solution">public class Nit extends Thread {
public void run(){ /*neki kod*/ }
}
Nit t = new Nit();</syntaxhighlight>
# <syntaxhighlight lang="java" class="solution">Thread t = new Thread() {
public void run(){ /*neki kod*/ }
};</syntaxhighlight>
</div>

=== 3. задатак ===

Прва нит извршава <code>readMethod()</code> и закључала је <code>readLock</code>. Друга нит је позвала <code>writeMethod()</code>.

<syntaxhighlight lang="java">
public class LockExample {
private static final ReentrantReadWriteLock rwLock = new ReentrantReadWriteLock();

public void readMethod() {
rwLock.readLock().lock();
try {
// Neki kod...
} finally {
rwLock.readLock().unlock();
}
}

public void writeMethod() {
if (!rwLock.isWriteLocked()) {
rwLock.writeLock().lock();
try {
// Neki kod..
} finally {
rwLock.writeLock().unlock();
}
}
}
}

</syntaxhighlight>

Чему служи параметар у конструктору <code>ReentrantReadWriteLock</code>?
Одговор: <span class="spoiler" data-solution="text">FIFO Fairness</span>

Шта се дешава са другом нити?
Одговор: <span class="spoiler" data-solution="text">Блокира се на <code>writeLock</code></span>

== Улазни тест Групe 3 ==

=== 1. задатак ===
Када нит T увек трајно престаје да се извршава?

<div class="abc-list" data-solution="single">
# Када нит позове wait над неким објектом.
# <span class="solution">Када се заврши њена run метода.</span>
# Када позове своју interrupt методу.
# Ниједан од понуђених одговора.
</div>

=== 2. задатак ===

Који од наведених исказа су тачни?

<div class="abc-list" data-solution="multiple">
# <span class="solution"><code>ArrayBlockingQueue</code> je pogodan za rešavanje ProducerConsumer problema.</span>
# Za implementaciju <code>ProducerConsumer</code> problema, može se koristiti par metoda <code>add(E e) i remove()</code> objekta tipa <code>BlockingQueue</code>, bez dodatnih sinhronizacionih elemenata/direktiva.
# <span class="solution"> Za implementaciju <code>ProducerConsumer</code> problema, može se koristiti par metoda <code>putFirst(E e) i takeLast()</code> objekta tipa <code>BlockingDeque</code>, bez dodatnih sinhronizacionih elemenata/direktiva.</span>
# Za implementaciju <code>ProducerConsumer</code> problema, može se koristiti par metoda <code>transfer(E e) i take()</code> objekta tipa <code>TransferQueue</code>, bez dodatnih sinhronizacionih elemenata/direktiva.
# Za implementaciju <code>ProducerConsumer</code> problema, može se koristiti par metoda <code>putFirst(E e) i takeFirst()</code> objekta tipa <code>BlockingDeque</code>, bez dodatnih sinhronizacionih elemenata/direktiva.
</div>

=== 3. задатак ===

Уколико нит threadA тренутно извршава методу обј.а(), а потом нит threadB позива методу обј.б(), који од понуђених одговора су тачни, уколико је дат следећи део кода?

<syntaxhighlight lang="java">
public class A {
private ReentrantReadWriteLock rw = new ReentrantReadWriteLock(true);

public void a() {
try {
rw.readLock().lock();
// kritična sekcija A... // <- threadA
} finally {
rw.readLock().unlock();
}
}

public void b() {
try {
if (rw.getReadLockCount()==0) {
rw.writeLock().lock();
}
// kritična sekcija B...
} finally {
rw.writeLock().unlock();
}
}
}

A obj = new A();
</syntaxhighlight>

<div class="abc-list" data-solution="multiple">
# <span class="solution"> Десиће се грешка приликом извршавања.</span>
# Аргумент конструктора ReentrantReadWriteLock означава да могу две нити истовремено да позивају закључавање.
# <span class="solution">Нити А и Б могу истовремено да извршавају критичне секције у методама a() и b() (респективно).</span>
# Нит Б ће бити блокирана док нит А не заврши позив методе a().
# <span class="solution">Аргумент конструктора ReentrantReadWriteLock означава да ли ће се буђење нити обављати по FIFO принципу.</span>
# <span class="solution">Нит Б неће извршити закључавање, јер услов if-a није испуњен.</span>
</div>

== Улазни тест Групe 4 ==

=== 1. задатак ===

Који од следећег су валидни начини да се иницијализује нит?

<div class="abc-list" data-solution="multiple">
# <syntaxhighlight lang="java">Runnable r = new Runnable() {
public void run(){ /*neki kod*/ }
};</syntaxhighlight>
# <syntaxhighlight lang="java" class="solution">Runnable r = new Runnable() {
public void run(){ /*neki kod*/}
};
Thread t = new Thread(r);</syntaxhighlight>
# <syntaxhighlight lang="java" class="solution">Thread t = new Thread();</syntaxhighlight>
# <syntaxhighlight lang="java" class="solution">public class Nit extends Thread {
public void run(){ /*neki kod*/ }
}
Nit t = new Nit();</syntaxhighlight>
# <syntaxhighlight lang="java" class="solution">Thread t = new Thread() {
public void run(){ /*neki kod*/ }
};</syntaxhighlight>
</div>

=== 2. задатак ===

Који од наведених исказа су тачни?

<div class="abc-list" data-solution="multiple">
# <span class="solution"><code>ArrayBlockingQueue</code> je pogodan za rešavanje ProducerConsumer problema.</span>
# Za implementaciju <code>ProducerConsumer</code> problema, može se koristiti par metoda <code>add(E e) i remove()</code> objekta tipa <code>BlockingQueue</code>, bez dodatnih sinhronizacionih elemenata/direktiva.
# <span class="solution"> Za implementaciju <code>ProducerConsumer</code> problema, može se koristiti par metoda <code>putFirst(E e) i takeLast()</code> objekta tipa <code>BlockingDeque</code>, bez dodatnih sinhronizacionih elemenata/direktiva.</span>
# Za implementaciju <code>ProducerConsumer</code> problema, može se koristiti par metoda <code>transfer(E e) i take()</code> objekta tipa <code>TransferQueue</code>, bez dodatnih sinhronizacionih elemenata/direktiva.
# Za implementaciju <code>ProducerConsumer</code> problema, može se koristiti par metoda <code>putFirst(E e) i takeFirst()</code> objekta tipa <code>BlockingDeque</code>, bez dodatnih sinhronizacionih elemenata/direktiva.
</div>

=== 3. задатак ===

Како правилно осигурати међусобно искључивање критичне секције?

{{delimično rešeno}}

== Поставка Свих Група==

У зависности од групе било је потребно решити један од следећих проблема:

1. Решити <code>Atomic Broadcast</code> проблем користећи <code>AtomicInteger</code> и опционо <code>Semaphore</code> . Бафер садржи B елемената. Потребно је да програм буде максимално конкурентан и отпоран на прекиде.

2. Решити <code>H2O</code> проблем користећи <code>CyclicBarrier</code>. Потребно је да програм буде максимално конкурентан и отпоран на прекиде.

3. Решити <code>Dining Philosophers</code> проблем користећи <code>AtomicInteger</code> и регионе. филозофи који су раније изразили жељу за храном треба раније да буду опслужени . Потребно је да програм буде максимално конкурентан и отпоран на прекиде.

4. Решити <code>Child Care</code> проблем користећи <code>ConcurrentLinkedQueue</code> и друге произвољне синхронизационе директиве. Родитељ доводи једно или више деце у обданиште и чека све док се не појави место, како би оставио сву децу одједном и отишао. Родитељ може и да одведе једно или више деце, такође одједном. Мора се поштовати редослед доласка родитеља који остављају децу и васпитачица које одлазе са посла. Потребно је да програм буде максимално конкурентан и отпоран на прекиде.

== Решење за Atomic Broadcast ==

==== <code>Test.java</code> ====

<syntaxhighlight lang="java">

package rs.ac.bg.etf.kdp.lab12024G1;

import java.util.concurrent.Semaphore;
import java.util.concurrent.atomic.AtomicInteger;

public class Test {

private static final int consumersCount=3;
private static final int b=5;

public static void main(String[] args) {

AtomicInteger[][] reads = new AtomicInteger[b][consumersCount];

Semaphore mutex = new Semaphore(1);

AtomicInteger[] buffer = new AtomicInteger[b];

for (int i = 0; i < buffer.length; i++)
buffer[i] = new AtomicInteger(0);

Consumer[] consumers = new Consumer[consumersCount];

Producer p = new Producer(consumersCount, buffer, reads,b,mutex);
p.start();

for (int i = 0; i < b; i++)
for(int j=0;j<consumersCount;j++)
reads[i][j] = new AtomicInteger(0);

for (int i = 0; i < consumersCount; i++) {
consumers[i] = new Consumer(buffer, reads,b,mutex,i);
consumers[i].start();
}
}

}

</syntaxhighlight>

==== <code>Producer.java</code> ====

<syntaxhighlight lang="java">

package rs.ac.bg.etf.kdp.lab12024G1;

import java.util.concurrent.Semaphore;
import java.util.concurrent.atomic.AtomicInteger;

public class Producer extends Thread {

private final int consumers;
private AtomicInteger[] buffer;
private AtomicInteger[][] reads;
private Semaphore mutex;
private int b;

public Producer(int consumers, AtomicInteger[] buffer, AtomicInteger[][] reads, int bb, Semaphore mutex) {
this.consumers = consumers;
this.buffer = buffer;
this.reads = reads;
b=bb;
this.mutex = mutex;
}

@Override
public void run() {
for (int i = 0; i <b; i++) {
for (int j = 0; j < consumers; j++)
while(reads[i][j].get() == 1)
Thread.onSpinWait();

int rand = (int)(Math.random() * 10);
System.out.println("Producer produced element: " + rand );
mutex.acquireUninterruptibly();
buffer[i].set(rand);
mutex.release();

mutex.acquireUninterruptibly();
for (int j2 = 0; j2 < consumers; j2++)
reads[i][j2].set(0);

mutex.release();
}
}

}
</syntaxhighlight>

==== <code>Consumer.java</code> ====

<syntaxhighlight lang="java">

package rs.ac.bg.etf.kdp.lab12024G1;

import java.util.concurrent.Semaphore;
import java.util.concurrent.atomic.AtomicInteger;

public class Consumer extends Thread {

private int id;
private AtomicInteger[][] reads;
private AtomicInteger[] buffer;
private Semaphore mutex;
private int b;

public Consumer(AtomicInteger[] buff, AtomicInteger[][] r, int bb,Semaphore mutex, int i) {
buffer = buff;
reads=r;
id=i;
this.mutex = mutex;
b=bb;
}

@Override
public void run() {
for (int i = 0; i < b; i++) {
while(reads[i][id].get() == 1)
Thread.onSpinWait();
mutex.acquireUninterruptibly();
int elem = buffer[i].get();
System.out.println("Consumer "+id+" consumed element "+elem +"from place "+i);
reads[i][id].set(1);
mutex.release();

try {
sleep((int)(Math.random()*2000));
} catch (InterruptedException e) {
throw new RuntimeException(e);
}

}
}

}
</syntaxhighlight>

== Решење за H2O ==

==== <code>Test.java</code> ====

<syntaxhighlight lang="java">
package H20;

import java.util.concurrent.CyclicBarrier;
import java.util.concurrent.atomic.AtomicInteger;

public class Test {
public static void main(String[] args) {
int cnt = 10;

Barrier barrier = new Barrier(new CyclicBarrier(3));

Hydrogen[] h = new Hydrogen[cnt*2];
Oxygen[] o = new Oxygen[cnt];

for(int i = 0; i < cnt; i++) {
o[i] = new Oxygen(barrier);
h[2*i] = new Hydrogen(barrier);
h[2*i + 1] = new Hydrogen(barrier);

o[i].start();
h[2*i].start();
h[2*i+1].start();
}

}
}
</syntaxhighlight>
==== <code>Oxygen.java</code> ====
<syntaxhighlight lang="java">
package H20;

import java.util.concurrent.BrokenBarrierException;
import java.util.concurrent.Semaphore;

public class Oxygen extends Thread {

Barrier barrier;

Oxygen(Barrier b){
barrier = b;
}

@Override
public void run() {
while(true) {
try {
Thread.sleep((int)(Math.random() * 4000));
} catch (InterruptedException e) {}

barrier.oxygen.acquireUninterruptibly();

barrier.oCount++;

try {
System.out.println("Kiseonik pristigao na barijeru");

if(barrier.barrier.await() == 0) {
System.out.println("\nFORMIRANJE VODE!\n");

barrier.hCount = 0;
barrier.oCount = 1;

barrier.hydrogen.release(2);
barrier.oxygen.release(1);
}

} catch (InterruptedException | BrokenBarrierException e) {
e.printStackTrace();
}

}
}

}

</syntaxhighlight>

==== <code>Hydrogen.java</code> ====

<syntaxhighlight lang="java">
package H20;

import java.util.concurrent.BrokenBarrierException;
import java.util.concurrent.Semaphore;

public class Hydrogen extends Thread {

Barrier barrier;

Hydrogen(Barrier b){
barrier = b;
}

@Override
public void run() {
while(true) {
try {
Thread.sleep((int)(Math.random() * 4000));
} catch (InterruptedException e) {}

barrier.hydrogen.acquireUninterruptibly();

barrier.hCount++;

try {
System.out.println("Vodonik pristigao na barijeru");

if(barrier.barrier.await() == 0) {
System.out.println("\nFORMIRANJE VODE!\n");
barrier.hCount = 0;
barrier.oCount = 1;

barrier.hydrogen.release(2);
barrier.oxygen.release(1);
}

} catch (InterruptedException | BrokenBarrierException e) {
e.printStackTrace();
}

}
}
}

</syntaxhighlight>

==== <code>Barrier.java</code> ====

<syntaxhighlight lang="java">
package H20;

import java.util.concurrent.CyclicBarrier;
import java.util.concurrent.Semaphore;

public class Barrier {
CyclicBarrier barrier;
Semaphore hydrogen, oxygen;
int hCount, oCount;

Barrier(CyclicBarrier cb){
barrier = cb;
hCount = 0;
oCount = 0;
hydrogen = new Semaphore(2);
oxygen = new Semaphore(1);
}

}
</syntaxhighlight>

== Решење за Dining Philosophers ==

==== <code>Test.java</code> ====

<syntaxhighlight lang="java">
package rs.ac.bg.etf.kdp.lab12024G3;

import java.util.concurrent.atomic.AtomicInteger;

public class Test {

public static final int N = 5;

public static void main(String[] args) {

Philosopher[] philosophers = new Philosopher[N];
AtomicInteger[] forks = new AtomicInteger[N];

for (int i = 0; i < forks.length; i++)
forks[i] = new AtomicInteger(1);

Table table = new Table();

for (int i = 0; i < N; i++) {
philosophers[i] = new Philosopher(forks, i, N, table);
philosophers[i].start();
}

}

}

</syntaxhighlight>
==== <code>Table.java</code> ====
<syntaxhighlight lang="java">
package rs.ac.bg.etf.kdp.lab12024G3;

import java.util.concurrent.atomic.AtomicInteger;

public class Table {

AtomicInteger ticket;
int next;

public Table() {
ticket = new AtomicInteger(0);
next = 0;
}

}

</syntaxhighlight>

==== <code>Philosopher.java</code> ====

<syntaxhighlight lang="java">
package rs.ac.bg.etf.kdp.lab12024G3;

import java.util.concurrent.atomic.AtomicInteger;

public class Philosopher extends Thread {

AtomicInteger[] forks;
int id,left,right,N,myTicket;
Table t;

public Philosopher(AtomicInteger[] forks, int id, int n,Table table) {
this.forks = forks;
this.id = id;
N = n;
left = id;
right = (id+1)%n;
t = table;
}

@Override
public void run() {
while(true) {
think();
run();
}
}

public void think() {
System.out.println("Philosopher "+id+" thinking");
try {
sleep((int)(Math.random() * 3000));
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}

public void eat() {
myTicket = t.ticket.getAndIncrement();
synchronized (forks) {

System.out.println("Philosopher "+id+" wants to eat");

while(forks[left].intValue() == 0 || forks[right].intValue() == 0 || myTicket != t.next)
try {
forks.wait();
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
System.out.println("Philosopher "+id+" started eating");
forks[left].set(0);
forks[right].set(0);

}

try {
sleep((int)(Math.random() * 2000));
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}

synchronized (forks) {

System.out.println("Philosopher "+id+" finished eating");
forks[left].set(1);
forks[right].set(1);
t.next++;
forks.notifyAll();
}
}
}

</syntaxhighlight>

== Решење за Child Care ==

==== <code>Test.java</code> ====

<syntaxhighlight lang="java">
package ChildCare;

public class Test {
public static void main(String[] args) {
Kindergarten k = new Kindergarten(12);
k.startProgram(4, 3);
}
}

</syntaxhighlight>
==== <code>Kindergarten.java</code> ====
<syntaxhighlight lang="java">
package ChildCare;

import java.util.concurrent.ConcurrentLinkedQueue;

public class Kindergarten {
int childrenInside = 0;
int teachersInside = 0;
int capacity;
public ConcurrentLinkedQueue<Integer> parentQueue;
public ConcurrentLinkedQueue<Integer> teacherQueue;
public Kindergarten(int capacity) {
parentQueue = new ConcurrentLinkedQueue<Integer>();
teacherQueue = new ConcurrentLinkedQueue<Integer>();
this.capacity = capacity;
}
public static boolean ruleFollowed(int teachers, int children, int capacity ) {
if(teachers == 0 || children > capacity) return false;
return teachers >= Math.ceil(children / 3.0);
}
public void startProgram(int teachersUsed, int parentsUsed) {
Teacher[] teachers = new Teacher[teachersUsed];
Parent[] parents = new Parent[parentsUsed];
for(int i = 0; i < teachersUsed; i++) {
teachers[i] = new Teacher(i, this);
teachers[i].start();
}
for(int i = 0; i < parentsUsed; i++) {
parents[i] = new Parent(i, this);
parents[i].start();
}

}
}

</syntaxhighlight>

==== <code>Teacher.java</code> ====

<syntaxhighlight lang="java">
package ChildCare;

import java.util.Random;
import java.util.concurrent.ConcurrentLinkedQueue;

public class Teacher extends Thread {
Kindergarten k;
int id;

public Teacher(int id, Kindergarten k) {
this.k = k;
this.id = id;
}
public void run() {
while(true) {
try {
Thread.sleep(new Random().nextInt(5000));
} catch (InterruptedException e) {
e.printStackTrace();
}
synchronized(k) {
k.teachersInside++;
System.out.println("Teacher " + id + " came to work.");
k.notifyAll();
}
try {
Thread.sleep(new Random().nextInt(5000));
} catch (InterruptedException e) {
e.printStackTrace();
}

synchronized(k) {
k.teacherQueue.add(id);
System.out.println("Teacher " + id + " wishes to leave work.");
while(!(k.teacherQueue.element() == id && Kindergarten.ruleFollowed(k.teachersInside - 1, k.childrenInside, k.capacity))) {
try {
k.wait();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
System.out.println("Teacher " + id + " has left work.");
k.teachersInside--;
k.teacherQueue.remove();
k.notifyAll();
}
}
}
}

</syntaxhighlight>

==== <code>Parent.java</code> ====

<syntaxhighlight lang="java">
package ChildCare;

import java.util.Random;
import java.util.concurrent.ConcurrentLinkedQueue;

public class Parent extends Thread {

boolean interacted = false;
Kindergarten k;
int id;
public Parent(int id, Kindergarten k) {
this.k = k;
this.id = id;
}
public void run() {

while(true) {
try {
Thread.sleep(new Random().nextInt(5000));
} catch (InterruptedException e) {
e.printStackTrace();
}
int childrenBrought = 1 + new Random().nextInt(4);
System.out.println("Parent " + id + " brought " + childrenBrought + " children.");
interacted = false;

synchronized(k) {
k.parentQueue.add(id);
while(!(k.parentQueue.peek() == id && Kindergarten.ruleFollowed(k.teachersInside, k.childrenInside + childrenBrought, k.capacity))) {
try {
k.wait();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
k.parentQueue.remove();
k.childrenInside += childrenBrought;
System.out.println("Parent " + id + " left his " + childrenBrought + " children.");
k.notifyAll();
}
while(childrenBrought > 0) {
try {
Thread.sleep(new Random().nextInt(5000));
} catch (InterruptedException e) {
e.printStackTrace();
}
int childrenToPickUp = 1 + (1 + new Random().nextInt(4)) % childrenBrought;
synchronized(k) {
k.childrenInside -= childrenToPickUp;
System.out.println("Parent " + id + " took home his " + childrenToPickUp + "/" + childrenBrought + " children.");
k.notifyAll();
}
childrenBrought -= childrenToPickUp;
}

}
}
}

</syntaxhighlight>

[[Категорија:КДП]]
[[Категорија:Лабораторијске вежбе]]

Корисник:Ralepop

2026-06-03T21:06:16Z

Ralepop: Уклоњено преусмерење на Корисник:Elar

unpaid-lilac-gizmo@duck.com

КДП/Лаб 1 2024

2026-06-03T21:05:14Z

Ralepop: /* Решење за Atomic Broadcast */

{{tocright}}

'''Прва лабораторијска вежба 2024. године''' одржана је 29. i 30. априла и носила је 10 бодова (3 бода Moodle 7 бодова задатак). Укупно је било 4 групе.

== Улазни тест Група 1 и 2 ==

=== 1. задатак ===
Уколико нит А позове a(), а нит Б позове b(), шта ће се десити са нити Б?

<syntaxhighlight lang="java">
public class A {
public synchronized void a() {
//neki kod ...
}

public synchronized void b() {
//neki kod..
}

A obj = new A();
}
</syntaxhighlight>

Одговор: <span class="spoiler" data-solution="text">Зауставиће се док се не изврши a()</span>

=== 2. задатак ===

Који од следећег су валидни начини да се иницијализује нит?

<div class="abc-list" data-solution="multiple">
# <syntaxhighlight lang="java">Runnable r = new Runnable() {
public void run(){ /*neki kod*/ }
};</syntaxhighlight>
# <syntaxhighlight lang="java" class="solution">Runnable r = new Runnable() {
public void run(){ /*neki kod*/}
};
Thread t = new Thread(r);</syntaxhighlight>
# <syntaxhighlight lang="java" class="solution">Thread t = new Thread();</syntaxhighlight>
# <syntaxhighlight lang="java" class="solution">public class Nit extends Thread {
public void run(){ /*neki kod*/ }
}
Nit t = new Nit();</syntaxhighlight>
# <syntaxhighlight lang="java" class="solution">Thread t = new Thread() {
public void run(){ /*neki kod*/ }
};</syntaxhighlight>
</div>

=== 3. задатак ===

Прва нит извршава <code>readMethod()</code> и закључала је <code>readLock</code>. Друга нит је позвала <code>writeMethod()</code>.

<syntaxhighlight lang="java">
public class LockExample {
private static final ReentrantReadWriteLock rwLock = new ReentrantReadWriteLock();

public void readMethod() {
rwLock.readLock().lock();
try {
// Neki kod...
} finally {
rwLock.readLock().unlock();
}
}

public void writeMethod() {
if (!rwLock.isWriteLocked()) {
rwLock.writeLock().lock();
try {
// Neki kod..
} finally {
rwLock.writeLock().unlock();
}
}
}
}

</syntaxhighlight>

Чему служи параметар у конструктору <code>ReentrantReadWriteLock</code>?
Одговор: <span class="spoiler" data-solution="text">FIFO Fairness</span>

Шта се дешава са другом нити?
Одговор: <span class="spoiler" data-solution="text">Блокира се на <code>writeLock</code></span>

== Улазни тест Групe 3 ==

=== 1. задатак ===
Када нит T увек трајно престаје да се извршава?

<div class="abc-list" data-solution="single">
# Када нит позове wait над неким објектом.
# <span class="solution">Када се заврши њена run метода.</span>
# Када позове своју interrupt методу.
# Ниједан од понуђених одговора.
</div>

=== 2. задатак ===

Који од наведених исказа су тачни?

<div class="abc-list" data-solution="multiple">
# <span class="solution"><code>ArrayBlockingQueue</code> je pogodan za rešavanje ProducerConsumer problema.</span>
# Za implementaciju <code>ProducerConsumer</code> problema, može se koristiti par metoda <code>add(E e) i remove()</code> objekta tipa <code>BlockingQueue</code>, bez dodatnih sinhronizacionih elemenata/direktiva.
# <span class="solution"> Za implementaciju <code>ProducerConsumer</code> problema, može se koristiti par metoda <code>putFirst(E e) i takeLast()</code> objekta tipa <code>BlockingDeque</code>, bez dodatnih sinhronizacionih elemenata/direktiva.</span>
# Za implementaciju <code>ProducerConsumer</code> problema, može se koristiti par metoda <code>transfer(E e) i take()</code> objekta tipa <code>TransferQueue</code>, bez dodatnih sinhronizacionih elemenata/direktiva.
# Za implementaciju <code>ProducerConsumer</code> problema, može se koristiti par metoda <code>putFirst(E e) i takeFirst()</code> objekta tipa <code>BlockingDeque</code>, bez dodatnih sinhronizacionih elemenata/direktiva.
</div>

=== 3. задатак ===

Уколико нит threadA тренутно извршава методу обј.а(), а потом нит threadB позива методу обј.б(), који од понуђених одговора су тачни, уколико је дат следећи део кода?

<syntaxhighlight lang="java">
public class A {
private ReentrantReadWriteLock rw = new ReentrantReadWriteLock(true);

public void a() {
try {
rw.readLock().lock();
// kritična sekcija A... // <- threadA
} finally {
rw.readLock().unlock();
}
}

public void b() {
try {
if (rw.getReadLockCount()==0) {
rw.writeLock().lock();
}
// kritična sekcija B...
} finally {
rw.writeLock().unlock();
}
}
}

A obj = new A();
</syntaxhighlight>

<div class="abc-list" data-solution="multiple">
# <span class="solution"> Десиће се грешка приликом извршавања.</span>
# Аргумент конструктора ReentrantReadWriteLock означава да могу две нити истовремено да позивају закључавање.
# <span class="solution">Нити А и Б могу истовремено да извршавају критичне секције у методама a() и b() (респективно).</span>
# Нит Б ће бити блокирана док нит А не заврши позив методе a().
# <span class="solution">Аргумент конструктора ReentrantReadWriteLock означава да ли ће се буђење нити обављати по FIFO принципу.</span>
# <span class="solution">Нит Б неће извршити закључавање, јер услов if-a није испуњен.</span>
</div>

== Улазни тест Групe 4 ==

=== 1. задатак ===

Који од следећег су валидни начини да се иницијализује нит?

<div class="abc-list" data-solution="multiple">
# <syntaxhighlight lang="java">Runnable r = new Runnable() {
public void run(){ /*neki kod*/ }
};</syntaxhighlight>
# <syntaxhighlight lang="java" class="solution">Runnable r = new Runnable() {
public void run(){ /*neki kod*/}
};
Thread t = new Thread(r);</syntaxhighlight>
# <syntaxhighlight lang="java" class="solution">Thread t = new Thread();</syntaxhighlight>
# <syntaxhighlight lang="java" class="solution">public class Nit extends Thread {
public void run(){ /*neki kod*/ }
}
Nit t = new Nit();</syntaxhighlight>
# <syntaxhighlight lang="java" class="solution">Thread t = new Thread() {
public void run(){ /*neki kod*/ }
};</syntaxhighlight>
</div>

=== 2. задатак ===

Који од наведених исказа су тачни?

<div class="abc-list" data-solution="multiple">
# <span class="solution"><code>ArrayBlockingQueue</code> je pogodan za rešavanje ProducerConsumer problema.</span>
# Za implementaciju <code>ProducerConsumer</code> problema, može se koristiti par metoda <code>add(E e) i remove()</code> objekta tipa <code>BlockingQueue</code>, bez dodatnih sinhronizacionih elemenata/direktiva.
# <span class="solution"> Za implementaciju <code>ProducerConsumer</code> problema, može se koristiti par metoda <code>putFirst(E e) i takeLast()</code> objekta tipa <code>BlockingDeque</code>, bez dodatnih sinhronizacionih elemenata/direktiva.</span>
# Za implementaciju <code>ProducerConsumer</code> problema, može se koristiti par metoda <code>transfer(E e) i take()</code> objekta tipa <code>TransferQueue</code>, bez dodatnih sinhronizacionih elemenata/direktiva.
# Za implementaciju <code>ProducerConsumer</code> problema, može se koristiti par metoda <code>putFirst(E e) i takeFirst()</code> objekta tipa <code>BlockingDeque</code>, bez dodatnih sinhronizacionih elemenata/direktiva.
</div>

=== 3. задатак ===

Како правилно осигурати међусобно искључивање критичне секције?

{{delimično rešeno}}

== Поставка Свих Група==

У зависности од групе било је потребно решити један од следећих проблема:

1. Решити <code>Atomic Broadcast</code> проблем користећи <code>AtomicInteger</code> и опционо <code>Semaphore</code> . Бафер садржи B елемената. Потребно је да програм буде максимално конкурентан и отпоран на прекиде.

2. Решити <code>H2O</code> проблем користећи <code>CyclicBarrier</code>. Потребно је да програм буде максимално конкурентан и отпоран на прекиде.

3. Решити <code>Dining Philosophers</code> проблем користећи <code>AtomicInteger</code> и регионе. филозофи који су раније изразили жељу за храном треба раније да буду опслужени . Потребно је да програм буде максимално конкурентан и отпоран на прекиде.

4. Решити <code>Child Care</code> проблем користећи <code>ConcurrentLinkedQueue</code> и друге произвољне синхронизационе директиве. Родитељ доводи једно или више деце у обданиште и чека све док се не појави место, како би оставио сву децу одједном и отишао. Родитељ може и да одведе једно или више деце, такође одједном. Мора се поштовати редослед доласка родитеља који остављају децу и васпитачица које одлазе са посла. Потребно је да програм буде максимално конкурентан и отпоран на прекиде.

== Решење за Atomic Broadcast ==

==== <code>Test.java</code> ====

<syntaxhighlight lang="java">

package rs.ac.bg.etf.kdp.lab12024G1;

import java.util.concurrent.Semaphore;
import java.util.concurrent.atomic.AtomicInteger;

public class Test {

private static final int consumersCount=3;
private static final int b=5;

public static void main(String[] args) {

AtomicInteger[][] reads = new AtomicInteger[b][consumersCount];

Semaphore mutex = new Semaphore(1);

AtomicInteger[] buffer = new AtomicInteger[b];

for (int i = 0; i < buffer.length; i++)
buffer[i] = new AtomicInteger(0);

Consumer[] consumers = new Consumer[consumersCount];

Producer p = new Producer(consumersCount, buffer, reads,b,mutex);
p.start();

for (int i = 0; i < b; i++)
for(int j=0;j<consumersCount;j++)
reads[i][j] = new AtomicInteger(0);

for (int i = 0; i < consumersCount; i++) {
consumers[i] = new Consumer(buffer, reads,b,mutex,i);
consumers[i].start();
}
}

}

</syntaxhighlight>

==== <code>Producer.java</code> ====

<syntaxhighlight lang="java">

package rs.ac.bg.etf.kdp.lab12024G1;

import java.util.concurrent.Semaphore;
import java.util.concurrent.atomic.AtomicInteger;

public class Producer extends Thread {

private final int consumers;
private AtomicInteger[] buffer;
private AtomicInteger[][] reads;
private Semaphore mutex;
private int b;

public Producer(int consumers, AtomicInteger[] buffer, AtomicInteger[][] reads, int bb, Semaphore mutex) {
this.consumers = consumers;
this.buffer = buffer;
this.reads = reads;
b=bb;
this.mutex = mutex;
}

@Override
public void run() {
for (int i = 0; i <b; i++) {
for (int j = 0; j < consumers; j++)
while(reads[i][j].get() == 1)
Thread.onSpinWait();

int rand = (int)(Math.random() * 10);
System.out.println("Producer produced element: " + rand );
mutex.acquireUninterruptibly();
buffer[i].set(rand);
mutex.release();

mutex.acquireUninterruptibly();
for (int j2 = 0; j2 < consumers; j2++)
reads[i][j2].set(0);

mutex.release();
}
}

}
</syntaxhighlight>

==== <code>Consumer.java</code> ====

<syntaxhighlight lang="java">

package rs.ac.bg.etf.kdp.lab12024G1;

import java.util.concurrent.Semaphore;
import java.util.concurrent.atomic.AtomicInteger;

public class Consumer extends Thread {

private int id;
private AtomicInteger[][] reads;
private AtomicInteger[] buffer;
private Semaphore mutex;
private int b;

public Consumer(AtomicInteger[] buff, AtomicInteger[][] r, int bb,Semaphore mutex, int i) {
buffer = buff;
reads=r;
id=i;
this.mutex = mutex;
b=bb;
}

@Override
public void run() {
for (int i = 0; i < b; i++) {
while(reads[i][id].get() == 1)
Thread.onSpinWait();
mutex.acquireUninterruptibly();
int elem = buffer[i].get();
System.out.println("Consumer "+id+" consumed element "+elem +"from place "+i);
reads[i][id].set(1);
mutex.release();

try {
sleep((int)(Math.random()*2000));
} catch (InterruptedException e) {
throw new RuntimeException(e);
}

}
}

}
</syntaxhighlight>

== Решење за H2O ==

==== <code>Test.java</code> ====

<syntaxhighlight lang="java">
package H20;

import java.util.concurrent.CyclicBarrier;
import java.util.concurrent.atomic.AtomicInteger;

public class Test {
public static void main(String[] args) {
int cnt = 10;

Barrier barrier = new Barrier(new CyclicBarrier(3));

Hydrogen[] h = new Hydrogen[cnt*2];
Oxygen[] o = new Oxygen[cnt];

for(int i = 0; i < cnt; i++) {
o[i] = new Oxygen(barrier);
h[2*i] = new Hydrogen(barrier);
h[2*i + 1] = new Hydrogen(barrier);

o[i].start();
h[2*i].start();
h[2*i+1].start();
}

}
}
</syntaxhighlight>
==== <code>Oxygen.java</code> ====
<syntaxhighlight lang="java">
package H20;

import java.util.concurrent.BrokenBarrierException;
import java.util.concurrent.Semaphore;

public class Oxygen extends Thread {

Barrier barrier;

Oxygen(Barrier b){
barrier = b;
}

@Override
public void run() {
while(true) {
try {
Thread.sleep((int)(Math.random() * 4000));
} catch (InterruptedException e) {}

barrier.oxygen.acquireUninterruptibly();

barrier.oCount++;

try {
System.out.println("Kiseonik pristigao na barijeru");

if(barrier.barrier.await() == 0) {
System.out.println("\nFORMIRANJE VODE!\n");

barrier.hCount = 0;
barrier.oCount = 1;

barrier.hydrogen.release(2);
barrier.oxygen.release(1);
}

} catch (InterruptedException | BrokenBarrierException e) {
e.printStackTrace();
}

}
}

}

</syntaxhighlight>

==== <code>Hydrogen.java</code> ====

<syntaxhighlight lang="java">
package H20;

import java.util.concurrent.BrokenBarrierException;
import java.util.concurrent.Semaphore;

public class Hydrogen extends Thread {

Barrier barrier;

Hydrogen(Barrier b){
barrier = b;
}

@Override
public void run() {
while(true) {
try {
Thread.sleep((int)(Math.random() * 4000));
} catch (InterruptedException e) {}

barrier.hydrogen.acquireUninterruptibly();

barrier.hCount++;

try {
System.out.println("Vodonik pristigao na barijeru");

if(barrier.barrier.await() == 0) {
System.out.println("\nFORMIRANJE VODE!\n");
barrier.hCount = 0;
barrier.oCount = 1;

barrier.hydrogen.release(2);
barrier.oxygen.release(1);
}

} catch (InterruptedException | BrokenBarrierException e) {
e.printStackTrace();
}

}
}
}

</syntaxhighlight>

==== <code>Barrier.java</code> ====

<syntaxhighlight lang="java">
package H20;

import java.util.concurrent.CyclicBarrier;
import java.util.concurrent.Semaphore;

public class Barrier {
CyclicBarrier barrier;
Semaphore hydrogen, oxygen;
int hCount, oCount;

Barrier(CyclicBarrier cb){
barrier = cb;
hCount = 0;
oCount = 0;
hydrogen = new Semaphore(2);
oxygen = new Semaphore(1);
}

}
</syntaxhighlight>

== Решење за Dining Philosophers ==

==== <code>Test.java</code> ====

<syntaxhighlight lang="java">
package rs.ac.bg.etf.kdp.lab12024G3;

import java.util.concurrent.atomic.AtomicInteger;

public class Test {

public static final int N = 5;

public static void main(String[] args) {

Philosopher[] philosophers = new Philosopher[N];
AtomicInteger[] forks = new AtomicInteger[N];

for (int i = 0; i < forks.length; i++)
forks[i] = new AtomicInteger(1);

Table table = new Table();

for (int i = 0; i < N; i++) {
philosophers[i] = new Philosopher(forks, i, N, table);
philosophers[i].start();
}

}

}

</syntaxhighlight>
==== <code>Table.java</code> ====
<syntaxhighlight lang="java">
package rs.ac.bg.etf.kdp.lab12024G3;

import java.util.concurrent.atomic.AtomicInteger;

public class Table {

AtomicInteger ticket;
int next;

public Table() {
ticket = new AtomicInteger(0);
next = 0;
}

}

</syntaxhighlight>

==== <code>Philosopher.java</code> ====

<syntaxhighlight lang="java">
package rs.ac.bg.etf.kdp.lab12024G3;

import java.util.concurrent.atomic.AtomicInteger;

public class Philosopher extends Thread {

AtomicInteger[] forks;
int id,left,right,N,myTicket;
Table t;

public Philosopher(AtomicInteger[] forks, int id, int n,Table table) {
this.forks = forks;
this.id = id;
N = n;
left = id;
right = (id+1)%n;
t = table;
}

@Override
public void run() {
while(true) {
int choice = (int)(Math.random() * 2);

switch (choice) {
case 0: {
eat();
break;
}
case 1:{
think();
break;
}
default:
throw new IllegalArgumentException("Unexpected value: " + choice);
}
}
}

public void think() {
System.out.println("Philosopher "+id+" thinking");
try {
sleep((int)(Math.random() * 3000));
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}

public void eat() {
myTicket = t.ticket.getAndIncrement();
synchronized (forks) {

System.out.println("Philosopher "+id+" wants to eat");

while(forks[left].intValue() == 0 || forks[right].intValue() == 0 || myTicket != t.next)
try {
forks.wait();
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
System.out.println("Philosopher "+id+" started eating");
t.next++;
forks[left].set(0);
forks[right].set(0);

}

try {
sleep((int)(Math.random() * 2000));
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}

synchronized (forks) {

System.out.println("Philosopher "+id+" finished eating");
forks[left].set(1);
forks[right].set(1);
forks.notifyAll();
}
}
}

</syntaxhighlight>

== Решење за Child Care ==

==== <code>Test.java</code> ====

<syntaxhighlight lang="java">
package ChildCare;

public class Test {
public static void main(String[] args) {
Kindergarten k = new Kindergarten(12);
k.startProgram(4, 3);
}
}

</syntaxhighlight>
==== <code>Kindergarten.java</code> ====
<syntaxhighlight lang="java">
package ChildCare;

import java.util.concurrent.ConcurrentLinkedQueue;

public class Kindergarten {
int childrenInside = 0;
int teachersInside = 0;
int capacity;
public ConcurrentLinkedQueue<Integer> parentQueue;
public ConcurrentLinkedQueue<Integer> teacherQueue;
public Kindergarten(int capacity) {
parentQueue = new ConcurrentLinkedQueue<Integer>();
teacherQueue = new ConcurrentLinkedQueue<Integer>();
this.capacity = capacity;
}
public static boolean ruleFollowed(int teachers, int children, int capacity ) {
if(teachers == 0 || children > capacity) return false;
return teachers >= Math.ceil(children / 3.0);
}
public void startProgram(int teachersUsed, int parentsUsed) {
Teacher[] teachers = new Teacher[teachersUsed];
Parent[] parents = new Parent[parentsUsed];
for(int i = 0; i < teachersUsed; i++) {
teachers[i] = new Teacher(i, this);
teachers[i].start();
}
for(int i = 0; i < parentsUsed; i++) {
parents[i] = new Parent(i, this);
parents[i].start();
}

}
}

</syntaxhighlight>

==== <code>Teacher.java</code> ====

<syntaxhighlight lang="java">
package ChildCare;

import java.util.Random;
import java.util.concurrent.ConcurrentLinkedQueue;

public class Teacher extends Thread {
Kindergarten k;
int id;

public Teacher(int id, Kindergarten k) {
this.k = k;
this.id = id;
}
public void run() {
while(true) {
try {
Thread.sleep(new Random().nextInt(5000));
} catch (InterruptedException e) {
e.printStackTrace();
}
synchronized(k) {
k.teachersInside++;
System.out.println("Teacher " + id + " came to work.");
k.notifyAll();
}
try {
Thread.sleep(new Random().nextInt(5000));
} catch (InterruptedException e) {
e.printStackTrace();
}

synchronized(k) {
k.teacherQueue.add(id);
System.out.println("Teacher " + id + " wishes to leave work.");
while(!(k.teacherQueue.element() == id && Kindergarten.ruleFollowed(k.teachersInside - 1, k.childrenInside, k.capacity))) {
try {
k.wait();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
System.out.println("Teacher " + id + " has left work.");
k.teachersInside--;
k.teacherQueue.remove();
k.notifyAll();
}
}
}
}

</syntaxhighlight>

==== <code>Parent.java</code> ====

<syntaxhighlight lang="java">
package ChildCare;

import java.util.Random;
import java.util.concurrent.ConcurrentLinkedQueue;

public class Parent extends Thread {

boolean interacted = false;
Kindergarten k;
int id;
public Parent(int id, Kindergarten k) {
this.k = k;
this.id = id;
}
public void run() {

while(true) {
try {
Thread.sleep(new Random().nextInt(5000));
} catch (InterruptedException e) {
e.printStackTrace();
}
int childrenBrought = 1 + new Random().nextInt(4);
System.out.println("Parent " + id + " brought " + childrenBrought + " children.");
interacted = false;

synchronized(k) {
k.parentQueue.add(id);
while(!(k.parentQueue.peek() == id && Kindergarten.ruleFollowed(k.teachersInside, k.childrenInside + childrenBrought, k.capacity))) {
try {
k.wait();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
k.parentQueue.remove();
k.childrenInside += childrenBrought;
System.out.println("Parent " + id + " left his " + childrenBrought + " children.");
k.notifyAll();
}
while(childrenBrought > 0) {
try {
Thread.sleep(new Random().nextInt(5000));
} catch (InterruptedException e) {
e.printStackTrace();
}
int childrenToPickUp = 1 + (1 + new Random().nextInt(4)) % childrenBrought;
synchronized(k) {
k.childrenInside -= childrenToPickUp;
System.out.println("Parent " + id + " took home his " + childrenToPickUp + "/" + childrenBrought + " children.");
k.notifyAll();
}
childrenBrought -= childrenToPickUp;
}

}
}
}

</syntaxhighlight>

[[Категорија:КДП]]
[[Категорија:Лабораторијске вежбе]]

Корисник:Ralepop

2025-12-06T03:34:48Z

Ralepop: Ralepop преместио је страницу Корисник:Ralepop на Корисник:Elar

#Преусмери [[Корисник:Elar]]

Корисник:Elar

2025-12-06T03:34:48Z

Ralepop: Ralepop преместио је страницу Корисник:Ralepop на Корисник:Elar

unpaid-lilac-gizmo@duck.com

Корисник:Elar

2025-12-06T03:31:40Z

Ralepop:

unpaid-lilac-gizmo@duck.com

Интелигентни системи

2025-12-05T20:04:43Z

Ralepop: /* Настава */

{{Предмет
| шифра = 13С113ИС, 13E114ИС
| семестар = 5 (СИ), 7
| статус = изборни
| страница = [http://ri4es.etf.bg.ac.rs/ ri4es.etf.rs]
| одсек = СИ, РТИ
}}
'''Интелигентни системи''' је изборни предмет из петог и седмог семестра за СИ, а само седмог за РТИ.

== Корисне везе ==
* [https://jetbrains.com/pycharm/ PyCharm] — развојно окружење за ''Python''
* [https://app.box.com/s/0r50je333z1qyypz0h3rm0iqb9s0d64f/folder/38795524647 ETF Materijali (Box)] (рокови)

== Настава ==
Области су подељене у три блока на предавањима и вежбама, које долазе редом на колоквијумима:
* '''Први блок:''' алгоритми претраживања, методи задовољења ограничења
* '''Други блок:''' теорија игара - симултане игре и секвенцијалне игре, продукциони системи (само на предавањима), рад у неизвесном окружењу
* '''Трећи блок:''' машинско учење (надгледано, ненадгледано и учење са подршком)
Вежбе су потребне за колоквијуме, домаће задатке и део испита са задацима. Предавања су потребна за део испита са теоријом, али домаћи задаци могу да замене тај део бодова и генерално су занимљивији. Презентације са [http://ri4es.etf.bg.ac.rs/vezbe.html вежби] и [http://ri4es.etf.bg.ac.rs/predavanja.html предавања] су доступна са странице предмета.

== Домаћи ==
Домаћи задаци на предмету нису обавезни, али могу да замене бодове са теоријског дела испита и тиме ослободе студента од слушања предавања. Имају три домаћа задатка, по један за сваки блок наставе, сваки по 10 бодова. Пошто теорија на испиту носи 20 бодова, студенти морају да бирају која два домаћа задатка ће радити и бранити. Домаћи задаци се раде у ''Python''. Део окружења који нема везе са суштином задатка је већ дат, и студентима је дато да имплементирају суштину, односно интелигенцију у задатку. Студентима уз поставку буде дата нека врста јавних тестова за своје домаће, док се на одбрани домаћи тестирају са неком врстом тајних тестова чисто како би се проверило да ли они раде ван тестова на којим је студент пробао. Додатан рад на опционалним стварима попут графичког корисничког интерфејса може бити награђен којим бодом преко максимума. Школске 2023/24. године, додатни поени су се добијали за истакнуте перформансе или кроз међусобно тачмичење алгоритама.

Стари домаћи задаци доступни су са [http://ri4es.etf.bg.ac.rs/projekat.html странице предмета].

Примери модификација за домаће задатке из школске 2023/24 се могу се наћи на [[Интелигентни_системи/Домаћи_2023|следећој страници]].

== Испитни рокови ==
На страници предмета нису доступни старији рокови, јер су задаци који су били релевантни са старих рокова издвојени на презентације са вежби. Неки старији рокови се могу наћи на драјву у одељку за [[#Корисне везе|корисне везе]].

=== Колоквијум 1===
{{#dpl:
| titleregexp = Интелигентни_системи/К1
| noresultsheader = Тренутно нема сачуваних рокова.
| format = ,\n* [[%PAGE%|²{#invoke:String¦sub¦%PAGE%¦22¦-1}²]],,
}}

=== Колоквијум 2===
{{#dpl:
| titleregexp = Интелигентни_системи/К2
| noresultsheader = Тренутно нема сачуваних рокова.
| format = ,\n* [[%PAGE%|²{#invoke:String¦sub¦%PAGE%¦22¦-1}²]],,
}}

=== Колоквијум ===
{{#dpl:
| titleregexp = Интелигентни_системи/К
| noresultsheader = Тренутно нема сачуваних рокова.
| format = ,\n* [[%PAGE%|²{#invoke:String¦sub¦%PAGE%¦22¦-1}²]],,
}}

=== Испит ===
{{#dpl:
| titleregexp = Интелигентни_системи/.* \d+$
| nottitleregexp = Интелигентни_системи/К\d
| nottitleregexp = Интелигентни_системи/К
| nottitleregexp = Интелигентни_системи/Домаћи
| noresultsheader = Тренутно нема сачуваних рокова.
| format = ,\n* [[%PAGE%|²{#invoke:String¦sub¦%PAGE%¦22¦-1}²]],,
}}

== Начин оцењивања ==
* <math>K_1</math>, <math>K_2</math> — бодови са првог и другог колоквијума (0-25, могу се поправити у сваком року с тим што освојени бодови на поправкама важе само у року у којем је рађена поправка) - на РТИ ово представља један колоквијум који вреди 50 поена
* <math>D</math> — укупни бодови са домаћих задатака (0-20)
* <math>I</math> — бодови са трећег колоквијума, односно делу испита са задацима (0-30)
* <math>T</math> — бодови са теоријског дела испита (0-20), ако је започето решавање, гледа се само то
* Бодови: <math>P = K_1 + K_2 + OR \left(T, D\right) + I</math>

У сваком року могуће је радити било коју комбинацију [К1+К2+И, К1+И, К2+И, И, К+И] и уз сваки од њих могуће је радити теорију која мења домаће задатке. Ако се ради теорија, она у потпуности мења домаће задатке (није могуће радити један домаћи и једно теоријско питање). '''Поени ни са једног дела испита се не преносе у наредне испитне рокове, која год комбинација да се ради.'''

{| class="wikitable"
! Бодови
| <math>P \leq 50</math> || <math>50 < P \leq 60</math> || <math>60 < P \leq 70</math> || <math>70 < P \leq 80</math> || <math>80 < P \leq 90</math> || <math>90 < P</math>
|-
! Оцена
| 5 || 6 || 7 || 8 || 9 || 10
|}

== Потребна помоћ ==
* {{zadaci|postavke}}

Корисник:Elar

2025-12-05T00:00:38Z

Ralepop:

rale@keemail.me

Корисник:Elar

2025-08-17T23:41:25Z

Ralepop: Нова страница: SI