pdf

Interblocage #

Il arrive fréquement que des processus se bloquent l’un l’autre. Sans intervention extérieure (de l’utilisateur ou de l’OS) cette situation est insoluble. C’est l’interblocage.

foot

L’arbitre vient séparer les joueurs qui pourraient rester indéfiniment ainsi…

Partage des ressources #

Nous avons dits précédemment que des processus peuvent avoir besoin de la même ressource.

Dans de nombreuses situations, deux processus (ou davantage) peuvent souhaiter accéder à la même donnée (sur le disque dur ou autre) :

• Les deux processus ont uniquement besoin de lire la donnée : celle-ci est alors partagée, sans problème complexe.
• Les deux processus ont besoin de la donnée de manière exclusive, pour la modifier, par exemple.
• Les deux processus ont besoin de communiquer entre eux : l’un doit attendre un résultat de l’autre.

Exemple 1

Deux processus P1 et P2 ont tous les deux besoin de la même donnée D pour la modifier, c’est-à-dire de manière exclusive. Le premier à y accéder est P1, D lui est alloué par le système d’exploitation. Lorsque P2 souhaite accéder à D, la ressource n’est pas disponible : P2 est alors bloqué jusqu’à la fin de l’utilisation de D par P1.

Représentation graphique #

• P1 et P2 sont les processus,

• R1 est la ressource

• Une flêche de R1 à P1 signifie que P1 a acquis la ressource R1

• Une flêche de P2 à R1 signifie que P2 a demandé la ressource R1.

Comprenez bien :

• P1 est prêt ou est exécuté. Il n’est pas bloqué
• P2 est bloqué jusqu’à la libération de la ressource R1 par P1.

Dans cette situation, P2 attend… mais P1 va bien s’arrêter un jour et lui permettre d’avancer.

Aucun blocage.

Exemple 2

Deux processus P1 et P2 ont tous deux les besoin de deux ressources, R1 et R2.
Chaque processus bloque une donnée et doit attendre d’avoir accès à la seconde pour se terminer et les libérer.

Si la chronologie est la suivante :

• P1 demande R1 et l’aquiert
• P2 demande R2 et l’aquiert
• P1 demande R2 et l’attend
• P2 demande R1 et l’attend

Alors aucun des deux processus ne pourra avancer. C’est l’interblocage. Rien ne pourra avancer sans une intervention extérieure.

Face à cette problématique la plupart des systèmes d’exploitation ont choisir de ne pas essayer d’éviter les interblocages mais de les détecter s’ils surviennent et de les solutionner.

Détecter une situation d’interblocage #

Afin de résoudre conceptuellement ce problème on peut utiliser un graphe orienté.

• On sépare les processus et les ressources : ce sont les noeuds du graphe.
• Lorsqu’un processus attend une ressource, un arc est tracé partant de ce processus vers la ressource,
• Lorsqu’un processus acquiert une ressource, un arc est tracé partant de la ressource vers le processus. On efface l’arc dans l’autre sens s’il existe.

L’interblocage se produit lorsqu’il existe un cycle dans le graphe

Ce graphe présente un cycle et les processus sont bloqués.

Ce graphe ne présente pas de cycle, il n’y a pas d’interblocage.

Pas non plus de cycle et donc pas d’interblocage.

Conclusion sur l’interblocage #

L’interblocage est une situation qui conduit à la paralysie de plusieurs processus.

L’éviter totalement est presque impossible. Pour la résoudre lorsqu’elle se produit il faut une intervention extérieure (utilisateur, OS).

vs

Pour la repérer, on peut dessiner un graphe orienté. Présence d’un cycle = interblocage.

from multiprocessing import Process
from random import random
from time import sleep


def hello():
    for _ in range(5):
        print("hello")
        sleep(random())


def bonjour():
    for _ in range(5):
        print("bonjour")
        sleep(random())


p1 = Process(target=hello)
p2 = Process(target=bonjour)

p1.start()
p2.start()

p1.join()
p2.join()

hello
bonjour
hello
bonjour
hello
hello
bonjour
bonjour
bonjour
hello

hello
bonjour
bonjour
bonjour
hello
hello
hello
hello
bonjour
bonjour

import threading


def increment_global():
    global x
    x += 1


def task():
    for _ in range(500000):
        increment_global()


def race(nb: int):
    global x
    x = 0
    t1 = threading.Thread(target=task)
    t2 = threading.Thread(target=task)

    t1.start()
    t2.start()

    t1.join()
    t2.join()

    print(f"after race number {nb}, x = {x}")


def main():
    for i in range(5):
        race(i)


if __name__ == "__main__":
    main()

$ python competition.py
after race number 0, x = 712104
after race number 1, x = 850346
after race number 2, x = 893592
after race number 3, x = 813423
after race number 4, x = 761881