КДП/Август 2021

Августовски испит 2021. године одржан је 2. септембра. Поставка овог рока може се наћи са странице предмета.

1. задатак

Сличан задатак дошао је у јануару 2020. године са Signal and Wait дисциплином.

Поставка

Потребно је реализовати семафор који поред стандардних атомских операција signal() и wait() има и атомске операције signal(n) и wait(n) које интерну семафорску променљиву атомски увећава односно умањује за n уколико је то могуће, уколико није чека док не буде било могуће. Потребно је решити проблем користећи мониторе који имају Signal and Continue дисциплину. Процес који је раније упутио захтев треба раније да обави своју операцију. Број процеса и максимална вредност n нису унапред познати. Условне променљиве су FIFO према тренутку доласка, немају приоритетну методу wait и има их коначан број.

Решење

class Semaphore {
    private int value;
    private Queue<Integer> requests = new Queue<>();
    private Condition queue = new Condition();
    public Semaphore(int value) {
        this.value = value;
    }
    public synchronized void wait(int num) {
        if (value >= num) {
            value -= num;
        } else {
            requests.insert(num);
            queue.wait();
        }
    }
    public synchronized void signal(int num) {
        value += num;
        while (requests.size() > 0 && value >= requests.top()) {
            value -= requests.pop();
            queue.signal();
        }
    }
    public synchronized void wait() {
        wait(1);
    }
    public synchronized void signal() {
        signal(1);
    }
}

2. задатак

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

Поставка

У свемиру постоји N небеских тела која међусобно интерагују (N Body Gravitational Problem). Користећи семафоре потребно је решити овај проблем користећи торбу послова за дохватање посла. Потребно је реализовати следеће: Worker (обавља израчунавање), Bag (обавља поделу посла) и Collector (обавља прикупљање резултата).

Решење

Док овај задатак није решен, од користи може бити информација шта се у задатку отприлике очекивало:

• Чињеница да се у задатку ради о небеским телима је потпуно небитна.
• Worker нити врше нека израчунавања над небеским телима (може се моделовати неком методом нпр. izracunaj()).
• Параметри ових израчунавања (шта се тачно рачуна) морају бити преузети од Bag нити. Овај модел познат је као bag of tasks и објашњен је у књизи Захарија Радивојевића Конкурентно и дистрибуирано програмирање на страни 22.
• На крају свих израчунавања Collector нит их преузима. Након што та нит обради преузете резултате, даје Bag нити додатне параметре израчунавања која се опет прослеђују Worker нитима.

За све недоумице око поставке овог задатка обратити се Сањи Делчев.

3. задатак

Поставка

Решити проблем филозофа који ручавају (Dining Philosophers Problem) користећи концепт рандевуа (Rendezvous).

Решење

Module Server
    op dohvatiViljuske(idF);
    op vratiViljuske(idF);
Body
Process Server{
    const int N = 5;
    boolean jedu[N] = {false};
    while(true){
        //pretpostavka da kompajler vraca negativne vrednosti za moduo
        in dohvatiViljusku(i) and !jedu[(i-1)%N<0 ? ((i-1)%N+N) : (i-1)%N] and !jedu[(i+1)%N] -> jedu[i] = true;
        [] vratiViljuske(i) -> jedu[i] = false;
        ni
    }
}
End Server;

procces Filozof[i=0..4]{
    while(true){
        misli;
        call Server.dohvatiViljuske(i);
        jedi;
        call Server.vratiViljuske(i);
    }
}

4. задатак

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

Поставка

Постоји један произвођач и N потрошача који деле заједнички бафер капацитета B (Atomic broadcast problem). Произвођач убацује производ у бафер и то само у слободне слотове на који чекају свих N потрошача. Сваки потрошач мора да прими производ у тачно оном редоследу у коме су произведени, мада различити потрошачи могу у исто време да узимају различите производе. Произвођачи и потрошачи могу да комуницирају искључиво са процесом координатором (централизовано решење) који има само један ток контроле и понаша се као активни монитор. Сваки процес има само једно сандуче из кога може да чита, и из сваког сандучета може да чита само један процес док већи број може да уписује. Написати код за произвођаче, потрошаче и за процес координатор.