КДП/Прстен

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

Јун 2020, 5. задатак

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

Поставка

Реализовати прстен од n процеса, који комуницирају асинхроним прослеђивањем порука коришћењем комуникационих канала и send и receive исказа, а код кога процес 0 генерише случајан низ од m природних бројева у интервалу од 1 до 20.000 завршен са sentinel вредношћу EONAT (нпр 20.001). Преосталих n-1 процеса одстрањују из низа све појаве првих n-1 простих бројева. Сваки процес има по један различит прост број за који је задужен. Након одстрањивања простих бројева, модификован низ се дистрибуира свим процесима. Обезбедити максималну конкурентност.

Решење

const int N = ...;
const int m = ...;
const int EONAT = 20001;
chan values[N](int);

void process0(){
    int array[m];
    for (int i = 0; i < m; i++) array[i] = rand(1, 20000);
    for (int i = 0; i < m; i++) send values[1](array[i]);
    send values[1](EONAT);
    bool end = false;
    int temp, index = 0;
    while (!end) {
        receive values[0](temp);
        if (temp == EONAT) end = true;
        else array[index++] = temp;
    }
    for (int i = 0; i < index; i++) send values[1](array[i]);
    send values[1](EONAT);
}

void process(int id, int myNumber) {
    int array[m];
    bool end = false;
    int temp;
    while (!end) {
        receive values[id](temp);
        if (temp == EONAT) end = true;
        else if (temp != myNumber) send values[(id + 1) % N](temp);
    }
    end = false;
    int index = 0;
    while (!end) {
        receive values[id](temp);
        if (temp == EONAT) end = true;
        else {
            array[index++] = temp;
            if (id != N-1) send values[(id + 1) % N](temp);
        }
    }
}

Јун 2021, 3. задатак

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

Поставка

Посматра се прстен у коме сваки чвор може да прими поруку само од свог претходника и који може да пошаље поруку смо^[sic] свом следбенику. Сваки чвор садржи целобројну вредност. Потребно је остварити интеракције између тих чворова користећи синхрону комуникацију да би се сазнало која је минимална а која је максимална вредност. Сваки чвор треба да сазна које су максимална и минимална вредност.

Решење

const int N = 100;
chan<pair<int, int>> values[N];

void process(int i, int v) {
    int min = v;
    int max = v;
    pair<int, int> newPair;
    if (i == 0) {
        // Први процес прво шаље, прима коначни резултат и прослеђује
        values[0].send({min, max});
        newPair = values[N-1].receive();
    } else {
        // Остали процеси прво примају, израчунавају, шаљу даље, примају коначни резултат и прослеђују
        newPair = values[i-1].receive();
        if (newPair.first < min) {
            min = newPair.first;
        }
        if (newPair.second > max) {
            max = newPair.second;
        }
        values[i].send({min, max});
        newPair = values[i-1].receive();
    }
    min = newPair.first;
    max = newPair.second;
    if (i != N-1) {
        // Ако смо последњи процес не треба да шаљемо првом опет, јер неће примити
        values[i].send({min, max});
    }
}