KDP/Februar 2020

Februarski ispit 2020. godine održan je 8. februara. Postavka se može naći sa stranice predmeta (zipovana).

1. zadatak

Postavka

Koristeći raspodeljene binarne semafore rešiti problem proizvođača i potrošača (Producer – Consumer Problem).

Rešenje

Rešenje sa baferom za M proizvođača i N potrošača

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

Postavka

Postoji grupa od N filozofa koji provodi svoj život tako što naizmenično filozofiraju, čekaju na piće, i piju (The Drinking Philosophers Problem). Filozofi su tako raspoređeni da je po jedna flaša sa pićem postavljena između susednih filozofa. U nekom trenutku filozof može da postane žedan. Žednom filozofu je potrebno nekoliko susednih flaša da bi napravio koktel i počeo da ga pije. Izbor pića zavisi od trenutnog raspoloženja i može se razlikovati od prilike do prilike. Kada prikupi sva potrebna pića filozof započinje sa njihovim ispijanjem koje traje izvesno vreme. Kada se napije, filozof vraća flaše da i drugi uživaju, a on prelazi na filozofiranje. Napisati program koji simulira ponašanje filozofa koristeći uslovne kritične regione.

Rešenje

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

Postavka

Filterski procesi imaju jedan ulaz i jedan izlaz. Procesi imaju samo tri lokacije. Napravite protočnu obradu (pipeline) od n ovih filterskih procesa koji pronalaze medijanu: do n ulaznih pozitivnih vrednosti (neparno) koje se ubacuju na početak protočne obrade, a završavaju se sa EOS. Na izlaz protočne obrade se šalje medijana pa EOS.

Rešenje

Pošto je u zadatku rečeno da je dozvoljeno koristiti samo tri lokacije u procesu, jedna će biti odvojena za broj koji pristiže a druge dve za lokalne minimume i maksimume. Pamtiće se minimumi i maksimumi jer je medijana neparnog broja elemenata upravo ona vrednost koja je tačno na sredini liste u sortiranom poretku. Za razliku od drugih rešenja ovakvog tipa zadatka na vikiju, ništa se ne šalje na izlaz osim EOS kad se isti primi jer je sva obrada za medijanu već razrešena unutar petlje.

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

Ovaj zadatak nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.

Postavka

Posmatra se berbernica u kojoj za tri različite stolice rade tri berberina (The Hilzer's Barbershop problem). Pored ove tri stolice u berbernici se nalazi i čekaonica koja prima 10 mušterija koje mogu da sede i 10 koje mogu da stoje, ukupno 20. Kada mušterija dođe do berbernice ukoliko na šišanje čeka više od 20 mušterija onda odlazi, a ukoliko berbernica nije puna onda ostaje. Ukoliko barem jedan berberin spava mušterija koja dođe na red za šišanje budi onog berberina koji je najduže spavao i seda u njegovu stolicu. Na mesto te mušterije koja je ustala seda mušterija koja je najduže stajala. Ukoliko su svi berberi zauzeti onda mušterija čeka, i to ako ima mesta za sedenje seda, a ako ne onda stoji. Mušterije se opslužuju u redosledu po kome su prispele, i sedaju u istom tom redosledu. Kada berberin završi sa šišanjem mušterija mu plaća i izlazi iz berbernice. Berberin sve vreme ili spava ili šiša ili naplaćuje. Koristeći C-Linda napisati procese berberina i mušterija.