KDP/Jun 2021

Izvor: SI Wiki
Pređi na navigaciju Pređi na pretragu

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

1. zadatak

Postavka

Potrebno je da N procesa dele dva štampača. Pre upotrebe štampača, proces P[i] poziva monitorsku proceduru request(), a procedura vraća identifikator dodeljenog štampača - printer. Po završetku štampanja, proces P[i] oslobađa štampač sa release(printer). Definišite monitorsku invarijantu. Razviti monitor koji koristi Signal and Continue disciplinu. Nakon toga, pretpostaviti da kod procedure request postoji dodatni argument kojim proces dostavlja prioritet zahteva. Modifikovati monitor, tako da se štampači dobijaju u skladu sa prioritetom. Pri istom prioritetu treba da važi redosled pristizanja zahteva - FCFS.

Rešenje

Monitorska invarijanta, ukoliko je broj štampača, je . Krajnje modifikovani monitor izgleda: 

class PrintersMonitor {
    private class ProcessPriority implements Comparable<ProcessPriority> {
        public int priority;
        public int ticket;
        public int id;
        public int printer;
        public ProcessPriority(int priority, int ticket, int id) {
            this.priority = priority;
            this.ticket = ticket;
            this.id = id;
        }
        @Override
        public int compareTo(ProcessPriority p2) {
            if (priority == p2.priority) {
                // Ако је приоритет исти, уреди по времену стизања
                return ticket - p2.ticket;
            }
            // Прво се уређује по приоритету
            return priority - p2.priority;
        }
    }
    private static final int N = 100;
    private boolean[] busy = new boolean[2];
    private Condition[] free = new Condition[N];
    private PriorityQueue<ProcessPriority> pq = new PriorityQueue<>(N);
    private int ticket = 0;
    private int id = 0;
    public PrintersMonitor() {
        for (int i = 0; i < N; ++i) {
            free[i] = new Condition();
        }
    }
    public synchronized int request(int priority) {
        // Прво проверимо да ли има слободних штампача
        for (int i = 0; i < 2; ++i) {
            if (!busy[i]) {
                busy[i] = true;
                return i;
            }
        }
        // Ако нема, убацујемо се у ред за чекање
        int myTicket = ticket++;
        int myId = id;
        id = (id + 1) % N;
        ProcessPriority pp = new ProcessPriority(priority, myTicket, myId);
        pq.push(pp);
        free[myId].wait();
        // Одблокирао нас је неки процес који је раније држао неки штампач
        return pp.printer;
    }
    public synchronized void release(int printer) {
        if (pq.isEmpty()) {
            busy[printer] = false;
        } else {
            ProcessPriority pp = pq.pop();
            free[pp.id].signal();
            pp.printer = printer;
        }
    }
}

2. zadatak

Postavka

Posmatra se agencija za iznajmljivanje automobila. U voznom parku postoje 20 standardnih vozila i 10 luks vozila. Prilikom dolaska klijenta da iznajmi auto, on se izjašnjava da li želi da iznajmi standardno ili luks vozilo ili mu je sve jedno. Nakon toga on čeka u redu sve dok mu se vozilo ne dodeli na korišćenje. Po završetku korišćenja, korisnik dolazi još jednom u agenciju i vraća auto. U agenciji postoji jedan zaposleni koji vodi evidenciju o tome koji auto je trenutno na korišćenju kod kog korisnika. Klijentima nije dozvoljeno napuštanje agencije sve dok zaposleni ne obradi njihov zahtev za preuzimanje ili vraćanje vozila. Koristeći regione napisati metodu koje se poziva prilikom dolaska klijenta da iznajmi auto, metodu koje se poziva prilikom dolaska klijenta da vrati auto i metodu koja simulira rad zaposlenog, kao i kod za inicijalizaciju. Potrebno je obezbediti da vozila ne stoje na parkingu agencije, ukoliko postoji bilo koji klijent koji želi da iznajmi taj tip vozila.

Rešenje

#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. zadatak

Postavka

Posmatra se prsten u kome svaki čvor može da primi poruku samo od svog prethodnika i koji može da pošalje poruku smo[sic] svom sledbeniku. Svaki čvor sadrži celobrojnu vrednost. Potrebno je ostvariti interakcije između tih čvorova koristeći sinhronu komunikaciju da bi se saznalo koja je minimalna a koja je maksimalna vrednost. Svaki čvor treba da sazna koje su maksimalna i minimalna vrednost.

Rešenje

const int N = 100;
chan<pair<int, int>> values[N];

void process(int i, int v) {
    int min = v;
    int max = v;
    pair<int, int> newPair;
    if (i == 0) {
        // Први процес прво шаље, прима коначни резултат и прослеђује
        values[0].send({min, max});
        newPair = values[N-1].receive();
    } else {
        // Остали процеси прво примају, израчунавају, шаљу даље, примају коначни резултат и прослеђују
        newPair = values[i-1].receive();
        if (newPair.first < min) {
            min = newPair.first;
        }
        if (newPair.second > max) {
            max = newPair.second;
        }
        values[i].send({min, max});
        newPair = values[i-1].receive();
    }
    min = newPair.first;
    max = newPair.second;
    if (i != N-1) {
        // Ако смо последњи процес не треба да шаљемо првом опет, јер неће примити
        values[i].send({min, max});
    }
}

4. zadatak

Postavka

Posmatra se špil od 24 karte, podeljene u 4 boje, sa po 6 različitih brojeva. Igru igraju 4 igrača, koji sede za okruglim stolom i svaki od njih inicijalno drži po 4 karte. Između dva susedna igrača se nalazi gomila sa kartama, koja može u nekom trenutku biti prazna, a inicijalno sadrži 2 karte. Igra se završava kada neki igrač objavi da ima sve 4 karte istog broja, u različitim bojama, i tada svi igrači prekidaju igru. Svaki igrač, dok god nema 4 iste i niko nije objavio da je pobednik, izbacuje jednu kartu iz svoje ruke i stavlja je na gomilu sa svoje leve strane, potom uzima jednu kartu iz gomile sa svoje desne strane. Pretpostaviti da su igračima inicijalno podeljene karte na slučajan način. Koristeći C-Linda, napisati izgled procedure za jednog igrača. Pored igrača, ne postoji nijedan drugi proces.

Rešenje

Ključna funkcija je void player(int i), dok ostale daju kontekst rešenju. Korišćeni tagovi su:

  • player: inicijalna podela karata igračima
  • deck: sadržaj jednog špila na stolu
  • game over: da li je igra gotova
  • can set game over: da li igrač može da objavi da je pobedio (semafor oko game over)
typedef pair<int, int> Card;

template<typename T>
T randomChoice(vector<T>& vec) {
    int index = rand() * vec.size() / RAND_MAX;
    T ret = vec[index];
    vec.erase(vec.begin() + index);
    return ret;
}

bool hasWon(vector<Card>& cards) {
    bool colors[4] = {false};
    colors[cards[0].first] = true;
    int num = cards[0].second;
    for (int i = 1; i < 4; ++i) {
        if (cards[i].second != num || colors[cards[i].first]) {
            return false;
        }
        colors[cards[i].first] = true;
    }
    return true;
}

void player(int i) {
    vector<Card> cards;
    Card c;
    for (int i = 0; i < 4; ++i) {
        in("player", i, &c);
        cards.push_back(c);
    }
    while (true) {
        if (hasWon(cards)) {
            in("can set game over");
            if (!rdp("game over")) {
                out("game over");
            }
            out("can set game over");
            out("deck", (i + 1) % 4, Card(-1, -1));
            break;
        }
        c = randomChoice(cards);
        out("deck", (i + 1) % 4, c);
        in("deck", i, &c);
        if (rdp("game over")) {
            break;
        }
        cards.push_back(c);
    }
}

void initialize() {
    // Празнимо простор торки од претходне игре
    while (inp("deck") || inp("player") || inp("game over") || inp("can set game over"));
    // Вршимо насумичну расподелу шпила
    vector<Card> cards;
    for (int color = 0; color < 4; ++color) {
        for (int number = 0; number < 6; ++number) {
            cards.push_back({color, number});
        }
    }
    for (int d = 0; d < 4; ++d) {
        for (int c = 0; c < 2; ++c) {
            Card card = randomChoice(cards);
            out("deck", d, card);
        }
    }
    for (int p = 0; p < 4; ++p) {
        for (int c = 0; c < 4; ++c) {
            Card card = randomChoice(cards);
            out("player", p, card);
        }
        eval(player, p);
    }
    out("can set game over");
}
Preuzeto iz „https://siwiki.rs/w/index.php?title=КДП/Јун_2021&oldid=5579”