Wielowątkowość bez blokady jest przeznaczona dla prawdziwych ekspertów od wątków

Czytałem odpowiedź, którą Jon Skeet udzielił na pytanie i wspomniał w niej:

Jeśli o mnie chodzi, wielowątkowość bez blokad jest dla prawdziwych ekspertów od wątków, z których nie jestem.

To nie pierwszy raz, kiedy to słyszę, ale bardzo niewiele osób mówi o tym, jak to się robi, jeśli jesteś zainteresowany nauczeniem się pisania wielowątkowego kodu bez blokad.

Więc moje pytanie brzmi, poza tym, że nauczysz się wszystkiego, co możesz o wątkach itp., Gdzie zaczniesz próbować nauczyć się pisać kod wielowątkowy bez blokad i jakie są dobre zasoby.

Twoje zdrowie

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).

Książka Joe Duffy'ego:

http://www.bluebytesoftware.com/books/winconc/winconc_book_resources.html

Prowadzi również bloga na te tematy.

Sztuczka pozwalająca uzyskać prawidłowe programy o niskim poziomie blokad polega na dokładnym zrozumieniu reguł modelu pamięci w konkretnej kombinacji sprzętu, systemu operacyjnego i środowiska wykonawczego.

Osobiście nie jestem na tyle sprytny, aby wykonać poprawne programowanie z niskim blokadą poza InterlockedIncrement, ale jeśli jesteś, świetnie, idź na to. Po prostu upewnij się, że zostawiłeś w kodzie dużo dokumentacji, aby ludzie, którzy nie są tak sprytni, jak ty, przypadkowo nie złamali jednego z niezmienników modelu pamięci i nie wprowadzili niemożliwego do znalezienia błędu.

Obecnie nie ma czegoś takiego jak „wątkowanie bez blokowania”. Był to interesujący plac zabaw dla środowisk akademickich i tym podobnych pod koniec ubiegłego wieku, kiedy sprzęt komputerowy był powolny i drogi. Algorytm Dekkera był zawsze moim ulubionym, nowoczesny sprzęt wypuścił go na pastwisko. To już nie działa.

Skończyły to dwa wydarzenia: rosnąca dysproporcja między szybkością pamięci RAM i procesora. I zdolność producentów chipów do umieszczenia więcej niż jednego rdzenia procesora w jednym chipie.

Problem z szybkością pamięci RAM wymagał od projektantów chipa umieszczenia bufora na chipie procesora. Bufor przechowuje kod i dane, szybko dostępne dla rdzenia procesora. I może być odczytywany i zapisywany z / do pamięci RAM w znacznie wolniejszym tempie. Ten bufor nazywany jest pamięcią podręczną procesora, większość procesorów ma co najmniej dwa z nich. Pamięć podręczna pierwszego poziomu jest mała i szybka, druga jest duża i wolniejsza. Tak długo, jak procesor może odczytywać dane i instrukcje z pamięci podręcznej pierwszego poziomu, będzie działać szybko. Brak pamięci podręcznej jest naprawdę drogi, powoduje uśpienie procesora nawet na 10 cykli, jeśli dane nie znajdują się w pierwszej pamięci podręcznej, aż na 200 cykli, jeśli nie ma jej w drugiej pamięci podręcznej i należy je odczytać BARAN.

Każdy rdzeń procesora ma własną pamięć podręczną, przechowują one swój własny „widok” pamięci RAM. Kiedy procesor zapisuje dane, zapis jest wykonywany w pamięci podręcznej, która jest następnie powoli przenoszona do pamięci RAM. Nieuniknione, każdy rdzeń będzie miał teraz inny widok na zawartość pamięci RAM. Innymi słowy, jeden procesor nie wie, co zapisał inny procesor, dopóki ten cykl zapisu pamięci RAM nie zostanie zakończony, a procesor odświeży swój własny widok.

To jest dramatycznie niezgodne z wątkami. Zawsze naprawdę obchodzi cię, jaki jest stan innego wątku, gdy musisz odczytać dane, które zostały zapisane przez inny wątek. Aby to zapewnić, musisz jawnie zaprogramować tak zwaną barierę pamięci. Jest to prymitywny procesor niskiego poziomu, który zapewnia, że ​​wszystkie pamięci podręczne procesora są w spójnym stanie i mają aktualny widok pamięci RAM. Wszystkie oczekujące zapisy muszą zostać opróżnione do pamięci RAM, a następnie pamięci podręczne należy odświeżyć.

Jest to dostępne w .NET, metoda Thread.MemoryBarrier () implementuje jedną. Biorąc pod uwagę, że jest to 90% pracy, którą wykonuje instrukcja lock (i 95% czasu wykonania), po prostu nie jesteś na czele, unikając narzędzi, które daje ci .NET i próbując wdrożyć własne.

Google dla wolnych od blokad struktur danych i pamięci transakcyjnej oprogramowania .

Zgadzam się z Johnem Skeetem w tej sprawie; wątki bez blokady to plac zabaw dla diabła i najlepiej pozostawić je ludziom, którzy wiedzą, że wiedzą to, co powinni wiedzieć.

Jeśli chodzi o wielowątkowość, musisz dokładnie wiedzieć, co robisz. Mam na myśli zbadanie wszystkich możliwych scenariuszy / przypadków, które mogą wystąpić podczas pracy w środowisku wielowątkowym. Wielowątkowość bez blokady nie jest biblioteką ani klasą, którą włączamy, to wiedza / doświadczenie, które zdobywamy podczas naszej podróży po wątkach.

Mimo że wątki bez blokad mogą być trudne w .NET, często można wprowadzić znaczące ulepszenia podczas korzystania z blokady, badając dokładnie, co ma być zablokowane, i minimalizując zablokowaną sekcję ... jest to również znane jako minimalizowanie ziarnistości blokady .

Na przykład powiedz po prostu, że musisz zabezpieczyć wątek kolekcji. Nie tylko na ślepo blokuj metodę iterującą po kolekcji, jeśli wykonuje ona na każdym elemencie jakieś zadanie intensywnie wykorzystujące procesor. Państwo może wystarczy umieścić blokady wokół tworząc płytkie kopię kolekcji. Iterowanie po kopii mogłoby wtedy działać bez blokady. Oczywiście jest to wysoce zależne od specyfiki twojego kodu, ale udało mi się rozwiązać problem konwoju zamków dzięki temu podejściu.