КДП/К2 2019

Други колоквијум 2019. године одржан је 23. априла. Поставка се може наћи са странице предмета (зипована).

1. задатак

Поставка

Проблем филозофа који ручавају (Dining Philosophers Problem). Решити проблем филозофа који ручавају користећи мониторе са signal and wait дисциплином. Филозофи који су раније изразили жељу за храном треба раније да буду опслужени.

Решење

class DiningPhilosophers {
    public static final int N = 10;
    boolean forks[] = new boolean[N];
    Condition queue = new Condition();
    int ticket = 1;
    private int left(int id) {
        return id;
    }
    private int right(int id) {
        return id + 1;
    }
    public synchronized void acquireForks(int id) {
        if (queue.queue() || forks[left(id)] || forks[right(id)]) {
            queue.wait((ticket++) * N + id);
        }
        forks[left(id)] = true;
        forks[right(id)] = true;
        signal();
    }
    public synchronized void releaseForks(int id) {
        forks[left(id)] = false;
        forks[right(id)] = false;
        signal();
    }
    private void signal() {
        if (queue.empty()) {
            return;
        }
        int id = queue.minrank() % N;
        if (!forks[left(id)] && !forks[right(id)]) {
            queue.signal();
        }
    }
}

2. задатак

Поставка

У берберници раде два берберина, Аца и Браца, постоји 10 столица за чекање и још петоро муштерија може да стоји и чека. Муштерије које долазе се изјашњавају да ли чекају код Аце или Браце или им је свеједно ко ће да их услужи. Ако муштерија види да нема места у берберници и не може бити услужена, одлази. Када је берберин слободан, муштерија која је најдуже чекала ће прва бити услужена (осим ако чека на другог берберина и тада тражимо следећу муштерију у низу). Када се ослободи столица за чекање, муштерија која је најдуже стајала треба да седне. Уколико је неки од берберина беспослен, он спава, и прва муштерија која код њега дође на ред треба да га пробуди и буде услужена. Користећи условне критичне регионе решити овај проблем.

Решење

#include "common.h"
#include <map>
#include <queue>

using namespace std;

struct BarberShop {
    // Додељивање идентификатора муштеријама по реду доласка
    int ticket = 1;
    // Идентификатор особе која седи у седишту, или 0 уколико нико не седи
    int seat[2] = {0};
    // Да ли је берберин завршио са шишањем и чека особу да плати
    bool finished[2] = {false};
    // std::map је подразумевано сортиран
    map<int, int> waitingQueue;
    // Редови чекања за муштерије код Аце, Браце и оне којима је свеједно
    queue<int> barberQueue[3];
};
BarberShop shop;

const int ACA_ID = 0;
const int BRACA_ID = 1;
const int ANY_ID = 2;

void barber(int id) {
    while (true) {
        region (shop) {
            // Спавамо док чекамо да прва особа која дође седне на столицу
            await (shop.seat[id] != 0);
        }
        // Шишање
        region (shop) {
            // Завршено шишање, чекамо на плаћање
            shop.finished[id] = true;
            await (!shop.finished[id]);
            // Узимамо следећу муштерију
            if (!shop.barberQueue[id].empty()) {
                shop.seat[id] = shop.barberQueue[id].front();
                shop.barberQueue[id].pop();
            } else if (!shop.barberQueue[ANY_ID].empty()) {
                shop.seat[id] = shop.barberQueue[ANY_ID].front();
                shop.barberQueue[ANY_ID].pop();
            } else {
                shop.seat[id] = 0;
            }
        }
    }
}

// Да ли је седиште за шишање код одређеног берберина тренутно резервисано за неку особу
int barberEquals(int barberId, int value) {
    if (barberId == ACA_ID && shop.seat[ACA_ID] == value) {
        return ACA_ID;
    }
    if (barberId == BRACA_ID && shop.seat[BRACA_ID] == value) {
        return BRACA_ID;
    }
    if (barberId == ANY_ID) {
        if (shop.seat[ACA_ID] == value) {
            return ACA_ID;
        }
        if (shop.seat[BRACA_ID] == value) {
            return BRACA_ID;
        }
    }
    return -1;
}

int barberFree(int barberId) {
    return barberEquals(barberId, 0);
}

void client(int barberId) {
    region (shop) {
        if (shop.waitingQueue.size() == 15 && barberFree(barberId) == -1) {
            // Особа не може бити услужена
            return;
        }
        int myTicket = shop.ticket++;
        if (barberFree(barberId) != 1) {
            // Без чекања седамо на столицу за шишање
            shop.seat[barberFree(barberId)] = myTicket;
        } else {
            shop.barberQueue[barberId].push(myTicket);
            // Овиме повећавамо shop.waitingQueue.size()
            shop.waitingQueue[myTicket] = shop.waitingQueue.size();
            // Чекамо на столицу за чекање или шишање
            await (shop.waitingQueue[myTicket] < 10 || barberEquals(barberId, myTicket) != -1);
            if (barberEquals(barberId, myTicket) == -1) {
                // Седамо на столицу за чекање
                await (barberEquals(barberId, myTicket) != -1);
            }
            // Устали смо са столице и смањујемо shop.waitingQueue.size
            shop.waitingQueue.erase(myTicket);
            int i = 0;
            for (auto& it : shop.waitingQueue) {
                shop.waitingQueue[it.first] = i++;
            }
        }
        int barber = barberEquals(barberId, myTicket);
        // Чекање током шишања
        await (shop.finished[barber]);
        // Плаћање
        shop.finished[barber] = false;
    }
}