КДП/Јануар 2020

Јануарски испит 2020. године одржан је 18. јануара. Поставка овог рока може се наћи са странице предмета (зипована).

1. задатак

Сличан задатак дошао је у августу 2021. године са Signal and Continue дисциплином.

Поставка

Потребно је реализовати семафор који поред стандардних атомских операција signal() и wait() има и атомске операције signal(n) и wait(n) која интерну семафорску променљиву атомски увећава односно умањује за n уколико је то могуће, уколико није чека док не буде били могуће. Потребно је решити проблем користећи мониторе који имају Signal and Wait дисциплину. Процес који је раније упутио захтев треба раније да обави своју операцију. Број процеса и максимална вредност 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();
            internalSignal();
        }
    }
    public synchronized void signal(int num) {
        value += num;
        internalSignal();
    }
    public synchronized void wait() {
        wait(1);
    }
    public synchronized void signal() {
        signal(1);
    }
    private void internalSignal() {
        if (requests.size() > 0 && value >= requests.top()) {
            value -= requests.pop();
            queue.signal();
        }
    }
}

2. задатак

Поставка

Користећи семафоре написати програм који решава проблем путовања лифтом. Путник позива лифт са произвољног спрата. Када лифт стигне на неки спрат сви путници који су изразили жељу да сиђу на том спрату обавезно изађу. Након изласка путника сви путници који су чекали на улазак уђу у лифт и кажу на који спрат желе да пређу. Тек када се сви изјасне лифт прелази даље. Лифт редом обилази спратове и стаје само на оне где има путника који улазе или излазе. Може се претпоставити да постоји N спратова.

Решење

struct Floor {
    list<sem*> peopleEntering;
    sem mutexEntering = 1;
    list<sem*> peopleExiting;
    sem mutexExiting = 1;
};

const int N = 10;
Floor floors[N];
sem liftSem = 0;

void person() {
    sem personSem = 0;
    int currentFloorIndex = rand() % N;
    while (true) {
        // Особа може да каже да хоће да изађе на истом спрату као тренутном
        // Претпоставка: особа није глупа
        int nextFloorIndex = rand() % N;
        Floor& currentFloor = floors[currentFloorIndex];
        Floor& nextFloor = floors[nextFloorIndex];
        currentFloor.mutexEntering.wait();
        currentFloor.peopleEntering.push_back(&personSem);
        currentFloor.mutexEntering.signal();
        // Чекамо да дође лифт
        personSem.wait();
        // Улазимо у лифт и бирамо на којем спрату стајемо
        nextFloor.mutexExiting.wait();
        nextFloor.peopleExiting.push_back(&personSem);
        nextFloor.mutexExiting.signal();
        liftSem.signal();
        // Чекамо да лифт стигне на наш спрат
        personSem.wait();
        // Излазимо из лифта
        liftSem.signal();
    }
}

void lift() {
    int currentFloorIndex = 0;
    bool goingUp = true;
    while (true) {
        // Одређивање следећег спрата
        // Претпоставка: лифт све време иде горе-доле, без обзира да ли га је неко звао
        if (goingUp) {
            if (++currentFloorIndex == N-1) {
                goingUp = false;
            }
        } else {
            if (--currentFloorIndex == 0) {
                goingUp = true;
            }
        }
        Floor& floor = floors[currentFloorIndex];
        // Не морамо да чекамо на mutexExiting, јер се он заузима само када путници улазе
        // што тренутно није случај
        int countPeopleExiting = floor.peopleExiting.size();
        // Задржавамо mutexEntering док не испразнимо листу, како нам не би ушао неочекивани путник
        floor.mutexEntering.wait();
        int countPeopleEntering = floor.peopleEntering.size();
        if (countPeopleExiting == 0 && countPeopleEntering == 0) {
            // Не стајемо на овом спрату
            floor.mutexEntering.signal();
            continue;
        }
        // Стајемо на овом спрату
        // Пуштамо људе да изађу
        for (int i = 0; i < countPeopleExiting; ++i) {
            sem* personSem = floor.peopleExiting.front();
            personSem->signal();
            floor.peopleExiting.pop_front();
        }
        for (int i = 0; i < countPeopleExiting; ++i) {
            liftSem.wait();
        }
        // Пуштамо људе да уђу
        for (int i = 0; i < countPeopleEntering; ++i) {
            sem* personSem = floor.peopleEntering.front();
            personSem->signal();
            floor.peopleEntering.pop_front();
        }
        for (int i = 0; i < countPeopleEntering; ++i) {
            liftSem.wait();
        }
        floor.mutexEntering.signal();
        // Настављамо на следећи спрат
    }
}

3. задатак

Поставка

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

Решење

enum op_kind { WAIT, SIGNAL, WAITN, SIGNALN };
chan request(int, op_kind, int);
chan reply[n](bool);

class Semaphore {
public:
    void run() {
        int clientID;
        op_kind kind;
        int n;
        int tokens = 0;
        queue<pair<int,int>> pending;
        while (true) {
            receive request(clientID, kind, n);
            if (kind == WAIT) {
                if (tokens <= 0) {
                    pending.push(make_pair(clientID, 1));
                } else {
                    tokens--;
                    send reply[clientID](true);
                }
            } else if (kind == WAITN) {
                if (tokens <= n-1) {
                    pending.push(make_pair(clientID, n));
                } else {
                    tokens = tokens-n;
                    send reply[clientID](true);
                }
            } else if (kind == SIGNAL) {
                tokens++;
                if (!pending.empty() && pending.front().second == tokens) {
                    tokens = 0;
                    send reply[pending.front().first](true);
                    pending.pop();
                }
            } else if (kind == SIGNALN) {
                tokens += n;
                while (!pending.empty() && pending.front().second <= tokens) {
                    tokens -= pending.front().second;
                    send reply[pending.front().first](true);
                    pending.pop();
                }
            }
        }
    }
}

4. задатак

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

Поставка

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