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:
-
void transfer(account a1, account a2, double amount) {
-
a1.debit(amount);
-
a2.credit(amount);
-
}
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. 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) {
-
statements; //tutaj umieszcza się operacje
-
done = STMCommit ();
-
}
-
else {
-
STMWait();
-
}
-
}
-
catch (Throwable t) {
-
done = STMCommit ();
-
if (done) {
-
throw t;
-
}
-
}
-
}
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:
- [1] Language Support for Lightweight Transactions; Tim Harris, Keir Fraser, OOPSLA ’03
- [2] Transactions for Memory; Joe Duffy; MSDN Magazine, Jun 2003
- [3] Ralf’s Sudelbücher blog, STM tag
