Compare-and-swap

Compare-and-swap, CAS (porównaj i zamień) – operacja atomowa stosowana w wielowątkowych procesach w celu synchronizacji. Jej działanie polega na porównaniu zawartości pewnej lokacji w pamięci z zadaną wartością a następnie, jeśli obie wartości są równe, jej zmodyfikowaniu do nowej wartości. Niepodzielność operacji zapewnia, że nowa wartość jest wyznaczona na podstawie aktualnych danych. Jeśli wartość zostałaby w międzyczasie zmodyfikowana przez inny wątek to zapis by się nie powiódł. Wynik operacji musi wskazywać, czy działanie zapisu zostało wykonane czy nie. Może to być prosty typ logiczny lub zwracanie wartości odczytanej z podanej lokacji (lecz nie zapisanej).

Historia

Instrukcja compare-and-swap była integralną częścią architektury IBM 370 i jej następników począwszy od 1970 roku. Systemy operacyjne działające na tej architekturze intensywnie korzystały z tej instrukcji w celu uproszczenia procesów (zadań systemowych i zadań użytkownika) i przetwarzania równoległego przez eliminację, do najwyższego możliwego stopnia, „disabled spin locks”, które były zastosowane we wcześniejszych wersjach systemów operacyjnych IBM. W tych systemach operacyjnych nową jednostkę roboczą można było utworzyć „globalnie” lub „lokalnie” na liście serwisów przez wywołanie pojedynczej instrukcji CAS. To znacząco zwiększyło reaktywność w systemie operacyjnym.

W procesorach x86 i Itanium istnieje instrukcja CMPXCHG, która poprzedzona prefiksem LOCK realizuje operację CAS w środowisku wieloprocesorowym.

Realizacja

Poniższa funkcja w C przedstawia zachowanie wariantu instrukcji CAS, która jako wynik zwraca poprzednią wartość komórki pamięci. Jednak jest to tylko demonstracja, która nie zapewnia niepodzielności. Rzeczywista implementacja wymaga wsparcia sprzętowego.

int compare_and_swap (int* reg, int oldval, int newval) 
{
  int old_reg_val = *reg;
  if (old_reg_val == oldval) 
     *reg = newval;
  return old_reg_val;
}

Zawartość old_reg_val jest zawsze zwracana. Jej ponowne porównanie pozwala stwierdzić czy jej wartość równa się oldval, ponieważ jeśli jest ona inna to oznacza, że inny proces wykonał tę samą instrukcję i udało mu się wymienić wartość reg na newval.

Języki wysokiego poziomu

C++

Początkowo standard języka C++ nie definiował metody CAS. Taka funkcjonalność była dostępna jako funkcja systemu operacyjnego, bądź jako rozszerzenie kompilatora lub dostarczana przez zewnętrzne biblioteki. Wraz z pojawieniem się C++11, pojawiły się standardowe mechanizmy ułatwiające korzystanie z wątków: atomic_compare_exchange_weak, atomic_compare_exchange_strong, atomic_compare_exchange_weak_explicit i atomic_compare_exchange_strong_explicit.

.NET Framework (C#)

W bibliotece standardowej jest dostępna metoda Interlocked.CompareExchange, która implementuje funkcjonalność CAS.

Java

Począwszy od wersji 1.5, biblioteka standardowa zawiera pakiet java.util.concurrent.atomic, w którym znajdują się klasy AtomicBoolean, AtomicInteger, AtomicLong i AtomicReference zawierające metodę compareAndSet będącą implementacją CAS.

Zastosowanie

Instrukcja CAS jest stosowana do implementowania podstawowych obiektów stosowanych w synchronizacji procesów np. semaforów jak również bardziej wyszukanych algorytmów synchronizacji nieblokujących.

Algorytmy korzystające z CAS zazwyczaj odczytują wartość kluczową z pamięci i ją zapamiętują. Na jej podstawie wyliczają nową wartość. Następnie dokonywana jest zamiana kluczowej wartości w pamięci przy wykorzystaniu CAS na nową dokonując porównania z zapamiętaną starą wartością. Jeśli CAS zwraca rezultat będący niepowodzeniem, to cała procedura jest powtarzana od początku, tj. kolejna wartość kluczowa jest ponownie odczytywana, na jej podstawie wyznaczana jest następna nowa wartość i CAS jest wykorzystywane do zamiany wartości pamięci. Taka pętla jest wykonywana tak długo aż zakończy się sukcesem.

Problem ABA

Niektóre z algorytmów korzystających z instrukcji CAS muszą rozwiązywać błąd pierwszego rodzaju znany jako problem ABA. Jest bowiem możliwe, że w czasie między odczytaniem starej wartości a czasem wykonania instrukcji CAS, inny procesor lub wątek zmieni wartość pamięci dwa lub więcej razy w taki sposób, że przypisze ponownie wartość zgodną ze starą wartością. Problem pojawia się w momencie, gdy pozornie taka sama wartość uzyskuje zupełnie inne znaczenie, np. jest to adres ponownie przydzielonej pamięci lub przepełniony licznik.

Korzyści

Spotyka się opinie, że CAS i inne operacje atomowe są niepotrzebne w systemach jednoprocesorowych, ponieważ niepodzielność operacji można uzyskać przez zablokowanie obsługi przerwań na czas wykonywania wrażliwych operacji. Jednak blokowanie przerwań ma wiele skutków ubocznych. Kod, który może blokować przerwania, musi być zaufany, ponieważ jeśli jest podejrzany, może zmonopolizować procesor. Kod musi być także poprawny, inaczej może się zatrzymać w nieskończonej pętli.

W systemach wieloprocesorowych zwykle nie jest możliwe zablokowanie przerwań na wszystkich procesorach w tym samym czasie. A nawet jeśli byłoby to możliwe to dwa lub więcej procesorów mogłoby próbować czytać i modyfikować tę samą daną w tym samym czasie, co nie gwarantowałoby niepodzielności. Instrukcja CAS rozwiązuje takie kolizje między procesorami.

Rozszerzenia

Z uwagi na to, że CAS operuje na danych, których rozmiar nie przekracza zmiennych typu wskaźnikowego, a większość algorytmów synchronizacji nieblokujących wymaga umożliwienia zmieniania wielu lokacji, zostały opracowane różne rozszerzenia.

• Podwójny CAS porównuje dwie niepowiązane lokacje z dwoma oczekiwanymi wartościami, i jeśli obie są równe, umieszczana są w nich dwie nowe wartości. Taka instrukcja istnieje tylko na procesorach Motorola 680x0.
• CAS podwójnej szerokości porównujący lokację zdolną pomieścić dwie zmienne typu wskaźnikowego. Na późniejszych procesorach x86 dostępne są instrukcje CMPXCHG8B i CMPXCHG16B, które tę funkcję realizują.
• Porównanie pojedynczej szerokości, a zamiana podwójnej szerokości. Taką funkcję realizuje instrukcja cmp8xchg16 na procesorach Itanium.
• Uogólnienie operacji porównania i zamiany dla dowolnej ilości dowolnie wybranych lokacji. Zazwyczaj taki uogólniony CAS jest realizowany programowo z wykorzystaniem CAS podwójnej szerokości. Wadą takiego rozwiązania jest brak skalowalności.

Zobacz też

• Fetch-and-add

Bibliografia

• Maurice Herlihy. Wait-free synchronization. „ACM Trans. Program. Lang. Syst.”. 13 (1), s. 124–149, styczeń 1991. DOI: 10.1145/114005.102808. [dostęp 2012-11-24]. (ang.).