КДП/Синхронизациони алгоритми

Извор: SI Wiki
Пређи на навигацију Пређи на претрагу

Синхронизациони алгоритми су област конкуретног програмирања из првог блока наставе и долазе на првом колоквијуму за СИ и колоквијуму за РТИ.



Јул 2021, 1. задатак

Debug: КДП/Јул 2021 1. задатак

Поставка

Код Tie breaker алгоритма за n процеса се догодио следећи случај – приликом извршавања кода за улазак у критичну секцију, свих n процеса су ушли у стање 1 и ниједан још није ушао у стање 2. Одговорити на следећа питања и образложити одговор:

  1. Да ли процес који је први ушао у стање 1 први улази у стање 2?
  2. Да ли процес који је први ушао у стање n-2 први улази у критичну секцију?
  3. Да ли процес који је последњи ушао у стање 1 може да буде трећи који улази у стање 2?
  4. Да ли процес који је последњи ушао у стање 1 може да буде први који улази у критичну секцију?

Решење

  1. У општем случају, не мора да значи да ће процес који је први ушао у стање 1 први ући и у стање 2. Пошто се у том тренутку сви процеси налазе у стању 1, било који процес који није последњи стигао у стање 1 ће моћи да први уђе у стање 2. Специјално, у случају када је , процес који је први ушао у стање 1 ће гарантовано први ући у стање 2.
  2. У првом стању могу да се нађу процеса, у другом стању процеса... том логиком у стању могу да се нађу 3 процеса истовремено. Један од та три процеса ће последњи ући и неће моћи да напредује, док ће остала два моћи да напредују и не гарантује се који од та два процеса ће први напредовати.
  3. Процес који је последњи ушао у стање 1 ће бити последњи који ће из њега изаћи. Могуће је да он буде трећи који улази у стање 2 уколико је , у супротном не мора да значи.
  4. Процес који је последњи ушао у стање 1 је последњи који улази у критичну секцију. Да би такође био и први, морало би да важи а то нема смисла.

Јун 2020, 1. задатак

Debug: КДП/Јун 2020 1. задатак

Поставка

Андерсенов алгоритам за N процеса реализован помоћу addAndGet операције. Уколико би addAndGet операција имала следећи ефекат: addAndGet(var, incr) : < var = var + incr; return(var); >, да ли је могуће направити Fine grain решење, полазећи од Coarse grain решења (написати га), и ако је могуће – направите га.

Решење

Coarse-grain решење: 

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 решење: 

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

Јун 2022, 1. задатак

Debug: КДП/Јун 2022 1. задатак
Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.

Поставка

Објасните шта је At-Most-Once-Property. Објасните зашто, када је испуњена та особина, критична референца има особине атомске акције. Дати два примера у којима су по два процеса.

Решење

К1 2020, 1. задатак

Debug: КДП/К1 2020 1. задатак

Поставка

Написати и објасните[sic] CLH алгоритам за критичну секцију (coarse grain). Реализовати (fine grain) верзију алгоритма уколико би на датом процесору постојала операција SWAP која би недељиво обављала замену вредности два операнда (SWAP(var1, var2): < temp = var1; var1 = var2; var2 = temp; >). Објаснити зашто је то правична (fair) критична секција.

Решење

CLH алгоритам уланчава процесе који желе да уђу у критичну секцију у неку врсту уланчане листе, тако да сваки проверава да ли је онај пре њега и даље закључан и у тренутку када више не буде закључан улази у критичну секцију. 

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;
        // Некритична секција
    }
}

Пошто је prev овде локална променљива и ту нема критичне референце, await се може заменити обичном петљом. Са друге стране, за атомску акцију prev = tail; tail = node; потребна нам је поменута SWAP инструкција: 

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;
        // Некритична секција
    }
}

Ова критична секција је правична јер ће први процес који уради замену (изврши SWAP инструкцију) бити први који ће ући у критичну секцију.

К1 2022, 1. задатак

Debug: КДП/К1 2022 1. задатак

Поставка

Написати и објасните[sic] Андерсенов алгоритам за критичну секцију (coarse grain). Реализовати (fine grain) верзију алгоритма уколико би на датом процесору умест FA постојала операција Compare-And-Swap која би недељиво обављала (CAS(a, b, c) : < if (a == c) { c = b; return true; } else { a = c; return false; } >).

Решење

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;
        // Некритична секција
    }
}


Септембар 2023, 1. задатак

Debug: КДП/Септембар 2023 1. задатак

Поставка

Написати и објаснити CLH алгоритам за критичну секцију (coarse grain). Реализовати (fine grain) верзију алгоритма уколико би на датом процесору постојала операција SWAP која би недељиво обављала замену вердности два операнда (SWAP(var1, var2): <temp=var1; var1=var2; var2=temp;>). Објаснити зашто је то правична критична секција.

Решење

CLH алгоритам процесе уланчава у уланчану листу по редоследу којим долазе. Самим тим та листа се понаша као ред и тиме је овај алгоритам правичан јер користи FIFO принцип. Coarse-grain решење: 

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 решење: Пошто су prev и new_node локални показивачи, можемо да их усмеримо на новокреирани чвор. Затим се недељиво позива функција SWAP која ће недељиво заменити вредност prev и tail показивача. 

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

Фебруар 2021, 1. задатак

Debug: КДП/Фебруар 2021 1. задатак

Поставка

Написати и објасните test and test and set решење за критичну секцију. Уколико би уместо TS(var) постојала операција SWAP која би недељиво обављала замену вредности два операнда (SWAP(var1, var2) : < temp = var1; var1 = var2; var2 = temp; >), да ли је могуће направити Fine grain решење и ако је могуће – направите га.

Решење

У Test-and-set решењу при свакој провери дељене промењиве се истовремено и уписује у њу а то захтева синхронизацију кеш меморија језгара процесора и значајно окупира магистралу и не дозвољавва другим процесима да је користе. Ради боље перформансе програма потребно је што је могуће више смањити уписе у дељене промењиве.

Test and test and set решење ради баш то. Прво се процес врти у петљи док је критична секција закључана, па тек онда кад се откључа покуша да добије приступ, а ако није успео опет се врти у петљи док процес који је заузео критичну секцију пре њега не ослободи кључ.

Fine grain решење користећи SWAP(var1, var2) : < temp = var1; var1 = var2; var2 = temp; > би могло да се реши на следећи начин: 

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;  // ослободи браву 
		// некритична секција
	}
}

Фебруар 2023, 1. задатак

Debug: КДП/Фебруар 2023 1. задатак

Поставка

Fine grain Ticket алгоритам реализован помоћу addAndGet операције. Уколико би addAndGet операција имала следећи ефекат: addAndGet(var, incr) : < var = var + incr; return(var);, да ли је могуће направити Fine grain решење, полазећи од Coarse grain решења, и ако је могуће - направите га. Написати и Coarse grain решење.

Решење

Coarse-grain решење: 

int ticket = 0;
int next = 0;

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

Fine-grain решење: 

int ticket = 0;
int next = 0;

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

Фебруар 2024, 1. задатак

Debug: КДП/Фебруар 2024 1. задатак

Поставка

Написати и објаснити Test and set решење за критичну секцију (coarse grain и fine grain). Дати решење за смањење инвалидације кеш меморија у том случају.

Решење

Преузето из „https://siwiki.rs/w/index.php?title=КДП/Синхронизациони_алгоритми&oldid=5683”