KDP/K 2019

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) {
        // Следећи мора да је писац, јер да је читалац листа би била празна
        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

Ovaj zadatak nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.

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.