KDP/Jul 2020

Postavka ovog roka može se naći sa stranice predmeta.

1. zadatak

Ovaj zadatak nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.

Postavka

Koristeći raspodeljene binarne semafore i tehniku predaje štafetne palice rešiti problem čitalaca i pisaca (Readers - Writers Problem).

2. zadatak

Postavka

Problem izgradnje molekula vode (The H2O Problem). Napisati monitor sa signal and continue disciplinom za rešavanje ovog problema, pod sledećim uslovima. Atomi vodonika, kada žele da naprave molekul vode, pozivaju monitorsku proceduru hReady(), atomi kiseonika pozivaju monitorsku proceduru oReady(). Poslednji pristigli atom treba da pozove monitorsku proceduru makeWater(), nakon čijeg završetka sva tri atoma treba da završe svoje odgovarajuće hReady() i oReady() procedure. Ne sme biti izgladnjivanja.

Rešenje

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() {
        // ...
    }
}

3. zadatak

Postavka

Koristeći aktivne monitore rešiti problem filozofa koji ručavaju (The Dining Philosophers). Filozofi mogu da komuniciraju isključivo sa procesom koordinatorom (centralizovano rešenje). Obezbediti da filozof koji je pre zatražio da jede pre i započinje sa jelom. Napisati kod za filozofe i za proces koordinator

Rešenje

Napomena: Zbog zahteva da filozof koji je pre zatražio da jede pre i započne sa jelom ide se po strogo FIFO redosledu, i filozofi koji su se zablokirali na čekanju viljuške neće je dobiti sve dok svi filozofi koji su zatražili viljušku pre njih ne dobiju svoju, i iz tog razloga je potrebna while petlja kod otpuštanja viljuške.

const int N = ...;
enum op_kind{REQUEST,RELEASE};
// Poslednji parametar ukazuje na to da li filozof trazi levu ili desnu viljusku
chan request(int, op_kind kind, bool);
chan reply[N](bool);

class Coordinator {
public:
    void run() {
        int philosopher;
        op_kind kind;
        bool left;
        queue<pair<int,int>> waiting;
        int forks[N] = {};
        while (true) {
            receive request(philosopher, kind, left);
            int fork = left ? philosopher : (philosopher + 1) % N;
            if (kind == REQUEST) {
                if (forks[fork] == 0) {
                    forks[fork] = 1;
                    send reply[philosopher](true);
                } else {
                    waiting.push(make_pair(philosopher, fork));
                }
            } else if (kind == RELEASE) {
                forks[fork] = 0;
                while (!waiting.empty() && forks[waiting.front().second] == 0){
                    send reply[waiting.front().first](true);
                    waiting.pop();
                }
            }
        }
    }
}

void philosopher(int id) {
    bool status;
    while(true) {
        // Think
        send request(id, REQUEST, id != 0);
        receive reply[id](status);
        send request(id, REQUEST, id == 0);
        receive reply[id](status);
        // Eat
        send request(id, RELEASE, id != 0);
        send request(id, RELEASE, id == 0);
    }
}

4. zadatak

Ovaj zadatak nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.

Postavka

Posmatra se semafor za regulaciju saobraćaja na ulici sa jednim pešačkim prelazom. Kada pešak stigne do pešačkog prelaza, ukoliko je svetlo za pešake zeleno, on prelazi ulicu. Ukoliko je u momentu njegovog dolaska svetlo za pešake crveno, on čeka da se uključi zeleno svetlo. Zeleno svetlo za pešake se uključuje ili nakon K sekundi od pojave prvog pešaka koji je zatekao crveno svetlo, ili nakon prolaska C automobila od poslednjeg aktivnog zelenog svetla za pešake. Zeleno svetlo za pešake trajanja G sekundi se pali samo ukoliko je ispunjen neki od navedenih uslova i barem jedan pešak čeka. Potrebno je u jeziku CSP napisati procese pešaka, automobila i semafora, ukoliko je poznato da u sistemu postoji N automobila i T pešaka. Dostupna je funkcija system_current_time koja vraća trenutno vreme sistema.