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: