KDP/Jun 2022
Ispit u junskom ispitnom roku 2022. godine održan je 14. juna. Postavka ovog roka još uvek nije dostupna sa stranice predmeta.
1. zadatak
- Ovaj zadatak nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.
Postavka
Objasnite šta je At-Most-Once-Property. Objasnite zašto, kada je ispunjena ta osobina, kritična referenca ima osobine atomske akcije. Dati dva primera u kojima su po dva procesa.
Rešenje
2. zadatak
- Ovaj zadatak nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.
Postavka
Postoje tri osobe među kojima treba izabrati jednu (The Odd Person Wins Game). Svaka od tih osoba poseduje novčić koji ima dve strane. Izbor osobe se odigrava tako što svaka osoba nezavisno baca svoj novčić. Ukoliko postoji osoba kojoj je novčić pao na drugu stranu u odnosu na preostale osobe, onda se ta osoba izabira. Ukoliko sve osobe imaju isto postavljen novčić, postupak se ponavlja sve dok se ne izabere jedna. Osobe nakon svakog bacanja moraju da znaju da li su izabrane ili ne ili se postupak ponavlja. Koristeći semafore napisati program koji opisuje ponašanje osobe. Nijednoj osobi ne treba davati prednost na osnovu njihovog identifikatora.
Rešenje
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;
}
}
4. zadatak
Postavka
Trajekt za prevoz automobila, kamiona i autobusa prevozi vozila sa obale na obalu. Trajekt poseduje N pozicija koje su linearno postavljene jedna iza druge. Kamion zauzima tri, autobus dve, a automobil jednu poziciju. Vozila čekaju na trajekt u redu i na njega ulaze jedno po jedno po redosledu u kojem čekaju u redu, dok na trajektu ima mesta. Kada naredno vozilo u redu za trajekt nema mesta da se ukrca ili kada je trajekt pun, trajekt započinje prevoz vozila na drugu obalu. Na drugoj obali vozila se iskrcavaju u redosledu suprotnom od redosleda u kojem su se ukrcala. Kada se sva vozila iskrcaju, prazan trajekt se vraća na početnu obalu. Koristeći regione napisati program koji rešava ovaj problem.
Rešenje
struct Trajekt {
int cap = N;
int curr = 0, next = 0, ticketIn = 0, ticketOut = 0;
bool ukrcavanje = false, iskrcavanje = false
}
Trajekt t;
void vozilo(int space) {
int myTicketIn, myTicketOut;
region(t) {
myTicketIn = t.ticketIn++;
await (t.ukrcavanje && t.ticketIn == myTicketIn);
if (t.cap - t.curr < space) {
// ukoliko nema mesta za mene, posalji trajekt pa sacekaj da se vrati
t.ukrcavanje = false;
await (t.ukrcavanje);
}
t.curr += space;
myTicketOut = ++t.ticketOut;
t.next++;
if (t.curr == t.cap)
t.ukrcavanje = false;
}
// prevozimo se
region(t) {
await (t.iskrcavanje && myTicketOut == t.ticketOut);
if (--t.ticketOut == 0)
// ukoliko sam poslednji, posalji trajekt nazad
t.iskrcavanje = false
}
}
void trajekt() {
while (1) {
region(t) {
t.ukrcavanje = true
await (!t.ukrcavanje);
}
preveziVozila();
region(t) {
t.iskrcavanje = true;
await (!t.iskrcavanje);
}
vratiSeNazad();
}
}
5. zadatak
Postavka
Koristeći sinhronu razmenu poruka napisati distribuirano rešenje za problem filozofa koji ručavaju (The Dining Philosophers Problem). Kod distribuiranog rešenja procesi filozofi komuniciraju samo sa procesima viljuškama i procesi viljuške komuniciraju samo sa procesima filozofima.
Rešenje
void philosopher(int ID, chan<string> release, chan<char> forkL, chan<char> forkR) {
while (true) {
// Филозофирамо
if (ID % 2 == 0) {
forkL.send('R');
forkR.send('L');
} else {
forkR.send('L');
forkL.send('R');
}
// Једемо
release.receive();
release.receive();
}
}
void fork(chan<char> acquire, chan<string> philL, chan<string> philR) {
while (true) {
char dir = acquire.receive();
if (dir == 'L') {
philL.send("release");
} else {
philR.send("release");
}
}
}
6. zadatak
Postavka
Postoji P proizvođača i C potrošača koji dele zajednički bafer kapaciteta B (Atomic broadcast problem). Proizvođači generišu proizvod po proizvod na koje čekaju svih C potrošača. Svaki potrošač mora da primi proizvode u tačno onom redosledu u kome su proizvedeni, mada različiti potrošači mogu u isto vreme da uzimaju različite proizvode. Rešiti problem koristeći C-Linda, tako da se ni u kom trenutku u zajedničkom prostoru ne nađe više od B proizvoda.
Rešenje
Tagovi korišćeni u ovoj implementaciji su:
buffer empty: postoji mesta da proizvođač ubacuje u baferbuffer full: postoje proizvodi u baferu koje potrošači mogu da čitajuproduct: proizvod sa određenim indeksom u nizusize: veličina baferaproducer index: indeks u baferu do kog su proizvođači stigli sa popunjavanjemconsumer count: broj potrošača koji je preostao da pročita proizvod na određenom indeksu
const int P = 100;
const int C = 100;
const int B = 100;
struct Product {};
Product produce();
void consume(Product p);
int producer() {
while (true) {
Product p = produce();
in("buffer empty");
int index;
in("producer index", &index);
out("product", index, p);
out("consumer count", index, C);
out("producer index", (index + 1) % B);
int size;
in("size", &size);
if (size == 0) {
out("buffer full");
}
out("size", ++size);
if (size < B) {
out("buffer empty");
}
}
}
void consumer() {
int index = 0;
while (true) {
in("buffer full");
Product p;
int count;
in("consumer count", index, &count);
if (count == 1) {
in("product", index, &p);
int size;
in("size", &size);
if (size == B) {
out("buffer empty");
}
out("size", --size);
if (size > 0) {
out("buffer full");
}
} else {
rd("product", index, &p);
out("consumer count", index, count-1);
out("buffer full");
}
index = (index + 1) % B;
consume(p);
}
}
void initialize() {
out("buffer empty");
out("size", 0);
out("producer index", 0);
}