KDP/Sinhronizacioni algoritmi

Sinhronizacioni algoritmi su oblast konkuretnog programiranja iz prvog bloka nastave i dolaze na prvom kolokvijumu za SI i kolokvijumu za RTI.

Jul 2021, 1. zadatak

Debug: KDP/Jul 2021 1. zadatak

Postavka

Kod Tie breaker algoritma za n procesa se dogodio sledeći slučaj – prilikom izvršavanja koda za ulazak u kritičnu sekciju, svih n procesa su ušli u stanje 1 i nijedan još nije ušao u stanje 2. Odgovoriti na sledeća pitanja i obrazložiti odgovor:

1. Da li proces koji je prvi ušao u stanje 1 prvi ulazi u stanje 2?
2. Da li proces koji je prvi ušao u stanje n-2 prvi ulazi u kritičnu sekciju?
3. Da li proces koji je poslednji ušao u stanje 1 može da bude treći koji ulazi u stanje 2?
4. Da li proces koji je poslednji ušao u stanje 1 može da bude prvi koji ulazi u kritičnu sekciju?

Rešenje

1. U opštem slučaju, ne mora da znači da će proces koji je prvi ušao u stanje 1 prvi ući i u stanje 2. Pošto se u tom trenutku svi procesi nalaze u stanju 1, bilo koji proces koji nije poslednji stigao u stanje 1 će moći da prvi uđe u stanje 2. Specijalno, u slučaju kada je $n = 2$, proces koji je prvi ušao u stanje 1 će garantovano prvi ući u stanje 2.
2. U prvom stanju mogu da se nađu $n$ procesa, u drugom stanju $n-1$ procesa... tom logikom u stanju $n-2$ mogu da se nađu 3 procesa istovremeno. Jedan od ta tri procesa će poslednji ući i neće moći da napreduje, dok će ostala dva moći da napreduju i ne garantuje se koji od ta dva procesa će prvi napredovati.
3. Proces koji je poslednji ušao u stanje 1 će biti poslednji koji će iz njega izaći. Moguće je da on bude treći koji ulazi u stanje 2 ukoliko je $n = 3$, u suprotnom ne mora da znači.
4. Proces koji je poslednji ušao u stanje 1 je poslednji koji ulazi u kritičnu sekciju. Da bi takođe bio i prvi, moralo bi da važi $n = 1$ a to nema smisla.

Jun 2020, 1. zadatak

Debug: KDP/Jun 2020 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;
        /* некритична секција */
    }
}

Jun 2022, 1. zadatak

Debug: KDP/Jun 2022 1. zadatak

Ovaj zadatak nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.

Postavka

Objasnite šta je At-Most-Once-Property. Objasnite zašto, kada je ispunjena ta osobina, kritična referenca ima osobine atomske akcije. Dati dva primera u kojima su po dva procesa.

K1 2020, 1. zadatak

Debug: KDP/K1 2020 1. zadatak

Postavka

Napisati i objasnite^[sic] CLH algoritam za kritičnu sekciju (coarse grain). Realizovati (fine grain) verziju algoritma ukoliko bi na datom procesoru postojala operacija SWAP koja bi nedeljivo obavljala zamenu vrednosti dva operanda (SWAP(var1, var2): < temp = var1; var1 = var2; var2 = temp; >). Objasniti zašto je to pravična (fair) kritična sekcija.

Rešenje

CLH algoritam ulančava procese koji žele da uđu u kritičnu sekciju u neku vrstu ulančane liste, tako da svaki proverava da li je onaj pre njega i dalje zaključan i u trenutku kada više ne bude zaključan ulazi u kritičnu sekciju.

Node* tail = nullptr;

void worker() {
    while (true) {
        Node* node = new Node();
        node->locked = true;
        < prev = tail; tail = node; >
        < await (prev == nullptr || !prev->locked); >
        // Критична секција
        node->locked = false;
        // Некритична секција
    }
}

Pošto je prev ovde lokalna promenljiva i tu nema kritične reference, await se može zameniti običnom petljom. Sa druge strane, za atomsku akciju prev = tail; tail = node; potrebna nam je pomenuta SWAP instrukcija:

Node* tail = nullptr;

void worker() {
    while (true) {
        Node* node = new Node();
        node->locked = true;
        Node* prev = node;
        SWAP(prev, tail);
        while (prev != nullptr && prev->locked) skip();
        // Критична секција
        node->locked = false;
        // Некритична секција
    }
}

Ova kritična sekcija je pravična jer će prvi proces koji uradi zamenu (izvrši SWAP instrukciju) biti prvi koji će ući u kritičnu sekciju.

K1 2022, 1. zadatak

Debug: KDP/K1 2022 1. zadatak

Postavka

Napisati i objasnite^[sic] Andersenov algoritam za kritičnu sekciju (coarse grain). Realizovati (fine grain) verziju algoritma ukoliko bi na datom procesoru umest FA postojala operacija Compare-And-Swap koja bi nedeljivo obavljala (CAS(a, b, c) : < if (a == c) { c = b; return true; } else { a = c; return false; } >).

Rešenje

Coarse-grain:

const int N = 100;
int slot = 0;
bool slots[N];

void worker(int id) {
    while (true) {
        < int myslot = slot; slot = slot % N + 1; >
        < await (slots[myslot]); >
        // Критична секција
        < slots[myslot] = false;
        slots[myslot % N + 1] = true; >
        // Некритична секција
    }
}

Fine-grain:

const int N = 100;
int slot = 0;
bool slots[N];

void worker(int id) {
    while (true) {
        int myslot = slot;
        while (!CAS(myslot, myslot % N + 1, slot)) skip();
        while (!slots[myslot]) skip();
        // Критична секција
        slots[myslot] = false;
        slots[myslot % N + 1] = true;
        // Некритична секција
    }
}

Septembar 2023, 1. zadatak

Debug: KDP/Septembar 2023 1. zadatak

Postavka

Napisati i objasniti CLH algoritam za kritičnu sekciju (coarse grain). Realizovati (fine grain) verziju algoritma ukoliko bi na datom procesoru postojala operacija SWAP koja bi nedeljivo obavljala zamenu verdnosti dva operanda (SWAP(var1, var2): <temp=var1; var1=var2; var2=temp;>). Objasniti zašto je to pravična kritična sekcija.

Rešenje

CLH algoritam procese ulančava u ulančanu listu po redosledu kojim dolaze. Samim tim ta lista se ponaša kao red i time je ovaj algoritam pravičan jer koristi FIFO princip. Coarse-grain rešenje:

struct Node {
    bool locked;
    Node() {
        locked = true;
    }
};

Node* tail = nullptr;

void process() {
    while (true) {
        Node* new_node = new Node();
        Node* prev;
        < prev = tail; tail = new_node; >
        < await(tail == nullptr || !prev->locked); >
        /* критична секција */
        new_node->locked=false;
        /* некритична секција */
    }
}

Fine-grain rešenje: Pošto su prev i new_node lokalni pokazivači, možemo da ih usmerimo na novokreirani čvor. Zatim se nedeljivo poziva funkcija SWAP koja će nedeljivo zameniti vrednost prev i tail pokazivača.

struct Node {
    bool locked;
    Node() {
        locked = true;
    }
};

Node* tail = nullptr;

void process() {
    while (true) {
        Node* new_node = new Node();
        Node* prev = new_node;
        SWAP(prev, tail);
        while(prev!= nullptr && prev->locked) skip();
        /* критична секција */
        new_node->locked=false;
        /* некритична секција */
    }
}

Februar 2021, 1. zadatak

Debug: KDP/Februar 2021 1. zadatak

Postavka

Napisati i objasnite test and test and set rešenje za kritičnu sekciju. Ukoliko bi umesto TS(var) postojala operacija SWAP koja bi nedeljivo obavljala zamenu vrednosti dva operanda (SWAP(var1, var2) : < temp = var1; var1 = var2; var2 = temp; >), da li je moguće napraviti Fine grain rešenje i ako je moguće – napravite ga.

Rešenje

U Test-and-set rešenju pri svakoj proveri deljene promenjive se istovremeno i upisuje u nju a to zahteva sinhronizaciju keš memorija jezgara procesora i značajno okupira magistralu i ne dozvoljavva drugim procesima da je koriste. Radi bolje performanse programa potrebno je što je moguće više smanjiti upise u deljene promenjive.

Test and test and set rešenje radi baš to. Prvo se proces vrti u petlji dok je kritična sekcija zaključana, pa tek onda kad se otključa pokuša da dobije pristup, a ako nije uspeo opet se vrti u petlji dok proces koji je zauzeo kritičnu sekciju pre njega ne oslobodi ključ.

Fine grain rešenje koristeći SWAP(var1, var2) : < temp = var1; var1 = var2; var2 = temp; > bi moglo da se reši na sledeći način:

bool lock = false;
void process(int id) {
	bool initialLock = true; // У lock треба да се недељиво упише true, а ако је брава ослобођена у initialLock ће се уписати false након замене а ко није ослобођена остаће иста вредност
	while (true) {
		while (lock == true) skip;  // врти се lock true, тј. док је брава заузета 
		SWAP(lock, initialLock) //замени вредност браве и initialLock;
		while (initialLock == true) {  
			while (lock == true) skip;  // врти се поново ако ниси успео, tj. ако је неко други заузео критичну секцију 
		}
		//  критична секција
		lock = false;  // ослободи браву 
		// некритична секција
	}
}

Februar 2023, 1. zadatak

Debug: KDP/Februar 2023 1. zadatak

Postavka

Fine grain Ticket algoritam 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, i ako je moguće - napravite ga. Napisati i Coarse grain rešenje.

Rešenje

Coarse-grain rešenje:

int ticket = 0;
int next = 0;

void process() {
    while (true) {
        int myTicket=0;
        < myTicket=ticket++; >
        < await(myTicket==next); >
        /* критична секција */
        next++;
        /* некритична секција */
    }
}

Fine-grain rešenje:

int ticket = 0;
int next = 0;

void process() {
    while (true) {
        int myTicket=0;
        myTicket = addAndGet(ticket, 1) - 1;
        while(myTicket != next) skip();
        /* критична секција */
        next++;
        /* некритична секција */
    }
}

Februar 2024, 1. zadatak

Debug: KDP/Februar 2024 1. zadatak

Ovaj zadatak nije rešen. Pomozite SI Wiki tako što ćete ga rešiti.

Postavka

Napisati i objasniti Test and set rešenje za kritičnu sekciju (coarse grain i fine grain). Dati rešenje za smanjenje invalidacije keš memorija u tom slučaju.