J’ai écrit en début d’année un verrou permettant de contourner les deadlocks en java.
Avant d’en expliquer le fonctionnement, un rapide petit rappel sur ce qu’est une situation de deadlock:

Etape 1: le premier thread acquiert le verrou numéro 1.
Etape 2: le second thread acquiert le verrou numéro 2.
Etape 3: le premier thread cherche maintenant à acquérir le deuxième verrou. Il doit donc attendre que le deuxième thread n’en soit plus propriétaire.
Etape 4: le deuxième thread cherche maintenant à acquérir le premier verrou. Il doit donc attendre que le premier thread n’en soit plus propriétaire.

Cette situation est une situation d’inter-blocage: chacun des deux threads attend que l’autre libère le verrou qu’il possède, le programme est donc bloqué.

Détection d’une situation d’interblocage
Pour écrire un algorithme permettant de résoudre ce problème, il faut commencer par savoir le détecter. Ce n’est pas très évident avec cet exemple, alors voyons un peu une situation d’inter-blocage impliquant 4 threads et 4 verrous:

On voit désormais qu’une situation d’inter-blocage se manifeste par la création d’un cycle: en partant d’un thread quelconque et en allant de verrou en thread et de thread en verrou, on retombe sur le thread de départ.
Cette remarque faîte, il devient relativement aisé de concevoir un algorithme qui détecte une telle situation. En voici un exemple en pseudo-code:


pour chaque verrou
     si le propriétaire du verrou est le thread qui lance la vérification
          alors pour chaque threads demandeurs de ce verrou
               if(isDeadLock(demandeur))
                    un cycle a été détecté



isDeadLock(thread):
     si le thread passé en paramètre est le thread courant
          un cycle a été détecté
     sinon
          pour chaque verrou dont le thread est propriétaire
               pour chaque demandeur de ces verrous
                         isDeadLock(demandeur)


Intégration de l’algorithme dans notre verrou
Le fonctionnement interne d’un verrou est le suivant:

Il reste donc à intégrer notre algorithme de détection de cycle au coeur de ce système et effectuer les opérations nécessaires selon que la détection soit positive (abandon au moyen d’une exception) ou non (poursuite de l’attente).

Durant la période d’attente, chaque thread devra donc régulièrement s’assurer qu’un cycle n’a pas été constitué; cela n’implique pas nécessairement une attente active puisqu’il est possible de donner en paramètre de la fonction wait un délais au delà duquel le thread devra se réveiller s’il n’a pas été notifié.