КДП/К1 2018

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

1. задатак

Поставка

Потребно је урадити синхронизацију на баријери која функционише на следећи начин: постоје два процеса координатора за по половину радних процеса (претпоставити паран број радних процеса) који треба да се синхронизују на баријери. Притом, та два процеса координатора прво закључују када су сви њихови процеси стигли до њихових интерних подбаријера и кроз поступак међусобне комуникације координатора утврђују када су сви радни процеси стигли до еквивалентне јединствене баријере. Након тога оба процеса координатора треба да дозволе радним процесима да прођу баријеру. Написати кôд радних процеса и оба процеса координатора.

Решење

const int N = ...;
sem arrive[N] = {0};
sem pass[N] = {0};
bool coordinator = false;
sem coordinatorSem = 0;
sem mutex = 1;

void coordinator1() {
    for (int i = 0; i < N / 2; i++) arrive[i].wait();
    mutex.wait();
    if (coordinator) {
        coordinator = false;
        mutex.signal();
        coordinatorSem.signal();
    } else {
        coordinator = true;
        mutex.signal();
        coordinatorSem.wait();
    }
    for (int i = 0; i < N / 2; i++) pass[i].signal();
}

void coordinator2() {
    for (int i = N / 2; i < N; i++) arrive[i].wait();
    mutex.wait();
    if (coordinator) {
        coordinator = false;
        mutex.signal();
        coordinatorSem.signal();
    } else {
        coordinator = true;
        mutex.signal();
        coordinatorSem.wait();
    }
    for (int i = N / 2; i < N; i++) pass[i].signal();
}

void process(int i) {
    while (true) {
        work();
        arrive[i].signal();
        pass[i].wait();
    }
}

2. задатак

Поставка

Негде у Африци постоји дубок кањон на чијим литицама живе бабуни (The Baboons Crossing Problem). Између две литице кањона постоји лијана преко које бабуни прелазе реку. Да би се избегао сукоб између бабуна у једном тренутку на лијани смеју да се нађу само бабуни који припадају једној страни кањона. Такође, лијана може да издржи највише 5 бабуна, иначе пуца. Користећи семафоре написати програм за бабуне са обе стране кањона.

Решење

const int N = 5;
int baboons = 0;
int currentSide = 0;
sem waiting[2] = {0};
List<int> list;
sem mutex=0;

// side je 0 ili 1, u zavisnosti sa koje strane kanjona se nalazi
void baboon(int side) {
    mutex.wait();
    // Uslov list.size() == 0 da ne bi doslo do izgladnjivanja
    if (baboons == 0 || (currentSide == side && baboons < N && list.size() == 0)) {
        currentSide=side;
        baboons++;
        mutex.signal();
    } else {
        list.add(side);
        mutex.signal();
        waiting[side].wait();
    }

    cross();

    mutex.wait();
    baboons--;
    if (list.size() > 0) {
        // Ako je sledeci zablokiran kretao sa iste strane, moze da krene kada jedan babun predje na drugu stranu
        if (list.get(0) == side) {
            list.pop(0);
            baboons++;
            waiting[side].signal();
        } else if (baboons == 0) {
            // Ako je sledeci zablokiran kretao sa suprotne strane, moze da krene samo kada svi babuni sa prvobitne
            // strane predju lijanu, i sa njim mozemo pustiti jos maksimalno 4(N-1) babuna sa iste strane ako su
            // se svi zablokirali za redom
            currentSide = !side;
            while (list.get(0) == (!side) && baboons < N) {
                list.pop(0);
                baboons++;
                waiting[!side].signal();
            }
        }
    }
    mutex.signal();
}