Czym jest mechanizm CAS (Compare-And-Swap)?

Mechanizm Compare-And-Swap (CAS) to atomowa operacja maszynowa używana do implementacji synchronizacji bez blokowania.

Zasada działania:

1. Odczytuje aktualną wartość komórki pamięci (expectedValue).
2. Próbuje zapisać nową wartość (newValue) do tej komórki tylko jeśli aktualna wartość jest zgodna z expectedValue.
3. Zwraca wartość boolean: true, jeśli zapis powiódł się (czyli wystąpiła zgodność), false w przeciwnym razie.

W Java CAS jest zaimplementowany w klasach z pakietu java.util.concurrent.atomic, np. AtomicInteger, AtomicLong, AtomicReference.

Przykład użycia AtomicInteger:

// java
import java.util.concurrent.atomic.AtomicInteger;

public class CasExample {
    private AtomicInteger count = new AtomicInteger(0);

    public void increment() {
        while (true) {
            int expectedValue = count.get(); // Odczytujemy aktualną wartość
            int newValue = expectedValue + 1;
            if (count.compareAndSet(expectedValue, newValue)) {
                // Jeśli aktualna wartość nie zmieniła się od odczytu,
                // wykonujemy zapis i wychodzimy z pętli
                break;
            }
            // Jeśli wartość się zmieniła, próbujemy ponownie
        }
    }
}

Zalety:

• Nieblokujący: wątki nie blokują się nawzajem, co zmniejsza koszty przełączania kontekstu, szczególnie przy niskiej konkurencji.
• Unika problemów z zakleszczeniem (deadlock).

Wady:

• Problem ABA: jeśli wartość komórki zmienia się z A na B, a potem z powrotem na A, CAS uzna, że nie było zmian. Aby rozwiązać ten problem, używa się klas typu AtomicStampedReference lub AtomicMarkableReference.
• Może wystąpić duża liczba nieudanych prób (spin loops) przy dużej konkurencji.