KDP/Januar 2020

Januarski ispit 2020. godine održan je 18. januara. Postavka ovog roka može se naći sa stranice predmeta (zipovana).

1. zadatak

Sličan zadatak došao je u avgustu 2021. godine sa Signal and Continue disciplinom.

Postavka

Potrebno je realizovati semafor koji pored standardnih atomskih operacija signal() i wait() ima i atomske operacije signal(n) i wait(n) koja internu semaforsku promenljivu atomski uvećava odnosno umanjuje za n ukoliko je to moguće, ukoliko nije čeka dok ne bude bili moguće. Potrebno je rešiti problem koristeći monitore koji imaju Signal and Wait 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 i nemaju prioritetnu metodu wait.

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();
            internalSignal();
        }
    }
    public synchronized void signal(int num) {
        value += num;
        internalSignal();
    }
    public synchronized void wait() {
        wait(1);
    }
    public synchronized void signal() {
        signal(1);
    }
    private void internalSignal() {
        if (requests.size() > 0 && value >= requests.top()) {
            value -= requests.pop();
            queue.signal();
        }
    }
}

2. zadatak

Postavka

Koristeći semafore 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. Lift redom obilazi spratove i staje samo na one gde ima putnika koji ulaze ili izlaze. Može se pretpostaviti da postoji N spratova.

Rešenje

struct Floor {
    list<sem*> peopleEntering;
    sem mutexEntering = 1;
    list<sem*> peopleExiting;
    sem mutexExiting = 1;
};

const int N = 10;
Floor floors[N];
sem liftSem = 0;

void person() {
    sem personSem = 0;
    int currentFloorIndex = rand() % N;
    while (true) {
        // Особа може да каже да хоће да изађе на истом спрату као тренутном
        // Претпоставка: особа није глупа
        int nextFloorIndex = rand() % N;
        Floor& currentFloor = floors[currentFloorIndex];
        Floor& nextFloor = floors[nextFloorIndex];
        currentFloor.mutexEntering.wait();
        currentFloor.peopleEntering.push_back(&personSem);
        currentFloor.mutexEntering.signal();
        // Чекамо да дође лифт
        personSem.wait();
        // Улазимо у лифт и бирамо на којем спрату стајемо
        nextFloor.mutexExiting.wait();
        nextFloor.peopleExiting.push_back(&personSem);
        nextFloor.mutexExiting.signal();
        liftSem.signal();
        // Чекамо да лифт стигне на наш спрат
        personSem.wait();
        // Излазимо из лифта
        liftSem.signal();
    }
}

void lift() {
    int currentFloorIndex = 0;
    bool goingUp = true;
    while (true) {
        // Одређивање следећег спрата
        // Претпоставка: лифт све време иде горе-доле, без обзира да ли га је неко звао
        if (goingUp) {
            if (++currentFloorIndex == N-1) {
                goingUp = false;
            }
        } else {
            if (--currentFloorIndex == 0) {
                goingUp = true;
            }
        }
        Floor& floor = floors[currentFloorIndex];
        // Не морамо да чекамо на mutexExiting, јер се он заузима само када путници улазе
        // што тренутно није случај
        int countPeopleExiting = floor.peopleExiting.size();
        // Задржавамо mutexEntering док не испразнимо листу, како нам не би ушао неочекивани путник
        floor.mutexEntering.wait();
        int countPeopleEntering = floor.peopleEntering.size();
        if (countPeopleExiting == 0 && countPeopleEntering == 0) {
            // Не стајемо на овом спрату
            floor.mutexEntering.signal();
            continue;
        }
        // Стајемо на овом спрату
        // Пуштамо људе да изађу
        for (int i = 0; i < countPeopleExiting; ++i) {
            sem* personSem = floor.peopleExiting.front();
            personSem->signal();
            floor.peopleExiting.pop_front();
        }
        for (int i = 0; i < countPeopleExiting; ++i) {
            liftSem.wait();
        }
        // Пуштамо људе да уђу
        for (int i = 0; i < countPeopleEntering; ++i) {
            sem* personSem = floor.peopleEntering.front();
            personSem->signal();
            floor.peopleEntering.pop_front();
        }
        for (int i = 0; i < countPeopleEntering; ++i) {
            liftSem.wait();
        }
        floor.mutexEntering.signal();
        // Настављамо на следећи спрат
    }
}

3. zadatak

Postavka

Koristeći tehniku aktivnih monitora potrebno je realizovati semafor koji pored standardnih atomskih operacija signal() i wait() ima i atomske operacije signal(n) i wait(n) koja internu semaforsku promenljivu atomski uvećava odnosno umanjuje za n ukoliko je to moguće, ukoliko nije čeka dok ne bude bili moguće. Proces koji je ranije uputio zahtev treba ranije da obavi svoju operaciju.

Rešenje

enum op_kind { WAIT, SIGNAL, WAITN, SIGNALN };
chan request(int, op_kind, int);
chan reply[n](bool);

class Semaphore {
public:
    void run() {
        int clientID;
        op_kind kind;
        int n;
        int tokens = 0;
        queue<pair<int,int>> pending;
        while (true) {
            receive request(clientID, kind, n);
            if (kind == WAIT) {
                if (tokens <= 0) {
                    pending.push(make_pair(clientID, 1));
                } else {
                    tokens--;
                    send reply[clientID](true);
                }
            } else if (kind == WAITN) {
                if (tokens <= n-1) {
                    pending.push(make_pair(clientID, n));
                } else {
                    tokens = tokens-n;
                    send reply[clientID](true);
                }
            } else if (kind == SIGNAL) {
                tokens++;
                if (!pending.empty() && pending.front().second == tokens) {
                    tokens = 0;
                    send reply[pending.front().first](true);
                    pending.pop();
                }
            } else if (kind == SIGNALN) {
                tokens += n;
                while (!pending.empty() && pending.front().second <= tokens) {
                    tokens -= pending.front().second;
                    send reply[pending.front().first](true);
                    pending.pop();
                }
            }
        }
    }
}

4. 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), po Njutnovom zakonu gravitacije. Svako telo interaguje sa svakim, pri čemu razmenjuju informacije o poziciji, brzini i vektoru sile. Koristeći CSP potrebno je rešiti ovaj problem koristeći torbu poslova za dohvatanje posla i sinhronizaciju na barijeri u svakoj iteraciji. Potrebno je realizovati sledeće procese: Worker (obavlja izračunavanje), Bag (obavlja podelu posla) i Collector (obavlja prikupljanje rezultata). Broj procesa Worker nije poznat, ali je poznato da ih ima manje od N. Postoji tačno jedan proces Bag i tačno jedan proces Collector.