Qu'est-ce que le verrouillage et le concept Re-entrant en général?

91

Je suis toujours confus. Quelqu'un expliquerait-il ce que Reentrant signifie dans différents contextes? Et pourquoi voudriez-vous utiliser réentrant ou non réentrant?

Dites primitives de verrouillage pthread (posix), sont-elles réentrantes ou non? Quels pièges faut-il éviter lors de leur utilisation?

Le mutex est-il réentrant?

vehomzzz
la source

Réponses:

157

Verrouillage rentrant

Un verrou réentrant est un verrou dans lequel un processus peut réclamer le verrou plusieurs fois sans se bloquer. C'est utile dans les situations où il n'est pas facile de savoir si vous avez déjà saisi une serrure. Si un verrou n'est pas rentrant, vous pouvez saisir le verrou, puis le bloquer lorsque vous le récupérez, bloquant ainsi efficacement votre propre processus.

La réentrance en général est une propriété du code dans laquelle il n'a pas d'état central modifiable qui pourrait être corrompu si le code était appelé pendant son exécution. Un tel appel pourrait être effectué par un autre thread, ou il pourrait être effectué de manière récursive par un chemin d'exécution provenant du code lui-même.

Si le code repose sur un état partagé qui pourrait être mis à jour au milieu de son exécution, il n'est pas rentrant, du moins pas si cette mise à jour pourrait le casser.

Un cas d'utilisation pour le verrouillage rentrant

Un exemple (quelque peu générique et artificiel) d'application pour un verrou rentrant pourrait être:

  • Vous avez un calcul impliquant un algorithme qui parcourt un graphe (peut-être avec des cycles). Une traversée peut visiter le même nœud plus d'une fois en raison des cycles ou en raison de plusieurs chemins vers le même nœud.

  • La structure de données est sujette à un accès simultané et pourrait être mise à jour pour une raison quelconque, peut-être par un autre thread. Vous devez être en mesure de verrouiller des nœuds individuels pour faire face à une corruption potentielle des données en raison de conditions de concurrence. Pour une raison quelconque (peut-être des performances), vous ne souhaitez pas verrouiller globalement toute la structure de données.

  • Votre calcul ne peut pas conserver des informations complètes sur les nœuds que vous avez visités, ou vous utilisez une structure de données qui ne permet pas de répondre rapidement aux questions «ai-je déjà été ici».

    Un exemple de cette situation serait une simple implémentation de l'algorithme de Dijkstra avec une file d'attente prioritaire implémentée comme un tas binaire ou une recherche en largeur en utilisant une simple liste chaînée comme file d'attente. Dans ces cas, l'analyse de la file d'attente pour les insertions existantes est O (N) et vous pouvez ne pas vouloir le faire à chaque itération.

Dans cette situation, garder une trace des verrous que vous avez déjà acquis coûte cher. En supposant que vous souhaitiez effectuer le verrouillage au niveau du nœud, un mécanisme de verrouillage réentrant vous évite d'avoir à dire si vous avez déjà visité un nœud. Vous pouvez simplement verrouiller aveuglément le nœud, peut-être le déverrouiller après l'avoir sorti de la file d'attente.

Mutex rentrants

Un simple mutex n'est pas rentrant car un seul thread peut être dans la section critique à un moment donné. Si vous attrapez le mutex et que vous essayez de le récupérer à nouveau, un simple mutex n'a pas assez d'informations pour dire qui le détenait auparavant. Pour ce faire de manière récursive, vous avez besoin d'un mécanisme où chaque thread avait un jeton afin que vous puissiez dire qui avait attrapé le mutex. Cela rend le mécanisme mutex un peu plus cher, vous ne voudrez peut-être pas le faire dans toutes les situations.

IIRC l'API des threads POSIX offre l'option de mutex rentrants et non rentrants.

ConcernedOfTunbridgeWells
la source
2
Bien que de telles situations doivent généralement être évitées de toute façon, car il est également difficile d'éviter les impasses, etc. Le filetage est de toute façon assez difficile sans que l'on doute que vous ayez déjà un verrou.
Jon Skeet
+1, considérez également le cas où le verrou n'est PAS réentrant, vous pouvez vous bloquer si vous ne faites pas attention. De plus, en C, vous n'avez pas les mêmes mécanismes que les autres langages pour vous assurer que le verrou est libéré autant de fois qu'il est acquis. Cela peut entraîner de gros problèmes.
user7116
1
c'est exactement ce qui m'est arrivé hier: je n'ai pas pris en compte la question de la réintégration et j'ai fini par déboguer une impasse pendant 5 heures ...
vehomzzz
@Jon Skeet - Je pense qu'il y a probablement des situations (voir mon exemple quelque peu artificiel ci-dessus) où le suivi des verrous n'est pas pratique en raison des performances ou d'autres considérations.
ConcernedOfTunbridgeWells
21

Un verrou ré-entrant vous permet d'écrire une méthode Mqui met un verrou sur la ressource A, puis d'appeler Mrécursivement ou à partir d'un code qui détient déjà un verrou A.

Avec un verrou non rentrant, vous auriez besoin de 2 versions de M, une qui verrouille et une qui ne le fait pas, et une logique supplémentaire pour appeler la bonne.

Henk Holterman
la source
Cela signifie-t-il que si j'ai des appels récursifs acquérant le même verrou obj plus d'une fois - disons des xfois par un thread donné, je ne peux pas entrelacer l'exécution sans libérer tous les verrous acquis de manière récursive (même verrou mais pour un xnombre de fois)? Si c'est vrai, cela rend essentiellement cette implémentation séquentielle. Est-ce que je manque quelque chose?
DevdattaK
Cela ne devrait pas être un vrai problème mondial. Il s'agit plus de verrouillage granulaire et qu'un thread ne se verrouille pas.
Henk Holterman
16

Le verrou réentrant est très bien décrit dans ce tutoriel .

L'exemple du didacticiel est beaucoup moins artificiel que dans la réponse concernant le parcours d'un graphe. Un verrou réentrant est utile dans des cas très simples.

Ratna Beresford
la source
3

Le quoi et le pourquoi du mutex récursif ne devraient pas être une chose aussi compliquée décrite dans la réponse acceptée.

Je voudrais noter ma compréhension après quelques recherches sur le net.


Tout d'abord, vous devez comprendre que lorsque vous parlez de mutex , les concepts multi-threads sont également impliqués. (le mutex est utilisé pour la synchronisation. Je n'ai pas besoin de mutex si je n'ai qu'un seul thread dans mon programme)


Deuxièmement, vous devez connaître la différence entre un mutex normal et un mutex récursif .

Cité de l' APUE :

(Un mutex récursif est a) Un type de mutex qui permet au même thread de le verrouiller plusieurs fois sans le déverrouiller au préalable.

La principale différence est que dans le même fil , le reverrouillage d'un verrou récursif ne conduit pas à un blocage, ni ne bloque le thread.

Cela signifie-t-il que le verrouillage récursif ne provoque jamais de blocage?
Non, cela peut toujours provoquer un blocage en tant que mutex normal si vous l'avez verrouillé dans un thread sans le déverrouiller et essayez de le verrouiller dans d'autres threads.

Voyons du code comme preuve.

  1. mutex normal avec blocage
#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);

}

production:

thread1
thread1 hey hey
thread2

exemple commun de blocage, pas de problème.

  1. mutex récursif avec blocage

Décommentez simplement cette ligne
error = pthread_mutexattr_settype(&lock_attr, PTHREAD_MUTEX_RECURSIVE);
et commentez l'autre.

production:

thread1
thread1 hey hey
thread2

Oui, le mutex récursif peut également provoquer un blocage.

  1. mutex normal, reverrouiller dans le même thread
#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);

}

production:

thread1
func3
thread2

Impasse dans thread t1, dans func3.
(J'utilise sleep(2)pour rendre plus facile de voir que le blocage est d'abord causé par le reverrouillage func3)

  1. mutex récursif, reverrouiller dans le même thread

Encore une fois, décommentez la ligne mutex récursive et commentez l'autre ligne.

production:

thread1
func3
func3 hey hey
thread1 hey hey
thread2

Impasse dans thread t2, dans func2. Voir? func3se termine et se termine, le reverrouillage ne bloque pas le thread ou ne mène pas à un blocage.


Alors, dernière question, pourquoi en avons-nous besoin?

Pour la fonction récursive (appelée dans les programmes multi-threads et vous souhaitez protéger certaines ressources / données).

Par exemple, vous avez un programme multi-thread et appelez une fonction récursive dans le thread A. Vous avez des données que vous souhaitez protéger dans cette fonction récursive, vous utilisez donc le mécanisme mutex. L'exécution de cette fonction est séquentielle dans le thread A, donc vous reverrouilleriez définitivement le mutex en récursivité. L'utilisation d'un mutex normal provoque des blocages. Et mutex résursif est inventé pour résoudre ce problème.

Voir un exemple de la réponse acceptée Quand utiliser le mutex récursif? .

Le Wikipedia explique très bien le mutex récursif. Vaut vraiment le détour. Wikipédia: Reentrant_mutex

Meule
la source