KDP/C-Linda
C-Linda je oblast distribuiranog programiranja iz trećeg bloka nastave i dolazi na distribuiranom delu ispita za SI i RTI.
Januar 2021, 4. zadatak
Postavka
Na ulasku u jednu železničku stanicu sa jednom ulaznom prugom i jednim slepim kolosekom desio se kvar, pa se na ulazu napravila kolona međunarodnih i domaćih vozova. Kvar je otklonjen i treba puštati vozove. Da bi međunarodni vozovi manje kasnili, oni se puštaju prvi, po redosledu dolaska. Pošto postoji samo jedna pruga i vozovi se ne mogu „preticati”, svi domaći vozovi koji su bili ispred međunarodnih u koloni se prebacuju na slepi kolosek koji je dovoljno veliki da svi vozovi mogu da stanu. Kada svi međunarodni vozovi odu, puštaju se prvo vozovi sa slepog koloseka, pa onda preostali domaći vozovi iz kolone. Sama stanica ima N perona, tj. N vozova istovremeno mogu da ukrcavaju i iskrcavaju putnike. Vozovi koji u međuvremenu pristižu treba da budu opsluženi, ali novopristigli međunarodni nemaju prioritet u odnosu na vozove koji su ispred njih u koloni. Rešiti problem koristeći C-Linda. Napisati potrebnu inicijalizaciju koja oslikava stanje nakon otklanjanja kvara. Voditi računa o tome da su kompozicije vozova teške i da je potrebno vreme da se voz pomeri sa jednog mesta na drugo.
Rešenje
Sledeći tagovi su korišćeni tokom realizacije:
ticket: redosled voza po pristizanjucurrent: voz koji trenutno okupira ulaz (bilo da izlazi iz ulaza i ide u slepi kolosek, izlazi iz ulaza i ide na stanicu ili izlazi iz slepog koloseka i ide na stanicu)sidetrack: vozovi koji se nalaze u slepom koloseku, prva vrednost je redosled u slepom koloseku a druga redosled pristizanja vozasidetrackHead: prvi voz koji sledeći treba da izađe iz slepog koloseka, po redosledu u slepom kolosekusidetrackTail: broj vozova u slepom kolosekustation: vozovi koji su trenutno na jednom od regularnih N koloseka
Način na koji je u ovom rešenju bilo određeno da li je voz pristigao tokom kvara ili posle je provera da li je njegov redosled pristizanja veći ili jednak konstanti M, što je broj vozova koji su pristigli tokom kvara. Nakon početne inicijalizacije stanja nakon popravljanja kvara očekuje se da novopristigli vozovi sami naprave train proces.
const int N = 10;
const int M = 100;
void setCurrentFromSidetrack() {
int sidetrackTicket;
int sidetrackHead;
in("sidetrackHead", &sidetrackHead);
in("sidetrack", sidetrackHead, &sidetrackTicket);
out("sidetrackHead", sidetrackHead + 1);
out("current", sidetrackTicket);
}
void train(bool isInternational) {
int ticket;
in("ticket", &ticket);
out("ticket", ticket + 1);
in("current", ticket);
bool arrivedLater = ticket >= M;
bool isSidetrack = !isInternational && !arrivedLater;
if (isSidetrack) {
// Прво идемо у слепи колосек
int sidetrackTail;
in("sidetrackTail", &sidetrackTail);
out("sidetrack", sidetrackTail, ticket);
out("sidetrackTail", sidetrackTail + 1);
if (ticket == M - 1) {
// Ми смо последњи воз који је стигао током квара,
// треба да предамо првом из слепог колосека
setCurrentFromSidetrack();
in("current", ticket);
} else {
// Предајемо следећем возу који је стигао током квара
out("current", ticket + 1);
in("current", ticket);
}
}
int station;
in("station", &station);
// Идемо на станицу, па чим ослободимо улаз пуштамо следећег
if (isSidetrack) {
if (rdp("sidetrack")) {
// Пуштамо следећег из слепог колосека
setCurrentFromSidetrack();
} else {
// Нема више никог из слепог колосека, пуштамо обичну колону
out("current", M);
}
} else {
if (ticket == M - 1) {
// Ми смо последњи воз који је стигао током квара,
// треба да предамо возовима из слепог колосека, уколико постоје
if (rdp("sidetrack")) {
setCurrentFromSidetrack();
} else {
// Нико није ушао у слепи колосек
out("current", ticket + 1);
}
} else {
// Пуштамо следећи воз, пошто још увек колона која је стигла
// током квара није изашла из улаза
out("current", ticket + 1);
}
}
// Одлазимо са станице
out("station", station);
}
void initialize() {
out("ticket", 0);
for (int i = 0; i < M; ++i) {
eval(train, rand() % 2 == 1);
// Чекамо да воз покупи свој ticket
rd("ticket", i + 1);
}
for (int i = 0; i < N; ++i) {
out("station", i);
}
out("current", 0);
out("sidetrackHead", 0);
out("sidetrackTail", 0);
}
Januar 2022, 3. zadatak
Postavka
Rešiti problem filozofa koji ručavaju koristeći C-Lindu. Filozof koji je ranije izrazio želju za hranom treba ranije da budu[sic] opslužen.
Rešenje
const int N = 5;
void philosopher(int i) {
int left = i;
int right = (i + 1) % N;
int ticket;
while (true) {
// Мислимо
in("ticket", &ticket);
out("ticket", ticket + 1);
in("current", ticket);
in("fork", left);
in("fork", right);
out("current", ticket + 1);
// Једемо
out("fork", right);
out("fork", left);
}
}
void init() {
for (int i = 0; i < N; ++i) {
out("fork", i);
eval(philosopher, i);
}
out("ticket", 0);
out("current", 0);
}
Januar 2023, 4. zadatak
Postavka
Trajekt za prevoz vozila prevozi vozila sa obale na obalu. Trajekt poseduje M traka od kojih svaka ima N pozicija koje su linearno postavljene jedna iza druge. Vozilo zauzima jednu poziciju. Vozilo prilikom dolaska staje u red za slučajno izabranu traku i čeka na ukrcavanje. Nema mogućnosti za prestrojavanjem. Vozila ulaze u svoju traku jedno po jedno po redosledu u kojem čekaju u traci, dok na trajektu ima mesta. Kada je pun, trajekt započinje prevoz vozila na drugu obalu. Na drugoj obali vozila se iskrcavaju iz svoje trake u redosledu suprotnom od redosleda u kojem su se ukrcala u svoju traku. Kada se sva vozila iskrcaju, prazan trajekt se vraća na početnu obalu. Koristeći C-Linda napisati program koji rešava ovaj problem.
Rešenje
Jul 2021, 3. zadatak
Postavka
U Lindi realizovati licitaciju u kojoj postoji jedan proces vođa_licitacije i n procesa učesnika_u_licitaciji i jedan proces tick koji samo ažurira vreme. Vođa licitacije treba da inicijalizuje torku sa početnom vrednošću i da posle datog vremenskog intervala završi licitaciju, uspešno ako je izlicitirana vrednost veća od rezervisane vrednosti, neuspešno inače. Procesi učesnici u licitaciji treba da se realizuju tako da se ne blokiraju kada se završi data licitacija, treba da znaju koja je izlicitirana vrednost i da li su je oni postavili.
Rešenje
Tagovi u ovom rešenju označavaju:
value: Trenutna vrednost licitacijetime out: Postavlja se kad istekne vremeended: Postavlja se kad vođa licitacije objavi kraj licitacije
const int FINAL_TIME = 100;
const int INITIAL_VALUE = 50;
const int RESERVE_VALUE = 100;
int getBid();
void sleep(unsigned int seconds);
void vodjaLicitacije() {
out("value", INITIAL_VALUE, -1);
in("time out");
int value;
int user;
in("value", &value, &user);
out("ended", value > RESERVE_VALUE);
out("value", value, user);
}
void ucesnikULicitaciji(int i) {
int value;
int user;
int bid = getBid();
bool success;
in("value", &value, &user);
if (rdp("ended") || value > bid) {
out("value", value, user);
} else {
out("value", bid, i);
}
rd("ended", &success);
rd("value", &value, &user);
if (success && user == i) {
// Ми добијамо лицитацију
}
}
void tick() {
int time = 0;
while (true) {
sleep(1);
if (++time == FINAL_TIME) {
out("time out");
}
}
}
Jun 2020, 6. zadatak
- Ovaj zadatak nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.
Postavka
Posmatra se skup čvorova u grafu koji mogu da komuniciraju samo sa svojim susedima (Distributed Pairing Problem). Svaki čvor treba da nađe čvor sa kojim će se upariti. Na kraju postupka uparivanja svaki čvor će ili imati svog para, ili ostati neuparen, ali tako da ni jedna dva susedna čvora ne ostanu neuparena. Napisati program za čvor koristeći biblioteku C-Linda.
Rešenje
Jun 2021, 4. zadatak
Postavka
Posmatra se špil od 24 karte, podeljene u 4 boje, sa po 6 različitih brojeva. Igru igraju 4 igrača, koji sede za okruglim stolom i svaki od njih inicijalno drži po 4 karte. Između dva susedna igrača se nalazi gomila sa kartama, koja može u nekom trenutku biti prazna, a inicijalno sadrži 2 karte. Igra se završava kada neki igrač objavi da ima sve 4 karte istog broja, u različitim bojama, i tada svi igrači prekidaju igru. Svaki igrač, dok god nema 4 iste i niko nije objavio da je pobednik, izbacuje jednu kartu iz svoje ruke i stavlja je na gomilu sa svoje leve strane, potom uzima jednu kartu iz gomile sa svoje desne strane. Pretpostaviti da su igračima inicijalno podeljene karte na slučajan način. Koristeći C-Linda, napisati izgled procedure za jednog igrača. Pored igrača, ne postoji nijedan drugi proces.
Rešenje
Ključna funkcija je void player(int i), dok ostale daju kontekst rešenju. Korišćeni tagovi su:
player: inicijalna podela karata igračimadeck: sadržaj jednog špila na stolugame over: da li je igra gotovacan set game over: da li igrač može da objavi da je pobedio (semafor okogame over)
typedef pair<int, int> Card;
template<typename T>
T randomChoice(vector<T>& vec) {
int index = rand() * vec.size() / RAND_MAX;
T ret = vec[index];
vec.erase(vec.begin() + index);
return ret;
}
bool hasWon(vector<Card>& cards) {
bool colors[4] = {false};
colors[cards[0].first] = true;
int num = cards[0].second;
for (int i = 1; i < 4; ++i) {
if (cards[i].second != num || colors[cards[i].first]) {
return false;
}
colors[cards[i].first] = true;
}
return true;
}
void player(int i) {
vector<Card> cards;
Card c;
for (int i = 0; i < 4; ++i) {
in("player", i, &c);
cards.push_back(c);
}
while (true) {
if (hasWon(cards)) {
in("can set game over");
if (!rdp("game over")) {
out("game over");
}
out("can set game over");
out("deck", (i + 1) % 4, Card(-1, -1));
break;
}
c = randomChoice(cards);
out("deck", (i + 1) % 4, c);
in("deck", i, &c);
if (rdp("game over")) {
break;
}
cards.push_back(c);
}
}
void initialize() {
// Празнимо простор торки од претходне игре
while (inp("deck") || inp("player") || inp("game over") || inp("can set game over"));
// Вршимо насумичну расподелу шпила
vector<Card> cards;
for (int color = 0; color < 4; ++color) {
for (int number = 0; number < 6; ++number) {
cards.push_back({color, number});
}
}
for (int d = 0; d < 4; ++d) {
for (int c = 0; c < 2; ++c) {
Card card = randomChoice(cards);
out("deck", d, card);
}
}
for (int p = 0; p < 4; ++p) {
for (int c = 0; c < 4; ++c) {
Card card = randomChoice(cards);
out("player", p, card);
}
eval(player, p);
}
out("can set game over");
}
Jun 2022, 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);
}
Februar 2020, 4. zadatak
- Ovaj zadatak nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.
Postavka
Posmatra se berbernica u kojoj za tri različite stolice rade tri berberina (The Hilzer's Barbershop problem). Pored ove tri stolice u berbernici se nalazi i čekaonica koja prima 10 mušterija koje mogu da sede i 10 koje mogu da stoje, ukupno 20. Kada mušterija dođe do berbernice ukoliko na šišanje čeka više od 20 mušterija onda odlazi, a ukoliko berbernica nije puna onda ostaje. Ukoliko barem jedan berberin spava mušterija koja dođe na red za šišanje budi onog berberina koji je najduže spavao i seda u njegovu stolicu. Na mesto te mušterije koja je ustala seda mušterija koja je najduže stajala. Ukoliko su svi berberi zauzeti onda mušterija čeka, i to ako ima mesta za sedenje seda, a ako ne onda stoji. Mušterije se opslužuju u redosledu po kome su prispele, i sedaju u istom tom redosledu. Kada berberin završi sa šišanjem mušterija mu plaća i izlazi iz berbernice. Berberin sve vreme ili spava ili šiša ili naplaćuje. Koristeći C-Linda napisati procese berberina i mušterija.
Rešenje
Februar 2022, 3. zadatak
Postavka
Koristeći C-Linda bibliioteku rešiti problem berberina koji spava (The Sleeping Barber Problem). Berbernica se sastoji od čekaonice sa n=5 stolica i berberske stolice na kojoj se ljudi briju. Ukoliko nema mušterija, brica spava. Ukoliko mušterija uđe u berbernicu 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.
Rešenje
Značenje tagova korišćenih u rešenju:
people: Broj ljudi u berberniciwakeup: Signal berberinu da se probudi od prve mušterijecurrent: Berberin javlja mušteriji da sedne na stolicusat: Mušterija javlja berberinu da je sela na stolicufinished: Berberin javlja mušteriji da je završioticket: Redni broj mušterije
const int N = 5;
void barber() {
int current = 0;
int currPeople;
in("people", &currPeople);
out("people", currPeople);
while (true) {
if (currPeople == 0) {
in("wakeup");
}
out("current", current++);
in("sat");
// Берберин шиша муштерију
in("people", &currPeople);
--currPeople;
out("people", currPeople);
out("finished");
}
}
bool customer() {
int currPeople;
in("people", &currPeople);
if (currPeople == 0) {
// Муштерија буди берберина
out("wakeup");
} else if (currPeople == N + 1) {
// Муштерија одлази
out("people", currPeople);
return false;
}
int myTicket;
in("ticket", &myTicket);
out("ticket", myTicket + 1);
out("people", currPeople + 1);
// Муштерија чека на свој ред
in("current", myTicket);
out("sat");
in("finished");
return true;
}
void initialize() {
out("ticket", 0);
out("people", 0);
}