KDP/Februar 2022

Postavka ovog roka može se naći sa stranice predmeta.

1. zadatak

Ovaj zadatak nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.

Postavka

Realizovati monitor sa Signal and Continue disciplinom za pristup resursima. Procesi koji pozivaju monitorske procedure mogu da rezervišu do dve instance resursa. Ukupno inicijalno postoje tri slobodne instance resursa. Procesi prilikom poziva monitorske procedure za zauzimanje resursa definišu prioritet zahteva kao visok ili normalan. Kada neki proces oslobađa dve instance resursa, a postoje procesi koji su na čekanju i koji traže dve instance resursa, ti procesi uvek imaju prednost u odnosu na procese koji su na čekanju i traže jedan resurs. Sprečiti izgladnjivanje.

2. zadatak

Postavka

Račun u banci može da deli više korisnika (The Savings Account Problem). Svaki korisnik može da uplaćuje i podiže novac sa računa pod uslovom da saldo na tom računu nikada ne bude negativan. Ukoliko na računu nema dovoljno novca, korisnik treba da čeka dok neko drugi ne uplati novac na taj račun. Nijedan korisnik ne može biti isplaćen dok god svi koji su pre njega tražili isplatu ne dobiju svoj novac. Rešiti problem koristeći semafore (ne treba proveravati da li korisnik sme da pristupi nekom računu; u banci može postojati više računa).

Rešenje

U rešenju se smatra da svaki korisnik radi u samo jednoj niti, da svaka nit ima svoj identifikator, i da se taj identifikator prosleđuje funkcijama za uplaćivanje i podizanje novca.

struct Account {
    int balance;
    int maxTicket = 0;
    int waitUntilAbove = 0;
    sem mutex = 1;
    sem balanceSem = 0;
};

const int NumOfAccounts = 100;
const int NumOfUsers = 100;
Account accounts[NumOfAccounts];
sem users[NumOfUsers] = {1, 0, 0, ...};

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

    // Чекамо да нас претходни корисник у реду чекања прозове.
    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();
    }

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

3. zadatak

Ovaj zadatak nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.

Postavka

Koristeći C-Linda bibliioteku rešiti problem berberina koji spava (The Sleeping Barber Problem). Berbernica se sastoji od čekaonice sa n=5 stolica i berberske stolice na kojoj se ljudi briju. Ukoliko nema mušterija, brica spava. Ukoliko mušterija uđe u berbernicu i sve stolice su zauzete, mušterija ne čeka, već odmah izlazi. Ukoliko je berberin zauzet, a ima slobodnih stolica, mušterija seda i čeka da dođe na red. Ukoliko berberin spava, mušterija ga budi.

4. zadatak

Ovaj zadatak nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.

Postavka

Automobili koji dolaze sa severa i juga moraju da pređu reku preko mosta (One lane bridge problem). Na mostu, na žalost, postoji samo jedna vozna traka. Znači, u bilo kom trenutku mostom može da prođe jedan ili više automobila koji dolaze iz istog smera (ali ne i iz suprotnog smera). Koristeći CSP napisati program koji rešava dati problem. Sprečiti izgladnjivanje.