MSDN Magazine > Accueil > Tous les numéros > 2008 > Juin >  Simultanéité : Outils et techniques pour l'iden...
Simultanéité
Outils et techniques pour l'identification des problèmes de simultanéité
Rahul V. Patil et Boby George

Cet article aborde les sujets suivants :
  • Problèmes de test de simultanéité
  • Bogues insaisissables et leurs dépendances
  • Nouveaux outils pour la détection des barrages
  • Pratiques recommandées pour la conception de vos tests
Cet article utilise les technologies suivantes :
Analyse dynamique et statique, vérification de modèle
Pour satisfaire le besoin perpétuel d'augmentation de puissance informatique, l'industrie du matériel informatique s'oriente de plus en plus vers les systèmes à processeurs multicœurs. Contrairement aux performances d'application accrues obtenues grâce à des processeurs aux vitesses d'horloge plus élevées, les améliorations de performances dans les systèmes multicœurs peuvent uniquement être obtenues en écrivant des programmes parallèles efficaces.
Différentes formes de parallélisme existent depuis longtemps dans le secteur du logiciel. Cependant, la création d'applications logicielles grand public exploitant la puissance totale du matériel parallèle nécessite des modifications significatives des pratiques conçues pour les applications séquentielles.
Les applications parallèles ne sont pas simples à tester. Par exemple, les bogues de simultanéité sont difficiles à détecter en raison du comportement non déterministe dont font preuve les applications parallèles. Même si ces bogues sont détectés, il est difficile de les reproduire de façon systématique. Qui plus est, après avoir remédié à un défaut, il est difficile de garantir que ce défaut a véritablement été corrigé et n'a pas été simplement masqué. En outre, le parallélisme peut également introduire de nouveaux goulots d'étranglement de performances devant être identifiés.
Dans cet article, nous examinerons les techniques de test pour les programmes parallèles et présenterons six outils utiles que vous pouvez utiliser pour détecter les défauts potentiellement sérieux. Nous commencerons avec les catégories suivantes de bogues de simultanéité : conditions de concurrence, exclusions mutuelles incorrectes et réordonnancement de mémoire.

Conditions de concurrence, blocages et autres
La concurrence survient lorsque deux threads d'exécution ou plus d'un programme multithread essaient d'accéder aux mêmes données partagées et qu'au moins un des accès est une écriture. Les conditions de concurrence nuisibles sont source d'imprévisibilité et sont souvent difficiles à détecter. Les conséquences d'une condition de concurrence pourraient ne devenir visibles que beaucoup plus tard ou dans une partie totalement différente du programme. Elles sont également incroyablement difficiles à reproduire. Les concurrences sont évitées en utilisant des techniques de synchronisation pour séquencer correctement les opérations entre les threads.
Identification des données de test et rapports de mesures
Pour les applications parallèles, les données de test sont définies en identifiant les aspects d'évolutivité du scénario. L'évolutivité dont fait preuve l'application dépend vraiment de la capacité de parallélisme de l'algorithme utilisé. Certains algorithmes peuvent produire une accélération super-linéaire pour certains groupes de problèmes (par exemple, une recherche via une distribution non uniforme). D'autres algorithmes peuvent ne pas produire d'accélération excessivement parallèle en raison d'une capacité de parallélisme limitée, ce qui se traduit par des accélérations de la vitesse d'exécution totale non proportionnelles au nombre de processeurs. Pourtant, d'autres algorithmes (comme les tris) n'évoluent pas de façon linéaire en fonction de la taille du jeu de données. Comme vous pouvez le constater, il est important de comprendre dans quelle mesure les performances d'application évoluent dans les catégories suivantes :
Nombre de threads ou de cœurs de processeur L'utilisateur s'attend généralement à ce qu'une application parallèle évolue de façon linéaire lorsque le nombre de processeurs ou de threads augmente.
Taille du jeu de données L'utilisateur s'attend généralement à ce que les performances de l'application parallèle ne diminuent pas lorsque la taille du jeu de données d'entrée augmente.
Charge de travail d'exécution La quantité de travail effectuée par le thread peut ne pas demeurer constante à mesure que l'exécution progresse. Elle peut augmenter ou diminuer, varier de façon aléatoire ou présenter une distribution normale. Les variations de la charge de travail au fil de la progression de l'exécution peuvent avoir une incidence sur les caractéristiques de performances de l'application. Les variations de la charge de travail au fil de la progression de l'exécution peuvent prendre les formes suivantes : charge de travail constante, augmentation de la charge de travail, diminution de la charge de travail, charge de travail aléatoire et charge de travail normalement distribuée.
Le temps d'exécution est la mesure la plus couramment utilisée pour la création de rapports. Les autres mesures utilisées incluent l'accélération atteinte par rapport à l'application séquentielle et l'accélération dans les différentes catégories d'évolutivité. Il est important de définir la mesure utilisée pour la création de rapports et son mode de calcul. Voici quelques bonnes questions pour démarrer : Quelles sont les valeurs devant figurer sur le rapport ? Comment apparaîtront-elles sur le rapport ? Les instruments utilisés pour prendre la mesure affecte-t-ils les performances ? De plus, lorsque c'est possible, prenez la mesure dans plusieurs parties afin qu'il soit possible de comprendre les performances des sous-parties du système.
Parfois, les concurrences peuvent être sûres et intentionnelles. Par exemple, il pourrait exister un indicateur global nommé « done » (Terminé), pour lequel il existe un seul thread d'écriture mais de nombreux threads de lecture. Le thread d'écriture configure l'indicateur pour qu'il indique à tous les threads de se terminer sans incident. Tous les threads de lecture peuvent être exécutés en boucle avec while (!done), en lisant l'indicateur en continu. Lorsqu'un thread remarque que l'indicateur done est défini, il quitte sa boucle while. Dans la plupart des cas, ceci est une concurrence bénigne. Comme nous l'expliquerons plus loin dans cet article, il existe des outils permettant de détecter les conditions de concurrence. Cependant, ces outils risquent de signaler des concurrences qui sont en fait bénignes, et de faire état d'erreurs connues sous le nom de faux positifs.
Un blocage survient lorsque deux threads ou plus s'attendent mutuellement, formant alors un cycle et empêchant tous les threads de progresser de quelconque façon. Les blocages peuvent être introduits par le programmeur en essayant d'éviter des conditions de concurrence. Par exemple, l'utilisation incorrecte de primitives de synchronisation, comme l'acquisition de verrous dans un ordre incorrect, peut entraîner une situation où deux threads ou plus s'attendent mutuellement. Les blocages peuvent également survenir dans des cas où aucune structure de verrouillage n'est utilisée. Tout type d'attente circulaire peut provoquer un blocage.
Examinons l'exemple suivant de situation de blocage potentielle. Le thread 1 fait ceci :
Acquire Lock A;
Acquire Lock B; 
Release Lock B; 
Release Lock A;
Thread 2 proceeds like so:
Acquire Lock B;
Acquire Lock A; // if thread 1 has already acquired lock 
                // A and waiting to acquire lock B, then 
                // this is a deadlock
Release Lock A;
Release Lock B;
La privation est un délai illimité ou un blocage permanent d'un ou plusieurs threads exécutables dans une application multithread. Les threads qui ne sont pas planifiés pour s'exécuter même s'ils ne bloquent pas ou n'attendent pas quoi que ce soit sont dits en privation. La privation résulte généralement des règles et stratégies de planification. Par exemple, si un thread de haute priorité non bloquant qui s'exécute en permanence est planifié avec un thread de basse priorité, sur un processeur monocœur, le thread de basse priorité n'aura aucune chance de s'exécuter. Pour éviter de telles conditions, le Planificateur de Windows® intervient fréquemment pour réduire la privation en rehaussant de temps en temps les priorités des threads en privation.
Les verrous actifs surviennent lorsque les threads sont planifiés mais ne progressent pas car ils réagissent continuellement à leurs changements d'état réciproques. La meilleure façon de décrire ceci est d'imaginer deux personnes se rapprochant dans un couloir étroit et s'écartant simultanément pour laisser passer l'autre, en bloquant chaque fois le chemin de l'autre. Ces écarts empêchent toute progression positive et entraînent un verrou actif. Une utilisation de processeur élevée sans véritable signe de travail effectué est un signe classique de verrou actif. Les verrous actifs sont incroyablement difficiles à détecter et à diagnostiquer.

Problèmes d'ordonnancement de mémoire
Lorsque le compilateur optimise le code, il peut décider de réordonnancer des éléments de code pour améliorer les performances. Cependant, ceci peut provoquer un comportement imprévu dans les threads qui surveillent les modifications de l'état global. Par exemple, imaginons que vous disposez de deux threads d'exécution : thread 1 et thread 2. Supposons également que vous disposez de deux variables globales, x et y, toutes deux initialisées sur 0. Le thread 1 exécute ces lignes :
x=10;
y=5;
Le thread 2 exécute ceci :
if (y == 5)
{
  Assert(x != 10);
}
Ici, le compilateur d'optimisation pourrait observer que y sera en fin de compte réaffecté à 5 de toute façon, et pourrait réordonnancer le code pour que y soit affecté de 5 avant que x soit affecté de 10. Du point de vue du thread unique exécutant ces deux affectations, l'ordonnancement n'a pas d'importance. Par conséquent, il existe un risque que l'assertion du thread 2 soit déclenchée, car x pourrait ne pas être égal à 10.
Lorsque c'est nécessaire, il est possible d'éviter l'ordonnancement de mémoire de compilateur en utilisant des variables volatiles et des caractéristiques de compilateur intrinsèques. Il est également utile de signaler qu'avec les indicateurs d'optimisation courants activés, le thread 2 peut ne jamais voir de mise à jour des variables y ou x. L'utilisateur devra ici utiliser des variables volatiles.
Le réordonnancement de compilateur n'est pas la seule complication. Les optimisations d'accès mémoire telles que la mise en cache et l'extraction préalable par les exécutions spéculatives peuvent donner lieu à une situation où les opérations de mémoire exécutées par un thread sur un processeur sont perçues comme survenues dans un ordre différent par un autre thread sur un autre processeur. Ce type de réordonnancement de mémoire peut uniquement se produire sur un système multiprocesseur ou multicœur.
Pour clarifier, supposons qu'il existe deux threads d'exécution : thread 1 et thread 2. Supposons en outre que m et n sont globaux, tous deux initialisés sur 0, et que a, b, c et d sont des variables locales. Le thread 1 (sur le processeur 1) a ces instructions :
m = 5;     // A1
int a = m; // A2
int b = n; // A3
Le thread 2 (sur le processeur 2) a celles-ci :
n = 5;     //A4
int c = n; //A5
int d = m; //A6
Logiquement (dans un monde où la mémoire est séquentiellement cohérente), b == d == 0 ne peut jamais se produire après l'exécution de toutes ces instructions. Cependant, le réordonnancement de mémoire matériel peut entraîner une situation où les écritures dans la mémoire partagée (A1 et A4) sont transférées au tampon de stockage, ce qui peut mener les différents processeurs à considérer différemment les écritures.

Stratégies de test
La batterie de tests d'une application simultanée comprend des tests d'exactitude, de fiabilité, de performances et d'évolutivité. L'exactitude de l'application est déterminée à l'aide de techniques telles que l'analyse statique, l'analyse dynamique et la vérification de modèle. Les performances et la fiabilité sont testées en étudiant les charges induites pas le parallélisme et le test de contrainte. L'évolutivité est testée en analysant le comportement de l'application sur des systèmes de tailles variables.
Les techniques d'analyse statique analysent le code sans exécuter le programme. D'ordinaire, l'analyse statique est exécutée en examinant les métadonnées d'une application compilée ou d'un code source annoté. L'analyse inclut généralement une inspection formelle pour garantir que les intentions et les suppositions du programmeur empêchent un comportement inexact. Prefix et Prefast sont deux des outils d'analyse statique les plus utilisés pour les applications natives, tandis que FxCop est très apprécié pour le code géré.
L'analyse statique comporte des avantages comme des inconvénients. Parmi les avantages, citons l'exhaustivité et le niveau de détail de la couverture, la confiance dans la conception du produit qu'une telle analyse formelle contribue à asseoir, et les rapports d'erreur précis qui rendent les bogues plus faciles à détecter et à résoudre. Cependant, pour traiter les bogues de simultanéité, l'analyse statique nécessite des intentions de spécification d'annotation conséquentes. En outre, ces annotations doivent en soi être correctes. Qui plus est, les outils qui utilisent l'analyse statique ont tendance à générer beaucoup faux positifs et à nécessiter un effort considérable pour réduire le nombre de ces faux positifs.
Dans l'analyse dynamique, les bogues sont détectés en examinant les traces de l'exécution. Il existe deux types d'analyse dynamique : en ligne et hors connexion. Les outils qui utilisent l'analyse dynamique en ligne analysent un programme pendant qu'il s'exécute. Les outils qui utilisent l'analyse dynamique hors connexion suivent et analysent les traces ultérieurement pour détecter les bogues. L'analyse dynamique est pratique car elle nécessite très peu, voire aucun, de travail supplémentaire de la part du développeur au moment du développement, génère moins de faux positifs et facilite la résolution des problèmes les plus évidents. Comme les bogues sont uniquement découverts dans le chemin d'exécution, les chemins les plus fréquemment parcourus génèrent le plus grand nombre de bogues. Ceci améliore la fiabilité à moindre coût.
Mais il existe également des inconvénients. Vous pouvez uniquement détecter les bogues dans le chemin d'exécution, et vous devez vous appuyer sur des scénarios de test pour une bonne couverture du code. En fait, certains outils peuvent uniquement repérer une concurrence si elle est survenue pendant l'exécution. Par conséquent, si l'outil ne signale pas de bogue, vous ne pouvez pas être certain qu'il n'en existe pas. La plupart des outils d'analyse dynamique reposent sur l'un ou l'autre instrument capable de modifier le comportement de l'exécution, ce qui constitue un autre inconvénient. En raison de leur complexité, les performances de ces outils ont tendance à être très faibles.
La dernière méthode est la vérification de modèle. Il s'agit de la méthode permettant de vérifier l'exactitude d'un système simultané à l'état fini. Elle permet un raisonnement déductif formel. Le vérificateur de modèle tente de simuler des conditions de concurrence et de blocage. La vérification de modèle vous permet de prouver formellement l'absence de concurrences et de blocages. Cette méthode permet d'asseoir la confiance dans la conception et l'architecture, fournit une couverture très élevée, et nécessite un nombre réduit de pilotes externes.
Néanmoins, à l'instar des autres méthodes de test, la vérification de modèle présente des inconvénients. Dans la plupart des cas, il est très difficile d'extraire automatiquement le modèle du code (il existe de rares cas d'utilisation limitée). L'extraction manuelle du modèle est également assez complexe. La quantité de vérifications est trop importante en raison de l'éclatement de l'espace d'état, une situation où le nombre potentiel d'états possibles est trop important pour être analysé. L'éclatement de l'espace d'état peut être contrôlé dans une certaine mesure en appliquant des techniques de réduction qui utilisent des heuristiques compliquées. Ces heuristiques peuvent elles aussi présenter des inconvénients, notamment l'impossibilité de détecter des bogues dans les applications à durée d'exécution prolongée.
Enfin, la vérification de modèle nécessite une conception et une planification de la mise en œuvre extrêmement rigoureuses. La vérification de modèle peut prouver que la conception ne comporte pas d'erreurs, mais sa mise en œuvre peut toujours être inexacte. Dans la pratique, la vérification de modèle est seulement utile pour des sections réduites et critiques d'un produit. D'autres techniques hybrides incluent l'association de l'analyse dynamique et de la vérification du modèle. CHESS en est un exemple, comme vous le verrez bientôt.
Algorithmes de détection des concurrences
L'algorithme de verrouillage, utilisé dans les outils d'analyse statique et dynamique, signale une concurrence potentielle lorsque deux threads ou plus accèdent à la mémoire partagée sans que les threads gèrent un verrou commun. Fondamentalement, l'algorithme indique que pour chaque variable de mémoire partagée v, un ensemble non vide de verrous C(v) sera posé par chaque thread pendant l'accès à la variable. Initialement, C (v) est la liste de tous les verrous. Chaque thread gère également deux ensembles de verrous : locks(t), indiquant tous les verrous posés et writeLocks(t), indiquant tous les verrous d'écriture posés. Voici comment fonctionne l'algorithme :
  1. Pour chaque variable v de mémoire partagée, gérer un ensemble C(v) de verrous. Initialement, C (v) est la liste de tous les verrous.
  2. Chaque thread gère également deux ensembles de verrous : locks(t), indiquant tous les verrous posés et writeLocks(t), indiquant tous les verrous d'écriture posés.
  3. À chaque lecture de v par le thread t :
    1. Définir C(v) = C(v) intersection locks(t).
    2. Si C(v) == NULL est défini, générer une erreur.
  4. À chaque lecture de v par le thread t :
    1. Définir C(v) = C(v) intersection writelocks(t).
    2. Si C(v) == NULL est défini, générer une erreur.
En fait, lorsque l'application progresse, C(v) de chaque variable commence à réduire. Une erreur est déclenchée si C(v) devient nul (par exemple, si l'intersection de l'ensemble de verrous des threads est NULL au moment de l'accès à la mémoire partagée).
Malheureusement, toutes les concurrences signalées par un algorithme de verrouillage ne sont pas de véritables concurrences. Il est possible d'écrire du code exempt de concurrences sans utiliser les verrous, soit en appliquant d'ingénieuses astuces de développement, soit en utilisant d'autres primitives de synchronisation telles que la signalisation. Ceci rend très difficile la détection des bogues authentiques. Les annotations et certaines suppressions peuvent contribuer à alléger ce problème.
L'algorithme happens-before (se produit avant) est un autre algorithme de détection des concurrences, qui repose sur un ordonnancement partiel des événements dans les systèmes distribués. Voici une présentation de l'algorithme qui calcule l'ordre partiel afin de déterminer les événements survenus avant un autre événement (les événements, dans ce contexte, sont toutes les instructions, y compris la lecture/écriture et les verrous) :
  • Dans un thread unique, les événements sont ordonnancés dans l'ordre dans lequel ils surviennent.
  • Parmi plusieurs threads, les événements sont ordonnancés en fonction des propriétés des primitives de synchronisation. Par exemple, si lock(a) est en cours d'acquisition par deux threads, le déverrouillage par un thread est considéré comme survenu avant le verrouillage d'un autre thread.
  • Si deux threads ou plus accèdent à une variable partagée, et que les accès ne sont pas ordonnancés de manière déterministe par la relation happens-before, on considère qu'une concurrence est survenue.
L'algorithme est illustré à la figure A.
Le déverrouillage du thread 1 est survenu avant le verrouillage du thread 2. Ainsi, l'accès à la variable partagée ne peut jamais se produire en même temps et il n'y a pas de concurrence. Le coût de la surveillance de telles relations constitue un inconvénient majeur de cet algorithme.
Plus globalement, le problème réside dans le fait que la capacité de cet algorithme à détecter les concurrences dépend totalement de l'ordre de planification. L'ordre partiel est uniquement prévu pour cette instance spécifique de la planification et peut manquer des bogues pour le même test s'il est effectué un jour différent. La figure B ne signale aucune concurrence, mais l'ordre d'exécution de la figure C fait état de concurrences. De nombreuses concurrences sont survenues plusieurs années seulement après la sortie d'un produit. Par conséquent, cette détection ne laisse pas une impression de couverture complète.
D'un autre côté, l'algorithme happens-before génère très peu de faux positifs. La plupart des bogues signalés sont réels. Cependant, happens-before ignore de nombreuses erreurs (faux négatifs) et est très difficile à implémenter efficacement.
Parallèlement à cela, l'algorithme de verrouillage est très efficace et peut détecter plus d'erreurs. Cependant, il a tendance à générer trop de faux positifs. Des efforts ont été mis en œuvre pour combiner ces algorithmes afin de surmonter les inconvénients des deux approches. Remarque : ces algorithmes de détection des concurrences ont évolué au cours de plusieurs années et vous trouverez les sources de ceux-ci en effectuant une recherche sur les portails de l'ACM/IEEE.
Figure A algorithme Happens-Before (Cliquez sur l'image pour l'agrandir)
Figure B Les concurrences ne seront pas signalées (Cliquez sur l'image pour l'agrandir)
Figure C Les concurrences seront signalées (Cliquez sur l'image pour l'agrandir)

Outils de test de simultanéité
Il existe plusieurs outils de test de simultanéité sur le marché pour vous aider à gérer blocages, les verrous actifs, les pannes et tout autre problème potentiel que vous pourriez rencontrer pendant l'exécution de transactions parallèles. Chaque outil que nous examinons ici vous aidera dans un domaine particulier.
CHESS Créé par Microsoft Research, CHESS est une combinaison originale de vérification de modèle et d'analyse dynamique (voir go.microsoft.com/fwlink/?LinkId=116523). Il détecte les erreurs de simultanéité en explorant systématiquement les planifications et les entrelacements de threads. Il est capable de détecter les conditions de concurrence, les blocages, les pannes, les verrouillages actifs et les problèmes d'altération des données. Pour faciliter le débogage, il fournit également une exécution entièrement répétable. Comme avec la plupart des vérifications de modèle, l'exploration systématique fournit une couverture détaillée.
En tant qu'outil d'analyse dynamique, CHESS exécute un test unitaire normal à plusieurs reprises sur un planificateur spécialisé. À chaque répétition, il choisit un ordre de planification différent. En tant que vérificateur de modèle, il contrôle le planificateur spécialisé qui est capable de créer des entrelacements de threads spécifiques. Pour contrôler l'éclatement de l'espace d'état, CHESS applique une réduction d'ordre partiel et une délimitation originale du contexte d'itération.
Lors de la délimitation du contexte d'itération, au lieu de limiter l'éclatement de l'espace d'état en fonction de la profondeur, CHESS limite le nombre de basculements de threads dans une exécution donnée. Le thread lui-même peut exécuter un nombre illimité d'étapes entre les basculements de thread, laissant ainsi la profondeur d'exécution sans limite (ce qui constitue un gros avantage par rapport à la vérification de modèle). Cette pratique repose sur la preuve empirique qu'un faible nombre de basculements de thread systématiques est suffisant pour exposer la plupart des bogues de simultanéité.
CHESS peut détecter les blocages et les concurrence (en utilisant l'algorithme de verrouillage de Goldilocks décrit à l'adresse go.microsoft.com/fwlink/?LinkId=116877) mais repose sur les assertions du programmeur pour les autres vérifications de l'état. Il s'attend également à ce que tous les programmes se terminent et à ce qu'il existe une garantie d'impartialité (progression en avant) pour tous les threads. Ainsi, si le programme entre dans un état de boucle continue, il signale un verrouillage actif.
S'agissant des tests, vous commenceriez par exécuter CHESS avec une limite du contexte d'itération de 2. Lorsque plus aucun bogue n'est détecté, la limite doit être augmentée à 3, et ainsi de suite. D'un point de vue empirique, la plupart des bogues devraient être détectés avec une limite de 2 et 3. Par conséquent, il peut s'agir d'une façon très efficace d'éliminer les bogues à un stade plus précoce.
Pour l'instrumentation, CHESS dévie les appels de synchronisation à l'API Win32® pour contrôler et introduire intentionnellement un non-déterminisme. De plus, il nécessite que le code de développeur inclue de nombreuses assertions afin de garantir la cohérence des états (ce qu'un bon code devrait de toute façon faire). Cependant, comme la plupart des outils d'analyse dynamique, il nécessite une bonne suite de tests pour une large couverture. CHESS est une bénédiction pour tous les développeurs et testeurs qui ne pouvaient s'appuyer que sur le test de contrainte pour de meilleurs tests entrelacés. Il utilise des tests unitaires normaux et simule méthodiquement des entrelacements intéressants.
Intel Thread Checker est un outil d'analyse dynamique pour la recherche des blocages (y compris les blocages potentiels), ses immobilismes, des concurrences de données et des utilisations incorrectes des API de synchronisation natives de Windows (voir go.microsoft.com/fwlink/?LinkId=115727). Thread Checker doit instrumenter le code source ou le fichier binaire compilé pour faire en sorte que toutes les références à la mémoire et toutes les primitives de synchronisation Win32 standard soient observables. Au moment de l'exécution, le fichier binaire instrumenté fournit des informations suffisantes pour que l'analyseur puisse mettre en place un ordre partiel d'exécution. L'outil effectue ensuite une analyse happens-before sur l'ordre partiel. Reportez-vous à l'encadré « Algorithmes de détection des concurrences » pour plus d'informations sur l'analyse happens-before.
Pour des raisons de performances et d'évolutivité, au lieu de se rappeler de tous les accès à une variable partagée, l'outil se rappelle uniquement des accès récents. Ceci contribue à améliorer l'efficacité de l'outil pendant l'analyse des applications à durée d'exécution prolongée. Cependant, l'effet secondaire est qu'il manquera certains bogues. Il s'agit d'un compromis et il est peut-être plus important de trouver un grand nombre de bogues dans les applications à durée d'exécution prolongée plutôt que de trouver tous les bogues dans les applications très courtes.
Le seul autre inconvénient majeur de l'outil réside dans le fait qu'il ne peut pas prendre en compte la synchronisation via des opérations à blocage, comme celles utilisées dans les verrous tournants (spinlocks). Cependant, pour les applications qui utilisent uniquement les primitives de synchronisation standard, il s'agit probablement de l'un des outils de test disponibles les mieux pris en charge pour le test de simultanéité d'applications natives.
RacerX Cet outil d'analyse statique sensible au flux est utilisé pour détecter les concurrences et les blocages. Il contourne la nécessité fastidieuse d'annoter l'intégralité du code source. En fait, la seule exigence d'annotation est que les utilisateurs fournissent un tableau spécifiant les API utilisées pour acquérir et libérer les verrous. Les attributs des primitives de verrouillage telles que rotation, blocage et réentrance peuvent également être spécifiés. Ce tableau sera généralement très petit, avec au plus 30 entrées. Ceci réduit considérablement le fardeau d'annotation du code source pour les grands systèmes.
Dans la première phase, RacerX parcourt chaque fichier de code source et génère un graphique de flux de contrôle (Control Flow Graph, CFG). Le CFG comporte les informations liées aux appels de fonctions, à la mémoire partagée, à l'utilisation des pointeurs et à d'autres données. Pendant qu'il crée le CFG, le programme fait également référence au tableau de primitives de synchronisation et marque les appels à ces API.
Une fois le CFG complet créé, la phase d'analyse démarre, qui inclut l'exécution du vérificateur de concurrence et du vérificateur de blocage. Parcourir le CFG peut être une longue opération, mais des techniques de réduction et de mise en cache sont utilisées pour réduire son impact. Pendant que le flux de contexte est parcouru, l'algorithme de verrouillage est utilisé pour repérer les concurrences potentielles (voir l'encadré « Algorithmes de détection des concurrences » pour plus de détails sur l'algorithme). Pour l'analyse des blocages, il calcule les cycles de verrouillage chaque fois que des verrous sont posés.
La dernière phase implique le post-traitement de toutes les erreurs signalées afin de les hiérarchiser par importance et nocivité d'erreur. Comme on pouvait s'y attendre avec l'analyse statique, les auteurs du programme ont passé beaucoup de temps à réduire les faux positifs afin de présenter les bogues avec un degré de confiance élevé. Les résultats de cet outil sont impressionnants et il semble très pratique du point de vue de l'ingénierie de test.
Chord Il s'agit d'un outil d'analyse statique pour Java, sensible au contexte et insensible au flux. Son insensibilité au flux lui permet d'être beaucoup plus évolutif que d'autres outils statiques, au prix toutefois d'une perte de précision. Il prend également en compte les primitives de synchronisation spécifiques disponibles dans Java. L'algorithme utilisé est très complexe et nécessiterait l'introduction de nombreux concepts. (Consultez go.microsoft.com/fwlink/?LinkId=116526 pour plus d'informations sur Chord)
KISS Développé par Microsoft Research, cet outil de vérification de modèle s'adresse aux programmes simultanés en C. Puisque l'espace d'état éclate rapidement dans un système simultané, KISS transforme un programme simultané en C en un programme séquentiel simulant l'exécution de l'entrelacement. Un vérificateur de modèle séquentiel est ensuite utilisé pour exécuter l'analyse.
L'application est instrumentée avec des instructions qui convertissent le programme simultané en un programme séquentiel, KISS assumant la responsabilité du contrôle du non-déterminisme. Le basculement de contexte non déterministe est limité par des principes similaires à ceux décrits ci-dessus dans CHESS. Le programmeur est censé introduire des assertions qui valident les suppositions de simultanéité. L'outil ne signale pas les faux positifs. Cet outil est un prototype de recherche et a été utilisé par l'équipe des pilotes Windows, qui utilise principalement du code en C (voir go.microsoft.com/fwlink/?LinkId=115723).
Zing Cet outil est un vérificateur de modèle pur prévu pour la vérification au moment de la conception des programmes simultanés. Zing possède son propre langage personnalisé, utilisé pour décrire des états et transitions complexes, et il est entièrement capable de modéliser des machines d'état simultanées. Comme les autres vérificateurs de modèle, Zing fournit une méthode complète pour la vérification des conceptions. Il contribue également à améliorer la confiance dans la conception car vous pouvez vérifier des suppositions et prouver formellement la présence ou l'absence de certaines conditions. Il lutte également contre l'éclatement d'espace d'état simultané grâce à des techniques de réduction innovantes.
Le modèle que Zing utilise (pour vérifier l'exactitude des programmes) doit être créé manuellement ou par des traducteurs. Bien que des traducteurs de domaines spécifiques puissent être écrits, nous n'avons toujours pas rencontré de traducteurs complets et réussis pour les applications CLR ou natives. Sans traducteurs, nous estimons que Zing ne peut pas être utilisé dans les projets logiciels de grande ampleur, sauf pour vérifier l'exactitude de sous-sections critiques du projet (voir go.microsoft.com/fwlink/?LinkId=115725).

Test de performances
Le test de performances constitue une partie intégrale et essentielle du processus de test de simultanéité. Après tout, l'une des motivations essentielles du développement d'applications parallèles est de fournir des performances supérieures par rapport aux applications séquentielles. Comme le postulent les lois d'Amdahl et de Gustafson, les gains de performances atteints par une application parallèle sont considérablement influencés par les aspects de capacité de parallélisme de son algorithme, la proportion d'éléments séquentiels du programme, la surcharge de parallélisme et les caractéristiques données/charge de travail. Le test de performances permet aux parties prenantes de comprendre et d'analyser les caractéristiques de performances des applications parallèles.
La méthodologie générale pour le test de performances des applications parallèles est identique à celle du test de performances des applications séquentielles. La section suivante décrit comment certaines des étapes essentielles du test de performances doivent être adaptées pour les applications simultanées. Pour comprendre les facteurs les plus utiles à mesurer, consultez l'encadré « Identification des données de test et des mesures à utiliser pour la création de rapports ».
L'étape la plus importante du test de performances est la définition des objectifs ou du but du test. Pour les applications parallèles, les objectifs de test valides incluent la compréhension de la capacité de parallélisme/évolutivité de l'algorithme utilisé, la compréhension des caractéristiques de performances de diverses alternatives de conception, la découverte des surcharges de synchronisation et de communication, et la vérification que les exigences de performances sont atteintes.
Il est important de noter que l'objectif et l'étendue du test de performances peuvent également varier en fonction du responsable du test. Par exemple, les clients déployant une application parallèle effectueront un test des performances afin de s'assurer que les besoins de l'entreprise sont satisfaits, tandis que l'équipe de développement sera intéressée par un test de performances approfondi pour identifier les goulots d'étranglement et améliorer la capacité de parallélisme du programme. Qui plus est, les objectifs de test peuvent varier durant le cycle de développement du logiciel. Pendant la phase de conception et d'implémentation, l'objectif du test pourrait être de comprendre et d'améliorer les caractéristiques des performances de l'application, tandis que pendant les phases de test et de publication (phases de stabilisation), il pourrait être de garantir que les performances ne régressent pas d'une génération à l'autre.
La définition des scénarios de test et de leurs objectifs est une autre étape importante du processus de test de performances. Les équipes de développement souhaitant comprendre les caractéristiques de performances d'une application parallèle doivent définir trois types de scénario de test : les tests d'indicateurs de performance clé (KPI) et les micro-tests d'évaluation (MBM).
Les relations entre ces différents types de test de performances peuvent être considérées comme équivalentes à ce qui existe entre les tests de système, les tests d'intégration et les tests unitaires. En d'autres termes, un test de scénario de client génère un ensemble de tests KPI et un test KPI génère un ensemble de tests MBM. La compréhension de la relation entre ces différents types de test permet aux développeurs de comprendre les relations de performances entre les diverses sous-parties d'une application parallèle. L'acquisition de cette compréhension permet également une meilleure hiérarchisation des bogues de performances et, plus important encore, permet à l'équipe de développement de répondre aux plaintes des clients concernant les performances par des suggestions orientées vers le résultat.
La définition d'objectifs de performances pour les applications un tant soit peu spécialisées est difficile, sans parler des applications parallèles. L'une des approches de la définition des objectifs consiste à dériver l'objectif en triangulant les mesures obtenues d'après les mesures de performances algorithmiques ou théoriques prévues pour chaque composant et sous-composant de l'application, d'après l'analyse comparative (les candidats pour la comparaison incluent les applications similaires de concurrents) et d'après le profilage de l'implémentation/application existante (si elles existent).
Comme pour les objectifs de test, chaque scénario de test doit définir un ensemble de critères d'acceptation (un ensemble de valeurs validant les résultats de test). Pour les scénarios de test parallèle, les variables suivantes peuvent être utilisées comme critères d'acceptation.
Un écart dans les résultats Ceci est signe d'une application instable. L'écart dans les résultats de test peut être compris en calculant la déviation standard des résultats.
Utilisation du processeur Une utilisation de processeur faible peut être un signe de bogues de simultanéité tels que des blocages ou des surcharges de synchronisation. À l'inverse, une utilisation élevée de processeur n'indique pas nécessairement une réussite, car les verrous actifs entraînent souvent une utilisation élevée du processeur.
Nettoyages de la mémoire Pour les applications gérées, un nombre trop important d'opérations de gestion de la mémoire peut freiner la véritable exécution des tâches et peut indiquer une conception ou une mise en œuvre défectueuses.
Temps total d'exécution des threads Ceci vous permet d'effectuer une approximation du temps total d'exécution si le programme doit être exécuté de façon séquentielle. La comparaison du temps total d'exécution des threads au temps de mise en œuvre séquentielle écoulé du même programme d'algorithme est une façon de comprendre les surcharges générales de parallélisme (et de noter si le test est valide).
Utilisation totale de la mémoire La mesure de l'utilisation totale de la mémoire peut être utile pour la compréhension du profil de mémoire de l'application. Pour les applications gérées, le Garbage Collector joue un rôle significatif dans la modification de l'utilisation de la mémoire totale de l'application et doit être pris en considération pendant l'évaluation de l'utilisation de la mémoire.
Avant que vous ne commenciez le test des performances, il existe trois étapes importantes que vous devez suivre pour garantir des résultats plus pertinents. Premièrement, minimiser l'écart dans l'environnement de test (un écart peut être introduit par l'application ou par l'environnement de test). Les écarts dans l'environnement de test peuvent être réduits en arrêtant des services et des applications et en réduisant les interférences réseau. L'écart causé par l'application peut être réduit en exécutant des itérations de préparation et en recueillant les mesures de plusieurs itérations multiples du test.
Deuxièmement, pour les applications gérées, l'exécution prématurée du Garbage Collector peut invalider les résultats de performances. Par conséquent, vous devez réduire le risque d'invocation du Garbage Collector pendant les mesures de performances en invoquant de force le nettoyage de la mémoire avant ou après avoir recueilli les mesures et/ou modifié GCLatencyMode en LowLatency (ceci est uniquement vrai avec Microsoft® .NET Framework 3.5).
Troisièmement, effectuez toujours un préchauffage avant de recueillir les mesures. Le préchauffage par l'exécution du test une première fois avant de recueillir les mesures permet d'éliminer les coûts uniques tels que l'initialisation des variables, le coût de compilation juste-à-temps (dans les applications gérées) et la latence initiale des échecs de cache. Notez qu'en fonction des scénarios de performances, il pourrait également être important de mesurer les performances de démarrage à froid. (Pour plus d'informations sur l'amélioration des performances de démarrage des applications, consultez l'article msdn2.microsoft.com/magazine/cc337892.aspx.)
Lectures supplémentaires sur les tests de simultanéité

Utilisation de la synchronisation

Bugslayer : Wait Chain Traversal

Plus de blocages : Techniques avancées permettant d'éviter et de détecter les blocages dans les applications .NET

ReadWriteBarrier (C++)

Ordonnancement en mémoire de l'architecture Intel 64

Synchronisation et problèmes liés aux multiprocesseurs

PreFast étape par étape

Test d'applications avec AppVerifier

Conseils sur les tests de performances pour les applications Web

Test de contrainte
Le test de contrainte de logiciel fait souvent référence au test de l'application en termes de robustesse, de disponibilité et de propreté de la gestion des erreurs. La robustesse est habituellement testée en invoquant à plusieurs reprises les mêmes fonctionnalités ou la même combinaison de fonctionnalités et en s'assurant de l'exactitude de l'exécution. La disponibilité est testée en exécutant l'application dans des conditions de ressources difficiles, par exemple avec une mémoire réduite ou une charge de processeur élevée, et en s'assurant que l'application ne se bloque pas ou qu'elle échoue proprement. La propreté de la gestion d'erreurs est souvent testée en introduisant des erreurs (injection d'erreur) ou en déclenchant des erreurs multiples.
Lors du test de contrainte d'applications simultanées, une plus grande importance doit être accordée au test de la robustesse et de la disponibilité de l'application. En raison du comportement non déterministe des applications parallèles, l'invocation à plusieurs reprises de la même fonctionnalité ou combinaison de fonctionnalités pourrait générer des chemins d'accès au code différents, ce qui pourrait à son tour se traduire par un plus grand nombre de bogues découverts. Qui plus est, le test de disponibilité sous des conditions de ressources difficiles (telles que la création de nombreux threads ou de threads multiples entrant en situation de blocage/verrouillage actif) est particulièrement important puisque la probabilité qu'un client rencontrera de tels scénarios est relativement élevée pour les applications parallèles.
Il est important de noter qu'il est extrêmement difficile d'analyser la raison initiale des bogues de simultanéité liés à la contrainte et de reproduire ces bogues de façon systématique. Cependant, comme les outils de test de simultanéité sont nouveaux, le test de contrainte est un supplément très important pour le test fonctionnel.

Conclusion
Pour profiter véritablement de toute la puissance que l'informatique parallèle peut offrir, il est impératif de faire évoluer les pratiques de développement de logiciel actuelles qui ont été créées pour développer et tester des applications séquentielles. Il est difficile de développer et de tester des applications simultanées en raison d'une nouvelle classe de bogues introduite par le parallélisme. Cet article a présenté les divers types de bogues simultanés, les stratégies de recherche de bogues simultanés et a expliqué comment adapter le test de performances aux scénarios simultanés.

Rahul V. Patil est Responsable de conception et de test de logiciels au sein de l'équipe Parallel Computing Platform de Microsoft et dirige les efforts de test avec l'infrastructure de simultanéité native.

Boby George est également Responsable de conception et de test de logiciels au sein de l'équipe Parallel Computing Platform de Microsoft et responsable des efforts de test des performances avec l'infrastructure d'informatique parallèle gérée.

Page view tracker