KDP/Februar 2024

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

1. zadatak

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

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

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.