КДП/Монитори
Монитори су област конкурентног програмирања из другог блока наставе и долазe на другом колоквијуму за СИ и колоквијуму за РТИ.
Јануар 2020, 1. задатак
- Сличан задатак дошао је у августу 2021. године са Signal and Continue дисциплином.
Поставка
Потребно је реализовати семафор који поред стандардних атомских операција signal() и wait() има и атомске операције signal(n) и wait(n) која интерну семафорску променљиву атомски увећава односно умањује за n уколико је то могуће, уколико није чека док не буде били могуће. Потребно је решити проблем користећи мониторе који имају Signal and Wait дисциплину. Процес који је раније упутио захтев треба раније да обави своју операцију. Број процеса и максимална вредност n нису унапред познати. Условне променљиве су FIFO према тренутку доласка и немају приоритетну методу wait.
Решење
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();
}
}
}
Јануар 2021, 2. задатак
Поставка
Постоји тоалет капацитета N (N > 1) који могу да користе жене, мушкарци, деца и домар (Single Bathroom Problem) такав да важе следећа правила коришћења: у исто време у тоалету не могу наћи и жене и мушкарци; деца могу да деле тоалет и са женама и са мушкарцима; дете може да се нађе у тоалету само ако се тамо налази барем једна жена или мушкарац; домар има ексклузивно право коришћења тоалета. Написати монитор са signal and wait дисциплином који решава дати проблем, као и главне програме за мушкарце, жене, децу и домаре, кроз које су дати примери коришћења мониторских процедура.
Решење
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();
}
}
}
Јануар 2022, 2. задатак
Поставка
У берберници раде два берберина, Аца и Браца, постоји 10 столица за чекање и две столице за којима берберини раде. Муштерије које долазе се изјашњавају да ли чекају код Аце или Браце или им је свеједно ко ће да их услужи. Након завршеног бријања, муштерија плаћа и одлази. Ако муштерија види да нема места у берберници и не може бити услужена, одлази. Када је берберин слободан, муштерија која је најдуже чекала ће прва бити услужена (осим ако чека на другог берберина и тада тражимо следећу муштерију у низу). Уколико је неки од берберина беспослен, он спава, и прва муштерија која код њега дође на ред треба да га пробуди и буде услужена. Користећи мониторе са signal and continue дисциплином решити овај проблем.
Решење
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();
}
}
Јануар 2023, 2. задатак
- Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.
Поставка
Аутомобили који долазе са севера и југа морају да пређу реку преко неког старог моста (Old Bridge problem). На мосту постоји само једна возна трака, па сви аутомобили на мосту морају да се крећу у истом смеру. Због оптерећења моста које мост може да поднесе, број аутомобила који се налазе на мосту не сме да пређе K (K > 0). Написати монитор са signal and continue дисциплином који решава дати проблем.
Решење
Јул 2020, 2. задатак
Поставка
Проблем изградње молекула воде (The H2O Problem). Написати монитор са signal and continue дисциплином за решавање овог проблема, под следећим условима. Атоми водоника, када желе да направе молекул воде, позивају мониторску процедуру hReady(), атоми кисеоника позивају мониторску процедуру oReady(). Последњи пристигли атом треба да позове мониторску процедуру makeWater(), након чијег завршетка сва три атома треба да заврше своје одговарајуће hReady() и oReady() процедуре. Не сме бити изгладњивања.
Решење
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() {
// ...
}
}
Јул 2021, 2. задатак
Поставка
Посматра се агенција за изнајмљивање аутомобила. У возном парку постоје M стандардних возила и N лукс возила. Приликом доласка клијента који жели да изнајми ауто, он се изјашњава да ли жели да изнајми стандардно или лукс возило или му је свеједно. Клијент чека у реду све док му се возило не додели на коришћење. По завршетку коришћења, корисник долази још једном у агенцију и враћа ауто. Потребно је обезбедити да клијенти преузимају своје аутомобиле по редоследу доласка у агенцију. Клијент има могућност да изнајми више возила, али је сваки долазак везан искључиво за позајмицу једног аутомобила. Решити проблем користећи мониторе сa signal and continue дисциплином.
Решење
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();
}
}
}
}
Јун 2020, 3. задатак
- Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.
Поставка
Објасните како се реализује монитор са Signal and Continue дисциплином, код кога је дозвољено да се из једне мониторске методе позива друга мониторска метода користећи семафоре. За сваку каракеристичну[sic] ситуацију (5 ситуацијa) дати основне компоненте кôда (као са предавања) и објасните функцију делова тог кôда. За сваку ситуацију посебно навести који семафори се користе, и од чега зависи број тих семафора.
Решење
Јун 2021, 1. задатак
Поставка
Потребно је да N процеса деле два штампача. Пре употребе штампача, процес P[i] позива мониторску процедуру request(), а процедура враћа идентификатор додељеног штампача - printer. По завршетку штампања, процес P[i] ослобађа штампач са release(printer). Дефинишите мониторску инваријанту. Развити монитор који користи Signal and Continue дисциплину. Након тога, претпоставити да код процедуре request постоји додатни аргумент којим процес доставља приоритет захтева. Модификовати монитор, тако да се штампачи добијају у складу са приоритетом. При истом приоритету треба да важи редослед пристизања захтева - FCFS.
Решење
Мониторска инваријанта, уколико je број штампача, je . Крајње модификовани монитор изгледа:
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;
}
}
}
Јун 2022, 3. задатак
Поставка
Монитор треба да регулише распоред уласка пацијената на преглед код једног лекара. Сваки регуларно заказани пацијент је пре приступања том монитору добио један од 12 хронолошки поређаних полусатних интервала за тај дан (прављење распореда није део задатка). Пацијент када дође на преглед (не мора да буде тачан) позива мониторску процедуру želim_da_se_pregledam и том приликом доставља ID и почетак полусатног интервала у коме је њему заказан преглед. Ако је лекар заузет, пацијенти на чекању ће се поређати на основу хронолошког редоследа у распореду за тај дан. Лекар позива мониторску процедуру sledeći, која враћа идентификатор следећег пацијента, када жели да прегледа следећег пацијента. Ако нема пацијената у том случају, лекар се поствља у стање чекања из кога излази када наиђе први пацијент. Написати овакав монитор користећи дисциплину Signal and Wait и условне променљиве код којих нема приоритетних редова чекања. Монитор не треба да садржи синхронизацију везану за крај прегледа.
Решење
// 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;
}
}
Август 2021, 1. задатак
- Сличан задатак дошао је у јануару 2020. године са Signal and Wait дисциплином.
Поставка
Потребно је реализовати семафор који поред стандардних атомских операција signal() и wait() има и атомске операције signal(n) и wait(n) које интерну семафорску променљиву атомски увећава односно умањује за n уколико је то могуће, уколико није чека док не буде било могуће. Потребно је решити проблем користећи мониторе који имају Signal and Continue дисциплину. Процес који је раније упутио захтев треба раније да обави своју операцију. Број процеса и максимална вредност n нису унапред познати. Условне променљиве су FIFO према тренутку доласка, немају приоритетну методу wait и има их коначан број.
Решење
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);
}
}
К 2019, 2. задатак
Поставка
Посматра се једна подземна гаража. Постоји само једна рампа која служи и за улаз, и за излаз из гараже. Кроз рампу у једном тренутку може да пролази само један аутомобил из било ког смера. У гаражи има N места за паркирање. Аутомобили који улазе, могу да уђу, један по један, уколико има слободних места, по редоследу по којем су тражили улаз. Уколико слободног места нема, проверава се да ли има аутомобила који хоће да изађу. Ако након изласка свих аутомобила који желе да изађу и уласка аутомобила који су дошли пре њега за аутомобил неће бити места, он одлази у потрагу за другом гаражом. Аутомобили при изласку плаћају услуге гараже и излазе један по један, по редоследу по којем су затражили излазак. Предност на рампи имају аутомобили који излазе из гараже.
Написати монитор са signal and continue дисциплином који има следеће методе: boolean trazim_ulaz(), за тражење дозволе за улаз у гаражу, која враћа true ако се дозвољава улаз у гаражу, а false ако нема места; void usao(), за обавештавање о уласку у гаражу; void trazim_izlaz() за тражење дозволе за изласком из гараже; void izasao() за обавештавање о изласку из гараже.
Решење
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();
}
}
}
К 2021, 1. задатак
Поставка
Монитор треба да обезбеди скупљање гајбица са ивице воћњака. Процеси берачи доносе по неколико пуних гајбица (зависно од носивости берача) до пута на ивици њиве. Када поред пута берачи оставе бар prikolica_kapacitet гајбица, треба да се пробуди један од процеса traktor_sa_prikolicom, да дођу до пута крај њиве и покупе онолико гајбица колико стаје у приколицу (prikolica_kapacitet). Процеси traktor_sa_prikolicom позивају мониторску процедуру spreman_da_pokupim када заврше превоз претходне приколице воћа. Берачи позивају мониторску процедуру ostavljam_gajbice, када донесу гајбице до ивице пута. Обезбедити да процес traktor_sa_prikolicom који је пре дошао пре треба и да се утовари. Подразумевати Signal and Continue дисциплину.
Решење
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();
}
}
}
К 2022, 1. задатак
Поставка
Користећи мониторе са Signal and wait дисциплином решити проблем берберина који спава (The Sleeping Barber Problem). Берберница се сатоји од чекационице са n=5 столица и берберске столице на којој се људи брију. Уколико нема муштерија, брица спава. Уколико муштерија уђе у бербеницу и све столице су заузете, муштерија не чека, већ одмах излази. Уколико је берберин заузет, а има слободних столица, муштерија седа и чека да дође на ред. Уколико берберин спава, муштерија га буди. Обезбедити да се муштерије опслужују по редоследу доласка. Условне променљиве нису FIFO нити имају приоритетне редове чекања.
Решење
Видети презентације са предавања.
К2 2019, 1. задатак
Поставка
Проблем филозофа који ручавају (Dining Philosophers Problem). Решити проблем филозофа који ручавају користећи мониторе са signal and wait дисциплином. Филозофи који су раније изразили жељу за храном треба раније да буду опслужени.
Решење
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();
}
}
}
К2 2022, 1. задатак
Поставка
Решити проблем Читалаца и писаца (Readers/Writers) користећи мониторе са дисциплином Signal and Continue. Проблем решити користећи технику прослеђивања услова (Passing the Condition). Монитор треба да поседује 4 методе: lockShared() — желим да читам, lockExclusive() — желим да пишем, unlock() — завршавам, и upgradeLock() — са читања прелазим на писање.
Решење
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();
}
}
}
Септембар 2023, 2. задатак
Поставка
Трајект за превоз аутомобила, камиона и аутобуса превози возила са обале на обалу. Трајект поседује N позиција које су линеарлно постављене једна иза друге. Камиона заузима три, аутовус две а аутомобил једну позицију. Возила чекају на трајект у реду и на њега улазе једно по једно по редоследу у ком чекају у реду, док на трајекту има места. Када нема места да се наредно возило у реду укрца и трајект није у потпуности попуњен, преко реда се укрцавају мања возила док се трајект не попуни у потпуности. Када је комплетно пун, трајект започиње превоз возила на другу обалу. На другој обали возила се искрцавају у редоследу супротном од оног у којем су се укрцала. Када се сва возила искрцају, празан трајект се враћа на почетну обалу. Написати монитор са signal and wait дисциплином који решава дати проблем.
Решење
- Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.
Фебруар 2022, 1. задатак
- Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.
Поставка
Реализовати монитор са Signal and Continue дисциплином за приступ ресурсима. Процеси који позивају мониторске процедуре могу да резервишу до две инстанце ресурса. Укупно иницијално постоје три слободне инстанце ресурса. Процеси приликом позива мониторске процедуре за заузимање ресурса дефинишу приоритет захтева као висок или нормалан. Када неки процес ослобађа две инстанце ресурса, а постоје процеси који су на чекању и који траже две инстанце ресурса, ти процеси увек имају предност у односу на процесе који су на чекању и траже један ресурс. Спречити изгладњивање.
Решење
Фебруар 2023, 2. задатак
- Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.
Поставка
Племе људождера једе заједничку вечеру из казана који може да прими M порција куваних мисионара (The Dining Savages Problem). Када људождер пожели да руча онда се он сам послужи из заједничког казана, уколико казан није празан. Уколико је казан празан људождер буди кувара и сачека док кувар не напуни казан и онда узима своју порцију, а тек након тога преостали могу јести. Није дозвољено будити кувара уколико се налази бар мало хране у казану. Написати монитор са signal and continue дисциплином који решава дати проблем.