KDP/Januar 2021
Postavka ovog roka može se naći sa stranice predmeta.
1. zadatak
- Ovaj zadatak nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.
Postavka
Potrebno je realizovati tajmer koristeći privatne semafore i tehniku predaje štafetne palice. Tajmer ima dve metode, prva je metoda wakeme koja omogućava da se data nit blokirana n jedinica vremena (ovo je argument), a druga je metoda tick koja označava da je istekla jedna jedinica vremena.
Rešenje
2. zadatak
Postavka
Postoji toalet kapaciteta N (N > 1) koji mogu da koriste žene, muškarci, deca i domar (Single Bathroom Problem) takav da važe sledeća pravila korišćenja: u isto vreme u toaletu ne mogu naći i žene i muškarci; deca mogu da dele toalet i sa ženama i sa muškarcima; dete može da se nađe u toaletu samo ako se tamo nalazi barem jedna žena ili muškarac; domar ima ekskluzivno pravo korišćenja toaleta. Napisati monitor sa signal and wait disciplinom koji rešava dati problem, kao i glavne programe za muškarce, žene, decu i domare, kroz koje su dati primeri korišćenja monitorskih procedura.
Rešenje
class SingleBathroomProblem {
public static final int capacity = 10;
private int count = 0;
private int childCount = 0;
// Група која је тренутно у тоалету
// -1 - нема никога, 0 - мушкарци, 1 - жене, 2 - домар
private int group = -1;
private final Condition queue = new Condition();
private final Condition childrenQueue = new Condition();
private final Condition waitingForChildren = new Condition();
private int ticket = 1;
private void signalPersonOrChild() {
boolean personWaiting = queue.queue() && queue.minrank() % 3 == group;
boolean childWaiting = childrenQueue.queue();
if (personWaiting && childWaiting) {
if (queue.minrank() > childrenQueue.minrank() * 3) {
// Одрасла особа је стигла пре детета
queue.signal();
} else {
// Дете је стигло пре одрасле особе
childrenQueue.signal();
}
} else if (personWaiting) {
queue.signal();
} else if (childWaiting) {
childrenQueue.signal();
}
}
public synchronized void enterMan() {
int myTicket = ticket++;
if (count == capacity || group == 1 || group == 2 || queue.queue()) {
// Пун тоалет, у њему су жене/домар или има других особа испред тоалета
queue.wait(myTicket * 3);
}
++count;
if (group == -1) {
// Означавамо да је тренутно активна група мушкараца
group = 0;
} else if (waitingForChildren.queue()) {
// Ако има мушкарца који чека децу јавља му се да не мора више да чека
waitingForChildren.signal();
}
if (count != capacity) {
signalPersonOrChild();
}
}
public synchronized void enterWoman() {
int myTicket = ticket++;
if (count == capacity || group == 0 || group == 2 || queue.queue()) {
// Пун тоалет или су у њему мушкарци/домар
queue.wait(myTicket * 3 + 1);
}
++count;
if (group == -1) {
// Означавамо да је тренутно активна група жена
group = 1;
} else if (waitingForChildren.queue()) {
// Ако има жена која чека децу јавља јој се да не мора више да чека
waitingForChildren.signal();
}
if (count != capacity) {
signalPersonOrChild();
}
}
public synchronized void enterJanitor() {
int myTicket = ticket++;
if (group != -1) {
// У тоалету или испред тоалета има било кога
queue.wait(myTicket * 3 + 2);
}
++count;
// Означавамо да је домар тренутно у тоалету
group = 2;
}
public synchronized void enterChild() {
int myTicket = ticket++;
if (count == capacity || group == 2 || group == -1 || queue.queue() || childrenQueue.queue() || waitingForChildren.queue()) {
// Пун тоалет, у њему нема никога, у њему је домар, има других особа
// испред тоалета или има особа која је унутра и чека да деца изађу
childrenQueue.wait(myTicket);
}
++count;
++childCount;
if (count != capacity) {
signalPersonOrChild();
}
}
public synchronized void exitMan() {
if (count == childCount + 1) {
// Мушкарац не може да изађе док су деца сама у тоалету
waitingForChildren.wait();
}
--count;
if (count == 0) {
// Нема више никог у тоалету, пусти следећу одраслу особу ако је има
group = -1;
if (queue.queue()) {
queue.signal();
}
} else {
signalPersonOrChild();
}
}
public synchronized void exitWoman() {
if (count == childCount + 1) {
// Жена не може да изађе док су деца сама у тоалету
waitingForChildren.wait();
}
--count;
if (count == 0) {
// Нема више никог у тоалету, пусти следећу одраслу особу ако је има
group = -1;
if (queue.queue()) {
queue.signal();
}
} else {
signalPersonOrChild();
}
}
public synchronized void exitJanitor() {
--count;
// Сигурно нема више никог у тоалету
group = -1;
if (queue.queue()) {
queue.signal();
}
}
public synchronized void exitChild() {
--count;
--childCount;
if (waitingForChildren.queue() && childCount == 0) {
// Јави особи која чека на излазак детета да су сва деца изашла
waitingForChildren.signal();
}
if (count == 0) {
// Нема више никог у тоалету, пусти следећу одраслу особу ако је има
group = -1;
if (queue.queue()) {
queue.signal();
}
} else {
signalPersonOrChild();
}
}
}
3. zadatak
Postavka
Realizujte coarse grain ticket algoritam za ulazak u kritičnu sekciju koristeći CSP.
Rešenje
Nije jasno na šta se misli pod coarse grain realizacijom u ovom slučaju, ali je ispod jedna moguća implementacija ticket algoritma za ulazak u kritičnu sekciju koristeći CSP.
[ticket::TICKET || user(i: 1..N)::USER]
TICKET::
users: (1..N) integer;
head: integer;
tail: integer;
head := 0;
tail := 0;
*[
head == tail; (i: 1..N) user(i)?enter ->
// Нема никога, па пуштамо овог корисника
user(i)!pass;
tail := (tail + 1) mod N
□
head <> tail; (i: 1..N) user(i)?enter ->
// Додајемо корисника у ред чекања
users(tail) := i;
tail := (tail + 1) mod N
□
(i: 1..N) user(i)?exit ->
head := (head + 1) mod N;
[
// Пуштамо следећег корисника, уколико га има
users(head) <> 0 ->
user(users(head))!pass;
users(head) := 0
]
□
]
USER::
ticket!enter;
ticket?pass;
// У критичној секцији
ticket!exit
4. zadatak
Postavka
Na ulasku u jednu železničku stanicu sa jednom ulaznom prugom i jednim slepim kolosekom desio se kvar, pa se na ulazu napravila kolona međunarodnih i domaćih vozova. Kvar je otklonjen i treba puštati vozove. Da bi međunarodni vozovi manje kasnili, oni se puštaju prvi, po redosledu dolaska. Pošto postoji samo jedna pruga i vozovi se ne mogu „preticati”, svi domaći vozovi koji su bili ispred međunarodnih u koloni se prebacuju na slepi kolosek koji je dovoljno veliki da svi vozovi mogu da stanu. Kada svi međunarodni vozovi odu, puštaju se prvo vozovi sa slepog koloseka, pa onda preostali domaći vozovi iz kolone. Sama stanica ima N perona, tj. N vozova istovremeno mogu da ukrcavaju i iskrcavaju putnike. Vozovi koji u međuvremenu pristižu treba da budu opsluženi, ali novopristigli međunarodni nemaju prioritet u odnosu na vozove koji su ispred njih u koloni. Rešiti problem koristeći C-Linda. Napisati potrebnu inicijalizaciju koja oslikava stanje nakon otklanjanja kvara. Voditi računa o tome da su kompozicije vozova teške i da je potrebno vreme da se voz pomeri sa jednog mesta na drugo.
Rešenje
Sledeći tagovi su korišćeni tokom realizacije:
ticket: redosled voza po pristizanjucurrent: voz koji trenutno okupira ulaz (bilo da izlazi iz ulaza i ide u slepi kolosek, izlazi iz ulaza i ide na stanicu ili izlazi iz slepog koloseka i ide na stanicu)sidetrack: vozovi koji se nalaze u slepom koloseku, prva vrednost je redosled u slepom koloseku a druga redosled pristizanja vozasidetrackHead: prvi voz koji sledeći treba da izađe iz slepog koloseka, po redosledu u slepom kolosekusidetrackTail: broj vozova u slepom kolosekustation: vozovi koji su trenutno na jednom od regularnih N koloseka
Način na koji je u ovom rešenju bilo određeno da li je voz pristigao tokom kvara ili posle je provera da li je njegov redosled pristizanja veći ili jednak konstanti M, što je broj vozova koji su pristigli tokom kvara. Nakon početne inicijalizacije stanja nakon popravljanja kvara očekuje se da novopristigli vozovi sami naprave train proces.
const int N = 10;
const int M = 100;
void setCurrentFromSidetrack() {
int sidetrackTicket;
int sidetrackHead;
in("sidetrackHead", &sidetrackHead);
in("sidetrack", sidetrackHead, &sidetrackTicket);
out("sidetrackHead", sidetrackHead + 1);
out("current", sidetrackTicket);
}
void train(bool isInternational) {
int ticket;
in("ticket", &ticket);
out("ticket", ticket + 1);
in("current", ticket);
bool arrivedLater = ticket >= M;
bool isSidetrack = !isInternational && !arrivedLater;
if (isSidetrack) {
// Прво идемо у слепи колосек
int sidetrackTail;
in("sidetrackTail", &sidetrackTail);
out("sidetrack", sidetrackTail, ticket);
out("sidetrackTail", sidetrackTail + 1);
if (ticket == M - 1) {
// Ми смо последњи воз који је стигао током квара,
// треба да предамо првом из слепог колосека
setCurrentFromSidetrack();
in("current", ticket);
} else {
// Предајемо следећем возу који је стигао током квара
out("current", ticket + 1);
in("current", ticket);
}
}
int station;
in("station", &station);
// Идемо на станицу, па чим ослободимо улаз пуштамо следећег
if (isSidetrack) {
if (rdp("sidetrack")) {
// Пуштамо следећег из слепог колосека
setCurrentFromSidetrack();
} else {
// Нема више никог из слепог колосека, пуштамо обичну колону
out("current", M);
}
} else {
if (ticket == M - 1) {
// Ми смо последњи воз који је стигао током квара,
// треба да предамо возовима из слепог колосека, уколико постоје
if (rdp("sidetrack")) {
setCurrentFromSidetrack();
} else {
// Нико није ушао у слепи колосек
out("current", ticket + 1);
}
} else {
// Пуштамо следећи воз, пошто још увек колона која је стигла
// током квара није изашла из улаза
out("current", ticket + 1);
}
}
// Одлазимо са станице
out("station", station);
}
void initialize() {
out("ticket", 0);
for (int i = 0; i < M; ++i) {
eval(train, rand() % 2 == 1);
// Чекамо да воз покупи свој ticket
rd("ticket", i + 1);
}
for (int i = 0; i < N; ++i) {
out("station", i);
}
out("current", 0);
out("sidetrackHead", 0);
out("sidetrackTail", 0);
}