КДП/Јун 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;
private int waiting = 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);
++waiting;
free[myId].wait();
// Одблокирао нас је неки процес који је раније држао неки штампач
--waiting;
return pp.printer;
}
public synchronized void release(int printer) {
if (waiting == 0) {
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. задатак
- Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.
Поставка
Посматра се прстен у коме сваки чвор може да прими поруку само од свог претходника и који може да пошаље поруку смо свом следбенику. Сваки чвор садржи целобројну вредност. Потребно је остварити интеракције између тих чворова користећи синхрону комуникацију да би се сазнало која је минимална а која је максимална вредност. Сваки чвор треба да сазна које су максимална и минимална вредност.
Решење
4. задатак
- Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.
Поставка
Посматра се шпил од 24 карте, подељене у 4 боје, са по 6 различитих бројева. Игру играју 4 играча, који седе за округлим столом и сваки од њих иницијално држи по 4 карте. Између два суседна играча се налази гомила са картама, која може у неком тренутку бити празна, а иницијално садржи 2 карте. Игра се завршава када неки играч објави да има све 4 карте истог броја, у различитим бојама, и тада сви играчи прекидају игру. Сваки играч, док год нема 4 исте и нико није објавио да је победник, избацује једну карту из своје руке и ставља је на гомилу са своје леве стране, потом узима једну карту из гомиле са своје десне стране. Претпоставити да су играчима иницијално подељене карте на случајан начин. Користећи C-Linda, написати изглед процедуре за једног играча. Поред играча, не постоји ниједан други процес.