Interblocage

Définition de l'interblocage

Dans la partie précédente, nous avons vu que l'on pouvait utiliser un verrou pour éviter des problèmes d'accès concurrents à une ressource par plusieurs threads. Dans notre cas, c'était juste une variable compteur, mais cela pourrait être l'accès en écriture à un fichier, l'accès en modification à une table de base de données, etc. Il peut donc y avoir plusieurs ressources, et c'est la source potentielle de ce que l'on appelle l'interblocage.

L'interblocage (de l'anglais deadlock) se produit, par exemple, lorsqu'un thread T1 ayant déjà acquis la ressource R1 demande l'accès à une ressource R2, pendant que le thread T2, ayant déjà acquis la ressource R2, demande l'accès à la ressource R1. Chacun des deux threads attend alors la libération de la ressource possédée par l'autre. La situation est donc bloquée.

Cela vous semble abstrait ? Un problème de théoricien de l'informatique ? Que nenni ! La mission martienne pathfinder en a donné un exemple très concret.

Pathfinder

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é.

Simulation de l'interblocage

Description de la situation

Nous allons nous même simuler un interblocage dans une situat :ion 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.

On peut imaginer un problème analogue assez simplement avec un respect strict de la priorité à droite à un croisement de deux routes, sur lesquelles arrive simultanément 4 voitures. Chacune attend que celle à sa droite démarre. La boucle n'a pas de fin là non plus. On a un interblocage «routier».

Un programme qui simule la situation

Voici le code d'un programme qui simule ce que fait notre robot :

"""
NSI Archicture, Systèmes d'exploitation
Interblocage dans un robot.
"""

# Librairie utilisées
from threading import Thread
from threading import Lock
import time
import random

# Les ressources utilisées par le robot
R1_moteurs = Lock()
R2_wifi = Lock()
R3_camera = Lock()

# Variable partagée par les 3 threads
fin = False
compteur = 0


def P1_pilotage_manuel():
    """Fonction embarquée dans le thread P1"""
    global compteur
    while fin == False:
        print("P1 : demande de R1_moteurs...")
        R1_moteurs.acquire()
        print("P1 : demande de R2_wifi...")
        R2_wifi.acquire()
        print("P1 : début travail")
        time.sleep(random.random()/100.0)
        print("P1 : fin travail")
        compteur += 1
        print(f"*** {compteur} tâche(s) terminée(s)")
        print("P1 : libération de R1_moteurs...")
        R1_moteurs.release()
        print("P1 : libération de R2_wifi...")
        R2_wifi.release()


def P2_envoi_flux_video():
    """Fonction embarquée dans le thread P2"""
    global compteur
    while fin == False:
        print("P2 : demande de R2_wifi...")
        R2_wifi.acquire()
        print("P2 : demande de R3_camera...")
        R3_camera.acquire()
        print("P2 : début travail")
        time.sleep(random.random()/100.0)
        print("P2 : fin travail")
        compteur += 1
        print(f"*** {compteur} tâche(s) terminée(s)")
        print("P2 : libération de R2_wifi...")
        R2_wifi.release()
        print("P2 : libération de R3_camera...")
        R3_camera.release()


def P3_auto_tests_materiels():
    """Fonction embarquée dans le thread P3"""
    global compteur
    while fin == False:
        print("P3 : demande de R3_camera...")
        R3_camera.acquire()
        print("P3 : demande de R1_moteurs...")
        R1_moteurs.acquire()
        print("P3 : début travail")
        time.sleep(random.random()/100.0)
        print("P3 : fin travail")
        compteur += 1
        print(f"*** {compteur} tâche(s) terminée(s)")
        print("P3 : libération de R3_camera...")
        R3_camera.release()
        print("P3 : libération de R1_moteurs...")
        R1_moteurs.release()


if __name__ == '__main__':
    # Création des threads
    t1 = Thread(target=P1_pilotage_manuel)
    t2 = Thread(target=P2_envoi_flux_video)
    t3 = Thread(target=P3_auto_tests_materiels)

    # Lancement des threads
    t1.start()
    t2.start()
    t3.start()

    # Attente de la fin du travail
    t1.join()
    t2.join()
    t3.join()

Vous pouvez télécharger ce fichier pour ne pas avoir à le recopier.

Les solutions

La gestion des threads et des verrous n'est pas une chose simple. Il n'y a pas de recette magique, mais des stratégies, des bonnes pratiques et une nécessaire réflexion. La vidéo en lien ci dessous vous propose une présentation détaillé qui reprend toutes les notions et vous parle aussi des stratégies adoptées pour résoudre le problème de l'interblocage.