KDP/K 2019

Kolokvijum 2019. godine za RTI održan je 24. novembra. Postavka ovog roka može se naći sa stranice predmeta (zipovana).

1. zadatak

Postavka

Rešiti problem čitalaca i pisaca (Reader Writers Problem) koristeći semafore. Obezbediti da procesi započinju pristup resursu po redosledu slanja zahteva. Pretpostaviti da u nekom trenutku maksimalno N procesa može uputiti zahtev za pristup resursu.

Rešenje

const int N = 100;
// Један више како бисмо могли да користимо проверу head == tail
// да бисмо видели да ли је листа празна
sem sems[N + 1];
bool isReader[N + 1];
int head = 0;
int tail = 0;
sem mutex;
// count == -1 => писац
int count = 0;

void read();
void write();

void reader() {
    mutex.wait();
    if (head == tail && count >= 0) {
        // Ако је листа празна значи да сигурно немамо писаца у њој
        ++count;
        mutex.signal();
    } else {
        int index = tail;
        tail = (tail + 1) % (N + 1);
        isReader[index] = true;
        mutex.signal();
        sems[index].wait();
    }
    read();
    mutex.wait();
    if (--count == 0 && head != tail) {
        // Следећи мора да је писац, јер да је читалац листа би била празна
        count = -1;
        sems[head].signal();
        head = (head + 1) % (N + 1);
    }
    mutex.signal();
}

void writer() {
    mutex.wait();
    if (head == tail && count == 0) {
        // Ако нема читалаца нити писаца и листа је празна, можемо само да прођемо
        --count;
        mutex.signal();
    } else {
        int index = tail;
        tail = (tail + 1) % (N + 1);
        isReader[index] = false;
        mutex.signal();
        sems[index].wait();
    }
    write();
    mutex.wait();
    if (head == tail) {
        // Нико више не чека
        count = 0;
    } else if (isReader[head]) {
        // Чекају читаоци иза писца
        count = 0;
        while (isReader[head] && head != tail) {
            ++count;
            sems[head].signal();
            head = (head + 1) % (N + 1);
        }
    } else {
        // Чека писац иза писца
        sems[head].signal();
        head = (head + 1) % (N + 1);
    }
    mutex.signal();
}

2. zadatak

Postavka

Posmatra se jedna podzemna garaža. Postoji samo jedna rampa koja služi i za ulaz, i za izlaz iz garaže. Kroz rampu u jednom trenutku može da prolazi samo jedan automobil iz bilo kog smera. U garaži ima N mesta za parkiranje. Automobili koji ulaze, mogu da uđu, jedan po jedan, ukoliko ima slobodnih mesta, po redosledu po kojem su tražili ulaz. Ukoliko slobodnog mesta nema, proverava se da li ima automobila koji hoće da izađu. Ako nakon izlaska svih automobila koji žele da izađu i ulaska automobila koji su došli pre njega za automobil neće biti mesta, on odlazi u potragu za drugom garažom. Automobili pri izlasku plaćaju usluge garaže i izlaze jedan po jedan, po redosledu po kojem su zatražili izlazak. Prednost na rampi imaju automobili koji izlaze iz garaže.

Napisati monitor sa signal and continue disciplinom koji ima sledeće metode: boolean trazim_ulaz(), za traženje dozvole za ulaz u garažu, koja vraća true ako se dozvoljava ulaz u garažu, a false ako nema mesta; void usao(), za obaveštavanje o ulasku u garažu; void trazim_izlaz() za traženje dozvole za izlaskom iz garaže; void izasao() za obaveštavanje o izlasku iz garaže.

Rešenje

class PodzemnaGaraza {
    private static final int N = 100;
    private int ulazi = 0;
    private int izlazi = 0;
    private int parkirano = 0;
    private boolean rampaZauzeta = false;
    private Condition ulaziRed = new Condition();
    private Condition izlaziRed = new Condition();
    public synchronized boolean trazim_ulaz() {
        if (parkirano + ulazi == N) {
            return false;
        }
        ++ulazi;
        if (!ulaziRed.queue() && !izlaziRed.queue() && !rampaZauzeta) {
            // Нема никога, улазимо
            rampaZauzeta = true;
            return true;
        }
        ulaziRed.wait();
        // rampaZauzeta је постављена од стране нити која сигнлизира
        return true;
    }
    public synchronized void usao() {
        ++parkirano;
        --ulazi;
        signal();
    }
    public synchronized void trazim_izlaz() {
        ++izlazi;
        --parkirano;
        if (!izlaziRed.queue() && !rampaZauzeta) {
            rampaZauzeta = true;
            return;
        }
        izlaziRed.wait();
        // rampaZauzeta је постављена од стране нити која сигнлизира
    }
    public synchronized void izasao() {
        --izlazi;
        signal();
    }
    private void signal() {
        rampaZauzeta = false;
        if (izlaziRed.queue()) {
            rampaZauzeta = true;
            izlaziRed.signal();
        } else if (ulaziRed.queue() && parkirano + izlazi < N) {
            rampaZauzeta = true;
            ulaziRed.signal();
        }
    }
}