КДП/Јул 2020

Поставка овог рока може се наћи са странице предмета.

1. задатак

Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.

Поставка

Користећи расподељене бинарне семафоре и технику предаје штафетне палице решити проблем читалаца и писаца (Readers - Writers Problem).

2. задатак

Поставка

Проблем изградње молекула воде (The H2O Problem). Написати монитор са signal and continue дисциплином за решавање овог проблема, под следећим условима. Атоми водоника, када желе да направе молекул воде, позивају мониторску процедуру hReady(), атоми кисеоника позивају мониторску процедуру oReady(). Последњи пристигли атом треба да позове мониторску процедуру makeWater(), након чијег завршетка сва три атома треба да заврше своје одговарајуће hReady() и oReady() процедуре. Не сме бити изгладњивања.

Решење

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. задатак

Поставка

Користећи активне мониторе решити проблем филозофа који ручавају (The Dining Philosophers). Филозофи могу да комуницирају искључиво са процесом координатором (централизовано решење). Обезбедити да филозоф који је пре затражио да једе пре и започиње са јелом. Написати код за филозофе и за процес координатор

Решење

Напомена: Због захтева да филозоф који је пре затражио да једе пре и започне са јелом иде се по строго ФИФО редоследу, и филозофи који су се заблокирали на чекању виљушке неће је добити све док сви филозофи који су затражили виљушку пре њих не добију своју, и из тог разлога је потребна while петља код отпуштања виљушке.

const int N = ...;
enum op_kind{ACQUIRE,RELEASE};
// Poslednji parametar ukazuje na to da li filozof trazi levu (true) ili desnu (false) viljusku
chan request(int, op_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 == ACQUIRE) {
                if (forks[fork] == 0) {
                    forks[fork] = 1;
                    send reply[philosopher](true);
                } else {
                    waiting.push({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, ACQUIRE, id != 0);
        receive reply[id](status);
        send request(id, ACQUIRE, id == 0);
        receive reply[id](status);
        // Eat
        send request(id, RELEASE, id != 0);
        send request(id, RELEASE, id == 0);
    }
}

4. задатак

Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.

Поставка

Посматра се семафор за регулацију саобраћаја на улици са једним пешачким прелазом. Када пешак стигне до пешачког прелаза, уколико је светло за пешаке зелено, он прелази улицу. Уколико је у моменту његовог доласка светло за пешаке црвено, он чека да се укључи зелено светло. Зелено светло за пешаке се укључује или након К секунди од појаве првог пешака који је затекао црвено светло, или након проласка C аутомобила од последњег активног зеленог светла за пешаке. Зелено светло за пешаке трајања G секунди се пали само уколико је испуњен неки од наведених услова и барем један пешак чека. Потребно је у језику CSP написати процесе пешака, аутомобила и семафора, уколико је познато да у систему постоји N аутомобила и T пешака. Доступна је функција system_current_time која враћа тренутно време система.