КДП/Фебруар 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. задатак

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

Поставка

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

4. задатак

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

Поставка

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