КДП/Јануар 2020

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

1. задатак

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

Поставка

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

2. задатак

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

Поставка

Користећи семафоре написати програм који решава проблем путовања лифтом. Путник позива лифт са произвољног спрата. Када лифт стигне на неки спрат сви путници који су изразили жељу да сиђу на том спрату обавезно изађу. Након изласка путника сви путници који су чекали на улазак уђу у лифт и кажу на који спрат желе да пређу. Тек када се сви изјасне лифт прелази даље. Лифт редом обилази спратове и стаје само на оне где има путника који улазе или излазе. Може се претпоставити да постоји 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. задатак

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

Поставка

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

4. задатак

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

Поставка

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