Co to jest blokada ponownego wejścia i ogólnie koncepcja?

Zawsze się mylę. Czy ktoś mógłby wyjaśnić, co oznacza Reentrant w różnych kontekstach? I dlaczego miałbyś chcieć użyć ponownego wtajemniczenia vs. niewracającego?

Powiedz prymitywy blokujące pthread (posix), czy są one ponownie wchodzące, czy nie? Jakich pułapek należy unikać podczas ich używania?

Czy mutex powraca?

Blokowanie ponownego wejścia

Blokada ponownego wejścia to taka, w której proces może żądać blokady wiele razy bez blokowania się. Jest to przydatne w sytuacjach, w których nie jest łatwo śledzić, czy już złapałeś zamek. Jeśli blokada nie jest ponownie wprowadzana, możesz ją chwycić, a następnie zablokować, gdy idziesz, aby ją chwycić ponownie, skutecznie blokując własny proces.

Ogólnie rzecz biorąc, ponowne wejście jest właściwością kodu, w którym nie ma centralnego stanu, w którym można by modyfikować, który mógłby zostać uszkodzony, gdyby kod został wywołany podczas wykonywania. Takie wywołanie mogłoby być wykonane przez inny wątek lub rekurencyjnie przez ścieżkę wykonania pochodzącą z samego kodu.

Jeśli kod opiera się na stanie współdzielonym, który może zostać zaktualizowany w trakcie jego wykonywania, nie jest on ponownie wprowadzany, a przynajmniej nie, jeśli ta aktualizacja mogłaby go złamać.

Przypadek użycia dla ponownego wejścia do blokowania

Przykładem (nieco ogólnym i wymyślonym) wniosku o blokadę ponownego wejścia może być:

• Masz pewne obliczenia obejmujące algorytm, który przechodzi przez wykres (być może z cyklami). Przechodzenie może odwiedzać ten sam węzeł więcej niż jeden raz z powodu cykli lub wielu ścieżek do tego samego węzła.

• Struktura danych podlega współbieżnemu dostępowi i może z jakiegoś powodu zostać zaktualizowana, na przykład przez inny wątek. Musisz mieć możliwość blokowania poszczególnych węzłów, aby poradzić sobie z potencjalnym uszkodzeniem danych z powodu warunków wyścigu. Z jakiegoś powodu (być może wydajności) nie chcesz globalnie blokować całej struktury danych.

• Twoje obliczenia nie mogą zachować pełnych informacji o odwiedzonych węzłach lub używasz struktury danych, która nie pozwala na szybkie udzielenie odpowiedzi na pytania typu „czy byłem tu wcześniej”.
  
  Przykładem takiej sytuacji może być prosta implementacja algorytmu Dijkstry z kolejką priorytetową zaimplementowaną jako stos binarny lub przeszukiwanie wszerz przy użyciu prostej połączonej listy jako kolejki. W takich przypadkach skanowanie kolejki pod kątem istniejących wstawień to O (N) i możesz nie chcieć tego robić w każdej iteracji.

W tej sytuacji śledzenie posiadanych zamków jest kosztowne. Zakładając, że chcesz wykonać blokowanie na poziomie węzła, mechanizm blokowania ponownego wejścia zmniejsza potrzebę stwierdzenia, czy wcześniej odwiedzałeś węzeł. Możesz po prostu na ślepo zablokować węzeł, być może odblokowując go po wyjęciu z kolejki.

Ponowne wejście muteksów

Prosty mutex nie jest ponownie wprowadzany, ponieważ tylko jeden wątek może znajdować się w sekcji krytycznej w danym momencie. Jeśli złapiesz muteks, a następnie spróbujesz go złapać ponownie, prosty mutex nie ma wystarczających informacji, aby powiedzieć, kto go wcześniej trzymał. Aby zrobić to rekurencyjnie, potrzebujesz mechanizmu, w którym każdy wątek miałby token, abyś mógł stwierdzić, kto złapał muteks. To sprawia, że ​​mechanizm mutex jest nieco droższy, więc możesz nie chcieć tego robić we wszystkich sytuacjach.

IIRC API wątków POSIX oferuje opcję muteksów re-entrant i non-re-entrant.

Blokada ponownego wejścia umożliwia napisanie metody, Mktóra nakłada blokadę na zasób, Aa następnie wywołuje Mrekursywnie lub z kodu, który już blokuje A.

Z blokadą Mjednokrotną potrzebowałbyś 2 wersji , jednej, która blokuje i jednej, która nie, oraz dodatkowej logiki, aby wywołać właściwą.

Blokada ponownego wejścia jest bardzo dobrze opisana w tym samouczku .

Przykład w samouczku jest znacznie mniej wymyślny niż w odpowiedzi dotyczącej przechodzenia przez wykres. Blokada ponownego wejścia jest przydatna w bardzo prostych przypadkach.

Co i dlaczego rekurencyjnego muteksu nie powinno być tak skomplikowaną rzeczą opisaną w przyjętej odpowiedzi.

Chciałbym spisać swoje zrozumienie po pewnym kopaniu w sieci.

Po pierwsze, powinieneś zdać sobie sprawę, że kiedy mówisz o muteksie , z pewnością chodzi również o koncepcje wielowątkowe. (mutex jest używany do synchronizacji. Nie potrzebuję muteksu, jeśli mam tylko 1 wątek w moim programie)

Po drugie, powinieneś znać różnicę między normalnym muteksem a rekurencyjnym muteksem .

Cytat z APUE :

(Rekurencyjny mutex to a) Typ muteksu, który pozwala temu samemu wątkowi na wielokrotne blokowanie go bez uprzedniego odblokowania.

Kluczowa różnica polega na tym, że w ramach tego samego wątku ponowne zablokowanie blokady rekurencyjnej nie prowadzi do zakleszczenia ani nie powoduje zablokowania wątku.

Czy to oznacza, że ​​blokada recuzyjna nigdy nie powoduje zakleszczenia?
Nie, nadal może powodować zakleszczenie jako normalny muteks, jeśli zablokowałeś go w jednym wątku bez odblokowania go i spróbujesz zablokować go w innych wątkach.

Zobaczmy jakiś kod jako dowód.

1. normalny mutex z zakleszczeniem

#include <pthread.h>
#include <stdio.h>

pthread_mutex_t lock;


void * func1(void *arg){
    printf("thread1\n");
    pthread_mutex_lock(&lock);
    printf("thread1 hey hey\n");

}


void * func2(void *arg){
    printf("thread2\n");
    pthread_mutex_lock(&lock);
    printf("thread2 hey hey\n");
}

int main(){
    pthread_mutexattr_t lock_attr;
    int error;
//    error = pthread_mutexattr_settype(&lock_attr, PTHREAD_MUTEX_RECURSIVE);
    error = pthread_mutexattr_settype(&lock_attr, PTHREAD_MUTEX_DEFAULT);
    if(error){
        perror(NULL);
    }

    pthread_mutex_init(&lock, &lock_attr);

    pthread_t t1, t2;

    pthread_create(&t1, NULL, func1, NULL);
    pthread_create(&t2, NULL, func2, NULL);

    pthread_join(t2, NULL);

}

wynik:

thread1
thread1 hey hey
thread2

typowy przykład zakleszczenia, nie ma problemu.

2. rekurencyjny mutex z zakleszczeniem

Po prostu odkomentuj tę linię
error = pthread_mutexattr_settype(&lock_attr, PTHREAD_MUTEX_RECURSIVE);
i skomentuj drugą.

wynik:

thread1
thread1 hey hey
thread2

Tak, rekurencyjny mutex może również powodować zakleszczenie.

3. normalny mutex, zablokuj ponownie w tym samym wątku

#include <pthread.h>
#include <stdio.h>
#include <unistd.h>

pthread_mutex_t lock;


void func3(){
    printf("func3\n");
    pthread_mutex_lock(&lock);
    printf("func3 hey hey\n");
}

void * func1(void *arg){
    printf("thread1\n");
    pthread_mutex_lock(&lock);
    func3();
    printf("thread1 hey hey\n");

}


void * func2(void *arg){
    printf("thread2\n");
    pthread_mutex_lock(&lock);
    printf("thread2 hey hey\n");
}

int main(){
    pthread_mutexattr_t lock_attr;
    int error;
//    error = pthread_mutexattr_settype(&lock_attr, PTHREAD_MUTEX_RECURSIVE);
    error = pthread_mutexattr_settype(&lock_attr, PTHREAD_MUTEX_DEFAULT);
    if(error){
        perror(NULL);
    }

    pthread_mutex_init(&lock, &lock_attr);

    pthread_t t1, t2;

    pthread_create(&t1, NULL, func1, NULL);
    sleep(2); 
    pthread_create(&t2, NULL, func2, NULL);

    pthread_join(t2, NULL);

}

wynik:

thread1
func3
thread2

Impas w thread t1, w func3.
(Używam, sleep(2)aby łatwiej zobaczyć, że zakleszczenie jest spowodowane najpierw ponownym zablokowaniem func3)

4. rekurencyjny mutex, blokuj ponownie w tym samym wątku

Ponownie odkomentuj rekursywną linię muteksu i skomentuj drugą linię.

wynik:

thread1
func3
func3 hey hey
thread1 hey hey
thread2

Impas w thread t2, w func2. Widzieć? func3kończy się i wychodzi, ponowne zablokowanie nie blokuje nici ani nie prowadzi do zakleszczenia.

Więc ostatnie pytanie, dlaczego tego potrzebujemy?

Dla funkcji rekurencyjnej (wywoływanej w programach wielowątkowych i chcesz chronić niektóre zasoby / dane).

Np. Masz program wielowątkowy i wywołujesz funkcję rekurencyjną w wątku A. Masz pewne dane, które chcesz chronić w tej funkcji rekurencyjnej, więc używasz mechanizmu mutex. Wykonywanie tej funkcji jest sekwencyjne w wątku A, więc na pewno ponownie zablokowałbyś muteks w rekurencji. Użyj normalnego muteksu powoduje zakleszczenia. I resursive mutex jest wymyślony, aby rozwiązać ten problem.

Zobacz przykład z zaakceptowanej odpowiedzi. Kiedy używać rekurencyjnego muteksu? .

Wikipedia bardzo dobrze wyjaśnia rekurencyjny muteks. Na pewno warto poczytać. Wikipedia: Reentrant_mutex