КДП/Штафетна палица
Техника штафетне палице је концепт конкуретног програмирања из првог блока наставе и долази на првом колоквијуму за СИ и колоквијуму за РТИ.
Јануар 2021, 1. задатак
- Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.
Поставка
Потребно је реализовати тајмер користећи приватне семафоре и технику предаје штафетне палице. Тајмер има две методе, прва је метода wakeme која омогућава да се дата нит блокирана n јединица времена (ово је аргумент), а друга је метода tick која означава да је истекла једна јединица времена.
Решење
const N = ...; // максималан бpој нити
class Timer {
sem mutex = 1;
sem privSem[N];
int timeLeft[N];
bool sleeping[N];
void wakeme(int id, int n) {
wait(mutex);
timeLeft[id] = n; sleeping[id] = true;
signal(mutex);
wait(privSem[id]); // блокира се на свом семафору
}
void tick(){
wait(mutex);
for(int i = 0 to N - 1){
if(sleeping[i]) {
timeLeft[i]--;
if(timeLeft[i] == 0) {
sleeping[i] = false;
signal(privSem[i]);
}
}
}
signal(mutex);
}
}
Јануар 2022, 1. задатак
Поставка
Разматра се проблем синхронизације на баријери (Barrier Synchronization). Синхронизациона баријера омогућава нитима да на њој сачекају док тачно N нити не достигне одређену тачку у извршавању пре него што било која од тих нити не настави са својим извршавањем. Користећи расподељене бинарне семафоре и технику предаје штафетне палице решити овај проблем. Омогућити да се иста баријера може користити већи број пута.
Решење
sem arrived = 1;
sem continued = 0;
int blocked = 0;
const int N = 100;
void work1();
void work2();
void worker() {
while (true) {
work1();
arrived.wait();
blocked++;
if (blocked != N) {
arrived.signal();
continued.wait();
}
blocked--;
if (blocked > 0) {
continued.signal();
} else {
arrived.signal();
}
work2();
}
}
Јул 2020, 1. задатак
- Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.
Поставка
Користећи расподељене бинарне семафоре и технику предаје штафетне палице решити проблем читалаца и писаца (Readers - Writers Problem).
Решење
Јул-1 2025, 1. задатак
- Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.
Поставка
Потребно је реализовати семафор који поред стандардних атомских операција signal() и wait() има и атомске операције signal(n) и wait(n) које интерну семафорску променљиву атомски увећава односно умањује за n уколико је то могуће, уколико није чека док не буде било могуће. Потребно је решити проблем користећи расподељене бинарне семафоре и технику предаје штафетне палице. Процес који је раније упутио wait захтев треба раније да обави своју операцију. Претпоставити да у било ком тренутку максимално N процеса може упутити захтев за приступ семафору.
Решење
Фебруар 2021, 2. задатак
- Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.
Поставка
Посматра се семафор за регулацију саобраћаја на улици са једним пешачким прелазом. Када пешак стигне до пешачког прелаза, уколико је светло за пешаке зелено, он прелази улицу. Уколико је у моменту његовог доласка светло за пешаке црвено, он чека да се укључи зелено светло. Зелено светло за пешаке се укључује или након К секунди од појаве првог пешака који је затекао црвено светло, или након проласка C аутомобила од последњег активног зеленог светла за пешаке. Зелено светло за пешаке трајања G секунди се пали само уколико је испуњен неки од наведених услова и барем један пешак чека. Користећи расподељене бинарне семафоре и технику предаје штафетне палице написати програме за пешаке, аутомобиле и семафор за регулацију саобраћаја. Доступна је функција system_time() која враћа тренутно време система. Учесницима треба неко време да пређу улицу.