Obecne implementacje „bez blokad” przez większość czasu działają według tego samego wzorca:
- * przeczytaj stan i zrób jego kopię **
- * modyfikuj kopię **
- wykonać operację blokowaną
- spróbuj ponownie, jeśli się nie powiedzie
(* opcjonalnie: zależy od struktury danych / algorytmu)
Ostatni kawałek jest niesamowicie podobny do spinlocka. W rzeczywistości jest to podstawowy spinlock . :)
Zgadzam się z @nobugz co do tego: koszt operacji blokowanych używanych w wielowątkowości bez blokad jest zdominowany przez zadania związane z pamięcią podręczną i spójnością pamięci, które musi wykonać .
Jednak dzięki strukturze danych „wolnej od blokad” zyskujesz to, że Twoje „blokady” są bardzo drobnoziarniste . Zmniejsza to prawdopodobieństwo, że dwa współbieżne wątki będą miały dostęp do tej samej „blokady” (lokalizacji pamięci).
W większości przypadków sztuczka polega na tym, że nie masz dedykowanych blokad - zamiast tego traktujesz np. Wszystkie elementy w tablicy lub wszystkie węzły w połączonej liście jako „blokadę spinową”. Czytasz, modyfikujesz i próbujesz aktualizować, jeśli od ostatniego odczytu nie było żadnej aktualizacji. Jeśli tak, spróbuj ponownie.
To sprawia, że "blokowanie" (och, przepraszam, nie blokowanie :) jest bardzo drobnoziarniste, bez wprowadzania dodatkowej pamięci lub wymagań dotyczących zasobów.
Zwiększenie drobnoziarnistości zmniejsza prawdopodobieństwo oczekiwania. Zrobienie tego tak drobnoziarnistego, jak to tylko możliwe, bez wprowadzania dodatkowych wymagań dotyczących zasobów, brzmi świetnie, prawda?
Jednak największą frajdą może być zapewnienie prawidłowego ładowania / zamawiania w sklepie .
Wbrew intuicji procesory mogą dowolnie zmieniać kolejność odczytów / zapisów pamięci - nawiasem mówiąc, są bardzo sprytne: trudno będzie ci to obserwować z jednego wątku. Jednak napotkasz problemy, gdy zaczniesz wielowątkowość na wielu rdzeniach. Twoja intuicja się załamie: tylko dlatego, że instrukcja znajduje się wcześniej w kodzie, nie oznacza to, że faktycznie nastąpi to wcześniej. Procesory mogą przetwarzać instrukcje poza kolejnością: a szczególnie lubią to robić z instrukcjami z dostępem do pamięci, aby ukryć opóźnienia pamięci głównej i lepiej wykorzystać swoją pamięć podręczną.
Teraz, wbrew intuicji, jest pewne, że sekwencja kodu nie płynie „z góry na dół”, zamiast tego działa tak, jakby w ogóle nie było sekwencji - i można ją nazwać „placem zabaw diabła”. Uważam, że niemożliwe jest udzielenie dokładnej odpowiedzi na temat tego, jakie ponowne zamówienia w załadunku / sklepie będą miały miejsce. Zamiast tego, zawsze mówi w kategoriach mays i mights i puszek i przygotować się na najgorsze. „Och, procesor może zmienić kolejność tego odczytu, aby nastąpił przed zapisem, więc najlepiej jest umieścić barierę pamięci tutaj, w tym miejscu”.
Sprawy komplikuje fakt, że nawet te Mays i mights mogą różnić się w poprzek architektur procesora. To może być, na przykład, że coś, co jest gwarancją nie stało w jednej architekturze może zdarzyć się na innym.
Aby prawidłowo obsługiwać wielowątkowość bez blokad, musisz zrozumieć modele pamięci.
Uzyskanie poprawnego modelu pamięci i gwarancji nie jest jednak trywialne, jak pokazuje ta historia, w której Intel i AMD wprowadziły pewne poprawki do dokumentacji MFENCEpowodującej zamieszanie wśród programistów JVM . Jak się okazało, dokumentacja, na której deweloperzy polegali od samego początku, nie była po pierwsze tak precyzyjna.
Blokady w .NET powodują powstanie niejawnej bariery pamięci, więc możesz z nich bezpiecznie korzystać (przez większość czasu, to znaczy ... zobacz na przykład ten Joe Duffy - Brad Abrams - Vance Morrison o leniwej inicjalizacji, blokadach, ulotnościach i pamięci bariery. :) (Pamiętaj, aby skorzystać z linków na tej stronie.)
Jako dodatkowy bonus, zostaniesz wprowadzony do modelu pamięci .NET w ramach pobocznego zadania . :)
Jest też „oldie but goldie” autorstwa Vance Morrison: What Every Dev Must Know About Multithreaded Apps .
... i oczywiście, jak wspomniał @Eric , Joe Duffy jest ostateczną lekturą na ten temat.
Dobry STM może zbliżyć się do drobnoziarnistego blokowania, jak to tylko możliwe, i prawdopodobnie zapewni wydajność, która jest zbliżona lub porównywalna z wykonaną ręcznie implementacją. Jednym z nich jest STM.NET z projektów MS DevLabs .
Jeśli nie jesteś fanatykiem tylko .NET, Doug Lea wykonał świetną robotę w JSR-166 .
Cliff Click ma interesujące podejście do tablic mieszania, które nie polega na blokowaniu pasków - jak robią to współbieżne tablice mieszania Java i .NET - i wydaje się, że dobrze skalują się do 750 procesorów.
Jeśli nie boisz się zapuszczać się na terytorium Linuksa, poniższy artykuł zawiera więcej informacji na temat wewnętrznych elementów obecnych architektur pamięci i tego, jak współdzielenie linii 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 rozważenia, łatwiejsze do wdrożenia i mniej podatne na błędy niż niedopracowana implementacja blokowania, która stara się być inteligentna. (Jest to jednak - subiektywnie - prawdziwe również w przypadku rozwiązania opartego na STM). Założę się również, że o lata świetlne łatwiej jest poprawnie napisać porządną aplikację rozproszoną np. W Erlangu, jak sugeruje wiele udanych przykładów.
MPI ma jednak swoje własne koszty i kłopoty, gdy działa na jednym, wielordzeniowym systemie . Np. W Erlang do rozwiązania są problemy związane z synchronizacją planowania procesów i kolejek wiadomości .
Ponadto, w swej istocie, systemy MPI zwykle implementują rodzaj kooperatywnego planowania N: M dla „lekkich procesów”. Oznacza to na przykład, że istnieje nieuniknione przełączanie kontekstu między lekkimi procesami. Prawdą jest, że nie jest to „klasyczny przełącznik kontekstu”, ale przeważnie operacja w przestrzeni użytkownika i można ją wykonać szybko - jednak szczerze wątpię, czy można ją sprowadzić do 20-200 cykli, jakie zajmuje operacja blokowana . Przełączanie kontekstu w trybie użytkownika jest z pewnością wolniejszenawet w bibliotece Intel McRT. Szeregowanie N: M z lekkimi procesami nie jest nowością. LWP były w Solarisie od dawna. Zostali opuszczeni. W NT były włókna. Są teraz przeważnie reliktem. W NetBSD były "aktywacje". Zostali opuszczeni. Linux miał własne podejście do tematu wątków N: M. Wydaje się, że jest już trochę martwy.
Od czasu do czasu pojawiają się nowi pretendenci: na przykład McRT firmy Intel lub ostatnio User-Mode Scheduling wraz z ConCRT firmy Microsoft.
Na najniższym poziomie robią to, co robi planista N: M MPI. Erlang - lub jakikolwiek inny system MPI - może znacznie skorzystać na systemach SMP, wykorzystując nowy UMS .
Wydaje mi się, że pytanie OP nie dotyczy zalet i subiektywnych argumentów za / przeciw jakimkolwiek rozwiązaniom, ale gdybym miał na to odpowiedzieć, wydaje mi się, że zależy to od zadania: budowy niskopoziomowych, wysokowydajnych podstawowych struktur danych, które działają na pojedynczy system 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 każdej chwili pod względem wydajności, nawet jeśli powyższe zmarszczki zostaną usunięte np. w Erlang.
Aby zbudować coś średnio bardziej złożonego, który działa w jednym systemie, być może wybrałbym klasyczne blokowanie gruboziarniste lub, jeśli wydajność ma duże znaczenie, STM.
W przypadku budowy systemu rozproszonego system MPI byłby prawdopodobnie naturalnym wyborem.
Zauważ, że istnieją również implementacje MPI dla .NET (chociaż wydają się nie być tak aktywne).