Jak mogę napisać konstrukcję bez blokady?

Użyj biblioteki, takiej jak Intel ' s Threading Building Blocks, zawiera ona sporo wolnych od blokady struktur i algorytmów. Naprawdę nie polecam próby samodzielnego pisania kodu bez blokady, jest to bardzo podatne na błędy i trudne do uzyskania.

Pisanie kodu bez blokady wątku jest trudne, ale Ten artykuł z Herb Sutter da ci początek.

Jak zauważył sblundy, jeśli wszystkie obiekty są niezmienne, tylko do odczytu, nie musisz się martwić o blokowanie, jednak oznacza to, że będziesz musiał często kopiować obiekty. Kopiowanie zazwyczaj wiąże się z malloc i malloc używa blokowania do synchronizacji alokacji pamięci między wątkami, więc obiekty niezmienne mogą kupić ci mniej niż myślisz (malloc sam skaluje się raczej źle, a malloc jest powolny {4]}; jeśli robisz dużo malloc w sekcji krytycznej wydajności, nie oczekuj dobrego osiągi).

Jeśli potrzebujesz tylko zaktualizować proste zmienne (np. 32 lub 64-bitowy int lub wskaźniki), wykonać po prostu operacje dodawania lub odejmowania na nich lub po prostu zamienić wartości dwóch zmiennych, większość platform oferuje "operacje atomowe" dla tego (dalsze GCC oferuje również te). Atomic nie jest tym samym co thread-safe . Jednak atomic upewnia się, że jeśli jeden wątek zapisze 64-bitową wartość do miejsca pamięci, na przykład, a inny wątek odczytuje z niego, albo pobiera wartość przed operacją zapisu lub po operacji zapisu, ale nigdy broken wartość pomiędzy operacją zapisu (np. taka, w której pierwsze 32 bity są już nowe, ostatnie 32 bity są nadal starą wartością! Może się to zdarzyć, jeśli nie użyjesz atomic access na takiej zmiennej).

Jednakże, jeśli masz strukturę C z 3 wartościami, które chcą zaktualizować, nawet jeśli zaktualizujesz wszystkie trzy za pomocą operacji atomowych, są to trzy niezależne operacje, więc czytnik może zobaczyć strukturę, w której jedna wartość jest już aktualizowana, a dwie nie są aktualizowane. Tutaj będziesz potrzebował blokady, jeśli musisz zapewnić, że czytnik widzi wszystkie wartości w strukturze będące albo starymi, albo nowymi wartościami.

Jednym ze sposobów na lepsze skalowanie zamków jest użycie zamków R/W. W wielu przypadkach aktualizacje danych są raczej rzadkie( operacje zapisu), ale dostęp do danych jest bardzo częsty( odczyt danych), pomyśl o kolekcjach (Hashtable, drzewa). W takim przypadku zamki R/w kupią masz ogromny wzrost wydajności, ponieważ wiele wątków może trzymać blokadę odczytu w tym samym czasie(nie będą blokować się nawzajem) i tylko wtedy, gdy jeden wątek chce blokady zapisu, wszystkie inne wątki są blokowane na czas aktualizacji.

Najlepszym sposobem na uniknięcie problemów z wątkami jest nie udostępnianie żadnych danych między wątkami. Jeśli każdy wątek zajmuje się przez większość czasu danymi, do których nie ma dostępu żaden inny wątek, nie będziesz potrzebował blokowania tych danych (również żadnych operacji atomowych). Więc staraj się udostępniać jak najmniej danych możliwe między wątkami. Wtedy potrzebujesz tylko szybkiego sposobu przenoszenia danych między wątkami, jeśli naprawdę musisz (ITC, komunikacja między wątkami). W zależności od systemu operacyjnego, platformy i języka programowania (niestety nie powiedziałeś nam żadnego z nich), mogą istnieć różne potężne metody dla ITC.

I wreszcie, kolejną sztuczką do pracy ze współdzielonymi danymi, ale bez blokowania, jest upewnienie się, że wątki nie mają dostępu do tych samych części współdzielonych danych. Np. jeśli dwa wątki dzielą tablicę, ale jeden będzie miał dostęp tylko do parzystych, drugi tylko do nieparzystych indeksów, nie potrzebujesz blokowania. Lub jeśli oba mają ten sam blok pamięci, a jeden używa tylko górnej połowy, drugi tylko dolną, nie trzeba blokować. Chociaż nie jest powiedziane, że doprowadzi to do dobrej wydajności; szczególnie nie na procesorach wielordzeniowych. Operacje zapisu jednego wątku na tych współdzielonych danych (Uruchamianie jednego rdzenia) mogą wymusić przepłukanie pamięci podręcznej dla innego wątku (uruchamianie na innym rdzeniu) i te przepłukania pamięci podręcznej są często szyjką butelki dla aplikacji wielowątkowych działających na nowoczesnych procesorach wielordzeniowych.

Jak powiedział mój profesor (Nir Shavit z "The Art of Multiprocessor Programming") na zajęciach: proszę nie. głównym powodem jest testowalność-nie można testować kodu synchronizacji. Możesz uruchamiać symulacje, możesz nawet testować. Ale to w najlepszym razie przybliżenie. To czego naprawdę potrzebujesz to matematyczny dowód poprawności. I bardzo niewielu zdolnych do ich zrozumienia, nie mówiąc już o ich pisaniu. Tak więc, jak mówili inni: użyj istniejących bibliotek. Joe Duffy ' s blog bada niektóre techniki (sekcja 28). Pierwszą z nich, którą powinieneś wypróbować, jest podział drzewa - przełam na mniejsze zadania i połącz.

Niezmienność jest jednym z podejść, aby uniknąć blokowania. Zobacz dyskusję Erica Lipperta i implementację rzeczy takich jak niezmienne stosy i kolejki.

W re. Odpowiedź sumy, Maurice Herlithy pokazuje w sztuce programowania wieloprocesorowego, że w rzeczywistości Wszystko może być napisane bez blokad (patrz rozdział 6). iirc, to zasadniczo polega na podziale zadań na elementy węzła przetwarzania (jak zamknięcie funkcji), i zapytaniu każdego z nich. Wątki obliczą stan, śledząc wszystkie węzły z ostatniego buforowanego. Oczywiście może to, w najgorszym przypadku, skutkować sekwencyjną wydajnością, ale ma ważną funkcję bez blokady właściwości, zapobiegając scenariuszom, w których wątki mogą być zaplanowane przez długi czas, gdy trzymają blokady. Herlithy osiąga również teoretyczną wydajność bez czekania, co oznacza, że jeden wątek nie skończy czekać wiecznie, aby wygrać atomic enqueue (jest to dużo skomplikowanego kodu).

Wielowątkowa Kolejka / stos jest zaskakująco trudna (sprawdź problem ABA). Inne rzeczy mogą być bardzo proste. Przyzwyczaić się do while (true) { atomicCAS dopóki nie zamieniłem go } bloki; są niesamowicie potężne. Intuicja co jest poprawne z CAS może pomóc w rozwoju, choć należy użyć dobrych testów i może bardziej wydajnych narzędzi (może SKETCH, nadchodzące MIT Kendo, lub spin?), aby sprawdzić poprawność, czy można ją zredukować do prostej struktury.

Proszę pisać więcej o swoim problemie. Trudno dać dobrą odpowiedź bez szczegółów.

Edit immutability jest ładne, ale jej przydatność jest ograniczona, jeśli Dobrze to Rozumiem. Tak naprawdę nie pokonuje zagrożeń związanych z zapisem po odczycie; rozważ dwa wątki wykonujące " mem = NewNode(mem)"; oba mogą odczytać mem, a następnie oba go zapisać; nie jest to poprawne dla klasycznej funkcji inkrementacji. Ponadto, prawdopodobnie jest powolny z powodu alokacji sterty (która musi być zsynchronizowana między wątkami).

Inmutability miałoby taki efekt. Zmiany w obiekcie powodują powstanie nowego obiektu. Lisp działa w ten sposób pod przykrywką.

Pozycja 13 efektywna Java wyjaśnia tę technikę.

Cliff Click przeprowadził wiele badań nad wolnymi strukturami danych poprzez wykorzystanie skończonych maszyn stanowych, a także opublikował wiele implementacji dla Javy. Jego prace, slajdy i wdrożenia można znaleźć na jego blogu: http://blogs.azulsystems.com/cliff/

Użyj istniejącej implementacji, ponieważ ten obszar pracy jest domeną ekspertów domen i doktorów (jeśli chcesz to zrobić dobrze!)

Na przykład istnieje Biblioteka kodu tutaj:

Http://www.cl.cam.ac.uk/research/srg/netos/lock-free/

Większość algorytmów lub struktur bez blokady zaczyna się od jakiejś operacji atomowej, tzn. zmiana miejsca pamięci, która raz rozpoczęta przez wątek zostanie zakończona, zanim jakikolwiek inny wątek będzie mógł wykonać tę samą operację. Czy masz taką operację w swoim środowisku?

Zobacz TUTAJ , aby zapoznać się z artykułem kanonicznym na ten temat.

Spróbuj również tego Artykuł Wikipedii Artykuł dla dalszych pomysłów i linków.

Podstawowa zasada synchronizacji bez blokady jest następująca:

• Kiedy czytasz strukturę, podążasz za odczytem z testem, aby sprawdzić, czy struktura została zmutowana od momentu rozpoczęcia odczytu i spróbuj ponownie, dopóki nie uda Ci się odczytać, nie pojawiając się nic innego i nie mutując podczas tego procesu;

• Za każdym razem, gdy mutujesz strukturę, układasz swój algorytm i dane tak, aby istniał jeden atomowy krok, który, jeśli zostanie wykonany, powoduje cała zmiana, aby stała się widoczna dla innych wątków i uporządkować rzeczy tak, aby żadna zmiana nie była widoczna, chyba że ten krok zostanie wykonany. Do tego kroku używasz dowolnego mechanizmu lockfree atomic, który istnieje na twojej platformie (np. compare-and-set, Load-linked+store-conditional, itp.). W tym kroku musisz sprawdzić, czy jakikolwiek inny wątek zmutował obiekt od czasu rozpoczęcia operacji mutacji, Zatwierdź, jeśli nie, i zacznij od nowa, jeśli tak.

Jest wiele przykładów bez wiedzy o tym, co wdrażasz i na jakiej platformie, trudno być bardziej szczegółowym.

Jeśli piszesz własne, wolne od blokad struktury danych dla wielordzeniowego procesora, nie zapomnij o barierach pamięci! Rozważ również zajrzenie do technik Software Transaction Memory.

Jeśli widzisz blokadę, najpierw spróbowałbym użyć bardziej ziarnistych blokad w Twoich strukturach danych, a nie całkowicie wolnych od blokad algorytmów.

Na przykład, obecnie pracuję nad aplikacją wielowątkową, która ma własny system wiadomości (lista kolejek dla każdego wątku, Kolejka zawiera Wiadomości do przetworzenia wątku), aby przekazać informacje między wątkami. Istnieje globalna blokada tej struktury. W moim przypadku nie potrzebuję tak dużej prędkości, więc to nie ma znaczenia. Ale jeśli taka blokada stanie się problemem, może być zastąpiona przez pojedyncze blokady w każdej kolejce, na przykład. Wtedy dodanie / usunięcie elementu do / z określonej kolejki nie wpłynie na inne kolejki. Nadal istniałaby globalna blokada dodawania nowej kolejki itp., ale nie byłoby to aż tak kontrowersyjne.

Nawet pojedyncza Kolejka multi-produces/consumer może być zapisywana z ziarnistym blokowaniem na każdym elemencie, zamiast mieć globalną blokadę. Może to również wyeliminować niezgodność.

Cóż, to zależy od rodzaju struktury, ale trzeba zrobić strukturę tak, aby ostrożnie i cicho wykrywała i radziła sobie z ewentualnymi konfliktami.

Wątpię, żeby można było zrobić taki, który jest w 100% wolny od blokady, ale znowu, to zależy od tego, jakiego rodzaju strukturę trzeba zbudować.

Może być również konieczne rozerwanie struktury, aby wiele wątków działało na poszczególnych elementach, a następnie zsynchronizować / rekombinować.

Jak już wspomniałem, to naprawdę zależy od tego, o jakiej strukturze mówisz. Na przykład można napisać kolejkę ograniczoną bez blokady, ale nie taką, która umożliwia losowy dostęp.

Reduce or eliminate shared mutable state.

W Javie używaj Javy.util.współbieżne pakiety w JDK 5+ zamiast pisać własne. Jak wspomniano powyżej, jest to naprawdę dziedzina dla ekspertów, i jeśli nie masz wolnego roku lub dwóch, walcowanie własne nie jest opcją.

Możesz wyjaśnić, co masz na myśli przez strukturę?

W tej chwili zakładam, że masz na myśli ogólną architekturę. Możesz to osiągnąć, nie dzieląc pamięci między procesami i używając modelu aktora dla swoich procesów.

Spójrz na mój Link ConcurrentLinkedHashMap, aby znaleźć przykład jak napisać strukturę danych bez blokady. Nie jest on oparty na żadnych pracach naukowych i nie wymaga lat badań, jak sugerują inni. To po prostu wymaga starannej inżynierii.

Moja implementacja używa ConcurrentHashMap, która jest algorytmem lock-per-bucket, ale nie opiera się na tej implementacji. Można go łatwo zastąpić implementacją bez blokady Cliff Click. Pożyczyłem pomysł od Cliff, ale używane znacznie bardziej wyraźnie, jest modelowanie wszystkich operacji CAS za pomocą maszyny stanowej. To znacznie upraszcza model, jak widać, że mam zamki psuedo za pośrednictwem Stanów ing. Inną sztuczką jest umożliwienie lenistwa i rozwiązania w razie potrzeby. Zobaczysz to często z cofaniem lub pozwalaniem innym wątkom" pomóc " w czyszczeniu. W moim przypadku zdecydowałem się pozwolić martwym węzłom na liście być eksmitowane, gdy dotrą do głowy, a nie radzić sobie ze złożonością usuwania ich ze środka lista. Mogę to zmienić, ale nie do końca ufałem mojemu algorytmowi śledzenia wstecznego i chciałem odłożyć poważną zmianę, taką jak przyjęcie podejścia blokującego 3 węzły.

Książka "Sztuka programowania wieloprocesorowego" to świetny podkład. Ogólnie jednak polecam unikanie projektów bez blokad w kodzie aplikacji. Często jest to po prostu przesada, gdzie inne, mniej podatne na błędy, techniki są bardziej odpowiednie.

Jeśli przeczytasz kilka implementacji i artykułów dotyczących tego tematu, zauważysz, że istnieje następujący wspólny temat:

1) Shared state objects are lisp / clojure style inmutable: oznacza to, że wszystkie operacje zapisu są zaimplementowane kopiując istniejący stan w nowym obiekcie, wprowadzając modyfikacje do nowego obiektu, a następnie próbując zaktualizować udostępniony stan(uzyskany z wyrównanego wskaźnika, który można zaktualizować za pomocą prymitywnego CAS). Innymi słowy, nigdy przenigdy nie modyfikujesz istniejący obiekt, który może być odczytany przez więcej niż bieżący wątek. Inmutability może być zoptymalizowane za pomocą semantyki kopiowania przy zapisie dla dużych, złożonych obiektów, ale jest to kolejne drzewo nuts

2) jasno określasz, jakie dozwolone przejścia między aktualnym i następnym stanem są ważne: Następnie sprawdzanie poprawności algorytmu staje się prostsze o rząd wielkości

3) Obsługa odrzuconych odniesień w listach wskaźników zagrożenia dla każdego wątku. Po obiektach referencyjnych są bezpieczne, ponowne użycie, jeśli to możliwe

Zobacz inny mój pokrewny post, w którym kod zaimplementowany semaforami i muteksami jest (częściowo) reimplementowany w stylu wolnym od blokady: wzajemne wykluczenie i semafory