Wady blokad
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
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
- skalary: AtomicLong, AtomicInteger, AtomicBoolean, AtomicReference
- tablice: AtomicLongArray, AtomicIntegerArray, AtomicReferenceArray
- aktualizatory pól: AtomicLongFieldUpdater, AtomicIntegerFieldUpdater...
- złożone zmienne: AtomicStampedReference, AtomicMarkedReference
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;
}
}
}
