КДП/Семафори
Семафори су концепт из конкурентног програмирања из првог блока наставе и долазе на првом колоквијуму за СИ и колоквијуму за РТИ.
Јануар 2020, 2. задатак
Поставка
Користећи семафоре написати програм који решава проблем путовања лифтом. Путник позива лифт са произвољног спрата. Када лифт стигне на неки спрат сви путници који су изразили жељу да сиђу на том спрату обавезно изађу. Након изласка путника сви путници који су чекали на улазак уђу у лифт и кажу на који спрат желе да пређу. Тек када се сви изјасне лифт прелази даље. Лифт редом обилази спратове и стаје само на оне где има путника који улазе или излазе. Може се претпоставити да постоји N спратова.
Решење
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();
// Настављамо на следећи спрат
}
}
Јануар 2023, 1. задатак
- Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.
Поставка
Имплементирати и објасните основну разлику и разлоге за постојање те разлике између имплементација бафера коначног капацитета (bounded buffer) за случајеве 1 произвођач и 1 потрошач, као и M произвођача и N потрошача помоћу семафора. У складу са објашњењем, прикажите разлике и за случајеве M произвођача и 1 потрошач, као и 1 произвођач и N потрошача.
Решење
Јун 2020, 2. задатак
Поставка
Посматра се острво на коме људи могу да разгледају музеј о диносаурусима и парк за живим примерцима (The Jurassic Park Problem). У парку постоји N безбедних возила која могу да приме по једног путника. У парк може долазити произвољан број посетилаца. На почетку посетилац слободно разгледа музеј са експонатима. Када заврши разгледање, прелази на део са живим диносаурусима, тако што сачека да се појави прво сигурно возило које ће га провести кроз парк. Када наиђе слободно возило, посетилац прелази на вожњу по парку која траје неко време. На крају вожње посетилац напушта парк (може некад да се врати), а возило се враћа да прими следећег посетиоца. Уколико су сва возила заузета, посетилац који жели да иде у обилазак чека слободно возило. Уколико постоји слободно возило, али не и посетилац који тренутно чека да уђе, онда возило чека. Користећи семафоре написати програме за посетиоце и возила, као и код за иницијализацију.
Решење
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();
// Посетилац је напустио парк и можда се некад врати
}
}
Јун 2022, 2. задатак
- Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.
Поставка
Постоје три особе међу којима треба изабрати једну (The Odd Person Wins Game). Свака од тих особа поседује новчић који има две стране. Избор особе се одиграва тако што свака особа независно баца свој новчић. Уколико постоји особа којој је новчић пао на другу страну у односу на преостале особе, онда се та особа изабира. Уколико све особе имају исто постављен новчић, поступак се понавља све док се не изабере једна. Особе након сваког бацања морају да знају да ли су изабране или не или се поступак понавља. Користећи семафоре написати програм који описује понашање особе. Ниједној особи не треба давати предност на основу њиховог идентификатора.
Решење
Август 2021, 2. задатак
- Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.
Поставка
У свемиру постоји N небеских тела која међусобно интерагују (N Body Gravitational Problem). Користећи семафоре потребно је решити овај проблем користећи торбу послова за дохватање посла. Потребно је реализовати следеће: Worker (обавља израчунавање), Bag (обавља поделу посла) и Collector (обавља прикупљање резултата).
Решење
Док овај задатак није решен, од користи може бити информација шта се у задатку отприлике очекивало:
- Чињеница да се у задатку ради о небеским телима је потпуно небитна.
Workerнити врше нека израчунавања над небеским телима (може се моделовати неком методом нпр.izracunaj()).- Параметри ових израчунавања (шта се тачно рачуна) морају бити преузети од
Bagнити. Овај модел познат је као bag of tasks и објашњен је у књизи Захарија Радивојевића Конкурентно и дистрибуирано програмирање на страни 22. - На крају свих израчунавања
Collectorнит их преузима. Након што та нит обради преузете резултате, дајеBagнити додатне параметре израчунавања која се опет прослеђујуWorkerнитима.
За све недоумице око поставке овог задатка обратити се Сањи Делчев.
К 2019, 1. задатак
Поставка
Решити проблем читалаца и писаца (Reader Writers Problem) користећи семафоре. Обезбедити да процеси започињу приступ ресурсу по редоследу слања захтева. Претпоставити да у неком тренутку максимално N процеса може упутити захтев за приступ ресурсу.
Решење
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();
}
К1 2018, 1. задатак
Поставка
Потребно је урадити синхронизацију на баријери која функционише на следећи начин: постоје два процеса координатора за по половину радних процеса (претпоставити паран број радних процеса) који треба да се синхронизују на баријери. Притом, та два процеса координатора прво закључују када су сви њихови процеси стигли до њихових интерних подбаријера и кроз поступак међусобне комуникације координатора утврђују када су сви радни процеси стигли до еквивалентне јединствене баријере. Након тога оба процеса координатора треба да дозволе радним процесима да прођу баријеру. Написати кôд радних процеса и оба процеса координатора.
Решење
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();
}
}
== К1 2018, 2. задатак ==
Поставка
Негде у Африци постоји дубок кањон на чијим литицама живе бабуни (The Baboons Crossing Problem). Између две литице кањона постоји лијана преко које бабуни прелазе реку. Да би се избегао сукоб између бабуна у једном тренутку на лијани смеју да се нађу само бабуни који припадају једној страни кањона. Такође, лијана може да издржи највише 5 бабуна, иначе пуца. Користећи семафоре написати програм за бабуне са обе стране кањона.
Решење
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();
}
К1 2020, 2. задатак
Поставка
Посматра се један паркинг. Постоји само једна рампа која служи и за улаз на паркинг, и за излаз са паркинга, кроз коју може пролазити само један аутомобил у једном тренутку. На паркингу има N места за паркирање. Аутомобили који улазе, могу да уђу, један по један, уколико има слободних места. Уколико нема слободног места, проверава се да ли има аутомобила који хоће да изађу. Ако након изласка свих аутомобила који желе да изађу и уласка аутомобила који су дошли пре њега за аутомобил неће бити места, он одлази у потрагу за другим паркингом. Аутомобили при изласку плаћају услуге паркинга и излазе један по један. На почетку предност на рампи имају аутомобили који излазе са паркинга. Након што кроз рампу изађе K узастопних аутомобила, приоритет се мења (додељује се већи приоритет онима који улазе). Након проласка K узастопних аутомобила који улазе, приоритет се поново мења. Ако нема аутомобила из смера који има приоритет, аутомобили који немају приоритетни смер смеју да пролазе кроз рампу. Коришћењем једног низа од 2N + 1 семафора направити методе за тражење дозвола за улаз и излаз и обавештавање о уласку и изласку аутомобила са паркинга. Није дозвољено користити помоћне структуре података ни додатне елементе за синхронизацију процеса. Аутомобили не смеју да се претичу.
Решење
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();
}
}
}
К1 2022, 2. задатак
Поставка
Посматра се забавни парк са N аутића који могу да приме по једну особу (Bumper Cars Problem). M особа се шета по парку и може да одлучи да се провоза. Особа која жели да се вози стаје у ред и чека слободни ауто. Када се ослободи ауто и претходни возач напусти ауто прва особа из реда добија прилику да вози ауто и да се судара са другим аутима. Након неког времена особа завршава вожњу, враћа ауто на одговарајуће место, напушта ауто и одлази да се шета по парку. Особа може више пута да дође да се вози. Уколико постоји више аута, особа бира онај који је најдуже чекао на вожњу. Уколико тренутно нема особа које желе да се возе ауто стаје у ред и чека да дође особа. Користећи семафоре написати програм који решава овај проблем.
Решење
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();
// Настављамо шетњу
}
}
Фебруар 2020, 1. задатак
Поставка
Користећи расподељене бинарне семафоре решити проблем произвођача и потрошача (Producer – Consumer Problem).
Решење
Решење са бафером за M произвођача и N потрошача
#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;
}
}
Фебруар 2022, 2. задатак
Поставка
Рачун у банци може да дели више корисника (The Savings Account Problem). Сваки корисник може да уплаћује и подиже новац са рачуна под условом да салдо на том рачуну никада не буде негативан. Уколико на рачуну нема довољно новца, корисник треба да чека док неко други не уплати новац на тај рачун. Ниједан корисник не може бити исплаћен док год сви који су пре њега тражили исплату не добију свој новац. Решити проблем користећи семафоре (не треба проверавати да ли корисник сме да приступи неком рачуну; у банци може постојати више рачуна).
Решење
У решењу се сматра да сваки корисник ради у само једној нити, да свака нит има свој идентификатор, и да се тај идентификатор прослеђује функцијама за уплаћивање и подизање новца.
#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();
}