KDP/Februar 2022

Izvor: SI Wiki
Pređi na navigaciju Pređi na pretragu

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.

Rešenje

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. 

#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. zadatak

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.

Rešenje

Značenje tagova korišćenih u rešenju:

  • people: Broj ljudi u berbernici
  • wakeup: Signal berberinu da se probudi od prve mušterije
  • current: Berberin javlja mušteriji da sedne na stolicu
  • sat: Mušterija javlja berberinu da je sela na stolicu
  • finished: Berberin javlja mušteriji da je završio
  • ticket: Redni broj mušterije
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. zadatak

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.

Rešenje

[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;
];
Preuzeto iz „https://siwiki.rs/w/index.php?title=КДП/Фебруар_2022&oldid=5592”