KDP/Februar 2024

1. zadatak

Ovaj zadatak nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.

Postavka

Napisati i objasniti Test and set rešenje za kritičnu sekciju (coarse grain i fine grain). Dati rešenje za smanjenje invalidacije keš memorija u tom slučaju.

2. zadatak

Ovaj zadatak nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.

Postavka

Koristeći uslovne kritične regione napisati program koji rešava problem putovanja liftom. Putnik poziva lift sa proizvoljnog sprata. Kada lift stigne na neki sprat svi putnici koji su izrazili želju da siđu na tom spratu obavezno izađu. Nakon izlaska putnika svi putnici koji su čekali na ulazak uđu u lift i kažu na koji sprat žele da pređu. Tek kada se svi izjasne lift prelazi dalje. Nije potrebno optimizovati put lifta i putnika.

3. zadatak

Postavka

Rešiti problem čitalaca i pisaca (Readers-Writers problem) koristeći aktivne monitore. Obezbediti da proces koji je pre uputio zahtev za pristup resursu pre treba da bude opslužen.

Rešenje

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. zadatak

Ovaj zadatak nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.

Postavka

Posmatra se špil od 24 karte, podeljene u 4 boje, sa po 6 različitih brojeva. Igru igraju 4 igrača, koja sede za okruglim stolom i svaki od njih inicijalno drži po 4 karte. Između sva susedna igrača se nalazi gomila sa kartama, koja može u nekom trenutku biti prazna, a inicijalno sadrži 2 karte. Igra se završava kada bar jedan igrač objavi da ima sve 4 karte istog broja, u različitim bojama, o tada svi igrači prekidaju igru. Svaki igrač, dok god nema 4 karte iste i niko nije objavio da je pobednik, izbacuje jednu kartu iz svoje ruke i stavlja je na gomilu sa svoje leve strane, potom uzima jednu kartu sa vrha iz gomile sa svoje desne strane. Pretpostaviti da su igračima inicijalno podeljene karte na slučajan način. Koristeći CSP napisati programe za igrače i gomile sa kartama.