Concepts en mémoire partagée

La programmation en mémoire partagée est un des deux grands types de programmation parallèle. Tous les fils d’exécution partagent la même mémoire : c’est à la fois un atout et un problème. Un atout car cela évite de dupliquer des données car elles peuvent être volumineuses. Un problème car l’accès concurrent à un même espace mémoire en écriture/lecture peut générer des comportements imprédictibles. Cet façon de programmer a été une des forces des supercalculateurs comme le Cray C90… Il existe différents types d’API : les API de threadings standards (fournis par l’OS en général), les API asynchrones (comme asyncio de Python), les threads poids-mouches comme dans Erlang, OpenMP, les instructions SSE2 ou SSE3, etc… Pour résoudre les problèmes et avoir un bon fonctionnement, il faut mettre en place les bonnes techniques ou les bons concepts…

Préemptif ou coopératif 

Lorsque nous avons 10 fils d’exécution en parallèle mais seulement 4 processeurs, nous ne pouvons avoir que 4 fils qui s’exécutent réellement en même temps. La question qui se pose est « qui décide de qui s’exécute et combien de temps ». Il y a deux grandes philosophies qui existent : le mode préemptif et le mode coopératif. Chacun ayant ces avantages et ces inconvénients.

Le mode préemptif

Dans le mode préemptif nécessite un ordonnanceur : un programme qui va décider qui s’exécute et combien de temps sur le processeur. Tous les systèmes Unix, Linux ou Windows disposent d’un tel ordonnanceur. Ce système garantit que chaque fil d’exécution sera exécuté un quantum de temps et qu’aucun d’entre eux n’accaparera la ressource : il garantit une forme d’équité.
Pendant la préemption, l’état du fil d’exécution (drapeaux, registres et pointeur d’instruction) est sauvé dans la mémoire. Il doit être rechargé dans le processeur pour que l’exécution reprenne : c’est la commutation de contexte. Il y a différents défauts à ce mode :

• L’ordonnanceur consomme du temps d’exécution
• Un fil d’exécution qui est bloqué dans une boucle infinie continuera de consommer son quantum de temps machine indéfiniment. En d’autres termes, même si elle ne peut rien faire ou n’a rien à faire, une tâche monopolise de la ressource processeur.

Le mode préemptif se retrouve dans les API de threads de l’OS ou dans OpenMP.

Le mode coopératif

Dans le cadre d’une coopération un fil qui s’exécute décide de passer la main à un autre fil et de libérer la ressource processeur. Le système est conçu pour qu’une tâche qui n’a rien à faire (qui est en attente d’une ressource extérieure) ne soit pas exécutée.  

Le défaut du système est qu’une tâche peut être non coopérative et monopoliser le processeur et ne jamais rendre la main comme une tâche de calcul. Windows 3.1 utilisait un système coopératif qui a, par la suite, été abandonné car inadapté aux besoins d’un OS. Ce système est très adapté aux applications effectuant beaucoup d’IO (entrées/sorties réseaux par exemple) mais pas aux tâches de calculs. 

Le mode coopératif se retrouvera dans les API asynchrones : asyncio en Python, std ::async en C++, etc. 

Dans quel état j’erre ?

Il n’y aurait guère d’intérêt à écrire un article sur le sujet s’il n’y avait pas des difficultés à résoudre… Entre les accès concurrents et les deadlocks, il y a de nombreuses difficultés à résoudre qui ne sont, malheureusement, souvent détectées qu’à l’exécution. 

Pour illustrer la difficulté, nous allons partir d’un cas simple mais concret. Supposons que nous exécutions une application qui gère une variable A (initialisée à 0). Dans l’application, 2 fils d’exécution s’exécutent parallèlement et incrémentent cette variable. Ce qui correspondrait au schéma suivant : 

Malheureusement l’instruction « A=A+1 » peut être décomposé en plusieurs sous-instructions. Dans notre cas, nous allons regarder ce que fait la JVM (Java Virtual Machine) : 

L’accès à la mémoire se fait via le « LOAD @A » et le « STORE @A » ; le reste se fait dans la pile. Et maintenant regardons ce qui se passe lors de différents cas d’exécution des instructions en fonction du temps et selon 2 threads. N’oublions pas qu’à l’état initial A valait 0.  

• Cas 1

Ce que l’on constate, c’est que le calcul se fait simultanément dans les piles de chaque thread mais qu’il y a un décalage dans la sauvegarde en mémoire. A H+3, le thread 1 stocke 1 dans A. A H+4, le thread 2 stocke aussi 1 dans A. Bien que l’on ait fait A+1 deux fois, le résultat final sera A valant 1.  

• Cas 2

A H+3, the thread 1 stocke 1 dans 1; puis à H+4 le thread 2 lit la valeur de A qui vaut 1… Et donc à H+8, la valeur 2 sera stocké dans A. 

• Cas 3 :

Dans le cas suivant, à H+3, la lecture de la valeur de A et l’écriture dans A se font en même temps. Le résultat est donc indéterminé car on ne peut garantir quelle sera la valeur de A pendant le « LOAD @A ». 

La conclusion de ces 3 cas est que, dès lors qu’il y a un accès concurrent à une même ressource (la variable A), il y a un risque d’avoir un résultat non-prédictible. Il faut donc trouver un moyen d’avoir un accès synchronisé à A qui garantisse que les 2 threads n’y accèdent pas simultanément. 

On retrouve aussi ce type de problème dans la vie réelle : 

Le risque de collision est fort, une solution consiste à mettre des feux rouges pour éviter que les véhicules ne puissent se croiser. Il nous reste à trouver les versions informatiques des feux rouges. 

Primitives de synchronisation

Section critique

Concept mis au point en 1965 par Edsger Dijkstra, la section critique est une portion de code dans laquelle il est garanti qu’il n’y aura jamais plus d’un thread simultanément. Voici une représentation des transitions d’états pour entrer/sortir d’une section critique via un réseau de Pétri qui permet aussi de démontrer le bon fonctionnement de la stratégie : 

Pour être efficace, la section critique doit contenir le moins d’instructions possibles. Sinon celle-ci devient un goulot d’étranglement.  

Pour programmer avec une section critique, on a besoin de 3 fonctions (une initialisation, une pour entrer en section critique et la dernière pour en sortir). Par exemple, l’API Win32 propose les fonctions suivantes  InitializeCriticalSection, EnterCriticalSection et LeaveCriticalSection. Ce concept n’est pas forcément accessible dans toutes les API ou OS. 

Atomicité

Une action atomique est une action qui s’exécute sans être interrompue. C’est un concept que l’on retrouve via du typage dans des langages comme C++ (avec les types std::atomic) ou en Rust (via l’espace de noms std::sync::atomic). Les types atomiques doivent être des entiers ou des dérivés d’entiers (comme des pointeurs). 

Sémaphore

Présenté en 1965 par Edsger Dijkstra, un sémaphore est une variable qui sera accédée par différents acteurs de façon séquentielle via des actions atomiques. On utilise un sémaphore lorsque l’on a une ressource (en quantité limitée) partagée entre plusieurs fils concurrents : par exemple les descripteurs de fichiers disponibles dans un OS.  

Pour pouvoir être utilisé de façon logicielle, il doit être couplé au niveau matériel via des actions atomiques. En plus de la fonction d’initialisation, Dijkstra a proposé 2 fonctions (atomiques) : P et V qui viennent du néerlandais Proberen et Verhogen. P permet d’attendre qu’une ressource soit disponible pour la prendre : elle décrémente le compteur contenu dans le sémaphore. V libère la ressource : elle incrémente le compteur du sémaphore. 

Mutex

Mutex est la contraction de « mutual exclusion » : exclusion mutuelle ou verrou. Conceptuellement il est équivalent à un sémaphore de quantité 1 mais conçu avec un algorithme plus performant. 

Il y a une fonction d’initialisation et des fonctions « lock/acquire » et « unlock/release ». « lock/acquire » est bloquante jusqu’à ce que l’accès à la ressource soit disponible. Oublier de libérer le verrou après usage peut créer une situation de deadlock ou inter-blocage. 

Mutex récursif ou réentrant 

Supposons que nous avons une classe A proposant une interface contenant 2 fonctions f1 et f2. Les instances de A pouvant être accédées depuis plusieurs threads, on y définit 2 variables membres « a » et « b ». Pour protéger l’accès concurrent aux variables, on rajoute un mutex « m » comme variable membre. La fonction f1 met à jour la variable membre « a » et la fonction f2 met à jour « b » et appelle f1… En python un verrou se dit Lock, cela donnerait le code suivant : 

from threading import Lock 

class A: 
    def __init__( self ): 
        self.a = 0 
        self.b = 1 
        self.m = Lock() 

    def f1( self ): 
        with self.m: 
            self.a += 1 

    def f2( self ): 
        with self.m: 
            self.b *= 2 
            self.f1() 

obj = A() 
obj.f2() 

Dans le cas suivant, l’appel à f2 on déclenche les appels suivants : 

with m: # acquiert le verrou « m » 
    self.b *= 2 
    with m: # attend que le verrou « m » soit disponible pour l’acquérir 
        # ce qui n’arrivera jamais 
        self.a += 1 

Le fait que le même thread tente d’acquérir une seconde fois un même verrou provoque un inter-blocage. C’est pour résoudre ce type de situation que le verrou récursif ou réentrant a été créé : pour permettre qu’un même thread puisse acquérir plusieurs fois le même verrou mais il devra le libérer pour chaque acquisition !

Timer

Un timer est un moyen d’appeler dans le futur une fonction dans un thread dédié. Un exemple d’utilisation est la SplashScreen dans les frameworks graphiques : elle se ferme automatiquement au bout d’un certain temps. Pour ce faire, avant de lancer l’affichage, il y a un armement de timer pour exécuter, dans le futur, la fonction « Close » de la fenêtre. 

Condition

Une condition est une primitive de synchronisation qui permet de bloquer un ou plusieurs threads dans l’attente d’une notification : elle est toujours couplée à un verrou. Dans le cas d’une situation producteurs/consommateurs, on souhaiterait que les consommateurs soient endormis jusqu’à ce que des producteurs aient générés des messages à consommer : dans ce cas les threads en attente sont réveillés par une notification. 

Les défis à relever

Accès concurrent non protégé

Un cas d’erreur qui arrive malheureusement trop souvent, une variable (ou une portion de code) est oubliée et, bien qu’accédée par plusieurs threads, elle n’est pas protégée par une primitive de synchronisation. Cela va créer des états incohérents qui peuvent au mieux faire crasher l’application ou, au pire, fournir un résultat incorrect sans erreur du programme (ce qui est bien plus dur à corriger : il faut d’abord s’en rendre compte). 

Deadlock

Une situation d’inter-blocage arrive lorsqu’un thread attend (de façon bloquante) une ressource (verrou par exemple) qui ne sera jamais libéré. 

Famine ou starvation

La famine arrive lorsqu’un thread est privé des ressources nécessaires pour terminer son travail. La cause en est souvent un algorithme inéquitable. 

Conclusion – mémoire partagée

Les concepts sont une chose mais leur mise en pratique en est une autre. Et de plus, cela dépend du langage et des API choisies qui peuvent rajouter des contraintes et difficultés. 

A lire aussi :