---
# System prepended metadata

title: L7 - zarys teoretyczny (bez wyprowadzenia wzorów)

---

# L7 - zarys teoretyczny (bez wyprowadzenia wzorów)

* **Safe boolean MRSW**
![](https://i.imgur.com/j3kjdpQ.png)
nic tu się nie dzieje, zwykła tablica bitów srsw, każdy wątek własny indeks
 
* **Regular boolean MRSW**
![](https://i.imgur.com/mcM9t35.png)
zmieniamy value tylko wtedy, gdy jest różne od ostatniego

* **Regular M-valued MRSW**
![](https://i.imgur.com/rmsmTuk.png)

* **Atomic SRSW**
write(x) polega na ustawieniu i-tego bitu i wyzerowaniu wszystkich mniejszych
read() szuka pierwszego zapalonego bitu i zwraca jego indeks
![](https://i.imgur.com/zRipNsl.png)
![](https://i.imgur.com/NyQ5kFQ.png)
ThreadLocal własny, osobny obiekt dla każdego wątku
stamp to para wartośc-czas
zapisujemy stampa wykonanego przez ostatniego write'a (obiekt lastStamp)
jak wątek odczytuje, to bierze wartość na podstawie maxa ze swojego ostatnio przeczytanego stampa i ogólnego stampa, ale nie aktualizuje ogólnego stampa, tylko swoją ostatnio przeczytaną wartość
jak robi write to aktualizuje ogólnego stampa

* **Atomic MRSW** (plansza odjeżdża XD)

![](https://i.imgur.com/0MNCMLZ.png)
mamy 2d tablice srsw
- każdy wątek trzyma swój ostatni czas zapisu w lastStamp (lokalnie)
- read() najpierw liczy zwracane value na podstawie największego stampa (czasu) z wiersza, potem zapisuje w kolumnie (poza sobą) value, a na końcu zwraca value
- write() aktualizuje swój ostatni czas zapisu, a potem zapisuje po przekątnej nowe value
- rozwiązuje to problem w którym np write zapisywałby a[0], a następnie jest uśpiony i nie zapisze od razu a[1...n-1], a następnie wątek 0 przeczytałby nową wartość, a wątki 1...n-1 przeczytałyby starą wartość (tak nie może być, dalsze read() nie mogą przeczytać innej wartości niż poprzedni read() w trakcie trwania write())
- dlatego read() zanim zwróci wartość to najpierw aktualizuje swoją zwracaną wartość, a potem aktualizuje w kolumnie value dla innych readów, dzięki temu unikamy problemu opisanego punkt wyżej

* **Atomic MRMW** (plansza odjechała)
![](https://i.imgur.com/5jAXQ9K.png)
- bazujemy na tablicy MRSW, każdy wątek ma swój indeks
- read() czyta całą tablicę i zwraca najświezszy rezultat
- write() najpierw sprawdza maksymalny czas w całej tablicy, a potem aktualizuje na sowim indeksie nową wartość z czasem +1

* **Migawka (snapshot) obstruction-free**
- chcemy odczytać wiele wartości, ale tak, żeby w trakcie czytania żadna z nich się nie zmieniła
- bazujemy na tablicy MRSW (kazdy wątek ma swój indeks)
- pomysł polega na kręceniu się w kółko, podwójnym odczycie, i jeśli odczyty są takie same no to nic nie mogło się zmienić i sukces, wpp. kręć się dalej
![](https://i.imgur.com/OmB5QAw.png)
* **Migawka (snapshot) wait-free**
- update zapisuje sobie ostatni stan całej tablicy
- jeśli w trakcie trwania scan() jakiś wątek zrobił update() dwukrotnie, to możemy skorzystać z jego zapisu ostatniego stanu
![](https://i.imgur.com/jowd8ow.png)
![](https://i.imgur.com/ERLLpXR.png)

* ogólny konsensus dla N wątków na podstawie N binarnych konsensusów
każdy wątek próbuje wygrać konsensus dla swojego bitu i ustawić innym że przegrali