КДП/Јун 2021
Поставка овог рока може се наћи са странице предмета.
1. задатак
Поставка
Потребно је да N процеса деле два штампача. Пре употребе штампача, процес P[i] позива мониторску процедуру request(), а процедура враћа идентификатор додељеног штампача - printer. По завршетку штампања, процес P[i] ослобађа штампач са release(printer). Дефинишите мониторску инваријанту. Развити монитор који користи Signal and Continue дисциплину. Након тога, претпоставити да код процедуре request постоји додатни аргумент којим процес доставља приоритет захтева. Модификовати монитор, тако да се штампачи добијају у складу са приоритетом. При истом приоритету треба да важи редослед пристизања захтева - FCFS.
Решење
Мониторска инваријанта, уколико je број штампача, je . Крајње модификовани монитор изгледа:
class PrintersMonitor {
private class ProcessPriority implements Comparable<ProcessPriority> {
public int priority;
public int ticket;
public int id;
public int printer;
public ProcessPriority(int priority, int ticket, int id) {
this.priority = priority;
this.ticket = ticket;
this.id = id;
}
@Override
public int compareTo(ProcessPriority p2) {
if (priority == p2.priority) {
// Ако је приоритет исти, уреди по времену стизања
return ticket - p2.ticket;
}
// Прво се уређује по приоритету
return priority - p2.priority;
}
}
private static final int N = 100;
private boolean[] busy = new boolean[2];
private Condition[] free = new Condition[N];
private PriorityQueue<ProcessPriority> pq = new PriorityQueue<>(N);
private int ticket = 0;
private int id = 0;
public PrintersMonitor() {
for (int i = 0; i < N; ++i) {
free[i] = new Condition();
}
}
public synchronized int request(int priority) {
// Прво проверимо да ли има слободних штампача
for (int i = 0; i < 2; ++i) {
if (!busy[i]) {
busy[i] = true;
return i;
}
}
// Ако нема, убацујемо се у ред за чекање
int myTicket = ticket++;
int myId = id;
id = (id + 1) % N;
ProcessPriority pp = new ProcessPriority(priority, myTicket, myId);
pq.push(pp);
free[myId].wait();
// Одблокирао нас је неки процес који је раније држао неки штампач
return pp.printer;
}
public synchronized void release(int printer) {
if (pq.isEmpty()) {
busy[printer] = false;
} else {
ProcessPriority pp = pq.pop();
free[pp.id].signal();
pp.printer = printer;
}
}
}
2. задатак
Поставка
Посматра се агенција за изнајмљивање аутомобила. У возном парку постоје 20 стандардних возила и 10 лукс возила. Приликом доласка клијента да изнајми ауто, он се изјашњава да ли жели да изнајми стандардно или лукс возило или му је све једно. Након тога он чека у реду све док му се возило не додели на коришћење. По завршетку коришћења, корисник долази још једном у агенцију и враћа ауто. У агенцији постоји један запослени који води евиденцију о томе који ауто је тренутно на коришћењу код ког корисника. Клијентима није дозвољено напуштање агенције све док запослени не обради њихов захтев за преузимање или враћање возила. Користећи регионе написати методу које се позива приликом доласка клијента да изнајми ауто, методу које се позива приликом доласка клијента да врати ауто и методу која симулира рад запосленог, као и код за иницијализацију. Потребно је обезбедити да возила не стоје на паркингу агенције, уколико постоји било који клијент који жели да изнајми тај тип возила.
Решење
#include <map>
#include <queue>
using namespace std;
// Структуре за упућивање захтева запосленом
struct Request {
int customerId;
unsigned place;
};
enum RequestType {
STANDARD_VEHICLE,
LUXURY_VEHICLE,
ANY_VEHICLE,
RETURN_VEHICLE
};
// Монитор
struct CarDealership {
queue<Request> standardRequests;
queue<Request> luxuryRequests;
queue<Request> anyRequests;
queue<Request> returnRequests;
map<int, int> rentedCars;
int place = 1;
};
CarDealership dealership;
// Ова два реда се мењају само из запосленог, тако да не морају да буду у региону.
queue<int> standardCars;
queue<int> luxuryCars;
int rentCar(int customerId, int which) {
region (dealership) {
unsigned myPlace = dealership.place++;
switch (which) {
case STANDARD_VEHICLE:
dealership.standardRequests.push({customerId, myPlace});
break;
case LUXURY_VEHICLE:
dealership.luxuryRequests.push({customerId, myPlace});
break;
case ANY_VEHICLE:
dealership.anyRequests.push({customerId, myPlace});
break;
}
await (dealership.rentedCars[customerId]);
}
}
void returnCar(int customerId) {
region (dealership) {
unsigned myPlace = dealership.place++;
dealership.returnRequests.push({customerId, myPlace});
await (!dealership.rentedCars[customerId]);
}
}
void employee() {
while (true) {
Request req;
int request = 0;
region (dealership) {
await (
dealership.standardRequests.size() +
dealership.luxuryRequests.size() +
dealership.anyRequests.size() +
dealership.returnRequests.size() > 0
);
unsigned minPlace = -1;
if (
!dealership.standardRequests.empty() &&
!standardCars.empty() &&
dealership.standardRequests.front().place < minPlace
) {
minPlace = dealership.standardRequests.front().place;
request = STANDARD_VEHICLE;
}
if (
!dealership.luxuryRequests.empty() &&
!luxuryCars.empty() &&
dealership.luxuryRequests.front().place < minPlace
) {
minPlace = dealership.luxuryRequests.front().place;
request = LUXURY_VEHICLE;
}
if (
!dealership.anyRequests.empty() &&
(!standardCars.empty() || !luxuryCars.empty()) &&
dealership.anyRequests.front().place < minPlace
) {
minPlace = dealership.anyRequests.front().place;
request = ANY_VEHICLE;
}
if (!dealership.returnRequests.empty() && dealership.returnRequests.front().place < minPlace) {
minPlace = dealership.returnRequests.front().place;
request = RETURN_VEHICLE;
}
switch (request) {
case STANDARD_VEHICLE:
req = dealership.standardRequests.front();
dealership.standardRequests.pop();
break;
case LUXURY_VEHICLE:
req = dealership.luxuryRequests.front();
dealership.luxuryRequests.pop();
break;
case ANY_VEHICLE:
req = dealership.anyRequests.front();
dealership.anyRequests.pop();
break;
case RETURN_VEHICLE:
req = dealership.returnRequests.front();
dealership.returnRequests.pop();
break;
}
}
// Овде запослени ради неки свој посао бележења
region (dealership) {
switch (request) {
case STANDARD_VEHICLE:
dealership.rentedCars[req.customerId] = standardCars.front();
standardCars.pop();
break;
case LUXURY_VEHICLE:
dealership.rentedCars[req.customerId] = luxuryCars.front();
luxuryCars.pop();
break;
case ANY_VEHICLE:
if (standardCars.empty()) {
dealership.rentedCars[req.customerId] = luxuryCars.front();
luxuryCars.pop();
} else {
dealership.rentedCars[req.customerId] = standardCars.front();
standardCars.pop();
}
break;
case RETURN_VEHICLE:
int carId = dealership.rentedCars[req.customerId];
dealership.rentedCars[req.customerId] = 0;
if (carId > 20) {
luxuryCars.push(carId);
} else {
standardCars.push(carId);
}
break;
}
}
}
}
int main() {
for (int i = 0; i < 20; ++i) {
standardCars.push(i + 1);
}
for (int i = 0; i < 10; ++i) {
luxuryCars.push(i + 21);
}
return 0;
}
3. задатак
Поставка
Посматра се прстен у коме сваки чвор може да прими поруку само од свог претходника и који може да пошаље поруку смо[sic] свом следбенику. Сваки чвор садржи целобројну вредност. Потребно је остварити интеракције између тих чворова користећи синхрону комуникацију да би се сазнало која је минимална а која је максимална вредност. Сваки чвор треба да сазна које су максимална и минимална вредност.
Решење
const int N = 100;
chan<pair<int, int>> values[N];
void process(int i, int v) {
int min = v;
int max = v;
pair<int, int> newPair;
if (i == 0) {
// Први процес прво шаље, прима коначни резултат и прослеђује
values[0].send({min, max});
newPair = values[N-1].receive();
} else {
// Остали процеси прво примају, израчунавају, шаљу даље, примају коначни резултат и прослеђују
newPair = values[i-1].receive();
if (newPair.first < min) {
min = newPair.first;
}
if (newPair.second > max) {
max = newPair.second;
}
values[i].send({min, max});
newPair = values[i-1].receive();
}
min = newPair.first;
max = newPair.second;
if (i != N-1) {
// Ако смо последњи процес не треба да шаљемо првом опет, јер неће примити
values[i].send({min, max});
}
}
4. задатак
Поставка
Посматра се шпил од 24 карте, подељене у 4 боје, са по 6 различитих бројева. Игру играју 4 играча, који седе за округлим столом и сваки од њих иницијално држи по 4 карте. Између два суседна играча се налази гомила са картама, која може у неком тренутку бити празна, а иницијално садржи 2 карте. Игра се завршава када неки играч објави да има све 4 карте истог броја, у различитим бојама, и тада сви играчи прекидају игру. Сваки играч, док год нема 4 исте и нико није објавио да је победник, избацује једну карту из своје руке и ставља је на гомилу са своје леве стране, потом узима једну карту из гомиле са своје десне стране. Претпоставити да су играчима иницијално подељене карте на случајан начин. Користећи C-Linda, написати изглед процедуре за једног играча. Поред играча, не постоји ниједан други процес.
Решење
Кључна функција је void player(int i), док остале дају контекст решењу. Коришћени тагови су:
player: иницијална подела карата играчимаdeck: садржај једног шпила на столуgame over: да ли је игра готоваcan set game over: да ли играч може да објави да је победио (семафор окоgame over)
typedef pair<int, int> Card;
template<typename T>
T randomChoice(vector<T>& vec) {
int index = rand() * vec.size() / RAND_MAX;
T ret = vec[index];
vec.erase(vec.begin() + index);
return ret;
}
bool hasWon(vector<Card>& cards) {
bool colors[4] = {false};
colors[cards[0].first] = true;
int num = cards[0].second;
for (int i = 1; i < 4; ++i) {
if (cards[i].second != num || colors[cards[i].first]) {
return false;
}
colors[cards[i].first] = true;
}
return true;
}
void player(int i) {
vector<Card> cards;
Card c;
for (int i = 0; i < 4; ++i) {
in("player", i, &c);
cards.push_back(c);
}
while (true) {
if (hasWon(cards)) {
in("can set game over");
if (!rdp("game over")) {
out("game over");
}
out("can set game over");
out("deck", (i + 1) % 4, Card(-1, -1));
break;
}
c = randomChoice(cards);
out("deck", (i + 1) % 4, c);
in("deck", i, &c);
if (rdp("game over")) {
break;
}
cards.push_back(c);
}
}
void initialize() {
// Празнимо простор торки од претходне игре
while (inp("deck") || inp("player") || inp("game over") || inp("can set game over"));
// Вршимо насумичну расподелу шпила
vector<Card> cards;
for (int color = 0; color < 4; ++color) {
for (int number = 0; number < 6; ++number) {
cards.push_back({color, number});
}
}
for (int d = 0; d < 4; ++d) {
for (int c = 0; c < 2; ++c) {
Card card = randomChoice(cards);
out("deck", d, card);
}
}
for (int p = 0; p < 4; ++p) {
for (int c = 0; c < 4; ++c) {
Card card = randomChoice(cards);
out("player", p, card);
}
eval(player, p);
}
out("can set game over");
}