###### tags: `prir` `studia`

# Algorytmy na wzajemne wykluczanie

## Algorytm Dekkera

- algorytm wyraża chęć wejścia do sekcji krytycznej
- jeśli dwa algorytmy wyraziły chęć, to sprawdzają, czyja jest kolejność i jeden ustępuje drugiemu

boolean chcep=false, chceq=false;
int czyja_kolej=1

-> PROCES P
loop forever {
    sekcja_lokalna
    chcep=true
    while (chceq) {
        if (czyja_kolej==2) {
            chcep = false
            await czyja_kolej == 1
            chcep = true
        }
    }
    sekcja_krytyczna
    czyja_kolej = 2
    chcep = false
}

-> PROCES Q
loop forever {
    sekcja_lokalna
    chceq=true
    while (chcep) {
        if (czyja_kolej==1) {
            chceq = false
            await czyja_kolej == 2
            chceq = true
        }
    }
    sekcja_krytyczna
    czyja_kolej = 1
    chceq = false
}

## Algorytm Petersona
- procesy wyrażają chęć wejścia do sekcji krytycznej
- procesy zgłaszają, że poprosili o dostęp jako ostatni
- jeżeli dwa procesy wyrażają chęć na wejście do sekcji krytycznej, to przechodzi ten, który nie był ostatni

boolean chcep=false, chceq=false
int kto_ostatni=1

-> PROCES P
sekcja_lokalna
chcep = true
kto_ostatni = 1
await chceq==false or kto_ostatni==2
sekcja_krytyczna
chcep=false

-> PROCES Q
sekcja_lokalna
chceq = true
kto_ostatni = 2
await chcep==false or kto_ostatni==1
sekcja_krytyczna
chceq=false

## Algorytm Dorana-Thomasa
- procesy zgłaszają chęć wejścia do sekcji krytycznej
- ustalona jest kolej
- jeśli jest kolej innego procesu, to odpuszczają i go puszczają pierwszego

boolean chcep=false, chceq=false
int czyja_kolej=1

-> PROCES P
sekcja_lokalna
chcep=true
if (chceq) {
    if(czyja_kolej==2) {
        chcep=false
        await czyja_kolej==1
        chcep=true    
    }
    await chceq==false
}
sekcja_krytyczna
chcep=false
czyja_kolej=2

-> PROCES Q
sekcja_lokalna
chceq=true
if(chcep) {
    if(czyja_kolej==1) {
        chceq=false
        await czyja_kolej==1
        chceq=true
    }
    await chcep==false
}
sekcja_krytyczna
chceq=false
czyja_kolej=1

## Algorytm piekarniany
- proces który chce wejść do sekcji krytycznej pobiera bilet z numerem
- bilet musi mieć wartość większą niż wartości na wczesniej wydanych biletach
- jeśli proces posiada bilet z najmniejszym numerem - może wejść do sekcji krytycznej
- jeżeli zdarzy się, że numery na biletach dwóch procesów beda takie same - pierwszeństwo ma ten z mniejszym identyfikatorem

### dla dwóch procesów

int np=0, nq=0

-> PROCES P
loop forever {
    sekcja_lokalna
    np = nq+1
    await nq == 0 or np <= nq
    sekcja_krytyczna
    np = 0
}

-> PROCES Q
loop forever {
    sekcja_lokalna
    nq = np+1
    await np == 0 or nq <= np
    sekcja_krytyczna
    nq = 0
}

### dla N procesów

int numer[0..N-1] = [0,..,0]

-> PROCES [id]
sekcja lokalna
numer[id] = max(numer)+1
// ta petla uruchomi await czekający, aż będzie kolej
// procesu id badając jego zależności z wszystkimi innymi
for all other processes j {
    await (numer[j]==0)
    or (numer[id] < numer[j])
    or (numer[id] == numer[j] and (id<j))
sekcja_krytyczna
numer[id] = 0
}

### dla N procesów bez atomowych przypisań

boolean wybiera[0..N-1] = [false,..,false]
int numer[0..N-1] = [0,..,0]

-> PROCES [id]
loop forever {
    sekcja_lokalna
    wybiera[id] = true
    numer[id] = max(numer)+1
    wybiera[id] = false
    for all other processes j {
        await wybiera[j] == false
        await (numer[j] == 0)
        or (numer[id] < numer[j])
        or (numer[id] == numer[j] and id < j)
    }
    sekcja_krytyczna
    numer[id] = 0
}

## Algorytm szybki

- algorytm piekarniany wymaga wielu pętli, nawet przy braku rywalizacji
- algorytm jest **szybki**, gdy w przypadku braku rywalizacji, proces może wejść do sekcji krytycznej wykonując w protokole wstępnym i końcowym stałą i niewielką liczbę instrukcji
- żadna z tych instrukcji **nie może być await**

### Szkic takiego algorytmu
- sekcja chroniona jest przz dwie bramki
- w przypadku braku rywalizacji, proces przejdzie przez nie w skończonej liczbie kroków
- w przypadku rywalizacji, tylko jeden proces przejdzie przez obie bramki, pozostałe cofają się przed pierwszą bramkę

int bramka1=-1, bramka2=-1
boolean chce[0..N-1] = [false,..,false]

-> PROCES [id]
loop infinity {
1:    sekcja_lokalna
2:    bramka1=id    chce[id] = true
3:    if (bramka2!=-1) chce[id] = false; goto 2
      bramka2=id
      if (bramka1 != id) {
          chce[id] = false
          for all other processes j {
              await chce[j] == false
          }
          if (bramka2 != id) goto 2
          else chce[id] = true
      }
      sekcja_krytyczna
      bramka2 = -1
      chce[id] = false
}

## Algorytm Ricarta-Agrawali (w systemie rozproszonym)
- poprzednie algorytmy działały na pamięci wspólnej
- algorytm opiera się na pomyśle pobierania biletów
- w systemie rozproszonym nie można ich bezpośrednio porównywać, trzeba je przesłać
- algorytm składa się z dwóch procesów
- główny
- z sekcją lokalną i krytyczną
- z protokołami wstępnym i końcowym
- odbiorca
- przetwarza otrzymane komunikaty

int num=0, maxNum=0
boolean chceSK = false
set<int> wstrzymane

-> GŁOWNY
loop forever {
    sekcja_lokalna
    chceSK = true
    num = maxNum+1
    for all other nodes N:
        send(REQ, N, id, num)
    for all other nodes N:
        await(RESP, N)
    sekcja_krytyczna
    chceSK = false
    foreach j in wstrzymane:
        wstrzymane.remove(j)
        send(RESP, N, id)
}

-> ODBIORCA
int nadawca, reqNum
loop forever {
    receive(REQ, nadawca, reqNum)
    maxNum = max(maxNum, reqNum)
    if !chceSK or reqNum < num
    or (reqNum == num and nadawca < id):
        send(RESP, nadawca, id)
    else:
        wstrzymane.add(nadawca)    
}