КДП/Јун 2022

Испит у јунском испитном року 2022. године одржан је 14. јуна. Поставка овог рока још увек није доступна са странице предмета.

1. задатак

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

Поставка

Објасните шта је At-Most-Once-Property. Објасните зашто, када је испуњена та особина, критична референца има особине атомске акције. Дати два примера у којима су по два процеса.

2. задатак

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

Поставка

Постоје три особе међу којима треба изабрати једну (The Odd Person Wins Game). Свака од тих особа поседује новчић који има две стране. Избор особе се одиграва тако што свака особа независно баца свој новчић. Уколико постоји особа којој је новчић пао на другу страну у односу на преостале особе, онда се та особа изабира. Уколико све особе имају исто постављен новчић, поступак се понавља све док се не изабере једна. Особе након сваког бацања морају да знају да ли су изабране или не или се поступак понавља. Користећи семафоре написати програм који описује понашање особе. Ниједној особи не треба давати предност на основу њиховог идентификатора.

3. задатак

Поставка

Монитор треба да регулише распоред уласка пацијената на преглед код једног лекара. Сваки регуларно заказани пацијент је пре приступања том монитору добио један од 12 хронолошки поређаних полусатних интервала за тај дан (прављење распореда није део задатка). Пацијент када дође на преглед (не мора да буде тачан) позива мониторску процедуру želim_da_se_pregledam и том приликом доставља ID и почетак полусатног интервала у коме је њему заказан преглед. Ако је лекар заузет, пацијенти на чекању ће се поређати на основу хронолошког редоследа у распореду за тај дан. Лекар позива мониторску процедуру sledeći, која враћа идентификатор следећег пацијента, када жели да прегледа следећег пацијента. Ако нема пацијената у том случају, лекар се поствља у стање чекања из кога излази када наиђе први пацијент. Написати овакав монитор користећи дисциплину Signal and Wait и условне променљиве код којих нема приоритетних редова чекања. Монитор не треба да садржи синхронизацију везану за крај прегледа.

Решење

// pretpostavka da je ID 0-11
class Monitor {
    private Condition[] awaitPatient[12], awaitDoctor;
    private boolean[] patientChecked[12];  // da li je pacijent pregledan, potreban zbog signal&wait
    private PriorityQueue<<int,int>> pq;   // prioritetni red slot, ID, sortiran po slotu
    
    public synchronized void zelim_da_se_pregledam(int ID, int slot) {
        pq.add(slot,ID);
        awaitDoctor.signal();
        // potrebno jer signal&wait predaje kontrolu pa je pacijent u medjuvremenu mozda pregledan
        if (patientChecked[ID] == false) awaitPatient[ID].wait();
    }
    
    public synchronized int sledeci() {
        if (pq.size() == 0) awaitDoctor.wait();
        int id = pq.pop().first;
        pq.remove();
        patientChecked[id] = true;
        awaitPatient[id].signal();
        return id;
    }
}

4. задатак

Поставка

Трајект за превоз аутомобила, камиона и аутобуса превози возила са обале на обалу. Трајект поседује N позиција које су линеарно постављене једна иза друге. Камион заузима три, аутобус две, а аутомобил једну позицију. Возила чекају на трајект у реду и на њега улазе једно по једно по редоследу у којем чекају у реду, док на трајекту има места. Када наредно возило у реду за трајект нема места да се укрца или када је трајект пун, трајект започиње превоз возила на другу обалу. На другој обали возила се искрцавају у редоследу супротном од редоследа у којем су се укрцала. Када се сва возила искрцају, празан трајект се враћа на почетну обалу. Користећи регионе написати програм који решава овај проблем.

Решење

struct Trajekt {
    int cap = N;
    int curr = 0, next = 0, ticketIn = 0, ticketOut = 0;
    bool ukrcavanje = false, iskrcavanje = false
}

Trajekt t;

void vozilo(int space) {
    int myTicketIn, myTicketOut;
    region(t) {
        myTicketIn = t.ticketIn++;
        await (t.ukrcavanje && t.ticketIn == myTicketIn);
        if (t.cap - t.curr < space) {
            // ukoliko nema mesta za mene, posalji trajekt pa sacekaj da se vrati
            t.ukrcavanje = false;
            await (t.ukrcavanje);
        }
        t.curr += space;
        myTicketOut = ++t.ticketOut;
        t.next++;
        if (t.curr == t.cap)
            t.ukrcavanje = false;
    }
    // prevozimo se
    region(t) {
        await (t.iskrcavanje && myTicketOut == t.ticketOut);
        if (--t.ticketOut == 0)
            // ukoliko sam poslednji, posalji trajekt nazad
            t.iskrcavanje = false
    }     
}

void trajekt() {
    while (1) {
        region(t) {
            t.ukrcavanje = true
            await (!t.ukrcavanje);
        }
        preveziVozila();
        region(t) {
            t.iskrcavanje = true;
            await (!t.iskrcavanje);
        }
        vratiSeNazad();
    }
}

5. задатак

Поставка

Користећи синхрону размену порука написати дистрибуирано решење за проблем филозофа који ручавају (The Dining Philosophers Problem). Код дистрибуираног решења процеси филозофи комуницирају само са процесима виљушкама и процеси виљушке комуницирају само са процесима филозофима.

Решење

void philosopher(int ID, chan<string> release, chan<char> forkL, chan<char> forkR) {
    while (true) {
        // Филозофирамо
        if (ID % 2 == 0) {
            forkL.send('R');
            forkR.send('L');
        } else {
            forkR.send('L');
            forkL.send('R');
        }
        // Једемо
        release.receive();
        release.receive();
    }
}

void fork(chan<char> acquire, chan<string> philL, chan<string> philR) {
    while (true) {
        char dir = acquire.receive();
        if (dir == 'L') {
            philL.send("release");
        } else {
            philR.send("release");
        }
    }
}

6. задатак

Поставка

Постоји P произвођача и C потрошача који деле заједнички бафер капацитета B (Atomic broadcast problem). Произвођачи генеришу производ по производ на које чекају свих C потрошача. Сваки потрошач мора да прими производе у тачно оном редоследу у коме су произведени, мада различити потрошачи могу у исто време да узимају различите производе. Решити проблем користећи C-Linda, тако да се ни у ком тренутку у заједничком простору не нађе више од B производа.

Решење

Тагови коришћени у овој имплементацији су:

• buffer empty: постоји места да произвођач убацује у бафер
• buffer full: постоје производи у баферу које потрошачи могу да читају
• product: производ са одређеним индексом у низу
• size: величина бафера
• producer index: индекс у баферу до ког су произвођачи стигли са попуњавањем
• consumer count: број потрошача који је преостао да прочита производ на одређеном индексу

const int P = 100;
const int C = 100;
const int B = 100;

struct Product {};
Product produce();
void consume(Product p);

int producer() {
    while (true) {
        Product p = produce();
        in("buffer empty");
        int index;
        in("producer index", &index);
        out("product", index, p);
        out("consumer count", index, C);
        out("producer index", (index + 1) % B);
        int size;
        in("size", &size);
        if (size == 0) {
            out("buffer full");
        }
        out("size", ++size);
        if (size < B) {
            out("buffer empty");
        }
    }
}

void consumer() {
    int index = 0;
    while (true) {
        in("buffer full");
        Product p;
        int count;
        in("consumer count", index, &count);
        if (count == 1) {
            in("product", index, &p);
            int size;
            in("size", &size);
            if (size == B) {
                out("buffer empty");
            }
            out("size", --size);
            if (size > 0) {
                out("buffer full");
            }
        } else {
            rd("product", index, &p);
            out("consumer count", index, count-1);
            out("buffer full");
        }
        index = (index + 1) % B;
        consume(p);
    }
}

void initialize() {
    out("buffer empty");
    out("size", 0);
    out("producer index", 0);
}