КДП/Фебруар 2020

Фебруарски испит 2020. године одржан је 8. фебруара. Поставка се може наћи са странице предмета (зипована).

1. задатак

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

Поставка

Користећи расподељене бинарне семафоре решити проблем произвођача и потрошача (Producer – Consumer Problem).

2. задатак

Поставка

Постоји група од N филозофа који проводи свој живот тако што наизменично филозофирају, чекају на пиће, и пију (The Drinking Philosophers Problem). Филозофи су тако распоређени да је по једна флаша са пићем постављенa између суседних филозофа. У неком тренутку филозоф може да постане жедан. Жедном филозофу је потребно неколико суседних флаша да би направио коктел и почео да га пије. Избор пића зависи од тренутног расположења и може се разликовати од прилике до прилике. Када прикупи сва потребна пића филозоф започиње са њиховим испијањем које траје извесно време. Када се напије, филозоф враћа флаше да и други уживају, а он прелази на филозофирање. Написати програм који симулира понашање филозофа користећи условне критичне регионе.

Решење

#include <queue>
#include <vector>

using namespace std;

const int N = 100;

struct Table {
    int drinks[N] = {-1};
    queue<int> drinkQueues[N];
};
Table table;

void philosophizing();
void drinking();
vector<int> getDrinkRound();

void philosopher(int id) {
    while (true) {
        vector<int> drinks = getDrinkRound();
        region (table) {
            for (int drink : drinks) {
                if (table.drinks[drink] == -1) {
                    table.drinks[drink] = id;
                } else {
                    table.drinkQueues[drink].push(id);
                    await (table.drinks[drink] == id);
                }
            }
        }
        drinking();
        region (table) {
            for (int drink : drinks) {
                if (table.drinkQueues[drink].empty()) {
                    table.drinks[drink] = -1;
                } else {
                    table.drinks[drink] = table.drinkQueues[drink].front();
                    table.drinkQueues[drink].pop();
                }
            }
        }
        philosophizing();
    }
}

3. задатак

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

Поставка

Филтерски процеси имају један улаз и један излаз. Процеси имају само три локације. Направите проточну обраду (pipeline) од n ових филтерских процеса који проналазе медијану: до n улазних позитивних вредности (непарно) које се убацују на почетак проточне обраде, а завршавају се са EOS. На излаз проточне обраде се шаље медијана па EOS.

4. задатак

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

Поставка

Посматра се берберница у којој за три различите столице раде три берберина (The Hilzer's Barbershop problem). Поред ове три столице у берберници се налази и чекаоница која прима 10 муштерија које могу да седе и 10 које могу да стоје, укупно 20. Када муштерија дође до бербернице уколико на шишање чека више од 20 муштерија онда одлази, а уколико берберница није пуна онда остаје. Уколико барем један берберин спава муштерија која дође на ред за шишање буди оног берберина који је најдуже спавао и седа у његову столицу. На место те муштерије која је устала седа муштерија која је најдуже стајала. Уколико су сви бербери заузети онда муштерија чека, и то ако има места за седење седа, а ако не онда стоји. Муштерије се опслужују у редоследу по коме су приспеле, и седају у истом том редоследу. Када берберин заврши са шишањем муштерија му плаћа и излази из бербернице. Берберин све време или спава или шиша или наплаћује. Користећи C-Linda написати процесе берберина и муштерија.