KDP/K 2021

Kolokvijum 2021. godine za RTI održan je 27. novembra. Postavka ovog roka može se naći sa stranice predmeta.

1. zadatak

Postavka

Monitor treba da obezbedi skupljanje gajbica sa ivice voćnjaka. Procesi berači donose po nekoliko punih gajbica (zavisno od nosivosti berača) do puta na ivici njive. Kada pored puta berači ostave bar prikolica_kapacitet gajbica, treba da se probudi jedan od procesa traktor_sa_prikolicom, da dođu do puta kraj njive i pokupe onoliko gajbica koliko staje u prikolicu (prikolica_kapacitet). Procesi traktor_sa_prikolicom pozivaju monitorsku proceduru spreman_da_pokupim kada završe prevoz prethodne prikolice voća. Berači pozivaju monitorsku proceduru ostavljam_gajbice, kada donesu gajbice do ivice puta. Obezbediti da proces traktor_sa_prikolicom koji je pre došao pre treba i da se utovari. Podrazumevati Signal and Continue disciplinu.

Rešenje

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

    synchronized void spreman_da_pokupim() {
        if (broj_gajbica < prikolica_kapacitet) {
            pokupi.wait(maxrank++);
        }
        broj_gajbica -= prikolica_kapacitet;
    }

    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. zadatak

Postavka

Problem vožnje autobusom (The bus problem). Putnici dolaze na autobusku stanicu i čekaju prvi autobus koji naiđe. Autobus kreće sa stanice kada svi putnici koji su bili na stanici u trenutku dolaska autobusa provere da li mogu da uđu i uđu ukoliko ima mesta. Putnici se izjašnjavaju na kojoj stanici će izaći iz autobusa. Kapacitet autobusa je K mesta. Putnici koji su došli dok je autobus bio na stanici čekaju na sledeći autobus. Postoje M autobusa koji saobraćaju između N stanica. Koristeći uslovne kritične regione napisati program za putnike i autobuse.

Rešenje

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;
        }
    }
}