КДП/Фебруар 2024

1. задатак

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

Поставка

Написати и објаснити Test and set решење за критичну секцију (coarse grain и fine grain). Дати решење за смањење инвалидације кеш меморија у том случају.

2. задатак

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

Поставка

Користећи условне критичне регионе написати програм који решава проблем путовања лифтом. Путник позива лифт са произвољног спрата. Када лифт стигне на неки спрат сви путници који су изразили жељу да сиђу на том спрату обавезно изађу. Након изласка путника сви путници који су чекали на улазак уђу у лифт и кажу на који спрат желе да пређу. Тек када се сви изјасне лифт прелази даље. Није потребно оптимизовати пут лифта и путника.

3. задатак

Поставка

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

Решење

const int N; // broj citalaca + broj pisaca
enum op_kind { START_READ, END_READ, START_WRITE, END_WRITE };
chan request(int id, op_kind op);
chan reply[N](bool);

void reader(int id) {
    bool status;
    while (true) {
        send request(id, START_READ);
        receive reply[id](status);
        // read
        send request(id, END_READ);
    }
}

void writer(int id) {
    bool status;
    while (true) {
        send request(id, START_WRITE);
        receive reply[id](status);
        // write
        send request(id, END_WRITE);
    }
}

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

    while (true) {
        int id, op;
        receive s(id, op);

        if (op == START_READ || op == START_WRITE) {
            buffer.push(id, op);
        }
        if (op == END_READ) numR--;
        if (op == END_WRITE) numW--;

        if (numW == 0 && numR == 0 && !buffer.empty()) {
            id, op = buffer.pop();
            if (op == START_READ) numR++;
            if (op == START_WRITE) numW++;
            send reply[id](true);
        }
        while (numW == 0 && !buffer.empty() && buffer.front().op == START_READ) {
            id, op = buffer.pop();
            numR++;
            send reply[id](true);
        }
    }
}

4. задатак

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

Поставка

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