КДП/К1 2022

1. задатак

Поставка

Написати и објасните^[sic] Андерсенов алгоритам за критичну секцију (coarse grain). Реализовати (fine grain) верзију алгоритма уколико би на датом процесору умест FA постојала операција Compare-And-Swap која би недељиво обављала (CAS(a, b, c) : < if (a == c) { c = b; return true; } else { a = c; return false; } >).

Решење

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. задатак

Поставка

Посматра се забавни парк са N аутића који могу да приме по једну особу (Bumper Cars Problem). M особа се шета по парку и може да одлучи да се провоза. Особа која жели да се вози стаје у ред и чека слободни ауто. Када се ослободи ауто и претходни возач напусти ауто прва особа из реда добија прилику да вози ауто и да се судара са другим аутима. Након неког времена особа завршава вожњу, враћа ауто на одговарајуће место, напушта ауто и одлази да се шета по парку. Особа може више пута да дође да се вози. Уколико постоји више аута, особа бира онај који је најдуже чекао на вожњу. Уколико тренутно нема особа које желе да се возе ауто стаје у ред и чека да дође особа. Користећи семафоре написати програм који решава овај проблем.

Решење

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();
        // Настављамо шетњу
    }
}