Interblocage (deadlock) : cours de Terminale NSI

Tu as déjà vu un ordinateur ou un programme qui se fige sans jamais se débloquer, même en attendant longtemps ? Parfois, la cause est un simple calcul très long. Mais dans d'autres cas, le programme est dans une impasse logique : chaque partie attend une autre partie, qui attend elle-même la première. Cette impasse porte un nom : l'interblocage.

Ce chapitre s'appuie sur ce que tu as vu juste avant : un système d'exploitation gère plusieurs processus en même temps, se partage le processeur grâce à l'ordonnancement, et fait cohabiter des programmes qui utilisent les mêmes ressources (fichiers, mémoire, périphériques, verrous). Dès que des processus se partagent des ressources, une question apparaît : que se passe-t-il quand chacun garde une ressource et en réclame une autre ?

Le mot « concurrente » est important : l'interblocage n'existe que si plusieurs processus (ou plusieurs processus légers, les threads) avancent en parallèle ou en alternance et se partagent des ressources. Un programme séquentiel simple, qui exécute ses instructions les unes après les autres sans rien partager, ne peut pas se bloquer de cette façon.

Imagine deux voitures face à face sur un chemin étroit où une seule peut passer. Chaque conducteur attend que l'autre recule. Personne ne recule, donc personne n'avance. Aucun des deux n'est en panne, aucun n'est lent : ils sont simplement chacun en attente de l'autre. C'est exactement l'idée de l'interblocage, avec des processus à la place des voitures et des ressources à la place du chemin.

Un exemple classique d'interblocage se produit quand deux processus légers essaient d'acquérir deux mutex dans un ordre différent.² Prenons deux mutex, M1 et M2, et deux processus légers, P1 et P2. Voici une séquence d'opérations possible, que nous construisons pour l'étude :

Dans une telle situation, les deux processus légers sont définitivement bloqués.² Le mot « définitivement » signifie que le temps ne règle rien : tu peux attendre une seconde, une heure ou un jour, la situation reste identique.

Voici une traduction possible du scénario avec le module threading. Les pauses courtes (sleep) servent seulement à faire en sorte que les deux fils prennent leur premier verrou avant de demander le second.

import threading, time

m1 = threading.Lock()
m2 = threading.Lock()

def p1():
    with m1:
        time.sleep(0.1)
        with m2:          # P1 attend M2
            print("P1 a fini")

def p2():
    with m2:
        time.sleep(0.1)
        with m1:          # P2 attend M1
            print("P2 a fini")

t1 = threading.Thread(target=p1)
t2 = threading.Thread(target=p2)
t1.start(); t2.start()
t1.join(); t2.join()   # ne se termine jamais

Si tu exécutes ce programme, aucun des deux messages ne s'affiche et le programme ne rend jamais la main.

Un interblocage n'est pas un simple ralentissement. Les processus pris dans cet état n'en sortent jamais, ce qui en fait une situation catastrophique.² Concrètement :

• les ressources détenues par les processus bloqués ne sont jamais rendues, donc d'autres processus qui en auraient besoin risquent de se bloquer à leur tour ;
• le travail attendu (une sauvegarde, une transaction, un affichage) n'est jamais terminé ;
• le programme ne produit aucune erreur : il attend, c'est tout, ce qui complique le diagnostic.

L'interblocage ne demande pas forcément deux acteurs : un processus peut aussi s'attendre lui-même.² Imagine un fil d'exécution qui prend un verrou simple (non réentrant), puis, dans une fonction appelée plus loin, demande à nouveau ce même verrou. Le verrou est déjà détenu, par lui-même, et il ne sera libéré qu'une fois la fonction terminée. Le fil attend donc un événement qu'il est seul à pouvoir provoquer.

import threading

verrou = threading.Lock()

def sous_tache():
    with verrou:        # demande un verrou déjà pris
        print("jamais affiché")

with verrou:
    sous_tache()

Que faire quand l'interblocage est là ? Et mieux, comment l'empêcher d'arriver ? Il existe deux familles de solutions : mettre fin à un interblocage existant, ou l'éviter. Pour mettre fin à un interblocage, il faut stopper l'un des deux processus responsables.¹ Une fois ce processus arrêté, les ressources qu'il détenait sont libérées, et l'autre processus peut enfin continuer.

Pour éviter un interblocage, le système doit disposer de renseignements sur les besoins des processus avant de leur distribuer des ressources.² Le principe : à chaque demande, il vérifie si l'accorder le conduirait vers un état « non sûr », c'est-à-dire une situation d'où un interblocage pourrait naître.² Dans ce cas, il peut retarder la demande au lieu de l'accorder tout de suite.

L'algorithme du banquier est un algorithme classique qui permet d'anticiper les interblocages. Pour fonctionner, il lui faut connaître d'avance le plafond de consommation de chaque ressource.² Son nom vient d'une image : un banquier n'accorde un prêt que s'il est sûr de pouvoir encore satisfaire les besoins de ses clients ensuite. Ici, le système n'accorde une ressource que s'il reste capable de répondre aux demandes maximales annoncées des processus.

Sur l'exemple des deux mutex, on peut raisonner directement. Si P1 et P2 demandent tous deux M1 d'abord, puis M2, alors celui qui obtient M1 en premier peut ensuite demander M2 : l'autre, qui attend M1, ne détient rien et ne bloque donc personne. La boucle d'attente ne peut plus se former. Convenir d'un même ordre d'acquisition pour les verrous est donc une bonne habitude de programmation. Ce raisonnement se vérifie sur la séquence de la section précédente : l'étape 2 (P2 prend M2 avant M1) disparaît.

Il faut distinguer deux notions voisines. Un système peut se trouver dans un état non sûr sans qu'un interblocage en résulte forcément.² Les mots « sûr » et « non sûr » décrivent seulement la possibilité d'un interblocage, pas sa réalisation.²

Le phénomène dépasse les processus. Un exemple pédagogique en base de données reprend l'idée avec des élèves : deux établissements A et B, et deux élèves de terminale X et Y. L'interblocage se voit entre X et Y, qui souhaitent échanger mais ne peuvent pas le faire sans que l'un des deux refuse la seule réponse positive qu'il a reçue.¹ La structure est la même : chacun attend que l'autre renonce en premier, donc personne ne bouge.