Interblocage

Un article de Wikipédia, l'encyclopédie libre.

Un interblocage (deadlock en anglais, appelé aussi étreinte fatale) est un phénomène qui peut survenir en programmation concurrente. L'interblocage se produit lorsque deux processus légers (thread) concurrents s'attendent mutuellement. Les processus bloqués dans cet état le sont définitivement, il s'agit donc d'une situation catastrophique. C'est E.G Coffman (1971 St Gravé) principalement qui a étudié les mécanismes conduisant aux phénomènes d'interblocage.

[modifier] Exemples

Un exemple concret d'interblocage peut se produire lorsque deux processus légers essayent d'acquérir deux verrous dans un ordre différent. Ainsi, si par exemple il y a deux mutex (nommés M1 et M2) et les deux processus légers suivants :

TâcheA :
  Obtenir M1
  Obtenir M2
  Action nécessitant les deux verrous
  Rendre M2
  Rendre M1

TâcheB :
  Obtenir M2
  Obtenir M1
  Action nécessitant les deux verrous
  Rendre M1
  Rendre M2

Un interblocage est possible. En effet, si par exemple, la séquence d'opération suivante survient :

1. La TâcheA obtient M1.
2. La TâcheB obtient M2.
3. La TâcheA attend pour obtenir M2 (qui est entre les mains de TâcheB).
4. La TâcheB attend pour obtenir M1 (qui est entre les mains de TâcheA).

Dans cette situation, les deux tâches (TâcheA et TâcheB) sont définitivement bloquées.

[modifier] Solutions pour éviter les interblocages

Il n'existe aucune solution permettant d'éviter tous les interblocages. Il est par contre possible de prendre des mesures pour limiter le risque d'interblocage, à commencer par une analyse très précise de l'application à écrire.

Une méthode consiste à toujours acquérir les mutex (exclusion mutuelle) dans le même ordre. En effet, si plusieurs processus légers (thread) nécessitent d'acquérir plusieurs verrous pour effectuer leur travail, s'ils acquièrent les verrous dans un ordre différent, il est possible qu'ils se bloquent lors de la séquence d'acquisition (comme dans l'exemple précédent).

Il convient aussi de s'intéresser aux priorités des processus. En effet, si par exemple un processus de haute priorité utilise un verrou en commun avec un processus de basse priorité (voir aussi inversion de priorité), il est possible d'obtenir des situations de blocage. Une solution à ce genre de problème consiste à n'utiliser des verrous qu'entre des processus de même priorité.

[modifier] Référence

• Luigi Zaffalon et Pierre Breguet, Programmation concurrente et temps réel avec ADA 95, Presses polytechniques et universitaires romandes, Lausanne, 1999

• Portail de l’informatique