Pamięć transakcyjna oprogramowania

W informatyce pamięć transakcyjna oprogramowania ( STM ) jest mechanizmem kontroli współbieżności , analogicznym do transakcji w bazie danych , służącym do kontrolowania dostępu do pamięci współdzielonej w obliczeniach współbieżnych . Jest to alternatywa dla synchronizacji opartej na blokadach . STM to strategia zaimplementowana w oprogramowaniu, a nie jako komponent sprzętowy. Transakcja w tym kontekście ma miejsce, gdy fragment kodu wykonuje serię odczytów i zapisów w pamięci współdzielonej. Te odczyty i zapisy logicznie występują w jednej chwili; stany pośrednie nie są widoczne dla innych (udanych) transakcji. Pomysł zapewnienia sprzętowej obsługi transakcji zrodził się w artykule Toma Knighta z 1986 roku . Pomysł ten spopularyzowali Maurice Herlihy i J. Eliot B. Moss . W 1995 Nir Szawit a Dan Touitou rozszerzył ten pomysł na pamięć transakcyjną wyłącznie programową (STM). Od 2005 roku STM jest przedmiotem intensywnych badań, a wsparcie dla praktycznych wdrożeń rośnie.

Wydajność

W przeciwieństwie do technik blokowania stosowanych w większości nowoczesnych aplikacji wielowątkowych, STM jest często bardzo optymistyczny : wątek wykonuje modyfikacje w pamięci współdzielonej bez względu na to, co mogą robić inne wątki, rejestrując każdy odczyt i zapis w dzienniku. Zamiast nakładać na pisarza obowiązek upewnienia się, że nie wpłynie to niekorzystnie na inne operacje w toku, spoczywa on na czytelniku, który po zakończeniu całej transakcji sprawdza, czy inne wątki nie dokonały jednocześnie zmian w pamięci, do której miał dostęp w przeszłość. Ta ostateczna operacja, w której zmiany transakcji są zatwierdzane i, jeśli walidacja zakończy się pomyślnie, wprowadzane są na stałe, nazywana jest zatwierdzeniem . Transakcja może również zostać przerwana w dowolnym momencie, powodując wycofanie lub cofnięcie wszystkich wcześniejszych zmian. Jeśli transakcja nie może zostać zatwierdzona z powodu sprzecznych zmian, jest zwykle przerywana i wykonywana ponownie od początku, aż do pomyślnego zakończenia.

Zaletą tego optymistycznego podejścia jest zwiększona współbieżność: żaden wątek nie musi czekać na dostęp do zasobu, a różne wątki mogą bezpiecznie i jednocześnie modyfikować rozłączne części struktury danych, które normalnie byłyby chronione tą samą blokadą.

Jednak w praktyce systemy STM mają również spadek wydajności w porównaniu z systemami opartymi na drobnoziarnistych blokadach na niewielkiej liczbie procesorów (od 1 do 4 w zależności od aplikacji). Wynika to przede wszystkim z narzutów związanych z utrzymaniem dziennika i czasem poświęconym na zatwierdzanie transakcji. Nawet w tym przypadku wydajność zazwyczaj nie jest gorsza niż dwa razy wolniejsza. Zwolennicy STM uważają, że ta kara jest uzasadniona koncepcyjnymi korzyściami STM .

Teoretycznie najgorszym przypadkiem złożoności przestrzennej i czasowej n współbieżnych transakcji jest O ( n ). Rzeczywiste potrzeby zależą od szczegółów implementacji (można sprawić, że transakcje zakończą się niepowodzeniem na tyle wcześnie, aby uniknąć narzutów), ale będą też przypadki, choć rzadkie, w których algorytmy oparte na blokadach mają lepszą złożoność czasową niż pamięć transakcyjna oprogramowania.

Konceptualne zalety i wady

Oprócz korzyści związanych z wydajnością , STM znacznie upraszcza konceptualne rozumienie programów wielowątkowych i pomaga uczynić programy łatwiejszymi w utrzymaniu dzięki pracy w harmonii z istniejącymi abstrakcjami wysokiego poziomu, takimi jak obiekty i moduły. Programowanie oparte na blokadach ma wiele dobrze znanych problemów, które często pojawiają się w praktyce:

• Blokowanie wymaga myślenia o nakładających się operacjach i operacjach częściowych w odległych i pozornie niepowiązanych sekcjach kodu, co jest zadaniem bardzo trudnym i podatnym na błędy.
• Blokowanie wymaga od programistów przyjęcia polityki blokowania, aby zapobiec zakleszczeniu , livelock i innym niepowodzeniom w celu osiągnięcia postępu. Takie zasady są często nieformalnie egzekwowane i zawodne, a kiedy pojawiają się takie problemy, są podstępnie trudne do odtworzenia i debugowania.
• Blokowanie może prowadzić do odwrócenia priorytetów , czyli zjawiska, w którym wątek o wysokim priorytecie jest zmuszony czekać na wątek o niskim priorytecie, który ma wyłączny dostęp do potrzebnego mu zasobu.

W przeciwieństwie do tego koncepcja transakcji pamięciowej jest znacznie prostsza, ponieważ każdą transakcję można postrzegać oddzielnie jako obliczenia jednowątkowe. Zakleszczenie i blokada na żywo są albo całkowicie zapobiegane, albo obsługiwane przez zewnętrznego menedżera transakcji; programista nie musi się tym martwić. Odwrócenie priorytetów nadal może stanowić problem, ale transakcje o wysokim priorytecie mogą przerwać sprzeczne transakcje o niższym priorytecie, które nie zostały jeszcze zatwierdzone.

Z drugiej strony konieczność przerwania nieudanych transakcji nakłada również ograniczenia na zachowanie transakcji: nie mogą one wykonać żadnej operacji, której nie można cofnąć, w tym większości operacji we/wy. Takie ograniczenia są zwykle przezwyciężane w praktyce poprzez tworzenie buforów, które ustawiają w kolejce nieodwracalne operacje i wykonują je w późniejszym czasie poza jakąkolwiek transakcją. W Haskell to ograniczenie jest wymuszane w czasie kompilacji przez system typów.

Operacje komponowalne

W 2005 roku Tim Harris, Simon Marlow , Simon Peyton Jones i Maurice Herlihy opisali system STM zbudowany na Concurrent Haskell , który umożliwia składanie dowolnych operacji atomowych w większe operacje atomowe, co jest użyteczną koncepcją niemożliwą w przypadku programowania opartego na blokadach. Cytując autorów:

Być może najbardziej podstawowym zarzutem [...] jest to, że programy oparte na blokadach nie tworzą : prawidłowe fragmenty mogą zawieść po połączeniu. Rozważmy na przykład tablicę skrótów z bezpiecznymi wątkowo operacjami wstawiania i usuwania. Załóżmy teraz, że chcemy usunąć jeden element A z tabeli t1 i wstawić go do tabeli t2; ale stan pośredni (w którym żadna tabela nie zawiera elementu) nie może być widoczny dla innych wątków. O ile implementator tablicy skrótów nie przewidzi takiej potrzeby, po prostu nie ma sposobu, aby spełnić to wymaganie. […] Krótko mówiąc, operacje, które są pojedynczo poprawne (wstawianie, usuwanie), nie mogą być składane w większe poprawne operacje.
—Tim Harris i in., „Transakcje w pamięci komponowalnej”, część 2: Tło, str. 2

W przypadku STM ten problem jest prosty do rozwiązania: wystarczy owinąć dwie operacje w transakcję, aby połączona operacja była atomowa. Jedynym punktem spornym jest to, że dla wywołującego, który nie jest świadomy szczegółów implementacji metod składowych, nie jest jasne, kiedy powinien podjąć próbę ponownego wykonania transakcji, jeśli się nie powiedzie. W odpowiedzi autorzy zaproponowali ponawiania , które wykorzystuje dziennik transakcji wygenerowany przez nieudaną transakcję do określenia, które komórki pamięci zostały odczytane, i automatycznie ponawia próbę transakcji, gdy jedna z tych komórek zostanie zmodyfikowana, w oparciu o logikę, że transakcja nie będzie się zachowywać inaczej, aż zmieni się przynajmniej jedna taka wartość.

Autorzy zaproponowali również mechanizm składania alternatyw , funkcję orElse . Uruchamia jedną transakcję, a jeśli ta transakcja ponawia próbę , uruchamia drugą. Jeśli obaj spróbują ponownie, spróbuje ponownie, gdy tylko zostanie wprowadzona odpowiednia zmiana. Ta funkcja, porównywalna z funkcjami takimi jak POSIX networking select() połączenie, pozwala dzwoniącemu czekać na jedno z wielu zdarzeń jednocześnie. Upraszcza również interfejsy programistyczne, na przykład udostępniając prosty mechanizm konwersji między operacjami blokującymi i nieblokującymi.

Schemat ten został zaimplementowany w kompilatorze Glasgow Haskell .

Proponowana obsługa języków

Konceptualna prostota STM umożliwia ich wystawienie na działanie programisty przy użyciu stosunkowo prostej składni języka. Tim Harris i Keir Fraser „Wsparcie językowe dla lekkich transakcji” zaproponowali pomysł wykorzystania klasycznego warunkowego regionu krytycznego (CCR) do reprezentowania transakcji. W najprostszej formie jest to po prostu „blok atomowy”, blok kodu, który logicznie pojawia się w jednej chwili:

  // Wstaw węzeł do listy podwójnie połączonej atomowo atomowo  {  newNode->prev = node; nowyWęzeł->następny = węzeł->następny;  węzeł->następny->poprzedni = nowywęzeł;  węzeł->następny = nowywęzeł;  }  

Po osiągnięciu końca bloku transakcja jest zatwierdzana, jeśli to możliwe, lub przerywana i ponawiana. (Jest to po prostu przykład koncepcyjny, a nie poprawny kod. Na przykład zachowuje się niepoprawnie, jeśli węzeł zostanie usunięty z listy podczas transakcji).

CCR zezwalają również na warunek ochronny , który pozwala transakcji czekać, aż będzie miała pracę do wykonania:

  atomic  (queueSize > 0) {usuń element z kolejki i użyj go} 

Jeśli warunek nie jest spełniony, menedżer transakcji zaczeka, aż inna transakcja dokona zatwierdzenia, które ma wpływ na warunek, przed ponowną próbą. To luźne powiązanie między producentami i konsumentami zwiększa modułowość w porównaniu z jawną sygnalizacją między wątkami. „Composable Memory Transactions” posunęło się o krok dalej dzięki ponowienia (omówione powyżej), które może w dowolnym momencie przerwać transakcję i poczekać, aż wartość wcześniej odczytana przez transakcję zostanie zmodyfikowana przed ponowną próbą. Na przykład:

  atomic  { if (queueSize > 0) { usuń element z kolejki i użyj go } else {  spróbuj ponownie  } } 

Ta możliwość dynamicznego ponawiania próby w późnym etapie transakcji upraszcza model programowania i otwiera nowe możliwości.

Jednym z problemów jest to, jak zachowują się wyjątki, gdy rozprzestrzeniają się poza transakcjami. W „Composable Memory Transactions” autorzy zdecydowali, że powinno to przerwać transakcję, ponieważ wyjątki zwykle wskazują na nieoczekiwane błędy w Concurrent Haskell, ale wyjątek może zachować informacje przydzielone i odczytane podczas transakcji do celów diagnostycznych. Podkreślają, że inne decyzje projektowe mogą być uzasadnione w innych ustawieniach.

Blokada transakcyjna

STM może być zaimplementowany jako algorytm bez blokad lub może wykorzystywać blokowanie. Istnieją dwa rodzaje schematów blokowania: W blokowaniu w czasie spotkania (Ennals, Saha i Harris) zapisy w pamięci są wykonywane przez tymczasowe uzyskanie blokady dla danej lokalizacji, bezpośrednie zapisanie wartości i zarejestrowanie jej w dzienniku cofania. Blokowanie w czasie zatwierdzania blokuje lokalizacje pamięci tylko podczas fazy zatwierdzania.

Schemat czasu zatwierdzenia o nazwie „Transactional Locking II” zaimplementowany przez Dice, Shalev i Shavit wykorzystuje zegar wersji globalnej. Każda transakcja rozpoczyna się od odczytania aktualnej wartości zegara i zapisania jej jako wersji do odczytu. Następnie przy każdym odczycie lub zapisie wersja określonej lokalizacji pamięci jest porównywana z wersją do odczytu; a jeśli jest większa, transakcja jest przerywana. Gwarantuje to wykonanie kodu na spójnej migawce pamięci. Podczas zatwierdzania wszystkie lokalizacje zapisu są blokowane, a numery wersji wszystkich lokalizacji odczytu i zapisu są ponownie sprawdzane. Na koniec zegar wersji globalnej jest zwiększany, nowe wartości zapisu z dziennika są zapisywane z powrotem do pamięci i oznaczane nową wersją zegara.

Coraz częściej stosowaną metodą zarządzania konfliktami transakcyjnymi w pamięci transakcyjnej , a zwłaszcza w STM, jest porządkowanie zobowiązań (zwane także porządkowaniem zobowiązań; CO). Jest on wykorzystywany do optymistycznego osiągania serializowalności (tj. bez blokowania po konflikcie, a jedynie blokowania do zatwierdzenia) przez „kolejność zatwierdzenia” (np. Ramadan i in. 2009 oraz Zhang i in. 2006). Serializowalność jest podstawą poprawności (transakcji współbieżnych i) pamięci transakcyjnej. Opublikowano już dziesiątki artykułów STM na temat „commit order”, a technika ta jest obciążona wieloma patentami.

W przypadku CO pożądaną właściwość serializowalności uzyskuje się przez zatwierdzanie transakcji tylko w porządku chronologicznym, który jest zgodny z porządkiem pierwszeństwa (określonym przez chronologiczne porządki operacji w konfliktach) odpowiednich transakcji. Aby wymusić CO, należy zastosować pewną implementację ogólnego algorytmu lokalnego CO . Cytowane powyżej streszczenie patentu opisuje ogólną implementację algorytmu z wcześniej określoną kolejnością zatwierdzania (należy to do kategorii „ogólnego algorytmu CO z ograniczeniami w czasie rzeczywistym”).

Kwestie implementacji

Jednym z problemów związanych z wdrażaniem programowej pamięci transakcyjnej z optymistycznym odczytem jest to, że niekompletna transakcja może odczytać niespójny stan (to znaczy odczytać mieszankę starych i nowych wartości zapisanych przez inną transakcję). Taka transakcja jest skazana na przerwanie, jeśli kiedykolwiek spróbuje się zatwierdzić, więc nie narusza to warunku spójności narzuconego przez system transakcyjny, ale możliwe jest, że ten „tymczasowy” niespójny stan spowoduje, że transakcja uruchomi fatalny warunek wyjątkowy, taki jak jako błąd segmentacji lub nawet wejść w nieskończoną pętlę, jak w poniższym wymyślonym przykładzie z rysunku 4 „Obsługa języków dla lekkich transakcji”:

atomic { if (x!= y) while (true) { } } atomowy { x++; y++; } Transakcja A Transakcja B

Pod warunkiem, że początkowo x = y , żadna z powyższych transakcji nie zmienia tego niezmiennika, ale możliwe jest, że transakcja A odczyta x po aktualizacji transakcji B, ale odczyta y przed aktualizacją transakcji B, co spowoduje wejście w nieskończoną pętlę. Zwykłą strategią radzenia sobie z tym jest przechwycenie wszelkich krytycznych wyjątków i przerwanie każdej transakcji, która nie jest ważna.

Jednym ze sposobów radzenia sobie z tymi problemami jest wykrywanie transakcji, które wykonują nielegalne operacje lub nie kończą się i przerywają je w czysty sposób; innym podejściem jest blokowania transakcyjnego .