КДП/C-Linda

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

Јануар 2021, 4. задатак

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

Поставка

На уласку у једну железничку станицу са једном улазном пругом и једним слепим колосеком десио се квар, па се на улазу направила колона међународних и домаћих возова. Квар је отклоњен и треба пуштати возове. Да би међународни возови мање каснили, они се пуштају први, по редоследу доласка. Пошто постоји само једна пруга и возови се не могу „претицати”, сви домаћи возови који су били испред међународних у колони се пребацују на слепи колосек који је довољно велики да сви возови могу да стану. Када сви међународни возови оду, пуштају се прво возови са слепог колосека, па онда преостали домаћи возови из колоне. Сама станица има N перона, тј. N возова истовремено могу да укрцавају и искрцавају путнике. Возови који у међувремену пристижу треба да буду опслужени, али новопристигли међународни немају приоритет у односу на возове који су испред њих у колони. Решити проблем користећи C-Linda. Написати потребну иницијализацију која осликава стање након отклањања квара. Водити рачуна о томе да су композиције возова тешке и да је потребно време да се воз помери са једног места на друго.

Решење

Следећи тагови су коришћени током реализације:

• ticket: редослед воза по пристизању
• current: воз који тренутно окупира улаз (било да излази из улаза и иде у слепи колосек, излази из улаза и иде на станицу или излази из слепог колосека и иде на станицу)
• sidetrack: возови који се налазе у слепом колосеку, прва вредност је редослед у слепом колосеку а друга редослед пристизања воза
• sidetrackHead: први воз који следећи треба да изађе из слепог колосека, по редоследу у слепом колосеку
• sidetrackTail: број возова у слепом колосеку
• station: возови који су тренутно на једном од регуларних N колосека

Начин на који је у овом решењу било одређено да ли је воз пристигао током квара или после је провера да ли је његов редослед пристизања већи или једнак константи M, што је број возова који су пристигли током квара. Након почетне иницијализације стања након поправљања квара очекује се да новопристигли возови сами направе train процес.

const int N = 10;
const int M = 100;

void setCurrentFromSidetrack() {
    int sidetrackTicket;
    int sidetrackHead;
    in("sidetrackHead", &sidetrackHead);
    in("sidetrack", sidetrackHead, &sidetrackTicket);
    out("sidetrackHead", sidetrackHead + 1);
    out("current", sidetrackTicket);
}

void train(bool isInternational) {
    int ticket;
    in("ticket", &ticket);
    out("ticket", ticket + 1);
    in("current", ticket);
    bool arrivedLater = ticket >= M;
    bool isSidetrack = !isInternational && !arrivedLater;
    if (isSidetrack) {
        // Прво идемо у слепи колосек
        int sidetrackTail;
        in("sidetrackTail", &sidetrackTail);
        out("sidetrack", sidetrackTail, ticket);
        out("sidetrackTail", sidetrackTail + 1);
        if (ticket == M - 1) {
            // Ми смо последњи воз који је стигао током квара,
            // треба да предамо првом из слепог колосека
            setCurrentFromSidetrack();
            in("current", ticket);
        } else {
            // Предајемо следећем возу који је стигао током квара
            out("current", ticket + 1);
            in("current", ticket);
        }
    }
    int station;
    in("station", &station);
    // Идемо на станицу, па чим ослободимо улаз пуштамо следећег
    if (isSidetrack) {
        if (rdp("sidetrack")) {
            // Пуштамо следећег из слепог колосека
            setCurrentFromSidetrack();
        } else {
            // Нема више никог из слепог колосека, пуштамо обичну колону
            out("current", M);
        }
    } else {
        if (ticket == M - 1) {
            // Ми смо последњи воз који је стигао током квара,
            // треба да предамо возовима из слепог колосека, уколико постоје
            if (rdp("sidetrack")) {
                setCurrentFromSidetrack();
            } else {
                // Нико није ушао у слепи колосек
                out("current", ticket + 1);
            }
        } else {
            // Пуштамо следећи воз, пошто још увек колона која је стигла
            // током квара није изашла из улаза
            out("current", ticket + 1);
        }
    }
    // Одлазимо са станице
    out("station", station);
}

void initialize() {
    out("ticket", 0);
    for (int i = 0; i < M; ++i) {
        eval(train, rand() % 2 == 1);
        // Чекамо да воз покупи свој ticket
        rd("ticket", i + 1);
    }
    for (int i = 0; i < N; ++i) {
        out("station", i);
    }
    out("current", 0);
    out("sidetrackHead", 0);
    out("sidetrackTail", 0);
}

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

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

Поставка

Решити проблем филозофа који ручавају користећи C-Lindu. Филозоф који је раније изразио жељу за храном треба раније да буду^[sic] опслужен.

Решење

const int N = 5;

void philosopher(int i) {
    int left = i;
    int right = (i + 1) % N;
    int ticket;
    while (true) {
        // Мислимо
        in("ticket", &ticket);
        out("ticket", ticket + 1);
        in("current", ticket);
        in("fork", left);
        in("fork", right);
        out("current", ticket + 1);
        // Једемо
        out("fork", right);
        out("fork", left);
    }
}

void init() {
    for (int i = 0; i < N; ++i) {
        out("fork", i);
        eval(philosopher, i);
    }
    out("ticket", 0);
    out("current", 0);
}

Јануар 2023, 4. задатак

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

Поставка

Трајект за превоз возила превози возила са обале на обалу. Трајект поседује M трака од којих свака има N позиција које су линеарно постављене једна иза друге. Возило заузима једну позицију. Возило приликом доласка стаје у ред за случајно изабрану траку и чека на укрцавање. Нема могућности за престројавањем. Возила улазе у своју траку једно по једно по редоследу у којем чекају у траци, док на трајекту има места. Када је пун, трајект започиње превоз возила на другу обалу. На другој обали возила се искрцавају из своје траке у редоследу супротном од редоследа у којем су се укрцала у своју траку. Када се сва возила искрцају, празан трајект се враћа на почетну обалу. Користећи C-Linda написати програм који решава овај проблем.

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

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

Поставка

У Линди реализовати лицитацију у којој постоји један процес vođa_licitacije и n процеса učesnika_u_licitaciji и један процес tick који само ажурира време. Вођа лицитације треба да иницијализује торку са почетном вредношћу и да после датог временског интервала заврши лицитацију, успешно ако је излицитирана вредност већа од резервисане вредности, неуспешно иначе. Процеси учесници у лицитацији треба да се реализују тако да се не блокирају када се заврши дата лицитација, треба да знају која је излицитирана вредност и да ли су је они поставили.

Решење

Тагови у овом решењу означавају:

• value: Тренутна вредност лицитације
• time out: Поставља се кад истекне време
• ended: Поставља се кад вођа лицитације објави крај лицитације

const int FINAL_TIME = 100;
const int INITIAL_VALUE = 50;
const int RESERVE_VALUE = 100;

int getBid();
void sleep(unsigned int seconds);

void vodjaLicitacije() {
    out("value", INITIAL_VALUE, -1);
    in("time out");
    int value;
    int user;
    in("value", &value, &user);
    out("ended", value > RESERVE_VALUE);
    out("value", value, user);
}

void ucesnikULicitaciji(int i) {
    int value;
    int user;
    int bid = getBid();
    bool success;
    in("value", &value, &user);
    if (rdp("ended") || value > bid) {
        out("value", value, user);
    } else {
        out("value", bid, i);
    }
    rd("ended", &success);
    rd("value", &value, &user);
    if (success && user == i) {
        // Ми добијамо лицитацију
    }
}

void tick() {
    int time = 0;
    while (true) {
        sleep(1);
        if (++time == FINAL_TIME) {
            out("time out");
        }
    }
}

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

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

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

Поставка

Посматра се скуп чворова у графу који могу да комуницирају само са својим суседима (Distributed Pairing Problem). Сваки чвор треба да нађе чвор са којим ће се упарити. На крају поступка упаривања сваки чвор ће или имати свог пара, или остати неупарен, али тако да ни једна два суседна чвора не остану неупарена. Написати програм за чвор користећи библиотеку C-Linda.

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

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

Поставка

Посматра се шпил од 24 карте, подељене у 4 боје, са по 6 различитих бројева. Игру играју 4 играча, који седе за округлим столом и сваки од њих иницијално држи по 4 карте. Између два суседна играча се налази гомила са картама, која може у неком тренутку бити празна, а иницијално садржи 2 карте. Игра се завршава када неки играч објави да има све 4 карте истог броја, у различитим бојама, и тада сви играчи прекидају игру. Сваки играч, док год нема 4 исте и нико није објавио да је победник, избацује једну карту из своје руке и ставља је на гомилу са своје леве стране, потом узима једну карту из гомиле са своје десне стране. Претпоставити да су играчима иницијално подељене карте на случајан начин. Користећи C-Linda, написати изглед процедуре за једног играча. Поред играча, не постоји ниједан други процес.

Решење

Кључна функција је void player(int i), док остале дају контекст решењу. Коришћени тагови су:

• player: иницијална подела карата играчима
• deck: садржај једног шпила на столу
• game over: да ли је игра готова
• can set game over: да ли играч може да објави да је победио (семафор око game over)

typedef pair<int, int> Card;

template<typename T>
T randomChoice(vector<T>& vec) {
    int index = rand() * vec.size() / RAND_MAX;
    T ret = vec[index];
    vec.erase(vec.begin() + index);
    return ret;
}

bool hasWon(vector<Card>& cards) {
    bool colors[4] = {false};
    colors[cards[0].first] = true;
    int num = cards[0].second;
    for (int i = 1; i < 4; ++i) {
        if (cards[i].second != num || colors[cards[i].first]) {
            return false;
        }
        colors[cards[i].first] = true;
    }
    return true;
}

void player(int i) {
    vector<Card> cards;
    Card c;
    for (int i = 0; i < 4; ++i) {
        in("player", i, &c);
        cards.push_back(c);
    }
    while (true) {
        if (hasWon(cards)) {
            in("can set game over");
            if (!rdp("game over")) {
                out("game over");
            }
            out("can set game over");
            out("deck", (i + 1) % 4, Card(-1, -1));
            break;
        }
        c = randomChoice(cards);
        out("deck", (i + 1) % 4, c);
        in("deck", i, &c);
        if (rdp("game over")) {
            break;
        }
        cards.push_back(c);
    }
}

void initialize() {
    // Празнимо простор торки од претходне игре
    while (inp("deck") || inp("player") || inp("game over") || inp("can set game over"));
    // Вршимо насумичну расподелу шпила
    vector<Card> cards;
    for (int color = 0; color < 4; ++color) {
        for (int number = 0; number < 6; ++number) {
            cards.push_back({color, number});
        }
    }
    for (int d = 0; d < 4; ++d) {
        for (int c = 0; c < 2; ++c) {
            Card card = randomChoice(cards);
            out("deck", d, card);
        }
    }
    for (int p = 0; p < 4; ++p) {
        for (int c = 0; c < 4; ++c) {
            Card card = randomChoice(cards);
            out("player", p, card);
        }
        eval(player, p);
    }
    out("can set game over");
}

Јун 2022, 6. задатак

Debug: КДП/Јун 2022 6. задатак

Поставка

Постоји P произвођача и C потрошача који деле заједнички бафер капацитета B (Atomic broadcast problem). Произвођачи генеришу производ по производ на које чекају свих C потрошача. Сваки потрошач мора да прими производе у тачно оном редоследу у коме су произведени, мада различити потрошачи могу у исто време да узимају различите производе. Решити проблем користећи C-Linda, тако да се ни у ком тренутку у заједничком простору не нађе више од B производа.

Решење

Тагови коришћени у овој имплементацији су:

• buffer empty: постоји места да произвођач убацује у бафер
• buffer full: постоје производи у баферу које потрошачи могу да читају
• product: производ са одређеним индексом у низу
• size: величина бафера
• producer index: индекс у баферу до ког су произвођачи стигли са попуњавањем
• consumer count: број потрошача који је преостао да прочита производ на одређеном индексу

const int P = 100;
const int C = 100;
const int B = 100;

struct Product {};
Product produce();
void consume(Product p);

int producer() {
    while (true) {
        Product p = produce();
        in("buffer empty");
        int index;
        in("producer index", &index);
        out("product", index, p);
        out("consumer count", index, C);
        out("producer index", (index + 1) % B);
        int size;
        in("size", &size);
        if (size == 0) {
            out("buffer full");
        }
        out("size", ++size);
        if (size < B) {
            out("buffer empty");
        }
    }
}

void consumer() {
    int index = 0;
    while (true) {
        in("buffer full");
        Product p;
        int count;
        in("consumer count", index, &count);
        if (count == 1) {
            in("product", index, &p);
            int size;
            in("size", &size);
            if (size == B) {
                out("buffer empty");
            }
            out("size", --size);
            if (size > 0) {
                out("buffer full");
            }
        } else {
            rd("product", index, &p);
            out("consumer count", index, count-1);
            out("buffer full");
        }
        index = (index + 1) % B;
        consume(p);
    }
}

void initialize() {
    out("buffer empty");
    out("size", 0);
    out("producer index", 0);
}

Фебруар 2020, 4. задатак

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

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

Поставка

Посматра се берберница у којој за три различите столице раде три берберина (The Hilzer's Barbershop problem). Поред ове три столице у берберници се налази и чекаоница која прима 10 муштерија које могу да седе и 10 које могу да стоје, укупно 20. Када муштерија дође до бербернице уколико на шишање чека више од 20 муштерија онда одлази, а уколико берберница није пуна онда остаје. Уколико барем један берберин спава муштерија која дође на ред за шишање буди оног берберина који је најдуже спавао и седа у његову столицу. На место те муштерије која је устала седа муштерија која је најдуже стајала. Уколико су сви бербери заузети онда муштерија чека, и то ако има места за седење седа, а ако не онда стоји. Муштерије се опслужују у редоследу по коме су приспеле, и седају у истом том редоследу. Када берберин заврши са шишањем муштерија му плаћа и излази из бербернице. Берберин све време или спава или шиша или наплаћује. Користећи C-Linda написати процесе берберина и муштерија.

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

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

Поставка

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

Решење

Значење тагова коришћених у решењу:

• people: Број људи у берберници
• wakeup: Сигнал берберину да се пробуди од прве муштерије
• current: Берберин јавља муштерији да седне на столицу
• sat: Муштерија јавља берберину да је села на столицу
• finished: Берберин јавља муштерији да је завршио
• ticket: Редни број муштерије

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);
}