TNSI : Processus - Interblocage / Deadlock

Introduction

Le Système d'Exploitation dispose d'un ordonnanceur qui permet de gérer les accès concurrents aux ressources (des accès qui peuvent être réalisés de manière indépendante, et dans un ordre quelconque - non séquentiel) et prévenir certains problèmes d'accès aux ressources (interblocage/deadlock, famines, etc..) ¹.

Un Problème de Synchronisation

Une Situation

• Considérons un programme de jeu multijoueurs (par ex. minecraft) utilisant une variable globale nb_epees qui représente le nombre d'épées sur un même serveur/monde.
• Cette variable globale nb_epees en réserve (commune) est gérée par une même fonction.
• Imaginons deux joueurs utilisant cette même fonction

Des Processus Concurrents

• La double exécution de cette fonction se traduit par la création de deux processus P1 et P2.
• Supposons maintenant qu'il ne reste qu'une seule épée en réserve:
  • P1 est élu, lance la prise d'une épée, mais est interrompu par l'ordonnanceur pour élire P2 avant que P1 n'ait décrémenté nb_epees.
  • P2 a, quant à lui, le temps de décrémenter nb_epees. Quand P1 est élu à nouveau, il reprend où il en était et ne vérifie pas s'il reste une épée et ne voit donc pas d'anomalie.
• Chaque joueur se retrouve donc avec une épée, alors qu'il n'en restait plus qu'une

Pour gérer convenablement les accès concurrents à des mémoires partagés, des systèmes de Verrous et de Sémaphores⁷ (voire de moniteurs ⁸, qui ne seront pas détaillés ici) sont le plus souvent mis en place.

Processus Concurrents

Dans ce cas, on dit que les processus P1 et P2 sont concurrents car ils sollicitent tous deux la (ou les) mêmes ressources, de manière indépendante l'un de l'autre, sur des intervalles de temps entrelacés (qui se chevauchent, entre leur début et leur fin).

Programmation Concurrente

La Programmation Concurrente permet de gérer et d'optimiser l'exécution de processus concurrents.

Un Problème d'Interblocage

Une analogie humoristique

Col

Le Courrier de l'Eure

Col

4 Priorités à droite... circulaires

Interblocage

Imaginons dans cette partie que deux processus P1 et P2 se répartissent deux ressources : R1 et R2.

• P1 est élu, demande et obtient une ressource R1, puis :
• P1 est commuté par l'ordonnanceur : P2 est élu, demande et obtient R2,
• P2 demande R1, mais il ne peut l'obtenir car détenue par P1
• P2 est donc commuté : P1 est élu (car R1 est détenue par P1) et il demande R2, mais il ne peut pas l'obtenir car R2 est détenu par P2.
• P1 est à son tour commuté : P2 est élu (car R2 est détenue par P2) et il demande R1
• etc..
• Les processus sont alors bloqués dans l'attente l'un de l'autre dans un cycle sans fin : On parle dans ce cas d'interblocage / deadlock . Des solutions (détection/guérison ou prévention) sont mises en place qui ne seront pas étudiées ici.

Caractérisation des Interblocages

• Ensemble de Ressources:
  • Partageables, ou pas
  • Réquisitionnables, ou pas
• Chaque Ressource est dans l'état:
  • Libre
  • Verrouillée en mode exclusif
  • Verrouillée en mode partagé
• Chaque Processus utilise une ressource de la manière suivante :
  • Demande (si conflit \(\rightarrow\) attente)
  • utilisation
  • libération

\(\quad\quad\quad\) État Demande	Libre	Verrou Partagé	Verrou Exclusif
Partagé	Oui	Oui	conflit
Exclusif	Oui	conflit	conflit

Les Conditions de Coffman

La situation d'interblocage est le grand danger de la progammation concurrente : Elle a été théorisée par l'informaticien Edward Coffman (1934-)⁴ qui a énoncé, dans un article de \(1971\), quatre conditions nécessaires et suffisantes (appelées conditions de coffman) pour mener à l'interblocage :

• Exclusion mutuelle (mutex) : au moins une des ressources du système doit être en accès exclusif.
• Rétention des ressources : un processus détient au moins une ressource et requiert une autre ressource détenue par un autre processus
• Non préemption : Seul le détenteur d'une ressource peut la libérer.
• Attente circulaire : Chaque processus attend une ressource détenue par un autre processus. P1 attend une ressource détenue par P2 qui à son tour attend une ressource détenue par (P3 etc... qui attend une ressource détenue par) P1, ce qui clos la boucle.

Il existe heureusement des stratégies pour éviter ces situations. Nous ne rentrerons pas ici dans ces considérations qui dépassent le cadre du programme.

Références et Notes

---

1. Guillaume Connan, Problèmes d'Interblocage ↩

2. Olivier LECLUSE, Gestion des Processus ↩

3. Processus & Threads, Linux Attitude ↩

4. Conditions de Coffman, wikipedia ↩

5. Cours Progammation Système, Sémaphores ↩

6. Introduction à la Programmation Concurrente, reds.heig-vd.ch ↩

7. Vidéo d'Intro à la Programmation Concurrente, les Sémaphores, Univ Grenoble ↩

8. Moniteurs, wikipedia ↩

9. Communication Inter-Processus, wikipedia ↩