KDP/K1 2020

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

1. zadatak

Postavka

Napisati i objasnite^[sic] CLH algoritam za kritičnu sekciju (coarse grain). Realizovati (fine grain) verziju algoritma ukoliko bi na datom procesoru postojala operacija SWAP koja bi nedeljivo obavljala zamenu vrednosti dva operanda (SWAP(var1, var2): < temp = var1; var1 = var2; var2 = temp; >). Objasniti zašto je to pravična (fair) kritična sekcija.

Rešenje

CLH algoritam ulančava procese koji žele da uđu u kritičnu sekciju u neku vrstu ulančane liste, tako da svaki proverava da li je onaj pre njega i dalje zaključan i u trenutku kada više ne bude zaključan ulazi u kritičnu sekciju.

Node* tail = nullptr;

void worker() {
    while (true) {
        Node* node = new Node();
        node->locked = true;
        < prev = tail; tail = node; >
        < await (prev == nullptr || !prev->locked); >
        // Критична секција
        node->locked = false;
        // Некритична секција
    }
}

Pošto je prev ovde lokalna promenljiva i tu nema kritične reference, await se može zameniti običnom petljom. Sa druge strane, za atomsku akciju prev = tail; tail = node; potrebna nam je pomenuta SWAP instrukcija:

Node* tail = nullptr;

void worker() {
    while (true) {
        Node* node = new Node();
        node->locked = true;
        Node* prev = node;
        SWAP(prev, tail);
        while (prev != nullptr && prev->locked) skip();
        // Критична секција
        node->locked = false;
        // Некритична секција
    }
}

Ova kritična sekcija je pravična jer će prvi proces koji uradi zamenu (izvrši SWAP instrukciju) biti prvi koji će ući u kritičnu sekciju.

2. zadatak

Postavka

Posmatra se jedan parking. Postoji samo jedna rampa koja služi i za ulaz na parking, i za izlaz sa parkinga, kroz koju može prolaziti samo jedan automobil u jednom trenutku. Na parkingu ima N mesta za parkiranje. Automobili koji ulaze, mogu da uđu, jedan po jedan, ukoliko ima slobodnih mesta. Ukoliko nema slobodnog mesta, proverava se da li ima automobila koji hoće da izađu. Ako nakon izlaska svih automobila koji žele da izađu i ulaska automobila koji su došli pre njega za automobil neće biti mesta, on odlazi u potragu za drugim parkingom. Automobili pri izlasku plaćaju usluge parkinga i izlaze jedan po jedan. Na početku prednost na rampi imaju automobili koji izlaze sa parkinga. Nakon što kroz rampu izađe K uzastopnih automobila, prioritet se menja (dodeljuje se veći prioritet onima koji ulaze). Nakon prolaska K uzastopnih automobila koji ulaze, prioritet se ponovo menja. Ako nema automobila iz smera koji ima prioritet, automobili koji nemaju prioritetni smer smeju da prolaze kroz rampu. Korišćenjem jednog niza od 2N + 1 semafora napraviti metode za traženje dozvola za ulaz i izlaz i obaveštavanje o ulasku i izlasku automobila sa parkinga. Nije dozvoljeno koristiti pomoćne strukture podataka ni dodatne elemente za sinhronizaciju procesa. Automobili ne smeju da se pretiču.

Rešenje

const int N = 100;
const int K = 50;

sem sems[2 * N + 1];
// Број слободних места на паркингу (аутомобили који чекају излаз су ослободили своје место)
int capacity = N;
// Број аутомобила који чекају на улазу
int entering = 0;
// Број аутомобила који чекају на излазу
int exiting = 0;
int enterTail = 0;
int enterHead = 0;
int exitTail = 0;
int exitHead = 0;
// true - излаз, false - улаз
bool priority = true;
int passed = 0;
sem& mutex = sems[2 * N];
bool requestEntrance() {
    mutex.wait();
    if (capacity - entering <= 0) {
        mutex.signal();
        return false;
    }
    ++entering;
    if (entering == 1 && exiting == 0) {
        // Слободан пролаз
        mutex.signal();
        return true;
    }
    int semIndex = enterTail;
    enterTail = (enterTail + 1) % N;
    mutex.signal();
    sems[semIndex].wait();
    return true;
}
void requestExit() {
    mutex.wait();
    ++capacity;
    ++exiting;
    if (entering == 0 && exiting == 1) {
        // Слободан пролаз
        mutex.signal();
        return;
    }
    int semIndex = exitTail + N;
    exitTail = (exitTail + 1) % N;
    mutex.signal();
    sems[semIndex].wait();
}
void entered() {
    mutex.wait();
    --entering;
    --capacity;
    signal();
    mutex.signal();
}
void exited() {
    mutex.wait();
    --exiting;
    signal();
    mutex.signal();
}
void signal() {
    int semIndex = -1;
    bool hasCapacity = (capacity - exiting) < N;
    bool signalExit = (exiting > 0) && (priority || !hasCapacity || entering == 0);
    bool signalEnter = (entering > 0 && hasCapacity) && (!priority || exiting == 0);
    if (signalExit) {
        semIndex = exitHead + N;
        exitHead = (exitHead + 1) % N;
    } else if (signalEnter) {
        semIndex = enterHead;
        enterHead = (enterHead + 1) % N;
    }
    if (semIndex >= 0) {
        if (priority != signalExit) {
            // Ако сада није изашао аутомобил из реда који је имао приоритет,
            // ресетује се бројач узастопних аутомобила
            passed = 0;
        } else {
            ++passed;
        }
        if (passed == K) {
            passed = 0;
            priority = !priority;
        }
        sems[semIndex].signal();
    }
}
void car() {
    while (true) {
        if (requestEntrance()) {
            entered();
            // ...
            requestExit();
            // pay();
            exited();
        }
    }
}