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

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

1. задатак

Поставка

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

Решење

Решење са бафером за M произвођача и N потрошача

#include <semaphore>

class ProducerConsumer {

private:
	
	const int CAPACITY=...;
	int writeCursor=0;
	int readCursor = 0;
	
	int data[CAPACITY]; //Примера ради је узето да произвођач прави податке типа int
	
	std::binary_semaphore space_available(CAPACITY);
	std::binary_semaphore item_available(0);
	std::binary_semaphore mutexProducer(1);
	std::binary_semaphore mutexConsumer(1);

	
public:

	void producer() {
	
		spaceAvailable.acquire(); //у std::binary_semaphore ово је еквивалент операцији wait
		mutexProducer.acquire();
		
		data[writeCursor] = this.produce(); //Нека метода која би враћала неки број
		
		writeCursor = (writeCursor + 1) % CAPACITY;
		
		mutexProducer.release();
		item_available.release(); //у std::binary_semaphore ово је еквивалент операцији signal
		
		
	
	}


	int consumer() {
		item_available.acquire();
		mutexConsumer.acquire()
		
		int i = data[readCursor];
		
		readCursor = (readCursor + 1) % CAPACITY;
		
		item_available.release();
		mutexConsumer.release()
		
		return i;
		
	}


}

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

Поставка

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

Решење

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

void process() {

    chan<int> in;
    chan<int> out;
    int input;
    int mem[2];
    while ((input = in.receive()) != EOS) {       
        if (mem[0] <= input && input <= mem[1]) {
              out.send(input);
            } else if (input < mem[0]) {
                out.send(mem[0]);
                mem[0] = input;
            } else if (input > mem[1]) {
                out.send(mem[1]);
                mem[1] = input;
            }
    }
    out.send(EOS);
}

4. задатак

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

Поставка

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