Was ist das Wiedereintrittsschloss und das Konzept im Allgemeinen?

Ich bin immer verwirrt. Würde jemand erklären, was wieder eintritt in verschiedenen Kontexten bedeutet? Und warum sollten Sie wiedereintrittsfähig oder nicht wiedereintrittsfähig verwenden?

Sagen wir pthread (posix) sperrende Grundelemente, sind sie wiedereinsteigend oder nicht? Welche Fallstricke sollten bei der Verwendung vermieden werden?

Ist Mutex wieder am Start?

Wiedereintrittssperre

Eine Wiedereintrittssperre ist eine Sperre, bei der ein Prozess die Sperre mehrmals beanspruchen kann, ohne sich selbst zu blockieren. Dies ist in Situationen nützlich, in denen es nicht einfach ist, den Überblick zu behalten, ob Sie bereits ein Schloss ergriffen haben. Wenn ein Schloss nicht wiedereintritt, können Sie das Schloss greifen und dann blockieren, wenn Sie es erneut greifen, wodurch Ihr eigener Prozess effektiv blockiert wird.

Wiedereintritt im Allgemeinen ist eine Eigenschaft von Code, bei der es keinen zentralen veränderlichen Status gibt, der beschädigt werden könnte, wenn der Code während der Ausführung aufgerufen würde. Ein solcher Aufruf könnte von einem anderen Thread oder rekursiv von einem Ausführungspfad erfolgen, der aus dem Code selbst stammt.

Wenn der Code auf einem freigegebenen Status basiert, der während der Ausführung aktualisiert werden könnte, wird er nicht erneut eingegeben, zumindest nicht, wenn diese Aktualisierung ihn beschädigen könnte.

Ein Anwendungsfall für die Wiedereintrittssperre

Ein (etwas allgemeines und erfundenes) Beispiel für eine Anwendung für eine Wiedereintrittssperre könnte sein:

• Sie haben einige Berechnungen mit einem Algorithmus, der einen Graphen durchläuft (möglicherweise mit Zyklen). Eine Durchquerung kann denselben Knoten aufgrund der Zyklen oder aufgrund mehrerer Pfade zu demselben Knoten mehr als einmal besuchen.

• Die Datenstruktur unterliegt einem gleichzeitigen Zugriff und kann aus irgendeinem Grund möglicherweise von einem anderen Thread aktualisiert werden. Sie müssen in der Lage sein, einzelne Knoten zu sperren, um mögliche Datenbeschädigungen aufgrund von Rennbedingungen zu beheben. Aus irgendeinem Grund (möglicherweise aufgrund der Leistung) möchten Sie nicht die gesamte Datenstruktur global sperren.

• Ihre Berechnung kann keine vollständigen Informationen darüber enthalten, welche Knoten Sie besucht haben, oder Sie verwenden eine Datenstruktur, mit der Fragen, bei denen ich schon einmal hier war, nicht schnell beantwortet werden können.
  
  Ein Beispiel für diese Situation wäre eine einfache Implementierung des Dijkstra-Algorithmus mit einer Prioritätswarteschlange, die als binärer Heap implementiert ist, oder eine Breitensuche unter Verwendung einer einfachen verknüpften Liste als Warteschlange. In diesen Fällen ist das Durchsuchen der Warteschlange nach vorhandenen Einfügungen O (N), und Sie möchten dies möglicherweise nicht bei jeder Iteration tun.

In dieser Situation ist es teuer zu verfolgen, welche Sperren Sie bereits erworben haben. Angenommen, Sie möchten die Sperre auf Knotenebene durchführen, verringert ein neu eintretender Sperrmechanismus die Notwendigkeit, festzustellen, ob Sie zuvor einen Knoten besucht haben. Sie können den Knoten einfach blind sperren und ihn möglicherweise entsperren, nachdem Sie ihn aus der Warteschlange entfernt haben.

Wiedereintretende Mutexe

Ein einfacher Mutex wird nicht erneut eingegeben, da sich zu einem bestimmten Zeitpunkt nur ein Thread im kritischen Bereich befinden kann. Wenn Sie den Mutex greifen und dann versuchen, ihn erneut zu greifen, verfügt ein einfacher Mutex nicht über genügend Informationen, um festzustellen, wer ihn zuvor gehalten hat. Um dies rekursiv zu tun, benötigen Sie einen Mechanismus, bei dem jeder Thread ein Token hatte, damit Sie erkennen können, wer den Mutex gepackt hat. Dies macht den Mutex-Mechanismus etwas teurer, so dass Sie dies möglicherweise nicht in allen Situationen tun möchten.

IIRC Die POSIX-Threads-API bietet die Option für neu eintretende und nicht wiedereintretende Mutexe.

Mit einer Wiedereintrittssperre können Sie eine Methode schreiben M, die die Ressource sperrt Aund dann Mrekursiv oder aus Code aufruft, der bereits eine Sperre enthältA .

Mit einer nicht wiedereintretenden Sperre benötigen Sie zwei Versionen von M, eine, die sperrt und eine, die nicht sperrt, und zusätzliche Logik, um die richtige aufzurufen.

Die Wiedereintrittssperre wird in diesem Tutorial sehr gut beschrieben .

Das Beispiel im Tutorial ist weit weniger erfunden als in der Antwort zum Durchlaufen eines Diagramms. Eine Wiedereintrittssperre ist in sehr einfachen Fällen nützlich.

Das Was und Warum von rekursivem Mutex sollte nicht so kompliziert sein, wie in der akzeptierten Antwort beschrieben.

Ich möchte mein Verständnis nach einigem Stöbern im Netz aufschreiben.

Zunächst sollten Sie sich darüber im Klaren sein, dass bei der Diskussion über Mutex definitiv auch Multithread-Konzepte eine Rolle spielen. (Mutex wird für die Synchronisation verwendet. Ich brauche keinen Mutex, wenn ich nur 1 Thread in meinem Programm habe.)

Zweitens sollten Sie den Unterschied zwischen einem normalen Mutex und einem rekursiven Mutex kennen .

Zitiert aus APUE :

(Ein rekursiver Mutex ist a) Ein Mutex-Typ, mit dem derselbe Thread ihn mehrmals sperren kann, ohne ihn zuvor zu entsperren.

Der Hauptunterschied besteht darin, dass das erneute Sperren einer rekursiven Sperre innerhalb desselben Threads weder zu einem Deadlock führt noch den Thread blockiert.

Bedeutet dies, dass ein Recusive Lock niemals einen Deadlock verursacht?
Nein, es kann immer noch zu einem Deadlock als normalem Mutex führen, wenn Sie ihn in einem Thread gesperrt haben, ohne ihn zu entsperren, und versuchen, ihn in anderen Threads zu sperren.

Sehen wir uns einen Code als Beweis an.

1. normaler Mutex mit Deadlock

#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);

}

Ausgabe:

thread1
thread1 hey hey
thread2

häufiges Deadlock-Beispiel, kein Problem.

2. rekursiver Mutex mit Deadlock

Kommentieren Sie diese Zeile einfach aus
error = pthread_mutexattr_settype(&lock_attr, PTHREAD_MUTEX_RECURSIVE);
Kommentieren Sie und kommentieren Sie die andere aus.

Ausgabe:

thread1
thread1 hey hey
thread2

Ja, rekursiver Mutex kann auch einen Deadlock verursachen.

3. normaler Mutex, im selben Thread erneut sperren

#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);

}

Ausgabe:

thread1
func3
thread2

Deadlock in thread t1, in func3.
(Ich benutze es sleep(2), um leichter zu erkennen, dass der Deadlock zuerst durch erneutes Sperren verursacht wird. func3)

4. rekursiver Mutex, im selben Thread erneut sperren

Kommentieren Sie erneut die rekursive Mutex-Zeile aus und kommentieren Sie die andere Zeile aus.

Ausgabe:

thread1
func3
func3 hey hey
thread1 hey hey
thread2

Deadlock in thread t2, in func2. Sehen? func3Wird beendet und beendet, blockiert das erneute Verriegeln nicht den Faden oder führt zu einem Deadlock.

Letzte Frage, warum brauchen wir das?

Für rekursive Funktionen (wird in Multithread-Programmen aufgerufen und Sie möchten einige Ressourcen / Daten schützen).

Beispiel: Sie haben ein Multithread-Programm und rufen in Thread A eine rekursive Funktion auf. Sie haben einige Daten, die Sie in dieser rekursiven Funktion schützen möchten, und verwenden daher den Mutex-Mechanismus. Die Ausführung dieser Funktion erfolgt sequentiell in Thread A, sodass Sie den Mutex definitiv in Rekursion erneut sperren würden. Die Verwendung von normalem Mutex führt zu Deadlocks. Und resursiver Mutex erfunden, um dies zu lösen.

Sehen Sie sich ein Beispiel aus der akzeptierten Antwort an. Wann wird rekursiver Mutex verwendet? .

Die Wikipedia erklärt den rekursiven Mutex sehr gut. Auf jeden Fall eine Lektüre wert. Wikipedia: Reentrant_mutex