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).

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 {
                    table.drinks[drink] = 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.

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.