Pamięć transakcyjna

Tworząc aplikacje pracujące w systemach współbieżnych, jak i rozproszonych, każdy programista wcześniej czy później stanie przed problemem synchronizacji dostępu wątków lub procesów do obszaru zasobów współdzielonych, zwłaszcza pamięci – czy to w celu komunikacji między procesami, czy w celu odczytu lub modyfikacji współdzielonych danych.

Żądanie dostępu do danych może nastąpić jednocześnie w kilku wątkach, co wprowadza problem rywalizacji o zasoby. Jednakże, każdy z wątków wymaga wyłącznego dostępu do zasobu na czas wykonania kompletnej operacji. Sytuacja taka wymusza synchronizację dostępu do zasobów przez wątki, tak aby z jednej strony wykluczyć modyfikowanie wspólnych zasobów jednocześnie przez kilka wątków, a z drugiej strony zagwarantować pełną współbieżność i zniwelować możliwy efekt „zagłodzenia” wątku czy „wyścigu szczurów”.

Problemy te najczęściej rozwiązuje się poprzez zastosowanie mechanizmu blokad, atomizacji, zamków itp. Każdy ze sposobów ma swoje wady i zalety. Cechą wspólną tych rozwiązań jest to, że to programista musi zadbać o to, aby wrażliwy fragment kodu był w miarę możliwości w jednym miejscu (sekcja krytyczna), nałożyć i zdjąć odpowiednie muteksy, obsłużyć sytuacje wyjątkowe i jednocześnie zagwarantować współbieżność.

Rozpatrzmy bardzo prostą funkcję zamieniającą dwie zmienne:

void swap(int& x, int& y);

W wersji bez współbieżności jest bardzo prosta:

void swap(int& x, int& y){
int tmp=x;
x=y;
y=tmp;
}

Niestety przy zastosowaniu jej w wersji współbieżnej, mamy problem, gdyż nie mamy gwarancji, że inny wątek nie zmienił np. wartości zmiennej x pomiędzy przepisaniem jej do tmp a przypisaniem do y. W takiej sytuacji rozwiązanie współbieżne wyglądałoby na przykład tak:

void swap(int& x, int& y){
mutex.lock();
int tmp=x;
x=y;
y=tmp;
mutex.unlock();
}

Chociaż bezpieczniejsze byłoby np.:

void swap(int& x, int& y){
std::lock_guard<:mutex> lock(mutex);
int tmp=x;
x=y;
y=tmp;
}

Jeszcze większe problemy wystąpią, gdy obie zmienne będą pochodziły z odrębnych bloków lub, w przypadku systemów rozproszonych, gdy będą przechowywane na różnych węzłach. Należy wówczas zwiększyć liczbę muteksów i coraz bardziej komplikować kod wydawałoby się prostej funkcji.

STM – Software Transactional Memory

Aby odciążyć programistę od pilnowania tych problemów, uprościć kod i dać pewny w zachowaniu mechanizm ochronny, wprowadzono ideę zaczerpniętą z baz danych, czyli transakcje. Idea jest taka, że tworzymy jeden blok operacji modyfikujących dane współdzielone jako jedną transakcję, przy czym wszystkie instrukcje w transakcji muszą się wykonać z sukcesem albo nie wykona się żadna (j.n. niepodzielność transakcji – atomowość).

Każda transakcja musi spełniać cztery warunki – jest to tzw. własność ACID:

• Atomicity (niepodzielność) – transakcja musi zostać wykonana w całości lub wcale,
• Consistency (spójność) – po wykonaniu transakcji system pozostanie spójny, czyli nie zostaną naruszone jego zasady integralności,
• Isolation (izolacja) – jeśli dwie transakcje wykonywane są współbieżnie, to zwykle nie widzą wprowadzanych przez siebie zmian,
• Durability (stałość) – oznacza, że system potrafi się uruchomić i udostępnić spójne, nienaruszone i aktualne dane zapisane w ramach zatwierdzonych transakcji w wypadku wystąpienia sytuacji wyjątkowej.

Idea ta, użyta w języku programowania do zarządzania danymi współdzielonymi, to właśnie STM – Software Transactional Memory. Należy tu dodać, że istnieją podejścia wprowadzające tę ideę w hardware np. rozszerzenia TSX w niektórych procesorach Intela.

Podstawy STM stworzyli Nir Shavit i Dan Touitou w 1995 roku. Niemniej ze względu na problemy implementacyjne (wycofywanie i ponawianie transakcji, obsługa wyjątków itd.) pierwsze wdrożenia nastąpiły dosyć późno. Co ciekawe, najwcześniejszym wdrożeniem była adaptacja Erlangowej Mnesii opracowana przez Ericsson, która, pomimo że jej podstawową funkcjonalnością jest rozproszony, transakcyjny DBMS, spełnia również wymagania i oczekiwania STM. W 2005 roku Tim Harris, Simon Marlow, Simon Peyton Jones i Maurice Herlihy opisali system STM zbudowany na Concurrent Haskell, Umożliwia on ułożenie dowolnych operacji atomowych w większe operacje atomowe, co jest niemożliwe z programowaniem blokującym.

Inne implementacje to np.: ScalaSTM, JVSTM (Java), Concurent Ruby, Pugs(Perl), PyPy STM (Python). W przypadku języka C/C++ implementacje STM to TintSTM, Intel STM Compiler, LibLTX oraz wdrożenie w GCC++ (od v. 4.7, które zdaje się być pewną bazą dla standardu C++20). Dokładniejszy opis idei STM można znaleźć w opracowaniu [1] oraz [5].

Zastosowanie praktyczne: C++

Przypomnijmy sobie typową transakcję SQL-ową:

BEGIN TRANSACTION
//ciąg instrukcji SQL
INSERT INTO ....
.....
COMMIT TRANSACTION

Tak skonstruowany ciąg operacji na bazie zostanie wykonany w całości, gdy powiodą się wszystkie operacje i zostanie z powodzeniem wykonany commit. W przeciwnym wypadku zostanie wywołany rollback i wszystkie zmiany cofną się. Dokładnie to samo piszemy w przypadku nadzorowania operacjami nad pamięcią współdzieloną w STM.

__transaction_atomic{
operacja1();
operacja2();
}

Mamy tu blok operacji na pamięci współdzielonej nadzorowany przez STM (składnia gcc). Cały blok zostanie zakończony, a ewentualne modyfikacje zapisane, gdy wykonanie wszystkich operacji zostanie zwieńczone sukcesem. W przeciwnym wypadku całość zostaje wycofana do stanu początkowego i ponownie wykonana.

Trudności implementacyjne

Jedną z trudności implementacyjnych stanowi to, w jaki sposób przywrócić stan początkowy. Mamy kilka możliwości. Możemy albo gdzieś go przechowywać (dodatkowe kopiowanie), stworzyć metodę wsteczną (ale to łamie zasadę izolacji) albo jak w TSQL – tworzyć logi.

Następną otwartą kwestią pozostaje, jak wykrywać ewentualne konflikty czy inne czynniki nakazujące wycofanie transakcji.

Istnieją dwa podejścia do sterowania współbieżnością transakcji: optymistyczne i pesymistyczne. Optymistyczne oznacza, że transakcje wykonywane są niezależnie, a ewentualne konflikty, z powodu modyfikacji tych samych danych współdzielonych, wykrywane są podczas zatwierdzania transakcji. W przypadku ich wystąpienia transakcja jest wycofywana, czyli następuje przywrócenie obiektów do stanu sprzed wykonania transakcji. Transakcja jest następnie wykonywana ponownie, co może powodować wielokrotne wykonanie operacji nieodwracalnych, które obejmuje ta transakcja.

W podejściu pesymistycznym transakcje oczekują na dostęp do wszystkich współdzielonych obiektów i gdy warunek ten jest spełniony, jest wykonywana. Skutkuje to brakiem konfliktów spowodowanych przez jednoczesny dostęp do zasobów. W efekcie transakcje nie muszą być wycofywane i nie występuje problem z operacjami nieodwracalnymi.

Jak widać, implementacja nie jest prosta, stąd prace nad wdrożeniem STM (podejścia optymistycznego) do standardu C++ trwają już od 2012 roku i dopiero teraz mają szanse zostać zakończone (choć pierwotnie miały zostać wprowadzone w standardzie C++17).

Bloki do obsługi pamięci transakcyjnej

W wyniku wieloletnich prac oraz uwzględniając istniejące rozwiązania, postanowiono wprowadzić dwa rodzaje bloków do obsługi pamięci transakcyjnej: bloki zsynchronizowane i bloki atomowe:

• bloki zsynchronizowane zachowują się tak, jakby wszystkie bloki były chronione przez jeden globalny muteks rekursywny,

Bloki zsynchronizowane deklarowane są następująco:

synchronized { kod_bloku }

Mają one na celu rozwiązać niektóre trudności wiążące się z używaniem muteksów do synchronizowania dostępu do pamięci oraz uprościć ten dostęp. Dają większy poziom abstrakcji i większą elastyczność. Nie są one transakcjami i dlatego mogą wywoływać funkcje niebezpieczne transakcyjnie oraz mogą być zagnieżdżone. Opuszczenie zsynchronizowanego bloku (niezależnie od tego, czy poprzez dotarcie do końca, opuszczenie czy poprzez wywołanie wyjątku) powoduje synchronizację z następnym blokiem.

Nie mniej jednak zalecane jest zmniejszanie wielkości i ilości bloków zsynchronizowanych, ze względu na wydajność oraz możliwość spekulatywnego wykonania operacji, takich jak I/O. Natomiast, być może, w implementacjach zsynchronizowanych, uwzględnione zostanie wykorzystanie sprzętowej obsługi pamięci transakcyjnej. Na bloki zsynchronizowane nałożono kilka ograniczeń. Przede wszystkim zabronione zostało wchodzenie do ciała bloku zsynchronizowanego poprzez goto lub switch.

• bloki atomowe (nazywane również transakcjami atomowymi lub po prostu transakcjami) sprawiają wrażenie, że są jedną operacją atomową, a nie zsynchronizowanym blokiem (chyba że blok atomowy jest wykonywany w zsynchronizowanym bloku).

Transakcje atomowe zostały podzielone na trzy formy, deklarowane następująco:

atomic_noexcept { kod_bloku }
atomic_commit { kod_bloku }
atomic_cancel { kod_bloku }

Słowo kluczowe następujące po atomic to specyfikator wyjątku bloku atomowego. Określa zachowanie w sytuacjach wyjątkowych:

• noexcept: jeśli zostanie zgłoszony wyjątek, wywoływane jest std::abort
• commit: jeśli zostanie zgłoszony wyjątek, transakcja zostanie zatwierdzona normalnie
• cancel: jeśli zostanie zgłoszony wyjątek, wywoływane jest std::abort, chyba że wyjątek jest jednym z wyjątków używanych do anulowania transakcji, w którym to przypadku transakcja jest anulowana: wartości wszystkich lokalizacji pamięci w programie, które zostały zmodyfikowane przez efekty uboczne operacji bloku atomowego są przywracane do wartości, które miały w momencie uruchomienia bloku atomowego, a wyjątek kontynuuje rozwijanie stosu.

Wyjątki używane do anulowania dla transakcji:

std::bad_alloc, std::bad_array_new_length, std::bad_cast, std::bad_typeid, 
std::bad_exception, std::exception, std::tx_exception.

Zestaw typów wyjątków bezpiecznych cały czas ulega modyfikacji i najlepiej sprawdzić je w dokumentacji [2], [4]. Kod w treści transakcji musi być bezpieczny pod względem transakcji.

Jak zapewnić bezpieczeństwo transakcyjne?

Kod jest transakcyjnie niebezpieczny, jeśli:

• zawiera inicjalizację, przypisanie lub odczyt z obiektu zmiennego,
• zawiera deklarację asm,
• zawiera wywołanie funkcji niebezpiecznej transakcji lub wskaźnika funkcji, który nie jest transakcją bezpieczną,
• zawiera alokację i dealokację pamięci (odwołanie do systemu operacyjnego), aczkolwiek to ograniczenie może zostać usunięte w wersji finalnej standardu.

Poza tym zabronione jest wejście do bloku atomowego przy użyciu goto lub switch, synchronizacja przy pomocy blokad i obiektów atomowych oraz używanie funkcji niebezpiecznych transakcyjnie. Dodatkowo bloków transakcyjnych nie wolno zagnieżdżać. Wszystkie warunki określające co jest bezpieczne transakcyjnie, a co nie, precyzyjnie opisano w pozycjach [2], [3], [4].

Standard wprowadza również dodatkowe identyfikatory specjalnego znaczenia transaction_safe dla określenia explicite funkcji/metod, które są transakcyjnie bezpieczne, transaction_safe_dynamic i transaction_safe_noinherit dla funkcji wirtualnych oraz transaction_unsafe dla określenia funkcji transakcyjnie niebezpiecznych. Wykorzystywane również przy tworzeniu szablonów klas/funkcji bezpiecznych transakcyjnie.

struct A {
virtual void f1() transaction_safe;
virtual ~A()transaction_safe_noinherit;
virtual f2() transaction_safe_dynamic;
};

template {
void fun1(T) transaction_safe; //bezpieczna transakcyjnie
void fun2(T) transaction_unsafe; //nie bezpieczna transakcyjnie
}

Dodano również nowy typ wyjątku tx_exception, który powinien być używany do anulowania i wycofywania transakcji atomowej w bloku atomic_cancel.

Nadal natomiast trwają prace związane z destruktorami i destruktorami dla typów wyjątków, funkcjami wirtualnymi czy parametrami wskaźnika funkcji do funkcji (np. qsort). Istnieje kilka koncepcji rozwiązania istniejących problemów, lecz nie wiadomo, jakie rozwiązanie zostanie ostatecznie zaakceptowane. [2]. [3], [4].

Pewną, ale nadal niezatwierdzoną koncepcją jest wprowadzenie domen dla zsynchronizowanych bloków. Składniowo wyglądałoby to tak:

synchronized (domena) { kod_bloku }

Jeśli każdy zsynchronizowany blok ma dokładnie jedną domenę (i system nie rozpoznaje żadnej relacji między domenami), to jest logicznie równoważne z posiadaniem różnych muteksów dla każdej domeny. Jednakże to pojęcie jest bardziej ogólne niż muteksy w przypadku, gdy zsynchronizowane bloki mogą określać wiele domen. Wprowadza to wiele trudności implementacyjnych, więc w tej chwili jest całkowicie na etapie koncepcyjnym.

Po zapoznaniu się z tymi informacjami możemy wrócić do naszej funkcji swap i pokazać, jak wyglądałaby jej implementacja w oparciu o STM.

void swap(int& x, int& y){
atomic_commit{
int tmp=x;
x=y;
y=tmp;
}
}

Nadzieje na wdrożenie

Niestety wdrażanie STM w standardzie C++ przebiega wyjątkowo powoli, co jest z jednej strony związane zwłaszcza z problemami zachowania spójności przy wycofywaniu transakcji w przypadku niepowodzenia, a z drugiej dziwne wobec coraz większego wsparcia dla pamięci transakcyjnej w nowych procesorach. W związku z tymi problemami powstała inicjatywa „Transactional Memory Lite Support in C++”.

Jest to najświeższe podejście do pamięci transakcyjnej opierające się na zmniejszeniu wymagań wobec STM, wykorzystaniu algorytmów programowej pamięci TM, a także sprzętową i hybrydową pamięć TM oraz serializację transakcji na wklęsłej blokadzie mutex. Proponuje ona składnię

atomic
do {
...
}

Założeniem podejścia „lite” jest gwarancja, że transakcje będą wyglądać niepodzielnie w stosunku do innych transakcji.
Konkretnie:

1. Dwie transakcje powodują konflikt, jeśli mają dostęp do tej samej lokalizacji i co najmniej jedna z nich zapisuje tę lokalizację.
2. Jeśli transakcje A i B są w konflikcie, to albo koniec między wątkiem A następuje – przed początkiem B, albo koniec między wątkiem B – przed początkiem A.

Propozycją wersji „lite” są również alternatywy syntaktyczne i implementacje prototypowanie.

Pierwszą opcją jest struktura wykonania oparta na lambdzie do uruchamiania transakcji. W tym frameworku programista żąda uruchomienia bloku kodu jako transakcji, umieszczając go w wyrażeniu lambda i przekazując do specjalnej biblioteki TM.

Zamiast atomic { … } , oczekujemy, że składnia będzie wyglądać mniej więcej tak:

std::tm_exec([&]{... });

Mocne strony tego podejścia to:

• nie są wymagane żadne zmiany w interfejsie kompilatora,
• w przypadku systemów ze sprzętową obsługą TM możliwe jest zaimplementowanie std::tm_exec w całości jako bibliotekę: std::tm_exec może (1) rozpocząć transakcję sprzętową, (2) wykonać lambdę, a następnie (3) zatwierdzić sprzęt transakcję, wracając do ukrytej globalnej std::mutex w przypadku powtarzającego się niepowodzenia,
• w przypadku systemów bez sprzętowej obsługi pamięci TM możliwe jest zaimplementowanie std::tm_exec poprzez serializację wszystkich transakcji przy użyciu jednego nienazwanego globalnego std::mutex. Taka implementacja nie zapewniłaby skalowalności. Jednak w trosce o jak najłatwiejsze wdrożenie TM nie są wykluczane rozwiązania w początkowej fazie TS,
• w przypadku systemów, które chcą dodać obsługę oprogramowania TM, lambda w naturalny sposób umożliwia kompilatorowi przechwytywanie i dostęp instrumentu do pamięci w zakresie lokalnym oraz do śledzenia/wykrywania nieprawidłowych operacji, takich jak wywołania funkcji poza jednostką tłumaczeniową, dostępy do zmiennych volatile i atomowych itp.

Inną opcją jest użycie idiomu Resource Acquisition Is Initialization „pozyskiwanie zasobów to inicjalizacja” do oznaczania podmiotów transakcyjnych. To znaczy zamiast pisać atomic do { … }, programista napisałby:

{std::transaction_scope ts(); ... }

Większość zalet tego podejścia jest taka sama, jak w przypadku podejścia lambda. W szczególności:

• nie są wymagane żadne zmiany w interfejsie kompilatora,
• w przypadku systemów ze sprzętową obsługą pamięci TM oraz w systemach, które decydują się na serializację wszystkich transakcji w globalnym, nienazwanym muteks, wsparcie TM można osiągnąć w całości w bibliotece. Rozpoczęcie transakcji odbywa się w konstruktorze std::transaction_scope. Zatwierdzanie transakcji odbywa się w destruktorze.

Ponadto unika się dwóch pierwszych słabości podejścia lambda. To jest:

• nie ma żadnych dodatkowych kosztów związanych z tworzeniem i zarządzaniem lambdą,
• dostępne są wszystkie zmienne z zakresu nadrzędnego, nawet te (takie jak varargs) którego nie można przechwycić przez lambdę.

To podejście jest dostępne w postaci wtyczki do LLVM. Znajdziesz tu również kod oraz szczegóły realizacji.

Ponieważ wiele kwestii jest nadal otwartych, mogą nastąpić pewne różnice pomiędzy zawartymi tu informacjami a wersją ostateczną standardu. Dlatego zachęcam zainteresowanych do przeglądania statusu dokumentacji i postępu prac nad STM na stronach poświęconych standardowi C++.

Reasumując, na chwilę obecną prace komitetu standaryzacyjnego nad wprowadzeniem STM zwolniły. Jest to dziwne, zwłaszcza, że producenci procesorów coraz bardziej wspierają w swoich nowych projektach sprzętową TM. Również twórcy innych języków, choćby Python czy Java, wdrażają ideę STM. „Światełkiem w tunelu” jest inicjatywa LLVM. Główna przyczyną takiego stanu rzeczy są przede wszystkim problemy z bezpiecznym wycofywaniem transakcji w przypadku niepowodzenia. Mam jednak nadzieję, że w najbliższym czasie prace nad wdrożeniem STM do standardu C++ ruszą z miejsca.

Literatura:

1. “Taxonomy for Transactional Memory Systems” – Shweta Kulkarni i inni
2. “Transactional Memory Support for C++” – Victor Luchangco i inni (2013, 2014, 2014)
3. “Working Draft Technical Specification for C++ Extensions for Transactional Memory” – Michael Wong i inni
4. “Technical Specification for C++ Extensions for Transactional Memory”
5. “Transactional Memory Lite Support in C++”
6. “Compile time support for using Transactional Memory in C/C++ applications” – Miloš Milovanović i inni
7. Standard ISO/IEC TS 19841:2015

***

Jeśli interesujesz się tematyką C++, zajrzyj również do innych artykułów naszych ekspertów.