KDP/Februar 2020
Februarski ispit 2020. godine održan je 8. februara. Postavka se može naći sa stranice predmeta (zipovana).
1. zadatak
- Ovaj zadatak nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.
Postavka
Koristeći raspodeljene binarne semafore rešiti problem proizvođača i potrošača (Producer – Consumer Problem).
Rešenje
2. zadatak
Postavka
Postoji grupa od N filozofa koji provodi svoj život tako što naizmenično filozofiraju, čekaju na piće, i piju (The Drinking Philosophers Problem). Filozofi su tako raspoređeni da je po jedna flaša sa pićem postavljena između susednih filozofa. U nekom trenutku filozof može da postane žedan. Žednom filozofu je potrebno nekoliko susednih flaša da bi napravio koktel i počeo da ga pije. Izbor pića zavisi od trenutnog raspoloženja i može se razlikovati od prilike do prilike. Kada prikupi sva potrebna pića filozof započinje sa njihovim ispijanjem koje traje izvesno vreme. Kada se napije, filozof vraća flaše da i drugi uživaju, a on prelazi na filozofiranje. Napisati program koji simulira ponašanje filozofa koristeći uslovne kritične regione.
Rešenje
#include <queue>
#include <vector>
using namespace std;
const int N = 100;
struct Table {
int drinks[N] = {-1};
queue<int> drinkQueues[N];
};
Table table;
void philosophizing();
void drinking();
vector<int> getDrinkRound();
void philosopher(int id) {
while (true) {
vector<int> drinks = getDrinkRound();
region (table) {
for (int drink : drinks) {
if (table.drinks[drink] == -1) {
table.drinks[drink] = id;
} else {
table.drinkQueues[drink].push(id);
await (table.drinks[drink] == id);
}
}
}
drinking();
region (table) {
for (int drink : drinks) {
if (table.drinkQueues[drink].empty()) {
table.drinks[drink] = -1;
} else {
int id = table.drinkQueues[drink].front();
table.drinkQueues[drink].pop();
}
}
}
philosophizing();
}
}
3. zadatak
- Ovaj zadatak nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.
Postavka
Filterski procesi imaju jedan ulaz i jedan izlaz. Procesi imaju samo tri lokacije. Napravite protočnu obradu (pipeline) od n ovih filterskih procesa koji pronalaze medijanu: do n ulaznih pozitivnih vrednosti (neparno) koje se ubacuju na početak protočne obrade, a završavaju se sa EOS. Na izlaz protočne obrade se šalje medijana pa EOS.
Rešenje
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.