Jak efektywne jest blokowanie odblokowanego muteksu? Jaki jest koszt muteksu?

W języku niskiego poziomu (C, C ++ lub czymkolwiek): mam wybór pomiędzy posiadaniem kilku muteksów (takich jak to, co daje mi pthread lub cokolwiek zapewnia natywna biblioteka systemowa) lub jednym dla obiektu.

Jak skuteczne jest blokowanie muteksu? Tj. Ile jest prawdopodobnych instrukcji asemblera i ile czasu one zajmują (w przypadku, gdy mutex jest odblokowany)?

Ile kosztuje mutex? Czy naprawdę dużo muteksów jest problemem ? A może mogę po prostu wrzucić tyle zmiennych mutex do mojego kodu, ile mam intzmiennych i to naprawdę nie ma znaczenia?

(Nie jestem pewien, jak duże są różnice między różnymi urządzeniami. Jeśli tak, chciałbym również o nich wiedzieć. Ale przede wszystkim interesuje mnie wspólny sprzęt).

Chodzi o to, że używając wielu muteksów, z których każdy obejmuje tylko część obiektu, zamiast pojedynczego muteksu dla całego obiektu, mogłem zabezpieczyć wiele bloków. Zastanawiam się, jak daleko powinienem zajść w tym. Czyli powinienem spróbować zabezpieczyć jakikolwiek możliwy blok naprawdę tak daleko, jak to tylko możliwe, nieważne o ile jest to bardziej skomplikowane i ile więcej muteksów to oznacza?

Wpis na blogu WebKit (2016) dotyczący blokowania jest bardzo powiązany z tym pytaniem i wyjaśnia różnice między blokadą spinlock, blokadą adaptacyjną, futexem itp.

Mam wybór pomiędzy posiadaniem kilku muteksów lub jednego dla obiektu.

Jeśli masz wiele wątków, a dostęp do obiektu zdarza się często, wielokrotne blokady zwiększyłyby równoległość. Kosztem łatwości konserwacji, ponieważ większe blokowanie oznacza więcej debugowania blokowania.

Jak skuteczne jest blokowanie muteksu? Tj. Ile jest prawdopodobnych instrukcji asemblera i ile czasu one zajmują (w przypadku, gdy mutex jest odblokowany)?

Precyzyjne instrukcje asemblera są najmniejszym narzutem muteksu - gwarancje spójności pamięci / pamięci podręcznej są głównym narzutem. I rzadziej bierze się konkretny zamek - lepiej.

Mutex składa się z dwóch głównych części (uproszczenie): (1) flaga wskazująca, czy mutex jest zablokowany, czy nie i (2) kolejka oczekiwania.

Zmiana flagi to tylko kilka instrukcji i zwykle odbywa się bez wywołania systemowego. Jeśli mutex jest zablokowany, syscall doda wątek wywołujący do kolejki oczekiwania i rozpocznie czekanie. Odblokowanie, jeśli kolejka oczekiwania jest pusta, jest tanie, ale w przeciwnym razie wymaga wywołania systemowego, aby obudzić jeden z oczekujących procesów. (W niektórych systemach do implementacji muteksów używane są tanie / szybkie wywołania systemowe, stają się one powolnymi (normalnymi) wywołaniami systemowymi tylko w przypadku konfliktu).

Blokowanie odblokowanego muteksu jest naprawdę tanie. Odblokowanie mutexa bez rywalizacji też jest tanie.

Ile kosztuje mutex? Czy naprawdę dużo muteksów jest problemem? A może mogę po prostu wrzucić tyle zmiennych mutex do mojego kodu, ile mam zmiennych int i to naprawdę nie ma znaczenia?

Możesz wrzucić do swojego kodu dowolną liczbę zmiennych mutex. Ogranicza Cię jedynie ilość pamięci, jaką aplikacja może przydzielić.

Podsumowanie. Blokady przestrzeni użytkownika (aw szczególności muteksy) są tanie i nie podlegają żadnym ograniczeniom systemowym. Ale zbyt wiele z nich to koszmar do debugowania. Prosty stół:

1. Mniej blokad oznacza więcej konfliktów (powolne wywołania systemowe, blokady procesora) i mniejszy równoległość
2. Mniej blokad oznacza mniej problemów z debugowaniem problemów wielowątkowych.
3. Więcej blokad oznacza mniej sporów i wyższą równoległość
4. Więcej blokad oznacza większe szanse napotkania niemożliwych do usunięcia zakleszczeń.

Należy znaleźć i utrzymywać zrównoważony schemat blokowania do zastosowania, generalnie równoważąc # 2 i # 3.

(*) Problem z rzadziej blokowanymi muteksami polega na tym, że jeśli masz zbyt duże blokowanie w swojej aplikacji, powoduje to, że duża część ruchu między procesorami / rdzeniami opróżnia pamięć muteksów z pamięci podręcznej innych procesorów, aby zagwarantować spójność pamięci podręcznej. Opróżnienia pamięci podręcznej są jak lekkie przerwania i są obsługiwane przez procesory w sposób przejrzysty - ale wprowadzają tak zwane przestoje (szukaj hasła „przeciągnięcie”).

A blokady powodują, że kod blokujący działa wolno, często bez wyraźnego wskazania, dlaczego aplikacja działa wolno. (Niektóre archiwa zapewniają statystyki ruchu między procesorami / rdzeniami, inne nie).

Aby uniknąć problemu, ludzie na ogół uciekają się do dużej liczby blokad, aby zmniejszyć prawdopodobieństwo sporu o blokady i uniknąć przeciągnięcia. To jest powód, dla którego istnieje tanie blokowanie przestrzeni użytkownika, nie podlegające ograniczeniom systemowym.

Chciałem wiedzieć to samo, więc zmierzyłem to. Na moim pudełku (ośmiordzeniowy procesor AMD FX (tm) -8150 przy 3,612361 GHz) blokowanie i odblokowywanie odblokowanego muteksu, który znajduje się we własnej linii pamięci podręcznej i jest już buforowany, zajmuje 47 zegarów (13 ns).

Ze względu na synchronizację między dwoma rdzeniami (użyłem CPU # 0 i # 1), mogłem wywołać parę blokowania / odblokowania tylko raz na 102 ns na dwóch wątkach, a więc raz na 51 ns, z czego można wywnioskować, że zajmuje to około 38 ns do odzyskania po odblokowaniu wątku, zanim następny wątek będzie mógł go ponownie zablokować.

Program, którego użyłem do zbadania tego, można znaleźć tutaj: https://github.com/CarloWood/ai-statefultask-testsuite/blob/b69b112e2e91d35b56a39f41809d3e3de2f9e4b8/src/mutex_test.cxx

Zauważ, że ma kilka zakodowanych na stałe wartości specyficznych dla mojego pudełka (narzut xrange, yrange i rdtsc), więc prawdopodobnie będziesz musiał z nim poeksperymentować, zanim zadziała.

Wykres, który tworzy w tym stanie, to:

To pokazuje wynik testów porównawczych na następującym kodzie:

uint64_t do_Ndec(int thread, int loop_count)
{
  uint64_t start;
  uint64_t end;
  int __d0;

  asm volatile ("rdtsc\n\tshl $32, %%rdx\n\tor %%rdx, %0" : "=a" (start) : : "%rdx");
  mutex.lock();
  mutex.unlock();
  asm volatile ("rdtsc\n\tshl $32, %%rdx\n\tor %%rdx, %0" : "=a" (end) : : "%rdx");
  asm volatile ("\n1:\n\tdecl %%ecx\n\tjnz 1b" : "=c" (__d0) : "c" (loop_count - thread) : "cc");
  return end - start;
}

Dwa wywołania rdtsc mierzą liczbę zegarów potrzebnych do zablokowania i odblokowania „muteksu” (z narzutem 39 zegarów dla wywołań rdtsc na moim pudełku). Trzeci asm to pętla opóźniająca. Rozmiar pętli opóźnienia jest o 1 liczbę mniejszy dla wątku 1 niż dla wątku 0, więc wątek 1 jest nieco szybszy.

Powyższa funkcja jest wywoływana w ciasnej pętli o rozmiarze 100 000. Pomimo tego, że funkcja jest nieco szybsza dla wątku 1, obie pętle synchronizują się z powodu wywołania muteksu. Na wykresie widać to po tym, że liczba zegarów zmierzona dla pary blokada / odblokowanie jest nieco większa dla wątku 1, aby uwzględnić krótsze opóźnienie w pętli poniżej.

Na powyższym wykresie dolny prawy punkt jest pomiarem z opóźnieniem loop_count równym 150, a następnie po punktach na dole, w lewo, loop_count jest zmniejszany o jeden na każdy pomiar. Gdy osiągnie wartość 77, funkcja jest wywoływana co 102 ns w obu wątkach. Jeśli następnie loop_count zostanie jeszcze bardziej zredukowany, nie będzie już możliwa synchronizacja wątków, a mutex zacznie być faktycznie blokowany przez większość czasu, co skutkuje zwiększoną liczbą zegarów potrzebnych do wykonania blokady / odblokowania. Z tego powodu wzrasta również średni czas wywołania funkcji; więc punkty wykresu idą teraz w górę i ponownie w prawo.

Z tego możemy wywnioskować, że blokowanie i odblokowywanie muteksu co 50 ns nie stanowi problemu na moim pudełku.

Podsumowując, mój wniosek jest taki, że odpowiedź na pytanie OP jest taka, że ​​dodanie większej liczby muteksów jest lepsze, o ile prowadzi to do mniejszej rywalizacji.

Spróbuj zablokować muteksy tak krótkie, jak to możliwe. Jedynym powodem umieszczenia ich -powiedz- poza pętlą byłoby to, że pętla ta zapętla się szybciej niż raz na 100 ns (a raczej liczba wątków, które chcą uruchomić tę pętlę w tym samym czasie razy 50 ns) lub gdy 13 ns razy rozmiar pętli jest większym opóźnieniem niż opóźnienie otrzymywane przez rywalizację.

EDYCJA: Mam teraz dużo więcej wiedzy na ten temat i zaczynam wątpić w wniosek, który tutaj przedstawiłem. Po pierwsze, CPU 0 i 1 okazują się być hiperwątkowe; chociaż AMD twierdzi, że ma 8 prawdziwych rdzeni, z pewnością jest coś bardzo podejrzanego, ponieważ opóźnienia między dwoma innymi rdzeniami są znacznie większe (tj. 0 i 1 tworzą parę, podobnie jak 2 i 3, 4 i 5 oraz 6 i 7 ). Po drugie, std :: mutex jest zaimplementowany w taki sposób, że blokuje się na chwilę przed wykonaniem wywołań systemowych, gdy nie udaje mu się natychmiast uzyskać blokady muteksu (co bez wątpienia będzie bardzo wolne). Więc to, co tutaj zmierzyłem, to absolutnie najbardziej idealna lokalizacja, aw praktyce blokowanie i odblokowywanie może zająć drastycznie więcej czasu na zablokowanie / odblokowanie.

Podsumowując, mutex jest implementowany z atomiką. Aby zsynchronizować elementy atomowe między rdzeniami, należy zablokować wewnętrzną magistralę, która zamraża odpowiednią linię pamięci podręcznej na kilkaset cykli zegara. W przypadku, gdy nie można uzyskać blokady, należy wykonać wywołanie systemowe, aby uśpić wątek; to jest oczywiście bardzo wolne (wywołania systemowe są rzędu 10 mircosecond). Zwykle nie stanowi to problemu, ponieważ ten wątek i tak musi spać - ale może to być problem z dużą rywalizacją, w której wątek nie może uzyskać blokady na czas, w którym normalnie się obraca, tak samo jak wywołanie systemowe, ale MOŻE weź zamek wkrótce potem. Na przykład, jeśli kilka wątków blokuje i odblokowuje muteks w ciasnej pętli i każdy utrzymuje blokadę przez 1 mikrosekundę, wtedy mogą zostać ogromnie spowolnieni przez fakt, że są ciągle usypiani i ponownie budzeni. Ponadto, gdy wątek śpi i inny wątek musi go obudzić, ten wątek musi wykonać wywołanie systemowe i jest opóźniony o ~ 10 mikrosekund; to opóźnienie ma więc miejsce podczas odblokowywania muteksu, gdy inny wątek czeka na ten mutex w jądrze (po obróceniu trwało to zbyt długo).

Zależy to od tego, co faktycznie nazywasz „muteksem”, trybem systemu operacyjnego itp.

Co najmniej to Koszt zblokowane pracy pamięci. Jest to stosunkowo ciężka operacja (w porównaniu z innymi prymitywnymi poleceniami asemblera).

Jednak to może być znacznie wyższe. Jeśli to, co nazywasz "muteksem" jest obiektem jądra (tj. Obiektem zarządzanym przez system operacyjny) i działa w trybie użytkownika - każda operacja na nim prowadzi do transakcji w trybie jądra, co jest bardzo ciężka.

Na przykład na procesorze Intel Core Duo, Windows XP. Operacja zblokowana: zajmuje około 40 cykli procesora. Wywołanie trybu jądra (tj. Wywołanie systemowe) - około 2000 cykli procesora.

W takim przypadku możesz rozważyć użycie sekcji krytycznych. Jest to hybryda muteksu jądra i zablokowanego dostępu do pamięci.

Koszt będzie różny w zależności od implementacji, ale należy pamiętać o dwóch rzeczach:

• koszt będzie najprawdopodobniej będzie minimalny, ponieważ jest to zarówno dość prymitywne i operacja zostanie zoptymalizowany jak najwięcej, dzięki swojej strukturze (stosuje się wiele ).
• nie ma znaczenia, jak drogie jest, ponieważ musisz go używać, jeśli chcesz bezpiecznej pracy wielowątkowej. Jeśli tego potrzebujesz, potrzebujesz tego.

W systemach jednoprocesorowych można generalnie wyłączyć przerwania na wystarczająco długo, aby atomowo zmienić dane. Systemy wieloprocesorowe mogą wykorzystywać strategię testowania i ustawiania .

W obu przypadkach instrukcje są stosunkowo wydajne.

Jeśli chodzi o to, czy należy zapewnić pojedynczy muteks dla ogromnej struktury danych, czy też mieć wiele muteksów, po jednym dla każdej sekcji, to jest równoważenie.

Posiadając pojedynczy mutex, masz większe ryzyko rywalizacji między wieloma wątkami. Możesz zmniejszyć to ryzyko, mając muteks na sekcję, ale nie chcesz wpaść w sytuację, w której wątek musi zablokować 180 muteksów, aby wykonać swoją pracę :-)

Jestem zupełnie nowy w pthreads i mutex, ale mogę potwierdzić na podstawie eksperymentów, że koszt zablokowania / odblokowania muteksu jest prawie zerowy, gdy nie ma rywalizacji, ale gdy jest rywalizacja, koszt blokowania jest niezwykle wysoki. Uruchomiłem prosty kod z pulą wątków, w którym zadanie polegało tylko na obliczeniu sumy w zmiennej globalnej chronionej blokadą mutex:

y = exp(-j*0.0001);
pthread_mutex_lock(&lock);
x += y ;
pthread_mutex_unlock(&lock);

W jednym wątku program sumuje 10 000 000 wartości praktycznie natychmiastowo (mniej niż jedna sekunda); przy dwóch wątkach (na MacBooku z 4 rdzeniami) ten sam program zajmuje 39 sekund.