BETA
Aby się zalogować, najpiew wybierz portal.
Aby się zarejestrować, najpiew wybierz portal.
Podaj słowa kluczowe
Słowa kluczowe muszą mieć co najmniej 3 sąsiadujące znaki alfanumeryczne
Pole zawiera niedozwolone znaki

Baza wiedzy











Pamięć Transakcyjna - STM

23-07-2010 11:01 | Wojciech Grześkowiak
STM (z ang. Software Transaction Memory) to podejście zaczerpnięte od kolegów z baz danych. Skoro na jednej instancji bazy danych może pracować kilku klientów, to należy ich pracę w pewien sposób synchronizować, tak aby nie przeszkadzali sobie nawzajem. W tym celu wprowadzono transakcje. Idea jest bardzo prosta: albo wszystkie instrukcje w danej transakcji wykonają się poprawnie, albo żadna z nich nie powinna się wykonać. Taki pomysł chciano wprowadzić w języku programowania, zoba

STM (z ang. Software Transactional Memory) to podejście zaczerpnięte od kolegów z baz danych. Skoro na jednej instancji bazy danych może pracować kilku klientów, to należy ich pracę w pewien sposób synchronizować, tak aby nie przeszkadzali sobie nawzajem. W tym celu wprowadzono transakcje. Idea jest bardzo prosta: albo wszystkie instrukcje w danej transakcji wykonają się poprawnie, albo żadna z nich nie powinna się wykonać. Cecha ta określana jest jako niepodzielność. Głównych cech jest w sumie 4. Pozostałe to spójność (transakcja nie narusza niezmienników systemowych), izolacja (częściowe zmiany dokonane w środku transakcji nie są widziane na zewnątrz) oraz stałość (po ukończeniu transakcji zmiany zapisywane są na stałe i stają się wtedy widoczne dla innych). Taką ideę chciano wprowadzić w języku programowania, wykorzystując bardzo prosty zapis:

atomic {
 instrukcja1;
 instrukcja2;
}

Wszystkie instrukcje wykonają się poprawnie albo żadna z nich nie wykona się w ogóle. Co to oznacza? Jeżeli w pewnej chwili natrafimy na taki moment, że transakcja nie może być kontynuowana, zostaje ona wycofana i ponowiona, a skutki wykonania instrukcji, które zdążyły się wykonać, zostają wycofane. Brzmi niewiarygodnie? Jak to wykorzystać w programowaniu równoległym? Jakie są ograniczenia, a jakie możliwości? O tym w dalszej części artykułu.

Temat jest obszerny i nie sposób napisać tu o tym wszystkim, co chciałbym Wam przekazać. Postaram się skupić na najważniejszych faktach i wierzę, że skorzystacie z podanych linków, aby zaspokoić swoją ciekawość. Na początku najlepiej będzie posłużyć się przykładem Banku - sztandarowym, jeżeli chodzi o STM. W owym banku realizowany jest przelew pieniężny z jednego konta na drugie. Oto przykładowa funkcja (pominięto kod sprawdzający parametry, aktualny stan itp.):

void transfer(account a1, account a2, double amount) {
 a1.debit(amount);
 a2.credit(amount);
}

Jak wiadomo, w banku odbywają się setki, tysiące transakcji na sekundę. Wszystkie transakcje nie odbywają się w jednym wątku/procesie, więc potrzebna jest synchronizacja, aby żadnemu klientowi banku nie zginęły pieniążki. Na pierwszy (błędny) rzut oka można zastosować monitor na banku i nie dopuścić, aby żadne dwie transakcje wykonywały się w tym samym momencie. OK? Ale przez to nie możemy w tym samym momencie wykonać przelewu z A do B i z C do D. Wydajność takiego systemu transakcyjnego byłaby bardzo słaba. Kolejnym pomysłem byłoby zastosowanie monitorów na obiektach poszczególnych kont. Jednak powstaje kolejny problem: jeśli obciążymy jedno konto (wykonamy debit, ale jeszcze nie credit), i nastąpi przełączenie kontekstu wątku, w którym wykonywano ten transfer, to pieniądze w pewnej chwili nie znajdowałby się na żadnym z tych kont, a taka sytuacja z punktu widzenia banku jest niedopuszczalna. Inny pomysł: użyjmy semaforów/blokad w następujący sposób:

void transfer(account a1, account a2, double amount) {
 lock(a1) {
  lock(a2) {
   a1.debit(amount);
   a2.credit(amount);
  }
 }
}

Wydaje się sensowne, ale zaraz, zaraz: czy możemy się zakleszczyć (deadlock)? Naturalnie, wystarczy, że w tym samym momencie wykonamy przelew z A1 na A2 i z A2 na A1. Kiepskie rozwiązanie. A jeśli bank chce operować na więcej niż dwóch kontach jednocześnie? W ten sposób powstaje co raz więcej problemów do rozwiązania. W jaki sposób rozwiązać zatem ten problem?

Zależ nam, aby dwie operacje, debetowa oraz kredytowa, były wykonane, w kontekście jednej. Do tego celu zdefiniujmy transakcje. Zgodnie założeniem transakcji (pamięci transakcyjnej) obydwie operacje powinniśmy umieścić w atomowym bloku.

void transfer(account a1, account a2, double amount) {
  atomic {
    a1.debit(amount);
    a2.credit(amount);
  }
}

Przypuśćmy, że w tym samym czasie wykonywane są setki transakcji jednocześnie. Niektóre z nich używają tych samych kont bankowych. W takim przypadku transakcja powinna zachowywać się w następujący sposób: po wejściu w atmowy blok nic specjalnego nie powinno się wydarzyć. Pierwsza instrukcja - debetowa - modyfikuje stan konta, ale w taki sposób, że zmienione saldo tego konta widoczne jest jedynie wewnątrz transakcji (wewnątrz bloku atomic), a nie na zewnątrz. W podobny sposób wykonywana jest metoda kredytująca. Jeżeli mechnizm STM wykryje, że jakaś instrukcja modyfikuje/pobiera dane, które zmieniły się od chwili wejścia w blok atomowy, wszystkie instrukcje wykonane w tym bloku są wycofywane, a transakcja rozpoczyna się ponownie. Jeśli cała transakcja przebiegła poprawnie (bez wykrycia kolizji), to na końcu atomowego bloku zmienione dane są zatwierdzane (wykonany jest commit) i od tej chwili są widoczne dla wszystkich. Jak widać, założenie pamięci transakcyjnej jest bardzo optymistyczne.

Pewnie zadajecie sobie teraz pytanie, w jaki sposób wycofywać operacje? I słusznie. Oczywiście, w przypadku niektórych metod można zdefiniować "metodę wsteczną", ale w ten sposób nie uzyskamy izolacji, jednej z czterech własności transakcji, a ponadto nadal będziemy zmagać się z wyścigami. Właśnie dlatego STM bardzo trudno zaimplementować jako zewnętrzną bibliotekę, ponieważ mechanizm ten musi być ściśle powiązany ze środowiskiem wykonawczym.

Każdy odczyt oraz każdy zapis w atomowym bloku powinien być umieszczany w logu. Wpisy te posłużą albo do wycofania transakcji, albo do jej zatwierdzania. Zarządzanie takim logiem jest kluczowym aspektem w mechnizmie STM. Drugą ważną kwestią jest wykrywanie konfliktów, podczas których transakcja powinna być wycofana.

Istnieją dwie metody implementacji STM: z blokowaniem lub bez, czyli podobnie jak w mechanizmie synchronizacji. Jeden z pierwszych pomysłów, opisany w dokumencie [1], przedstawia implementację STM dla języka Java. Ograniczeniem w tym rozwiązaniu jest możliwość operowania jedynie na danych długości jednego słowa. Używa się w nim dodatkowych struktur, które przechowują informacje o transakcji. Sam atomowy blok przedstawiony jest następująco:

boolean done = false;
while (!done) {
  STMStart ();
  try {
    if (condition) {
      //tutaj umieszcza się operacje
      done = STMCommit ();
    }
    else {
      STMWait();
    }
  }
  catch (Throwable t) {
    done = STMCommit ();
    if (done) {
      throw t;
    }
  }
}

W kolejnej części artykułu chcialbym skupić się na wydajności transakcji względem zwykłych metod synchronizacji. Niestety pod biurkiem nie posiadam maszyny z kilkunastoma procesorami, dlatego w całej mierze opieram się na badaniu opisanym w dokumencie [1].

Przeprowadzono dwa rodzaje testów (w dokumencie opisano jeden więcej) na dwóch rodzajach maszyn. Obydwa testy polegały na konkurencyjnym dostępie do różnie zaimplementowanej hashmapy. Pierwsza maszyna, na jakiej przeprowadzano testy, miała jedynie 4 procesory, druga zaś miała ich aż 106! (to był rok 2003). W obu testach sukcesywnie zwiększano liczbę dostępnych jednostek.

Porównano 3 różne implementacje Hashmapy. Pierwsza jest standardowo dostępna w pakiecie java.util, HaspMap<K,V>, którą przed współbieżnym dostępem chroni pojedynczy mutex. Druga - z pakietu java.util.concurrent, ConcurrentHashMap<K,V>, zaimplementowana o wiele sprytniej, umożliwiająca m.in. jednoczesne czytanie. Ostatnia implementacja to zmodyfikowana wersja podstawowej hashmapy, w której usunięto mutex, a odpowiednie sekcje opatrzono transakcjami.

Pierwszy test polega na równoczesnym czytaniu i uaktualnianiu wpisów w 4096-elementowej hashmapie. Wyróżniono dwa przypadki: w pierwszym 1% wpisów uaktualniano, a 99% czytano, natomiast w drugim 16% zmieniano, a 84% czytano. Wyniki z 4 procesorowej maszyny (rysunek 1, tabela na górze) wskazują, że najlepszą implementacje miała hashmapa z pakietu java.util.concurrency. Autorzy tłumaczą, że to rozwiązanie jest o wiele bardziej zintegrowane z platformą niż ich własne, a ponadto operacje na kolekcji wykonywane były jedna po drugiej, wykorzystując 100% mocy, a taki przypadek jest mało prawdopodobny w realnych rozwiązaniach.

Inaczej sytuacja wygląda na maszynie ze 106 procesorami. Przy 1% zapisie rozwiązanie wykorzystujące transakcje wygrywało, ale dopiero przy 30 równoległych procesorach. Wytłumaczenie, jakie przytaczali badacze, odnosi się do narzutu spowodowanego zarządzaniem transakcjami. Przy małej ilości równoległych zapisów narzut ten powodował przegraną transakcji. Jednak przy dużej ilości równoległych operacji, transakcje były o tyle bardziej wydajne od java.util.concurrency, że dodatkowy narzut nie przeszkadzał w wygranej. Pamiętajmy, że rozwiązanie z pakietu java.util.concurency pozwala równocześnie czytać, a w rozwiązaniu transakcyjnym czytanie wywołuje zarządzanie transakcjami. Przy 16% uaktualnianiu transakcje wygrywały już od 5 równoległych procesów, ale w takim stopniu, jak Formuła 1 z Fiatem 126p na 1/4 mili. Prezentują to wykresy a i b na rysunku 2. We wszystkich przypadkach rozwiązanie z pojedynczym mutexem można porównać do ślimaka.

Drugi rodzaj testów polegał na równoległych operacjach "swap". Wybierano dwa klucze z tablicy hashującej, a następnie zamieniano wartości, na które te klucze się mapowały. Założenie było takie, aby taka operacja była atonomiczna. Pierwsze rozwiązanie, podobnie jak w teście pierwszym, bazowało na pojedynczym mutexie, natomiast w drugiej implementacji (java.util.concurrency) dodano blokady per klucz, a w trzecim przypadku, znów podobnie, użyto transakcji. Do testu użyto map wielkości 256 oraz 4096.

W przypadku więcej niż jednego procesora rozwiązanie z transakcjami bije na głowę pojedynczą blokadę. W porównaniu ze współbieżną hashmapą transakcje wypadają gorzej dla malej liczby procesorów (rysunek 1, tabela na dole). W przypadku maszyny z setką procesorów, wyraźnie widać przewagę transkacji nad pozostałymi metodami. Spowodowane jest to faktem, że niekolidujące aktualizacje mogą być faktycznie wykonywane równolegle, kiedy przy współbieżnej hashmapie procesy walczą o jedną blokadę (rysunek 2, wykresy c i d).

Podsumowując, jeżeli operacje na kolekcji wykonywane są równolegle, a prawdopodobieństwo tego, że procesy będą korzystać z tych samych pól, jest małe, transakcje wykazują znaczącą przewagę nad pozostałymi metodami synchronizacji. Operacje takie mogą faktycznie wykonywać się równoległe, a narzut spowodowany obsługą transakcji jest relatywnie bardzo mały w stosunku do zyskanej wydajności.

W przypadku niejasności odsyłam zainteresowany do lektury dokumentu [1].


Rysunek 1, Maszyna 4 rdzeniowa


Rysunek 2, Maszyna 106 rdzeniowa

W kolejnej części atrykułu, chciałbym się skupić na istniejących implementacjach STM.

Na rynku istnieje wiele rozwiązań implementująych STM - zdziwilibyście się, jak wiele. Są to rozszerzenia dla więkoszści języków: zaczynając od C, przez C++, C#, Java, Haskell, Perl. Dość pokaźna lista znajduje się w wikipedii [3]. W tym poście chciałbym omówić jedynie kilka.

Rozwiązanie, którego wydajność opisywałem w na początku artykułu, jest modyfikacją maszyny wirtualnej Javy. Dokładny opis znajduje się w dokumencie [1] oraz na stronie autorów [2]. Można pobrać przykładowy kod i spróbować samemu uruchomić to rozwiązanie.

Drugie rozwiązanie, jakie chciałbym zaprezentować, zostało stworzone w laboratoriach Microsoft Research (prawdopodobnie przy pomocy Brown University), i nosi nazwę SXM (dokumentacja znajduje się pod odnośnikiem [4]). Wersję 1.0 można pobrać pod adresem [5], a wersję 1.1 pod adresem [6]. Jest to implementacja na platformę .NET w postaci specjalnej biblioteki. Zamysł jest prosty: klasy, których chcemy używać równolegle, musimy zarejestrować w fabryce obiektów i dzięki tej fabryce musimy te obiekty tworzyć. Właściwości, których będziemy używać, należy dodatkowo opatrzyć specjalnym atrybutem. Fabryka dynamicznie tworzy podklasę i opakowuje atrybuty w specjalne wywołania - to są właśnie atonomiczne bloki. Dynamiczne tworzenie podklas możliwe jest dzięki mechanizmom z przestrzeni nazw System.Reflection.Emit. Ponadto kod źródłowy SXM, która można pobrać z podanych linków [5,6], zorganizowany jest jako benchmark. Zawiera dwie różne implementacje fabryk, nakłaniając programistę do napisania swojej i sprawdzenia jej wydajności z istniejącymi.

Kolejne rozwiązanie, również na platformę microsoftu, to STM.NET. Można śmiało założyć, że SXM był pierwowzorem, na którym bazowali inżynierowie tworzący STM.NET. STM.NET funkcjonował od jakiegoś czasu jako projekt na DevLab'ach, czyli wyżej w hierarchii niż SMX, w MS Research. Blog zespołu tworzącego można śledzić pod adresem [7], nadal, mimo tego, że projekt został zakończony - tak można przeczytać na oficjalnej stronie rozwiązania [8] - dnia 13 maja 2010 roku. Dla programisty zostawiono jedynie podręcznik użytkownika [9]. Rozwiązanie to nie było biblioteką, a zmodyfikowaną wersją platformy .NET 4 beta 1. Jak wiemy, mechanizm transakcji najlepiej sprawdzi się wtedy, kiedy będzie na stałe zintegrowany z platformą, na jaką został napisany - tak właśnie uczynili inżynierowie.

NSTM [2] to .NETowe rozwiązanie Ralfa Sudelbuchera, który na swoim blogu [11] w kilku wpisach [12] wyjaśnia dokładnie, w jaki sposób z niego korzystać. Tak jak poprzednio opisywane rozwiązania, NSTM opakowuje obiekty, ale w inny sposób, niż robi to np. SXM - opakowując wskazane metody i właściwości obiektu. NSTM trzyma wewnątrz fasady obiekt danej klasy, może go nam zwrócić (zapisze to wtedy w logu) i wtedy mamy możliwość jego modyfikacji, ale nastepnie należy go znów w całości zapisać. Przykład ze strony Ralfa:

INstmObject<double> myAccount;
INstmObject<double> yourAccount;

myAccount = NstmMemory.CreateObject(1000);
yourAccount = NstmMemory.CreateObject(500);

using (INstmTransaction tx = NstmMemory.BeginTransaction())
{
   double amountToTransfer = 150;
   myAccount.Write(myAccount.Read() - amountToTransfer);
   yourAccount.Write(yourAccount.Read() + amountToTransfer);
   tx.Commit();
}

Kolejnym rozwiązaniem autorstwa trochę większego producenta niż jednoosobowy zespół Ralfa jest Intel® C++ STM Compiler, Prototype Edition 3.0 [13]. Na początek zachęcam do obejrzenia Flashowej prezentacji [14] omawiającej problem transakcji. Choć wszystkie napisy w owej prezentacji brzmią "undefined", to animacja przedstawiona na rysunku obok doskonale tłumaczy zasady STM. Wracając jednak do samego rozwiązania. Środowisko to oczywiście C++. Odpowiednie metody klas (te, których chcemy używać w transakcji) należy opatrzyć atrybutem __declspec(tm_callable), samą transakcję deklarujemy przy pomocy bloku __declspec(tm_callable). Przykład ze strony producenta, w powiązaniu z OpenMP:

include<stdio.h>

int xx = 0;

class Base {
  public:
  __declspec(tm_callable)
  virtual void TxnAddOne() {
    xx = xx + 1;
  }
};

class Virtual : public Base {
  public:
  __declspec(tm_callable)
  void TxnAddOne() {
    xx = xx + 1;
  }
};

int main() {
  Base *x, *y;

  __tm_atomic {
    x = new Base();
    x->TxnAddOne();
  }

  __tm_atomic {
    y = new Virtual();
    y->TxnAddOne();
  }
}

Pobierz cały kod ze strony Intela [15]

Na rozwiązaniu Intela chciałbym zakończyć przedstawianie implementacji STM. Większość tych, które nie zostały omówione, nie była uaktualniana od kilku lat, a jak wiemy, w branży IT 2-3 lata to przepaść.

Podsumowując, transakcje są naprawdę ciekawym rozwiązaniem, i w miarę zwiększania równoległości aplikacji, mogą odegrać znaczącą rolę. Brak jest jednak ustandaryzowanych konstrukcji, które połączyłyby wszystkie implementacje. Ścisłe powiązanie z platformą, daje największe szanse przenośnym rozwiązaniom, takim jak Java, czy .NET. Należy pamiętać, że STMu nie można korzystać, w każdym współbieżnym przypadku, najlepiej sprawdza się w algorytmach z mało prawdopodobnymi konfliktami.

Źródła:

Artykuł powstał na podstawie wpisów na moim blogu.

Podobne artykuły

Komentarze 0

pkt.

Zaloguj się lub Zarejestruj się aby wykonać tę czynność.