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

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

1. задатак

Поставка

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

2. задатак

Поставка

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

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

4. задатак

Поставка

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