KDP/Jun 2021
Postavka ovog roka može se naći sa stranice predmeta.
1. zadatak
Postavka
Potrebno je da N procesa dele dva štampača. Pre upotrebe štampača, proces P[i] poziva monitorsku proceduru request(), a procedura vraća identifikator dodeljenog štampača - printer. Po završetku štampanja, proces P[i] oslobađa štampač sa release(printer). Definišite monitorsku invarijantu. Razviti monitor koji koristi Signal and Continue disciplinu. Nakon toga, pretpostaviti da kod procedure request postoji dodatni argument kojim proces dostavlja prioritet zahteva. Modifikovati monitor, tako da se štampači dobijaju u skladu sa prioritetom. Pri istom prioritetu treba da važi redosled pristizanja zahteva - FCFS.
Rešenje
Monitorska invarijanta, ukoliko je broj štampača, je . Krajnje modifikovani monitor izgleda:
class PrintersMonitor {
private boolean[] busy = new boolean[2];
private Condition free = new Condition();
public synchronized int request(int priority) {
while (true) {
for (int i = 0; i < 2; ++i) {
if (!busy[i]) {
return i;
}
}
free.wait(priority);
}
}
public synchronized void release(int printer) {
busy[printer] = false;
free.signal();
}
}
2. zadatak
Postavka
Posmatra se agencija za iznajmljivanje automobila. U voznom parku postoje 20 standardnih vozila i 10 luks vozila. Prilikom dolaska klijenta da iznajmi auto, on se izjašnjava da li želi da iznajmi standardno ili luks vozilo ili mu je sve jedno. Nakon toga on čeka u redu sve dok mu se vozilo ne dodeli na korišćenje. Po završetku korišćenja, korisnik dolazi još jednom u agenciju i vraća auto. U agenciji postoji jedan zaposleni koji vodi evidenciju o tome koji auto je trenutno na korišćenju kod kog korisnika. Klijentima nije dozvoljeno napuštanje agencije sve dok zaposleni ne obradi njihov zahtev za preuzimanje ili vraćanje vozila. Koristeći regione napisati metodu koje se poziva prilikom dolaska klijenta da iznajmi auto, metodu koje se poziva prilikom dolaska klijenta da vrati auto i metodu koja simulira rad zaposlenog, kao i kod za inicijalizaciju. Potrebno je obezbediti da vozila ne stoje na parkingu agencije, ukoliko postoji bilo koji klijent koji želi da iznajmi taj tip vozila.
Rešenje
#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. zadatak
- Ovaj zadatak nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.
Postavka
Rešenje
4. zadatak
- Ovaj zadatak nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.