DEADLOCK

## Un deadlock ? Qu'est-ce que c'est ?

Un **deadlock** en informatique est une situation d'impasse où plusieurs processus dans un système sont bloqués en attente d'une ressource détenue par un autre processus empêchant ainsi toute progression.

Pour illustrer cette situation, prenons un exemple de vie réelle.

*Dans la circulation, on peut se retrouver dans un embouteillage, causé par un accident ou un obstacle quelconque sur la route, les voitures et motos (les processus) , avant cet obstacle, veulent tous accéder à l'espace pour circuler, mais cet espace est détenu par l'obstacle (processus bloquant ) qui n'est pas en mesure de le libérer l'espace (la ressource) créant ainsi un blocage, un embouteillage.*

Comment peut-on alors se retrouver une situation de deadlock ?
## Différents types de deadlocks

Pour avoir un **deadlock** il suffit que les quatre (04) conditions suivantes sont remplies simultanément :

1) **Exclusion mutuelle (Mutual exclusion)**
L'exclusion mutuelle repose sur l'idée qu'une ressource critique ne doit pas être utilisée simultanément par plusieurs processus ou threads
***Exemple** :
Imaginons un système de réservation en ligne où deux utilisateurs tentent de réserver le dernier billet disponible pour un concert. Sans exclusion mutuelle, il est possible que les deux utilisateurs croient avoir réservé le billet, créant ainsi une incohérence dans le système.*

2) **Rétention et attente (Hold and Wait)**
La condition de **rétention et attente** se manifeste lorsqu'un processus détient une ou plusieurs ressources critiques qu’il n’a pas encore libérées, et ce même processus attend activement d’autres ressources nécessaires pour poursuivre son exécution.

**Exemple**:
*Imaginons un immeuble avec un parking souterrain accessible via une clé électronique. Cette clé est également nécessaire pour ouvrir la porte principale de l’immeuble. Voici la situation :

1. ***Personne A** est dans le parking. Elle a la clé et souhaite accéder à l’immeuble via la porte principale, mais elle attend qu'une place de parking se libère pour garer sa voiture.*
2. ***Personne B** est à l’intérieur de l’immeuble. Elle souhaite accéder au parking pour récupérer sa voiture, mais elle attend que **Personne A** utilise la clé pour lui ouvrir l’accès.*
3) **Non-préemption**
Elle se produit lorsqu'un processus ou un thread ne peut pas libérer volontairement une ressource qu'il détient tant qu'il n'a pas terminé son utilisation.
**Exemple** :
*Imaginons deux enfants qui jouent à des jeux de société à la maison.*

1. ***Enfant A** utilise un puzzle pour jouer.*
2. ***Enfant B** veut jouer avec le même puzzle, mais la règle est que **Enfant A** doit finir son puzzle avant de le rendre.*
3. *Pendant ce temps, **Enfant B** reste bloqué en attendant.*
4) **Attente circulaire (Circular Wait)**
Une attente circulaire se produit lorsqu’un ensemble de processus ou de threads se bloquent mutuellement en attendant des ressources, formant un cycle fermé d’attentes.
**Exemple**:
*Imaginons qu'il y a trois voitures (V1, V2, V3) dans un parking étroit avec des places en enfilade, et chaque voiture bloque l'accès à une autre :*

1. ***V1** est garée de façon à bloquer la sortie de **V2** et attend que **V3** se déplace pour pouvoir sortir.*
2. ***V2** est garée de manière à bloquer la sortie de **V3** et attend que **V1** se déplace pour pouvoir sortir.*
3. ***V3** est garée de façon à bloquer la sortie de **V1** et attend que **V2** se déplace pour pouvoir sortir.*

*Les trois voitures sont dans une situation d'attente circulaire :*

- *V1 attend V2, qui attend V3, qui attend V1.*
- *Aucune voiture ne peut avancer sans que l'autre se déplace, ce qui mène à une impasse où personne ne peut sortir.*

## Comment Prévenir et Résoudre les Deadlocks ?

#### 1. **Prévention de Deadlock**

La **prévention de deadlock** consiste à empêcher une ou plusieurs des quatre conditions nécessaires à la formation d’un deadlock. Ces conditions sont l'exclusion mutuelle, la possession et attente, la non-préemption, et l'attente circulaire. Voici les stratégies pour les éviter :

- **Éviter l'exclusion mutuelle** :
- Bien que l'exclusion mutuelle soit souvent inévitable (par exemple, accès en écriture dans une base, utilisations des verrous et semaphores), elle peut être réduite ou modifiée dans certaines situations. Les ressources peuvent être utilisées simultanément par plusieurs processus sans problème, par exemple, les données en lecture seule ou certaines structures de données partagées.
- **Interdire la possession et l'attente** :
- Les processus doivent obtenir toutes les ressources dont ils ont besoin au début de leur exécution. Si un processus ne peut pas obtenir toutes les ressources nécessaires, il doit se retirer et attendre d'avoir accès à toutes les ressources en même temps. Cela empêche un processus de détenir une ressource tout en en attendant une autre. Par exemple, si un processus exécute `SELECT FOR UPDATE` et ne peut pas obtenir le verrou sur une ligne en raison d'un autre processus ayant déjà acquis ce verrou, il peut relâcher tous ses verrous et recommencer la demande une fois que la ligne est libérée
- **Éviter la non-préemption** :
- Lorsque les processus détiennent des ressources et demandent d'autres ressources, ces ressources détenues peuvent être révoquées (précédemment non-préemptibles). Ainsi, si un processus attend une ressource, et qu’il ne peut pas l’obtenir immédiatement, les ressources qu'il détient peuvent être préemptées et allouées à d'autres processus.
- **Éviter l'attente circulaire** :
- Imposer un ordre strict d'acquisition des ressources. Par exemple, les processus doivent demander les ressources dans un ordre prédéfini. Si chaque processus suit cet ordre, aucune boucle d'attente circulaire ne pourra se former. Par exemple, un processus devra toujours obtenir R1 avant R2, et jamais l’inverse.

#### 2. **Détection de Deadlock**

La **détection de deadlock** consiste à surveiller le système pour identifier si un deadlock s'est produit. Si un deadlock est détecté, le système peut prendre des mesures pour résoudre la situation.

- **Algorithmes de détection** :
- Un algorithme de détection de deadlock examine l’état du système et les relations d’attente entre les processus. Le système construit un **graphe d’attente** ou **graphe de ressources**, où les processus et les ressources sont représentés sous forme de nœuds et les dépendances (attentes) sous forme d’arcs. Si un cycle est détecté dans ce graphe, un deadlock est présent.
- **Avantages** :
- La détection de deadlock est efficace lorsqu'elle peut être effectuée à intervalles réguliers et que le système est capable d'examiner les dépendances entre processus sans impact majeur sur les performances.
- **Inconvénients** :
- La détection peut être coûteuse en termes de ressources et de temps, surtout dans les systèmes avec un grand nombre de processus et de ressources.

#### 3. **Éviter un Deadlock**

L'**évitement de deadlock** est une approche proactive qui implique que le système analyse les demandes de ressources avant de les accorder pour éviter qu'un deadlock ne se produise. Contrairement à la prévention, l’évitement permet de libérer des ressources lorsqu’un deadlock est détecté avant qu’il ne se produise.

- **Algorithme du banquier** (Banker's Algorithm) :
- Cet algorithme est un exemple classique d’évitement de deadlock. Il permet de déterminer si une demande de ressources peut être accordée sans risquer un deadlock. Le système examine la **sécurité** des demandes en fonction des ressources disponibles et des ressources dont les processus ont besoin. Si la demande entraîne un état de non-sécurité (c'est-à-dire qu'un deadlock peut survenir), la ressource n'est pas allouée.
- **Avantages** :
- L’évitement garantit qu’un deadlock ne se produira jamais tant que le système fonctionne de manière sécurisée.
- **Inconvénients** :
- L’algorithme de banquier peut être coûteux en termes de performances, car chaque demande de ressources doit être vérifiée pour garantir la sécurité avant son allocation.

#### 4. **Récupération de Deadlock**

La **récupération de deadlock** se produit après qu’un deadlock ait été détecté. L'objectif ici est de sortir d’un deadlock sans avoir à redémarrer tout le système.

- **Annulation de processus** :

- Le système peut choisir d’annuler l’un des processus impliqués dans le deadlock. Ce processus peut être annulé de manière complète ou partielle, et ses ressources peuvent être libérées. Après avoir libéré les ressources, le système tente de reprendre l'exécution.
- **Prise de ressources** :

- Une autre approche consiste à **reprendre les ressources** détenues par un processus bloqué. Ces ressources peuvent ensuite être allouées à d’autres processus, permettant au système de sortir du deadlock.
- **Rétrogradation** :

- Si un processus ne peut pas terminer ou se libérer, il peut être rétrogradé dans un état antérieur, permettant ainsi de résoudre les conflits sans tuer le processus.
- **Avantages** :

- Ces méthodes permettent de sortir d’un deadlock sans devoir redémarrer ou réinitialiser l’ensemble du système.
- **Inconvénients** :

- L'annulation ou la prise de ressources peut entraîner une perte de travail ou des incohérences dans les données. Cela doit être géré de manière prudente pour éviter des effets secondaires indésirables.