Interblocage

I. Notion d'interblocage ou deadlock

Les interblocages sont des situations assez courantes dans la vie quotidienne. Le meilleur exemple est celui du carrefour avec priorité à droite. Si 4 routes arrivent à ce carrefour et s'il y a quatre véhicules, aucun ne peut s'engager sur le rond point puisque chaque véhicule possède à sa droite un voisin.

Interblocage ou deadlock

En informatique, ce problème survient également quand des processus convoitent les mêmes ressources. Le terme interblocage est quelquefois remplacé par les expressions poétiques "verrou mortel" (en anglais deadlock). Les processus bloqués dans cet état le sont définitivement.

II. Les ressources et l'interblocage

L'utilisation de ressources se fait en trois étapes :

• sollicitation de la ressource;
• utilisation de la ressource;
• libération de la ressource.

Exemple d'interblocage

Supposons un système possédant les ressources 1 et 2, ayant les processus A et B en exécution.

Supposons aussi que les ressources ne sont pas partageables : un seul processus à la fois peut utiliser une ressource.

Une façon de provoquer un interblocage est la suivante :

• Le processus A utilise la ressource 1;
• Le processus B utilise la ressource 2;
• Le processus A demande la ressource 2, et devient à l'état bloqué.
• Le processus B demande la ressource 1, et devient à l'état bloqué.

😢 Interblocage !

Acquérir

On trouve parfois le verbe acquérir qui a une signification complexe.

Pour un processus, acquérir une ressource signifie : « demander une ressource et attendre si elle n'est pas disponible, puis la réserver (l'utiliser) »

III. Modélisation des interblocages

On modélise les interblocages à l'aide de graphes orientés conçus de la façon suivante:

• Les processus sont représentés par des cercles.
• Les ressources sont représentées par des carrés.
• Une flèche qui va d'un carré à un cercle indique que la ressource est déjà attribuée au processus (figure a).
• Une flèche d'un cercle vers un carré indique que le processus est bloqué en attente de cette ressource (figure b).
• Les interblocages sont représentés dans ces graphiques par la présence d'un circuit dans le graphe orienté (figure c).

⚠️ Attention, il faut bien tenir compte du sens des flèches ! Si dans la figure c une des flèches était inversée, nous n'aurions pas un circuit.

IV. Un exemple détaillé

Auteur : Mireille Coilhac

Cet exemple peut se rencontrer dans le cas suivant :

• P1 fait une lecture sur R1 et une écriture sur R2. Il ne veut pas que R1 risque d’être modifié avant qu’il écrive sur R2.
• Et réciproquement pour P2.

V. Exemple

Détection des interblocages

Le tableau ci-dessous résume les possessions et demandes des processus A à G.

Processus	Ressources demandées	ressources détenues
A	2	1
B	3
C	2
D	2 et 3	4
E	5	3
F	2	6
G	4	5

Le graphe correspondant est le suivant :

Question

Quels sont les processus en interblocage ?

Solution

🌵 Il y a interblocage des processus D, E et G puisqu'ils forment un cycle avec les ressources 3, 4 et 5 (figure b).

VI. Apparition et prévention des interblocages

Cette situation d'interblocage a été théorisée par l'informaticien Edward Coffman (1934-) qui a énoncé quatre conditions - appelées conditions de Coffman - menant à l'interblocage :

Résumé

• Exclusion mutuelle : Les ressources ne sont pas partageables, un seul processus à la fois peut utiliser la ressource.
• Rétention des ressources : un processus détient au moins une ressource et requiert une autre ressource détenue par un autre processus. c'est à dire que les processus qui détiennent des ressources peuvent en demander d’autres.
• Non préemption : Seul le processus détenteur d'une ressource peut la libérer. On ne peut pas forcer un processus à rendre une ressource.
• 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.

Comment éviter un interblocage ?

Il existe heureusement des stratégies pour éviter ces situations. Par exemple :

• la prévention : on oblige le processus à déclarer à l'avance la liste de toutes les ressources auxquelles il va accéder.
• l'évitement : on fait en sorte qu'à chaque étape il reste une possibilité d'attribution de ressources qui évite le deadlock.
• la détection/résolution : on laisse la situation arriver jusqu'au deadlock, puis un algorithme de résolution détermine quelle ressource libérer pour mettre fin à l'interblocage.

VII. Exercices

Exercice 1 :

Sept processus Pi sont dans la situation suivante par rapport aux ressources Ri :

• P1 a obtenu R1 et demande R2
• P2 demande R3 et n’a obtenu aucune ressource tout comme P3 qui demande R2
• P4 a obtenu R2 et R4 puis demande R3
• P5 a obtenu R3 et demande R5
• P6 a obtenu R6 et demande R2
• P7 a obtenu R5 et demande R2.

On voudrait savoir s’il y a interblocage.

1. Construire un graphe orienté où les sommets sont les processus et les ressources, et où :

• La présence de l’arc Ri⇢Pj signifie que le processus Pj a obtenu la ressource Ri
• La présence de l’arc Pj⇢Ri signifie que le processus Pj demande la ressource Ri.

2. Y-a-t-il interblocage ? si oui précisez où.

Solution

Il y a un circuit dans le graphe. Il y a donc interblocage entre P4, P5 et P7.

Exercice 2 (d'après 2021, Métropole, Candidats Libres, J2, Ex. 2) :

Les états possibles d'un processus sont : prêt, élu, terminé et bloqué.

1. Expliquer à quoi correspond l'état élu.

Solution

Un processus élu est un processus en cours d'exécution.

2. Proposer un schéma illustrant les passages entre les différents états.

Solution

3. On suppose que quatre processus C1, C2, C3 et C4 sont créés sur un ordinateur, et qu'aucun autre processus n'est lancé sur celui-ci, ni préalablement ni pendant l'exécution des quatre processus. L'ordonnanceur, pour exécuter les différents processus prêts, les place dans une structure de données de type file. Un processus prêt est enfilé et un processus élu est défilé.

Parmi les propositions suivantes, recopier celle qui décrit le fonctionnement des entrées/sorties dans une file :

• Premier entré, dernier sorti
• Premier entré, premier sorti
• Dernier entré, premier sorti

Solution

Premier entré, premier sorti.

4. On suppose que les quatre processus arrivent dans la file et y sont placés dans l'ordre C1, C2, C3 et C4 . Les temps d'exécution totaux de C1, C2, C3 et C4 sont respectivement 100 ms, 190 ms, 80 ms et 60 ms.

• Après 40 ms d'exécution, le processus C1 demande une opération d'écriture disque, opération qui dure 200 ms. Pendant cette opération d'écriture, le processus C1 passe à l'état bloqué.
• Après 20 ms d'exécution, le processus C3 demande une opération d'écriture disque, opération qui dure 10 ms. Pendant cette opération d'écriture, le processus C3 passe à l'état bloqué.

Faire une frise chronologique et y indiquer les états de tous les processus.

Solution

5. Ci-dessous deux programmes en pseudo-code sont présentés.

Verrouiller un fichier signifie que le programme demande un accès exclusif au fichier et l'obtient si le fichier est disponible.

Programme 1	Programme 2
Vérrouiller fichier_1	Vérrouiller fichier_2
Calculs sur fichier_1	Vérrouiller fichier_1
Vérrouiller fichier_2	Calculs sur fichier_1
Calculs sur fichier_1	Calculs sur fichier_2
Calculs sur fichier_2	Dévérrouiller fichier_1
Calculs sur fichier_1	Dévérrouiller fichier_2
Dévérrouiller fichier_2
Dévérrouiller fichier_1

En supposant que les processus correspondant à ces programmes s'exécutent simultanément (exécution concurrente), expliquer le problème qui peut être rencontré.

Solution

• P1 demande et obtient le fichier_1. Il verrouille le fichier_1.

• P2 demande et obtient le fichier_2 . Il verrouille le fichier_2

• P1 demande le fichier_2 mais ne peut pas l'obtenir car il est verrouillé par P2.
  👉 P1 passe à l'état bloqué.

• P2 demande le fichier_1 mais ne peut pas l'obtenir car il est verrouillé par P1.
  👉 P2 passe à l'état bloqué.

😢 On a donc interblocage

6. Proposer une modification du programme 2 permettant d'éviter ce problème.

Solution

Il suffit d'intervertir les deux premières lignes du Programme 2.

Les deux programmes doivent alors commencer simultanément par Verrouiller fichier 1, ce qui n’est pas possible (exclusion mutuelle).

Nous avons donc deux possibilités :

• Si c’est le Programme 1 qui commence, P2 sera bloqué jusqu’à la fin de P1, après « dévérouillage de fichier1 ». Ils se feront donc l’un après l’autre, pas de problème.
• Si c’est P2 qui commence, P1 est bloqué jusqu’à ce que P2 dévérouille f1. Il peut faire ses calculs sur f1, puis il est bloqué jusqu’à ce que P2 dévérouille f2. P2 a terminé, et P1 peut terminer.

Exercice 3 :

Auteur Franck Chambon d'après 2022, Polynésie, J1, Ex. 2

Un système est composé de 4 périphériques, numérotés de 0 à 3, et d'une mémoire, reliés entre eux par un bus auquel est également connecté un dispositif ordonnanceur. À l'aide d'un signal spécifique envoyé sur le bus, l'ordonnanceur sollicite à tour de rôle les périphériques pour qu'ils indiquent le type d'opération (lecture ou écriture) qu'ils souhaitent effectuer, et l'adresse mémoire concernée.

Un tour a lieu quand les 4 périphériques ont été sollicités. Au début d'un nouveau tour, on considère que toutes les adresses sont disponibles en lecture et écriture.

Si un périphérique demande l'écriture à une adresse mémoire à laquelle on n'a pas encore accédé pendant le tour, l'ordonnanceur répond "OK" et l'écriture a lieu. Si on a déjà demandé la lecture ou l'écriture à cette adresse, l'ordonnanceur répond "ATT" et l'opération n'a pas lieu.

Si un périphérique demande la lecture à une adresse à laquelle on n'a pas encore accédé en écriture pendant le tour, l'ordonnanceur répond "OK" et la lecture a lieu. Plusieurs lectures peuvent avoir donc lieu pendant le même tour à la même adresse.

Si un périphérique demande la lecture à une adresse à laquelle on a déjà accédé en écriture, l'ordonnanceur répond "ATT" et la lecture n'a pas lieu.

Ainsi, pendant un tour, une adresse peut être utilisée soit une seule fois en écriture, soit autant de fois qu'on veut en lecture, soit pas utilisée.

Si un périphérique ne peut pas effectuer une opération à une adresse, il demande la même opération à la même adresse au tour suivant.

1. Le tableau donné en annexe 1 indique, sur chaque ligne, le périphérique sélectionné, l'adresse à laquelle il souhaite accéder et l'opération à effectuer sur cette adresse. Compléter dans la dernière colonne de cette annexe, à rendre avec la copie, la réponse donnée par l'ordonnanceur pour chaque opération.

Annexe 1

N° périphérique	Adresse	Opération	Réponse de l'ordonnanceur
0	10	écriture	"OK"
1	11	lecture	"OK"
2	10	lecture	"ATT"
3	10	écriture	"ATT"
0	12	lecture
1	10	lecture
2	10	lecture
3	10	écriture

Réponse

N° périphérique	Adresse	Opération	Réponse de l'ordonnanceur
0	10	écriture	"OK"
1	11	lecture	"OK"
2	10	lecture	"ATT"
3	10	écriture	"ATT"
0	12	lecture	"OK"
1	10	lecture	"OK"
2	10	lecture	"OK"
3	10	écriture	"ATT"

Il s'agit d'un nouveau tour, les lectures sont possibles, la première écriture ne l'est pas, on a déjà accédé en lecture pendant le tour à l'adresse demandée.

On suppose dans toute la suite que :

• le périphérique 0 écrit systématiquement à l'adresse 10 ;
• le périphérique 1 lit systématiquement à l'adresse 10 ;
• le périphérique 2 écrit alternativement aux adresses 11 et 12 ;
• le périphérique 3 lit alternativement aux adresses 11 et 12 ;

Pour les périphériques 2 et 3, le changement d'adresse n'est effectif que lorsque l'opération est réalisée.

2. On suppose que les périphériques sont sélectionnés à chaque tour dans l'ordre 0 ; 1 ; 2 ; 3. Expliquer ce qu'il se passe pour le périphérique 1.

Réponse

• À chaque début de tour, le périphérique 0 demande à écrire à l'adresse 10 ; c'est accepté.
• Juste après, le périphérique 1 demande à lire à l'adresse 10 ; c'est refusé.

Le périphérique 1 ne pourra jamais lire l'adresse 10.

Les périphériques sont sollicités de la manière suivante lors de quatre tours successifs :

• au premier tour, ils sont sollicités dans l'ordre 0 ; 1 ; 2 ; 3 ;
• au deuxième tour, dans l'ordre 1 ; 2 ; 3 ; 0 ;
• au troisième tour, 2 ; 3 ; 0 ; 1 ;
• puis 3 ; 0 ; 1 ; 2 au dernier tour.
• Et on recommence...

3.a. Préciser pour chacun de ces tours si le périphérique 0 peut écrire et si le périphérique 1 peut lire.

Réponse

• Tour 1 : 0 ; 1 ; 2 ; 3
  • 0 peut écrire, puis
  • 1 ne peut pas lire
• Tour 2 : 1 ; 2 ; 3 ; 0
  • 1 peut lire, puis
  • 0 ne peut pas écrire
• Tour 3 : 2 ; 3 ; 0 ; 1
  • 0 peut écrire, puis
  • 1 ne peut pas lire
• Tour 4 : 3 ; 0 ; 1 ; 2
  • 0 peut écrire, puis
  • 1 ne peut pas lire

3.b. En déduire la proportion des valeurs écrites par le périphérique 0 qui sont effectivement lues par le périphérique 1.

Réponse

• Au tour 1, la valeur écrite par le périphérique 0 sera lue par le périphérique 1 au tour suivant.
• Au tour 2, rien n'est écrit par le périphérique 0.
• Au tour 3, la valeur écrite par le périphérique 0 ne sera jamais lue par le périphérique 1 ; en effet, une autre écriture intervient avant la prochaine lecture.
• Au tour 4, la valeur écrite par le périphérique 0 ne sera jamais lue par le périphérique 1 ; en effet, une autre écriture intervient avant la prochaine lecture.

Ainsi, une seule valeur sur trois sera effectivement lue. La proportion est \(\frac13\).

On change la méthode d'ordonnancement : on détermine l'ordre des périphériques au cours d'un tour à l'aide de deux listes d'attente ATT_L et ATT_E établies au tour précédent.

Au cours d'un tour, on place dans la liste ATT_L toutes les opérations de lecture mises en attente, et dans la liste d'attente ATT_E toutes les opérations d'écriture mises en attente.

Au début du tour suivant, on établit l'ordre d'interrogation des périphériques en procédant ainsi :

• on interroge ceux présents dans la liste ATT_L, par ordre croissant d'adresse,
• on interroge ensuite ceux présents dans la liste ATT_E, par ordre croissant d'adresse,
• puis on interroge les périphériques restants, par ordre croissant d'adresse.

4. Compléter et rendre avec la copie le tableau fourni en annexe 2, en utilisant l'ordonnancement décrit ci-dessus, sur 3 tours.

Annexe 2

Tour	N° périphérique	Adresse	Opération	Réponse ordonnanceur	ATT_L	ATT_E
1	0	10	écriture	"OK"	vide	vide
1	1	10	lecture	"ATT"	(1, 10)	vide
1	2	11	écriture
1	3	11	lecture
2	1	10	lecture			vide
2
2
2
3	0	10	écriture		vide	vide
3	1	10	lecture			vide
3	2	11	écriture	"OK"	(1, 10)	vide
3	3	12	lecture

Réponse

Tour	N° périphérique	Adresse	Opération	Réponse ordonnanceur	ATT_L	ATT_E
1	0	10	écriture	"OK"	vide	vide
1	1	10	lecture	"ATT"	(1, 10)	vide
1	2	11	écriture	"OK"	(1, 10)	vide
1	3	11	lecture	"ATT"	(1, 10), (3, 11)	vide
2	1	10	lecture	"OK"	(3, 11)	vide
2	3	11	lecture	"OK"	vide	vide
2	0	10	écriture	"ATT"	vide	(0, 10)
2	2	12	écriture	"OK"	vide	(0, 10)
3	0	10	écriture	"OK"	vide	vide
3	1	10	lecture	"ATT"	(1, 10)	vide
3	2	11	écriture	"OK"	(1, 10)	vide
3	3	12	lecture	"OK"	(1, 10)	vide

Les colonnes e0 et e1 du tableau suivant recensent les deux chiffres de l'écriture binaire de l'entier n de la première colonne.

nombre n	écriture binaire de n sur deux bits	e1	e0
0	00	0	0
1	01	0	1
2	10	1	0
3	11	1	1

L'ordonnanceur attribue à deux signaux sur le bus de données les valeurs de e0 et e1 associées au numéro du circuit qu'il veut sélectionner. On souhaite construire à l'aide des portes ET, OU et NON un circuit pour chaque périphérique.
Chacun des quatre circuits à construire prend en entrée deux signaux e0 et e1, le signal de sortie s valant 1 uniquement lorsque les niveaux de e0 et e1 correspondent aux bits de l'écriture en binaire du numéro du périphérique correspondant.

Par exemple, le circuit ci-dessous réalise la sélection du périphérique 3. En effet, le signal s vaut 1 si et seulement si e0 et e1 valent tous les deux 1.

flowchart LR
    e0---ET(ET)
    e1---ET
    ET---s
    style e0 stroke-width:0px,opacity:0
    style e1 stroke-width:0px,opacity:0
    style s stroke-width:0px,opacity:0

5.a. Recopier sur la copie et indiquer dans le circuit ci-dessous les entrées e0 et e1 de façon que ce circuit sélectionne le périphérique 1.

flowchart LR
    ea( )---NON(NON)---ET(ET)
    eb( )----ET
    ET---s
    style ea stroke-width:0px,opacity:0
    style eb stroke-width:0px,opacity:0
    style s stroke-width:0px,opacity:0

Réponse

flowchart LR
    ea(e1)---NON(NON)---ET(ET)
    eb(e0)----ET
    ET---s
    style ea stroke-width:0px,opacity:0
    style eb stroke-width:0px,opacity:0
    style s stroke-width:0px,opacity:0

5.b. Dessiner un circuit constitué d'une porte ET et d'une porte NON, qui sélectionne le périphérique 2.

Réponse

flowchart LR
    ea(e1)----ET(ET)
    eb(e0)---NON(NON)---ET
    ET---s
    style ea stroke-width:0px,opacity:0
    style eb stroke-width:0px,opacity:0
    style s stroke-width:0px,opacity:0

5.c. Dessiner un circuit permettant de sélectionner le périphérique 0.

Réponse

flowchart LR
    ea(e0)---NON1(NON)---ET(ET)
    eb(e1)---NON2(NON)---ET
    ET---s
    style ea stroke-width:0px,opacity:0
    style eb stroke-width:0px,opacity:0
    style s stroke-width:0px,opacity:0

Exercice 4 :

D'après 2024, Amérique du Nord, J1, Exercice 1

Nous étudions quatre processus A, B, C et D qui utilisent des ressources suivantes :

• un fichier commun aux processus ;
• le clavier de l’ordinateur ;
• le processeur graphique (GPU) ;
• le port 25000 de la connexion Internet.

Voici le détail de ce que fait chaque processus :

A	B	C	D
acquérir le GPU	acquérir le clavier	acquérir le port	acquérir le fichier
faire des calculs	acquérir le fichier	faire des calculs	faire des calculs
libérer le GPU	libérer le clavier	libérer le port	acquérir le clavier
	libérer le fichier	libérer le port	libérer le clavier
			libérer le fichier

on a le chronogramme suivant :

Montrer que l’ordre d’exécution donné aboutit à une situation d’interblocage.

Réponse

• Le processus D demande et obtient la ressource fichier qui était libre.

• Le processus B demande et obtient la ressource clavier qui était libre.

• Le processus B demande la ressource fichier qui n'est pas disponible car détenue par le processus D. Il passe à l'état bloqué.

• Le processus D demande la ressource clavier qui n'est pas disponible car détenue par le processus B. Il passe à l'état bloqué.

Les deux procesus B et D sont bloqués, on est en situation d'interblocage.

graph LR
A[Fichier] --> D((D))
D --> C[Clavier]
C --> B((B))
B --> A

VIII. L'interblocage dans la mission Mars Pathfinder

1. La situation

En 1997, la mission Mars Pathfinder rencontre un problème alors que le robot est déjà sur Mars. Après un certain temps, des données sont systématiquement perdues. Les ingénieurs découvrent alors un bug lié à la synchronisation de plusieurs tâches. Les éléments incriminés étaient les suivants :

• une mémoire partagée, qui était protégée par un mutex (un mutex est un système de verrou du noyau)
• une gestion de bus sur la mémoire partagée, qui avait une priorité haute
• une écriture en mémoire partagée (récupération de données), qui avait la priorité la plus basse
• une troisième routine de communication, avec une priorité moyenne, qui ne touchait pas à la mémoire partagée

Il arrivait parfois que l'écriture (priorité faible) s'approprie le mutex. La gestion du bus (priorité haute) attendait ce mutex. La commutation de tâches laissait alors la routine de communication (priorité moyenne) s'exécuter. Or pendant ce temps, le mutex restait bloqué puisque les ressources étaient allouées à la routine de priorité basse. La gestion de bus ne pouvait donc plus s'exécuter et après un certain temps d'attente (une protection insérée par les ingénieurs via un système dit de chien de garde), le système effectuait un redémarrage. Un tel problème est connu sous le nom d'inversion de priorité.

Le problème n'était pas critique et le code fut corrigé à distance. Toutefois dans d'autres situations, les conséquences auraient pu être catastrophiques. On a ensuite constaté le fait que le problème était déjà survenu lors des essais sans avoir été corrigé.

2. Simulation de l'interblocage

Nous allons nous même simuler un interblocage dans une situation qui serait assez similaire à celle de la liaison martienne.

On va considérer un robot qui a trois ressources :

• Des moteurs qui lui permettent de se déplacer
• Une liaison wifi qui lui permet de communiquer
• Une caméra qui filme son environnement

Ce robot a trois processus que l'on notera P1, P2 et P3 :

• P1 est le pilotage manuel qui reçoit les ordres par le wifi et opère les moteurs
• P2 envoie le flux vidéo via la liaison wifi
• P3 est le processus qui fait un autotest matériel, hors liaison wifi

Le robot effectue les 3 taches en parallèle. Cela peut se résumer dans le tableau suivant

P1 : pilotage manuel	P2 : envoi de flux vidéo	P3 : auto-test matériel
Demande R1 (moteurs)	Demande R2 (wifi)	Demande R3 (camera)
Demande R2 (wifi)	Demande R3 (camera)	demande R1 (moteurs)
Libère R1 (moteurs)	Libère R2 (wifi)	Libère R3 (Caméra)
Libère R2(wifi)	Libère R3 (caméra)	Libère R1 (moteurs)

Cette séquence d'instruction peut se dérouler parfaitement bien, mais on peut arriver à une situation d'interblocage par un cycle.

• P1 demande la ressource R1, disponible, et la bloque
• P2 demande la ressource R2, disponible, et la bloque
• P3 demande la ressouce R3, disponible et la bloque
• étape suivante, P1 demande R2 mais doit attendre que P2 la libère.
• P2 demande R3, qui est bloquée par P3
• Et P3 demande R1 qui est bloqué par P1

La boucle est bouclée. On arrive à une situation correspondant à la figure ci dessous, ou chaque processus a bloqué la ressource associée par un trait plein et attend la ressource à laquelle il est relié par des pointillés. On est bloqué dans une boucle infernale.

Source : http://lycee.educinfo.org/index.php?page=interblocage&activite=processus

Crédits

Auteurs Mireille Coilhac, Valérie Mousseaux, Jean-Louis Thirot , sur la base du travail de :

• Olivier Lécluse
• monlycéenumerique.fr
• courstechinfo.be