Multi-threading bez blokady jest dla prawdziwych ekspertów od gwintowania

Obecne implementacje typu "lock-free" przez większość czasu podążają za tym samym wzorcem:

• *przeczytaj jakiś stan i zrób jego kopię * *
• *modify copy * *
• wykonaj operację z blokadą
• spróbuj ponownie, jeśli się nie powiedzie

_{(*opcjonalnie: zależy od struktury danych / algorytmu)}

Ostatni bit jest niesamowicie podobny do spinlocka. W rzeczywistości jest to podstawowy spinlock. :)
Zgadzam się z @nobugz w tej kwestii: koszt połączenia operacje używane w wielowątkowości bez blokady są zdominowane przez zadania cache i memory-coherency, które musi wykonywać.

to, co zyskujesz dzięki strukturze danych, która jest "wolna od blokad", to to, że Twoje" blokady " są bardzo drobnoziarniste. Zmniejsza to prawdopodobieństwo, że dwa równoległe wątki uzyskają dostęp do tej samej "blokady" (lokalizacji pamięci).

Sztuczka najczęściej polega na tym, że nie masz dedykowanych blokad - zamiast tego traktujesz np. wszystkie elementy w tablicy lub wszystkie węzły w powiązanej liście jako "spin-lock". Czytasz, modyfikujesz i próbujesz zaktualizować, jeśli nie było aktualizacji od ostatniego czytania. Jeśli tak, spróbuj ponownie.
To sprawia, że "blokowanie" (oh, sorry, non-locking :) jest bardzo drobnoziarniste, bez wprowadzania dodatkowych wymagań dotyczących pamięci lub zasobów.
Czyniąc go bardziej drobnoziarnistym zmniejsza prawdopodobieństwo oczekiwania. Wykonanie go tak drobnoziarnistego, jak to tylko możliwe, bez wprowadzania dodatkowych wymagań dotyczących zasobów brzmi świetnie, prawda?

Większość zabawy jednak może pochodzić z zapewniając prawidłowe ładowanie / zamawianie sklepu .
Wbrew własnej intuicji, procesory mogą dowolnie zmieniać kolejność odczytów/zapisów pamięci - przy okazji są bardzo inteligentne: będziesz miał problem z obserwacją tego z jednego wątku. Pojawią się jednak problemy, gdy zaczniesz robić wielowątkowość na wielu rdzeniach. Twoja intuicja ulegnie załamaniu: to, że instrukcja jest wcześniej w Twoim kodzie, nie oznacza, że faktycznie stanie się wcześniej. Procesory mogą przetwarzać instrukcje nie w porządku: a szczególnie lubią to robić instrukcje z dostępem do pamięci, aby ukryć opóźnienie pamięci głównej i lepiej wykorzystać ich pamięć podręczną.

Teraz, jest pewne wbrew intuicji, że sekwencja kodu nie płynie "z góry na dół", zamiast tego biegnie tak, jakby w ogóle nie było sekwencji - i może być nazywana "devil' s playground". Uważam, że nie jest możliwe podanie dokładnej odpowiedzi na to, jakie zmiany w ładowaniu/przechowywaniu będą miały miejsce. Zamiast tego zawsze mówi się w kategoriach mays i mights i puszki i przygotować się na najgorsze. "Och, procesor Może zmienić kolejność odczytu, aby przyszedł przed tym zapisem, więc najlepiej jest umieścić barierę pamięci tutaj, w tym miejscu."

Sprawy komplikuje fakt, że nawet te mays i mights mogą się różnić w zależności od architektury procesora. Może to być na przykład przypadek, że coś, co jest {15]}gwarantowane, że nie wydarzy się {16]} w jednej architekturze może się zdarzyć na innym.

---

Aby uzyskać" bez blokady " wielowątkowość, musisz zrozumieć modele pamięci.
Uzyskanie poprawnego modelu pamięci i gwarancji nie jest jednak trywialne, o czym świadczy ta historia, w której Intel i AMD wprowadzili pewne poprawki do dokumentacji MFENCE, powodując pewne zamieszanie wśród programistów JVM. Jak się okazało, dokumentacja, na której od początku opierali się programiści, nie była tak precyzyjna w pierwszym miejsce.

Blokady w. NET powodują ukrytą barierę pamięci, dzięki czemu możesz bezpiecznie z nich korzystać (przez większość czasu, czyli... zobacz na przykład to Joe Duffy-Brad Abrams-Vance Morrison wielkość na leniwe inicjalizacji, zamki, lotnych i bariery pamięci. :) (Pamiętaj, aby podążać za linkami na tej stronie.)

[1]} jako dodatkowy bonus, poznasz model pamięci. NET podczas zadania pobocznego [21]}. :) Jest też "oldie but goldie" z Vance ' a Morrison: Co Każdy Dev Musi Wiedzieć O Wielowątkowych Aplikacjach .

...i oczywiście, jak @Eric wspomniał, Joe Duffy jest definitywną lekturą na ten temat.

Dobry STM może zbliżyć się do drobnoziarnistego blokowania i prawdopodobnie zapewni wydajność zbliżoną lub dorównującą ręcznie wykonanej implementacji. Jednym z nich jest STM.NET z DevLabs projects Z MS.

Jeśli nie jesteś fanatykiem. NET, Doug Lea wykonał świetną robotę w JSR-166 .
Cliff Click ma ciekawe podejście do tabel hashowych, które nie polegają na blokowaniu pasków-jak to robią równoległe tabele hashowe Java i. NET - i wydają się dobrze skalować do 750 procesorów.

Jeśli nie boisz się wkroczyć na terytorium Linuksa, poniższy artykuł zawiera więcej informacji na temat wewnętrznych aspektów obecnych architektur pamięci i tego, jak współdzielenie pamięci podręcznej może zniszczyć wydajność: co każdy programista powinien wiedzieć o pamięci .

@Ben poczynił wiele komentarzy na temat MPI: szczerze zgadzam się, że MPI może zabłysnąć w niektórych obszarach. Rozwiązanie oparte na MPI może być łatwiejsze do zrozumienia, łatwiejsze do wdrożenia i mniej podatne na błędy niż na wpół upieczona implementacja blokowania, która stara się być inteligentna. (Dotyczy to jednak-subiektywnie-również rozwiązania opartego na STM.) Założę się też, że latami świetlnymi łatwiej jest poprawnie napisać porządną rozproszoną aplikację w np. Erlang, jak wiele udanych przykłady sugerują.

MPI ma jednak własne koszty i własne problemy, gdy jest uruchamiany na pojedynczym, wielordzeniowym systemie. Na przykład w Erlang, istnieją problemy do rozwiązania wokół synchronizacji harmonogramu procesów i kolejek wiadomości.
Ponadto, systemy MPI zazwyczaj implementują rodzaj współpracy N:m scheduling dla "lekkich procesów". Oznacza to na przykład, że istnieje nieunikniona zmiana kontekstu między lekkimi procesy. To prawda, że nie jest to "klasyczny przełącznik kontekstowy", ale przede wszystkim operacja przestrzeni użytkownika i może być wykonana szybko - jednak szczerze wątpię, że może być przeprowadzona w ramach 20-200 cykli operacja zblokowana trwa. Przełączanie kontekstu w trybie użytkownika jest z pewnością wolniejsze nawet w Bibliotece Intel McRT. Planowanie N: M z lekkimi procesami nie jest nowością. LWP były tam przez długi czas w Solarisie. Zostały porzucone. W NT były włókna. Są to obecnie głównie relikt. W NetBSD były "aktywacje". Zostały porzucone. Linux miał swoje własne podejście do tematu N: m threading. Wygląda na to, że już nie żyje.
Od czasu do czasu pojawiają się nowe pretendenty: na przykład McRT od Intela, lub ostatnio user-Mode Scheduling wraz z ConCRT od Microsoftu.
Na najniższym poziomie robią to, co robi n: M MPI scheduler. Erlang - lub dowolny system MPI -, może znacznie skorzystać na systemach SMP wykorzystując nowy UMS .

Wydaje mi się, że pytanie OP Nie dotyczy zasadności i subiektywnych argumentów za/przeciw jakiemukolwiek rozwiązaniu, ale jeśli miałbym odpowiedzieć na to pytanie, to chyba zależy to od zadania: do budowy niskopoziomowych, wysokowydajnych podstawowych struktur danych, które działają na pojedynczym systemie z wieloma rdzeniami , albo techniki low-lock / "lock-free", albo STM dadzą najlepsze wyniki pod względem wydajności i prawdopodobnie pokonają rozwiązanie MPI w dowolnym momencie. wydajność, nawet jeśli powyższe zmarszczki są wyprostowane np. w Erlang.
Do budowy czegoś umiarkowanie bardziej skomplikowanego, co działa na jednym systemie, wybrałbym być może Klasyczne gruboziarniste blokowanie lub, jeśli chodzi o wydajność, STM.
Aby zbudować system rozproszony, system MPI prawdopodobnie dokonałby naturalnego wyboru.
Zauważ, że istnieją implementacje MPI dla . NET oraz (choć wydają się nie być tak aktywne).