Artykuł o STM na CodeGuru

Zebrałem swoje wszystkie wpisy na temat STM (z ang. Software Transaction Memory) i stworzyłem, chyba całkiem fajny, artykuł. Umieściłem go w jedynym sensownym i bardzo popularnym miejscu – mianowice na portalu CodeGuru. Choć nowych artykułów w portalu w tym roku nie było, to mam nadzieje, że przełamię lody i trochę ich tam teraz przybędzie.

Wspomnę także, że ruszył Club Online i za jakąkolwiek działalność na rzecz społeczności (news, artykuł, prelekcja) można zbierać punkty i wymieniać je na nagrody. Więcej informacji na tej stronie.

Dodałem także nową podstronę na blogu o dumnej nazwie „Articles„. Będę tam wstawiał linki do wszystkich swoich publikacji.

Zapraszam do czytania :)

Pamięć Transakcyjna – Istniejące implementacje – cz.2

W poprzednim poście przedstawiłem Wam kilka istniejących implementacji STM, a dzisiaj chciałbym dopełnić tę listę o kilka równie ważnych rozwiązań.

NSTM [2] to .NETowe rozwiązanie Ralfa Sudelbuchera, który na swoim blogu w kilku wpisach [1] 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:

  1. INstmObject<double> myAccount;
  2. INstmObject<double> yourAccount;
  3.  
  4. myAccount = NstmMemory.CreateObject(1000);
  5. yourAccount = NstmMemory.CreateObject(500);
  6.  
  7. using (INstmTransaction tx = NstmMemory.BeginTransaction())
  8. {
  9.    double amountToTransfer = 150;
  10.    myAccount.Write(myAccount.Read() – amountToTransfer);
  11.    yourAccount.Write(yourAccount.Read() + amountToTransfer);
  12.    tx.Commit();
  13. }

Kolejnym rozwiązaniem autorstwa trochę większego producenta niż jednoosobowy zespół Ralfa jest Intel® C++ STM Compiler, Prototype Edition 3.0 [3]. Na początek zachęcam do obejrzenia Flashowej prezentacji 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:

  1. include<stdio.h>
  2.  
  3. int xx = 0;
  4.  
  5. class Base {
  6.   public:
  7.   __declspec(tm_callable)
  8.   virtual void TxnAddOne() {
  9.     xx = xx + 1;
  10.   }
  11. };
  12.  
  13. class Virtual : public Base {
  14.   public:
  15.   __declspec(tm_callable)
  16.   void TxnAddOne() {
  17.     xx = xx + 1;
  18.   }
  19. };
  20.  
  21. int main() {
  22.   Base *x, *y;
  23.  
  24.   __tm_atomic {
  25.     x = new Base();
  26.     x->TxnAddOne();
  27.   }
  28.  
  29.   __tm_atomic {
  30.     y = new Virtual();
  31.     y->TxnAddOne();
  32.   }
  33. }

[Pobierz cały kod ze strony Intela]

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ść.

Był to ostatni wpis na temat Pamięci Transakcyjnej. W następnych postach z cyklu „Go Parallel, be Master” postaram się opisać kolejny sposób na tworzenie aplikacji równoległych, jednak tym razem z wykorzystaniem agentów oraz wiadomości. Zapraszam.

Źródła:

Promuj

Pamięć Transakcyjna – Istniejące implementacje – cz.1

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. W tym poście chciałbym omówić jedynie kilka.

Rozwiązanie, którego wydajność opisywałem w poprzednim poście, jest modyfikacją maszyny wirtualnej Javy. Dokładny opis znajduje się w dokumencie [1] oraz na tej stronie. 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ę tutaj [2]). Wersję 1.0 można pobrać tutaj [3], a wersję 1.1 tutaj [4]. 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 [3,4], 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. Historia tego produktu jest jednak o wiele bardziej ciekawa. STM.NET funkcjonował od jakiegoś czasu jako projekt na DevLab’ach, czyli wyżej w hierarchii niż MS Research. Blog zespołu tworzącego można śledzić tutaj nadal, mimo tego, że projekt został zakończony – tak można przeczytać na oficjalnej stronie rozwiązania – dnia 13 maja br. Dla programisty zostawiono jedynie podręcznik użytkownika. 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.

Według mnie projektu nie wycofano, bo był on mało przydatny. Myślę, że wejdzie on w skład Parallel Extensions w następnej wersji platformy – ale to tylko moje domysły. Dlaczego tak uważam? Wiadomo dokładnie, jak nazywał się plik, który był do pobrania w czasie trwania projektu (dotNetFx40_STMNet_10_x86.exe). Na zagranicznych portalach, na których był udostępniany, została po nim tylko notka, że usunięto zasób ze względu na prawa autorskie (zobacz). Ktoś się natrudził, aby to uczynić. Nie ustrzeżono się jednak błędów. Mimo usunięcia strony pobierania archiwa z przykładami i dokumentacją bezpośredni link do pliku działał jeszcze przez ponad miesiąc. Spragniony tego rozwiązania nadal szukam w czeluściach Internetu pliku ze zmodyfikowaną wersją platformy…

W następnym poście opiszę kolejne implementacje. Zapraszam.

Źródła:

Update, godz 14:30:

Z nieznanych mi przyczyn, podany link do zmodyfikowanej platformy, w serwisie depositfiles, zaczął nagle działać.

Promuj

Pamięć Transakcyjna – Wydajność

W poprzednich wpisach przedstawiłem Wam mechanizm Pamięci Transakcyjnej, a teraz chciałbym skupić się na jego wydajności 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

Źródła:

Promuj

Pamięć Transakcyjna – Od kuchni

W poprzednim poście wprowadziłem Was wstępnie w zagadnienie Pamięci Transakcyjnej. Dzisiaj kolejna porcja informacji na temat STM.

Pamiętacie przykład z Bankiem? Zależało nam, aby dwie operacje, debetowa oraz kredytowa, były wykonane, w kontekście jednej. Do tego celu zdefiniowaliśmy transakcje. Przypominam kod transferu:

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

Zgodnie założeniem transakcji (pamięci transakcyjnej) obydwie operacje powinniśmy umieścić w atomowym bloku.

  1. void transfer(account a1, account a2, double amount) {
  2.   atomic {
  3.     a1.debit(amount);
  4.     a2.credit(amount);
  5.   }
  6. }

Przypuśćmy, że w tym samym czasie wykonywane są setki transakcji. 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:

  1. boolean done = false;
  2. while (!done) {
  3.   STMStart ();
  4.   try {
  5.     if (condition) {
  6.       statements; //tutaj umieszcza się operacje
  7.       done = STMCommit ();
  8.     }
  9.     else {
  10.       STMWait();
  11.     }
  12.   }
  13.   catch (Throwable t) {
  14.     done = STMCommit ();
  15.     if (done) {
  16.       throw t;
  17.     }
  18.   }
  19. }

Więcej informacji o tym rozwiązaniu w dokumencie [1]. W kolejnym wpisie skoncentruję się na wydajności STM oraz porównam go ze zwykłym mechanizmem synchronizacji. Zapraszam.

Źródła:

Promuj

Pamięć Transakcyjna – Wstęp

Oto kolejny wpis mający przybliżyć moje imię do przedrostka mgr. W ostatnim poście przedstawiłem Wam wskazówki, skąd najlepiej czerpać informacje o rozwiązaniu Parallel Extensions. Dzisiaj chciałbym przedstawić kolejny mechanizm ułatwiający pisanie aplikacji równoległych – bardziej zaawansowany i wyszukany, a w dodatku jeszcze niestosowany w rozwiązaniach komercyjnych. Chodzi mianowicie  o Pamięć Transakcyjną.

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ć. 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, jeśli realizowane jest to w prawdziwych systemach bankowych? O tym w kolejnym wpisie. Zapraszam.

Źródła:

Promuj