KDP/Jun 2020
Postavka ovog roka može se naći sa stranice predmeta (zipovana).
1. zadatak
Postavka
Andersenov algoritam za N procesa realizovan pomoću addAndGet operacije. Ukoliko bi addAndGet operacija imala sledeći efekat: addAndGet(var, incr) : < var = var + incr; return(var); >, da li je moguće napraviti Fine grain rešenje, polazeći od Coarse grain rešenja (napisati ga), i ako je moguće – napravite ga.
Rešenje
Coarse-grain rešenje:
const int N = 100;
bool flag[N];
int tail = 0;
void worker() {
while (true) {
< int index = tail; tail = (tail + 1) % N; >
< await(flag[index]); >
/* критична секција */
flag[index] = false;
flag[(index + 1) % N] = true;
/* некритична секција */
}
}
Fine-grain rešenje:
const int N = 100;
bool flag[N];
int tail = 0;
void worker() {
while (true) {
int index = (addAndGet(tail, 1) - 1) % N;
while (!flag[index]) skip();
/* критична секција */
flag[index] = false;
flag[(index + 1) % N] = true;
/* некритична секција */
}
}
2. zadatak
Postavka
Posmatra se ostrvo na kome ljudi mogu da razgledaju muzej o dinosaurusima i park za živim primercima (The Jurassic Park Problem). U parku postoji N bezbednih vozila koja mogu da prime po jednog putnika. U park može dolaziti proizvoljan broj posetilaca. Na početku posetilac slobodno razgleda muzej sa eksponatima. Kada završi razgledanje, prelazi na deo sa živim dinosaurusima, tako što sačeka da se pojavi prvo sigurno vozilo koje će ga provesti kroz park. Kada naiđe slobodno vozilo, posetilac prelazi na vožnju po parku koja traje neko vreme. Na kraju vožnje posetilac napušta park (može nekad da se vrati), a vozilo se vraća da primi sledećeg posetioca. Ukoliko su sva vozila zauzeta, posetilac koji želi da ide u obilazak čeka slobodno vozilo. Ukoliko postoji slobodno vozilo, ali ne i posetilac koji trenutno čeka da uđe, onda vozilo čeka. Koristeći semafore napisati programe za posetioce i vozila, kao i kod za inicijalizaciju.
Rešenje
const int N = 100;
sem carCount = N;
list<pair<sem*, sem*>> freeCars;
sem carMutex = 1;
void car() {
sem carSem = 0;
sem visitorSem = 0;
while (true) {
// Враћамо се назад на место (први пут, ово служи за иницијализацију)
carMutex.wait();
freeCars.push_back({&carSem, &visitorSem});
carMutex.signal();
carCount.signal();
carSem.wait();
// Посетилац се вози по парку
visitorSem.signal();
// Готова вожња по парку
carSem.wait();
}
}
void visitor() {
while (true) {
// Обилазак музеја
carCount.wait();
carMutex.wait();
sem* carSem = freeCars.front().first;
sem* visitorSem = freeCars.front().second;
freeCars.pop_front();
carSem->signal();
carMutex.signal();
// Вожња по парку
visitorSem->wait();
// Готова вожња по парку
carSem->signal();
// Посетилац је напустио парк и можда се некад врати
}
}
3. zadatak
- Ovaj zadatak nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.
Postavka
Objasnite kako se realizuje monitor sa Signal and Continue disciplinom, kod koga je dozvoljeno da se iz jedne monitorske metode poziva druga monitorska metoda koristeći semafore. Za svaku karakerističnu[sic] situaciju (5 situacija) dati osnovne komponente kôda (kao sa predavanja) i objasnite funkciju delova tog kôda. Za svaku situaciju posebno navesti koji semafori se koriste, i od čega zavisi broj tih semafora.
Rešenje
4. zadatak
- Ovaj zadatak nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.
Postavka
U nekom obdaništu postoji pravilo koje kaže da se na svaka tri deteta mora naći barem jedna vaspitačica (The Child Care Problem). Roditelj dovodi jedno ili više dece u obdanište i čeka sve dok se ne pojavi mesto, kako bi ostavio svu decu odjednom i otišao. Roditelj takođe može da odvede jedno ili više dece, takođe odjednom. Vaspitačica dolazi na posao i sme da napusti obdanište samo ukoliko to ne narušava pravilo. Mora se poštovati redosled dolaska roditelja koji ostavljaju decu i vaspitačica koje odlaze sa posla. Koristeći uslovne kritične regione, napisati procedure za roditelje koji dovode decu, roditelje koji odvode decu, vaspitačice koje dolaze na posao i vaspitačice koje odlaze sa posla. Inicijalizovati početne uslove.
Rešenje
5. zadatak
Postavka
Realizovati prsten od n procesa, koji komuniciraju asinhronim prosleđivanjem poruka korišćenjem komunikacionih kanala i send i receive iskaza, a kod koga proces 0 generiše slučajan niz od m prirodnih brojeva u intervalu od 1 do 20.000 završen sa sentinel vrednošću EONAT (npr 20.001). Preostalih n-1 procesa odstranjuju iz niza sve pojave prvih n-1 prostih brojeva. Svaki proces ima po jedan različit prost broj za koji je zadužen. Nakon odstranjivanja prostih brojeva, modifikovan niz se distribuira svim procesima. Obezbediti maksimalnu konkurentnost.
Rešenje
const int N = ...;
const int m = ...;
const int EONAT = 20001;
chan values[N](int);
void process0(){
int array[m];
for (int i = 0; i < m; i++) array[i] = rand(1, 20000);
for (int i = 0; i < m; i++) send values[1](array[i]);
send values[1](EONAT);
bool end = false;
int temp, index = 0;
while (!end) {
receive values[0](temp);
if (temp == EONAT) end = true;
else array[index++] = temp;
}
for (int i = 0; i < index; i++) send values[1](array[i]);
send values[1](EONAT);
}
void process(int id, int myNumber) {
int array[m];
bool end = false;
int temp;
while (!end) {
receive values[id](temp);
if (temp == EONAT) end = true;
else if (temp != myNumber) send values[(id + 1) % N](temp);
}
end = false;
int index = 0;
while (!end) {
receive values[id](temp);
if (temp == EONAT) end = true;
else {
array[index++] = temp;
if (id != N-1) send values[(id + 1) % N](temp);
}
}
}
6. zadatak
- Ovaj zadatak nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.
Postavka
Posmatra se skup čvorova u grafu koji mogu da komuniciraju samo sa svojim susedima (Distributed Pairing Problem). Svaki čvor treba da nađe čvor sa kojim će se upariti. Na kraju postupka uparivanja svaki čvor će ili imati svog para, ili ostati neuparen, ali tako da ni jedna dva susedna čvora ne ostanu neuparena. Napisati program za čvor koristeći biblioteku C-Linda.