Problem z ABA

W obliczeniach wielowątkowych problem ABA występuje podczas synchronizacji, gdy lokalizacja jest odczytywana dwukrotnie, ma tę samą wartość dla obu odczytów, a „wartość jest taka sama” jest używana do wskazania „nic się nie zmieniło”. Jednak inny wątek może wykonać się między dwoma odczytami i zmienić wartość, wykonać inną pracę, a następnie zmienić wartość z powrotem, oszukując w ten sposób pierwszy wątek, myśląc „nic się nie zmieniło”, mimo że drugi wątek działał, co narusza to założenie.

Problem ABA występuje, gdy wiele wątków (lub procesów ) uzyskujących dostęp do współdzielonych danych przeplata się. Poniżej znajduje się sekwencja zdarzeń, która ilustruje problem ABA:

  1. Proces odczytuje wartość A z jakiejś współdzielonej lokalizacji pamięci,
  2. jest wywłaszczany , umożliwiając uruchomienie procesu,
  3. zapisuje wartość B do lokalizacji pamięci współdzielonej
  4. zapisuje wartość A do lokalizacji pamięci współdzielonej
  5. jest wywłaszczany, umożliwiając uruchomienie procesu,
  6. odczytuje wartość A z lokalizacji pamięci współdzielonej,
  7. określa, że ​​wartość pamięci współdzielonej nie uległa zmianie i trwa.

Chociaż może że zachowanie nie będzie poprawne z powodu „ukrytej” modyfikacji w pamięci współdzielonej

Typowy przypadek problemu ABA występuje podczas implementacji struktury danych bez blokad . Jeśli element zostanie usunięty z listy, usunięty, a następnie nowy element zostanie przydzielony i dodany do listy, często przydzielony obiekt znajduje się w tej samej lokalizacji co usunięty obiekt z powodu alokacji pamięci MRU . Wskaźnik do nowego elementu jest zatem często równy wskaźnikowi do starego elementu, co powoduje problem z ABA.

Przykłady

Rozważmy przykład oprogramowania (napisany w C++) ABA przy użyciu stosu bez blokady : 


  
   
  
  
  
    
      
         
         
      
      
         
      
      
      
         
         
      
      
    
  
  
  
  
     
      
         
        
      
      
      
         
        
      
      
    
  
 /* Naiwny stos bez blokad, który cierpi na problem z ABA.*/  class  Stack  {  std  ::  atomic  <  Obj  *>  top_ptr  ;  //  // Wysuwa górny obiekt i zwraca do niego wskaźnik.  //  Obj  *  Pop  ()  {  while  (  1  )  {  Obj  *  ret_ptr  =  top_ptr  ;  if  (  !  ret_ptr  )  return  nullptr  ;  // Dla uproszczenia załóżmy, że możemy upewnić się, że to wyłuskanie jest bezpieczne  // (tzn. że żaden inny wątek nie pojawił się w międzyczasie na stosie).  Obj  *  następny_ptr  =  ret_ptr  ->  następny  ;  // Jeśli górny węzeł nadal jest w stanie spoczynku, załóżmy, że nikt nie zmienił stosu.  // (To stwierdzenie nie zawsze jest prawdziwe ze względu na problem z ABA)  // Atomowo zamień top na next.  if  (  top_ptr  .  porównaj_exchange_weak  (  ret_ptr  ,  next_ptr  ))  {  return  ret_ptr  ;  }  // Stos się zmienił, zacznij od nowa.  }  }  //  // Przesuwa obiekt określony przez obj_ptr na stos.  //  void  Push  (  Obj  *  obj_ptr  )  {  while  (  1  )  {  Obj  *  next_ptr  =  top_ptr  ;  obj_ptr  ->  następny  =  następny_ptr  ;  // Jeśli górny węzeł jest nadal następny, załóżmy, że nikt nie zmienił stosu.  // (To stwierdzenie nie zawsze jest prawdziwe z powodu problemu z ABA)  // Atomowo zamień top na obj.  if  (  top_ptr  .  porównaj_exchange_weak  (  następny_ptr  ,  obj_ptr  ))  {  return  ;  }  // Stos się zmienił, zacznij od nowa.  }  }  };

Ten kod może normalnie zapobiegać problemom związanym z równoczesnym dostępem, ale ma problemy z ABA. Rozważ następującą sekwencję:

Stos początkowo zawiera górę → A → B → C

Wątek 1 zaczyna uruchamiać pop:

ret = A; następny = B;

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

 
    
    
     
   
 
 
    
    
     
   
 
 
 
    
     
 {  // Wątek 2 działa pop:  ret  =  A  ;  następny  =  B  ;  Compare_exchange_weak  (  A  ,  B  )  // Sukces, top = B  return  A  ;  }  // Teraz stos jest na wierzchu → B → C  {  // Wątek 2 znów działa:  ret  =  B  ;  następny  =  C  ;  Compare_exchange_weak  (  B  ,  C  )  // Sukces, top = C  return  B  ;  }  // Teraz stos jest na wierzchu → C  delete  B  ;  {  // Wątek 2 odkłada teraz A z powrotem na stos:  A  ->  next  =  C  ;  Compare_exchange_weak  (  C  ,  A  )  // Sukces, top = A  }

Teraz stos jest na górze → A → C

Gdy Wątek 1 zostanie wznowiony:

porównaj_wymianę_słaby(A, B)

Ta instrukcja się powiedzie, ponieważ znajduje top == ret (oba są A), więc ustawia top na następny (czyli B). Ponieważ B zostało usunięte, program uzyska dostęp do zwolnionej pamięci, gdy spróbuje spojrzeć na pierwszy element na stosie. W C++, jak pokazano tutaj, dostęp do zwolnionej pamięci jest niezdefiniowanym zachowaniem : może to spowodować awarie, uszkodzenie danych lub nawet po cichu wydawać się, że działa poprawnie. Błędy ABA, takie jak ten, mogą być trudne do debugowania.

Obejścia

Oznakowane odniesienie do stanu

Typowym obejściem jest dodanie dodatkowych bitów „znacznika” lub „pieczęci” do rozważanej ilości. Na przykład algorytm wykorzystujący porównanie i zamianę na wskaźniku może użyć niższych bitów adresu, aby wskazać, ile razy wskaźnik został pomyślnie zmodyfikowany. Z tego powodu następne porównanie i zamiana nie powiedzie się, nawet jeśli adresy są takie same, ponieważ bity znaczników nie będą pasować. Nazywa się to czasem ABAʹ, ponieważ drugie A różni się nieco od pierwszego. Takie tagowane odniesienia do stanu są również używane w pamięci transakcyjnej . Chociaż do implementacji można użyć oznakowanego wskaźnika , preferowane jest oddzielne pole znacznika, jeśli dostępny jest CAS o podwójnej szerokości.

Jeśli pole „tag” się zawija, gwarancje wobec ABA już nie obowiązują. Jednak zaobserwowano, że na obecnie istniejących procesorach i przy użyciu znaczników 60-bitowych żadne zawijanie nie jest możliwe, o ile czas życia programu (to znaczy bez ponownego uruchamiania programu) jest ograniczony do 10 lat; ponadto argumentowano, że ze względów praktycznych zwykle wystarczy mieć 40-48 bitów znacznika, aby zabezpieczyć się przed zawijaniem. Ponieważ nowoczesne procesory (w szczególności wszystkie nowoczesne procesory x64) zwykle obsługują 128-bitowe operacje CAS, może to pozwolić na solidne gwarancje przeciwko ABA.

Węzły pośrednie

Poprawnym, ale kosztownym podejściem jest użycie węzłów pośrednich, które nie są elementami danych, a tym samym zapewnienie niezmienników podczas wkładania i usuwania elementów [Valois].

Odroczona reklamacja

Innym podejściem jest odroczenie odzyskania usuniętych elementów danych. Jednym ze sposobów odroczenia odzyskiwania jest uruchomienie algorytmu w środowisku wyposażonym w automatyczny moduł wyrzucania elementów bezużytecznych ; problem polega jednak na tym, że jeśli GC nie jest wolny od blokad, to cały system nie jest wolny od blokad, nawet jeśli sama struktura danych jest.

Innym sposobem odroczenia rekultywacji jest użycie jednego lub więcej wskaźników zagrożeń , które są wskaźnikami do lokalizacji, które w przeciwnym razie nie mogłyby pojawić się na liście. Każdy wskaźnik zagrożenia reprezentuje stan pośredni trwającej zmiany; obecność wskaźnika zapewnia dalszą synchronizację [Doug Lea]. Wskaźniki zagrożeń są wolne od blokad, ale mogą śledzić co najwyżej stałą liczbę elementów na wątek jako będących w użyciu.

Jeszcze innym sposobem na odroczenie odzyskiwania jest użycie aktualizacji odczytu i kopiowania (RCU) , która polega na umieszczeniu aktualizacji w sekcji krytycznej po stronie odczytu RCU, a następnie oczekiwaniu na okres prolongaty RCU przed zwolnieniem usuniętych elementów danych. Używanie RCU w ten sposób gwarantuje, że żaden usunięty element danych nie pojawi się ponownie, dopóki wszystkie aktualnie wykonywane operacje nie zostaną zakończone. RCU jest wolne od blokad, ale nie jest odpowiednie dla wszystkich obciążeń.

Instrukcje alternatywne

Zamiast używać pojedynczych instrukcji porównania i zamiany obejmujących cały wskaźnik, niektóre procesory mają inne instrukcje, które mają być bardziej odporne lub odporne na problem ABA.

Niektóre architektury zapewniają „większe” operacje atomowe, na przykład zarówno łącza do przodu, jak i do tyłu na podwójnie połączonej liście mogą być aktualizowane atomowo; chociaż ta funkcja jest zależna od architektury, jest w szczególności dostępna dla architektur x86/x64 (x86 pozwala na 64-bitowy CAS, a wszystkie nowoczesne procesory x64 pozwalają na 128-bitowy CAS) i IBM z/Architecture (która pozwala na do 128-bitowego CAS).

Niektóre architektury udostępniają instrukcje warunkowe związane z ładowaniem, w których składowanie jest wykonywane tylko wtedy, gdy nie ma innych sklepów we wskazanej lokalizacji. To skutecznie oddziela pojęcie „przechowywanie zawiera wartość” od „przechowywanie zostało zmienione”. Przykłady obejmują DEC Alpha , MIPS , PowerPC , RISC-V i ARM (v6 i nowsze). Ponieważ te instrukcje zapewniają niepodzielność przy użyciu adresu, a nie wartości, procedury korzystające z tych instrukcji są odporne na problem ABA.

Zobacz też

  •   Deczew, Damian; Pirkelbauer, Peter; Stroustrup, Bjarne (2006). „Dynamicznie skalowalne tablice bez blokad” . CiteSeerX 10.1.1.86.2680 . {{ cite journal }} : Cite journal wymaga |journal= ( pomoc )
  • Deczew, Damian; Pirkelbauer, Peter; Stroustrup, Bjarne (2010). „Zrozumienie i skuteczne zapobieganie problemowi ABA w projektach bez blokad opartych na deskryptorach” (PDF) .
Pobrano z „ https://en.wikipedia.org/w/index.php?title=ABA_problem&oldid=1116672883 ”