КДП/К 2021

Колоквијум 2021. године за РТИ одржан је 27. новембра. Поставка овог рока може се наћи са странице предмета.

1. задатак

Поставка

Монитор треба да обезбеди скупљање гајбица са ивице воћњака. Процеси берачи доносе по неколико пуних гајбица (зависно од носивости берача) до пута на ивици њиве. Када поред пута берачи оставе бар prikolica_kapacitet гајбица, треба да се пробуди један од процеса traktor_sa_prikolicom, да дођу до пута крај њиве и покупе онолико гајбица колико стаје у приколицу (prikolica_kapacitet). Процеси traktor_sa_prikolicom позивају мониторску процедуру spreman_da_pokupim када заврше превоз претходне приколице воћа. Берачи позивају мониторску процедуру ostavljam_gajbice, када донесу гајбице до ивице пута. Обезбедити да процес traktor_sa_prikolicom који је пре дошао пре треба и да се утовари. Подразумевати Signal and Continue дисциплину.

Решење

class SkupljanjeGajbica {
    private static final int prikolica_kapacitet = 100;
    private int broj_gajbica = 0;
    private Condition pokupi;
    private int maxrank = 1;
    private int waiting = 0;

    public synchronized void spreman_da_pokupim() {
        if (broj_gajbica < prikolica_kapacitet || waiting > 0) {
            ++waiting;
            pokupi.wait(maxrank++);
            --waiting;
        }
        broj_gajbica -= prikolica_kapacitet;
    }

    public synchronized void ostavljam_gajbice(int broj) {
        broj_gajbica += broj;
        int broj_signala = broj_gajbica / prikolica_kapacitet;
        for (int i = 0; i < broj_signala; ++i) {
            pokupi.signal();
        }
    }
}

2. задатак

Поставка

Проблем вожње аутобусом (The bus problem). Путници долазе на аутобуску станицу и чекају први аутобус који наиђе. Аутобус креће са станице када сви путници који су били на станици у тренутку доласка аутобуса провере да ли могу да уђу и уђу уколико има места. Путници се изјашњавају на којој станици ће изаћи из аутобуса. Капацитет аутобуса је K места. Путници који су дошли док је аутобус био на станици чекају на следећи аутобус. Постоје M аутобуса који саобраћају између N станица. Користећи условне критичне регионе написати програм за путнике и аутобусе.

Решење

const int N = 100;
const int M = 100;
const int K = 50;

// Одређују са које станице на коју станицу иду путници
// Претпоставља се да један путник неће ићи са једне на ту исту станицу
int getStationIdFrom();
int getStationIdTo();

struct Station {
    // Број путника који чекају на станици
    int numPassengers = 0;
    // Број путника који треба да провере свој статус
    // пре него што аутобус настава
    int passengersChecking = 0;
    // Овим бројем ће бити ажуриран број путника у аутобусу
    // након што сви путници провере свој статус
    int busPassengers = 0;
    // Редослед доласка аутобуса на станицу
    int currTicket = 0;
    int nextTicket = 0;
    // Аутобус који је тренутно на станици
    int busId = -1;
    // Број путника који треба да изађу на станици
    // из одређеног аутобуса
    int passengersExiting[M] = {0};
};
Station stations[N];

void bus(int busId) {
    int stationId = 0;
    int numPassengers = 0;
    while (true) {
        Station& station = stations[stationId];
        region (station) {
            int myTicket = station.nextTicket++;
            // Чекамо ред на станици
            await (station.currTicket == myTicket);
            station.busId = busId;
            station.passengersChecking = station.numPassengers + station.passengersExiting[busId];
            station.busPassengers = numPassengers;
            // Чекамо да сви путници који улазе или излазе провере свој статус
            await (station.passengersChecking == 0);
            station.busId = -1;
            numPassengers = station.busPassengers;
            // Пуштамо следећи аутобус
            ++station.currTicket;
        }
        // Путујемо
        // Бирамо следећу станицу по кружном принципу
        stationId = (stationId + 1) % N;
    }
}

void passenger() {
    while (true) {
        Station& stationFrom = stations[getStationIdFrom()];
        Station& stationTo = stations[getStationIdTo()];
        bool entranceSuccessful = false;
        int currentBusId;
        while (!entranceSuccessful) {
            region (stationFrom) {
                // Дошли смо на станицу
                ++stationFrom.numPassengers;
                if (stationFrom.busId == -1) {
                    // Чекамо аутобус
                    await (stationFrom.busId != -1);
                } else {
                    // Аутобус је већ био ту, проверавамо статус
                    ++stationFrom.passengersChecking;
                }
                currentBusId = stationFrom.busId;
                if (stationFrom.busPassengers < K) {
                    // Успели смо да уђемо у аутобус
                    ++stationFrom.busPassengers;
                    --stationFrom.numPassengers;
                    entranceSuccessful = true;
                }
            }
            region (stationTo) {
                if (entranceSuccessful) {
                    ++stationTo.passengersExiting[currentBusId];
                }
            }
            region (stationFrom) {
                // Проверили смо свој статус и ажурирали бројеве
                --stationFrom.passengersChecking;
            }
        }
        // Путујемо
        region (stationTo) {
            // Чекамо док аутобус не дође на станицу
            await (stationTo.busId == currentBusId);
            --stationTo.passengersExiting[currentBusId];
            --stationTo.busPassengers;
            --stationTo.passengersChecking;
        }
    }
}