KDP/Monitori
Monitori su oblast konkurentnog programiranja iz drugog bloka nastave i dolaze na drugom kolokvijumu za SI i kolokvijumu za RTI.
Januar 2020, 1. zadatak
- Sličan zadatak došao je u avgustu 2021. godine sa Signal and Continue disciplinom.
Postavka
Potrebno je realizovati semafor koji pored standardnih atomskih operacija signal() i wait() ima i atomske operacije signal(n) i wait(n) koja internu semaforsku promenljivu atomski uvećava odnosno umanjuje za n ukoliko je to moguće, ukoliko nije čeka dok ne bude bili moguće. Potrebno je rešiti problem koristeći monitore koji imaju Signal and Wait disciplinu. Proces koji je ranije uputio zahtev treba ranije da obavi svoju operaciju. Broj procesa i maksimalna vrednost n nisu unapred poznati. Uslovne promenljive su FIFO prema trenutku dolaska i nemaju prioritetnu metodu wait.
Rešenje
class Semaphore {
private int value;
private Queue<Integer> requests = new Queue<>();
private Condition queue = new Condition();
public Semaphore(int value) {
this.value = value;
}
public synchronized void wait(int num) {
if (value >= num) {
value -= num;
} else {
requests.insert(num);
queue.wait();
internalSignal();
}
}
public synchronized void signal(int num) {
value += num;
internalSignal();
}
public synchronized void wait() {
wait(1);
}
public synchronized void signal() {
signal(1);
}
private void internalSignal() {
if (requests.size() > 0 && value >= requests.top()) {
value -= requests.pop();
queue.signal();
}
}
}
Januar 2021, 2. zadatak
Postavka
Postoji toalet kapaciteta N (N > 1) koji mogu da koriste žene, muškarci, deca i domar (Single Bathroom Problem) takav da važe sledeća pravila korišćenja: u isto vreme u toaletu ne mogu naći i žene i muškarci; deca mogu da dele toalet i sa ženama i sa muškarcima; dete može da se nađe u toaletu samo ako se tamo nalazi barem jedna žena ili muškarac; domar ima ekskluzivno pravo korišćenja toaleta. Napisati monitor sa signal and wait disciplinom koji rešava dati problem, kao i glavne programe za muškarce, žene, decu i domare, kroz koje su dati primeri korišćenja monitorskih procedura.
Rešenje
class SingleBathroomProblem {
public static final int capacity = 10;
private int count = 0;
private int childCount = 0;
// Група која је тренутно у тоалету
// -1 - нема никога, 0 - мушкарци, 1 - жене, 2 - домар
private int group = -1;
private final Condition queue = new Condition();
private final Condition childrenQueue = new Condition();
private final Condition waitingForChildren = new Condition();
private int ticket = 1;
private void signalPersonOrChild() {
boolean personWaiting = queue.queue() && queue.minrank() % 3 == group;
boolean childWaiting = childrenQueue.queue();
if (personWaiting && childWaiting) {
if (queue.minrank() > childrenQueue.minrank() * 3) {
// Одрасла особа је стигла пре детета
queue.signal();
} else {
// Дете је стигло пре одрасле особе
childrenQueue.signal();
}
} else if (personWaiting) {
queue.signal();
} else if (childWaiting) {
childrenQueue.signal();
}
}
public synchronized void enterMan() {
int myTicket = ticket++;
if (count == capacity || group == 1 || group == 2 || queue.queue()) {
// Пун тоалет, у њему су жене/домар или има других особа испред тоалета
queue.wait(myTicket * 3);
}
++count;
if (group == -1) {
// Означавамо да је тренутно активна група мушкараца
group = 0;
} else if (waitingForChildren.queue()) {
// Ако има мушкарца који чека децу јавља му се да не мора више да чека
waitingForChildren.signal();
}
if (count != capacity) {
signalPersonOrChild();
}
}
public synchronized void enterWoman() {
int myTicket = ticket++;
if (count == capacity || group == 0 || group == 2 || queue.queue()) {
// Пун тоалет или су у њему мушкарци/домар
queue.wait(myTicket * 3 + 1);
}
++count;
if (group == -1) {
// Означавамо да је тренутно активна група жена
group = 1;
} else if (waitingForChildren.queue()) {
// Ако има жена која чека децу јавља јој се да не мора више да чека
waitingForChildren.signal();
}
if (count != capacity) {
signalPersonOrChild();
}
}
public synchronized void enterJanitor() {
int myTicket = ticket++;
if (group != -1) {
// У тоалету или испред тоалета има било кога
queue.wait(myTicket * 3 + 2);
}
++count;
// Означавамо да је домар тренутно у тоалету
group = 2;
}
public synchronized void enterChild() {
int myTicket = ticket++;
if (count == capacity || group == 2 || group == -1 || queue.queue() || childrenQueue.queue() || waitingForChildren.queue()) {
// Пун тоалет, у њему нема никога, у њему је домар, има других особа
// испред тоалета или има особа која је унутра и чека да деца изађу
childrenQueue.wait(myTicket);
}
++count;
++childCount;
if (count != capacity) {
signalPersonOrChild();
}
}
public synchronized void exitMan() {
if (count == childCount + 1) {
// Мушкарац не може да изађе док су деца сама у тоалету
waitingForChildren.wait();
}
--count;
if (count == 0) {
// Нема више никог у тоалету, пусти следећу одраслу особу ако је има
group = -1;
if (queue.queue()) {
queue.signal();
}
} else {
signalPersonOrChild();
}
}
public synchronized void exitWoman() {
if (count == childCount + 1) {
// Жена не може да изађе док су деца сама у тоалету
waitingForChildren.wait();
}
--count;
if (count == 0) {
// Нема више никог у тоалету, пусти следећу одраслу особу ако је има
group = -1;
if (queue.queue()) {
queue.signal();
}
} else {
signalPersonOrChild();
}
}
public synchronized void exitJanitor() {
--count;
// Сигурно нема више никог у тоалету
group = -1;
if (queue.queue()) {
queue.signal();
}
}
public synchronized void exitChild() {
--count;
--childCount;
if (waitingForChildren.queue() && childCount == 0) {
// Јави особи која чека на излазак детета да су сва деца изашла
waitingForChildren.signal();
}
if (count == 0) {
// Нема више никог у тоалету, пусти следећу одраслу особу ако је има
group = -1;
if (queue.queue()) {
queue.signal();
}
} else {
signalPersonOrChild();
}
}
}
Januar 2022, 2. zadatak
Postavka
U berbernici rade dva berberina, Aca i Braca, postoji 10 stolica za čekanje i dve stolice za kojima berberini rade. Mušterije koje dolaze se izjašnjavaju da li čekaju kod Ace ili Brace ili im je svejedno ko će da ih usluži. Nakon završenog brijanja, mušterija plaća i odlazi. Ako mušterija vidi da nema mesta u berbernici i ne može biti uslužena, odlazi. Kada je berberin slobodan, mušterija koja je najduže čekala će prva biti uslužena (osim ako čeka na drugog berberina i tada tražimo sledeću mušteriju u nizu). Ukoliko je neki od berberina besposlen, on spava, i prva mušterija koja kod njega dođe na red treba da ga probudi i bude uslužena. Koristeći monitore sa signal and continue disciplinom rešiti ovaj problem.
Rešenje
class Berbernica {
// Идентификатори које муштерије могу да проследе у osisajSe()
public static final int ACA_ID = 0;
public static final int BRACA_ID = 1;
public static final int BILO_KO = 2;
// Редови чекања муштерија на столицама за шишање
private Condition[] redZaSisanje = new Condition[3];
// Редови чекања берберина када спавају
private Condition[] berberinGotov = new Condition[2];
// Редови чекања муштерија док се шишају
private Condition[] cekamKrajSisanja = new Condition[2];
// Редови чекања берберина док чекају муштерију да плати и изађе
private Condition[] cekamIsplatu = new Condition[2];
// Да ли је берберин тренутно заузет
private boolean[] zauzet = new boolean[2];
// Коју муштерију берберин тренутно шиша (идентификује се по броју у реду)
private int trenutnoSisam = new int[2];
// Број преосталих столица за седење
private int stolice = 10;
// Редни број муштерије
private int red = 1;
public Berbernica() {
for (int i = 0; i < 3; ++i) {
redZaSisanje[i] = new Condition();
}
for (int i = 0; i < 2; ++i) {
berberinGotov[i] = new Condition();
cekamKrajSisanja[i] = new Condition();
cekamIsplatu[i] = new Condition();
zauzet[i] = true;
}
}
// Враћа идентификатор берберина уколико је слободан,
// или -1 уколико нема слободних берберина за задати избор
private int daLiJeZauzet(int izbor) {
switch (izbor) {
case ACA_ID:
case BRACA_ID:
return zauzet[izbor] ? -1 : izbor;
case BILO_KO:
if (!zauzet[ACA_ID]) {
return ACA_ID;
}
if (!zauzet[BRACA_ID]) {
return BRACA_ID;
}
return -1;
}
}
public synchronized boolean osisajSe(int izbor) {
int mojRed = red++;
int berberin = daLiJeZauzet(izbor);
if (berberin == -1) {
if (stolice == 0) {
return false;
}
--stolice;
redZaSisanje[izbor].wait(mojRed);
if (izbor == BILO_KO) {
if (trenutnoSisam[ACA_ID] == mojRed) {
berberin = ACA_ID;
} else {
berberin = BRACA_ID;
}
} else {
berberin = izbor;
}
++stolice;
} else {
zauzet[berberin] = true;
trenutnoSisam[berberin] = mojRed;
berberinGotov[berberin].signal();
}
// Седање на столицу се не моделује неком посебном методом
cekamKrajSisanja[berberin].wait();
// Плаћање и излазак
cekamIsplatu[berberin].signal();
return true;
}
public synchronized void sacekajMusteriju(int berberId) {
int musterija;
if (redZaSisanje[berberId].queue() && redZaSisanje[BILO_KO].queue()) {
int musterija1 = redZaSisanje[berberId].minrank();
int musterija2 = redZaSisanje[BILO_KO].minrank();
if (musterija1 < musterija2) {
musterija = musterija1;
trenutnoSisam[berberId] = musterija;
redZaSisanje[berberId].signal();
} else {
musterija = musterija2;
trenutnoSisam[berberId] = musterija;
redZaSisanje[BILO_KO].signal();
}
} else if (redZaSisanje[berberId].queue()) {
musterija = redZaSisanje[berberId].minrank();
trenutnoSisam[berberId] = musterija;
redZaSisanje[berberId].signal();
} else if (redZaSisanje[BILO_KO].queue()) {
musterija = redZaSisanje[BILO_KO].minrank();
trenutnoSisam[berberId] = musterija;
redZaSisanje[BILO_KO].signal();
} else {
zauzet[berberId] = false;
berberinGotov[berberId].wait();
}
}
public synchronized void obavestiMusteriju(int berberId) {
trenutnoSisam[berberId] = 0;
cekamKrajSisanja[berberId].signal();
cekamIsplatu[berberId].wait();
}
}
Januar 2023, 2. zadatak
- Ovaj zadatak nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.
Postavka
Automobili koji dolaze sa severa i juga moraju da pređu reku preko nekog starog mosta (Old Bridge problem). Na mostu postoji samo jedna vozna traka, pa svi automobili na mostu moraju da se kreću u istom smeru. Zbog opterećenja mosta koje most može da podnese, broj automobila koji se nalaze na mostu ne sme da pređe K (K > 0). Napisati monitor sa signal and continue disciplinom koji rešava dati problem.
Rešenje
Jul 2020, 2. zadatak
Postavka
Problem izgradnje molekula vode (The H2O Problem). Napisati monitor sa signal and continue disciplinom za rešavanje ovog problema, pod sledećim uslovima. Atomi vodonika, kada žele da naprave molekul vode, pozivaju monitorsku proceduru hReady(), atomi kiseonika pozivaju monitorsku proceduru oReady(). Poslednji pristigli atom treba da pozove monitorsku proceduru makeWater(), nakon čijeg završetka sva tri atoma treba da završe svoje odgovarajuće hReady() i oReady() procedure. Ne sme biti izgladnjivanja.
Rešenje
class TheH2OProblem {
private Condition hQueue = new Condition();
private Condition oQueue = new Condition();
private int hCount = 0;
private int oCount = 0;
private int hTicket = 1;
private int oTicket = 1;
public synchronized void hReady() {
++hCount;
if (hCount >= 2 && oCount >= 1) {
makeWater();
hCount -= 2;
oCount -= 1;
hQueue.signal();
oQueue.signal();
} else {
hQueue.wait(hTicket++);
}
}
public synchronized void oReady() {
++oCount;
if (hCount >= 2 && oCount >= 1) {
makeWater();
hCount -= 2;
oCount -= 1;
hQueue.signal();
hQueue.signal();
} else {
oQueue.wait(oTicket++);
}
}
private void makeWater() {
// ...
}
}
Jul 2021, 2. zadatak
Postavka
Posmatra se agencija za iznajmljivanje automobila. U voznom parku postoje M standardnih vozila i N luks vozila. Prilikom dolaska klijenta koji želi da iznajmi auto, on se izjašnjava da li želi da iznajmi standardno ili luks vozilo ili mu je svejedno. Klijent čeka u redu sve dok mu se vozilo ne dodeli na korišćenje. Po završetku korišćenja, korisnik dolazi još jednom u agenciju i vraća auto. Potrebno je obezbediti da klijenti preuzimaju svoje automobile po redosledu dolaska u agenciju. Klijent ima mogućnost da iznajmi više vozila, ali je svaki dolazak vezan isključivo za pozajmicu jednog automobila. Rešiti problem koristeći monitore sa signal and continue disciplinom.
Rešenje
class CarAgency {
public static final STANDARD_VEHICLE = 0;
public static final LUXURY_VEHICLE = 1;
public static final ANY_VEHICLE = 2;
private int standardVehicles = 100;
private int luxuryVehicles = 10;
private final Condition[] queues = new Condition[3];
private int ticket = 1;
public CarAgency() {
for (int i = 0; i < 3; ++i) {
queues[i] = new Condition();
}
}
public synchronized void rentCar(int which) {
int myTicket = ticket++;
if (
standardVehicles == 0 && which == STANDARD_VEHICLE ||
luxuryVehicles == 0 && which == LUXURY_VEHICLE ||
(standardVehicles == 0 && luxuryVehicles == 0)
) {
// Нема возила, чекамо
queues[which].wait(myTicket);
// Број возила је смањен већ при сигнализирању
} else if (which == STANDARD_VEHICLE) {
// Желели смо стандардно возило и добили смо
--standardVehicles;
} else if (which == LUXURY_VEHICLE) {
// Желели смо луксузно возило и добили смо
--luxuryVehicles;
} else if (standardVehicles == 0) {
// Желели смо било које возило и добили смо луксузно
--luxuryVehicles;
} else {
// Желели смо било које возило и добили смо стандардно
--standardVehicles;
}
}
public synchronized void returnCar(int which) {
if (which == STANDARD_VEHICLE) {
++standardVehicles;
boolean qStandardVehicle = queues[STANDARD_VEHICLE].queue();
boolean qAnyVehicle = queues[ANY_VEHICLE].queue();
if (qStandardVehicle || qAnyVehicle) {
--standardVehicles;
}
if (qStandardVehicle && qAnyVehicle) {
if (queues[STANDARD_VEHICLE].minrank() < queues[ANY_VEHICLE].minrank()) {
queues[STANDARD_VEHICLE].signal();
} else {
queues[ANY_VEHICLE].signal();
}
} else if (qStandardVehicle) {
queues[STANDARD_VEHICLE].signal();
} else if (qAnyVehicle) {
queues[ANY_VEHICLE].signal();
}
} else {
++luxuryVehicles;
boolean qLuxuryVehicle = queues[LUXURY_VEHICLE].queue();
boolean qAnyVehicle = queues[ANY_VEHICLE].queue();
if (qLuxuryVehicle || qAnyVehicle) {
--luxuryVehicles;
}
if (qLuxuryVehicle && qAnyVehicle) {
if (queues[LUXURY_VEHICLE].minrank() < queues[ANY_VEHICLE].minrank()) {
queues[LUXURY_VEHICLE].signal();
} else {
queues[ANY_VEHICLE].signal();
}
} else if (qLuxuryVehicle) {
queues[LUXURY_VEHICLE].signal();
} else if (qAnyVehicle) {
queues[ANY_VEHICLE].signal();
}
}
}
}
Jun 2020, 3. zadatak
- Ovaj zadatak nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.
Postavka
Objasnite kako se realizuje monitor sa Signal and Continue disciplinom, kod koga je dozvoljeno da se iz jedne monitorske metode poziva druga monitorska metoda koristeći semafore. Za svaku karakerističnu[sic] situaciju (5 situacija) dati osnovne komponente kôda (kao sa predavanja) i objasnite funkciju delova tog kôda. Za svaku situaciju posebno navesti koji semafori se koriste, i od čega zavisi broj tih semafora.
Rešenje
Jun 2021, 1. zadatak
Postavka
Potrebno je da N procesa dele dva štampača. Pre upotrebe štampača, proces P[i] poziva monitorsku proceduru request(), a procedura vraća identifikator dodeljenog štampača - printer. Po završetku štampanja, proces P[i] oslobađa štampač sa release(printer). Definišite monitorsku invarijantu. Razviti monitor koji koristi Signal and Continue disciplinu. Nakon toga, pretpostaviti da kod procedure request postoji dodatni argument kojim proces dostavlja prioritet zahteva. Modifikovati monitor, tako da se štampači dobijaju u skladu sa prioritetom. Pri istom prioritetu treba da važi redosled pristizanja zahteva - FCFS.
Rešenje
Monitorska invarijanta, ukoliko je broj štampača, je . Krajnje modifikovani monitor izgleda:
class PrintersMonitor {
private class ProcessPriority implements Comparable<ProcessPriority> {
public int priority;
public int ticket;
public int id;
public int printer;
public ProcessPriority(int priority, int ticket, int id) {
this.priority = priority;
this.ticket = ticket;
this.id = id;
}
@Override
public int compareTo(ProcessPriority p2) {
if (priority == p2.priority) {
// Ако је приоритет исти, уреди по времену стизања
return ticket - p2.ticket;
}
// Прво се уређује по приоритету
return priority - p2.priority;
}
}
private static final int N = 100;
private boolean[] busy = new boolean[2];
private Condition[] free = new Condition[N];
private PriorityQueue<ProcessPriority> pq = new PriorityQueue<>(N);
private int ticket = 0;
private int id = 0;
public PrintersMonitor() {
for (int i = 0; i < N; ++i) {
free[i] = new Condition();
}
}
public synchronized int request(int priority) {
// Прво проверимо да ли има слободних штампача
for (int i = 0; i < 2; ++i) {
if (!busy[i]) {
busy[i] = true;
return i;
}
}
// Ако нема, убацујемо се у ред за чекање
int myTicket = ticket++;
int myId = id;
id = (id + 1) % N;
ProcessPriority pp = new ProcessPriority(priority, myTicket, myId);
pq.push(pp);
free[myId].wait();
// Одблокирао нас је неки процес који је раније држао неки штампач
return pp.printer;
}
public synchronized void release(int printer) {
if (pq.isEmpty()) {
busy[printer] = false;
} else {
ProcessPriority pp = pq.pop();
free[pp.id].signal();
pp.printer = printer;
}
}
}
Jun 2022, 3. zadatak
Postavka
Monitor treba da reguliše raspored ulaska pacijenata na pregled kod jednog lekara. Svaki regularno zakazani pacijent je pre pristupanja tom monitoru dobio jedan od 12 hronološki poređanih polusatnih intervala za taj dan (pravljenje rasporeda nije deo zadatka). Pacijent kada dođe na pregled (ne mora da bude tačan) poziva monitorsku proceduru želim_da_se_pregledam i tom prilikom dostavlja ID i početak polusatnog intervala u kome je njemu zakazan pregled. Ako je lekar zauzet, pacijenti na čekanju će se poređati na osnovu hronološkog redosleda u rasporedu za taj dan. Lekar poziva monitorsku proceduru sledeći, koja vraća identifikator sledećeg pacijenta, kada želi da pregleda sledećeg pacijenta. Ako nema pacijenata u tom slučaju, lekar se postvlja u stanje čekanja iz koga izlazi kada naiđe prvi pacijent. Napisati ovakav monitor koristeći disciplinu Signal and Wait i uslovne promenljive kod kojih nema prioritetnih redova čekanja. Monitor ne treba da sadrži sinhronizaciju vezanu za kraj pregleda.
Rešenje
// pretpostavka da je ID 0-11
class Monitor {
private Condition[] awaitPatient[12], awaitDoctor;
private boolean[] patientChecked[12]; // da li je pacijent pregledan, potreban zbog signal&wait
private PriorityQueue<<int,int>> pq; // prioritetni red slot, ID, sortiran po slotu
public synchronized void zelim_da_se_pregledam(int ID, int slot) {
pq.add(slot,ID);
awaitDoctor.signal();
// potrebno jer signal&wait predaje kontrolu pa je pacijent u medjuvremenu mozda pregledan
if (patientChecked[ID] == false) awaitPatient[ID].wait();
}
public synchronized int sledeci() {
if (pq.size() == 0) awaitDoctor.wait();
int id = pq.pop().first;
pq.remove();
patientChecked[id] = true;
awaitPatient[id].signal();
return id;
}
}
Avgust 2021, 1. zadatak
- Sličan zadatak došao je u januaru 2020. godine sa Signal and Wait disciplinom.
Postavka
Potrebno je realizovati semafor koji pored standardnih atomskih operacija signal() i wait() ima i atomske operacije signal(n) i wait(n) koje internu semaforsku promenljivu atomski uvećava odnosno umanjuje za n ukoliko je to moguće, ukoliko nije čeka dok ne bude bilo moguće. Potrebno je rešiti problem koristeći monitore koji imaju Signal and Continue disciplinu. Proces koji je ranije uputio zahtev treba ranije da obavi svoju operaciju. Broj procesa i maksimalna vrednost n nisu unapred poznati. Uslovne promenljive su FIFO prema trenutku dolaska, nemaju prioritetnu metodu wait i ima ih konačan broj.
Rešenje
class Semaphore {
private int value;
private Queue<Integer> requests = new Queue<>();
private Condition queue = new Condition();
public Semaphore(int value) {
this.value = value;
}
public synchronized void wait(int num) {
if (value >= num) {
value -= num;
} else {
requests.insert(num);
queue.wait();
}
}
public synchronized void signal(int num) {
value += num;
while (requests.size() > 0 && value >= requests.top()) {
value -= requests.pop();
queue.signal();
}
}
public synchronized void wait() {
wait(1);
}
public synchronized void signal() {
signal(1);
}
}
K 2019, 2. zadatak
Postavka
Posmatra se jedna podzemna garaža. Postoji samo jedna rampa koja služi i za ulaz, i za izlaz iz garaže. Kroz rampu u jednom trenutku može da prolazi samo jedan automobil iz bilo kog smera. U garaži ima N mesta za parkiranje. Automobili koji ulaze, mogu da uđu, jedan po jedan, ukoliko ima slobodnih mesta, po redosledu po kojem su tražili ulaz. Ukoliko slobodnog mesta nema, proverava se da li ima automobila koji hoće da izađu. Ako nakon izlaska svih automobila koji žele da izađu i ulaska automobila koji su došli pre njega za automobil neće biti mesta, on odlazi u potragu za drugom garažom. Automobili pri izlasku plaćaju usluge garaže i izlaze jedan po jedan, po redosledu po kojem su zatražili izlazak. Prednost na rampi imaju automobili koji izlaze iz garaže.
Napisati monitor sa signal and continue disciplinom koji ima sledeće metode: boolean trazim_ulaz(), za traženje dozvole za ulaz u garažu, koja vraća true ako se dozvoljava ulaz u garažu, a false ako nema mesta; void usao(), za obaveštavanje o ulasku u garažu; void trazim_izlaz() za traženje dozvole za izlaskom iz garaže; void izasao() za obaveštavanje o izlasku iz garaže.
Rešenje
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();
}
}
}
K 2021, 1. zadatak
Postavka
Monitor treba da obezbedi skupljanje gajbica sa ivice voćnjaka. Procesi berači donose po nekoliko punih gajbica (zavisno od nosivosti berača) do puta na ivici njive. Kada pored puta berači ostave bar prikolica_kapacitet gajbica, treba da se probudi jedan od procesa traktor_sa_prikolicom, da dođu do puta kraj njive i pokupe onoliko gajbica koliko staje u prikolicu (prikolica_kapacitet). Procesi traktor_sa_prikolicom pozivaju monitorsku proceduru spreman_da_pokupim kada završe prevoz prethodne prikolice voća. Berači pozivaju monitorsku proceduru ostavljam_gajbice, kada donesu gajbice do ivice puta. Obezbediti da proces traktor_sa_prikolicom koji je pre došao pre treba i da se utovari. Podrazumevati Signal and Continue disciplinu.
Rešenje
class SkupljanjeGajbica {
private static final int prikolica_kapacitet = 100;
private int broj_gajbica = 0;
private Condition pokupi;
private int maxrank = 1;
private int waiting = 0;
public synchronized void spreman_da_pokupim() {
if (broj_gajbica < prikolica_kapacitet || waiting > 0) {
++waiting;
pokupi.wait(maxrank++);
--waiting;
}
broj_gajbica -= prikolica_kapacitet;
}
public synchronized void ostavljam_gajbice(int broj) {
broj_gajbica += broj;
int broj_signala = broj_gajbica / prikolica_kapacitet;
for (int i = 0; i < broj_signala; ++i) {
pokupi.signal();
}
}
}
K 2022, 1. zadatak
Postavka
Koristeći monitore sa Signal and wait disciplinom rešiti problem berberina koji spava (The Sleeping Barber Problem). Berbernica se satoji od čekacionice sa n=5 stolica i berberske stolice na kojoj se ljudi briju. Ukoliko nema mušterija, brica spava. Ukoliko mušterija uđe u berbenicu i sve stolice su zauzete, mušterija ne čeka, već odmah izlazi. Ukoliko je berberin zauzet, a ima slobodnih stolica, mušterija seda i čeka da dođe na red. Ukoliko berberin spava, mušterija ga budi. Obezbediti da se mušterije opslužuju po redosledu dolaska. Uslovne promenljive nisu FIFO niti imaju prioritetne redove čekanja.
Rešenje
Videti prezentacije sa predavanja.
K2 2019, 1. zadatak
Postavka
Problem filozofa koji ručavaju (Dining Philosophers Problem). Rešiti problem filozofa koji ručavaju koristeći monitore sa signal and wait disciplinom. Filozofi koji su ranije izrazili želju za hranom treba ranije da budu opsluženi.
Rešenje
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();
}
}
}
K2 2022, 1. zadatak
Postavka
Rešiti problem Čitalaca i pisaca (Readers/Writers) koristeći monitore sa disciplinom Signal and Continue. Problem rešiti koristeći tehniku prosleđivanja uslova (Passing the Condition). Monitor treba da poseduje 4 metode: lockShared() — želim da čitam, lockExclusive() — želim da pišem, unlock() — završavam, i upgradeLock() — sa čitanja prelazim na pisanje.
Rešenje
class ReadersWriters {
private int readers = 0;
private int writers = 0;
private int ticket = 1;
private Condition okToRead = new Condition();
private Condition okToWrite = new Condition();
public synchronized void lockShared() {
if (writers == 0 && okToWrite.empty()) {
++readers;
} else {
okToRead.wait(ticket++);
}
}
public synchronized void lockExclusive() {
if (readers == 0 && writers == 0) {
++writers;
} else {
okToWrite.wait(ticket++);
}
}
public synchronized void unlock() {
if (readers > 0) {
if (--readers == 0 && okToWrite.queue()) {
writers = 1;
okToWrite.signal();
}
} else {
boolean readersNext = okToRead.queue() && (okToWrite.empty() || okToRead.minrank() < okToWrite.minrank());
boolean writersNext = okToWrite.queue() && (okToRead.empty() || okToWrite.minrank() < okToRead.minrank());
if (readersNext) {
while (okToRead.queue() && okToRead.minrank() < okToWrite.minrank()) {
++readers;
okToRead.signal();
}
} else if (writersNext) {
okToWrite.signal();
} else {
writers = 0;
}
}
}
public synchronized void upgradeLock() {
if (readers == 1) {
// Ако је само један читалац, конвертуј га у писца
readers = 0;
writers = 1;
} else {
// У супротном, мораће да сачека остале читаоце и писце како би постао писац
unlock();
lockExclusive();
}
}
}
Septembar 2023, 2. zadatak
Postavka
Trajekt za prevoz automobila, kamiona i autobusa prevozi vozila sa obale na obalu. Trajekt poseduje N pozicija koje su linearlno postavljene jedna iza druge. Kamiona zauzima tri, autovus dve a automobil jednu poziciju. Vozila čekaju na trajekt u redu i na njega ulaze jedno po jedno po redosledu u kom čekaju u redu, dok na trajektu ima mesta. Kada nema mesta da se naredno vozilo u redu ukrca i trajekt nije u potpunosti popunjen, preko reda se ukrcavaju manja vozila dok se trajekt ne popuni u potpunosti. Kada je kompletno pun, trajekt započinje prevoz vozila na drugu obalu. Na drugoj obali vozila se iskrcavaju u redosledu suprotnom od onog u kojem su se ukrcala. Kada se sva vozila iskrcaju, prazan trajekt se vraća na početnu obalu. Napisati monitor sa signal and wait disciplinom koji rešava dati problem.
Rešenje
- Ovaj zadatak nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.
Februar 2022, 1. zadatak
- Ovaj zadatak nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.
Postavka
Realizovati monitor sa Signal and Continue disciplinom za pristup resursima. Procesi koji pozivaju monitorske procedure mogu da rezervišu do dve instance resursa. Ukupno inicijalno postoje tri slobodne instance resursa. Procesi prilikom poziva monitorske procedure za zauzimanje resursa definišu prioritet zahteva kao visok ili normalan. Kada neki proces oslobađa dve instance resursa, a postoje procesi koji su na čekanju i koji traže dve instance resursa, ti procesi uvek imaju prednost u odnosu na procese koji su na čekanju i traže jedan resurs. Sprečiti izgladnjivanje.
Rešenje
Februar 2023, 2. zadatak
- Ovaj zadatak nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.
Postavka
Pleme ljudoždera jede zajedničku večeru iz kazana koji može da primi M porcija kuvanih misionara (The Dining Savages Problem). Kada ljudožder poželi da ruča onda se on sam posluži iz zajedničkog kazana, ukoliko kazan nije prazan. Ukoliko je kazan prazan ljudožder budi kuvara i sačeka dok kuvar ne napuni kazan i onda uzima svoju porciju, a tek nakon toga preostali mogu jesti. Nije dozvoljeno buditi kuvara ukoliko se nalazi bar malo hrane u kazanu. Napisati monitor sa signal and continue disciplinom koji rešava dati problem.