KDP/Semafori
Semafori su koncept iz konkurentnog programiranja iz prvog bloka nastave i dolaze na prvom kolokvijumu za SI i kolokvijumu za RTI.
Januar 2020, 2. zadatak
Postavka
Koristeći semafore napisati program koji rešava problem putovanja liftom. Putnik poziva lift sa proizvoljnog sprata. Kada lift stigne na neki sprat svi putnici koji su izrazili želju da siđu na tom spratu obavezno izađu. Nakon izlaska putnika svi putnici koji su čekali na ulazak uđu u lift i kažu na koji sprat žele da pređu. Tek kada se svi izjasne lift prelazi dalje. Lift redom obilazi spratove i staje samo na one gde ima putnika koji ulaze ili izlaze. Može se pretpostaviti da postoji N spratova.
Rešenje
struct Floor {
list<sem*> peopleEntering;
sem mutexEntering = 1;
list<sem*> peopleExiting;
sem mutexExiting = 1;
};
const int N = 10;
Floor floors[N];
sem liftSem = 0;
void person() {
sem personSem = 0;
int currentFloorIndex = rand() % N;
while (true) {
// Особа може да каже да хоће да изађе на истом спрату као тренутном
// Претпоставка: особа није глупа
int nextFloorIndex = rand() % N;
Floor& currentFloor = floors[currentFloorIndex];
Floor& nextFloor = floors[nextFloorIndex];
currentFloor.mutexEntering.wait();
currentFloor.peopleEntering.push_back(&personSem);
currentFloor.mutexEntering.signal();
// Чекамо да дође лифт
personSem.wait();
// Улазимо у лифт и бирамо на којем спрату стајемо
nextFloor.mutexExiting.wait();
nextFloor.peopleExiting.push_back(&personSem);
nextFloor.mutexExiting.signal();
liftSem.signal();
// Чекамо да лифт стигне на наш спрат
personSem.wait();
// Излазимо из лифта
liftSem.signal();
}
}
void lift() {
int currentFloorIndex = 0;
bool goingUp = true;
while (true) {
// Одређивање следећег спрата
// Претпоставка: лифт све време иде горе-доле, без обзира да ли га је неко звао
if (goingUp) {
if (++currentFloorIndex == N-1) {
goingUp = false;
}
} else {
if (--currentFloorIndex == 0) {
goingUp = true;
}
}
Floor& floor = floors[currentFloorIndex];
// Не морамо да чекамо на mutexExiting, јер се он заузима само када путници улазе
// што тренутно није случај
int countPeopleExiting = floor.peopleExiting.size();
// Задржавамо mutexEntering док не испразнимо листу, како нам не би ушао неочекивани путник
floor.mutexEntering.wait();
int countPeopleEntering = floor.peopleEntering.size();
if (countPeopleExiting == 0 && countPeopleEntering == 0) {
// Не стајемо на овом спрату
floor.mutexEntering.signal();
continue;
}
// Стајемо на овом спрату
// Пуштамо људе да изађу
for (int i = 0; i < countPeopleExiting; ++i) {
sem* personSem = floor.peopleExiting.front();
personSem->signal();
floor.peopleExiting.pop_front();
}
for (int i = 0; i < countPeopleExiting; ++i) {
liftSem.wait();
}
// Пуштамо људе да уђу
for (int i = 0; i < countPeopleEntering; ++i) {
sem* personSem = floor.peopleEntering.front();
personSem->signal();
floor.peopleEntering.pop_front();
}
for (int i = 0; i < countPeopleEntering; ++i) {
liftSem.wait();
}
floor.mutexEntering.signal();
// Настављамо на следећи спрат
}
}
Januar 2023, 1. zadatak
- Ovaj zadatak nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.
Postavka
Implementirati i objasnite osnovnu razliku i razloge za postojanje te razlike između implementacija bafera konačnog kapaciteta (bounded buffer) za slučajeve 1 proizvođač i 1 potrošač, kao i M proizvođača i N potrošača pomoću semafora. U skladu sa objašnjenjem, prikažite razlike i za slučajeve M proizvođača i 1 potrošač, kao i 1 proizvođač i N potrošača.
Rešenje
Jun 2020, 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();
// Посетилац је напустио парк и можда се некад врати
}
}
Jun 2022, 2. zadatak
- Ovaj zadatak nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.
Postavka
Postoje tri osobe među kojima treba izabrati jednu (The Odd Person Wins Game). Svaka od tih osoba poseduje novčić koji ima dve strane. Izbor osobe se odigrava tako što svaka osoba nezavisno baca svoj novčić. Ukoliko postoji osoba kojoj je novčić pao na drugu stranu u odnosu na preostale osobe, onda se ta osoba izabira. Ukoliko sve osobe imaju isto postavljen novčić, postupak se ponavlja sve dok se ne izabere jedna. Osobe nakon svakog bacanja moraju da znaju da li su izabrane ili ne ili se postupak ponavlja. Koristeći semafore napisati program koji opisuje ponašanje osobe. Nijednoj osobi ne treba davati prednost na osnovu njihovog identifikatora.
Rešenje
Avgust 2021, 2. zadatak
- Ovaj zadatak nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.
Postavka
U svemiru postoji N nebeskih tela koja međusobno interaguju (N Body Gravitational Problem). Koristeći semafore potrebno je rešiti ovaj problem koristeći torbu poslova za dohvatanje posla. Potrebno je realizovati sledeće: Worker (obavlja izračunavanje), Bag (obavlja podelu posla) i Collector (obavlja prikupljanje rezultata).
Rešenje
Dok ovaj zadatak nije rešen, od koristi može biti informacija šta se u zadatku otprilike očekivalo:
- Činjenica da se u zadatku radi o nebeskim telima je potpuno nebitna.
Workerniti vrše neka izračunavanja nad nebeskim telima (može se modelovati nekom metodom npr.izracunaj()).- Parametri ovih izračunavanja (šta se tačno računa) moraju biti preuzeti od
Bagniti. Ovaj model poznat je kao bag of tasks i objašnjen je u knjizi Zaharija Radivojevića Konkurentno i distribuirano programiranje na strani 22. - Na kraju svih izračunavanja
Collectornit ih preuzima. Nakon što ta nit obradi preuzete rezultate, dajeBagniti dodatne parametre izračunavanja koja se opet prosleđujuWorkernitima.
Za sve nedoumice oko postavke ovog zadatka obratiti se Sanji Delčev.
K 2019, 1. zadatak
Postavka
Rešiti problem čitalaca i pisaca (Reader Writers Problem) koristeći semafore. Obezbediti da procesi započinju pristup resursu po redosledu slanja zahteva. Pretpostaviti da u nekom trenutku maksimalno N procesa može uputiti zahtev za pristup resursu.
Rešenje
const int N = 100;
// Један више како бисмо могли да користимо проверу head == tail
// да бисмо видели да ли је листа празна
sem sems[N + 1];
bool isReader[N + 1];
int head = 0;
int tail = 0;
sem mutex;
// count == -1 => писац
int count = 0;
void read();
void write();
void reader() {
mutex.wait();
if (head == tail && count >= 0) {
// Ако је листа празна значи да сигурно немамо писаца у њој
++count;
mutex.signal();
} else {
int index = tail;
tail = (tail + 1) % (N + 1);
isReader[index] = true;
mutex.signal();
sems[index].wait();
}
read();
mutex.wait();
if (--count == 0 && head != tail) {
// Следећи мора да је писац, јер да је читалац листа би била празна
count = -1;
sems[head].signal();
head = (head + 1) % (N + 1);
}
mutex.signal();
}
void writer() {
mutex.wait();
if (head == tail && count == 0) {
// Ако нема читалаца нити писаца и листа је празна, можемо само да прођемо
--count;
mutex.signal();
} else {
int index = tail;
tail = (tail + 1) % (N + 1);
isReader[index] = false;
mutex.signal();
sems[index].wait();
}
write();
mutex.wait();
if (head == tail) {
// Нико више не чека
count = 0;
} else if (isReader[head]) {
// Чекају читаоци иза писца
count = 0;
while (isReader[head] && head != tail) {
++count;
sems[head].signal();
head = (head + 1) % (N + 1);
}
} else {
// Чека писац иза писца
sems[head].signal();
head = (head + 1) % (N + 1);
}
mutex.signal();
}
K1 2018, 1. zadatak
Postavka
Potrebno je uraditi sinhronizaciju na barijeri koja funkcioniše na sledeći način: postoje dva procesa koordinatora za po polovinu radnih procesa (pretpostaviti paran broj radnih procesa) koji treba da se sinhronizuju na barijeri. Pritom, ta dva procesa koordinatora prvo zaključuju kada su svi njihovi procesi stigli do njihovih internih podbarijera i kroz postupak međusobne komunikacije koordinatora utvrđuju kada su svi radni procesi stigli do ekvivalentne jedinstvene barijere. Nakon toga oba procesa koordinatora treba da dozvole radnim procesima da prođu barijeru. Napisati kôd radnih procesa i oba procesa koordinatora.
Rešenje
const int N = ...;
sem arrive[N] = {0};
sem pass[N] = {0};
bool coordinator = false;
sem coordinatorSem = 0;
sem mutex = 1;
void coordinator1() {
for (int i = 0; i < N / 2; i++) arrive[i].wait();
mutex.wait();
if (coordinator) {
coordinator = false;
mutex.signal();
coordinatorSem.signal();
} else {
coordinator = true;
mutex.signal();
coordinatorSem.wait();
}
for (int i = 0; i < N / 2; i++) pass[i].signal();
}
void coordinator2() {
for (int i = N / 2; i < N; i++) arrive[i].wait();
mutex.wait();
if (coordinator) {
coordinator = false;
mutex.signal();
coordinatorSem.signal();
} else {
coordinator = true;
mutex.signal();
coordinatorSem.wait();
}
for (int i = N / 2; i < N; i++) pass[i].signal();
}
void process(int i) {
while (true) {
work();
arrive[i].signal();
pass[i].wait();
}
}
== K1 2018, 2. zadatak ==
Postavka
Negde u Africi postoji dubok kanjon na čijim liticama žive babuni (The Baboons Crossing Problem). Između dve litice kanjona postoji lijana preko koje babuni prelaze reku. Da bi se izbegao sukob između babuna u jednom trenutku na lijani smeju da se nađu samo babuni koji pripadaju jednoj strani kanjona. Takođe, lijana može da izdrži najviše 5 babuna, inače puca. Koristeći semafore napisati program za babune sa obe strane kanjona.
Rešenje
const int N = 5;
int baboons = 0;
int currentSide = 0;
sem waiting[2] = {0};
List<int> list;
sem mutex=0;
// side je 0 ili 1, u zavisnosti sa koje strane kanjona se nalazi
void baboon(int side) {
mutex.wait();
// Uslov list.size() == 0 da ne bi doslo do izgladnjivanja
if (baboons == 0 || (currentSide == side && baboons < N && list.size() == 0)) {
currentSide=side;
baboons++;
mutex.signal();
} else {
list.add(side);
mutex.signal();
waiting[side].wait();
}
cross();
mutex.wait();
baboons--;
if (list.size() > 0) {
// Ako je sledeci zablokiran kretao sa iste strane, moze da krene kada jedan babun predje na drugu stranu
if (list.get(0) == side) {
list.pop(0);
baboons++;
waiting[side].signal();
} else if (baboons == 0) {
// Ako je sledeci zablokiran kretao sa suprotne strane, moze da krene samo kada svi babuni sa prvobitne
// strane predju lijanu, i sa njim mozemo pustiti jos maksimalno 4(N-1) babuna sa iste strane ako su
// se svi zablokirali za redom
currentSide = !side;
while (list.get(0) == (!side) && baboons < N) {
list.pop(0);
baboons++;
waiting[!side].signal();
}
}
}
mutex.signal();
}
K1 2020, 2. zadatak
Postavka
Posmatra se jedan parking. Postoji samo jedna rampa koja služi i za ulaz na parking, i za izlaz sa parkinga, kroz koju može prolaziti samo jedan automobil u jednom trenutku. Na parkingu ima N mesta za parkiranje. Automobili koji ulaze, mogu da uđu, jedan po jedan, ukoliko ima slobodnih mesta. Ukoliko nema slobodnog mesta, proverava se da li ima automobila koji hoće da izađu. Ako nakon izlaska svih automobila koji žele da izađu i ulaska automobila koji su došli pre njega za automobil neće biti mesta, on odlazi u potragu za drugim parkingom. Automobili pri izlasku plaćaju usluge parkinga i izlaze jedan po jedan. Na početku prednost na rampi imaju automobili koji izlaze sa parkinga. Nakon što kroz rampu izađe K uzastopnih automobila, prioritet se menja (dodeljuje se veći prioritet onima koji ulaze). Nakon prolaska K uzastopnih automobila koji ulaze, prioritet se ponovo menja. Ako nema automobila iz smera koji ima prioritet, automobili koji nemaju prioritetni smer smeju da prolaze kroz rampu. Korišćenjem jednog niza od 2N + 1 semafora napraviti metode za traženje dozvola za ulaz i izlaz i obaveštavanje o ulasku i izlasku automobila sa parkinga. Nije dozvoljeno koristiti pomoćne strukture podataka ni dodatne elemente za sinhronizaciju procesa. Automobili ne smeju da se pretiču.
Rešenje
const int N = 100;
const int K = 50;
sem sems[2 * N + 1];
// Број слободних места на паркингу (аутомобили који чекају излаз су ослободили своје место)
int capacity = N;
// Број аутомобила који чекају на улазу
int entering = 0;
// Број аутомобила који чекају на излазу
int exiting = 0;
int enterTail = 0;
int enterHead = 0;
int exitTail = 0;
int exitHead = 0;
// true - излаз, false - улаз
bool priority = true;
int passed = 0;
sem& mutex = sems[2 * N];
bool requestEntrance() {
mutex.wait();
if (capacity - entering <= 0) {
mutex.signal();
return false;
}
++entering;
if (entering == 1 && exiting == 0) {
// Слободан пролаз
mutex.signal();
return true;
}
int semIndex = enterTail;
enterTail = (enterTail + 1) % N;
mutex.signal();
sems[semIndex].wait();
return true;
}
void requestExit() {
mutex.wait();
++capacity;
++exiting;
if (entering == 0 && exiting == 1) {
// Слободан пролаз
mutex.signal();
return;
}
int semIndex = exitTail + N;
exitTail = (exitTail + 1) % N;
mutex.signal();
sems[semIndex].wait();
}
void entered() {
mutex.wait();
--entering;
--capacity;
signal();
mutex.signal();
}
void exited() {
mutex.wait();
--exiting;
signal();
mutex.signal();
}
void signal() {
int semIndex = -1;
bool hasCapacity = (capacity - exiting) < N;
bool signalExit = (exiting > 0) && (priority || !hasCapacity || entering == 0);
bool signalEnter = (entering > 0 && hasCapacity) && (!priority || exiting == 0);
if (signalExit) {
semIndex = exitHead + N;
exitHead = (exitHead + 1) % N;
} else if (signalEnter) {
semIndex = enterHead;
enterHead = (enterHead + 1) % N;
}
if (semIndex >= 0) {
if (priority != signalExit) {
// Ако сада није изашао аутомобил из реда који је имао приоритет,
// ресетује се бројач узастопних аутомобила
passed = 0;
} else {
++passed;
}
if (passed == K) {
passed = 0;
priority = !priority;
}
sems[semIndex].signal();
}
}
void car() {
while (true) {
if (requestEntrance()) {
entered();
// ...
requestExit();
// pay();
exited();
}
}
}
K1 2022, 2. zadatak
Postavka
Posmatra se zabavni park sa N autića koji mogu da prime po jednu osobu (Bumper Cars Problem). M osoba se šeta po parku i može da odluči da se provoza. Osoba koja želi da se vozi staje u red i čeka slobodni auto. Kada se oslobodi auto i prethodni vozač napusti auto prva osoba iz reda dobija priliku da vozi auto i da se sudara sa drugim autima. Nakon nekog vremena osoba završava vožnju, vraća auto na odgovarajuće mesto, napušta auto i odlazi da se šeta po parku. Osoba može više puta da dođe da se vozi. Ukoliko postoji više auta, osoba bira onaj koji je najduže čekao na vožnju. Ukoliko trenutno nema osoba koje žele da se voze auto staje u red i čeka da dođe osoba. Koristeći semafore napisati program koji rešava ovaj problem.
Rešenje
const int N = 100;
const int M = 100;
// Комуникација између аутомобила и особа
sem carSems[N];
sem peopleSems[M];
// Међусобно искључивање при приступу глобалном стању
sem mutex = 1;
// Подаци заштићени mutex-ом:
list<int> freeCars;
list<int> freePeople;
int mutexId;
void car(int carId) {
int personId;
while (true) {
mutex.wait();
if (freePeople.size() > 0) {
personId = freePeople.front();
freePeople.pop_front();
mutexId = carId;
peopleSems[personId].signal();
// Нема ослобађања mutex, чекамо да особа прочита mutexId
carSems[carId].wait();
} else {
freeCars.push_back(carId);
mutex.signal();
carSems[carId].wait();
personId = mutexId;
// Ослобађамо mutex који је особа закључала
mutex.signal();
// Обавештавамо особу да смо прочитали mutexId
peopleSems[personId].signal();
}
// Особа контролише ауто, чекамо да нас особа обавести кад заврши
carSems[carId].wait();
// Враћени смо назад
}
}
void person(int personId) {
int carId;
while (true) {
// Шетамо
mutex.wait();
if (freeCars.size() > 0) {
carId = freeCars.front();
freeCars.pop_front();
mutexId = personId;
carSems[carId].signal();
// Нема ослобађања mutex, чекамо да аутомобил прочита mutexId
peopleSems[personId].wait();
} else {
freePeople.push_back(personId);
mutex.signal();
peopleSems[personId].wait();
carId = mutexId;
// Ослобађамо mutex који је аутомобил закључао
mutex.signal();
// Обавештавамо аутомобил да смо прочитали mutexId
carSems[carId].signal();
}
// Возимо и на крају обавестимо аутомобил да смо завршили
carSems[carId].signal();
// Настављамо шетњу
}
}
Februar 2020, 1. zadatak
Postavka
Koristeći raspodeljene binarne semafore rešiti problem proizvođača i potrošača (Producer – Consumer Problem).
Rešenje
Rešenje sa baferom za M proizvođača i N potrošača
#include <semaphore>
class ProducerConsumer {
private:
const int CAPACITY=...;
int writeCursor=0;
int readCursor = 0;
int data[CAPACITY]; //Примера ради је узето да произвођач прави податке типа int
std::binary_semaphore space_available(CAPACITY);
std::binary_semaphore item_available(0);
std::binary_semaphore mutexProducer(1);
std::binary_semaphore mutexConsumer(1);
public:
void producer() {
spaceAvailable.acquire(); //у std::binary_semaphore ово је еквивалент операцији wait
mutexProducer.acquire();
data[writeCursor] = this.produce(); //Нека метода која би враћала неки број
writeCursor = (writeCursor + 1) % CAPACITY;
mutexProducer.release();
item_available.release(); //у std::binary_semaphore ово је еквивалент операцији signal
}
int consumer() {
item_available.acquire();
mutexConsumer.acquire()
int i = data[readCursor];
readCursor = (readCursor + 1) % CAPACITY;
item_available.release();
mutexConsumer.release()
return i;
}
}
Februar 2022, 2. zadatak
Postavka
Račun u banci može da deli više korisnika (The Savings Account Problem). Svaki korisnik može da uplaćuje i podiže novac sa računa pod uslovom da saldo na tom računu nikada ne bude negativan. Ukoliko na računu nema dovoljno novca, korisnik treba da čeka dok neko drugi ne uplati novac na taj račun. Nijedan korisnik ne može biti isplaćen dok god svi koji su pre njega tražili isplatu ne dobiju svoj novac. Rešiti problem koristeći semafore (ne treba proveravati da li korisnik sme da pristupi nekom računu; u banci može postojati više računa).
Rešenje
U rešenju se smatra da svaki korisnik radi u samo jednoj niti, da svaka nit ima svoj identifikator, i da se taj identifikator prosleđuje funkcijama za uplaćivanje i podizanje novca.
#include "common.h"
const int NumOfAccounts = 100;
const int NumOfUsers = 100;
struct Account {
int balance;
int maxTicket = 0;
int waitUntilAbove = 0;
sem mutex = 1;
sem balanceSem = 0;
sem users[NumOfUsers] = {1, 0, 0, ...};
};
Account accounts[NumOfAccounts];
void deposit(int amount, int accountId) {
Account& account = accounts[accountId];
account.mutex.wait();
// Уплаћујемо паре на рачун.
account.balance += amount;
// Уколико је неки други корисник захтевао исплату, проверавамо да ли може бити задовољена.
if (account.waitUntilAbove != 0 && account.balance >= account.waitUntilAbove) {
// Уколико јесте, на нама је да ажурирамо стање.
account.balance -= account.waitUntilAbove;
account.waitUntilAbove = 0;
account.balanceSem.signal();
}
account.mutex.signal();
}
void withdraw(int amount, int accountId) {
Account& account = accounts[accountId];
// Дохватамо наше место у реду чекања за исплату.
account.mutex.wait();
// Рачуна се на то да неће један корисник истовремено радити две исплате са истог налога.
int ticket = (account.maxTicket++) % NumOfUsers;
account.mutex.signal();
// Чекамо да нас претходни корисник у реду чекања прозове.
account.users[ticket].wait();
// Чекамо да се ослободи довољно средстава пре исплате.
account.mutex.wait();
if (account.balance >= amount) {
// Уколико већ има довољно средстава, ажурирамо стање.
account.balance -= amount;
account.mutex.signal();
} else {
// Уколико нема, остављамо следећем кориснику који уплаћује да ажурира стање и обавести нас.
account.waitUntilAbove = amount;
account.mutex.signal();
account.balanceSem.wait();
}
// Јави следећем кориснику да може да изврши исплату.
account.users[(ticket + 1) % NumOfUsers].signal();
}