KDP/Štafetna palica
Tehnika štafetne palice je koncept konkuretnog programiranja iz prvog bloka nastave i dolazi na prvom kolokvijumu za SI i kolokvijumu za RTI.
Januar 2021, 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
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);
}
}
Januar 2022, 1. zadatak
Postavka
Razmatra se problem sinhronizacije na barijeri (Barrier Synchronization). Sinhronizaciona barijera omogućava nitima da na njoj sačekaju dok tačno N niti ne dostigne određenu tačku u izvršavanju pre nego što bilo koja od tih niti ne nastavi sa svojim izvršavanjem. Koristeći raspodeljene binarne semafore i tehniku predaje štafetne palice rešiti ovaj problem. Omogućiti da se ista barijera može koristiti veći broj puta.
Rešenje
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();
}
}
Jul 2020, 1. zadatak
- Ovaj zadatak nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.
Postavka
Koristeći raspodeljene binarne semafore i tehniku predaje štafetne palice rešiti problem čitalaca i pisaca (Readers - Writers Problem).
Rešenje
Jul-1 2025, 1. zadatak
- Ovaj zadatak nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.
Postavka
Potrebno je realizovati semafor koji pored standardnih atomskih operacija signal() i wait() ima i atomske operacije signal(n) i wait(n) koje internu semaforsku promenljivu atomski uvećava odnosno umanjuje za n ukoliko je to moguće, ukoliko nije čeka dok ne bude bilo moguće. Potrebno je rešiti problem koristeći raspodeljene binarne semafore i tehniku predaje štafetne palice. Proces koji je ranije uputio wait zahtev treba ranije da obavi svoju operaciju. Pretpostaviti da u bilo kom trenutku maksimalno N procesa može uputiti zahtev za pristup semaforu.
Rešenje
Februar 2021, 2. zadatak
- Ovaj zadatak nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.
Postavka
Posmatra se semafor za regulaciju saobraćaja na ulici sa jednim pešačkim prelazom. Kada pešak stigne do pešačkog prelaza, ukoliko je svetlo za pešake zeleno, on prelazi ulicu. Ukoliko je u momentu njegovog dolaska svetlo za pešake crveno, on čeka da se uključi zeleno svetlo. Zeleno svetlo za pešake se uključuje ili nakon K sekundi od pojave prvog pešaka koji je zatekao crveno svetlo, ili nakon prolaska C automobila od poslednjeg aktivnog zelenog svetla za pešake. Zeleno svetlo za pešake trajanja G sekundi se pali samo ukoliko je ispunjen neki od navedenih uslova i barem jedan pešak čeka. Koristeći raspodeljene binarne semafore i tehniku predaje štafetne palice napisati programe za pešake, automobile i semafor za regulaciju saobraćaja. Dostupna je funkcija system_time() koja vraća trenutno vreme sistema. Učesnicima treba neko vreme da pređu ulicu.