Jaka jest różnica między muteksem a sekcją krytyczną?

134

Proszę wyjaśnić z perspektywy Linuksa, Windowsa?

Programuję w C #, czy te dwa terminy będą miały znaczenie. Publikuj tak dużo, jak możesz, z przykładami i tym podobnymi ....

Dzięki


źródło

Odpowiedzi:

232

W przypadku systemu Windows krytyczne sekcje są lżejsze niż muteksy.

Muteksy mogą być współużytkowane między procesami, ale zawsze powodują wywołanie systemowe jądra, które ma pewien narzut.

Sekcje krytyczne mogą być używane tylko w ramach jednego procesu, ale mają tę zaletę, że przełączają się w tryb jądra tylko w przypadku rywalizacji - niezakończone pozyskiwanie, które powinno być powszechnym przypadkiem, jest niesamowicie szybkie. W przypadku rywalizacji, wchodzą do jądra, aby czekać na jakiś element prymitywny synchronizacji (taki jak zdarzenie lub semafor).

Napisałem krótką przykładową aplikację, która porównuje czas między nimi. W moim systemie dla 1 000 000 niezakłóconych zakupów i wydań mutex zajmuje ponad jedną sekundę. Sekcja krytyczna trwa ~ 50 ms dla 1 000 000 akwizycji.

Oto kod testowy, uruchomiłem go i uzyskałem podobne wyniki, jeśli mutex jest pierwszy lub drugi, więc nie widzimy żadnych innych efektów.

HANDLE mutex = CreateMutex(NULL, FALSE, NULL);
CRITICAL_SECTION critSec;
InitializeCriticalSection(&critSec);

LARGE_INTEGER freq;
QueryPerformanceFrequency(&freq);
LARGE_INTEGER start, end;

// Force code into memory, so we don't see any effects of paging.
EnterCriticalSection(&critSec);
LeaveCriticalSection(&critSec);
QueryPerformanceCounter(&start);
for (int i = 0; i < 1000000; i++)
{
    EnterCriticalSection(&critSec);
    LeaveCriticalSection(&critSec);
}

QueryPerformanceCounter(&end);

int totalTimeCS = (int)((end.QuadPart - start.QuadPart) * 1000 / freq.QuadPart);

// Force code into memory, so we don't see any effects of paging.
WaitForSingleObject(mutex, INFINITE);
ReleaseMutex(mutex);

QueryPerformanceCounter(&start);
for (int i = 0; i < 1000000; i++)
{
    WaitForSingleObject(mutex, INFINITE);
    ReleaseMutex(mutex);
}

QueryPerformanceCounter(&end);

int totalTime = (int)((end.QuadPart - start.QuadPart) * 1000 / freq.QuadPart);

printf("Mutex: %d CritSec: %d\n", totalTime, totalTimeCS);
Michael
źródło
1
Nie jestem pewien, czy to dotyczy, czy nie (ponieważ nie skompilowałem i nie wypróbowałem twojego kodu), ale stwierdziłem, że wywołanie WaitForSingleObject z INFINITE skutkuje słabą wydajnością. Przekazanie mu wartości limitu czasu wynoszącej 1, a następnie zapętlenie podczas sprawdzania, czy zwrócił, spowodowało ogromną różnicę w wydajności części mojego kodu. Dzieje się tak głównie w kontekście oczekiwania na zewnętrzny uchwyt procesu, jednak ... Nie jest to muteks. YMMV. Chciałbym zobaczyć, jak mutex radzi sobie z tą modyfikacją. Wynikowa różnica czasu z tego testu wydaje się większa niż należało się spodziewać.
Troy Howard
5
@TroyHoward, czy nie po prostu obracasz blokowaniem w tym momencie?
dss539
Przyczyny tego rozróżnienia są prawdopodobnie głównie historyczne. Nie jest trudno wdrożyć blokowanie, które jest tak szybkie jak CriticalSection w przypadku niezakończonym (kilka instrukcji atomowych, brak wywołań systemowych), ale działa między procesami (z fragmentem pamięci współdzielonej). Zobacz np. Linux futexes .
regnarg
2
@TroyHoward spróbuj zmusić swój procesor do pracy na 100% przez cały czas i zobacz, czy INFINITE działa lepiej. Strategia zasilania może zająć nawet 40 ms na moim komputerze (Dell XPS-8700), aby powrócić do pełnej prędkości po tym, jak zdecyduje się zwolnić, co może nie zrobić, jeśli śpisz lub czekasz tylko przez milisekundę.
Stevens Miller
Nie jestem pewien, czy rozumiem, co jest tutaj demonstrowane. Ogólnie rzecz biorąc, wejście do sekcji krytycznej wymaga pozyskania jakiegoś semafora. Czy mówisz, że za kulisami system operacyjny ma skuteczny sposób implementacji zachowania tej krytycznej sekcji bez konieczności stosowania muteksów?
SN
89

Z teoretycznego punktu widzenia, sekcja krytyczna to fragment kodu, który nie może być uruchamiany jednocześnie przez wiele wątków, ponieważ kod ma dostęp do współdzielonych zasobów.

Muteks jest algorytmem (czasem nazwę strukturze danych), która służy do zabezpieczenia sekcji krytycznych.

Semafory i monitory są typowymi implementacjami muteksu.

W praktyce w systemie Windows dostępnych jest wiele implementacji mutexów. Różnią się one głównie w wyniku ich implementacji poziomem blokowania, zakresem, kosztami i wydajnością na różnych poziomach rywalizacji. Zobacz CLR Inside Out - using Concurrency for skalowalność, aby zapoznać się z wykresem kosztów różnych implementacji mutex.

Dostępne prymitywy synchronizacji.

lock(object)Oświadczenie jest realizowany za pomocą Monitor- patrz MSDN odniesienia.

W ostatnich latach prowadzono wiele badań nad synchronizacją nieblokującą . Celem jest zaimplementowanie algorytmów bez blokowania lub oczekiwania. W takich algorytmach proces pomaga innym procesom zakończyć pracę, aby proces mógł ostatecznie zakończyć swoją pracę. W konsekwencji proces może zakończyć swoją pracę nawet wtedy, gdy inne procesy, które próbowały wykonać jakąś pracę, zawieszają się. Używając blokad, nie zwalnialiby swoich blokad i nie zapobiegaliby kontynuacji innych procesów.

Daniel Brückner
źródło
Widząc zaakceptowaną odpowiedź, myślałem, że może źle pamiętam koncepcję sekcji krytycznych, dopóki nie zobaczyłem, że Teoretyczna Perspektywa, którą napisałeś. :)
Anirudh Ramanathan
2
Praktyczne programowanie bez blokad jest podobne do Shangri La, z wyjątkiem tego, że istnieje. Artykuł Keira Frasera (PDF) przedstawia to dość interesująco (sięgając 2004 roku). I nadal walczymy z tym w 2012 roku. Ssamy.
Tim Post
22

Oprócz innych odpowiedzi poniższe szczegóły dotyczą krytycznych sekcji w systemie Windows:

  • w przypadku braku rywalizacji pozyskanie krytycznej sekcji jest tak proste, jak InterlockedCompareExchangeoperacja
  • w strukturze sekcji krytycznej jest miejsce na muteks. Początkowo jest nieprzydzielony
  • jeśli istnieje rywalizacja między wątkami w sekcji krytycznej, mutex zostanie przydzielony i użyty. Wydajność sekcji krytycznej obniży się do wydajności muteksu
  • Jeśli spodziewasz się dużej rywalizacji, możesz przydzielić sekcję krytyczną, określając liczbę obrotów.
  • jeśli występuje rywalizacja o sekcję krytyczną z liczbą obrotów, wątek próbujący uzyskać sekcję krytyczną będzie się obracał (czekanie zajęte) przez tyle cykli procesora. Może to skutkować lepszą wydajnością niż uśpienie, ponieważ liczba cykli wykonania przełączenia kontekstu do innego wątku może być znacznie większa niż liczba cykli wykonanych przez wątek będący właścicielem w celu zwolnienia muteksu
  • jeśli licznik spinów wygaśnie, mutex zostanie przydzielony
  • kiedy wątek będący właścicielem zwolni sekcję krytyczną, wymagane jest sprawdzenie, czy mutex jest przydzielony, jeśli tak, to ustawi mutex na zwolnienie oczekującego wątku

W Linuksie myślę, że mają "blokadę spinu", która służy podobnemu celowi jak sekcja krytyczna z liczbą obrotów.

1800 INFORMACJE
źródło
Niestety sekcja krytyczna dla okna wymaga wykonania operacji CAS w trybie jądra , co jest znacznie droższe niż faktyczna operacja blokowana. Ponadto z krytycznymi sekcjami systemu Windows mogą być powiązane liczby obrotów.
Promit
2
To zdecydowanie nieprawda. CAS można wykonać za pomocą cmpxchg w trybie użytkownika.
Michael
Myślałem, że domyślna liczba obrotów wynosi zero, jeśli wywołałeś InitializeCriticalSection - musisz wywołać InitializeCriticalSectionAndSpinCount, jeśli chcesz zastosować liczbę obrotów. Czy masz do tego odniesienie?
1800 INFORMACJE
18

Sekcja krytyczna i Mutex nie są specyficzne dla systemu operacyjnego, ich koncepcje wielowątkowości / wieloprocesorowości.

Sekcja krytyczna to fragment kodu, który musi być uruchamiany samodzielnie w danym momencie (na przykład jednocześnie działa 5 wątków i funkcja o nazwie „krytyczna_sekcja_funkcja”, która aktualizuje tablicę ... nie chcesz wszystkich 5 wątków aktualizowanie tablicy na raz. Tak więc, gdy program wykonuje krytyczną_sekcję_funkcję (), żaden z pozostałych wątków nie może uruchamiać swojej funkcji krytycznej_sekcji.

mutex * Mutex to sposób implementacji kodu sekcji krytycznej (myśl o nim jak o token ... wątek musi go posiadać, aby uruchomić kod krytycznej sekcji)

Nieznane
źródło
2
Ponadto muteksy mogą być współużytkowane w procesach.
konfigurator
14

Muteks to obiekt, który może uzyskać wątek, uniemożliwiając innym wątkom uzyskanie go. Ma charakter doradczy, a nie obowiązkowy; Wątek może używać zasobu reprezentowanego przez muteks bez jego uzyskiwania.

Sekcja krytyczna to długość kodu, której system operacyjny gwarantuje, że nie zostanie przerwany. W pseudokodzie wyglądałoby to tak:

StartCriticalSection();
    DoSomethingImportant();
    DoSomeOtherImportantThing();
EndCriticalSection();
Zifre
źródło
1
Myślę, że plakat mówił o prymitywach synchronizacji trybu użytkownika, takich jak obiekt sekcji krytycznej win32, który zapewnia wzajemne wykluczanie. Nie wiem o Linuksie, ale jądro Windows ma krytyczne regiony, które zachowują się tak, jak opisujesz - nieprzerywalne.
Michael
1
Nie wiem, dlaczego zostałeś zlekceważony. Istnieje koncepcja sekcji krytycznej, którą poprawnie opisałeś, która różni się od obiektu jądra systemu Windows o nazwie CriticalSection, który jest rodzajem muteksu. Myślę, że PO pytał o tę drugą definicję.
Adam Rosenfield
Przynajmniej byłem zdezorientowany tagiem agnostyka językowego. Ale w każdym razie to właśnie otrzymujemy w przypadku Microsoft, nazywając ich implementację taką samą, jak klasa bazowa. Zła praktyka kodowania!
Mikko Rantanen
Cóż, poprosił o jak najwięcej szczegółów, a konkretnie powiedział, że Windows i Linux, więc brzmi, jakby koncepcje były dobre. +1 - też nie zrozumiał -1: /
Jason Coco
14

„Szybki” Windows równy krytycznej selekcji w Linuksie byłby futexem , co oznacza szybki muteks przestrzeni użytkownika. Różnica między futexem a muteksem polega na tym, że w przypadku futexa jądro jest zaangażowane tylko wtedy, gdy wymagany jest arbitraż, więc oszczędzasz na kosztach rozmowy z jądrem za każdym razem, gdy licznik atomowy jest modyfikowany. To .. może zaoszczędzić znaczną ilość czasu podczas negocjowania blokad w niektórych aplikacjach.

Futex może być również współdzielony między procesami, przy użyciu środków, których użyłbyś do współdzielenia muteksu.

Niestety, futexy mogą być bardzo trudne do wdrożenia (PDF). (Aktualizacja 2018, nie są tak przerażające jak w 2009).

Poza tym jest prawie taki sam na obu platformach. Dokonujesz atomowych, opartych na tokenach aktualizacji wspólnej struktury w sposób, który (miejmy nadzieję) nie spowoduje głodu. Pozostaje po prostu metoda osiągnięcia tego.

Tim Post
źródło
6

W systemie Windows sekcja krytyczna jest lokalna dla twojego procesu. Mutex może być współużytkowany / dostępny w różnych procesach. Zasadniczo odcinki krytyczne są znacznie tańsze. Nie mogę komentować konkretnie Linuksa, ale w niektórych systemach są to tylko aliasy tego samego.

Promuj
źródło
6

Aby dodać moje 2 centy, sekcje krytyczne są zdefiniowane jako struktura, a operacje na nich są wykonywane w kontekście trybu użytkownika.

ntdll! _RTL_CRITICAL_SECTION
   + 0x000 DebugInfo: Ptr32 _RTL_CRITICAL_SECTION_DEBUG
   + 0x004 LockCount: Int4B
   + 0x008 RecursionCount: Int4B
   + 0x00c OwningThread: Ptr32 Void
   + 0x010 LockSemaphore: Ptr32 Void
   + 0x014 SpinCount: Uint4B

Natomiast mutex to obiekty jądra (ExMutantObjectType) utworzone w katalogu obiektów systemu Windows. Operacje mutex są najczęściej implementowane w trybie jądra. Na przykład, tworząc Mutex, w końcu wywołujesz w jądrze nt! NtCreateMutant.

Jaskółka oknówka
źródło
Co się dzieje, gdy program, który uruchamia się i używa obiektu Mutex, ulega awarii? Czy obiekt Mutex jest automatycznie zwalniany? Nie, powiedziałbym. Dobrze?
Ankur
6
Obiekty jądra mają liczbę odwołań. Zamknięcie uchwytu na obiekcie zmniejsza liczbę odwołań, a gdy osiągnie 0, obiekt jest zwalniany. Kiedy proces ulega awarii, wszystkie jego uchwyty są automatycznie zamykane, więc mutex, do którego tylko ten proces ma dojście, zostanie automatycznie zwolniony.
Michael
I to jest powód, dla którego obiekty sekcji krytycznej są powiązane z procesami, z drugiej strony muteksy mogą być współużytkowane przez procesy.
Sisir,
2

Świetna odpowiedź od Michaela. Dodałem trzeci test dla klasy mutex wprowadzonej w C ++ 11. Wynik jest dość interesujący i nadal wspiera jego oryginalne poparcie dla obiektów CRITICAL_SECTION dla pojedynczych procesów.

mutex m;
HANDLE mutex = CreateMutex(NULL, FALSE, NULL);
CRITICAL_SECTION critSec;
InitializeCriticalSection(&critSec);

LARGE_INTEGER freq;
QueryPerformanceFrequency(&freq);
LARGE_INTEGER start, end;

// Force code into memory, so we don't see any effects of paging.
EnterCriticalSection(&critSec);
LeaveCriticalSection(&critSec);
QueryPerformanceCounter(&start);
for (int i = 0; i < 1000000; i++)
{
    EnterCriticalSection(&critSec);
    LeaveCriticalSection(&critSec);
}

QueryPerformanceCounter(&end);

int totalTimeCS = (int)((end.QuadPart - start.QuadPart) * 1000 / freq.QuadPart);

// Force code into memory, so we don't see any effects of paging.
WaitForSingleObject(mutex, INFINITE);
ReleaseMutex(mutex);

QueryPerformanceCounter(&start);
for (int i = 0; i < 1000000; i++)
{
    WaitForSingleObject(mutex, INFINITE);
    ReleaseMutex(mutex);
}

QueryPerformanceCounter(&end);

int totalTime = (int)((end.QuadPart - start.QuadPart) * 1000 / freq.QuadPart);

// Force code into memory, so we don't see any effects of paging.
m.lock();
m.unlock();

QueryPerformanceCounter(&start);
for (int i = 0; i < 1000000; i++)
{
    m.lock();
    m.unlock();
}

QueryPerformanceCounter(&end);

int totalTimeM = (int)((end.QuadPart - start.QuadPart) * 1000 / freq.QuadPart);


printf("C++ Mutex: %d Mutex: %d CritSec: %d\n", totalTimeM, totalTime, totalTimeCS);

Moje wyniki to 217, 473 i 19 (zauważ, że mój stosunek czasów dla ostatnich dwóch jest z grubsza porównywalny z Michaelem, ale moja maszyna jest co najmniej cztery lata młodsza od jego, więc możesz zobaczyć dowody na zwiększoną prędkość między 2009 a 2013 , kiedy wyszedł XPS-8700). Nowa klasa mutex jest dwukrotnie szybsza niż mutex systemu Windows, ale wciąż jest mniejsza niż jedna dziesiąta szybkości obiektu CRITICAL_SECTION systemu Windows. Zauważ, że przetestowałem tylko nierekurencyjny mutex. Obiekty CRITICAL_SECTION są rekurencyjne (jeden wątek może je wprowadzać wielokrotnie, pod warunkiem, że opuszcza tę samą liczbę razy).

Stevens Miller
źródło
0

Funkcje AC są nazywane reentrantem, jeśli używa tylko swoich rzeczywistych parametrów.

Funkcje ponownego wchodzenia mogą być wywoływane jednocześnie przez wiele wątków.

Przykład funkcji ponownego wejścia:

int reentrant_function (int a, int b)
{
   int c;

   c = a + b;

   return c;
}

Przykład funkcji niewracającej ponownie:

int result;

void non_reentrant_function (int a, int b)
{
   int c;

   c = a + b;

   result = c;

}

Standardowa biblioteka C strtok () nie jest ponownie wprowadzana i nie może być używana przez 2 lub więcej wątków w tym samym czasie.

Niektóre platformy SDK są dostarczane z ponownie wprowadzaną wersją strtok () o nazwie strtok_r ();

Enrico Migliore

Enrico Migliore
źródło