КДП/Август 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. задатак

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

Поставка

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

4. задатак

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