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

Go Parallel, Be Master

Jeśli widzieliście moją prezentację o Programowaniu Równoległym, wiecie, że nie jest mi obcy temat równoległości, wielowątkowości i wieloprocesorowości, uff…. Teraz ta znajomość wchodzi na inny poziom. Moja praca magisterska, której obrona planowana jest na luty 2011 r., będzie ściśle powiązana z tym zagadnieniem. Tematem jest paralelizm aplikacji oraz jego weryfikacja. W skrócie: mam wymyślić, jak w możliwie automatyczny sposób zrównoleglić aplikację oraz w jaki sposób zweryfikować takie zrównoleglenie.

Pierwsza część polega na zbudowaniu narzędzia (prawdopodobnie pluginu do Visual Studio), który będzie podpowiadał programiście, które elementy kodu można zrównoleglić oraz jak to zrobić, używając znanych metod i rozwiązań. Druga część, ściśle powiązana z pierwszą, ma na celu zweryfikowanie, czy podział aplikacji na niezależne, równoległe ciągi instrukcji nie zmieni jego zachowania w każdym możliwym przypadku szeregowania; ma być to dowód formalny.

Jak widać, zagadnienie nie jest trywialne, więc na początek będę musiał się troszkę podszkolić, przekopać przez tony literatury i kodu źródłowego. W cyklu notek opatrzonych tagiem „magister” będę na bieżąco raportował moje postępy. Zatem zaczynajmy…

Jeśli chodzi o programowanie równoległe (używając tej nazwy, będą odnosił się jednocześnie do programowania wielowątkowego i wieloprocesorowego), to na samym początku należy opanować podstawy. Czym jest wątek, proces, deadlock, mutex, monitor? Nie będę tego opisywał, ale proponuję samodzielnie poczytać i pomyśleć. Dodatkowo polecam serię artykułów o wielowątkowości na blogu Piotra Zielińskiego. Zostały tam opisane wspomniane elementy oraz ich zastosowanie w środowisku .NET.

Celem pierwszego etapu mojej pracy jest zapoznanie się z możliwie jak największa liczbą zaawansowanych rozwiązań do kontroli/wprowadzania równoległości. Przez zaawansowane mam na myśli wszystko poza klasycznym mutexem, semaforem czy monitorem. Oczywiście w tych rozwiązaniach takie właśnie mechanizmy zostały użyte, ale głęboko, głęboko, pod maską. Programiście zostaje za to udostępniony zupełnie inny, bardziej przyjazny interfejs. Na początek Parallel Extensions…

Nie będę się powtarzał i odsyłam zainteresowanych do mojego artykułu na CodeGuru (część 1, bo 2 nigdy nie powstała – mój błąd). Opisuję tam podstawy tego rozwiązania, wyjaśniam, jak to naprawdę działa, i kiedy należy takie mechanizmy stosować. Dodatkowo zachęcam do subskrypcji blogu zespołu rozwijającego ten produkt – PFX Team. Przynajmniej raz na tydzień pojawia się nowa notka opisująca pewną funkcjonalność produktu. Wspomnieć należy również o Parallel Computing Developer Center w strukturach portalu MSDN. Zebrano tam dziesiątki artykułów, przykładów, screencastów i wywiadów z osobami odpowiedzialnymi za projekt. Polecam!

Na koniec warto wspomnieć o konkurencyjnym rozwiązaniu dla języków C/C++  – OpenMP.

Promuj

.NET w parze z PowerShellem

Jaki jest najszybszy sposób, aby sprawdzić, jak zbudowana jest dana klasa z BCL? Jakie ma metody, właściwości? Niektórzy z pewnością poproszą o pomoc wujka Google, który z chęcią przerzuci zainteresowanych na witrynę MSDN Library. Miejsce to oczywiście godne polecenia każdemu, bo jak mało która dokumentacja jest naprawdę szczegółowa. Ale co w sytuacji, gdy nie mamy dostępu do internetu? Najprostszym sposobem byłoby stworzenie na szybko jakiejś aplikacji, wpisanie nazwy klasy i IntelliSense powinien podpowiedzieć nam całą resztę. Sprytnie, ale trochę ciężko. Zaznajomieni ze środowiskiem Visual Studio wiedzą, że istnieje coś takiego, jak Object Browser dostępny z menu Tools. Narzędzie całkiem przydatne, a dodatkowo informuje, w jakim zestawie dostępna jest dana klasa. Ostatnim sposobem, na którym chciałbym się dziś skoncentrować, jest PowerShell. Jak prześwietlać klasy i jak ich używać w skryptach –  o tym w dalszej części. Spokojnie, znajomość super powłoki nie jest wymagana.

Aby zdobyć informację o danym typie, wystarczy wpisać jego pełną nazwę, tj. razem z namespacesem w nawiasach kwadratowych:

PS C:UsersWojtek [System.IO.DriveType]

IsPublic IsSerial Name      BaseType
-------- -------- ----      --------
True     True     DriveType System.Enum
 

Jak widać, nie dostaliśmy zbyt wielu cennych informacji . Do dyspozycji na szczęście mamy wszystkie metody, jakie udostępnia klasa System.Type. Np. GetConstructors(), GetMembers(), GetFileds() itp. W podanych zastosowaniach będę używał komendy Format-Table, która powoduje wyświetlenie tylko tych właściwości obiektów, jakie chcę zobaczyć.

PS C:UsersWojtek> [System.IO.DriveType].GetFields() | Format-Table Name

Name
----
value__
Unknown
NoRootDirectory
Removable
Fixed
Network
CDRom
Ram
 

Łatwo i szybko dostaliśmy wyliczenia danej enumeracji. Jeśli chcemy zobaczyć, w jaki sposób działa dana funkcja, możemy stworzyć obiekt dowolnej klasy, a następnie uruchamiać jego metody. Zobaczcie to na przykładzie StringBuildera:

PS C:UsersWojtek> $a = New-Object System.Text.StringBuilder
PS C:UsersWojtek> $a.Append("hej")

Capacity MaxCapacity Length
-------- ----------- ------
      16  2147483647      3

PS C:UsersWojtek> $a.Append(" ho")

Capacity MaxCapacity Length
-------- ----------- ------
      16  2147483647      6

PS C:UsersWojtek> $a.ToString()
hej ho
 

Po każdej zmianie obiektu wyświetlane są jego właściwości i jak na dłoni widać, co się zmieniło. Bardzo przydatna rzecz podczas poznawania nowych klas.

Możliwości PowerShella są naprawdę ogromne, sam z pewnością nie jestem świadomy istnienia połowy z nich. Niecierpliwych odsyłam do angielskiego bloga w którym znajdziecie mnóstwo przykładów wykorzystania PowerShella na platformie .NET, a ciekawskich zachęcam do eksperymentowania. Polecam PowerGUI jako podstawowy edytor PSa.

Promuj

Konfigurowalne obrazy z HTTP GETa

Temat postu z pewnością nie mówi Wam zbyt wiele, dlatego pozwolę sobie go wyjaśnić. W dzisiejszym wpisie chciałbym przedstawić Wam usługi, jakie zewnętrzne firmy dostarczają deweloperom aplikacji internetowych poprzez zwracanie obrazów z konfigurowalnych adresów URL. Mówiąc jaśniej, to, jaki obraz zostanie zwrócony, zależy od podanych w adresie parametrów.

Na samym początku przyjrzyjmy się usłudze mojego „ulubionego” dostawcy, wujka Google’a – Chart Tools. Jak sama nazwa wskazuje, na naszą stronę możemy wstawiać wszelkiego rodzaju wykresy. Dokładna dokumentacja znajduje się tutaj, a teraz krótki przykład:

http://chart.apis.google.com/chart?cht=p3&chd=s:Uf9a&chs=250x100&chl=January|February|March|April

Dla jasności pokolorowałem odpowiednie sekcje w adresie. Śmiało, skopiujcie go do swojej przeglądarki i zmieńcie np. nazwę miesiąca. Do dyspozycji mamy naprawdę szeroki wachlarz wykresów, ikon, a nawet możemy wstawiać równania matematyczne i kody QR.

http://chart.apis.google.com/chart?cht=tx&chl=x%20=%20%5Cfrac%7B-b%20%5Cpm%20%5Csqrt%20%7Bb%5E2-4ac%7D%7D%7B2a%7D

Tutaj jednak adres nie jest już tak oczywisty. Ze względu na ograniczenia w znakach adresu URL wymagane jest odpowiednie kodowanie. Google daje nam naturalnie pomocne narzędzie. Oprócz API do wykresów nasz potentat dostarcza również podobną funkcjonalność dla map – sprawdź Google Static Maps.

Drugi dostawca podobnych usług to yuml.me. W tym przypadku mamy możliwość generowania diagramów UML. Jak wiadomo, diagramy te mogą prezentować rożne rodzaje schematów, zatem dają się zastosować w naprawdę wielu sytuacjach. Popatrzmy na taki przykład:

http://yuml.me/diagram/scruffy/class/[Customer]-%3E[Billing%20Address]

Na stronie usługodawcy możecie zobaczyć kilkanaście innych, bardziej rozbudowanych przykładów. Możliwości są naprawdę spore.

Czy znacie więcej serwisów udostępniających podobne funkcjonalności? A może znacie nazwę tego rodzaju usług? Chętnie się o nich dowiem.

Promuj

Testowanie metod asynchronicznych w Javie

Jeśli w swoim życiu napisaliście już setki klas i tysiące metod, a nie stworzyliście jeszcze żadnego testu, to marni z Was developerzy. Testy jednostkowe są naprawdę pożytecznym narzędziem, bo choć wydłużają proces produkcji, jednocześnie powodują, że wartość końcowego produktu jest wielokrotnie większa, a Wy jesteście pewni, że Wasz produkt działa. Pisanie testów metod pobierających argumenty i zwracających wyniki, które można na podstawie tych argumentów zweryfikować, to kaszka z mleczkiem. Znacznie trudniej testować metody, które uruchamiają zadania w tle, a wyniki zwracają przez tzw. callbacki. Pokaże Wam, jak uporałem się z tym problemem.

Z pewnością zetknęliście się kiedyś z modułem, który wystawiał dwa publiczne interfejsy. Jeden z nich służył do zarządzania komponentem, natomiast drugi implementowaliście w celu uzyskania informacji zwrotnych z tego modułu. Takie API można znaleźć w  kodzie C++ znacznie częściej, aniżeli w Javie czy C#. Metoda interfejsu zarządzającego często nic nie zwraca, a jeżeli już, to jedynie kod informacyjny np. ‚operacja zaplanowana do wykonania’, albo ‚nie można wykonać’. Po pewnym czasie przychodzi odpowiedź w formie wywołania metody z interfejsu notyfikacji, który uprzednio zaimplementowaliśmy i przekazaliśmy do modułu. Test takiej metody powinien sprawdzać zwracany kod, czekać (ale nie nieskończenie długo) na przyjście odpowiedzi oraz zweryfikować przysłane w notyfikacji dane.  Przykładowy projekt takich interfejsów możecie znaleźć w moim repozytorium w pakiecie pl.fones.blog.asynctest.

Klasa Engine to interfejs zarządzający, EngineNotifcations to, rzecz jasna, interfejs powiadomień, EngineTest to testy naszego komponentu, dziedziczą po AsyncBaseTestCase, a te z kolei po JUnitowych test case’ach. Będziemy testować metodę start(), która zwraca swój wynik w notyfikacji engineStarted().

Cała logika testowania asynchronicznych metod zawarta jest w klasie AsyncBaseTestCase. Metody notifyCallback() oraz waitForCallback() powinny być wołane w naszym teście, jedna w zaimplementowanym na rzecz testu interfejsie notyfikacji, a druga – w samej metodzie testującej. Ich działanie opiera się na obiekcie CountDownLunch.  Metoda waitForCallback() czeka, aż wartość licznika tego obiektu będzie równa zero, a metoda notifyCallback() zmniejsza jego wartość domyślnie ustawioną na 1. Dodatkowe struktury służą do przekazania parametrów notyfikacji i informacji, czy dany callback w ogóle nastąpił. W ten sposób możemy ustawić, jaki maksymalny czas dajemy komponentowi na odpowiedź. Poprzez tablicę flag sprawdzamy, czy dana notyfikacja nastąpiła, a przez kolekcję rezultatów dowiadujemy się o przekazanych parametrach. Wszystko w bezpieczny, wielowątkowy sposób, z wykorzystaniem dostępnych metod synchronizacji.

Jeśli znacie inny sposób, który usprawniłby moje rozwiązanie, chętnie go poznam.

Prezentacja o Programowaniu Równoległym

We wrześniu 2008 roku w naszym dotnetowym kole działającym przy Wydziale Elektroniki i Technik Informacyjnych Politechniki Warszawskiej ustalaliśmy szczegóły organizacji wydarzenia IT Academic Day na naszej uczelni. Rafał Maciąg, przewodniczący koła, zaproponował, aby ktoś z nas przygotował coś na tę okazję. Oprócz prezentacji takich firm jak ABC Data, Kasperksy, K2, miała mieć miejsce jeszcze jedna, studencka.  Nie zgłosił się żaden chętny, a i mi trudno było wyobrazić siebie w takiej roli. Jedynym argumentem był fakt, że interesowałem się wtedy jeszcze dość egzotycznym zagadnieniem, jakim jest Programowanie Równoległe. Temat pasował idealnie. Decyzja zapadła.

Do dyspozycji miałem bardzo wczesną wersję biblioteki Parallel Extensions (Lipiec 2008), tworzonej jeszcze w ramach Microsoft Research. Przygotowałem prezentacje, dema, pytania (były nagrody), no i oczywiście przemowę. Tydzień przed wydarzeniem Microsoft wypuścił CTP (Community Technology Preview) środowiska Visual Studio 2010. Upieczemy dwie pieczenie na jednym ogniu, pomyślałem. Pierwsza publiczna demonstracja Visual Studio 2010 w Polsce przypadła właśnie mnie (nie słyszałem, żeby ktoś pokazał to środowisko wcześniej, w końcu ja zrobiłem to kilka dni po premierze, wybaczcie mi skromność). Na wydziałowym, 4 rdzeniowym serwerze, zamontowaliśmy wspólnie z Rafałem obraz, wykorzystując technologię Hyper-V, i wypuściliśmy zdalny pulpit na świat. Wszystko dopięliśmy na ostatni guzik. W dniu konferencji tłumów nie było, co nie zmniejszyło jednak stresu. Moja prezentacja była przedostatnia, za to poprzednie wystarczająco wysoko podniosły poprzeczkę. 3.. 2… 1… Start!

Jeden slajd, drugi… ani się obejrzałem, a zaczęło brakować mi czasu, miałem tylko godzinę. Ostatecznie nie pokazałem wszystkich dem, za to wszystkie dostępne nagrody (książki i office’y) rozdałem w mig! Kurcze, naprawdę mnie słuchali i znali odpowiedzi na podchwytliwe pytania, a myślałem, że zostanie coś dla mnie… Żartuję! Dzisiaj, ponad 1,5 roku po tym wydarzeniu, żałuję, że nie zagłębiłem się w temat programowania równoległego jeszcze bardziej. W tym momencie wiem niewiele więcej, a temat poszerzył się n-krotnie. Moja praca inżynierska była, rzecz jasna, ważniejsza. Ale uwaga… moja praca magisterska będzie się bardzo wiązać z tym zagadnieniem, a dokładnie, z weryfikacją aplikacji równoległych.

Z wydarzenia, oprócz doświadczenia w prezentacjach, został mi jeszcze power point, artykuł na codeguru (pierwsza część) oraz źródła przedstawianych aplikacji. Jeśli ktoś nie miał przyjemności pracować z biblioteką ParallelFX, myślę, że będzie to dobra lektura. Dodatkowo w prezentacji zawarłem animacje przedstawiające prace menadżera zadań TPL (Task Parallel Library). Polecam!

Załączniki:

Pamięć Transakcyjna - STM [502.94 kB]
Parallel Extensions Presentation [3.21 MB]

Promuj