KDP/Jul 2021
Postavka ovog roka može se naći sa stranice predmeta.
1. zadatak
Postavka
Kod Tie breaker algoritma za n procesa se dogodio sledeći slučaj – prilikom izvršavanja koda za ulazak u kritičnu sekciju, svih n procesa su ušli u stanje 1 i nijedan još nije ušao u stanje 2. Odgovoriti na sledeća pitanja i obrazložiti odgovor:
- Da li proces koji je prvi ušao u stanje 1 prvi ulazi u stanje 2?
- Da li proces koji je prvi ušao u stanje n-2 prvi ulazi u kritičnu sekciju?
- Da li proces koji je poslednji ušao u stanje 1 može da bude treći koji ulazi u stanje 2?
- Da li proces koji je poslednji ušao u stanje 1 može da bude prvi koji ulazi u kritičnu sekciju?
Rešenje
- U opštem slučaju, ne mora da znači da će proces koji je prvi ušao u stanje 1 prvi ući i u stanje 2. Pošto se u tom trenutku svi procesi nalaze u stanju 1, bilo koji proces koji nije poslednji stigao u stanje 1 će moći da prvi uđe u stanje 2. Specijalno, u slučaju kada je , proces koji je prvi ušao u stanje 1 će garantovano prvi ući u stanje 2.
- U prvom stanju mogu da se nađu procesa, u drugom stanju procesa... tom logikom u stanju mogu da se nađu 3 procesa istovremeno. Jedan od ta tri procesa će poslednji ući i neće moći da napreduje, dok će ostala dva moći da napreduju i ne garantuje se koji od ta dva procesa će prvi napredovati.
- Proces koji je poslednji ušao u stanje 1 će biti poslednji koji će iz njega izaći. Moguće je da on bude treći koji ulazi u stanje 2 ukoliko je , u suprotnom ne mora da znači.
- Proces koji je poslednji ušao u stanje 1 je poslednji koji ulazi u kritičnu sekciju. Da bi takođe bio i prvi, moralo bi da važi a to nema smisla.
2. zadatak
Postavka
Posmatra se agencija za iznajmljivanje automobila. U voznom parku postoje M standardnih vozila i N luks vozila. Prilikom dolaska klijenta koji želi da iznajmi auto, on se izjašnjava da li želi da iznajmi standardno ili luks vozilo ili mu je svejedno. Klijent č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. Potrebno je obezbediti da klijenti preuzimaju svoje automobile po redosledu dolaska u agenciju. Klijent ima mogućnost da iznajmi više vozila, ali je svaki dolazak vezan isključivo za pozajmicu jednog automobila. Rešiti problem koristeći monitore sa signal and continue disciplinom.
Rešenje
class CarAgency {
public static final STANDARD_VEHICLE = 0;
public static final LUXURY_VEHICLE = 1;
public static final ANY_VEHICLE = 2;
private int standardVehicles = 100;
private int luxuryVehicles = 10;
private final Condition[] queues = new Condition[3];
private int ticket = 1;
public CarAgency() {
for (int i = 0; i < 3; ++i) {
queues[i] = new Condition();
}
}
public synchronized void rentCar(int which) {
int myTicket = ticket++;
if (
standardVehicles == 0 && which == STANDARD_VEHICLE ||
luxuryVehicles == 0 && which == LUXURY_VEHICLE ||
(standardVehicles == 0 && luxuryVehicles == 0)
) {
// Нема возила, чекамо
queues[which].wait(myTicket);
// Број возила је смањен већ при сигнализирању
} else if (which == STANDARD_VEHICLE) {
// Желели смо стандардно возило и добили смо
--standardVehicles;
} else if (which == LUXURY_VEHICLE) {
// Желели смо луксузно возило и добили смо
--luxuryVehicles;
} else if (standardVehicles == 0) {
// Желели смо било које возило и добили смо луксузно
--luxuryVehicles;
} else {
// Желели смо било које возило и добили смо стандардно
--standardVehicles;
}
}
public synchronized void returnCar(int which) {
if (which == STANDARD_VEHICLE) {
++standardVehicles;
boolean qStandardVehicle = queues[STANDARD_VEHICLE].queue();
boolean qAnyVehicle = queues[ANY_VEHICLE].queue();
if (qStandardVehicle || qAnyVehicle) {
--standardVehicles;
}
if (qStandardVehicle && qAnyVehicle) {
if (queues[STANDARD_VEHICLE].minrank() < queues[ANY_VEHICLE].minrank()) {
queues[STANDARD_VEHICLE].signal();
} else {
queues[ANY_VEHICLE].signal();
}
} else if (qStandardVehicle) {
queues[STANDARD_VEHICLE].signal();
} else if (qAnyVehicle) {
queues[ANY_VEHICLE].signal();
}
} else {
++luxuryVehicles;
boolean qLuxuryVehicle = queues[LUXURY_VEHICLE].queue();
boolean qAnyVehicle = queues[ANY_VEHICLE].queue();
if (qLuxuryVehicle || qAnyVehicle) {
--luxuryVehicles;
}
if (qLuxuryVehicle && qAnyVehicle) {
if (queues[LUXURY_VEHICLE].minrank() < queues[ANY_VEHICLE].minrank()) {
queues[LUXURY_VEHICLE].signal();
} else {
queues[ANY_VEHICLE].signal();
}
} else if (qLuxuryVehicle) {
queues[LUXURY_VEHICLE].signal();
} else if (qAnyVehicle) {
queues[ANY_VEHICLE].signal();
}
}
}
}
3. zadatak
Postavka
U Lindi realizovati licitaciju u kojoj postoji jedan proces vođa_licitacije i n procesa učesnika_u_licitaciji i jedan proces tick koji samo ažurira vreme. Vođa licitacije treba da inicijalizuje torku sa početnom vrednošću i da posle datog vremenskog intervala završi licitaciju, uspešno ako je izlicitirana vrednost veća od rezervisane vrednosti, neuspešno inače. Procesi učesnici u licitaciji treba da se realizuju tako da se ne blokiraju kada se završi data licitacija, treba da znaju koja je izlicitirana vrednost i da li su je oni postavili.
Rešenje
Tagovi u ovom rešenju označavaju:
value: Trenutna vrednost licitacijetime out: Postavlja se kad istekne vremeended: Postavlja se kad vođa licitacije objavi kraj licitacije
const int FINAL_TIME = 100;
const int INITIAL_VALUE = 50;
const int RESERVE_VALUE = 100;
int getBid();
void sleep(unsigned int seconds);
void vodjaLicitacije() {
out("value", INITIAL_VALUE, -1);
in("time out");
int value;
int user;
in("value", &value, &user);
out("ended", value > RESERVE_VALUE);
out("value", value, user);
}
void ucesnikULicitaciji(int i) {
int value;
int user;
int bid = getBid();
bool success;
in("value", &value, &user);
if (rdp("ended") || value > bid) {
out("value", value, user);
} else {
out("value", bid, i);
}
rd("ended", &success);
rd("value", &value, &user);
if (success && user == i) {
// Ми добијамо лицитацију
}
}
void tick() {
int time = 0;
while (true) {
sleep(1);
if (++time == FINAL_TIME) {
out("time out");
}
}
}
4. zadatak
Postavka
Postoji N procesa node(i:1..N) koji ili čuvaju elemente liste ili su slobodni. Svaki od njih može da čuva neku vrednost (value) i pokazivač na sledeći element u listi (next). Proces head čuva pokazivač na prvi element u listi. Prilikom brisanja elementa iz liste proces koji ga predstavlja se prebacuje na početak liste slobodnih procesa na koji ukazuje proces free. Proces start inicira brisanje elementa sa zadatom vrednošću iz liste. Realizovati procedure za sve navedene procese koristeći CSP.
Rešenje
[node(num: 1..N)::NODE, head::HEAD, free::FREE, start::START]
NODE::
value: integer;
next: integer;
free: boolean;
free := true;
[
num = N -> next := 0
□
num <> N -> next := num + 1
];
*[
free = false; start?get -> start!value(value, next)
□
free = true; start?get -> start!novalue
□
start?setNext(newNext) -> next := newNext
□
start?erase(newNext) -> free := true
// Акција постављања вредности није имплементирана
// јер није ни тражена у задатку
]
HEAD::
first: integer;
first := 0;
*[
first = 0; start?get -> start!empty
□
first <> 0; start?get -> start!first(first)
□
start?set(value) -> first := value
]
FREE::
free: integer;
free := 1;
*[
free = 0; start?get -> start!full
□
free <> 0; start?get -> start!free(free)
□
start?set(newFree) -> free := newFree
]
START::
// Претпоставимо да је задата вредност 14
value: integer;
value := 14;
prev: integer;
prev := 0;
head!get;
*[
// Вредност не постоји у листи
head?empty -> skip
□
head?first(first) -> node(first)!get
□
// Десила се нека грешка
(i: 1..N) node(i)?novalue -> skip
□
(i: 1..N) node(i)?value(nodeValue, next) -> [
nodeValue = value ->
[
prev = 0 -> head!set(next)
□
prev <> 0 -> node(prev)!setNext(next)
];
node(i)!erase;
free!get;
[
free?full -> node(i)!setNext(0)
□
free?free(nextFree) -> node(i)!setNext(nextFree)
];
free!set(i)
□
nodeValue <> value -> [
// Вредност не постоји у листи
next = 0 -> skip
□
next <> 0 -> node(next)!get
]
]
]