cours1 min de lecture

L'interblocage (deadlock)

Quand plusieurs processus s'attendent mutuellement et qu'aucun ne peut plus avancer — les quatre conditions de Coffman, l'exemple des philosophes, et comment l'éviter.

programme

Introduction

L'ordonnancement réussit à donner l'illusion que des processus indépendants s'exécutent en parallèle. Mais certains de ces processus ne sont pas indépendants : ils se partagent des ressources — un fichier, une imprimante, une zone de mémoire, une base de données. Quand deux processus ont chacun besoin de ressources que l'autre possède déjà, ils peuvent se retrouver à s'attendre mutuellement pour toujours. Image quotidienne : deux voitures qui se présentent face à face sur un pont à une seule voie et qui se klaxonnent mutuellement, chacune refusant de reculer. Aucune ne passe, le pont reste bloqué. Cet état pathologique s'appelle un interblocage (en anglais deadlock). C'est l'un des risques explicitement mentionnés par l'item .

Un exemple minimal — deux fichiers verrouillés

Imaginez deux processus $P_1$ et $P_2$ qui doivent chacun modifier deux fichiers A et B. Pour éviter qu'ils ne se marchent dessus, chacun verrouille le fichier avant de l'écrire.

Temps	$P_1$	$P_2$
$t_1$	verrouille `A`	verrouille `B`
$t_2$	demande `B` (attend)	demande `A` (attend)
$t_3$	bloqué — $P_2$ tient `B`	bloqué — $P_1$ tient `A`
$t_4$	toujours bloqué	toujours bloqué

Chaque processus possède une ressource et attend l'autre — qui ne se libérera jamais. Aucun ne progresse. Le système ne plante pas, mais ces deux processus sont gelés.

Un interblocage n'est pas un bug aléatoire : il survient quand l'ordre d'acquisition des ressources est mal pensé. Le code peut être correct dans 99 % des exécutions et bloquer dans 1 %.

Les quatre conditions de Coffman

En 1971, Edward Coffman a énoncé quatre conditions nécessaires pour qu'un interblocage soit possible. Toutes les quatre doivent être réunies — il suffit d'en briser une pour que l'interblocage devienne impossible.

Les 4 conditions de Coffman

Exclusion mutuelle — chaque ressource ne peut être détenue que par un seul processus à la fois.
Possession et attente — un processus garde ses ressources tout en en demandant de nouvelles.
Non-préemption — une ressource ne peut pas être retirée de force à un processus ; il doit la libérer volontairement.
Attente circulaire — il existe un cycle de processus $P_1 \to P_2 \to \dots \to P_n \to P_1$ , chacun attendant une ressource détenue par le suivant.

Sur notre exemple à deux fichiers, les quatre conditions sont vérifiées : le verrou est exclusif, $P_1$ garde A en attendant B, on ne lui retire pas A de force, et l'attente est circulaire ( $P_1$ attend $P_2$ , $P_2$ attend $P_1$ ).

Pour qu'un interblocage soit possible, il faut que ces quatre conditions soient…

L'exemple canonique — le dîner des philosophes

Cinq philosophes sont attablés autour d'une table ronde. Devant chacun se trouve une assiette de spaghettis, et entre deux assiettes voisines, une seule fourchette — soit cinq fourchettes pour cinq philosophes. Pour manger, un philosophe a besoin de deux fourchettes (celle de gauche et celle de droite). Quand il a fini, il les repose.

Si tous les philosophes prennent simultanément la fourchette à leur gauche, ils attendent ensuite la fourchette à leur droite — qui est déjà dans la main du voisin. Personne ne peut manger. C'est un interblocage : l'attente circulaire est manifeste.

Le dîner des philosophes

Comment éviter l'interblocage ?

Pour chaque condition de Coffman, une stratégie existe :

Condition à briser	Stratégie possible
Exclusion mutuelle	Utiliser des ressources partageables (lecture seule).
Possession et attente	Exiger qu'un processus demande toutes ses ressources d'un coup, ou aucune.
Non-préemption	Permettre de retirer une ressource (rollback de transaction en BDD).
Attente circulaire	Imposer un ordre total d'acquisition (toujours verrouiller `A` avant `B`).

La méthode la plus utilisée en pratique : imposer un ordre d'acquisition. Sur l'exemple des deux fichiers, si on convient que tout le monde verrouille A avant B, l'attente circulaire devient impossible.

Sur le dîner des philosophes, une solution élégante : imposer aux philosophes de numéro impair de prendre d'abord la fourchette de gauche, et aux philosophes de numéro pair de prendre d'abord celle de droite. L'ordre d'acquisition est ainsi globalement cohérent, et la circularité disparaît.

Pour briser l'attente circulaire entre verrous, la méthode la plus simple est…

Activité débranchée

Activité débranchée suggérée par le BO . Distribuez à 4 élèves deux jetons « ressource A » et deux jetons « ressource B » (un de chaque), avec pour consigne d'écrire une « tâche » qui nécessite l'usage simultané d'un A et d'un B. Faites jouer la scène : chacun prend un jeton, puis on observe qui attend qui. L'interblocage apparaît visuellement, et la discussion sur les solutions devient concrète.

Pour aller plus loin

Au-delà de la prévention (briser une condition), il existe aussi la détection (laisser l'interblocage se produire, le détecter, et résoudre par rollback) et l'évitement (refuser une demande qui mènerait à un état dangereux — algorithme du banquier). Ces techniques sont au cœur des systèmes de bases de données et des systèmes d'exploitation modernes.