KDP/K1 2018

Prvi kolokvijum 2018. godine održan je 19. marta. Postavka ovog roka može se naći sa stranice predmeta (zipovana).

1. zadatak

Postavka

Potrebno je uraditi sinhronizaciju na barijeri koja funkcioniše na sledeći način: postoje dva procesa koordinatora za po polovinu radnih procesa (pretpostaviti paran broj radnih procesa) koji treba da se sinhronizuju na barijeri. Pritom, ta dva procesa koordinatora prvo zaključuju kada su svi njihovi procesi stigli do njihovih internih podbarijera i kroz postupak međusobne komunikacije koordinatora utvrđuju kada su svi radni procesi stigli do ekvivalentne jedinstvene barijere. Nakon toga oba procesa koordinatora treba da dozvole radnim procesima da prođu barijeru. Napisati kôd radnih procesa i oba procesa koordinatora.

Rešenje

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. zadatak

Postavka

Negde u Africi postoji dubok kanjon na čijim liticama žive babuni (The Baboons Crossing Problem). Između dve litice kanjona postoji lijana preko koje babuni prelaze reku. Da bi se izbegao sukob između babuna u jednom trenutku na lijani smeju da se nađu samo babuni koji pripadaju jednoj strani kanjona. Takođe, lijana može da izdrži najviše 5 babuna, inače puca. Koristeći semafore napisati program za babune sa obe strane kanjona.

Rešenje

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