KDP/K1 2022

1. zadatak

Postavka

Napisati i objasnite^[sic] Andersenov algoritam za kritičnu sekciju (coarse grain). Realizovati (fine grain) verziju algoritma ukoliko bi na datom procesoru umest FA postojala operacija Compare-And-Swap koja bi nedeljivo obavljala (CAS(a, b, c) : < if (a == c) { c = b; return true; } else { a = c; return false; } >).

Rešenje

Coarse-grain:

const int N = 100;
int slot = 0;
bool slots[N];

void worker(int id) {
    while (true) {
        < int myslot = slot; slot = slot % N + 1; >
        < await (slots[myslot]); >
        // Критична секција
        < slots[myslot] = false;
        slots[myslot % N + 1] = true; >
        // Некритична секција
    }
}

Fine-grain:

const int N = 100;
int slot = 0;
bool slots[N];

void worker(int id) {
    while (true) {
        int myslot = slot;
        while (!CAS(myslot, myslot % N + 1, slot)) skip();
        while (!slots[myslot]) skip();
        // Критична секција
        slots[myslot] = false;
        slots[myslot % N + 1] = true;
        // Некритична секција
    }
}

2. zadatak

Postavka

Posmatra se zabavni park sa N autića koji mogu da prime po jednu osobu (Bumper Cars Problem). M osoba se šeta po parku i može da odluči da se provoza. Osoba koja želi da se vozi staje u red i čeka slobodni auto. Kada se oslobodi auto i prethodni vozač napusti auto prva osoba iz reda dobija priliku da vozi auto i da se sudara sa drugim autima. Nakon nekog vremena osoba završava vožnju, vraća auto na odgovarajuće mesto, napušta auto i odlazi da se šeta po parku. Osoba može više puta da dođe da se vozi. Ukoliko postoji više auta, osoba bira onaj koji je najduže čekao na vožnju. Ukoliko trenutno nema osoba koje žele da se voze auto staje u red i čeka da dođe osoba. Koristeći semafore napisati program koji rešava ovaj problem.

Rešenje

const int N = 100;
const int M = 100;

// Комуникација између аутомобила и особа
sem carSems[N];
sem peopleSems[M];
// Међусобно искључивање при приступу глобалном стању
sem mutex = 1;
// Подаци заштићени mutex-ом:
list<int> freeCars;
list<int> freePeople;
int mutexId;

void car(int carId) {
    int personId;
    while (true) {
        mutex.wait();
        if (freePeople.size() > 0) {
            personId = freePeople.front();
            freePeople.pop_front();
            mutexId = carId;
            peopleSems[personId].signal();
            // Нема ослобађања mutex, чекамо да особа прочита mutexId
            carSems[carId].wait();
        } else {
            freeCars.push_back(carId);
            mutex.signal();
            carSems[carId].wait();
            personId = mutexId;
            // Ослобађамо mutex који је особа закључала
            mutex.signal();
            // Обавештавамо особу да смо прочитали mutexId
            peopleSems[personId].signal();
        }
        // Особа контролише ауто, чекамо да нас особа обавести кад заврши
        carSems[carId].wait();
        // Враћени смо назад
    }
}

void person(int personId) {
    int carId;
    while (true) {
        // Шетамо
        mutex.wait();
        if (freeCars.size() > 0) {
            carId = freeCars.front();
            freeCars.pop_front();
            mutexId = personId;
            carSems[carId].signal();
            // Нема ослобађања mutex, чекамо да аутомобил прочита mutexId
            peopleSems[personId].wait();
        } else {
            freePeople.push_back(personId);
            mutex.signal();
            peopleSems[personId].wait();
            carId = mutexId;
            // Ослобађамо mutex који је аутомобил закључао
            mutex.signal();
            // Обавештавамо аутомобил да смо прочитали mutexId
            carSems[carId].signal();
        }
        // Возимо и на крају обавестимо аутомобил да смо завршили
        carSems[carId].signal();
        // Настављамо шетњу
    }
}