Le multithreading en C++

Une tâche est un flot d'exécution (une séquence de code) exécuté sur un équipement particulier (PC, PDA, imprimante, ...) à l'intérieur duquel l'ordre d'exécution des instructions élémentaires est total et déterminé par les paramètres d'entrées : les instructions se suivent invariablement les unes après les autres dans le contexte d'exécution de la tâche.
Le multitâche consiste pour un système à pouvoir dérouler plusieurs tâches simultanément, c'est à dire pour lesquels l'ordre de déroulement des différents flots n'est pas total entre eux. Cet ordre peut être perturbé selon deux axes :

• Répartitions de plusieurs tâches sur une même ressource physique : le système accorde du temps à une tâche, puis l'interrompt, change le contexte vers une autre tâche à qui est accordée du temps, et ainsi de suite ;
• Déroulement de plusieurs tâches sur des ressources physiques distinctes : plusieurs tâches se déroulent simultanément sur des ressources physiques différentes.

Le concepteur d'une tâche ne sait pas à priori où et quand son exécution va être interrompu au profit d'une autre tâche ni si une autre tâche est exécutée sur une autre ressource matériel en même temps.
La programmation concurrente recouvre les développements de systèmes faisant intervenir du multitâche.
Selon ce que recouvre le système, le multitâche peut mettre en oeuvre plusieurs équipements et/ou ne concerner qu'un seul d'entre eux. A chaque granularité, ses applications, ses mises en oeuvre, ses problèmes et ses solutions. Nous allons présenter globalement les différents niveaux des systèmes multitâches pour nous concentrer ensuite sur le niveau du thread.

Le niveau le plus haut de la programmation concurrente est donné par un système dont les différentes tâches sont réparties sur des équipements différents : plusieurs PC, des PC et des équipements annexes. Ce sont des systèmes où plusieurs programmes s'exécutent sur des machines différentes et interagissent entre eux pour fournir le service souhaité :

Chaque équipement peut avoir la responsabilité de tâches bien définies et les exécute dans le cadre de son environnement. Les différents équipements se sollicitent mutuellement via des schémas transactionnels complets (requête/réponse) ou non (message) en s'appuyant sur des protocoles avec des niveaux d'abstraction différents : TCP/IP, ODBC, RPC (Remote Procedure Call), CORBA, DCOM, etc.
Citons quelques exemples :

• Web : des serveurs HTTP tournent sur des machines dédiées et des clients web (Firefox, Internet Explorer, ...) tournent côté client. Le client interroge le serveur Web pour une ressource, le serveur construit la réponse, la renvoie au client et finalement le client la traite pour la proposer à l'utilisateur ;
• Mail : idem que précédent : un serveur mail tourne sur une machine dédiée qui se charge de recevoir les mails, de les garder puis les transmettre au client lorsque celui-ci le demande. Le client mail permet de récupérer, lire et envoyer les messages depuis un PC ;
• Restaurant : le serveur saisie votre commande sur un équipement de type PDA, cette commande est transmise à un PC qui assure la facturation, gère les stocks et envoie des commandes vers le serveur des fournisseurs ;
• Informatique distribuée (grille, cluster, ...) : des calculs sont distribués sur plusieurs PC ;
• SGBD : le SGBD présent sur le serveur regroupe les données et gère les transactions; les clients émettent des requêtes vers le serveur pour afficher des vues sur les données ou en modifier le contenu ;
• ...

Les systèmes d'exploitation actuels des PC sont tous multitâches. Vous pouvez surfer avec votre navigateur préféré tout en compilant votre dernier projet C++. Les O.S. spécifiques (en général pour l'embarqué) proposent souvent des architectures multitâches. Les O.S. mettent en oeuvre un ordonnanceur chargé de répartir les différentes tâches sur les ressources matérielles disponibles pour donner l'illusion d'un déroulement simultané. Le nombre de tâches étant le plus souvent supérieure au nombre de coeurs disponibles, l'O.S. découpe le temps processeurs et le distribue sur chaque tâche en basculant les contextes d'exécution. Ceci est évident sur un système à un seul coeur partagé par l'O.S. et les différentes tâches. Mais cela s'applique également sur les systèmes multicoeurs où cependant plusieurs tâches peuvent effectivement se dérouler en même temps sur des coeurs différents :

Le graphe ci-dessus n'a qu'un objectif d'illustration : nous avons choisi de mixer indifféremment les tâches sur les coeurs ce qui n'est pas forcément vrai. L'idée n'en reste pas moins valide.

Les premiers systèmes multitâches pour PC (par exemple, Windows 3.1) proposaient un système multi-tâche collaboratif : chaque tâche devait donner la main explicitement au système pour permettre à l'ordonnanceur de dérouler une autre tâche. Aujourd'hui, ces systèmes ont fait place au multitâche préemptif : le système d'exploitation prend seul l'initiative de suspendre une tâche pour permettre à une autre de se dérouler selon l'algorithme de l'ordonnanceur. Cette gestion est transparente pour le développeur d'un programme. Il n'a plus à se soucier de rendre régulièrement la main à l'OS et en contre partie ne doit pas faire d'hypothèse sur le moment où il est suspendu au profit d'une autre tâche.
Dans ce cadre, on appelle opération atomique une opération ou une séquence d'opérations dont l'exécution n'est pas interrompue par le changement de contexte vers une autre tâche.
L'O.S. peut prévoir des priorités accordées aux différentes tâches. Les tâches les plus prioritaires se voient accordées du temps CPU plus souvent que les tâches non prioritaires. L'utilisation des priorités ne peut se faire qu'en connaissance de l'algorithme de séquencement mis en oeuvre. Ainsi, sous Windows, attribuer à une tâche une priorité extrêmement élevée peut amener le système à ne plus donner du temps CPU à des tâches moins élevées cassant ainsi les bénéfices du multitâche, la tâche à la priorité très élevée gardant en permanence la main.
De façon plus général, l'algorithme d'ordonnancement utilisé par le système est souvent assez complexe, tient compte de divers paramètres (priorités, architecture multiprocesseur, affinités...) et met en oeuvre des stratégies pour éviter les blocages induits par l'ordonnanceur (les Priority Boosts ou Priority Inversion, par exemple). Il est par conséquent assez délicat de prévoir finement le scénario d'ordonnancement des tâches à un moment donné. Jouer avec ces paramètres peut s'avérer assez dangereux en l'absence d'une connaissance maîtrisée de l'O.S. et de sa stratégie d'ordonnancement.

Un système multiprocessus orchestre plusieurs applications concurrentes au sein du même équipement. Un processus se caractérise par le caractère fortement privée de la mémoire physique à laquelle il accède. Il s'agit bien de l'élément déterminant, chaque processus a des zones mémoires physiques distinctes : (1)(2)

Une application ne peut accéder aux zones mémoires d'une autre application. Les mécanismes d'échanges de données et de synchronisation sont contraints par cette étanchéité. En revanche, cela garantie qu'une application ne pourra corrompre directement les données d'une autre application.
L'échange et la synchronisation entre différents processus d'un même équipement peut s'opérer aussi via des interfaces avec des niveaux d'abstractions différents : ODBC, IPC, COM, pipes, mémoire partagée, fichiers, etc.
Quelques exemples de système multiprocessus :

• un service de journalisation utilisé par d'autres applications ;
• un serveur de base de données utilisé comme dépôt local et interrogé par une application d'affichage ;
• un I.D.E orchestrant un éditeur de code, un compilateur, un analyseur de code, un debugger ;
• ...

Un processus contient au moins un thread : une suite d'instructions déroulées séquentiellement. La littérature francophone emploie parfois le terme de processus léger (le terme anglo-saxon de 'light-weight process' peut recouvrir un sens légèrement différent). Le multithreading permet d'exécuter plusieurs séquences d'instructions parallèlement les unes aux autres dans le cadre d'un processus. Les threads d'une même application partagent entre eux une partie de la mémoire du processus. Ils peuvent échanger des informations via des variables. Cela induit des contraintes sur la façon de gérer correctement ces échanges, comme nous le verrons plus loin.
Fondamentalement, la différence entre un thread et un processus est bien cette séparation de la mémoire entre deux processus et son partage entre deux threads. Les threads d'un même processus partagent les variables globales, le tas, les handles de ressources, etc... Ils ont leur propre contexte de registre et leur propre pile, ce qui est nécessaire à l'exécution des séquences d'instructions.

Pourquoi préférer un système multithread à un système multiprocessus ? Il ne s'agit pas de préférer l'un à l'autre. Chacun ayant des domaines d'applications différents. Les systèmes multiprocessus offrent un cloisonnement plus fort des différents services et, en général, les durées de vie de chaque processus est indépendant des autres composants du système. Le multithread se différencie du multiprocessus par la facilité du partage des données puisque la mémoire virtuelle est la même et par la plus grande rapidité de bascule d'un thread à un autre (seule la pile et les registres sont à basculer). Ce qui en fait bien sûr un danger et l'origine de beaucoup de problèmes.

Une dernière remarque pour souligner que les threads sont subordonnées au processus qui les créé. La mort du processus entraîne la fin de tous les threads qu'il possède. Les processus n'ont pas de tels liens de subordination entre eux.

Compte tenu de la diffusion massive des architectures multi-coeurs et avec la mise en place des solutions GPGPU (General-Purpose Processing on Graphics Processing Units ou calcul générique sur un processeur graphique) de type CUDA, le parallélisme monte en puissance dans les développements actuels afin d'améliorer les performances des logiciels. Le parallélisme est entendu dans ce contexte comme la distribution des éléments d'un calcul sur un ensemble de données (3) dans différents coeurs afin d'améliorer significativement les performances du calcul. Les objectifs sont distincts : le parallélisme vise à améliorer le temps de calcul en mettant en oeuvre un algorithme et des outils permettant l'utilisation de plusieurs unités de calcul simultanément ; le multithreading vise à proposer à l'utilisateur la simultanéité au moins apparente du déroulement de différentes tâches sans soucis d'amélioration des performances. Si le multithreading peut s'accompagner d'une amélioration des performances du logiciel, il ne s'agit pas de l'objectif premier.
Ces différences d'objectif se traduisent par une différence dans la granularité des traitements qui font l'objet de l'une ou l'autre technique. Avec le parallélisme, on travaille au niveau d'un algorithme et d'un jeu de donnée. On met l'accent sur l'algorithme mis en oeuvre et sur la façon d'accéder aux données.
Avec le multithreading, on travaille au niveau d'un service pouvant mettre en oeuvre plusieurs algorithmes ou au moins des traitements plus complexes. L'accent est mis sur ses interactions avec les autres threads du système dans le cadre des problématiques de partage de ressources et de synchronisation.
Pour autant, le multithreading demeure une solution pour rendre ses programmes plus performants. La lecture d'un fichier ou l'écriture à l'écran bloquent le thread courant car l'accès aux périphériques est lent. Si une application est découpée entre plusieurs threads, alors pendant que l'un d'entre eux écrit sur un fichier, un autre peut prendre la main et continuer à travailler. Même sur un système mono-coeur cette approche accroît la performance globale de l'application.

Dans la classification de CallahanClassification de Callahan sur la problématique de la concurrence, le multithreading tel qu'il est abordé ici est défini par le pilier 1 : Réactivité et cloisonnement via des agents asynchrones ("Responsiveness and Isolation Via Asynchronous Agents"). Le parallélisme au sens de l'utilisation de plusieurs coeurs de calculs sur un ensemble de données correspond au pilier 2 : Débit et montée en charge des collections concurrentes ("Throughput and Scalability Via Concurrent Collections").

Différentes bibliothèques et techniques émergent pour distribuer des traitements sur différents coeurs de calculs. Citons : CUDA (GPGPU de NVidia), OpenCL (GPGPU du Khronos Group), OpenMP (consortium de constructeurs/éditeur de logiciel), TBB (Intel), QtConcurrent (QtSoftware, ex Trolltech).

Il est important de comprendre que ces différentes approches sont orthogonales entre elles : elles n'agissent pas au même niveau, elles n'ont pas les mêmes problématiques, elles n'utilisent pas les mêmes solutions. A l'heure où la course au GHz cède la place à celle des multicoeurs, le "free lunch" n'est possible que dans les applications qui savent utiliser ces différentes techniques. Le gain d'une application multithread n'est pas forcément proportionnel aux nombres de coeurs disponibles sur la plateforme. D'autres facteurs peuvent limiter ces gains en constituant des goulots d'étranglement : l'accès à des ressources plus lentes (fichiers, socket, ...), l'accès aux données mémoires disparates (cache L1 et L2 inutiles), un nombre de thread inapproprié par rapport aux nombres de coeurs, les caractéristiques des threads (leurs synchronisations, leur priorité, etc.).

Plusieurs scenarii accompagnent généralement la décision d'une conception multithread : un traitement synchrone trop long, un traitement asynchrone trop long, une attente indéterminée ou encore un agent de monitoring.
Dans le premier cas, le multi threading est perçu comme une réponse à un problème de performance. Un traitement long altère la réactivité de l'interface aboutissant à une I.H.M. figée. Le multithreading est alors envisagé pour informer l'utilisateur de l'avancement d'une tâche. Cet avancement a pour double objectif de faire patienter l'utilisateur et de lui signifier que le logiciel est toujours actif. Ce cas s'accompagne souvent par une interface réduite tant que la tâche n'est pas achevée : toutes les fonctionnalités ne sont plus disponibles et un avancement ou une animation maintient une I.H.M. active en attendant la fin du traitement. Les exemples typiques de ce cas sont : l'analyse d'un fichier, la transformation d'une donnée (application d'un filtre à une image)...

Le second cas concerne aussi une fonction suffisamment longue pour altérer la réactivité de l'I.H.M. La tâche n'empêche pas l'utilisateur de poursuivre son travail. Il s'agit bien d'offrir à l'utilisateur la possibilité d'effectuer plusieurs actions en même temps sans se soucier de l'achèvement de l'une avant d'entamer l'autre. L'I.H.M. est peu ou pas réduite et un avancement non intrusif peut informer de l'avancement de la tâche. Les exemples typiques de ce cas sont : l'impression, la sauvegarde des données...

Ce second cas possède une déclinaison : le pipeline. Un traitement se décompose en plusieurs séquences, chacune d'entre elles est déroulée dans un thread séparé. Cela permet de cloisonner les différentes séquences et donne la possibilité de commencer un nouveau traitement alors que le précédent n'est pas encore achevé. Cette approche est appropriée dans les protocoles où un message passe par différentes couches entre la demande applicative et son envoi.

Le troisième cas apparaît lorsqu'on est en attente d'un événement sur une interface externe non liée à l'utilisateur. La bibliothèque ou le système d'exploitation offre une méthode permettant l'attente de l'événement souhaité mais cette méthode ne rend pas la main tant que cet événement ne survient pas. Entre temps, on souhaite maintenir l'I.H.M. active et permettre à l'utilisateur de continuer son travail. Les exemples typiques concernent l'attente d'un message réseau, d'un événement sur une carte série, d'un signal sur une carte d'acquisition...

Les applications clients/serveurs peuvent utiliser une variante du cas précédent dans l'implémentation du serveur. Un thread principal est dédié à l'écoute des nouveaux clients. Puis la gestion effective de chaque client est déléguée à un thread dédié. Les threads clients et le thread d'écoute n'ayant plus d'échange :

Le quatrième met en concurrence une application principale et un thread qui surveille cette application. L'application principale se déroule dans un ou des threads pendant que le thread de monitoring tourne à côté. Il peut interroger l'application sur son état, être notifié par l'application de modifications de son état ou encore avoir des séquences courtes d'échanges requête/ réponse. Les exemples se situent dans l'aide contextuelle, le log d'information, la mise en place d'un chien de garde (watchdog)...

Les scénarii présentés mettent en concurrence un traitement et une I.H.M. En fait, ils peuvent être généralisés en mettant en concurrence un traitement non plus face à une I.H.M qui doit rester disponible mais avec un autre traitement critique qui doit rester réactif (Responsiveness dans la littérature anglo-saxone). Ainsi un serveur peut maintenir un thread principal pour l'écoute des nouvelles connexions et un ou des threads séparés pour la gestion des sessions avec les clients. Ce programme n'a pas d'I.H.M. mais la problématique reste identique : empêcher qu'une interface (celle qui attend les nouvelles connexions) ne soit bloquée à cause d'autres traitements (le dialogue avec les clients déjà connectés).

Les applications suffisamment complexes pour ressentir le besoin du multithreading sont souvent construites avec des frameworks offrant des services assez riches : MFC, Qt, wxWidgets, etc. Ces ateliers possèdent des mécanismes de notification par appel de callback ou par envoi de message pour des opérations liées à l'attente d'événements sur une interface spécifique. Ainsi, dans le cadre de projets réseaux, les MFC proposent la classe CAsyncSocket qui ne bloque pas sur l'envoi ou la réception d'un message. La spécialisation de OnReceive dans une classe dérivée de CAsyncSocket est appelée par l'atelier dans le contexte du thread courant dès lors que des données sont disponibles. De la même façon, wxWidgets émet des événements wxSOCKET_INPUT ou wxSOCKET_OUTPUT pour la réception ou l'émission de données. Ces mécanismes évitent d'avoir à gérer des réceptions ou des envois bloquants. Ces solutions sont à préférer pour au moins deux raisons. D'abord elles sont cohérentes avec le service proposé par le framework aboutissant naturellement à une architecture plus lisible dans ce cadre. Ensuite le multithreading induit une architecture logicielle plus complexe et fait émerger - comme nous allons le voir - des problèmes spécifiques : il ne faut jamais hésiter à opter pour des architectures simples garantissant moins de bug et facilitant les tâches de maintenance et d'évolution du logiciel.

Bien se documenter sur son framework ou sur la bibliothèque faisant émerger le besoin de multithreading.

Les framework d'I.H.M. sont construits autour de boîtes aux lettres et d'échanges de messages entre les différents objets entre eux suite à des événements internes ou à une interaction avec l'utilisateur. Lorsqu'il ne se passe rien, c'est à dire que l'utilisateur n'interagit pas avec l'application et que celle-ci est stable, la plus part de ces plateformes proposent un événement OnIdle. Ceci offre la possibilité d'effectuer des traitements pendant la période d'inactivité du logiciel.
Il faut bien comprendre qu'à l'échelle d'un processus l'inactivité d'un logiciel est un événement courant. Deux appuis touches successifs sur un clavier représentent pour un processus deux événements 'rares' au milieu d'une période assez calme.
Comment mettre en oeuvre cette technique ? Pour les cas de traitement trop long, cela consiste à créer un contexte et à atomiser le traitement en opérations plus élémentaires. A chaque appel à OnIdle, une opération élémentaire est déroulée et le contexte actualisé. Le traitement se termine dès que la dernière opération est exécutée.
Pour le cas d'attente d'un événement externe, la bibliothèque utilisée peut permettre d'associer un timer à l'attente de l'événement extérieure. Il suffit de positionner un timer de zéro ou suffisamment petit et de regarder si le retour est lié à l'expiration du timer ou à la réception d'un signal.
Cette approche souffre principalement de ne pas maîtriser à priori quand une séquence de OnIdle va être déroulée. Si l'application est très sollicitée, l'accomplissement de la tâche en est d'autant plus affecté. Cette solution peut être mise en oeuvre lorsque l'achèvement de la tâche de fond ne revêt pas un caractère important. Le second scénario proposé ci-dessus cadre assez bien avec cette solution puisque la tâche n'altère pas le déroulement de l'application.

L'utilisation d'un timer constitue une approche identique à la précédente si ce n'est qu'on ne laisse pas l'environnement décider de la fréquence de l'appel à notre traitement. L'idée est d'armer un timer et d'appeler la méthode de traitement à chaque fois que le timer claque. Les traitements longs synchrones ou asynchrones sont comme précédemment découpés en opérations plus petites et un contexte est associé. A chaque déclenchement du timer, une opération élémentaire est déroulée et le contexte est mis à jour. Lorsque la dernière opération est terminée, le timer est arrêté.
Pour le cas d'attente d'un événement externe, il suffit d'interroger l'interface en mode non bloquant à chaque fois que le timer se déclenche.

Cette solution concerne spécifiquement le cas d'un traitement trop long que l'on souhaite synchrone avec une I.H.M. d'attente. Le problème souvent rencontré est de permettre à l'I.H.M. de se mettre à jour et de réagir à minima pendant toute la durée du traitement. L'idée est de découper le traitement en opérations élémentaires. Entre chaque opération, la pompe des messages est appelée de façon à vider les messages générés soit par le traitement soit par l'utilisateur. Cette solution est le symétrique de celle de OnIdle : ici, ce n'est pas le traitement qui est appelé dans le temps disponible entre deux messages, mais c'est la boucle de message qui est appelée entre deux opérations du traitement.

L'appel régulier à une méthode permettant d'interroger l'état d'une interface s'appelle le polling. C'est souvent une technique alternative à l'utilisation des mécanismes de messages. L'application consiste alors à dérouler une boucle continuelle d'interrogation des interfaces (polling clavier, souris, réseau, etc.), suivi d'une séquence de mise à jour de l'état de l'application en fonction de l'état des interfaces.

Cette méthode peut ne pas toujours être adéquate et aboutir à des pertes d'information. Si le système passe d'un état E0 à un état E1 puis revient à l'état initial E0 entre 2 séquences consécutives de polling alors la transition à l'état E1 est perdue.

Une application proposant une interface un tant soit peu riche va s'appuyer sur une architecture logicielle à base de messages/boîtes aux lettres (les windows), le traitement des messages et leur échange est orchestré par la boucle principale chargée de pomper les messages et les transmettre aux boîtes aux lettres concernées, déclenchant l'action attendues. Ce système construit autour d'objet boîtes aux lettres se sollicitant mutuellement par l'envoi de message pour réaliser leur service correspond assez bien à un système multithread collaboratif. Le contexte de chaque thread est porté par l'instance d'une la boîte au lettre (HWND/CWnd) et le changement de contexte nécessite que chaque boîte au lettre redonne la main à la pompe des messages. Si les objets ne communiquent entre eux que par échange de messages, le parallèle reste à mon sens pertinent.

La situation de compétition ou race condition décrit un système dont le résultat est dépendant de l'ordre dans lequel sont effectuées certaines opérations. L'exemple le plus trivial apparaît lorsque plusieurs threads travaillent sur la même donnée sans synchronisation entre eux :

int variable;
void thread_1()
{
   variable = 1;
}

void thread_2()
{
   variable = 2;
}

La valeur de variable dépend de l'ordre dans lequel les threads sont exécutés. Ce problème paraît évident, mais la situation de compétition apparaît sur des opérations simples et où on ne l'attend pas forcément :

int variable = 0;
void thread_1()
{
   variable++;
}

void thread_2()
{
   variable++;
}

Quelle est la valeur de variable une fois thread_1 et thread_2 terminés ? Aucune idée ! Cela dépend plus subtilement de l'ordonnancement des threads. En effet, l'incrément (variable++) n'est pas une opération atomique. Pour s'en convaincre, il suffit de regarder le code assembleur de l'opération (code assembleur de Visual C++ Express 2008 en mode debug) :

mov eax,dword ptr [variable] 
add eax,1 
mov dword ptr [variable],eax

Imaginons ce premier scénario :

1. Le premier thread prend la main :
   1. A l'entrée, variable vaut 0
   2. On charge dans le registre eax la valeur de variable : eax <- 0
   3. On ajoute 1 à eax : eax <- 1
   4. On copie la valeur de eax dans variable : variable <- 1
2. Le second thread prend la main :
   1. A l'entrée, variable vaut 1
   2. On charge dans le registre eax la valeur de variable : eax <- 1
   3. On ajoute 1 à eax : eax <- 2
   4. On copie la valeur de eax dans variable : variable <- 2

Tout à l'air de fonctionner comme on aurait envie. Maintenant, regardons le scénario suivant :

1. Le premier thread prend la main :
   1. A l'entrée, variable vaut 0
   2. On charge dans le registre eax la valeur de variable : eax <- 0
   3. Le thread est suspendu : son registre est sauvegardé
2. Le second thread prend la main :
   1. A l'entrée, variable vaut 0
   2. On charge dans le registre eax la valeur de variable : eax <- 0
   3. On ajoute 1 à eax : eax <- 1
   4. On copie la valeur de eax dans variable : variable <- 1
3. Le premier thread récupère la main :
   1. On restaure les registres : eax <- 0
   2. On ajoute 1 à eax : eax <- 1
   3. On copie la valeur de eax dans variable : variable <- 1

Une fois les deux threads exécutés, variable vaut 1 !

Ces exemples doivent vous faire comprendre que si le problème se pose pour des opérations aussi simples, dès lors que les traitements sont complexes, il n'est plus possible de concevoir un comportement correct sans outils spécifiques pour synchroniser l'accès à des ressources partagées. C'est ce que nous verrons plus loin.

Imaginons le scénario suivant. La porte de votre bureau se déverrouille avec votre badge d'accès électronique. Ce midi vous avez été déjeuné avec un collègue qui travaille dans le bureau d'à-côté. En rentrant, vous vous rendez compte que vous avez oublié votre badge dans le bureau de votre collègue ... et pas de chance, votre collègue a oublié le sien dans votre bureau ! Vous ne pouvez déverrouiller votre bureau tant que votre collègue n'a pas déverrouillé sa porte mais votre collègue ne peut déverrouiller son bureau tant que vous n'avez pas déverrouillé votre porte. Vous ne pouvez plus qu'attendre tous les deux sans rien faire : votre responsable va râler ! Vous avez un interblocage ou deadlock.
Le monde des threads est aussi fait de portes et de verrous. Ces objets permettent de résoudre le problème précédent de race condition. Deux threads qui souhaitent partager une ressource utilisent ce système : le premier verrouille la porte tant qu'il a besoin de la ressource. Le second thread ne peut accéder à la ressource tant que la porte est verrouillée. Il se met en attente. Il devient clair maintenant qu'avec ce système l'interblocage peut se produire entre deux threads qui partagent deux verrous et attendent mutuellement l'ouverture de la porte verrouillée par l'autre :

void thread_1()
{
   attendre_porte_1_déverrouillée(); // 1.1
   verrouiller_porte_1(); // 1.2
   attendre_porte_2_déverrouillée(); // 1.3
   verrouiller_porte_2(); // 1.4
   traitement(); // 1.5
   déverrouiller_porte_2(); // 1.6
   déverrouiller_porte_1(); // 1.7
}
void thread_2()
{
   attendre_porte_2_déverrouillée(); // 2.1
   verrouiller_porte_2(); // 2.2
   attendre_porte_1_déverrouillée(); // 2.3
   verrouiller_porte_1(); // 2.4
   traitement(); // 2.5
   déverrouiller_porte_1(); // 2.6
   déverrouiller_porte_2(); // 2.7
}

L'exécution suivante provoque l'interblocage :

• 1.1
• 1.2
• 2.1
• 2.2
• 1.3
• 2.3
• -> deadlock !

Une déclinaison particulière de l'interblocage est le self deadlock. A priori, une fois une porte verrouillée, elle est interdite aux autres threads mais aussi au thread qui l'a verrouillée. Lorsque le même thread essaie de verrouiller une porte qu'il a déjà verrouillé, le blocage obtenu s'appelle un self deadlock

void thread_1()
{
   attendre_porte_déverrouillée();
   verrouiller_porte();
   traitement();
   déverrouiller_porte();
}

void traitement()
{
   attendre_porte_déverrouillée();
   verrouiller_porte();// self deadlock !
}

Pour terminer sur ces deadlocks, signalons que les fonctions permettant d'attendre qu'une porte soit déverrouillée sont optimisées pour ne pas consommer inutilement des ressources systèmes. Lorsqu'un thread entre dans une telle attente, le système suspend le thread et ne lui donne plus de temps processeur tant que la porte est verrouillée. Une application de deux threads en interblocage ne consomme plus aucune ressource (temps processeur nul) et ne fait plus rien. Encéphalogramme plat___

Pour résoudre le problème du deadlock présenté ci-dessus, les solutions présentent des fonctions d'attente associées à une durée. Si la porte n'a pu être déverrouillée pendant cette durée, alors un état d'échec est notifié à l'appelant laissant celui-ci la possibilité de passer à autre chose. Ceci peut permettre au moins à chaque thread de passer dans un mode d'échec et à l'application de continuer à fonctionner. Mais toute solution amène son propre cortège de problèmes
Reprenons notre situation précédente : vous travaillez au premier étage et votre collègue au second. En rentrant de déjeuner chacun part vers son bureau pas encore conscient de la catastrophe. Arrivé devant votre porte, vous vous souvenez que vous avez laissé votre badge chez votre collègue. Vous vous rendez à son bureau par l'escalier. Ce dernier a eu la même démarche que vous, mais a pris l'ascenseur : vous ne vous êtes pas croisé. Arrivé devant son bureau, vous vous rendez compte que la porte est fermée et décidez d'attendre cinq minutes le retour de votre collègue. Ce dernier attend aussi devant votre porte. Les cinq minutes écoulés, vous vous dites qu'il est trop bête de perdre ainsi son temps, vous allez prendre un café et reviendrez ensuite en pensant que votre collègue sera bien de retour à ce moment. Ce dernier a le même raisonnement que vous, mais n'aimant pas le café préfère aller discuter un instant avec un autre collègue. De retour chacun vers la porte de l'autre, vous pestez et attendez encore cinq minutes. A la fin de la journée, votre collègue et vous même avez passé votre temps à vous agiter mais sans pouvoir accéder à vos bureaux respectifs : c'est le live lock.
Une situation encore plus simple : vous attendez l'ascenseur, la porte s'ouvre, exactement en face de vous une autre personne. Vous esquissez un pas sur la gauche pour vous permettre de vous croiser. Malheurs ! Elle a la même idée que vous et esquisse aussi un pas sur sa droite se retrouvant inévitablement en face de vous. Vous voilà tous deux parti pour une danse sans fin de gauche à droite et de droite à gauche.
Le live lock à la différence du deadlock précédent peut laisser croire que le logiciel continuer de fonctionner car régulièrement les threads sont actifs et consomment des ressources, mais les tâches n'avancent pas car ils sont toujours en attente croisée :

void thread_1()
{
   attendre_porte_1_déverrouillée(); // 1.1
   verrouiller_porte_1(); // 1.2
   while(FAILED(attendre_porte_2_déverrouillée(10 secondes))  // 1.3
   {
      déverrouiller_porte_1(); // 1.4
      traitement_alternatif(); // 1.5
      verrouiller_porte_1(); // 1.6
   }
//   ...
}
void thread_2()
{
   attendre_porte_2_déverrouillée(); // 2.1
   verrouiller_porte_2(); // 2.2
   while(FAILED(attendre_porte_1_déverrouillée(10 secondes))  // 2.3
   {
      déverrouiller_porte_2(); // 2.4
      traitement_alternatif(); // 2.5
      verrouiller_porte_2(); // 2.6
   }
//   ...
}

Un live lock correspond au séquencement suivant :

• 1.1
• 1.2
• 2.1
• 2.2
• 1.3 (attente de 10 secondes pour le thread 1)
• 2.3 (attente de 10 secondes pour le thread 2)
• 1.4
• 1.5
• 1.6
• 2.4
• 2.5
• 2.6
• 1.3 (attente de 10 secondes pour le thread 1)
• 2.3 (attente de 10 secondes pour le thread 2)
• 2.4
• 2.5
• 1.4
• 1.5
• 2.6
• 1.6
• 2.3 (attente de 10 secondes pour le thread 2)
• 1.3 (attente de 10 secondes pour le thread 1)
• ...

La famine ou starvation est une généralisation des problèmes d'interblocages : une tâche ne peut accéder à une ressource pendant un temps indéterminé.
Dijkstra a le premier mis en évidence ces problèmes d'accès aux ressources partagées et Hoare l'a illustré par le problème du dîner des philosophes. Imaginez cinq philosophes assis à une table ronde, chacun a à sa gauche une fourchette. Dans leur assiette : un plat de spaghettis.

Pour manger, un philosophe a besoin de deux fourchettes et il ne peut prendre que celle qui est soit juste à sa gauche soit juste à sa droite. Bien sûr, les philosophes n'échangent pas entre eux. L'interblocage apparaît si tous les philosophes s'emparent de leur fourchette de gauche et se mettent à attendre celle de droite accaparée par le voisin. D'autres stratégies peuvent conduire à situation de famine d'un ou de plusieurs convives.
Dans un système avec priorité, un des threads peut ne jamais accéder à un verrou car des threads plus prioritaires l'auront toujours avant lui. Ceci peut devenir plus critique si trois threads T1, T2 et T3 d'ordre de priorité croissante, avec T1 attend une ressource verrouillée par T2 et T3 attend une ressource verrouillée par T1. T3, le thread pourtant le plus prioritaire, reste bloqué.

Une tâche peut passer dans un état suspendu : elle n'est alors plus éligible par l'ordonnanceur et ne reçoit donc pas de temps CPU pour s'exécuter tant qu'elle reste dans cet état. Une tâche passe dans un état suspendu :

• Implicitement lorsqu'elle attend qu'un verrou se libère et d'une façon général par tous les mécanismes d'attente proposés par le système ;
• Explicitement par des fonctions proposées par le système (Sleep).

On parle d'endormissement (dormancy) dès lors qu'une tâche reste dans cet état d'attente pendant un temps indéterminé. L'endormissement peut être lié à la famine (attente indéterminée d'une ressource) ou tout simplement à une erreur : la tâche est suspendue et jamais réveillée.

La réentrance est un terme apparu au départ dans la programmation système : une fonction est réentrante dès lors qu'elle peut être appelée avec des paramètres différents par une interruption alors qu'elle est déjà en cours d'exécution :

Dans le cadre de la programmation concurrente, une fonction réentrante est une fonction qui peut être exécutée correctement par plusieurs threads en même temps ou par le même thread avec des paramètres différents :

Une fonction est thread-safe si elle peut être appelée correctement par plusieurs threads distincts en même temps avec les mêmes paramètres. Grossièrement, une fonction thread-safe est une fonction qui se protège des problèmes de race-condition si nécessaire.

Par extension :

• Une classe est réentrante si toutes ses fonctions peuvent être appelées par plusieurs threads ou par le même threadsimultanément sur différentes instances.
• Une classe est thread-safe si toutes ses fonctions peuvent être appelées par plusieurs threads distincts simultanément sur la même instance.

En fait, une classe réentrante est une classe dont toutes les fonctions ne s'appuient que sur l'état de l'objet et des paramètres fournis. Elles ne dépendent dans leur déroulement ou dans leur retour ni de variables statiques de la classe, ni de variables statiques locales, ni de variables globales et ne font appels qu'à des classes réentrantes ou des fonctions libres réentrantes. La garantie de réentrance est articulée autour des paramètres qui lui sont donnés.
Une classe est thread-safe dès lors qu'elle utilise des moyens de synchronisation (verrous) pour l'accès aux ressources partagées. Le thread-safety est garantie par l'implémentation correcte de la classe.

Une fonction constante peut ne pas être réentrante : elle peut très bien s'appuyer sur des variables statiques ou globales.

Une fonction constante peut ne pas être thread-safe : elle peut accéder à un état en lecture seule mais celui-ci être modifié par ailleurs dans une autre fonction constante aboutissant à une situation de compétition.

L'utilisation d'une variable statique constante rompt la réentrance d'une fonction ou d'une classe. Le caractère constant ne suffit pas à se prémunir contre une exécution différenciée selon l'ordonnancement des threads : void fonction(int par_) { static const int first_par = par_; // ... }

La propriété thread-safe ne garantie pas la réentrance : une fonction peut s'appuyer sur un verrou non réentrant.

La réentrance ne garantie pas le caractère thread-safe : si on différencie le caractère réentrant du caractère thread-safe par le fait que le premier est considéré au regard d'appels avec des paramètres différents alors que le second suppose garantir l'appel pour des paramètres identiques, les deux notions deviennent orthogonales. Une classe peut très bien n'avoir que des fonctions s'appuyant uniquement sur l'état de l'instance et les paramètres fournis mais en aucun cas ne protégé l'accès à son état d'accès concurrent. Elle est bien réentrante mais n'est pas thread-safe.

IV-A-1. Thread principal et threads secondaires▲

IV-A-2. Threads I.H.M. et threads de travail▲

IV-A-3. Thread joignable et thread détaché.▲

IV-A-4. Qu'attend-on d'un type thread ?▲

IV-A-5. Attendre la fin d'un thread▲

IV-A-6. Suspendre/Reprendre▲

IV-A-7. Thread Local Storage▲

IV-B-1. Les mutex▲

IV-B-2. Les lock▲

IV-B-3. Les sémaphores▲

IV-C-1. Les condition variables▲

IV-C-2. Les barrières▲

Essentiellement en C++0x.

Les locks win32.
Slim Reader/Writer (SRW) Locks de Vista

Evènements se rapprochent des conditions -> ConditionVariable sous Vista

InitOnce[XXX] ? Interlocked[XXX] ?

Utilisations des versions multi-thread des bibliothèques boost compilées.