Architectures matérielles

L'interblocage

Que se passe-t-il quand plusieurs processus s'attendent mutuellement, pour toujours ? Le dîner des philosophes, un graphe, et comment éviter le blocage.

Durée · 2h Chapitre · B.2 / 2

Au programme

Objectifs de la séance

Mettre en évidence le risque d'interblocage entre plusieurs processus, le représenter avec un graphe, et connaître des stratégies pour l'éviter.

Activité 1

Le dîner des philosophes

Cinq philosophes autour d'une table ronde, cinq fourchettes (une entre chaque paire de voisins). Pour manger, chacun a besoin de ses deux fourchettes.

Règle : chaque philosophe affamé prend d'abord sa fourchette gauche, puis essaie de prendre celle de droite.

Si les 5 philosophes prennent tous leur fourchette gauche en même temps, que se passe-t-il ?

Chacun tient sa fourchette gauche et attend la droite, déjà tenue par son voisin (qui l'attend lui-même). Tous sont bloqués simultanément : c'est un interblocage. Sans intervention extérieure, la situation persiste indéfiniment.

Cours

Qu'est-ce que l'interblocage ?

Un interblocage (deadlock) est une situation dans laquelle plusieurs processus s'attendent mutuellement pour obtenir des ressources, si bien qu'aucun d'entre eux ne peut progresser.

Analogie : chaque philosophe joue le rôle d'un processus, chaque fourchette le rôle d'une ressource.

Cours

Le graphe d'attente

On représente la situation par un graphe : processus et ressources sont des sommets. Une flèche processus → ressource signifie « attend » ; une flèche ressource → processus signifie « est détenue par ».

À retenir : une situation d'interblocage correspond, dans ce graphe, à l'existence d'un cycle.

Exercice guidé

Un cycle à 2 processus

P1 détient R1 et attend R2. P2 détient R2 et attend R1.

Le cycle P1 → R2 → P2 → R1 → P1 se referme : il y a interblocage.

Cours

Comment éviter l'interblocage ?

Ordre total sur les ressources : chaque processus doit toujours demander ses ressources dans le même ordre (ex. toujours la fourchette de plus petit numéro d'abord).
Limiter les demandes simultanées : restreindre le nombre de processus pouvant demander des ressources en même temps.
Détecter puis résoudre : le système vérifie périodiquement l'existence d'un cycle dans le graphe d'attente, et interrompt un processus si besoin.

Si le philosophe n°5 prend sa fourchette de droite en premier, l'interblocage initial est-il encore possible ?

Non : en rompant la symétrie (un philosophe demande ses fourchettes dans l'ordre inverse des autres), on empêche la formation d'un cycle complet. Au moins un philosophe pourra toujours manger, ce qui débloque progressivement les autres. C'est le principe de l'ordre total sur les ressources.

Exercice type bac

À toi de jouer

1. Condition nécessaire pour qu'un interblocage se produise ?

Chaque processus impliqué détient au moins une ressource tout en attendant une ressource détenue par un autre processus du même groupe, formant une chaîne d'attente circulaire (un cycle).

2. Exemple avec deux imprimantes partagées

Le programme A réserve l'imprimante 1 et attend l'imprimante 2. Le programme B réserve l'imprimante 2 et attend l'imprimante 1. Aucun ne peut terminer ni libérer sa ressource : interblocage.

À ton rythme

Exercices gradués

Niveau 1

Explique ce qu'est un interblocage, en une ou deux phrases, avec tes propres mots.

Niveau 2

P1 détient R1 et R2. P2 attend R1. Y a-t-il interblocage ? Justifie avec le graphe.

Voir la correction

Pas de cycle (P1 ne demande rien à P2) : P1 finira par libérer R1, ce qui débloquera P2. Pas d'interblocage.

Niveau 3 — défi

Propose un scénario à 4 processus et 4 ressources provoquant un interblocage, dessine son graphe, puis explique comment l'éviter avec l'ordre total sur les ressources.

Bilan

Vocabulaire clé de la séance

Interblocage Deadlock Graphe d'attente Cycle Ordre total Détection

Chapitre suivant

La suite : les protocoles de routage

Encore un graphe, mais cette fois pour représenter un réseau : comment un paquet trouve-t-il sa route jusqu'à destination ?