Hery's devlog

Implementacja nieblokujących struktur danych często stwarza problemy często niespotykane przy okazji opracowywania jakichkolwiek innych algorytmów. Całkowicie zasadnie, najpopularniejszymi przykładami w opracowaniach na ten temat jest problem ABA i jego pochodne. Oczywiście, do dnia dzisiejszego powstało wiele sposobów radzenia sobie z nim. Jednym z ciekawszych są tak zwane hazard pointers.

Problem ABA

Na początek warto jednak przybliżyć (lub przypomnieć) dlaczego problem ABA jest problemem i o co w ogóle w nim chodzi. Bardzo często operacje na strukturach danych lock-free wyglądają w uproszczeniu tak:

1. Pobierz z pamięci dzielonej adres obiektu A ze wskaźnika head.
2. Wykonaj odpowiednie operacje na obiekcie A, np. odczytaj dane oraz adres kolejnego obiektu B.
3. Jeśli head wskazuje dalej na ten sam obiekt (tj. adres jest ten sam) przypisz do niego pobrany punkt wyżej adres obiektu B.
4. Zwolnij pamięć po obiekcie A

Jak widać jest to uproszczona implementacja ściągania elementu z nieblokującego stosu zaimplementowanego przy pomocy listy jednokierunkowej. Teraz, czas na problem ABA. Popatrzmy co się stanie jeśli w trakcie wykonywania pkt. 2 wątek zostanie wywłaszczony i w międzyczasie inny wątek (lub wątki) ściągnie ten element ze stosu i zwolni po nim pamięć, a następnie doda inny obiekt który zostanie umieszczony pod tym samym adresem. W takiej sytuacji pierwszy wątek po wznowieniu i dotarciu do pkt. 3 uzna że head wskazuje na ten sam obiekt co w pkt. 1 i uaktualni go (najprawdopodobniej) niepoprawnym adresem kolejnego obiektu. Dodatkowo jako wspomniane wcześniej "pochodne problemu ABA" rozumiem sytuacje gdy wątek będzie chciał odczytać dane z obiektu który w międzyczasie przestał istnieć.

Hazard pointers

Zasada działania tego mechanizmu jest dosyć prosta. Każdy wątek posiada wskaźnik, właśnie tytułowy hazard pointer, na obiekt który aktualnie przetwarza oraz prywatną (tj. używaną tylko przez wątek który jest jej właścicielem) listę obiektów które powinny zostać usunięte. Hazard pointers są ułożone w listę jednokierunkową możliwą do przeglądania przez każdego.

Teraz, dodatkowo, w pierwszym kroku adres obiektu A z head algorytm musi umieścić w hazard pointer jego wątku, po czym sprawdzić czy head nadal wskazuje na obiekt A (przed uaktualnieniem hazard pointera problem ABA jeszcze ma się dobrze). Jeśli tak to obiekt A jest bezpieczny i możemy na nim pracować. Gdy skończymy, po prostu zerujemy nasz hazard pointer.

Kolejne zmiany potrzebne są w pkt. 4. Zamiast po prostu zwalniać pamięć po zdjętym ze stosu elemencie jego adres jest umieszczony na liście obiektów do usunięcia. Następnie usunięte zostają wszystkie obiekty obecne na tej liście i nieobecne na liście hazard pointerów. Jest to bezpieczne ponieważ każdy przetwarzany lub z innego powodu potrzebny obiekt albo nie trafił jeszcze na tę listę, albo zaraz na nią trafi ale jeszcze jest zabezpieczony hazard pointerem. Wszystkie obiekty które już powinny być usunięte, ale ktoś ich jeszcze używa zostaną zwolnione przy następnej okazji.

Podsumowanie

Hazard pointers w dość prosty sposób zapewniają, że żaden obiekt nie zostanie usunięty w trakcie gdy jest przetwarzany przez inny wątek. Jest to rozwiązanie bardzo uniwersalne. Można je z powodzeniem stosować w konkretnych strukturach danych, a także jest świetnym uzupełnieniem innych ogólnych rozwiązań jak np. RCU, co zostało opisane w [1]. Pewną wspomnianą tam niedogodnością, dotyczącą nie tylko RCU, jest fakt, że każde użycie hazard pointera jest lock-free, a co za tym idzie tracą na tym operacje wait-free takie jak np. odczyt w przypadku RCU.

[1] A. Alexandrescu, M. Michael, Lock-Free Data Structures with Hazard Pointers