КДП/Јун 2021

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

1. задатак

Поставка

Потребно је да N процеса деле два штампача. Пре употребе штампача, процес P[i] позива мониторску процедуру request(), а процедура враћа идентификатор додељеног штампача - printer. По завршетку штампања, процес P[i] ослобађа штампач са release(printer). Дефинишите мониторску инваријанту. Развити монитор који користи Signal and Continue дисциплину. Након тога, претпоставити да код процедуре request постоји додатни аргумент којим процес доставља приоритет захтева. Модификовати монитор, тако да се штампачи добијају у складу са приоритетом. При истом приоритету треба да важи редослед пристизања захтева - FCFS.

Решење

Мониторска инваријанта, уколико je $N$ број штампача, je $0 \leq N \leq 2$. Крајње модификовани монитор изгледа:

class PrintersMonitor {
    private boolean[] busy = new boolean[2];
    private Condition free = new Condition();
    public synchronized int request(int priority) {
        while (true) {
            for (int i = 0; i < 2; ++i) {
                if (!busy[i]) {
                    return i;
                }
            }
            free.wait(priority);
        }
    }
    public synchronized void release(int printer) {
        busy[printer] = false;
        free.signal();
    }
}

2. задатак

Поставка

Посматра се агенција за изнајмљивање аутомобила. У возном парку постоје 20 стандардних возила и 10 лукс возила. Приликом доласка клијента да изнајми ауто, он се изјашњава да ли жели да изнајми стандардно или лукс возило или му је све једно. Након тога он чека у реду све док му се возило не додели на коришћење. По завршетку коришћења, корисник долази још једном у агенцију и враћа ауто. У агенцији постоји један запослени који води евиденцију о томе који ауто је тренутно на коришћењу код ког корисника. Клијентима није дозвољено напуштање агенције све док запослени не обради њихов захтев за преузимање или враћање возила. Користећи регионе написати методу које се позива приликом доласка клијента да изнајми ауто, методу које се позива приликом доласка клијента да врати ауто и методу која симулира рад запосленог, као и код за иницијализацију. Потребно је обезбедити да возила не стоје на паркингу агенције, уколико постоји било који клијент који жели да изнајми тај тип возила.

Решење

#include <map>
#include <queue>

using namespace std;

// Структуре за упућивање захтева запосленом
struct Request {
    int customerId;
    unsigned place;
};
enum RequestType {
    STANDARD_VEHICLE,
    LUXURY_VEHICLE,
    ANY_VEHICLE,
    RETURN_VEHICLE
};

// Монитор
struct CarDealership {
    queue<Request> standardRequests;
    queue<Request> luxuryRequests;
    queue<Request> anyRequests;
    queue<Request> returnRequests;
    map<int, int> rentedCars;
    int place = 1;
};
CarDealership dealership;

// Ова два реда се мењају само из запосленог, тако да не морају да буду у региону.
queue<int> standardCars;
queue<int> luxuryCars;

int rentCar(int customerId, int which) {
    region (dealership) {
        unsigned myPlace = dealership.place++;
        switch (which) {
            case STANDARD_VEHICLE:
                dealership.standardRequests.push({customerId, myPlace});
                break;
            case LUXURY_VEHICLE:
                dealership.luxuryRequests.push({customerId, myPlace});
                break;
            case ANY_VEHICLE:
                dealership.anyRequests.push({customerId, myPlace});
                break;
        }
        await (dealership.rentedCars[customerId]);
    }
}

void returnCar(int customerId) {
    region (dealership) {
        unsigned myPlace = dealership.place++;
        dealership.returnRequests.push({customerId, myPlace});
        await (!dealership.rentedCars[customerId]);
    }
}

void employee() {
    while (true) {
        Request req;
        int request = 0;
        region (dealership) {
            await (
                dealership.standardRequests.size() +
                dealership.luxuryRequests.size() +
                dealership.anyRequests.size() +
                dealership.returnRequests.size() > 0
            );
            unsigned minPlace = -1;
            if (
                !dealership.standardRequests.empty() &&
                !standardCars.empty() &&
                dealership.standardRequests.front().place < minPlace
            ) {
                minPlace = dealership.standardRequests.front().place;
                request = STANDARD_VEHICLE;
            }
            if (
                !dealership.luxuryRequests.empty() &&
                !luxuryCars.empty() &&
                dealership.luxuryRequests.front().place < minPlace
            ) {
                minPlace = dealership.luxuryRequests.front().place;
                request = LUXURY_VEHICLE;
            }
            if (
                !dealership.anyRequests.empty() &&
                (!standardCars.empty() || !luxuryCars.empty()) &&
                dealership.anyRequests.front().place < minPlace
            ) {
                minPlace = dealership.anyRequests.front().place;
                request = ANY_VEHICLE;
            }
            if (!dealership.returnRequests.empty() && dealership.returnRequests.front().place < minPlace) {
                minPlace = dealership.returnRequests.front().place;
                request = RETURN_VEHICLE;
            }
            switch (request) {
                case STANDARD_VEHICLE:
                    req = dealership.standardRequests.front();
                    dealership.standardRequests.pop();
                    break;
                case LUXURY_VEHICLE:
                    req = dealership.luxuryRequests.front();
                    dealership.luxuryRequests.pop();
                    break;
                case ANY_VEHICLE:
                    req = dealership.anyRequests.front();
                    dealership.anyRequests.pop();
                    break;
                case RETURN_VEHICLE:
                    req = dealership.returnRequests.front();
                    dealership.returnRequests.pop();
                    break;
            }
        }
        // Овде запослени ради неки свој посао бележења
        region (dealership) {
            switch (request) {
                case STANDARD_VEHICLE:
                    dealership.rentedCars[req.customerId] = standardCars.front();
                    standardCars.pop();
                    break;
                case LUXURY_VEHICLE:
                    dealership.rentedCars[req.customerId] = luxuryCars.front();
                    luxuryCars.pop();
                    break;
                case ANY_VEHICLE:
                    if (standardCars.empty()) {
                        dealership.rentedCars[req.customerId] = luxuryCars.front();
                        luxuryCars.pop();
                    } else {
                        dealership.rentedCars[req.customerId] = standardCars.front();
                        standardCars.pop();
                    }
                    break;
                case RETURN_VEHICLE:
                    int carId = dealership.rentedCars[req.customerId];
                    dealership.rentedCars[req.customerId] = 0;
                    if (carId > 20) {
                        luxuryCars.push(carId);
                    } else {
                        standardCars.push(carId);
                    }
                    break;
            }
        }
    }
}

int main() {
    for (int i = 0; i < 20; ++i) {
        standardCars.push(i + 1);
    }
    for (int i = 0; i < 10; ++i) {
        luxuryCars.push(i + 21);
    }
    return 0;
}

3. задатак

Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.

Поставка

Посматра се прстен у коме сваки чвор може да прими поруку само од свог претходника и који може да пошаље поруку смо свом следбенику. Сваки чвор садржи целобројну вредност. Потребно је остварити интеракције између тих чворова користећи синхрону комуникацију да би се сазнало која је минимална а која је максимална вредност. Сваки чвор треба да сазна које су максимална и минимална вредност.

4. задатак

Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.

Поставка

Посматра се шпил од 24 карте, подељене у 4 боје, са по 6 различитих бројева. Игру играју 4 играча, који седе за округлим столом и сваки од њих иницијално држи по 4 карте. Између два суседна играча се налази гомила са картама, која може у неком тренутку бити празна, а иницијално садржи 2 карте. Игра се завршава када неки играч објави да има све 4 карте истог броја, у различитим бојама, и тада сви играчи прекидају игру. Сваки играч, док год нема 4 исте и нико није објавио да је победник, избацује једну карту из своје руке и ставља је на гомилу са своје леве стране, потом узима једну карту из гомиле са своје десне стране. Претпоставити да су играчима иницијално подељене карте на случајан начин. Користећи C-Linda, написати изглед процедуре за једног играча. Поред играча, не постоји ниједан други процес.