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