Lock, mutex, semafor… jaka jest różnica?

Słyszałem te słowa związane z programowaniem równoległym, ale jaka jest między nimi różnica?

Blokada umożliwia wejście tylko jednego wątku do części, która jest zablokowana, a blokada nie jest współdzielona z żadnymi innymi procesami.

Muteks jest taki sam jak blokada, ale może być ogólnosystemowy (współdzielony przez wiele procesów).

Semafora działa tak samo jak mutex, ale pozwala x liczba wątków wejść, to może być wykorzystane na przykład ograniczyć liczbę CPU, IO lub ubijania intensywnych zadań uruchomionych w tym samym czasie.

Bardziej szczegółowy post o różnicach między muteksem a semaforem znajduje się tutaj .

Masz również blokady odczytu / zapisu, które pozwalają na nieograniczoną liczbę czytników lub 1 pisarz w danym momencie.

Istnieje wiele nieporozumień dotyczących tych słów.

To jest z poprzedniego postu ( https://stackoverflow.com/a/24582076/3163691 ), który doskonale pasuje tutaj:

1) Sekcja krytyczna = Obiekt użytkownika używany do umożliwienia wykonania tylko jednego aktywnego wątku z wielu innych w ramach jednego procesu . Pozostałe niewybrane wątki (@ pozyskanie tego obiektu) są uśpione .

[Brak możliwości przetwarzania, bardzo prymitywny obiekt].

2) Mutex Semaphore (alias Mutex) = Obiekt jądra używany do umożliwienia wykonania tylko jednego aktywnego wątku z wielu innych, wśród różnych procesów . Pozostałe niewybrane wątki (@ pozyskanie tego obiektu) są uśpione . Ten obiekt obsługuje własność wątku, powiadomienie o zakończeniu wątku, rekurencję (wielokrotne wywołania „pozyskaj” z tego samego wątku) i „unikanie priorytetowej inwersji”.

Możliwości międzyprocesowe, bardzo bezpieczny w użyciu, rodzaj obiektu synchronizacji „wysokiego poziomu”.

3) Counting Semaphore (alias Semaphore) = Obiekt jądra służący do wykonywania grupy aktywnych wątków z wielu innych. Pozostałe niewybrane wątki (@ pozyskanie tego obiektu) są uśpione .

[Zdolność międzyprocesowa nie jest jednak zbyt bezpieczna w użyciu, ponieważ brakuje w niej następujących atrybutów „mutex”: powiadomienia o zakończeniu wątku, rekurencji?, „Unikania inwersji priorytetów”? Itd.].

4) A teraz, mówiąc o „spinlockach”, najpierw kilka definicji:

Region krytyczny = region pamięci współdzielony przez 2 lub więcej procesów.

Blokada = zmienna, której wartość pozwala lub odmawia wejścia do „regionu krytycznego”. (Może być zaimplementowany jako prosta „flaga boolowska”).

Zajęte oczekiwanie = Ciągłe testowanie zmiennej, aż pojawi się jakaś wartość.

Wreszcie:

Spin-lock (inaczej Spinlock) = Blokada, która wykorzystuje zajęte oczekiwanie . ( Pozyskiwanie blokady odbywa się za pomocą xchg lub podobnych operacji atomowych ).

[Brak uśpienia wątku, najczęściej używany tylko na poziomie jądra. Nieefektywne dla kodu poziomu użytkownika].

Jako ostatni komentarz, nie jestem pewien, ale mogę postawić ci kilka dużych dolarów, że powyższe pierwsze 3 obiekty synchronizujące (# 1, # 2 i # 3) wykorzystują tę prostą bestię (# 4) w ramach ich implementacji.

Miłego dnia!.

Bibliografia:

Koncepcje czasu rzeczywistego dla systemów wbudowanych autorstwa Qing Li z Caroline Yao (CMP Books).

-Nowoczesne systemy operacyjne (3.) autorstwa Andrew Tanenbaum (Pearson Education International).

-Programowanie aplikacji dla Microsoft Windows (4.) autorstwa Jeffrey'a Richtera (Microsoft Programming Series).

Możesz także rzucić okiem na: https://stackoverflow.com/a/24586803/3163691

Większość problemów można rozwiązać za pomocą (i) samych blokad, (ii) tylko semaforów, ... lub (iii) kombinacji obu! Jak zapewne zauważyłeś, są one bardzo podobne: oba zapobiegają warunkom wyścigu , oba mają acquire()/ release()operacje, oba powodują zablokowanie / podejrzenie zerowej lub większej liczby wątków ... Naprawdę, zasadnicza różnica polega wyłącznie na tym , jak się blokują i odblokowują .

• Blokady (lub mutex ) ma dwa stany (0 lub 1). Można go odblokować lub zablokować . Są często używane, aby zapewnić, że tylko jeden wątek wchodzi w krytyczną sekcję na raz.
• Semafor ma wiele stanów (0, 1, 2, ...). Można go zablokować (stan 0) lub odblokować (stany 1, 2, 3, ...). Jeden lub więcej semaforów jest często używanych razem, aby zapewnić, że tylko jeden wątek wejdzie do sekcji krytycznej dokładnie wtedy, gdy liczba jednostek jakiegoś zasobu osiągnęła / nie osiągnęła określonej wartości (albo poprzez odliczanie do tej wartości, albo zliczanie do tej wartości ).

W przypadku obu blokad / semaforów próba wywołania, acquire()gdy operacja podstawowa znajduje się w stanie 0, powoduje zawieszenie wątku wywołującego. W przypadku zamków - próby uzyskania zamka są w stanie 1 zakończone powodzeniem. W przypadku semaforów - próby uzyskania blokady w stanach {1, 2, 3, ...} są udane.

W przypadku blokad w stanie 0, jeśli ten sam wątek, który wcześniej wywołał acquire(), teraz wywołuje polecenie release, wówczas wydanie jest udane. Jeśli próbował tego inny wątek - to, co się stanie, zależy od implementacji / biblioteki (zwykle próba jest ignorowana lub zgłaszany jest błąd). W przypadku semaforów w stanie 0 każdy wątek może wywołać zwolnienie i zakończy się powodzeniem (niezależnie od tego, który wątek poprzednio użył, aby ustawić semafor w stanie 0).

Z poprzedniej dyskusji możemy zobaczyć, że zamki mają pojęcie właściciela (jedynym wątkiem, który może wywołać release, jest właściciel), podczas gdy semafory nie mają właściciela (każdy wątek może wywołać release na semaforze).

Powoduje to wiele zamieszania, ponieważ w praktyce jest wiele odmian tej definicji wysokiego poziomu.

Ważne odmiany do rozważenia :

• Jak należy nazwać acquire()/ release()- [zmienia się masowo ]
• Czy twój zamek / semafor używa „kolejki” lub „zestawu” do zapamiętania oczekujących wątków?
• Czy twoją blokadę / semafor można współdzielić z wątkami innych procesów?
• Czy twoja blokada jest „reentrant”? - [Zwykle tak].
• Czy twoja blokada „blokuje / nie blokuje”? - [Zwykle nieblokujące są używane jako blokady blokujące (inaczej spin-blokady) powodują zajęte oczekiwanie].
• Jak upewnić się, że operacje są „atomowe”?

Zależy to od twojej książki / wykładowcy / języka / biblioteki / środowiska.
Oto krótka prezentacja z opisem, w jaki sposób niektóre języki odpowiadają na te szczegóły.

C, C ++ ( pthreads )

• Mutex jest realizowany poprzez pthread_mutex_t. Domyślnie nie można ich udostępniać innym procesom ( PTHREAD_PROCESS_PRIVATE), jednak mutex mają atrybut o nazwie pshared . Po ustawieniu muteks jest dzielony między procesy ( PTHREAD_PROCESS_SHARED).
• Blokada jest to samo, co mutex.
• Semafor jest realizowany poprzez sem_t. Podobnie jak muteksy, semafory mogą być współużytkowane przez trzy procesy wielu procesów lub utrzymywane w tajemnicy dla wątków jednego procesu. Zależy to od dostarczonego argumentu psharedsem_init .

python ( threading.py )

• Zamka ( threading.RLock) jest w większości taka sama jak C / C ++ pthread_mutex_tS. Obaj są ponownie wysłani . Oznacza to, że można je odblokować tylko przez ten sam wątek, który je zablokował. Dzieje się tak, gdy sem_tsemafory, threading.Semaphoresemafory i theading.Lockzamki nie są ponownie wysyłane - ponieważ w tym przypadku każdy wątek może odblokować / zablokować semafor.
• Muteks jest takie samo jak mocowanie (termin nie jest często używany w pytona).
• Semafora ( threading.Semaphore) jest w większości takie same, jak sem_t. Chociaż z sem_t, kolejka identyfikatorów wątków jest używana do zapamiętywania kolejności, w której wątki zostały zablokowane podczas próby zablokowania, gdy jest zablokowane. Gdy wątek odblokowuje semafor, pierwszy wątek w kolejce (jeśli taki istnieje) zostaje wybrany jako nowy właściciel. Identyfikator wątku jest usuwany z kolejki, a semafor zostaje ponownie zablokowany. Jednak z threading.Semaphore, zamiast kolejki używany jest zestaw, więc kolejność blokowania wątków nie jest zapisywana - każdy wątek w zestawie może zostać wybrany jako następny właściciel.

Java ( java.util.concurrent )

• Zamka ( java.util.concurrent.ReentrantLock) jest w większości taka sama jak C / C ++ pthread_mutex_t„S i Pythona threading.RLocktym, że sposób realizuje wielowejściowy zamka. Udostępnianie blokad między procesami jest trudniejsze w Javie, ponieważ JVM działa jako pośrednik. Jeśli wątek próbuje odblokować zamek, którego nie posiada, IllegalMonitorStateExceptionzostaje wyrzucony.
• Mutex jest taka sama jak zamkiem (termin nie jest często używany w Javie).
• Semafora ( java.util.concurrent.Semaphore) jest w większości takie same, jak sem_ti threading.Semaphore. Konstruktor semaforów Java akceptuje parametr boolean fairness , który kontroluje, czy użyć zestawu (false), czy kolejki (true) do przechowywania oczekujących wątków.

Teoretycznie semafory są często omawiane, ale w praktyce semafory nie są tak często używane. Semafor utrzymuje stan tylko jednej liczby całkowitej, więc często jest raczej mało elastyczny i wiele jest potrzebnych naraz - co powoduje trudności w zrozumieniu kodu. Ponadto fakt, że dowolny wątek może zwolnić semafor, jest czasem niepożądany. Zamiast tego używane są bardziej zorientowane obiektowo / nadrzędne poziomy synchronizacji / abstrakcje, takie jak „zmienne warunkowe” i „monitory”.

Spójrz na samouczek wielowątkowości autorstwa Johna Kopplina.

W sekcji Synchronizacja między wątkami wyjaśnia różnice między zdarzeniem, blokadą, muteksem, semaforem, licznikiem czasu oczekiwania

Mutex może być własnością tylko jeden wątek na raz, umożliwiając wątki koordynować wzajemnie wyłączny dostęp do zasobu udostępnionego

Obiekty przekroju krytycznego zapewniają synchronizację podobną do synchronizacji zapewnianej przez obiekty mutex, z tym wyjątkiem, że obiekty przekroju krytycznego mogą być używane tylko przez wątki jednego procesu

Inną różnicą między muteksem a sekcją krytyczną jest to, że jeśli obiekt sekcji krytycznej jest obecnie własnością innego wątku, EnterCriticalSection()czeka na własność w nieskończoność, natomiast WaitForSingleObject()w przypadku muteksu umożliwia określenie limitu czasu

Semafor utrzymuje liczyć od zera do wartości maksymalnej pewne ograniczenie liczby wątków, które są jednocześnie dostępu do udostępnionego zasobu.

Spróbuję opisać to przykładami:

Blokada: przykładem lockmoże być wspólny słownik, do którego dodawane są elementy (które muszą mieć unikalne klucze).
Blokada zapewni, że jeden wątek nie wejdzie w mechanizm kodu, który sprawdza, czy element znajduje się w słowniku, podczas gdy inny wątek (czyli w sekcji krytycznej) już przeszedł to sprawdzenie i dodaje element. Jeśli inny wątek spróbuje wprowadzić zablokowany kod, zaczeka (zostanie zablokowany), aż obiekt zostanie zwolniony.

private static readonly Object obj = new Object();

lock (obj) //after object is locked no thread can come in and insert item into dictionary on a different thread right before other thread passed the check...
{
    if (!sharedDict.ContainsKey(key))
    {
        sharedDict.Add(item);
    }
}

Semafor: Powiedzmy, że masz pulę połączeń, a następnie pojedynczy wątek może zarezerwować jeden element w puli, czekając, aż semafor uzyska połączenie. Następnie korzysta z połączenia, a po zakończeniu pracy zwalnia połączenie, zwalniając semafor.

Przykład kodu, który kocham, to bramkarz podany przez @Patric - oto:

using System;
using System.Collections.Generic;
using System.Text;
using System.Threading;

namespace TheNightclub
{
    public class Program
    {
        public static Semaphore Bouncer { get; set; }

        public static void Main(string[] args)
        {
            // Create the semaphore with 3 slots, where 3 are available.
            Bouncer = new Semaphore(3, 3);

            // Open the nightclub.
            OpenNightclub();
        }

        public static void OpenNightclub()
        {
            for (int i = 1; i <= 50; i++)
            {
                // Let each guest enter on an own thread.
                Thread thread = new Thread(new ParameterizedThreadStart(Guest));
                thread.Start(i);
            }
        }

        public static void Guest(object args)
        {
            // Wait to enter the nightclub (a semaphore to be released).
            Console.WriteLine("Guest {0} is waiting to entering nightclub.", args);
            Bouncer.WaitOne();          

            // Do some dancing.
            Console.WriteLine("Guest {0} is doing some dancing.", args);
            Thread.Sleep(500);

            // Let one guest out (release one semaphore).
            Console.WriteLine("Guest {0} is leaving the nightclub.", args);
            Bouncer.Release(1);
        }
    }
}

Mutex Jest dość Semaphore(1,1)powszechny i ​​często używany na całym świecie (szerokie zastosowanie, w przeciwnym razie lockbardziej odpowiednie). Jednego użyłby globalny Mutexpodczas usuwania węzła z globalnie dostępnej listy (ostatnią rzeczą, którą chcesz, aby inny wątek coś zrobił podczas usuwania węzła). Gdy zdobędziesz, Mutexjeśli inny wątek spróbuje go uzyskać Mutex, zostanie on uśpiony, dopóki SAMY wątek, który go nabył, Mutexgo nie zwolni.

Dobrym przykładem tworzenia globalnego muteksu jest @deepee

class SingleGlobalInstance : IDisposable
{
    public bool hasHandle = false;
    Mutex mutex;

    private void InitMutex()
    {
        string appGuid = ((GuidAttribute)Assembly.GetExecutingAssembly().GetCustomAttributes(typeof(GuidAttribute), false).GetValue(0)).Value.ToString();
        string mutexId = string.Format("Global\\{{{0}}}", appGuid);
        mutex = new Mutex(false, mutexId);

        var allowEveryoneRule = new MutexAccessRule(new SecurityIdentifier(WellKnownSidType.WorldSid, null), MutexRights.FullControl, AccessControlType.Allow);
        var securitySettings = new MutexSecurity();
        securitySettings.AddAccessRule(allowEveryoneRule);
        mutex.SetAccessControl(securitySettings);
    }

    public SingleGlobalInstance(int timeOut)
    {
        InitMutex();
        try
        {
            if(timeOut < 0)
                hasHandle = mutex.WaitOne(Timeout.Infinite, false);
            else
                hasHandle = mutex.WaitOne(timeOut, false);

            if (hasHandle == false)
                throw new TimeoutException("Timeout waiting for exclusive access on SingleInstance");
        }
        catch (AbandonedMutexException)
        {
            hasHandle = true;
        }
    }


    public void Dispose()
    {
        if (mutex != null)
        {
            if (hasHandle)
                mutex.ReleaseMutex();
            mutex.Dispose();
        }
    }
}

następnie użyj:

using (new SingleGlobalInstance(1000)) //1000ms timeout on global lock
{
    //Only 1 of these runs at a time
    GlobalNodeList.Remove(node)
}

Mam nadzieję, że to pozwoli Ci zaoszczędzić trochę czasu.

Wikipedia ma świetną sekcję na temat różnic między semaforami i muteksami :

Muteks jest zasadniczo tym samym co semafor binarny i czasami używa tej samej podstawowej implementacji. Różnice między nimi to:

Muteksy mają pojęcie właściciela, który jest procesem, który zablokował muteks. Tylko proces, który zablokował muteks, może go odblokować. Natomiast semafor nie ma pojęcia właściciela. Każdy proces może odblokować semafor.

W przeciwieństwie do semaforów muteksy zapewniają bezpieczeństwo inwersji priorytetowej. Ponieważ mutex zna swojego obecnego właściciela, możliwe jest promowanie priorytetu właściciela, ilekroć zadanie o wyższym priorytecie zacznie czekać na muteksie.

Muteksy zapewniają również bezpieczeństwo usuwania, w przypadku którego proces przechowywania muteksu nie może zostać przypadkowo usunięty. Semafory tego nie zapewniają.

Rozumiem, że muteks jest przeznaczony do użycia tylko w jednym procesie, ale w wielu wątkach, podczas gdy semafor może być używany w wielu procesach i odpowiadających im zestawach wątków.

Muteks jest również binarny (jest zablokowany lub odblokowany), podczas gdy semafor ma pojęcie liczenia lub kolejkę więcej niż jednego żądania blokady i odblokowania.

Czy ktoś może zweryfikować moje wyjaśnienie? Mówię w kontekście Linuksa, w szczególności Red Hat Enterprise Linux (RHEL) wersja 6, która wykorzystuje jądro 2.6.32.

Wykorzystanie programowania C w wariancie Linux jako podstawowy przypadek dla przykładów.

Zamek:

• Zwykle bardzo prosta konstrukcja binarna działająca albo zablokowana, albo odblokowana

• Brak koncepcji własności wątku, priorytetu, sekwencjonowania itp.

• Zwykle blokada wirowania, w której nić stale sprawdza dostępność zamków.

• Zwykle opiera się na operacjach atomowych, np. Testuj i ustawiaj, porównuj i wymieniaj, pobieraj i dodawaj itp.

• Zwykle wymaga wsparcia sprzętowego dla operacji atomowych.

Blokady plików:

• Zwykle używany do koordynowania dostępu do pliku za pośrednictwem wielu procesów.

• Wiele procesów może utrzymywać blokadę odczytu, jednak gdy jakikolwiek pojedynczy proces posiada blokadę zapisu, żaden inny proces nie może uzyskać blokady odczytu lub zapisu.

• Przykład: flock, fcntl itp.

Mutex:

• Wywołania funkcji Mutex zwykle działają w przestrzeni jądra i powodują wywołania systemowe.

• Wykorzystuje pojęcie własności. Tylko wątek, który obecnie zawiera muteks, może go odblokować.

• Mutex nie jest rekurencyjny (wyjątek: PTHREAD_MUTEX_RECURSIVE).

• Zwykle używany w powiązaniu ze zmiennymi warunkowymi i przekazywany jako argumenty np. Pthread_cond_signal, pthread_cond_wait itp.

• Niektóre systemy UNIX zezwalają na używanie muteksu w wielu procesach, chociaż może to nie być wymuszone we wszystkich systemach.

Semafor:

• Jest to liczba całkowita utrzymywana przez jądro, której wartości nie mogą spaść poniżej zera.

• Można go użyć do synchronizacji procesów.

• Wartość semafora może być ustawiona na wartość większą niż 1, w którym to przypadku zwykle wskazuje liczbę dostępnych zasobów.

• Semafor, którego wartość jest ograniczona do 1 i 0, jest określany jako semafor binarny.

Supporting ownership, maximum number of processes share locka maximum number of allowed processes/threads in critical sectionsą to trzy główne czynniki, które określają nazwę / typ współbieżnego obiektu z ogólną nazwą lock. Ponieważ wartości tych czynników są binarne (mają dwa stany), możemy je podsumować w tabeli 3 * 8 przypominającej prawdę.

• X (Obsługuje własność?): Nie (0) / tak (1)
• T (# procesy udostępniania):> 1 (∞) / 1
• Z (# procesów / wątków w CA):> 1 (∞) / 1

  X   Y   Z          Name
 --- --- --- ------------------------
  0   ∞   ∞   Semaphore              
  0   ∞   1   Binary Semaphore       
  0   1   ∞   SemaphoreSlim          
  0   1   1   Binary SemaphoreSlim(?)
  1   ∞   ∞   Recursive-Mutex(?)     
  1   ∞   1   Mutex                  
  1   1   ∞   N/A(?)                 
  1   1   1   Lock/Monitor           

Zmodyfikuj lub rozwiń tę tabelę, opublikowałem ją jako tabelę ascii, aby była edytowalna :)