Programmation parallèle

I. Présentation

Pour les programmes nécessitant beaucoup de calculs (simulation par exemple), il est rapidement devenu nécessaire de lancer plusieurs tâches en même temps. Pour cela, il a fallu développer des machines faites de nombreux processeurs. Au départ, cela ne concernait que les super-calculateurs, mais avec le développement des processeurs multi-core, il est devenu possible d'exécuter plusieurs tâches en même temps sur un ordinateur personnel.

Cependant, l'intérêt d'effectuer plusieurs tâche en même temps n'est pas lié qu'à cela. Par exemple, l'humain étant particulièrement long à taper sur un clavier, un logiciel de traitement de texte passe 99% de temps à ne rien faire. Il est donc intéressant, pendant ses longue périodes d'inactivité, de laisser d'autres logiciels s'exécuter. Mais si l'un de ces logiciels est un programme de calcul intensif, le système ne va pas attendre la fin de son exécution avant de repasser la main au traitement de texte. Le système va ainsi partager le temps du micro-processeurs entre les différents logiciels, ou plus exactement entre les différents processus.

Utiliser plusieurs processus peut également servir au sein d'une même application. Par exemple, si votre application graphique doit lancer un calcul qui prend plusieurs secondes, il n'est pas concevable, que cela bloque l'application. Aussi, on peut être amené, au sein d'une même application, à créer plusieurs threads, qui sont des sortes de processus légers.

En ce qui concerne l'exécutiond de tâches en parallèle, certains langages, comme ADA, comportent des instructions spéciales pour décrire ce genre de traitement, mais ces langages sont peu nombreux. Dans la plupart des langages, c'est notamment le cas de Python, il existe des bibliothèques qui permettent de créer et lancer des threads.

II. Un premier exemple de programme multi-thread en Python

Voici un programme Python constitué de 3 threads : le thread principal, et 2 threads, créés grâce au constructeur Thread(), qui prend en paramètre la fonction qui devra être exécutée par le thread en question, et lancés par l'appel à la méthode start() :

from threading import Thread
from time import sleep
from random import randint

def traitementA():
    i = 0
    while i < 100:
        print("A"+str(i))
        sleep(randint(1,10)/10)
        i += 1

def traitementB():
    i = 0
    while i < 100:
        print("B"+str(i))
        sleep(randint(1,10)/10)
        i += 1

t1 = Thread(target=traitementA)
t2 = Thread(target=traitementB)

t1.start()
t2.start()

for i in range(20):
    print("Thread principal")
    sleep(1)
print("Thread principal terminé")

À l'exécution, on peut s'apercevoir que les exécutions des 3 threads sont entrelacées, et que l'arrêt du thread principal n'empêche pas les autres threads de continuer à s'exécuter.

III. Le problème des données partagées

Il arrive fréquemment que des threads différents, fonctionnant simultanément, doivent partager des données. C'est d'ailleurs le moyen privilégié pour eux d'échanger de l'informaation. Le problème est alors que des comportements inattendus peuvent se produire. Prenon le cas du programme suivant, fort peu différent du précédent :

from threading import Thread
from time import sleep
from random import randint

c = 0
def traitementA():
    global c
    i = 0
    while i < 1000000:
        c = 1
        #sleep(randint(1,10)/10)
        if c != 1:
            print("*********** PROBLEME POUR A **************")
        i += 1

def traitementB():
    global c
    i = 0
    while i < 1000000:
        c = 2
        #sleep(randint(1,10)/10)
        if c != 2:
            print("*********** PROBLEME POUR B **************")
        i += 1

t1 = Thread(target=traitementA)
t2 = Thread(target=traitementB)

t1.start()
t2.start()

Dans cet exemple, si on regarde la fonction exécutée par le premier thread, à savoir traitementA, il semble évident que le texte "PROBLEME POUR A" ne devrait jamais s'afficher. Pourtant à l'exécution, on observe quelques affichage de ce message (si cela n'arrive pas, essayez plusieurs exécutions. Si cel n'arrive toujours pas, décommentez les deux lignes avec un caleçon sleep et ré-essayez.

En effet, entre le moment où le premier thread mais la variable c à 1 et le moment où il effectue le test c == 1, il est tout à fait possible que le deuxième thread ait mis cette même variable c à 2.

Bien sûr, le problème précédent fait un peu "cas d'école". Mais observons maintenant le programme suivant, qui est une version threadé du problème producteur-consommateur que vous verrez dans le chapitre sur les files : un producteur produit des ressources dans une file d'attente, et deux consommateurs consomment ces ressources. Bien sûr, les 2 consommateurs vérifient qu'il y a bien au moins une ressource de disponible avant de se servir :

from random import randint
from time import sleep
from threading import Thread

class File:
    def __init__(self):
        self.file = []

    def ajouter(self, e):
        sleep(randint(0,50)/1000)
        self.file.append(e)

    def tete(self):
        return self.file[0]

    def prelever(self):
        sleep(randint(0,50)/1000)
        s = self.file.pop(0)
        return s

    def estVide(self):
        return len(self.file) == 0

    def __str__(self):
        retour = ""
        for e in self.file:
            retour += str(e) + ','
        return retour


class Producteur:
    def __init__(self, nom):
        self.numeroRessource = 0
        self.nom = nom

    def produire(self):
        global file
        self.numeroRessource += 1
        nomRessource = self.nom + str(self.numeroRessource)
        print(self.nom + " produit la ressource " + nomRessource)
        file.ajouter(nomRessource)

class Consommateur:
    def __init__(self, nom):
        self.nom = nom

    def consommer(self):
        global file
        ressource = file.prelever()
        print(self.nom + " consomme la ressource " + str(ressource))

        
def moteurProducteur():
    producteur = Producteur("P")
    while(True):
        producteur.produire()
        sleep(randint(0,20)/1000)

def moteurConsommateurA():
    consommateurA = Consommateur("A")
    while(True):
        if not(file.estVide()):
            consommateurA.consommer()
            sleep(randint(0,15)/1000)

def moteurConsommateurB():
    consommateurB = Consommateur("B")
    while(True):
        if not(file.estVide()):
            consommateurB.consommer()
            sleep(randint(0,15)/1000)

file = File()

threadProducteur = Thread(target=moteurProducteur)
threadConsommateurA = Thread(target=moteurConsommateurA)
threadConsommateurB = Thread(target=moteurConsommateurB)

threadProducteur.start()
sleep(1)
threadConsommateurA.start()
threadConsommateurB.start()

À l'exécution, on constate très vite que l'un des 2 consommateurs "plante" : en effet, entre le moment où il teste que la file n'est pas vide et le moment où il se sert, l'autre consommateur est passé par là et a pris la dernière ressource disponible.

IV. La notion de verrou

A. Introduction

La seule façon de palier le problème exposé dans la partie suivante est de passer par une opération atomique appelée Test and set : il s'agit d'une opération qui ne peut pas être interrompue (d'ou le qualificatif atomique) qui teste la valeur d'une variable puis la modifie en fonction du résultat du test. Cette opération existe comme opération de base des microprocesseurs, et son utilation se traduit par l'utilisation de verrous en programmation.

Un verrou est un objet possédant 2 états : libre et verrouillé. Un thread qui verrouille un verrou libre continue son exécution normalement. Mais un thread qui tente de verrouiller un verrou déjà verrouillé est bloqué jusqu'à ce que le verrou ait été déverouillé qui l'avait verrouillée.

Lorsqu'un verrou est déverrouillé, l'un des threads en attente de verrouiller se verrou est débloqué et peut maintenant verrouiller ce verrou.

Ainsi, en utilisant des verrous, on peut déterminer des zones d'exclusion mutuelle ou sections critiques qui ne peuvent être exécutées que par 1 thread à la fois. Le problème présenté précédemment peut donc être résolu en utilisant des verrous

B. Les verrous en Python

En Python, la classe Lock du module threading permet de créer des verrous. Ceux-ci peuvent être verrouillés et déverrouillés respectivement par les méthodes acquire() et release().

Étudions le programme suivant :

from threading import Thread
from time import sleep
from random import randint

def traitementA():
    i = 0
    while i < 100:
        print("début section critique A")
        sleep(randint(1,10)/10)
        print("    milieu section critique A")
        sleep(randint(1,10)/10)
        print("fin section critique A")
        sleep(randint(1,10)/10)
        i += 1

def traitementB():
    i = 0
    while i < 100:
        print("début section critique B")
        sleep(randint(1,10)/10)
        print("    milieu section critique B")
        sleep(randint(1,10)/10)
        print("fin section critique B")
        sleep(randint(1,10)/10)
        i += 1
            
t1 = Thread(target=traitementA)
t2 = Thread(target=traitementB)

t1.start()
t2.start()

Si l'on exécute se code, on obtient un affichage du genre :

début section critique A
début section critique B
    milieu section critique B
fin section critique B
    milieu section critique A
fin section critique A
début section critique B
    milieu section critique B
début section critique A
fin section critique B

Comme on peut le voir, les affichages de chaque itération de chaque threads sont entremélés. Si cela n'est pas souhaitable, on va définir les traiements de chaque itération des 2 processus comme des zones d'exclusion mutuelle en utilisant un verrou : au début de l'itération, chaque thread va verrouiller un verrou, qu'il déverouillera à la fin de l'itération. Ainsi, le "traitement" fait par un processus ne peut pas être interrompu par l'autre. Pour ce faire, il suffit de modifier le programme ainsi :

from threading import Thread, Lock
from time import sleep
from random import randint

def traitementA():
    i = 0
    while i < 100:
        verrou.acquire()
        print("début section critique A")        #############################
        sleep(randint(1,10)/10)                  #                           #
        print("    milieu section critique A")   # zone d'exclusion mutuelle #
        sleep(randint(1,10)/10)                  #                           #
        print("fin section critique A")          #############################
        verrou.release()
        sleep(randint(1,10)/10)
        i += 1

def traitementB():
    i = 0
    while i < 100:
        verrou.acquire()
        print("début section critique B")        #############################
        sleep(randint(1,10)/10)                  #                           #
        print("    milieu section critique B")   # zone d'exclusion mutuelle #
        sleep(randint(1,10)/10)                  #                           #
        print("fin section critique B")          #############################
        verrou.release()
        sleep(randint(1,10)/10)
        i += 1
            
verrou = Lock()

t1 = Thread(target=traitementA)
t2 = Thread(target=traitementB)

t1.start()
t2.start()

On obtient alors un affichage qui peut ressembler au suivant :

début section critique A
    milieu section critique A
fin section critique A
début section critique B
    milieu section critique B
fin section critique B
début section critique B
    milieu section critique B
fin section critique B
début section critique A
    milieu section critique A
fin section critique A
début section critique B
    milieu section critique B
fin section critique B
début section critique A
    milieu section critique A
fin section critique A

Comme on peut le voir alors, il n'y a plus d'entrelacement entre les traitements des 2 threads.

C. Exercice

Exercice : Corrigez le programme Producteur/Consommateur de la section III en introduisant un verrou.

from random import randint
from time import sleep
from threading import Thread, Lock

class File:
    def __init__(self):
        self.file = []

    def ajouter(self, e):
        sleep(randint(0,50)/1000)
        self.file.append(e)

    def tete(self):
        return self.file[0]

    def prelever(self):
        sleep(randint(0,50)/1000)
        s = self.file.pop(0)
        return s

    def estVide(self):
        return len(self.file) == 0

    def __str__(self):
        retour = ""
        for e in self.file:
            retour += str(e) + ','
        return retour


class Producteur:
    def __init__(self, nom):
        self.numeroRessource = 0
        self.nom = nom

    def produire(self):
        global file
        self.numeroRessource += 1
        nomRessource = self.nom + str(self.numeroRessource)
        print(self.nom + " produit la ressource " + nomRessource)
        file.ajouter(nomRessource)

class Consommateur:
    def __init__(self, nom):
        self.nom = nom

    def consommer(self):
        global file
        ressource = file.prelever()
        print(self.nom + " consomme la ressource " + str(ressource))

        
def moteurProducteur():
    producteur = Producteur("P")
    while(True):
        producteur.produire()
        sleep(randint(0,20)/1000)

def moteurConsommateurA():
    global verrou
    consommateurA = Consommateur("A")
    while(True):
        verrou.acquire()
        if not(file.estVide()):
            consommateurA.consommer()
            sleep(randint(0,15)/1000)
        verrou.release()

def moteurConsommateurB():
    global verrou
    consommateurB = Consommateur("B")
    while(True):
        verrou.acquire()
        if not(file.estVide()):
            consommateurB.consommer()
            sleep(randint(0,15)/1000)
        verrou.release()

file = File()
verrou = Lock()
threadProducteur = Thread(target=moteurProducteur)
threadConsommateurA = Thread(target=moteurConsommateurA)
threadConsommateurB = Thread(target=moteurConsommateurB)

threadProducteur.start()
sleep(1)
threadConsommateurA.start()
threadConsommateurB.start()