КДП/Активни монитори

Активни монитори су концепт дистрибуираног програмирања из трећег блока наставе и долазе на дистрибуираном делу испита за СИ и РТИ.

Јануар 2020, 3. задатак

Debug: КДП/Јануар 2020 3. задатак

Поставка

Користећи технику активних монитора потребно је реализовати семафор који поред стандардних атомских операција signal() и wait() има и атомске операције signal(n) и wait(n) која интерну семафорску променљиву атомски увећава односно умањује за n уколико је то могуће, уколико није чека док не буде били могуће. Процес који је раније упутио захтев треба раније да обави своју операцију.

Решење

enum op_kind { WAIT, SIGNAL, WAITN, SIGNALN };
chan request(int, op_kind, int);
chan reply[n](bool);

class Semaphore {
public:
    void run() {
        int clientID;
        op_kind kind;
        int n;
        int tokens = 0;
        queue<pair<int,int>> pending;
        while (true) {
            receive request(clientID, kind, n);
            if (kind == WAIT) {
                if (tokens <= 0) {
                    pending.push(make_pair(clientID, 1));
                } else {
                    tokens--;
                    send reply[clientID](true);
                }
            } else if (kind == WAITN) {
                if (tokens <= n-1) {
                    pending.push(make_pair(clientID, n));
                } else {
                    tokens = tokens-n;
                    send reply[clientID](true);
                }
            } else if (kind == SIGNAL) {
                tokens++;
                if (!pending.empty() && pending.front().second == tokens) {
                    tokens = 0;
                    send reply[pending.front().first](true);
                    pending.pop();
                }
            } else if (kind == SIGNALN) {
                tokens += n;
                while (!pending.empty() && pending.front().second <= tokens) {
                    tokens -= pending.front().second;
                    send reply[pending.front().first](true);
                    pending.pop();
                }
            }
        }
    }
}

Јул 2020, 3. задатак

Debug: КДП/Јул 2020 3. задатак

Поставка

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

Решење

Напомена: Због захтева да филозоф који је пре затражио да једе пре и започне са јелом иде се по строго ФИФО редоследу, и филозофи који су се заблокирали на чекању виљушке неће је добити све док сви филозофи који су затражили виљушку пре њих не добију своју, и из тог разлога је потребна while петља код отпуштања виљушке.

const int N = ...;
enum op_kind{REQUEST,RELEASE};
// Poslednji parametar ukazuje na to da li filozof trazi levu ili desnu viljusku
chan request(int, op_kind kind, bool);
chan reply[N](bool);

class Coordinator {
public:
    void run() {
        int philosopher;
        op_kind kind;
        bool left;
        queue<pair<int,int>> waiting;
        int forks[N] = {};
        while (true) {
            receive request(philosopher, kind, left);
            int fork = left ? philosopher : (philosopher + 1) % N;
            if (kind == REQUEST) {
                if (forks[fork] == 0) {
                    forks[fork] = 1;
                    send reply[philosopher](true);
                } else {
                    waiting.push(make_pair(philosopher, fork));
                }
            } else if (kind == RELEASE) {
                forks[fork] = 0;
                while (!waiting.empty() && forks[waiting.front().second] == 0){
                    send reply[waiting.front().first](true);
                    waiting.pop();
                }
            }
        }
    }
}

void philosopher(int id) {
    bool status;
    while(true) {
        // Think
        send request(id, REQUEST, id != 0);
        receive reply[id](status);
        send request(id, REQUEST, id == 0);
        receive reply[id](status);
        // Eat
        send request(id, RELEASE, id != 0);
        send request(id, RELEASE, id == 0);
    }
}

Август 2021, 4. задатак

Debug: КДП/Август 2021 4. задатак

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

Поставка

Постоји један произвођач и N потрошача који деле заједнички бафер капацитета B (Atomic broadcast problem). Произвођач убацује производ у бафер и то само у слободне слотове на који чекају свих N потрошача. Сваки потрошач мора да прими производ у тачно оном редоследу у коме су произведени, мада различити потрошачи могу у исто време да узимају различите производе. Произвођачи и потрошачи могу да комуницирају искључиво са процесом координатором (централизовано решење) који има само један ток контроле и понаша се као активни монитор. Сваки процес има само једно сандуче из кога може да чита, и из сваког сандучета може да чита само један процес док већи број може да уписује. Написати код за произвођаче, потрошаче и за процес координатор.

Фебруар 2023, 3. задатак

Debug: КДП/Фебруар 2023 3. задатак

Поставка

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

Решење

Исти задатак дошао је у јулу 2020. године. Ипак, аутор је одлучио да постави своје решење које је добило максималан број бодова.

const int N = ...;
enum op_kind{REQUEST,RELEASE};
chan request(int, op_kind);
chan reply[N](bool);

class Coordinator {
public:
    void run() {
        int id;
        op_kind op;
        queue<int> waiting;
        int forks[N] = {true};
        while (true) {
            receive request(id, op);
            int left = id, right = (id + 1) % N;
            if (op == REQUEST) {
                if (forks[left] && forks[right]) {
                    forks[left] = forks[right] = false;
                    send reply[id](OK);
                } else {
                    waiting.push(id);
                }
            } else if (op == RELEASE) {
                forks[left] = forks[right] = true;
                send reply[id](OK);
                while (!waiting.empty()) {
                    id = waiting.top();
                    left = id, right = (id + 1) % N;
                    if (forks[left] && forks[right]) {
                        forks[left] = forks[right] = false;
                        waiting.pop();
                        send reply[id](OK);
                    } else break;
                }
            }
        }
    }
}

void philosopher(int id) {
    bool status;
    while (true) {
        // Think
        send request(id, REQUEST);
        receive reply[id](status);
        // Eat
        send request(id, RELEASE);
        receive reply[id](status)
    }
}

Фебруар 2024, 3. задатак

Debug: КДП/Фебруар 2024 3. задатак

Поставка

Решити проблем читалаца и писаца (Readers-Writers problem) користећи активне мониторе. Обезбедити да процес који је пре упутио захтев за приступ ресурсу пре треба да буде опслужен.

Решење

const int N = ...; //broj citalaca + broj pisaca
chan s(int, int); //id, op
chan r[N](int, int);

// 0 - start read
// 1 - end read
// 2 - start write
// 3 - end write

void reader(int id) {
    bool status;
    while(true) {
        send s(id, 0);
        receive r[id](status);
        //read
        send s(id, 1);
        receive r[id](status);
    }
}


void writer(int id) {
    bool status;
    while(true) {
        send s(id, 2);
        receive r[id](status);
        //write
        send s(id, 3);
        receive r[id](status);
    }
}


void monitor() {
    int id, op, numR = 0;
    queue buffer(int, int);

    while(true) {
        if(buffer.isNotEmpty()) id, op = buffer.get();
        else receive s(id, op);

        if(op == 0) {
            numR++;
            send r[id](true);
        } else if(op == 1) {
            numR--;
            send r[id](true);
        } else if(op == 2) {
            int id2, op2;
            while(numR > 0) {
                receive s(id2, op2);
                if(op2 == 0 || op2 == 2) buffer.put(id2, op2);
                else if(op2 == 1) {
                    numR--;
                    send r[id2](true);
                }
            }
            send r[id](true);
            while(true) {
                receive s(id2, op2);
                if(op2 == 0 || op2 == 2) buffer.put(id2, op2);
                else if(op2 == 3) {
                    send r[id2](true);
                    break;
                }
            }
        }
    }
}