KDP/Avgust 2021

Postavka ovog roka može se naći sa stranice predmeta.

1. zadatak

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

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

4. zadatak

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