КДП/К 2019

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

1. задатак

Поставка

Решити проблем читалаца и писаца (Reader Writers Problem) користећи семафоре. Обезбедити да процеси започињу приступ ресурсу по редоследу слања захтева. Претпоставити да у неком тренутку максимално N процеса може упутити захтев за приступ ресурсу.

Решење

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. задатак

Поставка

Посматра се једна подземна гаража. Постоји само једна рампа која служи и за улаз, и за излаз из гараже. Кроз рампу у једном тренутку може да пролази само један аутомобил из било ког смера. У гаражи има N места за паркирање. Аутомобили који улазе, могу да уђу, један по један, уколико има слободних места, по редоследу по којем су тражили улаз. Уколико слободног места нема, проверава се да ли има аутомобила који хоће да изађу. Ако након изласка свих аутомобила који желе да изађу и уласка аутомобила који су дошли пре њега за аутомобил неће бити места, он одлази у потрагу за другом гаражом. Аутомобили при изласку плаћају услуге гараже и излазе један по један, по редоследу по којем су затражили излазак. Предност на рампи имају аутомобили који излазе из гараже.

Написати монитор са signal and continue дисциплином који има следеће методе: boolean trazim_ulaz(), за тражење дозволе за улаз у гаражу, која враћа true ако се дозвољава улаз у гаражу, а false ако нема места; void usao(), за обавештавање о уласку у гаражу; void trazim_izlaz() за тражење дозволе за изласком из гараже; void izasao() за обавештавање о изласку из гараже.

Решење

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