КДП/Фебруар 2022 — разлика између измена

Извор: SI Wiki
Пређи на навигацију Пређи на претрагу
м (Objašnjenje tagova izbačeno van komentara)
м (feb2023, rešenje kačim kad dobijem rezultat)
Ред 1: Ред 1:
{{tocright}}
{{tocright}}
Поставка овог рока може се наћи са [https://rti.etf.bg.ac.rs/rti/ir3kdp/rokovi/2122/KDP_2022_feb.pdf странице предмета.]
Поставка овог рока може се наћи са [https://rti.etf.bg.ac.rs/rti/ir3kdp/rokovi/2223/KDP_2023_feb.pdf странице предмета.]


== 1. задатак ==
== 1. задатак ==
{{делимично решено}}
{{делимично_решено}}
=== Поставка ===
=== Поставка ===
Реализовати монитор са ''Signal and Continue'' дисциплином за приступ ресурсима. Процеси који позивају мониторске процедуре могу да резервишу до две инстанце ресурса. Укупно иницијално постоје три слободне инстанце ресурса. Процеси приликом позива мониторске процедуре за заузимање ресурса дефинишу приоритет захтева као висок или нормалан. Када неки процес ослобађа две инстанце ресурса, а постоје процеси који су на чекању и који траже две инстанце ресурса, ти процеси увек имају предност у односу на процесе који су на чекању и траже један ресурс. Спречити изгладњивање.
''Fine grain Ticket'' алгоритам реализован помоћу ''addAndGet'' операције. Уколико би ''addAndGet'' операција имала следећи ефекат: <code>addAndGet(var, incr) : < var = var + incr; return(var);</code>, да ли је могуће направити ''Fine grain'' решење, полазећи од ''Coarse grain'' решења, и ако је могуће - направите га. Написати и ''Coarse grain'' решење.  


=== Решење ===
=== Решење ===


== 2. задатак ==
== 2. задатак ==
{{делимично_решено}}
=== Поставка ===
=== Поставка ===
Рачун у банци може да дели више корисника (''The Savings Account Problem''). Сваки корисник може да уплаћује и подиже новац са рачуна под условом да салдо на том рачуну никада не буде негативан. Уколико на рачуну нема довољно новца, корисник треба да чека док неко други не уплати новац на тај рачун. Ниједан корисник не може бити исплаћен док год сви који су пре њега тражили исплату не добију свој новац. Решити проблем користећи семафоре (не треба проверавати да ли корисник сме да приступи неком рачуну; у банци може постојати више рачуна).
Племе људождера једе заједничку вечеру из казана који може да прими M порција куваних мисионара (''The Dining Savages Problem''). Када људождер пожели да руча онда се он сам послужи из заједничког казана, уколико казан није празан. Уколико је казан празан људождер буди кувара и сачека док кувар не напуни казан и онда узима своју порцију, а тек након тога преостали могу јести. Није дозвољено будити кувара уколико се налази бар мало хране у казану. Написати монитор са ''signal and continue'' дисциплином који решава дати проблем.


=== Решење ===
=== Решење ===
У решењу се сматра да сваки корисник ради у само једној нити, да свака нит има свој идентификатор, и да се тај идентификатор прослеђује функцијама за уплаћивање и подизање новца.
<syntaxhighlight lang="cpp">
#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();
}
</syntaxhighlight>


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


=== Решење ===
=== Решење ===
Значење тагова коришћених у решењу:
: ''Исти задатак дошао је у [[КДП/Јул 2020#3. задатак|јулу 2020. године]].
* <code>people</code>: Број људи у берберници
* <code>wakeup</code>: Сигнал берберину да се пробуди од прве муштерије
* <code>current</code>: Берберин јавља муштерији да седне на столицу
* <code>sat</code>: Муштерија јавља берберину да је села на столицу
* <code>finished</code>: Берберин јавља муштерији да је завршио
* <code>ticket</code>: Редни број муштерије
<syntaxhighlight lang="cpp">
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);
}
</syntaxhighlight>


== 4. задатак ==
== 4. задатак ==
{{делимично_решено}}
=== Поставка ===
=== Поставка ===
Аутомобили који долазе са севера и југа морају да пређу реку преко моста (''One lane bridge problem''). На мосту, на жалост, постоји само једна возна трака. Значи, у било ком тренутку мостом може да прође један или више аутомобила који долазе из истог смера (али не и из супротног смера). Користећи CSP написати програм који решава дати проблем. Спречити изгладњивање.
На једној обали реке се налази чамац који превози путнике са једне на другу обалу и који може да прими тачно десет путника. Чамац могу да користе мушкарци, жене и деца. Чамац може да исплови само ако се у њему налази тачно онолико путника колики му је капацитет, али само под условом да се у чамцу налазе бар два мушкарца. Деца не смеју ући у чамац уколико се у њему не налазе бар једна одрасла особа и по завршетку вожње у чамцу не смеју да остану само деца. Сматрати да ће се чамац након искрцавања свих путника одмах бити спреман да прими наредну групу путника. Користећи ''CSP'' написати програм који решава овај проблем.


=== Решење ===
=== Решење ===
<syntaxhighlight lang="pascal">
[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;
];
</syntaxhighlight>


[[Категорија:КДП]]
[[Категорија:КДП]]
[[Категорија:Рокови]]
[[Категорија:Рокови]]

Верзија на датум 11. фебруар 2023. у 01:23

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

1. задатак

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

Поставка

Fine grain Ticket алгоритам реализован помоћу addAndGet операције. Уколико би addAndGet операција имала следећи ефекат: addAndGet(var, incr) : < var = var + incr; return(var);, да ли је могуће направити Fine grain решење, полазећи од Coarse grain решења, и ако је могуће - направите га. Написати и Coarse grain решење.

Решење

2. задатак

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

Поставка

Племе људождера једе заједничку вечеру из казана који може да прими M порција куваних мисионара (The Dining Savages Problem). Када људождер пожели да руча онда се он сам послужи из заједничког казана, уколико казан није празан. Уколико је казан празан људождер буди кувара и сачека док кувар не напуни казан и онда узима своју порцију, а тек након тога преостали могу јести. Није дозвољено будити кувара уколико се налази бар мало хране у казану. Написати монитор са signal and continue дисциплином који решава дати проблем.

Решење

3. задатак

Поставка

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

Решење

Исти задатак дошао је у јулу 2020. године.

4. задатак

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

Поставка

На једној обали реке се налази чамац који превози путнике са једне на другу обалу и који може да прими тачно десет путника. Чамац могу да користе мушкарци, жене и деца. Чамац може да исплови само ако се у њему налази тачно онолико путника колики му је капацитет, али само под условом да се у чамцу налазе бар два мушкарца. Деца не смеју ући у чамац уколико се у њему не налазе бар једна одрасла особа и по завршетку вожње у чамцу не смеју да остану само деца. Сматрати да ће се чамац након искрцавања свих путника одмах бити спреман да прими наредну групу путника. Користећи CSP написати програм који решава овај проблем.

Решење

Преузето из „https://siwiki.rs/w/index.php?title=КДП/Фебруар_2022&oldid=5549”