Deadlock

Lorsqu'on commence à avoir beaucoup de méthodes ou blocs synchronized, comme on l'a dit précédemment, le programme devient de moins en moins concurrent. De plus, on peut se retrouver face à des deadlocks. Il s'agit d'un état dans lequel le programme est tout simplement bloqué et plus rien ne va pouvoir se passer, le programme ne pourra jamais se terminer. Pour comprendre cela, regardons un moment la figure suivante.

Figure 2.5 Deadlock.

Alice désire inviter Bob et Charles à une super fête, et leurs demande donc si ils veulent venir. Bob ne vient que si Charles vient, et vice-versa. On est donc dans une situation où plus rien ne bouge, Bob attend la réponse de Charles qui attend celle de Bob. On est coincé, on est dans un deadlock.

Graphe d'allocation des ressources

Prenons un exemple où un deadlock pourrait survenir dans un programme. Le listing suivant montre un exemple avec deux threads qui désirent obtenir les lockA et lockB.

Si le premier thread obtient les deux locks lockA et lockB avant que le second thread ne s'exécute, il n'y a aucun problème. Le second thread sera bloqué jusqu'à ce que le premier ait fini de s'exécuter. Par contre, si chaque thread a réussi à avoir un lock, on se retrouve dans une situation de deadlock. On peut voir qu'il y aura bien deadlock en dessinant le graphe d'allocation des ressources, montré sur la figure suivante.

Figure 2.6 Graphe d'allocation des ressources.

Les cercles représentent les threads et les rectangles représentent les ressources que désirent obtenir les threads, à savoir les locks. Lorqu'une ressource est détenue par un thread, on l'indique par une flèche held-by qui va de la ressource vers le thread. Lorsqu'un thread veut une ressource, on l'indique par une flèche requests allant du thread vers la ressource désirée. Si on trouve un cycle dans ce graphe, c'est qu'on est en situation de deadlock, c'est-à-dire qu'aucun thread ne peut plus rien faire car ils sont tous en attente d'une ou plusieurs ressource qu'ils ne pourront jamais avoir.

Exemple

Voyons un exemple concret qui pourrait conduire à un deadlock. Soit une classe Purse représentant un portemonnaie. On va définir une méthode de classe transfer permettant d'effectuer un transfert d'argent d'une portemonnaie vers un autre. Le listing suivant vous montre cette méthode.

Étant donné que l'état des deux portemonnaies va être modifié par la méthode, il faut s'assurer que le thread qui exécute la méthode possède les locks des deux objets avant de pouvoir faire le transfert. Supposons maintenant qu'il y a deux portemonnaies A et B que deux threads veulent effectuer un transfert. Le premier thread voulant faire un transfert de A vers B et le second thread de B vers A. En fonction de l'ordonnancement des threads, plusieurs situations différentes peuvent se produire. La figure suivante montre les quatre situations possibles, en montrant les locks obtenus par les deux threads. On voit que si chaque thread a juste le temps d'exécuter le premier synchronized, on est dans une situation de deadlock, chaque thread possède l'un des deux locks et attends pour voir l'autre, ce qui ne sera jamais possible.

Une solution possible est de rendre la méthode transfer synchronized. Mais cela implique qu'il ne pourra jamais y avoir deux transferts en même temps, même si les portemonnaies impliqués ne sont pas du tout les mêmes.