КДП/Фебруар 2022

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

1. задатак

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

Поставка

Реализовати монитор са Signal and Continue дисциплином за приступ ресурсима. Процеси који позивају мониторске процедуре могу да резервишу до две инстанце ресурса. Укупно иницијално постоје три слободне инстанце ресурса. Процеси приликом позива мониторске процедуре за заузимање ресурса дефинишу приоритет захтева као висок или нормалан. Када неки процес ослобађа две инстанце ресурса, а постоје процеси који су на чекању и који траже две инстанце ресурса, ти процеси увек имају предност у односу на процесе који су на чекању и траже један ресурс. Спречити изгладњивање.

2. задатак

Поставка

Рачун у банци може да дели више корисника (The Savings Account Problem). Сваки корисник може да уплаћује и подиже новац са рачуна под условом да салдо на том рачуну никада не буде негативан. Уколико на рачуну нема довољно новца, корисник треба да чека док неко други не уплати новац на тај рачун. Ниједан корисник не може бити исплаћен док год сви који су пре њега тражили исплату не добију свој новац. Решити проблем користећи семафоре (не треба проверавати да ли корисник сме да приступи неком рачуну; у банци може постојати више рачуна).

Решење

У решењу се сматра да сваки корисник ради у само једној нити, да свака нит има свој идентификатор, и да се тај идентификатор прослеђује функцијама за уплаћивање и подизање новца.

#include "common.h"

const int NumOfAccounts = 100;
const int NumOfUsers = 100;

struct Account {
    int balance;
    int maxTicket = 0;
    int waitUntilAbove = 0;
    sem mutex = 1;
    sem balanceSem = 0;
    sem users[NumOfUsers] = {1, 0, 0, ...};
};

Account accounts[NumOfAccounts];

void deposit(int amount, int accountId) {
    Account& account = accounts[accountId];
    account.mutex.wait();
    // Уплаћујемо паре на рачун.
    account.balance += amount;
    // Уколико је неки други корисник захтевао исплату, проверавамо да ли може бити задовољена.
    if (account.waitUntilAbove != 0 && account.balance >= account.waitUntilAbove) {
        // Уколико јесте, на нама је да ажурирамо стање.
        account.balance -= account.waitUntilAbove;
        account.waitUntilAbove = 0;
        account.balanceSem.signal();
    }
    account.mutex.signal();
}

void withdraw(int amount, int accountId) {
    Account& account = accounts[accountId];
    // Дохватамо наше место у реду чекања за исплату.
    account.mutex.wait();
    // Рачуна се на то да неће један корисник истовремено радити две исплате са истог налога.
    int ticket = (account.maxTicket++) % NumOfUsers;
    account.mutex.signal();

    // Чекамо да нас претходни корисник у реду чекања прозове.
    account.users[ticket].wait();

    // Чекамо да се ослободи довољно средстава пре исплате.
    account.mutex.wait();
    if (account.balance >= amount) {
        // Уколико већ има довољно средстава, ажурирамо стање.
        account.balance -= amount;
        account.mutex.signal();
    } else {
        // Уколико нема, остављамо следећем кориснику који уплаћује да ажурира стање и обавести нас.
        account.waitUntilAbove = amount;
        account.mutex.signal();
        account.balanceSem.wait();
    }

    // Јави следећем кориснику да може да изврши исплату.
    account.users[(ticket + 1) % NumOfUsers].signal();
}

3. задатак

Поставка

Користећи C-Linda библииотеку решити проблем берберина који спава (The Sleeping Barber Problem). Берберница се састоји од чекаонице са n=5 столица и берберске столице на којој се људи брију. Уколико нема муштерија, брица спава. Уколико муштерија уђе у берберницу и све столице су заузете, муштерија не чека, већ одмах излази. Уколико је берберин зaузет, а има слободних столица, муштерија седа и чека да дође на ред. Уколико берберин спава, муштерија га буди.

Решење

Значење тагова коришћених у решењу:

• people: Број људи у берберници
• wakeup: Сигнал берберину да се пробуди од прве муштерије
• current: Берберин јавља муштерији да седне на столицу
• sat: Муштерија јавља берберину да је села на столицу
• finished: Берберин јавља муштерији да је завршио
• ticket: Редни број муштерије

const int N = 5;

void barber() {
    int current = 0;
    int currPeople;
    in("people", &currPeople);
    out("people", currPeople);
    while (true) {
        if (currPeople == 0) {
            in("wakeup");
        }
        out("current", current++);
        in("sat");
        // Берберин шиша муштерију
        in("people", &currPeople);
        --currPeople;
        out("people", currPeople);
        out("finished");
    }
}

bool customer() {
    int currPeople;
    in("people", &currPeople);
    if (currPeople == 0) {
        // Муштерија буди берберина
        out("wakeup");
    } else if (currPeople == N + 1) {
        // Муштерија одлази
        out("people", currPeople);
        return false;
    }
    int myTicket;
    in("ticket", &myTicket);
    out("ticket", myTicket + 1);
    out("people", currPeople + 1);
    // Муштерија чека на свој ред
    in("current", myTicket);
    out("sat");
    in("finished");
    return true;
}

void initialize() {
    out("ticket", 0);
    out("people", 0);
}

4. задатак

Поставка

Аутомобили који долазе са севера и југа морају да пређу реку преко моста (One lane bridge problem). На мосту, на жалост, постоји само једна возна трака. Значи, у било ком тренутку мостом може да прође један или више аутомобила који долазе из истог смера (али не и из супротног смера). Користећи CSP написати програм који решава дати проблем. Спречити изгладњивање.

Решење

[Bridge::BRIDGE, Car(0..N)::CAR]

BRIDGE::[
    waiting: (0..2) (0..N) integer;
    waitingNum: (0..2) integer := 0;
    // 0 - нико, 1 - лево, 2 - десно
    priority: integer := 0;
    // 1 - лева страна, 2 - десна страна
    currentCrossing := 0;
    current: integer := 0;
    *[
        ; (i: 0..N) Car(i)?request(side) -> [
            currentCrossing = side and priority = side; -> [
                // Тренутно пролази наша страна и нико није дошао са друге
                current := current + 1;
                Car(i)!pass;
            ];
            □
            currentCrossing = side and priority <> side; -> [
                // Тренутно пролази наша страна али је неко дошао са друге
                waiting(side-1, waitingNum(side-1)) := i;
                waitingNum(side-1) := waitingNum(side-1) + 1;
            ];
            □
            currentCrossing <> side; -> [
                // Тренутно не пролази наша страна, зауставити их како би се спречило изгладњивање
                priority := side;
                waiting(side-1, waitingNum(side-1)) := i;
                waitingNum(side-1) := waitingNum(side-1) + 1;
            ];
        ];
        □
        ; (i: 0..N) Car(i)?passed -> [
            current := current - 1;
            [
                current = 0 and priority <> currentCrossing; -> [
                    // Нема више аутомобила који пролазе мостом али има оних који следећи имају приоритет
                    [
                        waitingNum(currentCrossing-1) == 0; -> [
                            // Уколико има аутомобила са стране која је досад пролазила, промени приоритет
                            // тако да они са друге стране који дођу после овога не могу да прођу
                            priority = (3 - priority);
                        ];
                    ];
                    // Промени страну која пролази и притом пусти све са друге стране
                    currentCrossing := (3 - currentCrossing);
                    (j: 0..waitingNum) Car(waiting(j, currentCrossing-1))!pass;
                    waitingNum := 0;
                ];
            ];
        ];
    ];
];

CAR::[
    Bridge!request(side);
    Bridge?pass;
    // Пролазимо
    Bridge!passed;
];