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

_Lokalność czasowa_
Komórki pamięci, które były ostatnio używane będą z wysokim prawdopodobieństwem używane ponownie w niedalekiej przyszłości.

_Lokalność przestrzenna_
Komórki pamięci o pobliskich adresach mają tendencje do bycia używanymi w krótkich odstępach czasu.

_MESI_, czyli każda z linii pamięci podręcznej może byc oznaczona jako
- Modified - dane pamięci podręcznej zostały zmienione, muszą zostać zapisane do pamięci operacyjnej,
- Exclusive - dane niemodyfikowane, jedyna kopia w jakiejkolwiek pamięci podręcznej,
- Shared - dane niemodyfikowane, mogą być też w innej pamięci podręcznej,
- Invalid - zawartość pamięci podręcznej nie jest spójna/zgodna.

## Zamek TAS

## Zamek TTAS

## Anderson Queue Lock

Kolejne komórki z tablicy `flags` będą znajdowały się w tych samych wierszach pamięci, każda zmiana pojedynczej flagi spowoduje zmianę stanu całego wiersza, zatem będzie więcej niepotrzebnego współdzielenia.
Rozwiązaniem jest takie rozmieszczenie flag w tablicy, aby na jedną flagę przypadał jeden wiersz pamięci.

## Exponential backoff

## CLH Lock (pomyśleć o CLH+timeous)


## MCS

Zamek implementuje timeout poprzez metodę `tryLock`, którą może wywołać każdy wątek w bloku try...catch. Metoda przyjmuje jako argument czas, który wątek wywołujący jest w stanie czekać na dostanie zamka. Próba otrzymania zamka jest porzucana jeżeli minie okrelony czas.

W algorytmnie CLH zwykłe porzucenie próby dostania się do zamka spowodowałoby zagłodzenie wątków czekających w kolejce. Z tego powodu porzucone węzły są przejmowane przez kolejne przychodzące wątki.

W strukturze `QNode` przechowujemy wskaźnik pod polem `pred` na inny `QNode`. Pole `pred` jest na początku zawsze `null`, a jeżeli nie zostanie podmienione na strukturę `AVAILABLE` tylko na inną strukturę, to oznacza, że wątek z niepowodzeniem wykonał metodę `tryLock`.

Jeżeli poprzednik (wskazywany przez `tail`) miał wartość `null` lub przechowywał `AVAILABLE` możemy otrzymać zamek. W przeciwnym przypadku wchodzimy w pętlę na ustalony przez nas czas.

W pętli czekamy, aż pole `pred` poprzedniego wątku stanie się `AVAILABLE` - wtedy dostajemy zamek.
Jeżeli zmieni się na inną wartość (poprzednik porzucił próbę dostania się do zamka) zmieniamy naszego poprzednika na tego, który jest wskazywany przez `pred`.

Jeżeli minie nasz czas musimy ustawić `tail` na naszego poprzednika, jeżeli jesteśmy ostatni w kolejce (`tail` wskazuje na nas). W przeciwnym przypadku ustawiamy nasze pole `pred` na naszego poprzednika.