КДП/К 2019

Поставка овог рока може се наћи са странице предмета (зипована).

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

Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.

Поставка

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

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