KDP/Avgust 2021

Avgustovski ispit 2021. godine održan je 2. septembra. Postavka ovog roka može se naći sa stranice predmeta.

1. zadatak

Sličan zadatak došao je u januaru 2020. godine sa Signal and Wait disciplinom.

Postavka

Potrebno je realizovati semafor koji pored standardnih atomskih operacija signal() i wait() ima i atomske operacije signal(n) i wait(n) koje internu semaforsku promenljivu atomski uvećava odnosno umanjuje za n ukoliko je to moguće, ukoliko nije čeka dok ne bude bilo moguće. Potrebno je rešiti problem koristeći monitore koji imaju Signal and Continue disciplinu. Proces koji je ranije uputio zahtev treba ranije da obavi svoju operaciju. Broj procesa i maksimalna vrednost n nisu unapred poznati. Uslovne promenljive su FIFO prema trenutku dolaska, nemaju prioritetnu metodu wait i ima ih konačan broj.

Rešenje

class Semaphore {
    private int value;
    private Queue<Integer> requests = new Queue<>();
    private Condition queue = new Condition();
    public Semaphore(int value) {
        this.value = value;
    }
    public synchronized void wait(int num) {
        if (value >= num) {
            value -= num;
        } else {
            requests.insert(num);
            queue.wait();
        }
    }
    public synchronized void signal(int num) {
        value += num;
        while (requests.size() > 0 && value >= requests.top()) {
            value -= requests.pop();
            queue.signal();
        }
    }
    public synchronized void wait() {
        wait(1);
    }
    public synchronized void signal() {
        signal(1);
    }
}

2. zadatak

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

Postavka

U svemiru postoji N nebeskih tela koja međusobno interaguju (N Body Gravitational Problem). Koristeći semafore potrebno je rešiti ovaj problem koristeći torbu poslova za dohvatanje posla. Potrebno je realizovati sledeće: Worker (obavlja izračunavanje), Bag (obavlja podelu posla) i Collector (obavlja prikupljanje rezultata).

Rešenje

Dok ovaj zadatak nije rešen, od koristi može biti informacija šta se u zadatku otprilike očekivalo:

• Činjenica da se u zadatku radi o nebeskim telima je potpuno nebitna.
• Worker niti vrše neka izračunavanja nad nebeskim telima (može se modelovati nekom metodom npr. izracunaj()).
• Parametri ovih izračunavanja (šta se tačno računa) moraju biti preuzeti od Bag niti. Ovaj model poznat je kao bag of tasks i objašnjen je u knjizi Zaharija Radivojevića Konkurentno i distribuirano programiranje na strani 22.
• Na kraju svih izračunavanja Collector nit ih preuzima. Nakon što ta nit obradi preuzete rezultate, daje Bag niti dodatne parametre izračunavanja koja se opet prosleđuju Worker nitima.

Za sve nedoumice oko postavke ovog zadatka obratiti se Sanji Delčev.

3. zadatak

Postavka

Rešiti problem filozofa koji ručavaju (Dining Philosophers Problem) koristeći koncept randevua (Rendezvous).

Rešenje

Module Server
    op dohvatiViljuske(idF);
    op vratiViljuske(idF);
Body
Process Server{
    const int N = 5;
    boolean jedu[N] = {false};
    while(true){
        //pretpostavka da kompajler vraca negativne vrednosti za moduo
        in dohvatiViljusku(i) and !jedu[(i-1)%N<0 ? ((i-1)%N+N) : (i-1)%N] and !jedu[(i+1)%N] -> jedu[i] = true;
        [] vratiViljuske(i) -> jedu[i] = false;
        ni
    }
}
End Server;

procces Filozof[i=0..4]{
    while(true){
        misli;
        call Server.dohvatiViljuske(i);
        jedi;
        call Server.vratiViljuske(i);
    }
}

4. zadatak

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

Postavka

Postoji jedan proizvođač i N potrošača koji dele zajednički bafer kapaciteta B (Atomic broadcast problem). Proizvođač ubacuje proizvod u bafer i to samo u slobodne slotove na koji čekaju svih N potrošača. Svaki potrošač mora da primi proizvod u tačno onom redosledu u kome su proizvedeni, mada različiti potrošači mogu u isto vreme da uzimaju različite proizvode. Proizvođači i potrošači mogu da komuniciraju isključivo sa procesom koordinatorom (centralizovano rešenje) koji ima samo jedan tok kontrole i ponaša se kao aktivni monitor. Svaki proces ima samo jedno sanduče iz koga može da čita, i iz svakog sandučeta može da čita samo jedan proces dok veći broj može da upisuje. Napisati kod za proizvođače, potrošače i za proces koordinator.