Problem ABA

Problem ABA – rodzaj błędu w synchronizacji procesów wielowątkowych, polegający na tym, że w przypadku dwukrotnego odczytu lokacji pamięci, gdy odczytana wartość jest taka sama w obu odczytach, to „taka sama wartość” jest interpretowana jako „nic się nie zmieniło”. Jednak inny wątek mógł, między odczytami w pierwszym wątku, zmienić wartość tej lokacji, wykonać jakieś zadania, a następnie ponownie zmienić wartość lokacji do wartości równej pierwotnej, niejako oszukując pierwszy wątek, że „nic się nie zmieniło”, mimo że drugi wątek wykonał pracę, która narusza to założenie.

Problem ABA pojawia się, kiedy wiele wątków (lub procesów) wykorzystuje dostęp do pamięci dzielonej naprzemiennie. Poniżej jest ciąg zdarzeń, których efektem jest problem ABA:

proces P₁ czyta wartość A z pamięci dzielonej
proces P₁ jest wywłaszczony, a uruchamiany jest proces P₂
proces P₂ zmienia wartość w pamięci dzielonej z A na B, a następnie z powrotem na A przed wywłaszczeniem
proces P₁ jest ponownie uruchamiany i widząc, że wartość w pamięci dzielonej się nie zmieniła, kontynuuje pracę

Mimo że P₁ może kontynuować działanie, jest także możliwe, że takie zachowanie nie będzie prawidłowe z powodu „ukrytych” zmian w pamięci dzielonej.

Powszechnym przypadkiem występowania problemu ABA jest realizacja struktur danych z wykorzystaniem synchronizacji nieblokującej. Jeśli element jest usunięty z listy i zwolniony, a następnie utworzony jest nowy element, który jest do listy dodany, może się zdarzyć, że nowy obiekt zajmuje ten sam obszar pamięci co uprzednio zwolniony, na skutek optymalizacji. Wobec tego wskaźnik na nowy obiekt jest identyczny ze wskaźnikiem na stary element listy, czego wynikiem jest problem ABA.

Przykłady edytuj

Filmowo−życiowy przykład problemu ABA edytuj

Maniek siedzi sobie na lotnisku z walizeczką zawierającą pokaźną sumę pieniędzy, którą postawił po swojej lewej stronie. Ma ją dostarczyć do swojego szefa, a że nie zna kodu do zamka szyfrowego, nie potrafi jej otworzyć. Pewna atrakcyjna i wyzywająco ubrana kobieta (Anastazja) przyciąga jego uwagę i rozpoczyna rozmowę. W trakcie gdy Anastazja odwraca uwagę Mańka, jej wspólnik (Albert) postanawia wykorzystać tę okazję aby przechwycić pieniądze. Zdaje sobie jednak sprawę, że jeśli Maniek odwróci głowę i zauważy brak walizeczki, to podniesie alarm, a wtedy on z Anastazją raczej lotniska nie opuszczą bez zatrzymania przez ochronę.

Zamiast tego, Albert szybko podmienia walizeczkę Mańka na identyczną lecz wypełnioną piaskiem o masie równej masie pieniędzy. Anastazja kończy rozmowę z Mańkiem, on wstaje, udaje się do samolotu i odlatuje. Jest kompletnie nieświadomy, że teraz walizeczka zawiera tylko piasek. Kiedy szef już otworzy walizeczkę, to Maniek będzie w wielkich tarapatach.

W tym scenariuszu stan A to walizeczka po lewej stronie Mańka, a stan B to jej brak. Początkowo walizeczka jest w stanie A. Jeśli Maniek by się odwrócił w czasie gdy Albert zabiera prawdziwą walizeczkę, a na jej miejscu umieszcza podróbkę, zauważyłby, że walizeczki nie ma (stan B) i wszcząłby alarm. Niestety, kiedy już skończył rozmowę z Anastazją to widział ponownie stan A, i chcąc nie chcąc, założył, że stan B nigdy się nie wydarzył.

Zobacz poniżej sekcję obejścia problemu aby znaleźć rozwiązanie jak Maniek mógł zapobiec temu nieszczęściu.

Przykład nieblokującej implementacji stosu edytuj

  /* Naiwny nieblokujący stos cierpiący na problem ABA. */
  class Stack {
    volatile Obj* top_ptr;
    //
    // Zdejmuje obiekt ze szczytu i zwraca wskaźnik do niego.
    //
    Obj* Pop() {
      while(1) {
        Obj* ret_ptr = top_ptr;
        if (!ret_ptr) return 0;
        Obj* next_ptr = ret_ptr->next;
        // Jeśli szczyt ciągle wskazuje na ret, to przyjmij, że nikt nie zmienił stosu.
        // (To twierdzenie nie zawsze jest prawdziwe ze względu na problem ABA)
        // Dokonuje atomowej wymianu szczytu z następnym.
        if (CompareAndSwap(top_ptr, ret_ptr, next_ptr)) {
          return ret_ptr;
        }
        // Stos jest zmodyfikowany, spróbuj ponownie.
      }
    }
    //
    // Umieszcza obiekt wskazywany przez obj_ptr na stosie.
    //
    void Push(Obj* obj_ptr) {
      while(1) {
        Obj* next_ptr = top_ptr;
        obj_ptr->next = next_ptr;
        // Jeśli szczyt ciągle wskazuje na next, to przyjmij, że nikt nie zmienił stosu.
        // (To twierdzenie nie zawsze jest prawdziwe ze względu na problem ABA)
        // Dokonuje atomowej zamiany szczytu z obiektem.
        if (CompareAndSwap(top_ptr, next_ptr, obj_ptr)) {
          return;
        }
        // Stos jest zmodyfikowany, spróbuj ponownie.
      }
    }
  };

Ten kod zwykle zapobiega problemom przy wielodostępie, lecz cierpi na problemy ABA. Rozważając następujący przypadek:

Początkowo stos zwiera top → A → B → C

Wątek 1 rozpoczyna zdejmowanie obiektu ze stosu (Pop):

 ret = A;
 next = B;

Wątek 1 zostaje przerwany tuż przed CompareAndSwap...

  { // Wątek 2 zdejmuje obiekt ze stosu (pop):
    ret = A;
    next = B;
    CompareAndSwap(A, A, B)  // Sukces, top = B
    return A;
  } // Teraz stos zawiera top → B → C
  { // Wątek 2 zdejmuje kolejny element:
    ret = B;
    next = C;
    CompareAndSwap(B, B, C)  // Sukces, top = C
    return B;
  } // Teraz stos zawiera top → C
  delete B;
  { // Wątek 2 umieszcza A z powrotem na stosie:
    A->next = C;
    CompareAndSwap(C, C, A)  // Sukces, top = A
  }

Teraz na stosie znajdują się top → A → C

Kiedy wątek 1 wznawia działanie:

 CompareAndSwap(A, A, B)

Ta instrukcja się udaje,a gdyż zauważa, że top == ret (obie są równe A), wobec czego ustawia szczyt na następny (który wynosi B). Z uwagi na to, że B został z pamięci usunięty (delete), program będzie się odwoływał do zwolnionej pamięci, kiedy nastąpi próba odczytu pierwszego elementu na stosie. Zachowanie w przypadku dostępu do zwolnionej pamięci jest niezdefiniowane, i zwykle prowadzi do szybkiej i nieoczekiwanej awarii aplikacji. Błędy ABA, takie jak ten, są trudne do śledzenia.

Obejścia problemu edytuj

Wracając do przykładu Mańka i jego walizeczki, czy Maniek mógłby coś zmienić?

Jest wiele sposobów, dzięki którym Maniek mógł zapobiec temu zdarzeniu, nawet nie otwierając walizeczki. Po pierwsze, mógł zastosować łańcuszek, którym by przypiął walizeczkę do siedzenia. W takim przypadku Albert musiałby go przeciąć, a Maniek słysząc przecinanie, wszcząłby alarm. Można to porównać do działania instrukcji LL/SC na niektórych procesorach. Innym rozwiązaniem mogłoby być zanotowanie numeru seryjnego prawdziwej walizeczki i sprawdzanie numeru za każdym razem, gdy się ją straci na pewien czas z zasięgu wzroku. Ten sposób to działanie podwójnej instrukcji CAS. Automatyczne odśmiecanie pamięci bądź hazard pointer, radzą sobie z tym problemem przez upewnienie się, że na świecie nie istnieje druga taka walizeczka jak Mańka. Jeśli Maniek, jego szef lub ktokolwiek inny opiekujący się walizeczką uzna, że już jej nie potrzebuje, to jest ona niszczona. Dopiero wtedy, i tylko wtedy, można utworzyć nową walizeczkę, która wygląda tak samo.

Poniżej przedstawione są przykłady jak w kodzie zrealizować powyższe pomysły.

Powszechnym obejściem jest dodanie nadmiarowych bitów „znaczników” do rozważanej wielkości. Na przykład algorytm stosujący compare-and-swap na wskaźnikach może stosować najmniej znaczące bity adresu do wskazywania, ile razy dany wskaźnik był pomyślnie zmieniony. Dzięki temu następne wywołanie compare-and-swap się nie powiedzie, nawet jeśli adres jest taki sam, ponieważ bity znaczników będą różne. To nie rozwiązuje problemu całkowicie, ponieważ bity znaczników się przepełniają i kontynuują zliczanie od nowa, lecz taki mechanizm pomaga unikać problemu. W niektórych architekturach dostępne są instrukcje CAS o zwiększonej (podwójnej) pojemności, pozwalającej na wielkie znaczniki. Nazywa się to czasami ABA' ponieważ drugie utworzone A jest nieco inne niż pierwsze.

Poprawnym, lecz drogim sposobem jest używanie węzłów pośrednich, które nie są elementami danych, dzięki czemu są niezmiennikami w trakcie wstawiania lub usuwania elementów [Valois].

Innym podejściem jest odraczanie przywracania zwolnionej pamięci. Sposoby opóźniania przywracania pamięci obejmują uruchamianie algorytmu w środowisku z automatycznym odśmiecaniem pamięci, hazard pointer lub read-copy-update (RCU).

Niektóre architektury dostarczają „dużych” instrukcji atomowych, takich, że nawet dwa wskaźniki (w przód i w tył) w listach dwukierunkowych mogą być aktualizowane w sposób niepodzielny.

Niektóre architektury dostarczają instrukcje load-link/store-conditional w których, zapis jest dokonywany tylko jeśli nie było innej operacji zapisu do zadanej lokacji. To skutecznie oddziela znaczenie „… zawiera wartość” od „… został zmieniony”. Takie instrukcje wspierane są przez DEC Alpha, MIPS, PowerPC lub ARM (v6 lub nowsza). Jednak, żadne praktyczne implementacje load-link nie będą bezpośrednio rozwiązywały problem ABA^[1].

Przypisy edytuj

↑ Michael 2004 ↓, s. 1.

Bibliografia edytuj

Damian Dechev, Peter Pirkelbauer, Bjarne Stroustrup: Lock-free Dynamically Resizable Arrays. [dostęp 2012-11-28]. (ang.).
Maged M. Michael: ABA Prevention Using Single-Word Instructions (LL/SC). 2004-01-29. [dostęp 2012-11-28]. [zarchiwizowane z tego adresu (2012-10-07)]. (ang.).
Damian Dechev, Peter Pirkelbauer, Bjarne Stroustrup: Understanding and Effectively Preventing the ABA Problem in Descriptor-based Lock-free Designs. [dostęp 2012-11-28]. (ang.).

[CITEREFMichael20041-1] Michael 2004 ↓, s. 1.

[1]