Agent z wiadomo艣ci膮

Z implementacj膮 r贸wnoleg艂ych zada艅 mo偶na sobie poradzi膰 na wiele r贸偶nych sposob贸w. Zazwyczaj jednak instalujemy blokady, monitory, tworzymy transakcje, oplatamy synchroniczny kod. Cz艂owiek my艣li synchronicznie, dzia艂a synchronicznie i cz臋sto pisze – je艣li potrafi – synchroniczny kod. Co by si臋 jednak sta艂o, gdyby ca艂e takie podej艣cie odwr贸ci膰 do g贸ry nogami? Takich prze艂omowych projekt贸w by艂o wiele, oferowa艂y nowy model pisania r贸wnoleg艂ych aplikacji, bez pami臋ci wsp贸lnej i z wymian膮 komunikat贸w. Takie rozwi膮zanie, mimo szeregu ogranicze艅, jest bardzo skalowalne. Przejd藕my jednak do rzeczy. W dzisiejszym wpisie chcia艂bym przedstawi膰 Wam Model Agenta [1] (czasami zwany r贸wnie偶 – Modelem Aktora).

Ca艂a idea tego podej艣cia polega na wyodr臋bnieniu agent贸w/aktor贸w, kt贸rzy spe艂niaj膮 jak膮艣 logicznie pojedyncz膮 rol臋. Agenci nie dziel膮 mi臋dzy sob膮 偶adnych zasob贸w, chyba 偶e umiejscowieni s膮 w jednej domenie. Zasoby takiej domeny podlegaj膮 wtedy synchronizacji. Komunikacja mi臋dzy agentami odbywa si臋 poprzez wiadomo艣ci, kt贸re s膮 przekazywane – i tu uwaga – przez kopiowanie. W ten prosty spos贸b ka偶da domena mo偶e dzia艂a膰 r贸wnoleg艂e wzgl臋dem innej – cz臋sto bywa tak, 偶e w domenie jest tylko jeden agent.

Aby zastosowa膰 Model Agenta, najlepiej jest wyobrazi膰 sobie projektowan膮 aplikacj臋 jako – uwaga – osiedle. Ca艂a aplikacja to jedno, przedmiejskie osiedle z domkami i poczt膮 – tyle. W ka偶dym domku mieszka przynajmniej jeden agent/agentka – dom to w艂a艣nie domena. W domku z ka偶dego sprz臋tu (zasobu) mo偶e korzysta膰 tylko jeden agent – mieszkaj膮cy w tym domku (s膮siad nie mo偶e niczego dotyka膰). Mamy wi臋c synchronizacj臋 wewn膮trz domeny. Agenci komunikuj膮 si臋 ze sob膮 albo przez listy, kt贸re wk艂adaj膮 do skrzynki przed domkiem, a listonosz, zanosi je do odpowiedniej skrzynki adresata (listonosz jest w tym przypadku kana艂em), albo przez karteczki na lod贸wce (wsp贸ln膮 pami臋膰), kiedy komunikujemy si臋 z domownikiem (agentem w tym samym domu). Ka偶dy agent jest in偶ynierem w danej kategorii. W listach dostaje dane do pracy i w listach r贸wnie偶 odsy艂a wyniki. Je艣li dw贸ch agent贸w w domku potrzebuje wiertarki, to jeden musi poczeka膰, a偶 drugi sko艅czy swoj膮 prac臋. Dok艂adnie m贸wi膮c, ka偶dy domek dzia艂a w innym w膮tku, a osiedle uto偶samiane jest z jednym procesem. Oczywi艣cie, nic nie stoi na przeszkodzie komunikacji mi臋dzy innymi osiedlami :-)

Wiem 偶e, jest to do艣膰 du偶a abstrakcja, ale na sam pocz膮tek przygody z agentami powinna wystarczy膰. Jest tam te偶 kilka niedoci膮gni臋膰, ale my艣l臋, 偶e kiedy b臋d臋 omawia艂 implementacje, na wszystkie pytania, znajdzie si臋 odpowied藕.

Ka偶da implementacja posiada w艂asne smaczki, kt贸re wprowadzaj膮 pewne udogodnienia w聽platformie/j臋zyku, na jakie dane rozwi膮zanie jest kierowane. Cho膰 na rynku istnieje kilka implementacji kierowanych na platform臋 .NET, to聽w kolejnych wpisach, chcia艂bym si臋 skoncentrowa膰 jedynie na rozwi膮zaniu zaproponowanym przez Microsoft – Axum [2]. Zapraszam wkr贸tce.

殴r贸d艂a:

Promuj

Pami臋膰 Transakcyjna 鈥 Istniej膮ce implementacje 鈥 cz.2


Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /home/fones/public_html/blog.fones.pl/wp-content/plugins/source-code-syntax-highlighting-plugin-for-wordpress/geshi.php on line 2147

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /home/fones/public_html/blog.fones.pl/wp-content/plugins/source-code-syntax-highlighting-plugin-for-wordpress/geshi.php on line 2147

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /home/fones/public_html/blog.fones.pl/wp-content/plugins/source-code-syntax-highlighting-plugin-for-wordpress/geshi.php on line 2147

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /home/fones/public_html/blog.fones.pl/wp-content/plugins/source-code-syntax-highlighting-plugin-for-wordpress/geshi.php on line 2147

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /home/fones/public_html/blog.fones.pl/wp-content/plugins/source-code-syntax-highlighting-plugin-for-wordpress/geshi.php on line 2147

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /home/fones/public_html/blog.fones.pl/wp-content/plugins/source-code-syntax-highlighting-plugin-for-wordpress/geshi.php on line 2147

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /home/fones/public_html/blog.fones.pl/wp-content/plugins/source-code-syntax-highlighting-plugin-for-wordpress/geshi.php on line 2147

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /home/fones/public_html/blog.fones.pl/wp-content/plugins/source-code-syntax-highlighting-plugin-for-wordpress/geshi.php on line 2147

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /home/fones/public_html/blog.fones.pl/wp-content/plugins/source-code-syntax-highlighting-plugin-for-wordpress/geshi.php on line 2147

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.  

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.  

[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

Co ma wsp贸lnego Google i Europride?

Co mam wsp贸lnego Google, Android i Europride? Wszyscy s膮 dzisiaj w Warszawie. Marsz z Pl. Bankowego na Pl. Konstytucji si臋 jeszcze nie zako艅czy艂, ale ju偶 teraz przesy艂am Wam zdj臋cia platformy,聽 kt贸rej tam si臋 nie spodziewa艂em zobaczy膰 :) Chocia偶, Google zawsze propagowa艂o wolno艣膰…

Dodatkowo, je艣li w polskiej wersji wyszukiwarki, wpiszecie 'gej’ albo 'lesbijka’, na stronie z wynikami, pojawi si臋 charakterystyczna t臋cza, uto偶samiana z homoseksualizmem.

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


Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /home/fones/public_html/blog.fones.pl/wp-content/plugins/source-code-syntax-highlighting-plugin-for-wordpress/geshi.php on line 2147

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /home/fones/public_html/blog.fones.pl/wp-content/plugins/source-code-syntax-highlighting-plugin-for-wordpress/geshi.php on line 2147

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /home/fones/public_html/blog.fones.pl/wp-content/plugins/source-code-syntax-highlighting-plugin-for-wordpress/geshi.php on line 2147

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /home/fones/public_html/blog.fones.pl/wp-content/plugins/source-code-syntax-highlighting-plugin-for-wordpress/geshi.php on line 2147

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /home/fones/public_html/blog.fones.pl/wp-content/plugins/source-code-syntax-highlighting-plugin-for-wordpress/geshi.php on line 2147

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /home/fones/public_html/blog.fones.pl/wp-content/plugins/source-code-syntax-highlighting-plugin-for-wordpress/geshi.php on line 2147

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /home/fones/public_html/blog.fones.pl/wp-content/plugins/source-code-syntax-highlighting-plugin-for-wordpress/geshi.php on line 2147

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /home/fones/public_html/blog.fones.pl/wp-content/plugins/source-code-syntax-highlighting-plugin-for-wordpress/geshi.php on line 2147

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /home/fones/public_html/blog.fones.pl/wp-content/plugins/source-code-syntax-highlighting-plugin-for-wordpress/geshi.php on line 2147

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /home/fones/public_html/blog.fones.pl/wp-content/plugins/source-code-syntax-highlighting-plugin-for-wordpress/geshi.php on line 2147

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /home/fones/public_html/blog.fones.pl/wp-content/plugins/source-code-syntax-highlighting-plugin-for-wordpress/geshi.php on line 2147

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /home/fones/public_html/blog.fones.pl/wp-content/plugins/source-code-syntax-highlighting-plugin-for-wordpress/geshi.php on line 2147

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /home/fones/public_html/blog.fones.pl/wp-content/plugins/source-code-syntax-highlighting-plugin-for-wordpress/geshi.php on line 2147

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.  

Zgodnie za艂o偶eniem transakcji (pami臋ci transakcyjnej) obydwie operacje powinni艣my umie艣ci膰 w atomowym bloku.

  1.  

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. span class=”co1″>//tutaj umieszcza si臋 operacje

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

Microsoft Biology Foundation

Microsoft Research opublikowa艂 pierwsz膮 wersj臋 Biology Foundation – zestawu narz臋dzi kierowanych do聽specjalist贸w od bioinformatyki, kt贸re stanowi rozszerzenie dla platformy .NET. Pierwsza wersja zawiera zbi贸r parser贸w, umo偶liwiaj膮cych czytanie z popularnych format贸w wykorzystywanych w bioinformatyce, a tak偶e zestaw algorytm贸w do manipulowania DNA, RNA oraz sekwencj膮 bia艂ek. Ponadto rozszerzenie zawiera connectory do biolgicznych web serwis贸w takich jak NCBI BLAST.

Pisz臋 o tym, poniewa偶 wiekszo艣膰 zaimplementowanych algorytm贸w w tej bibliotece wykorzystuje potencja艂 Parallel Extensions. Algorytmy takie daj膮 si臋 艂atwo zr贸wnolegli膰, poniewa偶 zawieraj膮 etapy, kt贸re mo偶na podzieli膰 na mniejsze niezale偶ne cz臋艣ci, mog膮ce zachodzi膰 r贸wnolegle.

Zapraszam na stron臋 projektu.

殴r贸d艂o:聽MSDN Blogs > External Research Team Blog

Promuj