КДП/К1 2020

Поставка овог рока може се наћи са странице предмета (зипована).

1. задатак

Поставка

Написати и објасните^[sic] CLH алгоритам за критичну секцију (coarse grain). Реализовати (fine grain) верзију алгоритма уколико би на датом процесору постојала операција SWAP која би недељиво обављала замену вредности два операнда (SWAP(var1, var2): < temp = var1; var1 = var2; var2 = temp; >). Објаснити зашто је то правична (fair) критична секција.

Решење

CLH алгоритам уланчава процесе који желе да уђу у критичну секцију у неку врсту уланчане листе, тако да сваки проверава да ли је онај пре њега и даље закључан и у тренутку када више не буде закључан улази у критичну секцију.

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;
        // Некритична секција
    }
}

Пошто је prev овде локална променљива и ту нема критичне референце, await се може заменити обичном петљом. Са друге стране, за атомску акцију prev = tail; tail = node; потребна нам је поменута SWAP инструкција:

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;
        // Некритична секција
    }
}

Ова критична секција је правична јер ће први процес који уради замену (изврши SWAP инструкцију) бити први који ће ући у критичну секцију.

2. задатак

Поставка

Посматра се један паркинг. Постоји само једна рампа која служи и за улаз на паркинг, и за излаз са паркинга, кроз коју може пролазити само један аутомобил у једном тренутку. На паркингу има N места за паркирање. Аутомобили који улазе, могу да уђу, један по један, уколико има слободних места. Уколико нема слободног места, проверава се да ли има аутомобила који хоће да изађу. Ако након изласка свих аутомобила који желе да изађу и уласка аутомобила који су дошли пре њега за аутомобил неће бити места, он одлази у потрагу за другим паркингом. Аутомобили при изласку плаћају услуге паркинга и излазе један по један. На почетку предност на рампи имају аутомобили који излазе са паркинга. Након што кроз рампу изађе K узастопних аутомобила, приоритет се мења (додељује се већи приоритет онима који улазе). Након проласка K узастопних аутомобила који улазе, приоритет се поново мења. Ако нема аутомобила из смера који има приоритет, аутомобили који немају приоритетни смер смеју да пролазе кроз рампу. Коришћењем једног низа од 2N + 1 семафора направити методе за тражење дозвола за улаз и излаз и обавештавање о уласку и изласку аутомобила са паркинга. Није дозвољено користити помоћне структуре података ни додатне елементе за синхронизацију процеса. Аутомобили не смеју да се претичу.

Решење

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

class Car {
    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];
public:
    bool requestEntrance() {
        mutex.wait();
        if (capacity - entering + exiting <= 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;
            exitHead = (exitHead + 1) % N;
        } else if (signalEnter) {
            semIndex = enterHead;
            exitHead = (enterHead + 1) % N;
        }
        if (semIndex >= 0) {
            if (priority != signalExit) {
                // Ако сада није изашао аутомобил из реда који је имао приоритет,
                // ресетује се бројач узастопних аутомобила
                passed = 0;
            } else {
                ++passed;
            }
            if (passed == K) {
                passed = 0;
                priority = !priority;
            }
            sems[semIndex].signal();
        }
    }
    void run() {
        while (true) {
            if (requestEntrance()) {
                entered();
                // ...
                requestExit();
                // pay();
                exited();
            }
        }
    }
};