Partager via

Considérations sur la programmation sans verrou pour Xbox 360 et Microsoft Windows

  • Article

La programmation sans verrou est une méthode permettant de partager en toute sécurité des données changeantes entre plusieurs threads sans le coût d’acquisition et de libération des verrous. Cela semble être une panacée, mais la programmation sans verrou est complexe et subtile, et parfois ne donne pas les avantages qu’elle promet. La programmation sans verrou est particulièrement complexe sur Xbox 360.

La programmation sans verrou est une technique valide pour la programmation multithread, mais elle ne doit pas être utilisée à la légère. Avant de l’utiliser, vous devez comprendre les complexités, et vous devez mesurer soigneusement pour vous assurer qu’elle vous apporte réellement les gains que vous attendez. Dans de nombreux cas, il existe des solutions plus simples et plus rapides, comme partager les données moins fréquemment, qui devraient être utilisées à la place.

Utiliser correctement et en toute sécurité la programmation sans verrou nécessite une connaissance approfondie de votre matériel et de votre compilateur. Cet article donne un aperçu de certaines des questions à considérer lorsqu’on essaie d’utiliser des techniques de programmation sans verrou.

Programmation avec verrous

Lors de l’écriture de code multithread, il est souvent nécessaire de partager des données entre les threads. Si plusieurs threads lisent et écrivent simultanément les structures de données partagées, une corruption de mémoire peut se produire. La manière la plus simple de résoudre ce problème est d’utiliser des verrous. Par exemple, si ManipulateSharedData doit être exécuté par un seul thread à la fois, une CRITICAL_SECTION peut être utilisée pour garantir cela, comme dans le code suivant :

// Initialize
CRITICAL_SECTION cs;
InitializeCriticalSection(&cs);

// Use
void ManipulateSharedData()
{
    EnterCriticalSection(&cs);
    // Manipulate stuff...
    LeaveCriticalSection(&cs);
}

// Destroy
DeleteCriticalSection(&cs);

Ce code est assez simple et direct, et il est facile de voir qu’il est correct. Cependant, la programmation avec des verrous présente plusieurs inconvénients potentiels. Par exemple, si deux threads essaient d’acquérir les mêmes deux verrous mais dans un ordre différent, vous pouvez obtenir un interblocage. Si un programme détient un verrou trop longtemps — en raison d’une mauvaise conception ou parce que le thread a été remplacé par un thread de priorité supérieure — d’autres threads peuvent être bloqués pendant longtemps. Ce risque est particulièrement grand sur Xbox 360 car les threads logiciels sont assignés à un thread matériel par le développeur, et le système d’exploitation ne les déplacera pas vers un autre thread matériel, même si l’un est inactif. La Xbox 360 n’a également aucune protection contre l’inversion de priorité, où un thread de haute priorité tourne en boucle en attendant qu’un thread de basse priorité libère un verrou. Enfin, si un appel de procédure différé ou une routine de service d’interruption essaie d’acquérir un verrou, vous pouvez obtenir un interblocage.

Malgré ces problèmes, les primitives de synchronisation, telles que les sections critiques, sont généralement le meilleur moyen de coordonner plusieurs threads. Si les primitives de synchronisation sont trop lentes, la meilleure solution est généralement de les utiliser moins fréquemment. Cependant, pour ceux qui peuvent se permettre une complexité supplémentaire, une autre option est la programmation sans verrou.

Programmation sans verrou

La programmation sans verrou, comme son nom l’indique, est une famille de techniques pour manipuler en toute sécurité des données partagées sans utiliser de verrous. Il existe des algorithmes sans verrou disponibles pour passer des messages, partager des listes et des files d’attente de données, et d’autres tâches.

Lors de la programmation sans verrou, il y a deux défis à relever : les opérations non atomiques et le réordonnancement.

Opérations non atomiques

Une opération atomique est une opération indivisible — une opération où d’autres threads sont garantis de ne jamais voir l’opération lorsqu’elle est à moitié terminée. Les opérations atomiques sont importantes pour la programmation sans verrou, car sans elles, d’autres threads pourraient voir des valeurs à moitié écrites ou un état incohérent.

Sur tous les processeurs modernes, vous pouvez supposer que les lectures et les écritures de types natifs naturellement alignés sont atomiques. Tant que le bus mémoire est au moins aussi large que le type lu ou écrit, le CPU lit et écrit ces types en une seule transaction de bus, rendant impossible pour d’autres threads de les voir dans un état à moitié complété. Sur x86 et x64, il n’y a aucune garantie que les lectures et écritures de plus de huit octets soient atomiques. Cela signifie que les lectures et écritures de 16 octets des registres de l’extension SIMD en streaming (SSE) et des opérations sur des chaînes peuvent ne pas être atomiques.

Les lectures et écritures de types qui ne sont pas naturellement alignés, par exemple écrire des DWORDs qui traversent des frontières de quatre octets, ne sont pas garanties d’être atomiques. Le CPU peut devoir faire ces lectures et écritures comme plusieurs transactions de bus, ce qui pourrait permettre à un autre thread de modifier ou de voir les données au milieu de la lecture ou de l’écriture.

Les opérations composites, telles que la séquence de lecture-modification-écriture qui se produit lorsque vous incrémentez une variable partagée, ne sont pas atomiques. Sur Xbox 360, ces opérations sont implémentées comme plusieurs instructions (lwz, addi, et stw), et le thread pourrait être remplacé au milieu de la séquence. Sur x86 et x64, il existe une seule instruction (inc) qui peut être utilisée pour incrémenter une variable en mémoire. Si vous utilisez cette instruction, incrémenter une variable est atomique sur les systèmes à processeur unique, mais ce n’est toujours pas atomique sur les systèmes multiprocesseurs. Rendre inc atomique sur les systèmes multiprocesseurs basés sur x86 et x64 nécessite d’utiliser le préfixe lock, qui empêche un autre processeur de faire sa propre séquence de lecture-modification-écriture entre la lecture et l’écriture de l’instruction inc.

Le code suivant montre des exemples :

// This write is not atomic because it is not natively aligned.
DWORD* pData = (DWORD*)(pChar + 1);
*pData = 0;

// This is not atomic because it is three separate operations.
++g_globalCounter;

// This write is atomic.
g_alignedGlobal = 0;

// This read is atomic.
DWORD local = g_alignedGlobal;

Garantir l’Atomicité

Vous pouvez vous assurer d’utiliser des opérations atomiques en combinant les éléments suivants :

  • Opérations naturellement atomiques
  • Verrous pour envelopper les opérations composites
  • Fonctions du système d’exploitation qui implémentent des versions atomiques des opérations composites populaires

Incrémenter une variable n’est pas une opération atomique, et l’incrémentation peut entraîner une corruption de données si elle est exécutée sur plusieurs threads.

// This will be atomic.
g_globalCounter = 0;

// This is not atomic and gives undefined behavior
// if executed on multiple threads
++g_globalCounter;

Win32 est livré avec une famille de fonctions qui offrent des versions atomiques de lecture-modification-écriture de plusieurs opérations courantes. Ce sont les fonctions de la famille InterlockedXxx. Si toutes les modifications de la variable partagée utilisent ces fonctions, les modifications seront sûres pour les threads.

// Incrementing our variable in a safe lockless way.
InterlockedIncrement(&g_globalCounter);

Réordonnancement

Un problème plus subtil est le réordonnancement. Les lectures et les écritures ne se produisent pas toujours dans l’ordre dans lequel vous les avez écrites dans votre code, et cela peut entraîner des problèmes très déroutants. Dans de nombreux algorithmes multithread, un thread écrit des données puis écrit sur un indicateur qui informe les autres threads que les données sont prêtes. Ceci est connu sous le nom d’écriture-libération. Si les écritures sont réordonnées, d’autres threads peuvent voir que l’indicateur est réglé avant de pouvoir voir les données écrites.

De même, dans de nombreux cas, un thread lit un indicateur puis lit des données partagées si l’indicateur indique que le thread a acquis l’accès aux données partagées. Ceci est connu sous le nom de lecture-acquisition. Si les lectures sont réorganisées, les données peuvent être lues à partir du stockage partagé avant l’indicateur, et les valeurs observées pourraient ne pas être à jour.

La réorganisation des lectures et des écritures peut être effectuée à la fois par le compilateur et par le processeur. Les compilateurs et les processeurs effectuent cette réorganisation depuis des années, mais sur les machines monoprocesseur, c’était moins problématique. Cela s’explique par le fait que la réorganisation des lectures et des écritures par le CPU est invisible sur les machines monoprocesseur (pour le code non pilote qui ne fait pas partie d’un pilote), et la réorganisation des lectures et des écritures par le compilateur est moins susceptible de causer des problèmes sur les machines monoprocesseur.

Si le compilateur ou le CPU réorganise les écritures montrées dans le code suivant, un autre thread peut voir que l’indicateur « alive » est défini tout en voyant encore les anciennes valeurs de x ou y. Une réorganisation similaire peut se produire lors de la lecture.

Dans ce code, un thread ajoute une nouvelle entrée au tableau des sprites :

// Create a new sprite by writing its position into an empty
// entry and then setting the 'alive' flag. If 'alive' is
// written before x or y then errors may occur.
g_sprites[nextSprite].x = x;
g_sprites[nextSprite].y = y;
g_sprites[nextSprite].alive = true;

Dans ce bloc de code suivant, un autre thread lit à partir du tableau des sprites :

// Draw all sprites. If the reads of x and y are moved ahead of
// the read of 'alive' then errors may occur.
for( int i = 0; i < numSprites; ++i )
{
    if( g_sprites[nextSprite].alive )
    {
        DrawSprite( g_sprites[nextSprite].x,
                g_sprites[nextSprite].y );
    }
}

Pour sécuriser ce système de sprites, nous devons empêcher la réorganisation des lectures et des écritures par le compilateur et le CPU.

Comprendre la réorganisation des écritures par le CPU

Certains CPU réorganisent les écritures de manière à ce qu’elles soient visibles de l’extérieur par d’autres processeurs ou dispositifs dans un ordre non programmé. Cette réorganisation n’est jamais visible pour le code non pilote monothread, mais elle peut causer des problèmes dans le code multithread.

Xbox 360

Alors que le CPU de la Xbox 360 ne réorganise pas les instructions, il réorganise les opérations d’écriture, qui se terminent après les instructions elles-mêmes. Cette réorganisation des écritures est spécifiquement autorisée par le modèle de mémoire PowerPC.

Les écritures sur la Xbox 360 ne vont pas directement dans le cache L2. Au lieu de cela, pour améliorer la bande passante d’écriture du cache L2, elles passent par des files d’attente de stockage puis par des tampons de rassemblement de stockage. Les tampons de rassemblement de stockage permettent d’écrire des blocs de 64 octets dans le cache L2 en une seule opération. Il y a huit tampons de rassemblement de stockage, ce qui permet d’écrire efficacement dans plusieurs zones de mémoire différentes.

Les tampons de rassemblement de stockage sont normalement écrits dans le cache L2 dans l’ordre premier entré, premier sorti (FIFO). Cependant, si la ligne de cache cible d’une écriture n’est pas dans le cache L2, cette écriture peut être retardée pendant que la ligne de cache est récupérée de la mémoire.

Même lorsque les tampons de rassemblement de stockage sont écrits dans le cache L2 dans un ordre strictement FIFO, cela ne garantit pas que les écritures individuelles sont écrites dans le cache L2 dans l’ordre. Par exemple, imaginez que le CPU écrit à l’emplacement 0x1000, puis à l’emplacement 0x2000, puis à l’emplacement 0x1004. La première écriture alloue un tampon de rassemblement de stockage et le place en tête de la file d’attente. La deuxième écriture alloue un autre tampon de rassemblement de stockage et le place ensuite dans la file d’attente. La troisième écriture ajoute ses données au premier tampon de rassemblement de stockage, qui reste en tête de la file d’attente. Ainsi, la troisième écriture finit par aller dans le cache L2 avant la deuxième écriture.

La réorganisation causée par les tampons de rassemblement de stockage est fondamentalement imprévisible, d’autant plus que les deux threads sur un cœur partagent les tampons de rassemblement de stockage, rendant l’allocation et la vidange des tampons de rassemblement de stockage très variables.

Ceci est un exemple de la manière dont les écritures peuvent être réorganisées. Il peut y avoir d’autres possibilités.

x86 et x64

Même si les CPU x86 et x64 réorganisent les instructions, ils ne réorganisent généralement pas les opérations d’écriture par rapport aux autres écritures. Il y a quelques exceptions pour la mémoire combinée en écriture. De plus, les opérations sur les chaînes (MOVS et STOS) et les écritures SSE de 16 octets peuvent être réorganisées en interne, mais sinon, les écritures ne sont pas réorganisées les unes par rapport aux autres.

Comprendre la réorganisation des lectures par le CPU

Certains CPU réorganisent les lectures de manière à ce qu’elles proviennent effectivement du stockage partagé dans un ordre non programmé. Cette réorganisation n’est jamais visible pour le code non pilote monothread, mais peut causer des problèmes dans le code multithread.

Xbox 360

Les manques de cache peuvent entraîner des retards dans certaines lectures, ce qui entraîne effectivement des lectures provenant de la mémoire partagée dans un ordre incorrect, et le timing de ces manques de cache est fondamentalement imprévisible. Le préchargement et la prédiction de branchement peuvent également entraîner des données provenant de la mémoire partagée dans un ordre incorrect. Ce ne sont que quelques exemples de la manière dont les lectures peuvent être réorganisées. Il peut y avoir d’autres possibilités. Cette réorganisation des lectures est spécifiquement autorisée par le modèle de mémoire PowerPC.

x86 et x64

Même si les CPU x86 et x64 réorganisent les instructions, ils ne réorganisent généralement pas les opérations de lecture par rapport aux autres lectures. Les opérations sur les chaînes (MOVS et STOS) et les lectures SSE de 16 octets peuvent être réorganisées en interne, mais sinon, les lectures ne sont pas réorganisées les unes par rapport aux autres.

Autres réorganisations

Même si les CPU x86 et x64 ne réorganisent pas les écritures par rapport aux autres écritures, ni ne réorganisent les lectures par rapport aux autres lectures, ils peuvent réorganiser les lectures par rapport aux écritures. Plus précisément, si un programme écrit à un emplacement puis lit à partir d’un autre emplacement, les données lues peuvent provenir de la mémoire partagée avant que les données écrites ne s’y rendent. Cette réorganisation peut casser certains algorithmes, comme les algorithmes d’exclusion mutuelle de Dekker. Dans l’algorithme de Dekker, chaque thread définit un indicateur pour indiquer qu’il veut entrer dans la région critique, puis vérifie l’indicateur de l’autre thread pour voir si l’autre thread est dans la région critique ou essaie d’y entrer. Le code initial est le suivant.

volatile bool f0 = false;
volatile bool f1 = false;

void P0Acquire()
{
    // Indicate intention to enter critical region
    f0 = true;
    // Check for other thread in or entering critical region
    while (f1)
    {
        // Handle contention.
    }
    // critical region
    ...
}


void P1Acquire()
{
    // Indicate intention to enter critical region
    f1 = true;
    // Check for other thread in or entering critical region
    while (f0)
    {
        // Handle contention.
    }
    // critical region
    ...
}

Le problème est que la lecture de f1 dans P0Acquire peut lire à partir du stockage partagé avant que l’écriture de f0 ne parvienne au stockage partagé. Pendant ce temps, la lecture de f0 dans P1Acquire peut lire à partir du stockage partagé avant que l’écriture de f1 ne parvienne au stockage partagé. L’effet net est que les deux threads définissent leurs indicateurs sur TRUE, et les deux threads voient l’indicateur de l’autre thread comme étant FALSE, donc ils entrent tous deux dans la région critique. Par conséquent, bien que les problèmes de réorganisation sur les systèmes basés sur x86 et x64 soient moins courants que sur Xbox 360, ils peuvent encore se produire. L’algorithme de Dekker ne fonctionnera pas sans barrières de mémoire matérielles sur aucune de ces plateformes.

Les CPU x86 et x64 ne réorganiseront pas une écriture avant une lecture précédente. Les CPU x86 et x64 ne réorganisent les lectures avant les écritures précédentes que si elles ciblent des emplacements différents.

Les CPU PowerPC peuvent réorganiser les lectures avant les écritures, et peuvent réorganiser les écritures avant les lectures, tant qu’elles concernent des adresses différentes.

Résumé de la réorganisation

Le CPU de la Xbox 360 réorganise les opérations de mémoire beaucoup plus agressivement que les CPU x86 et x64, comme indiqué dans le tableau suivant. Pour plus de détails, veuillez consulter la documentation du processeur.

Activité de réorganisation x86 et x64 Xbox 360
Lectures se déplaçant avant les lectures Non Oui
Écritures se déplaçant avant les écritures Non Oui
Écritures se déplaçant avant les lectures Non Oui
Lectures se déplaçant avant les écritures Oui Oui

 

Barrières Read-Acquire et Write-Release

Les principaux mécanismes utilisés pour empêcher le réarrangement des lectures et écritures sont appelés barrières d’acquisition en lecture et de libération en écriture. Une acquisition en lecture est une lecture d’un indicateur ou d’une autre variable pour obtenir la possession d’une ressource, accompagnée d’une barrière contre le réarrangement. De même, une libération en écriture est une écriture d’un indicateur ou d’une autre variable pour céder la possession d’une ressource, accompagnée d’une barrière contre le réarrangement.

Les définitions formelles, fournies par Herb Sutter, sont :

  • Une acquisition en lecture s’exécute avant toutes les lectures et écritures par le même thread qui la suivent dans l’ordre du programme.
  • Une libération en écriture s’exécute après toutes les lectures et écritures par le même thread qui la précèdent dans l’ordre du programme.

Lorsque votre code acquiert la possession d’une mémoire, soit en acquérant un verrou, soit en retirant un élément d’une liste chaînée partagée (sans verrou), il y a toujours une lecture impliquée - tester un indicateur ou un pointeur pour voir si la possession de la mémoire a été acquise. Cette lecture peut faire partie d’une opération InterlockedXxx, auquel cas elle implique à la fois une lecture et une écriture, mais c’est la lecture qui indique si la possession a été acquise. Après avoir acquis la possession de la mémoire, des valeurs sont généralement lues ou écrites dans cette mémoire, et il est très important que ces lectures et écritures s’exécutent après l’acquisition de la possession. Une barrière d’acquisition en lecture garantit cela.

Lorsque la possession d’une mémoire est libérée, soit en libérant un verrou, soit en poussant un élément dans une liste chaînée partagée, il y a toujours une écriture impliquée qui notifie les autres threads que la mémoire est maintenant disponible pour eux. Pendant que votre code avait la possession de la mémoire, il a probablement lu ou écrit dedans, et il est très important que ces lectures et écritures s’exécutent avant de libérer la possession. Une barrière de libération en écriture garantit cela.

Il est plus simple de considérer les barrières d’acquisition en lecture et de libération en écriture comme des opérations uniques. Cependant, elles doivent parfois être construites à partir de deux parties : une lecture ou une écriture et une barrière qui ne permet pas aux lectures ou écritures de la traverser. Dans ce cas, le placement de la barrière est crucial. Pour une barrière d’acquisition en lecture, la lecture de l’indicateur vient d’abord, puis la barrière, puis les lectures et écritures des données partagées. Pour une barrière de libération en écriture, les lectures et écritures des données partagées viennent d’abord, puis la barrière, puis l’écriture de l’indicateur.

// Read that acquires the data.
if( g_flag )
{
    // Guarantee that the read of the flag executes before
    // all reads and writes that follow in program order.
    BarrierOfSomeSort();

    // Now we can read and write the shared data.
    int localVariable = sharedData.y;
    sharedData.x = 0;

    // Guarantee that the write to the flag executes after all
    // reads and writes that precede it in program order.
    BarrierOfSomeSort();
    
    // Write that releases the data.
    g_flag = false;
}

La seule différence entre une acquisition en lecture et une libération en écriture est l’emplacement de la barrière mémoire. Une acquisition en lecture place la barrière après l’opération de verrouillage, et une libération en écriture place la barrière avant. Dans les deux cas, la barrière se trouve entre les références à la mémoire verrouillée et les références au verrou.

Pour comprendre pourquoi les barrières sont nécessaires à la fois lors de l’acquisition et de la libération des données, il est préférable (et plus précis) de penser à ces barrières comme garantissant la synchronisation avec la mémoire partagée, et non avec d’autres processeurs. Si un processeur utilise une libération en écriture pour libérer une structure de données vers la mémoire partagée, et un autre processeur utilise une acquisition en lecture pour accéder à cette structure de données à partir de la mémoire partagée, le code fonctionnera correctement. Si l’un des processeurs n’utilise pas la barrière appropriée, le partage de données peut échouer.

Utiliser la bonne barrière pour empêcher le réarrangement par le compilateur et le CPU pour votre plateforme est crucial.

Un des avantages d’utiliser les primitives de synchronisation fournies par le système d’exploitation est qu’elles incluent toutes les barrières mémoire appropriées.

Prévention du réarrangement par le compilateur

Le travail d’un compilateur est d’optimiser agressivement votre code afin d’améliorer les performances. Cela inclut le réarrangement des instructions partout où c’est utile et où cela ne change pas le comportement. Parce que la norme C++ ne mentionne jamais le multithreading, et parce que le compilateur ne sait pas quel code doit être thread-safe, le compilateur suppose que votre code est monothread lorsqu’il décide quels réarrangements il peut faire en toute sécurité. Par conséquent, vous devez dire au compilateur quand il n’est pas autorisé à réorganiser les lectures et écritures.

Avec Visual C++, vous pouvez empêcher le réarrangement par le compilateur en utilisant l’intrinsèque du compilateur _ReadWriteBarrier. Là où vous insérez _ReadWriteBarrier dans votre code, le compilateur ne déplacera pas les lectures et écritures à travers lui.

#if _MSC_VER < 1400
    // With VC++ 2003 you need to declare _ReadWriteBarrier
    extern "C" void _ReadWriteBarrier();
#else
    // With VC++ 2005 you can get the declaration from intrin.h
#include <intrin.h>
#endif
// Tell the compiler that this is an intrinsic, not a function.
#pragma intrinsic(_ReadWriteBarrier)

// Create a new sprite by filling in a previously empty entry.
g_sprites[nextSprite].x = x;
g_sprites[nextSprite].y = y;
// Write-release, barrier followed by write.
// Guarantee that the compiler leaves the write to the flag
// after all reads and writes that precede it in program order.
_ReadWriteBarrier();
g_sprites[nextSprite].alive = true;

Dans le code suivant, un autre thread lit dans le tableau sprite :

// Draw all sprites.
for( int i = 0; i < numSprites; ++i )
{

    // Read-acquire, read followed by barrier.
    if( g_sprites[nextSprite].alive )
    {
    
        // Guarantee that the compiler leaves the read of the flag
        // before all reads and writes that follow in program order.
        _ReadWriteBarrier();
        DrawSprite( g_sprites[nextSprite].x,
                g_sprites[nextSprite].y );
    }
}

Il est important de comprendre que _ReadWriteBarrier n’insère aucune instruction supplémentaire, et il n’empêche pas le CPU de réorganiser les lectures et écritures - il empêche seulement le compilateur de les réorganiser. Ainsi, _ReadWriteBarrier est suffisant lorsque vous implémentez une barrière de libération en écriture sur x86 et x64 (car x86 et x64 ne réorganisent pas les écritures, et une écriture normale est suffisante pour libérer un verrou), mais dans la plupart des autres cas, il est également nécessaire d’empêcher le CPU de réorganiser les lectures et écritures.

Vous pouvez également utiliser _ReadWriteBarrier lorsque vous écrivez dans une mémoire non-cacheable combinée en écriture pour empêcher la réorganisation des écritures. Dans ce cas, _ReadWriteBarrier aide à améliorer les performances, en garantissant que les écritures se produisent dans l’ordre linéaire préféré du processeur.

Il est également possible d’utiliser les intrinsèques _ReadBarrier et _WriteBarrier pour un contrôle plus précis du réarrangement par le compilateur. Le compilateur ne déplacera pas les lectures à travers une _ReadBarrier, et il ne déplacera pas les écritures à travers une _WriteBarrier.

Prévention du réarrangement par le CPU

Le réarrangement par le CPU est plus subtil que le réarrangement par le compilateur. Vous ne pouvez jamais le voir se produire directement, vous ne voyez que des bugs inexplicables. Afin d’empêcher le réarrangement par le CPU des lectures et écritures, vous devez utiliser des instructions de barrière mémoire, sur certains processeurs. Le nom général pour une instruction de barrière mémoire, sur Xbox 360 et sur Windows, est MemoryBarrier. Cette macro est implémentée de manière appropriée pour chaque plateforme.

Sur Xbox 360, MemoryBarrier est défini comme lwsync (synchronisation légère), également disponible via l’intrinsèque __lwsync, qui est défini dans ppcintrinsics.h. __lwsync sert également de barrière mémoire pour le compilateur, empêchant la réorganisation des lectures et écritures par le compilateur.

L’instruction lwsync est une barrière mémoire sur Xbox 360 qui synchronise un cœur de processeur avec le cache L2. Elle garantit que toutes les écritures avant lwsync atteignent le cache L2 avant toute écriture qui suit. Elle garantit également que toutes les lectures qui suivent lwsync ne récupèrent pas des données plus anciennes du cache L2 que les lectures précédentes. Le seul type de réarrangement qu’elle ne prévient pas est une lecture se déplaçant avant une écriture à une adresse différente. Ainsi, lwsync impose un ordre mémoire qui correspond à l’ordre mémoire par défaut sur les processeurs x86 et x64. Pour obtenir un ordre mémoire complet, il faut l’instruction de synchronisation plus coûteuse (également connue sous le nom de synchronisation lourde), mais dans la plupart des cas, cela n’est pas nécessaire. Les options de réarrangement mémoire sur Xbox 360 sont montrées dans le tableau suivant.

Réarrangement Xbox 360 Pas de synchronisation lwsync synchronisation
Lectures se déplaçant avant les lectures Oui No Non
Écritures se déplaçant avant les écritures Oui No Non
Écritures se déplaçant avant les lectures Oui No Non
Lectures se déplaçant avant les écritures Oui Oui Non

 

PowerPC a également les instructions de synchronisation isync et eieio (qui est utilisé pour contrôler le réordonnancement de la mémoire non mise en cache). Ces instructions de synchronisation ne devraient pas être nécessaires pour des fins de synchronisation normales.

Sur Windows, MemoryBarrier est défini dans Winnt.h et vous donne une instruction de barrière mémoire différente selon que vous compilez pour x86 ou x64. L’instruction de barrière mémoire sert de barrière complète, empêchant tout réordonnancement des lectures et écritures à travers la barrière. Ainsi, MemoryBarrier sur Windows offre une garantie de réordonnancement plus forte que sur Xbox 360.

Sur Xbox 360, et sur de nombreux autres processeurs, il y a un moyen supplémentaire d’empêcher le réordonnancement des lectures par le CPU. Si vous lisez un pointeur et utilisez ensuite ce pointeur pour charger d’autres données, le CPU garantit que les lectures du pointeur ne sont pas antérieures à la lecture du pointeur. Si votre indicateur de verrouillage est un pointeur et si toutes les lectures de données partagées se font à partir du pointeur, MemoryBarrier peut être omise, pour une modeste économie de performance.

Data* localPointer = g_sharedPointer;
if( localPointer )
{
    // No import barrier is needed--all reads off of localPointer
    // are guaranteed to not be reordered past the read of
    // localPointer.
    int localVariable = localPointer->y;
    // A memory barrier is needed to stop the read of g_global
    // from being speculatively moved ahead of the read of
    // g_sharedPointer.
    int localVariable2 = g_global;
}

L’instruction MemoryBarrier empêche uniquement le réordonnancement des lectures et écritures vers la mémoire mise en cache. Si vous allouez de la mémoire en tant que PAGE_NOCACHE ou PAGE_WRITECOMBINE, une technique courante pour les auteurs de pilotes de périphériques et pour les développeurs de jeux sur Xbox 360, MemoryBarrier n’a aucun effet sur les accès à cette mémoire. La plupart des développeurs n’ont pas besoin de synchronisation de la mémoire non mise en cache. La procédure n'entre pas dans le cadre de cet article.

Fonctions imbriquées et réordonnancement du CPU

Parfois, la lecture ou l’écriture qui acquiert ou libère une ressource est effectuée à l’aide d’une des fonctions InterlockedXxx. Sur Windows, cela simplifie les choses ; car sur Windows, les fonctions InterlockedXxx sont toutes des barrières en mémoire complète. Elles ont effectivement une barrière mémoire CPU à la fois avant et après elles, ce qui signifie qu’elles sont une barrière complète de lecture-acquisition ou d’écriture-libération toutes seules.

Sur Xbox 360, les fonctions InterlockedXxx ne contiennent pas de barrières mémoire CPU. Elles empêchent le réordonnancement des lectures et écritures par le compilateur mais pas par le CPU. Par conséquent, dans la plupart des cas lors de l’utilisation des fonctions InterlockedXxx sur Xbox 360, vous devez les précéder ou les suivre d’un __lwsync, pour en faire une barrière de lecture-acquisition ou d’écriture-libération. Pour plus de commodité et pour une meilleure lisibilité, il existe des versions Acquire et Release de nombreuses fonctions InterlockedXxx. Celles-ci viennent avec une barrière mémoire intégrée. Par exemple, InterlockedIncrementAcquire effectue une incrémentation imbriquée suivie d’une barrière mémoire __lwsync pour offrir la fonctionnalité complète de lecture-acquisition.

Il est recommandé d’utiliser les versions Acquire et Release des fonctions InterlockedXxx (dont la plupart sont également disponibles sur Windows, sans pénalité de performance) pour rendre votre intention plus évidente et pour faciliter la mise en place des instructions de barrière mémoire au bon endroit. Toute utilisation de InterlockedXxx sur Xbox 360 sans barrière mémoire doit être examinée très attentivement, car il s’agit souvent d’un bug.

Cet exemple montre comment un thread peut passer des tâches ou d’autres données à un autre thread en utilisant les versions Acquire et Release des fonctions InterlockedXxxSList. Les fonctions InterlockedXxxSList sont une famille de fonctions pour maintenir une liste chaînée simple partagée sans verrou. Notez que les variantes Acquire et Release de ces fonctions ne sont pas disponibles sur Windows, mais les versions régulières de ces fonctions sont une barrière mémoire complète sur Windows.

// Declarations for the Task class go here.

// Add a new task to the list using lockless programming.
void AddTask( DWORD ID, DWORD data )
{
    Task* newItem = new Task( ID, data );
    InterlockedPushEntrySListRelease( g_taskList, newItem );
}

// Remove a task from the list, using lockless programming.
// This will return NULL if there are no items in the list.
Task* GetTask()
{
    Task* result = (Task*)
        InterlockedPopEntrySListAcquire( g_taskList );
    return result;
}

Variables volatiles et réordonnancement

La norme C++ dit que les lectures de variables volatiles ne peuvent pas être mises en cache, les écritures volatiles ne peuvent pas être retardées, et les lectures et écritures volatiles ne peuvent pas être déplacées les unes par rapport aux autres. Cela suffit pour communiquer avec les dispositifs matériels, ce qui est le but du mot clé volatile dans la norme C++.

Cependant, les garanties de la norme ne sont pas suffisantes pour utiliser volatile pour le multithreading. La norme C++ n’empêche pas le compilateur de réordonner les lectures et écritures non volatiles par rapport aux lectures et écritures volatiles, et elle ne dit rien sur l’empêchement du réordonnancement par le CPU.

Visual C++ 2005 va au-delà du standard C++ pour définir des sémantiques adaptées au multithreading pour l’accès aux variables volatiles. À partir de Visual C++ 2005, les lectures des variables volatiles sont définies pour avoir des sémantiques de lecture-acquisition, et les écritures des variables volatiles sont définies pour avoir des sémantiques d’écriture-libération. Cela signifie que le compilateur ne réorganisera pas les lectures et écritures au-delà d’elles, et sur Windows, il garantira que le CPU ne le fera pas non plus.

Il est important de comprendre que ces nouvelles garanties ne s’appliquent qu’à Visual C++ 2005 et aux versions futures de Visual C++. Les compilateurs d’autres fournisseurs implémenteront généralement des sémantiques différentes, sans les garanties supplémentaires de Visual C++ 2005. De plus, sur Xbox 360, le compilateur n’insère aucune instruction pour empêcher le CPU de réordonner les lectures et écritures.

Exemple d’un canal de données sans verrou

Un canal est une construction qui permet à un ou plusieurs threads d’écrire des données qui sont ensuite lues par d’autres threads. Une version sans verrou d’un canal peut être une manière élégante et efficace de transmettre le travail d’un thread à un autre. Le SDK DirectX fournit LockFreePipe, un canal sans verrou pour un seul lecteur et un seul écrivain qui est disponible dans DXUTLockFreePipe.h. Le même LockFreePipe est disponible dans le SDK Xbox 360 dans AtgLockFreePipe.h.

LockFreePipe peut être utilisé lorsque deux threads ont une relation producteur/consommateur. Le thread producteur peut écrire des données dans le canal pour que le thread consommateur les traite plus tard, sans jamais bloquer. Si le canal se remplit, les écritures échouent, et le thread producteur devra réessayer plus tard, mais cela ne se produirait que si le thread producteur est en avance. Si le canal se vide, les lectures échouent, et le thread consommateur devra réessayer plus tard, mais cela ne se produirait que s’il n’y a aucun travail pour le thread consommateur à faire. Si les deux threads sont bien équilibrés, et si le canal est assez grand, le canal leur permet de transmettre les données en douceur sans délais ni blocages.

Performance sur Xbox 360

La performance des instructions et fonctions de synchronisation sur Xbox 360 variera en fonction de l’autre code en cours d’exécution. Acquérir des verrous prendra beaucoup plus de temps si un autre thread possède actuellement le verrou. InterlockedIncrement et les opérations de section critique prendront beaucoup plus de temps si d’autres threads écrivent sur la même ligne de cache. Le contenu des files d’attente de stockage peut également affecter les performances. Par conséquent, tous ces chiffres ne sont que des approximations, générées à partir de tests très simples :

  • lwsync a été mesuré comme prenant 33-48 cycles.
  • InterlockedIncrement a été mesuré comme prenant 225-260 cycles.
  • Acquérir ou libérer une section critique a été mesuré comme prenant environ 345 cycles.
  • Acquérir ou libérer un mutex a été mesuré comme prenant environ 2350 cycles.

Performances Windows

La performance des instructions et fonctions de synchronisation sur Windows varie largement en fonction du type et de la configuration du processeur, et de l’autre code en cours d’exécution. Les systèmes multi-cœurs et multi-sockets prennent souvent plus de temps pour exécuter des instructions de synchronisation, et l’acquisition de verrous prend beaucoup plus de temps si un autre thread possède actuellement le verrou.

Cependant, même certaines mesures générées à partir de tests très simples sont utiles :

  • MemoryBarrier a été mesuré comme prenant 20-90 cycles.
  • InterlockedIncrement a été mesuré comme prenant 36-90 cycles.
  • Acquérir ou libérer une section critique a été mesuré comme prenant 40-100 cycles.
  • Acquérir ou libérer un mutex a été mesuré comme prenant environ 750-2500 cycles.

Ces tests ont été effectués sur Windows XP sur une gamme de différents processeurs. Les temps courts étaient sur une machine mono-processeur, et les temps plus longs étaient sur une machine multi-processeur.

Bien qu’acquérir et libérer des verrous soit plus coûteux que d’utiliser une programmation sans verrou, il est encore mieux de partager les données moins fréquemment, évitant ainsi complètement le coût.

Réflexions sur la performance

Acquérir ou libérer une section critique consiste en une barrière mémoire, une opération InterlockedXxx, et quelques vérifications supplémentaires pour gérer la récursivité et se replier sur un mutex, si nécessaire. Vous devriez vous méfier de l’implémentation de votre propre section critique, car tourner en boucle en attendant qu’un verrou soit libre, sans se replier sur un mutex, peut gaspiller des performances considérables. Pour les sections critiques fortement contestées mais non détenues longtemps, vous devriez envisager d’utiliser InitializeCriticalSectionAndSpinCount afin que le système d’exploitation tourne pendant un certain temps en attendant que la section critique soit disponible plutôt que de se reporter immédiatement à un mutex si la section critique est détenue lorsque vous essayez de l’acquérir. Pour identifier les sections critiques qui peuvent bénéficier d’un compte de rotation, il est nécessaire de mesurer la durée de l’attente typique pour un verrou particulier.

Si un tas partagé est utilisé pour les allocations de mémoire—le comportement par défaut—chaque allocation et libération de mémoire implique l’acquisition d’un verrou. À mesure que le nombre de threads et le nombre d’allocations augmentent, les performances se stabilisent, puis commencent finalement à diminuer. Utiliser des tas par thread, ou réduire le nombre d’allocations, peut éviter ce goulet d’étranglement de verrouillage.

Si un thread génère des données et un autre thread consomme des données, ils peuvent finir par partager des données fréquemment. Cela peut se produire si un thread charge des ressources et un autre thread rend la scène. Si le thread de rendu référence les données partagées à chaque appel de dessin, la surcharge de verrouillage sera élevée. Une bien meilleure performance peut être réalisée si chaque thread a des structures de données privées qui sont ensuite synchronisées une fois par image ou moins.

Les algorithmes sans verrou ne sont pas garantis d’être plus rapides que les algorithmes utilisant des verrous. Vous devriez vérifier si les verrous vous causent réellement des problèmes avant d’essayer de les éviter, et vous devriez mesurer pour voir si votre code sans verrou améliore réellement les performances.

Résumé des différences entre les plateformes

  • Les fonctions InterlockedXxx empêchent le réordonnancement des lectures/écritures par le CPU sur Windows, mais pas sur Xbox 360.
  • La lecture et l’écriture des variables volatiles à l’aide de Visual Studio C++ 2005 empêchent le réordonnancement des lectures/écritures par le CPU sur Windows, mais sur Xbox 360, elles n’empêchent que le réordonnancement des lectures/écritures par le compilateur.
  • Les écritures sont réordonnées sur Xbox 360, mais pas sur x86 ou x64.
  • Les lectures sont réordonnées sur Xbox 360, mais sur x86 ou x64, elles ne sont réordonnées que par rapport aux écritures, et seulement si les lectures et écritures ciblent des emplacements différents.

Recommandations

  • Utilisez des verrous lorsque c’est possible car ils sont plus faciles à utiliser correctement.
  • Évitez de verrouiller trop fréquemment, afin que les coûts de verrouillage ne deviennent pas significatifs.
  • Évitez de maintenir des verrous trop longtemps, afin d’éviter les longues attentes.
  • Utilisez la programmation sans verrou lorsque cela est approprié, mais assurez-vous que les gains justifient la complexité.
  • Utilisez la programmation sans verrou ou les verrous de rotation dans les situations où d’autres verrous sont interdits, comme lors du partage de données entre les appels de procédure différés et le code normal.
  • N’utilisez que des algorithmes de programmation sans verrou standard qui ont été prouvés corrects.
  • Lorsque vous faites de la programmation sans verrou, assurez-vous d’utiliser des variables d’indicateur volatiles et des instructions de barrière mémoire au besoin.
  • Lors de l’utilisation de InterlockedXxx sur Xbox 360, utilisez les variantes Acquire et Release.

Références