Date de création 01/11/2007
Dernière mise à jour: 21/11/2007
Source de cette page: http://yves.maguer.free.fr/dead_lock/no_more_dead_lock.html
Voir mon CV
Objet
Cette page indique comment empêcher l'interblocage (étreinte fatale) lors de l'exécution de code qui s'exécute en parallèle (threads) et qui peut se bloquer (deadlock) lors de l'utilisation de mutex (système d'exclusion mutuelle, sémaphore).
La solution que je propose consiste à modifier le code existant pour ajouter un identifiant à chaque thread et à ses sous programmes, ainsi qu'a utiliser des fonctions "lock" et "unlock" qui contiennent un algorithme, qui lui-même détermine si l'application s'apprète à rentrer dans un deadlock, lors de chaque appel à la fonction "lock".
Description du problème à résoudre
Le cas de blocage dans un seul thread consiste à appeler 2 fois de suite lock dans le même thread, sans unlock entre.
Ce cas (trivial) est également traité par mon algorithme. Cependant je montre l'exmple avec 2 threads:
Le mutex X est pris par A, donc les lock suivants sur X (dans thread B) attendront qu'il soit débloqué par unlock X.
Le mutex Y est pris par B, donc les lock suivants sur Y (dans thread A) attendront qu'il soit débloqué par unlock Y
On peut constater dans l'exmple, qu'il y a interblocage des threads. Ceci est indépendant de l'endroit d'ou se fait le lock, dans un sous programme par exemple.
L'interblocage ne consomme par de temps UC, puisque les thread sont bloqués par les mutex.
Solution
La représentation du problème est un arbre orienté (mutex A bloque thread B, et thread B bloque mutex C).
Un interblocage consiste en un cycle dans cet arbre. Mon algorithme ne fait pas de parcours dans l'arbre. Le temps d'exécution doit rester court. Mon algorithme s'exécute en moins de 5ms sans que je sache combien (valeur 000ms affichée avec "GetSystemTime (&Stm)" ).
Mon algorithme consiste à supprimer toutes les feuilles de l'arbre (ceux qui ne bloquent personne sont supprimés de l'arbre, récursivement).
Lorsque le nombre de feuilles supprimées est égal à zéro, si l'arbre est vide, c'est qu'il n'y a pas de cycle, donc on peux faire l'appel à la fonction lock de bas niveau.
Si l'arbre n'est pas vide, c'est qu'il contient un cycle, donc un interblocage.
L'action à réaliser dans ce cas est de vôtre responsabilité. On peut par exemple:
- faire unlock du premier lock du cycle (le plus vieux),
- tuer et relancer l'application,
- ne pas faire le lock,
- faire unlock et lock du premier bloqueur puis faire le lock demandé,
- réécrire l'application pour ne pas imbriquer les lock/unlock, etc...
Je vais construire un tableau qui contiendra en colonnes les noms des thread, et en lignes le noms des mutex.
Je construis également une liste des threads qui sont les premiers à prendre un mutex (les bloqueurs).
Le tableau sera rempli à chaque appel de "safe_lock", la surcouche de lock, qui contient mon algorithme. Idem pour "safe_unlock" qui modifie le tableau. La récursivité pour supprimer les feuilles, se fera par une boucle "while" sur le tableau, plutôt que par un appel de fonction.
Les appels à "safe_lock" et "safe_unlock" contiendront les paramètres "identifiant du thread" que je nommerais "ID_thr", et "identifiant du mutex" que je nommerais "ID_mut".
Pour disposer de ID_thr, il faut ajouter ce paramètre à toute fonction du programme qui peut faire un appel à "safe_lock" ou "safe_unlock". Dans chaque thread, il faut ajouter l'affectation à ID_thr, à une valeur différente pour chaque thread.
Ensuite, il faut remplacer dans toute l'application, les appels à lock et unlock, par des appels à "safe_lock" et "safe_unlock".
Pour manipuler le tableau qui va gérer l'état des lock, je devrais bloquer par un mutex mon propre algorithme. Le même mutex servira pour "safe_lock" et "safe_unlock".
deadlock temporaire
Une situation de deadlock entre thread A et B, par exemple, peut être débloquée si un troisième thread C effectue un unlock sur un des mutex qui bloque A et B. Ceci ne devrait pas être normal si l'application est bien écrite.
Le résultat, dans ce cas, est un blocage temporaire des threads A et B. Mon algorithme peut donc servir à mettre en évidence les cas ou cela se produit, dans un fichier de log, par exemple.
code source de l'algorithme
J'ai codé mon algorithme (en C++, Visual C++ 6.0, Microsoft) dans le cadre professionnel, donc le code source ne m'appartient pas.
Cependant, vous pouvez contacter "Studelec", 2 rue Paul Mesplé, 31100 Toulouse, pour voir les conditions d'utilisation.
compatibilité
J'ai appliqué mon algorithme sur les mutex de POSIX, mais mon algorithme s'applique sur tout système similaire.
Mes fonctions "safe_lock" et "safe_unlock" sont donc des surcouches de "pthread_mutex_lock ()" et "pthread_mutex_unlock ()".
De la même façon, mon algorithme peut être traduit dans un autre langage informatique.
Le même besoin existe pour bloquer des accès aux bases de données, ou des cas d'interblocages peuvent être diagnostiqués ou solutionnés par mon algorithme.
Objet
Cette page indique comment empêcher l'interblocage (étreinte fatale) lors de l'exécution de code qui s'exécute en parallèle (threads) et qui peut se bloquer (deadlock) lors de l'utilisation de mutex (système d'exclusion mutuelle, sémaphore).
La solution que je propose consiste à modifier le code existant pour ajouter un identifiant à chaque thread et à ses sous programmes, ainsi qu'a utiliser des fonctions "lock" et "unlock" qui contiennent un algorithme, qui lui-même détermine si l'application s'apprète à rentrer dans un deadlock, lors de chaque appel à la fonction "lock".
Description du problème à résoudre
Le cas de blocage dans un seul thread consiste à appeler 2 fois de suite lock dans le même thread, sans unlock entre.
Ce cas (trivial) est également traité par mon algorithme. Cependant je montre l'exmple avec 2 threads:
Le mutex X est pris par A, donc les lock suivants sur X (dans thread B) attendront qu'il soit débloqué par unlock X.
Le mutex Y est pris par B, donc les lock suivants sur Y (dans thread A) attendront qu'il soit débloqué par unlock Y
On peut constater dans l'exmple, qu'il y a interblocage des threads. Ceci est indépendant de l'endroit d'ou se fait le lock, dans un sous programme par exemple.
L'interblocage ne consomme par de temps UC, puisque les thread sont bloqués par les mutex.
Solution
La représentation du problème est un arbre orienté (mutex A bloque thread B, et thread B bloque mutex C).
Un interblocage consiste en un cycle dans cet arbre. Mon algorithme ne fait pas de parcours dans l'arbre. Le temps d'exécution doit rester court. Mon algorithme s'exécute en moins de 5ms sans que je sache combien (valeur 000ms affichée avec "GetSystemTime (&Stm)" ).
Mon algorithme consiste à supprimer toutes les feuilles de l'arbre (ceux qui ne bloquent personne sont supprimés de l'arbre, récursivement).
Lorsque le nombre de feuilles supprimées est égal à zéro, si l'arbre est vide, c'est qu'il n'y a pas de cycle, donc on peux faire l'appel à la fonction lock de bas niveau.
Si l'arbre n'est pas vide, c'est qu'il contient un cycle, donc un interblocage.
L'action à réaliser dans ce cas est de vôtre responsabilité. On peut par exemple:
- faire unlock du premier lock du cycle (le plus vieux),
- tuer et relancer l'application,
- ne pas faire le lock,
- faire unlock et lock du premier bloqueur puis faire le lock demandé,
- réécrire l'application pour ne pas imbriquer les lock/unlock, etc...
Je vais construire un tableau qui contiendra en colonnes les noms des thread, et en lignes le noms des mutex.
Je construis également une liste des threads qui sont les premiers à prendre un mutex (les bloqueurs).
Le tableau sera rempli à chaque appel de "safe_lock", la surcouche de lock, qui contient mon algorithme. Idem pour "safe_unlock" qui modifie le tableau. La récursivité pour supprimer les feuilles, se fera par une boucle "while" sur le tableau, plutôt que par un appel de fonction.
Les appels à "safe_lock" et "safe_unlock" contiendront les paramètres "identifiant du thread" que je nommerais "ID_thr", et "identifiant du mutex" que je nommerais "ID_mut".
Pour disposer de ID_thr, il faut ajouter ce paramètre à toute fonction du programme qui peut faire un appel à "safe_lock" ou "safe_unlock". Dans chaque thread, il faut ajouter l'affectation à ID_thr, à une valeur différente pour chaque thread.
Ensuite, il faut remplacer dans toute l'application, les appels à lock et unlock, par des appels à "safe_lock" et "safe_unlock".
Pour manipuler le tableau qui va gérer l'état des lock, je devrais bloquer par un mutex mon propre algorithme. Le même mutex servira pour "safe_lock" et "safe_unlock".
deadlock temporaire
Une situation de deadlock entre thread A et B, par exemple, peut être débloquée si un troisième thread C effectue un unlock sur un des mutex qui bloque A et B. Ceci ne devrait pas être normal si l'application est bien écrite.
Le résultat, dans ce cas, est un blocage temporaire des threads A et B. Mon algorithme peut donc servir à mettre en évidence les cas ou cela se produit, dans un fichier de log, par exemple.
code source de l'algorithme
J'ai codé mon algorithme (en C++, Visual C++ 6.0, Microsoft) dans le cadre professionnel, donc le code source ne m'appartient pas.
Cependant, vous pouvez contacter "Studelec", 2 rue Paul Mesplé, 31100 Toulouse, pour voir les conditions d'utilisation.
compatibilité
J'ai appliqué mon algorithme sur les mutex de POSIX, mais mon algorithme s'applique sur tout système similaire.
Mes fonctions "safe_lock" et "safe_unlock" sont donc des surcouches de "pthread_mutex_lock ()" et "pthread_mutex_unlock ()".
De la même façon, mon algorithme peut être traduit dans un autre langage informatique.
Le même besoin existe pour bloquer des accès aux bases de données, ou des cas d'interblocages peuvent être diagnostiqués ou solutionnés par mon algorithme.