Interblocage : exercices corrigés de Terminale NSI

On exécute la première instruction de $P_1$ : il verrouille $M_1$.

On passe la main à $P_2$ : il verrouille $M_2$ (libre, donc il l'obtient).

$P_1$ reprend et demande $M_2$. Ce mutex est détenu par $P_2$ : $P_1$ attend.

$P_2$ reprend et demande $M_1$. Ce mutex est détenu par $P_1$ : $P_2$ attend.

Bilan : $P_1$ détient $M_1$ et attend $M_2$ ; $P_2$ détient $M_2$ et attend $M_1$.

Aucun des deux ne peut déverrouiller ce qu'il détient, puisque ces déverrouillages se trouvent après la demande qui le bloque. Personne ne libère rien : l'attente est circulaire et définitive.

Affirmation a : fausse. Les processus bloqués dans un interblocage le sont définitivement. ²

Affirmation b : vraie. Un processus peut aussi s'attendre lui-même, par exemple en redemandant une ressource qu'il détient déjà et qui ne peut pas être prise deux fois. ²

Affirmation c : vraie. La résolution passe par l'arrêt d'un des processus fautifs. ¹

Affirmation d : vraie. Deadlock est le terme anglais ; on parle aussi d'étreinte fatale. ²

Les processus sont X et Y. La ressource attendue par chacun est l'accord de l'autre.

X attend l'accord de Y pour donner le sien ; Y attend l'accord de X pour donner le sien.

On a donc le cycle : X attend Y, Y attend X. Aucun des deux ne bougera, c'est un interblocage.

Règle possible : on décide à l'avance que X (par exemple l'élève de plus petit numéro) donne son accord en premier. Il n'attend alors plus personne, Y reçoit l'accord et peut répondre.

Autre issue : un tiers impose la décision en retirant l'un des deux de la boucle d'attente, ce qui revient à arrêter l'un des protagonistes. ¹

On choisit les 2 positions de $a_1, a_2$ parmi 4 : $\binom{4}{2}=6$ entrelacements.

On les énumère : $a_1a_2b_1b_2$, $a_1b_1a_2b_2$, $a_1b_1b_2a_2$, $b_1b_2a_1a_2$, $b_1a_1a_2b_2$, $b_1a_1b_2a_2$.

Dans $a_1a_2b_1b_2$ : $P_1$ obtient les deux mutex, termine puis $P_2$ passe. Pas d'interblocage. Même chose pour $b_1b_2a_1a_2$.

Dans les quatre autres, $a_1$ et $b_1$ se produisent avant $a_2$ et $b_2$ : $P_1$ détient $M_1$, $P_2$ détient $M_2$, puis chacun demande le mutex de l'autre. Interblocage.

Il y a donc $6-2=4$ entrelacements menant à un interblocage, soit 4 sur 6.

Les deux processus veulent d'abord $M_1$. Un seul des deux l'obtient, disons $P_1$.

$P_2$ attend alors $M_1$ sans rien détenir.

$P_1$ demande $M_2$ : il est libre puisque $P_2$ n'a rien pris. $P_1$ l'obtient, travaille, puis libère $M_2$ et $M_1$.

$P_2$ peut alors obtenir $M_1$ puis $M_2$. Le raisonnement est le même si $P_2$ passe en premier.

Un cycle supposerait $P_2$ détenant un mutex que $P_1$ attend. Ici, celui qui attend ne détient rien, donc le cycle n'existe pas.

Au second verrouillage, $M$ est déjà détenu par $P$ lui-même. $P$ se met en attente de la libération de $M$.

Seul $P$ pourrait libérer $M$, mais $P$ est bloqué en attendant : la libération n'aura jamais lieu.

Il s'agit bien d'un interblocage : un processus peut aussi s'attendre lui-même. ²

Correction : ne pas verrouiller deux fois, par exemple en déverrouillant $M$ avant l'appel de la fonction, ou en restructurant le code pour que seule une fonction prenne le mutex.

Arrêter $P_2$ libère les ressources qu'il détenait, donc $F_2$ devient disponible.

$P_1$ peut obtenir $F_2$, poursuivre son travail puis se terminer en libérant $F_1$ : il n'est plus bloqué.

Le cycle d'attente est rompu, car un des deux maillons a disparu. Arrêter l'un des deux processus fautifs est bien l'une des façons de mettre fin à un interblocage. ¹

Inconvénient : le travail de $P_2$ est perdu ou interrompu, il faudra le relancer, et il risque de retomber dans le même blocage si le code n'a pas changé.

Exemplaires libres : $10-(3+2+2)=3$.

Besoins restants : $P_1$ : $9-3=6$ ; $P_2$ : $4-2=2$ ; $P_3$ : $7-2=5$.

Seul $P_2$ (besoin 2 ≤ 3 libres) peut aller au bout tout de suite. Il prend 2 exemplaires (il en reste 1 de libre), termine, puis rend ses 4 exemplaires : $3-2+4=5$ libres.

Ensuite $P_3$ (besoin 5 ≤ 5) peut finir : il prend 5, termine et rend $2+5=7$ exemplaires ; il y en a donc 7 de libres.

Enfin $P_1$ (besoin 6 ≤ 7) finit à son tour. L'ordre $P_2$, $P_3$, $P_1$ permet à tous de se terminer.

Réponse à la question 4 : $10-(3+2+2)-2+4=5$ exemplaires libres.

Après l'attribution de $A$, $Q$ avance et libère $B$. Aucune attente circulaire ne s'installe : il n'y a pas d'interblocage.

L'affirmation de l'élève est fausse. Un état non sûr ne conduit pas forcément à un interblocage : la notion indique seulement une possibilité d'interblocage. ²

Dans notre cas, c'est précisément la libération de $B$ qui évite l'attente circulaire, de sorte que l'état est non sûr sans que le système soit bloqué. ²

Intérêt de la prudence : à chaque allocation, le système examine si elle l'amènerait vers un état non sûr. ² S'il l'évite, il n'a pas à parier sur le comportement futur des processus.

Limite : cette prudence nécessite de connaître les demandes à l'avance, ce qui est impossible pour beaucoup de systèmes ; l'évitement des interblocages est alors souvent irréalisable. ²