Wielowątkowość - zmienne atomowe i nieblokujące algorytmy

Wady blokad

Synchronizacja jest czasami zbyt ciężkim rozwiązaniem np do implementowania licznika.
Dodatkowo mechanizm ten pociąga za sobą niebezpieczeństwo związane z żywotnością a także ogranicza skalowalność i wydajność - np zablokowany proces nie może nic robić w trakcie jak oczekuje na blokadę.
Część struktur danych da się zaimplementować nie korzystając z synchronizacji. Część z nich można zaimplementować za pomocą słowa kluczowego volatile - ale może ono być stosowane jedyne w prostych pojedyńczych operacjach w których poprzedni stan nie wpływa na przyszły, czyli np nie można jej zastosować do liczników które są dość prostym rodzajem stanu.
Rozwiązaniem tego problemu są zmienne atomowe i nieblokujące algorytmy które można dzięki nim zaimplementować.

Sprzętowe wspomaganie wielowątkowości

Blokowanie często można nazwać pesymistycznym a czasami wystarczy porównać czy zmienna którą chcemy ustawić została zmieniona od czasu kiedy ją odczytaliśmy i zmieniliśmy - nazywa się to blokowaniem optymistycznym (używanym także np hibernacie do updatowania danych w bazie danych). Dzisiaj prawie wszystkie procesory posiadają jakąś implementację atomowej operacji odczytu-zapisu. Najpopularniejszą z nich jest compare and swap - CAS.
CAS ma trzy argumenty - V - miejsce w pamięci do zmiany, A - oczekiwana aktualna wartość, B - nowej wartość. CAS atomowo zmieni V na B tylko jeśli aktualna wartość to A w przeciwnym razie nic zmieni w miejscu V.
W takim wypadku jeśli wiele wątków zmienia V to część z nich przegra - ale nie są one blokowane i mogą ponowić swoją operacje, dodatkowo mamy pewność że jeden na pewno wygra a to powoduje że zawsze nastąpi postęp. Właśnie z takich instrukcji korzysta JVM do implementacji zmiennych atomowych.

Zmienne atomowe

Istnieje 12 klas zmiennych atomowych:

• skalary: AtomicLong, AtomicInteger, AtomicBoolean, AtomicReference
• tablice: AtomicLongArray, AtomicIntegerArray, AtomicReferenceArray
• aktualizatory pól: AtomicLongFieldUpdater, AtomicIntegerFieldUpdater...
• złożone zmienne: AtomicStampedReference, AtomicMarkedReference

Zmienne atomowe można traktować jako takie lepsze zmienne volatile. Ich dodatkowym atrybutem jest możliwość zmiany w stosunku do poprzedniego stanu. Tą funkcjonalność na zmiennych volatile można uzyskać korzystając z aktualizatorów pól np klasy AtomicLongFieldUpdater i ich metod np compareAndSet - należy pamiętać że jest to rozwiązanie trochę słabsze bo działa jedynie kiedy wszystkie zmiany na zmiennej dokonywane są aktualizatorem - jeśli nie to rozwiązanie nie będzie działać.

W kwestii wydajności zmienne atomowe w porównaniu z rozwiązaniami bazującymi na blokadach wypadają dużo lepiej przy średnim obciążeniu zmian na polu. Jeśli zmian na polu jest bardzo dużo (co jest nierealistyczne) to zmienne atomowe mogą działać gorzej - jest to oczywiste ponieważ w takim wypadku większość wątków nie może wykonać zmiany na polu i powtarza operację wiele razy co powoduje wiele przełączeń kontekstu.

Algorytmy nieblokujące

Dzięki zmiennym atomowym i operacjami CAS można stworzyć algorytmy które, jeśli dobrze zaprojektowane, będą działać szybko w obu przypadkach - dużym i małym obciążeniu, oczywiście przy nierealistycznie dużym obciążeniu algorytm może działać słabo, należy jednak pamiętać że w takich algorytmach zawsze przynajmniej jeden wątek wykonuje postęp a inne nie są zablokowane więc zawsze ktoś wykona postęp.

Przykład stosu nieblokującego:

public class NonBlockingStack<T> {

private AtomicReference<Node<T>> top = new AtomicReference<>();

public void push(T data) {

Node<T> expextedTop;

Node<T> newTop = new Node<T>(data);

do {

expextedTop = top.get();

newTop.setNext(expextedTop);

} while (!top.compareAndSet(expextedTop, newTop));

}

public T pop() {

Node<T> expextedTop;

do {

expextedTop = top.get();

if (expextedTop == null) {

return null;

}

} while (top.compareAndSet(expextedTop, expextedTop.getNext()));

return expextedTop.getData();

}

private static class Node<T> {

private T data;

private Node<T> next;

public Node(T data) {

this.data = data;

}

public T getData() {

return data;

}

public Node<T> getNext() {

return next;

}

public void setNext(Node<T> next) {

this.next = next;

}

}

}