---
# System prepended metadata

title: PW - Lista 8

---

# PW - Lista 8

# Zadanie 1
![](https://i.imgur.com/UMEXirN.png)


Załóżmy, że mamy nieczekającą implementację protokołu binarnego konsensusu dla trzech wątków, używająca wyłącznie wymienionych wyżej zasobów. Rozważmy punkt krytyczny. Bez utraty ogólności załóżmy, że następna wykonana przez A instrukcja wprowadza nas w stan 0-walentny, a następna wykonana przez B wprowadza nas w stan 1-walentny. Punktem krytycznym może być jedynie sytuacja w której dwa wątki wykonują operację na tym samym obiekcie.

1. 2x read() na obiekcie rejestru MRSW. Nie może być stanem krytycznym.

2. write() i read() na obiekcie rejestru MRSW. Nie może być stanem krytycznym.

![](https://i.imgur.com/p8vMAf9.png)

3. compareAndSet() na obiekcie rejestru RMW. 

    Rozpatrzmy następujący stan krytyczny. Weźmy wątki A i B, oraz rejestr RAB. A i B wykonują operację cAS. Nie może być stanem krytycznym.
    
![](https://i.imgur.com/vzbQ0pH.png)

:::success
# Zadanie 2
![](https://i.imgur.com/789Vopv.png)
:::
```java=
/*W tym kodzie wątek A ma numer 0, B ma 1, C ma 2. Indeksujemy tablice MRSW i r numerami wątków*/
public class Consensus{
    boolean proposed[] = new boolean[3];
    double[] r = new double[3]{-1,-1,-1} /*RAC RAB RBC*/
    public boolean decide(boolean x){
        proposed[ID] = x; /* tablica wartości zaproponowanych 
                       * przez wątki (wartości na wejściu wątków)*/
        double_cAS(r[ID],r[(ID+1)%3],-1,ID) /*tu próbujemy ustawić wartości obydwu rejestów RMW przypisanych do wątku (np RAB i RAC dla wątku A)*/
        if(r[ID].get() != -1) /* (*) */
            return proposed[r[ID].get()];
        else 
            return proposed[r[(ID+1)%3]].get()];
    }
}
```

:::success
# Zadanie 3
:::
![](https://i.imgur.com/xZTfiYo.png)

```java=
public class CASConsensus extends ConsensusProtocol {
   private AtomicInteger r = new AtomicInteger(-1);
       
   public T decide(T value) {
       propose(value);
       r.compareAndSet(-1, threadId);
       return proposed[r.get()];
   }
}
```

Zauważmy, że n wątków może użyć funkcji compareAndSet, dla nich nie ma żadnego ograniczenia, więc konsensus będzie działać prawidłowo. N+1szy wątek nie może jej już wykorzystać ten funkcji. Trzebaby zatem dla niego oraz reszty wątków stworzyć konsensus za pomocą tylko rejestrów atomowych.

Możemy teraz zauważyć, że mamy n wątków, które wykonały compare_and_set i jeden, który nie może tego wykonać. Ta sytuacja jest analogiczna, do próby wykonania konsensusu dla 2 wątków jedynie za pomocą rejestrów atomowych. A jak wiadomo, nie da się tego zrobić.

![](https://i.imgur.com/bAAsr1k.png)
Z perspektywy wątku n+1 stan jest w obu gałęziach taki sam, więc wątek ten zwróci tę samą wartość. Sprzeczność.
![](https://i.imgur.com/jiLC6YU.png)
