INTRODUCTION

D’après le modèle von Neumann, on peut se représenter un ordinateur comme une machine séquentielle qui, d’après un programme, exécute des instructions les unes après les autres occupant chacune le processeur un certain temps. Dans ce modèle, aucune simultanéité n’est possible et, de ce fait, ni traitement parallèle ni concurrence. Dans la vie de tous jours, les processus parallèles sont pourtant omniprésents : chaque être vivant existe en tant qu’individu à part entière mais de nombreux processus se déroulent simultanément à l’intérieur de son corps.

Les avantages du traitement parallèle sont évidents : il permet un gain de performance énorme puisque plusieurs tâches sont résolues en même temps. De plus, la redondance et la chance de survie augmente puisque la panne d’un composant du système n’entraîne pas nécessairement la panne du système dans son ensemble.

La parallélisation des algorithmes est toutefois une tâche ardue qui, malgré des efforts de recherche considérables, n’est pas encore parvenue à maturité. Le problème essentiel est que les sous-processus partagent généralement des ressources et dépendent de l’issue d’autres processus.

LE MULTI-THREADING EST PLUS SIMPLE QU’IL N’EN A L’AIR

En Python, il est très facile d’exécuter le code d’une fonction dans son propre thread. Il suffit pour cela d’importer le module threading et de passer à start_new_thread() le nom de la fonction à exécuter en parallèle ainsi que d’éventuels paramètres qu’il faut empaqueter dans un tuple. Le thread débute alors immédiatement son exécution avec le code de la fonction mentionnée..

Notre premier programme faisant usage des threads met en œuvre deux tortues qui dessinent chacune un escalier simultanément et de manière indépendante. Il faut pour cela une fonction nommée de manière arbitraire, en l’occurrence paint(), qui peut prendre des paramètres comme la tortue qui doit réaliser l’opération ainsi qu’un fanion indiquant s’il faut effectuer le dessin vers la gauche ou vers la droite. On passe ensuite le nom de cette fonction sans les parenthèses ainsi qu’un tuple contenant les arguments (la tortue et le fanion) à la méthode thread.start_new_thread(). Et c’est parti pour notre premier programme parallèle !

from gturtle import *
import thread

def paint(t, isLeft):
    for i in range(16):
        t.forward(20)
        if isLeft:
            t.left(90)
        else:
            t.right(90)
        t.forward(20)
        if isLeft:
            t.right(90)
        else:
            t.left(90)
    
tf = TurtleFrame()
john = Turtle(tf)
john.setPos(-160, -160)
laura = Turtle(tf)
laura.setColor("red")
laura.setPenColor("red")
laura.setPos(160, -160)
thread.start_new_thread(paint, (john, False))
thread.start_new_thread(paint, (laura, True))

MEMENTO

CRÉER ET DÉMARRER DES THREADS EN TANT QU’INSTANCE D’UNE CLASSE

MEMENTO

TERMINER LES THREADS

Une fois démarré, un thread ne peut pas être terminé directement depuis une méthode extérieure à lui-même, comme par exemple depuis un autre thread. Pour que le thread se termine, il faut nécessairement que l’exécution de sa méthode run() se termine. C’est la raison pour laquelle il n’est jamais une bonne idée de mettre une boucle while infinie dans la méthode run() d’un thread. Il faut plutôt utiliser une variable globale booléenne isRunning pour contrôler l’exécution de la boucle while. Cette variable sera normalement mise à True tant que le thread doit s’exécuter mais peut également être mise sur False depuis un autre thread pour demander son arrêt.

Dans le programme suivant, les deux tortues effectuent un mouvement aléatoire jusqu’à ce que l’une des deux sorte de la surface circulaire.

from threading import Thread
from random import random
import time
from gturtle import *

class TurtleAnimator(Thread):
    def __init__(self, turtle):
        Thread.__init__(self)
        self.t = turtle

    def run(self):
        while isRunning:
            self.t.forward(50 * random())
            self.t.left(-180 + 360 * random())

tf = TurtleFrame()
john = Turtle(tf)
laura = Turtle(tf)
laura.setColor("red")
laura.setPenColor("red")
laura.setPos(-200, 0)
laura.rightCircle(200)
laura.setPos(0, 0)
thread1 = TurtleAnimator(john)
thread2 = TurtleAnimator(laura)
isRunning = True
thread1.start() 
thread2.start()

while isRunning and not tf.isDisposed():
    if laura.distance(0, 0) > 200 or john.distance(0, 0) > 200:
        isRunning = False
    time.sleep(0.001)
tf.setTitle("Limit exceeded")

MEMENTO

METTRE DES THREADS EN PAUSE

Pour ne suspendre un thread que pour un temps, on peut sauter les instructions présentes dans run() en utilisant un fanion global isPaused et reprendre leur exécution ultérieurement en mettant isPaused sur False.

from threading import Thread
from random import random 
import time
from gturtle import *

class TurtleAnimator(Thread):
    def __init__(self, turtle):
        Thread.__init__(self)
        self.t = turtle

    def run(self):
        while True:
            if isPaused:
                Turtle.sleep(10)
            else: 
                self.t.forward(100 * random())
                self.t.left(-180 + 360 * random())

tf = TurtleFrame()
john = Turtle(tf)
laura = Turtle(tf)
laura.setColor("red")
laura.setPenColor("red")
laura.setPos(-200, 0)
laura.rightCircle(200)
laura.setPos(0, 0)
thread1 = TurtleAnimator(john)
thread2 = TurtleAnimator(laura)
isPaused = False
thread1.start() 
thread2.start()

tf.setTitle("Running")
while not isPaused and not tf.isDisposed():
    if laura.distance(0, 0) > 200 or john.distance(0, 0) > 200:
        isPaused = True
        tf.setTitle("Paused")
        Turtle.sleep(2000)
        laura.home()
        john.home()
        isPaused = False
        tf.setTitle("Running")
    time.sleep(0.001)

Il est même bien plus avisé de stopper un thread avec Monitor.putSleep() et de reprendre son exécution par la suite avec Monitor.wakeUp(). .

from threading import Thread
from random import random
import time
from gturtle import *

class TurtleAnimator(Thread):
    def __init__(self, turtle):
        Thread.__init__(self)
        self.t = turtle

    def run(self):
        while True:
            if isPaused:
                Monitor.putSleep()
            self.t.forward(100 * random())
            self.t.left(-180 + 360 * random())

tf = TurtleFrame()
john = Turtle(tf)
laura = Turtle(tf)
laura.setColor("red")
laura.setPenColor("red")
laura.setPos(-200, 0)
laura.rightCircle(200)
laura.setPos(0, 0)
thread1 = TurtleAnimator(john)
thread2 = TurtleAnimator(laura)
isPaused = False
thread1.start() 
thread2.start()

tf.setTitle("Running")
while not isPaused and not tf.isDisposed():
    if laura.distance(0, 0) > 200 or john.distance(0, 0) > 200:
        isPaused = True
        tf.setTitle("Paused")
        Turtle.sleep(2000)
        laura.home()
        john.home()
        isPaused = False
        Monitor.wakeUp()
        tf.setTitle("Running")
    time.sleep(0.001)

MEMENTO

ATTENDRE LE RÉSULTAT DU TRAITEMENT D’UN THREAD

Dans ce programme, on utilise un thread ouvrier (worker thread) pour calculer la somme des nombres entiers entre 1 et 1'000'000. Le programme principal attend le résultat et affiche le temps nécessaire pour l’effectuer. Comme ce temps peut légèrement varier, on refait la mesure 10 fois de suite dans un thread ouvrier. On utilise join() pour attendre la fin de l’exécution du thread.

from threading import Thread
import time

class WorkerThread(Thread):
     def __init__(self, begin, end):
         Thread.__init__(self)
         self.begin = begin
         self.end = end
         self.total = 0

     def run(self):
         for i in range(self.begin, self.end):
             self.total += i

startTime = time.clock()
repeat 10:
    thread = WorkerThread(0, 1000000)
    thread.start()
    thread.join() 
    print(thread.total)
print("Time elapsed:", time.clock() - startTime, "s")

Comme dans la vie réelle, on peut déléguer du travail pénible à plusieurs ouvriers différents. Si l’on utilise deux threads ouvriers pour que chacun effectue la moitié du travail, il faudra attendre que les deux aient terminé pour combiner leur résultat.

from threading import Thread
import time

class WorkerThread(Thread):
     def __init__(self, begin, end):
         Thread.__init__(self)
         self.begin = begin
         self.end = end
         self.total = 0

     def run(self):
         for i in range(self.begin, self.end):
             self.total += i

startTime = time.clock()
repeat 10:
    thread1 = WorkerThread(0, 500000)
    thread2 = WorkerThread(500000, 1000000)
    thread1.start()
    thread2.start()
    thread1.join() 
    thread2.join()  
    result = thread1.total + thread2.total
    print result 
print "Time elapsed:", time.clock() - startTime, "s"

MEMENTO

SECTIONS CRITIQUES ET VERROUS

Puisque les threads s’exécutent de manière indépendante, la modification de données communes par plusieurs threads est délicate. Pour éviter des collisions non souhaitées entre les threads, on regroupe les instructions qui doivent nécessairement être exécutées sans interruption en les regroupant dans un bloc de programme appelée section critique muni de protections garantissant qu’il sera exécuté sans interruption, de manière atomique. Si un autre thread tente d’exécuter ce bloc de code, il doit attendre jusqu’à ce que le thread actuel ait terminé l’exécution de ce même bloc de code. Cette protection est implémentée dans les programmes Python à l’aide d’un verrou (lock en anglais). Un verrou est une instance de la classe Lock qui possède deux états possibles : verrouillé (locked) et déverrouillé (unlocked) ainsi que deux méthodes, acquire() et release() fonctionnant selon les règles suivantes :

On dit qu’un thread acquière le verrou avec acquire() et le libère à nouveau avec release() [plus... Dans d’autres langages de programmation, le mécanisme de verrou est
également appelé synchronisation de threads.

En lieu et place du simple verrou, on utilise parfois des verrous plus
perfectionnés tels que les sémaphores (semaphore) ou les moniteurs
(monitor) afin de garantir une synchronisation plus fine ].

Voici plus précisément comment procéder pour protéger une section critique : on commence par créer un objet global lock = Lock() qui est bien entendu dans un état initial déverrouillé. Chaque thread tente ensuite d’acquérir le verrou avec acquire() en entrant dans la section critique. En cas d’échec, si le verrou est déjà verrouillé par un autre thread, le thread demandeur est automatiquement mis en veille jusqu’à la libération du verrou. Lorsqu’un thread acquière le verrou, il traverse la section critique et libère le verrou lorsqu’il a terminé avec release() de sorte que les autres threads puissent à leur tour l’acquérir [plus... Lorsque plusieurs threads sont en attente du verrou, c’est le système d’exploitation
qui choisit le prochain thread à pouvoir l’acquérir tout en veillant à ce
que chaque thread ait l’occasion de l’acquérir afin d’éviter que certains
threads ne soient affamés (starvation)].

On peut comparer une section critique dans le code comme une ressource contenue dans une pièce munie d’une porte fermée à clé. Le verrou de la section critique agit alors comme une clé suspendue à l’entrée de la pièce nécessaire à un thread pour entrer dans la pièce. Un thread, lorsqu’il pénètre dans la pièce (section critique) prend alors la clé avec lui et referme la porte derrière lui. Tous les threads qui voudraient pénétrer dans la pièce doivent alors faire la queue pour attendre la clé. Une fois que le thread actuellement dans la pièce a terminé son travail, il ressort de la pièce et suspend la clé à son emplacement. Le premier thread qui attend devant la porte peut alors pénétrer la pièce et effectuer son travail. Si aucun thread n’attend devant la porte, la clé reste simplement suspendue jusqu’à ce qu’un prochain thread tente d’entrer dans la section critique.

Dans le programme suivant, le dessin et la suppression de carrés remplis constitue la section critique. On efface un carré en repeignant par-dessus avec la couleur d’arrière-fond blanche. Le thread principal crée un carré rouge clignotant en dessinant le carré rouge et en l’effaçant après un court laps de temps. Dans un second thread MyThread, le clavier est sans arrêt interrogé avec getKeyCode(). Si l’utilisateur presse sur la barre d’espace, le carré est déplacé à une position aléatoire.

Il est évident que la section critique doit être protégée par un verrou. Si le déplacement du carré avait lieu pendant qu’il en train d’être dessiné ou effacé, le comportement serait chaotique.

from gpanel import *
from threading import Thread, Lock
from random import randint

class MyThread(Thread):
    def run(self):
        while not isDisposed():
            if getKeyCode() == 32:
                print("----------- Lock requested by MyThread")
                lock.acquire()
                print("----------- Lock acquired by MyThread")
                move(randint(2, 8), randint(2, 8))
                delay(500)  # for demonstration purposes
                print("----------- Lock releasing by MyThread...")
                lock.release()
            else:
                delay(1)

def square():
    print("Lock requested by main")
    lock.acquire()
    print("Lock acquired by main")
    setColor("red")
    fillRectangle(2, 2)
    delay(1000)
    setColor("white")
    fillRectangle(2, 2) 
    delay(1000)
    print("Lock releasing by main...")
    lock.release()

lock = Lock()
makeGPanel(0, 10, 0, 10)

t = MyThread()
t.start()
move(5, 5)
while not isDisposed():
    square()
    delay(1) # Give up thread for a short while

MEMENTO

GUI-WORKERS

Les fonctions de rappel lancées par un composant GUI (GUI = Graphical User Interface) s’exécutent dans un thread propre au système nommé Event Dispatch Thread (EDT). Celui-ci est responsable de garantir un rendu correct de la fenêtre graphique ainsi que de ses différents composants (boutons, etc.). Du fait que le rendu s’effectue à la fin de la fonction de rappel, l’interface graphique est gelée jusqu’à ce que cette dernière se termine. Il n’est de ce fait pas possible de programmer des animations graphiques au sein des fonctions de rappel d’interface graphique. Il faut impérativement suivre la règle suivante de manière très stricte :

Les fonctions de rappel (callbacks) d’interface graphique (GUI) doivent retourner très rapidement et n’impliquer aucun traitement de longue durée (> 10 ms).

En l’occurrence, une tâche est considérée de longue durée si son exécution excède une durée de 10 ms. Il faut estimer cette durée d’exécution en tenant compte des pires conditions possibles telles qu’un processeur lent et une charge système élevée. Si une action dure trop longtemps, il faut l’exécuter dans un thread séparé appelé GUI worker en anglais.

Le programme suivant dessine une rosace lors d’un clic sur l’un des deux boutons. Le dessin est animé et prend un certain temps. Il faut de ce fait effectuer le dessin dans un thread ouvrier, ce qui ne devrait vous poser aucun problème vu vos connaissances sur les threads.

from gpanel import *
from javax.swing import *
import math
import thread

def rho(phi):
    return math.sin(n * phi)

def onButtonClick(e):
    global n
    enableGui(False)
    if e.getSource() == btn1:
        n = math.e
    elif e.getSource() == btn2:
        n = math.pi
#    drawRhodonea()    
    thread.start_new_thread(drawRhodonea, ())

def drawRhodonea():
    clear()
    phi = 0
    while phi < nbTurns * math.pi:
        r = rho(phi)
        x = r * math.cos(phi)    
        y = r * math.sin(phi)    
        if phi == 0:
          move(x, y)
        else:
          draw(x, y)
        phi += dphi
    enableGui(True)

def enableGui(enable):
    btn1.setEnabled(enable)
    btn2.setEnabled(enable)
                    
dphi = 0.01
nbTurns = 100
makeGPanel(-1.2, 1.2, -1.2, 1.2)
btn1 = JButton("Go (e)", actionListener = onButtonClick)
btn2 = JButton("Go (pi)", actionListener = onButtonClick)
addComponent(btn1)
addComponent(btn2)
validate()

MEMENTO

MATÉRIEL SUPPLÉMENTAIRE

SITUATIONS DE COMPÉTITION, INTERBLOCAGE

Les êtres humains travaillent de manière hautement parallèle mais leur raisonnement logique est essentiellement séquentiel. Il nous est de ce fait très difficile de conserver une vue d’ensemble de l’exécution de programmes multi threads. Voilà pourquoi il faut toujours utiliser les threads avec une grande précaution, aussi élégants puissent-ils paraître de prime abord.

Hormis dans les applications basées sur des données et traitements aléatoires, un programme devrait toujours retourner le même résultat (postcondition) lorsqu’on lui fournit les mêmes conditions initiales (préconditions). Ceci n’est en aucun cas garanti pour les programmes comportant plusieurs threads accédant à des données partagées, même si les sections critiques sont protégées par des verrous. Le programme suivant démontre cette affirmation : il comporte deux threads, thread1 et thread2, effectuant une addition et une multiplication de deux nombres globaux a and b. Les variables globales a et b sont protégées par les verrous lock_a et lock_b. La programme principal initialise et démarre les deux threads et attend ensuite qu’ils se terminent. La valeur finale des variables a et b est finalement affichée dans la console.

Les threads sont ici générés de manière différente en spécifiant la méthode run() en tant que paramètre nommé du constructeur de la classe Thread.

from threading import Thread, Lock
from time import sleep

def run1():
    global a, b
    print("----------- lock_a requested by thread1")
    lock_a.acquire()
    print("----------- lock_a acquired by thread1")
    a += 5
#    sleep(1)
    print("----------- lock_b requested by thread1")
    lock_b.acquire()
    print("----------- lock_b acquired by thread1")
    b += 7
    print("----------- lock_a releasing by thread1")
    lock_a.release()
    print("----------- lock_b releasing by thread1")
    lock_b.release()

def run2():
    global a, b
    print("lock_b requested by thread2")
    lock_b.acquire()
    print("lock_b acquired by thread2")
    b *= 3
#    sleep(1)
    print("lock_a requested by thread2")
    lock_a.acquire()
    print("lock_a acquired by thread2")
    a *= 2
    print("lock_b releasing by thread2")
    lock_b.release()
    print("lock_a releasing by thread2")
    lock_a.release()

a = 100
b = 200
lock_a = Lock()
lock_b = Lock()

thread1 = Thread(target = run1)
thread1.start()
thread2 = Thread(target = run2)
thread2.start()
thread1.join()
thread2.join()
print("Result: a =", a, ", b =", b)

MEMENTO

lock_a requested by thread1

lock_b requested by thread2

La situation peut d’ailleurs prendre une tournure encore plus fâcheuse et geler complètement le programme. Juste avant le blocage du programme, on peut alors observer les lignes suivantes dans la console :

----------- lock_a requested by thread1
lock_b requested by thread2
lock_b acquired by thread2
lock_a requested by thread2
----------- lock_a acquired by thread1
----------- lock_b requested by thread1

Il faut un sacré travail de détective pour comprendre ce qui s’est passé dans ce cas. Tentons tout de même le coup : apparemment, le thread1 commence l’exécution en premier et tente d’acquérir le verrou lock_a. Avant qu’il n’ait l’occasion de terminer l’exécution de cette section critique, le thread2 tente d’acquérir le verrou lock_b avec succès. Immédiatement, le thread2 tente également d’acquérir le verrour lock_a, mais en vain puisque celui-ci a déjà été acquis par le thread1. De ce fait, le thread2 est bloqué en attendant la libération du verrou par thread1 qui continue son exécution et tente d’acquérir le verrou lock_b. C’est là que les choses se gâtent car le verrou lock_b est déjà acquis par le thread2 qui est bloqué dans son exécution. Ainsi, les deux threads se bloquent mutuellement sans espoir de pouvoir libérer le verrou nécessaire à l’autre thread pour être débloqué, ce qui bloque tout le programme. On appelle cela une situation d’interblocage (deadlock en anglais). L’activation des instructions sleep(1) par suppression du commentaire permet de conduire le programme systématiquement dans cette condition. Réfléchissez à cela pour essayer de bien comprendre ce phénomène.

Comme vous pouvez le constater, un interblocage survient lorsque deux threads thread1 et thread2 dépendent de deux ressources partagées a et b et se bloquent mutuellement. Par conséquent, il peut arriver que le thread2 attende sur le verrou lock_a et que le thread1 attende sur le verrou lock_b , se bloquant mutuellement de telle sorte que les verrous n’ont aucune chance d’être libérés.

Pour éviter les situations d’interblocage, il faut scrupuleusement adhérer à la règle suivante :

Les ressources partagées devraient être si possible protégées par un seul verrou. De plus, il faut impérativement s’assurer que le verrou soit libéré.

EXPRESSIONS ATOMIQUES ET THREAD-SAFE

Si plusieurs threads sont impliqués dans un programme, on ne connait jamais, en tant que programmeur, à quel moment et à quel endroit du code va avoir lieu le basculement entre threads. Comme nous l’avons déjà constaté, cela peut conduire à des résultats inattendus et incorrects lorsque les threads travaillent avec des ressources partagées. Ceci est particulièrement vrai si plusieurs threads changent une fenêtre de sorte que, lorsqu’un thread ouvrier est généré au sein d’une fonction de rappel GUI pour exécuter un code de longue durée, il faut presque toujours s’attendre à des situations chaotiques. Dans le programme précédent, nous avons évité ce problème en désactivant les boutons durant l’exécution des fonctions de rappel. On peut s’assurer que plusieurs threads puissent s’exécuter en parallèle sans se marcher sur les pieds en prenant des précautions particulières. Un tel code est alors appelé thread-safe. Écrire du code thread-safe pour qu’il puisse être exécuté dans en environnement multi-threads sans conflit est un véritable art. [plus.. On appelle réentrance la situation qui survient lorsqu’un thread exécute une fonction et est interrompu par un autre thread qui appelle la même fonction. Une fonction thread-safe peut sans problème être appelée de manière réentrante].

Il existe peu de bibliothèques thread-safe puisqu’elles sont généralement moins performantes et qu’elles comportent un risque d’interblocage. Comme vous avez pu le constater, la bibliothèque GPanel n’est pas thread-safe alors que la bibliothèque de tortues gTurtle est thread-safe. On peut en effet déplacer plusieurs tortues dans plusieurs threads de manière quasi simultanée. Dans le programme suivant, chaque clic de souris engendre à la position du clic une nouvelle tortue pilotée par un thread séparé. Chaque tortue dessine et remplit une étoile de manière autonome.

from gturtle import *
import thread

def onMousePressed(event):
#    createStar(event)
    thread.start_new_thread(createStar, (event,))

def createStar(event):
    t = Turtle(tf)
    x = t.toTurtleX(event.getX())
    y = t.toTurtleY(event.getY())
    t.setPos(x, y)
    t.startPath()
    repeat 9:
        t.forward(100)
        t.right(160)
    t.fillPath()        
     
tf = TurtleFrame(mousePressed = onMousePressed)
tf.setTitle("Klick To Create A Working Turtle")

MEMENTO

EXERCICES