Partager via

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

  • Article

La programmation sans verrou est un moyen de partager en toute sécurité des données modifiées entre plusieurs threads sans coût d’acquisition et de libération de 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 verrouillage 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’il vous donne réellement les gains que vous attendez. Dans de nombreux cas, il existe des solutions plus simples et plus rapides, telles que le partage de données moins fréquemment, qui doivent être utilisées à la place.

L’utilisation correcte et sécurisée de la programmation sans verrou nécessite une connaissance significative de votre matériel et de votre compilateur. Cet article donne une vue d’ensemble de certains des problèmes à prendre en compte lorsque vous essayez 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 des threads. Si plusieurs threads lisent et écrivent simultanément les structures de données partagées, une altération de la mémoire peut se produire. Le moyen le plus simple de résoudre ce problème consiste à utiliser des verrous. Par instance, si ManipulateSharedData ne doit être exécuté que par un 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 simple, et il est facile de dire qu’il est correct. Toutefois, la programmation avec verrous présente plusieurs inconvénients potentiels. Par exemple, si deux threads essaient d’acquérir les deux mêmes verrous mais les acquièrent dans un ordre différent, vous pouvez obtenir un blocage. Si un programme conserve un verrou pendant trop longtemps( en raison d’une conception médiocre ou parce que le thread a été échangé par un thread de priorité plus élevée), d’autres threads peuvent être bloqués pendant une longue période. Ce risque est particulièrement important sur Xbox 360, car les threads logiciels se voient attribuer un thread matériel par le développeur et le système d’exploitation ne les déplace pas vers un autre thread matériel, même si l’un d’eux est inactif. La Xbox 360 n’a pas non plus de protection contre l’inversion de priorité, où un thread à priorité élevée tourne dans une boucle en attendant qu’un thread de faible priorité libère un verrou. Enfin, si un appel de procédure différée ou une routine de service d’interruption tente d’acquérir un verrou, vous pouvez obtenir un blocage.

Malgré ces problèmes, les primitives de synchronisation, telles que les sections critiques, sont généralement la meilleure façon de coordonner plusieurs threads. Si les primitives de synchronisation sont trop lentes, la meilleure solution consiste généralement à les utiliser moins fréquemment. Toutefois, pour ceux qui peuvent se permettre la 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 permettant de 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.

Lorsque vous effectuez une programmation sans verrou, vous devez relever deux défis : les opérations non atomiques et la réorganisation.

Opérations non atomiques

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

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

Les lectures et écritures de types qui ne sont pas naturellement alignés (pour instance, l’écriture de DWORD qui dépassent des limites de quatre octets) ne sont pas garanties atomiques. Le processeur peut avoir à effectuer ces lectures et écritures sous forme de plusieurs transactions de bus, ce qui peut 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 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 sous la forme de plusieurs instructions (lwz, addi et stw), et le thread peut être échangé en dehors 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, l’incrémentation d’une variable est atomique sur les systèmes à processeur unique, mais elle n’est toujours pas atomique sur les systèmes multiprocesseurs. La création d’inc atomic sur les systèmes multiprocesseurs x86 et x64 nécessite l’utilisation du préfixe de verrou, ce qui empêche un autre processeur d’effectuer 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;

Garantie de l’atomicité

Vous pouvez être sûr d’utiliser des opérations atomiques en combinant les éléments suivants :

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

L’incrémentation d’une variable n’est pas une opération atomique, et l’incrémentation peut entraîner une altération des 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 fourni avec une famille de fonctions qui offrent des versions atomiques en lecture-modification-écriture de plusieurs opérations courantes. Il s’agit de la famille de fonctions InterlockedXxx. Si toutes les modifications de la variable partagée utilisent ces fonctions, les modifications seront thread-safe.

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

Réorganisation

Un problème plus subtil est la réorganisation. Les lectures et les écritures ne se produisent pas toujours dans l’ordre dans lequel vous les avez écrites dans votre code, ce qui peut entraîner des problèmes très confus. Dans de nombreux algorithmes multithread, un thread écrit des données, puis écrit dans un indicateur qui indique à d’autres threads que les données sont prêtes. Il s’agit d’une version d’écriture. Si les écritures sont réorganisées, d’autres threads peuvent voir que l’indicateur est défini avant de pouvoir voir les données écrites.

De même, dans de nombreux cas, un thread lit à partir d’un indicateur, puis lit certaines données partagées si l’indicateur indique que le thread a acquis l’accès aux données partagées. C’est ce qu’on appelle une acquisition en lecture. Si les lectures sont réorganisées, les données peuvent être lues à partir du stockage partagé avant l’indicateur et les valeurs affichées peuvent 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 ont effectué cette réorganisation depuis des années, mais sur les ordinateurs monoprocesseurs, cela a été moins problématique. En effet, le réarrangement du processeur des lectures et des écritures est invisible sur les ordinateurs monoprocesseurs (pour le code de pilote non de périphérique qui ne fait pas partie d’un pilote de périphérique), et le réarrangement du compilateur des lectures et des écritures est moins susceptible de provoquer des problèmes sur les machines monoprocesseur.

Si le compilateur ou le processeur réorganise les écritures indiquées dans le code suivant, un autre thread peut voir que l’indicateur actif est défini tout en voyant les anciennes valeurs pour x ou y. Un réarrangement similaire peut se produire lors de la lecture.

Dans ce code, un thread ajoute une nouvelle entrée au tableau de 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 de 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 sprite, nous devons empêcher le compilateur et le réorganisation du processeur des lectures et des écritures.

Présentation du réarrangement du processeur des écritures

Certains processeurs réorganisent les écritures afin qu’elles soient visibles en externe par d’autres processeurs ou appareils dans l’ordre non-programme. Cette réorganisation n’est jamais visible pour le code non-pilote à thread unique, mais elle peut entraîner des problèmes dans le code multithread.

Xbox 360

Bien que le processeur 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 Xbox 360 ne sont pas directement dans le cache L2. Au lieu de cela, afin d’améliorer la bande passante d’écriture du cache L2, ils passent par les files d’attente de magasin, puis pour stocker-collecter des mémoires tampons. Les mémoires tampons store-collect permettent d’écrire des blocs de 64 octets dans le cache L2 en une seule opération. Il existe huit mémoires tampons de stockage-collecte, qui permettent une écriture efficace dans plusieurs zones de mémoire différentes.

Les mémoires tampons de stockage-collecte sont normalement écrites dans le cache L2 dans l’ordre FIFO (first-in-out). Toutefois, 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 extraite de la mémoire.

Même lorsque les mémoires tampons de stockage-collecte sont écrites dans le cache L2 dans un ordre FIFO strict, cela ne garantit pas que les écritures individuelles sont écrites dans le cache L2 dans l’ordre. Par instance, imaginez que le processeur écrit dans l’emplacement 0x1000, puis dans l’emplacement 0x2000, puis dans l’emplacement 0x1004. La première écriture alloue une mémoire tampon de stockage-collecte et la place à l’avant de la file d’attente. La deuxième écriture alloue une autre mémoire tampon de stockage-collecte et la place ensuite dans la file d’attente. La troisième écriture ajoute ses données à la première mémoire tampon de stockage-collecte, qui reste à l’avant de la file d’attente. Ainsi, la troisième écriture finit par aller au cache L2 avant la deuxième écriture.

La réorganisation provoquée par les mémoires tampons de stockage-collecte est fondamentalement imprévisible, en particulier parce que les deux threads d’un cœur partagent les mémoires tampons de stockage-collecte, ce qui rend l’allocation et la vidage des mémoires tampons de stockage-collecte hautement variables.

Il s’agit d’un exemple de la façon dont les écritures peuvent être réorganisées. Il peut y avoir d’autres possibilités.

x86 et x64

Bien que les processeurs 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 existe quelques exceptions pour la mémoire combinée en écriture. En outre, les opérations de chaîne (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.

Présentation du réarrangement du processeur des lectures

Certains processeurs réorganisent les lectures afin qu’elles proviennent effectivement d’un stockage partagé dans un ordre non-programme. Cette réorganisation n’est jamais visible pour le code non-pilote à thread unique, mais peut entraîner des problèmes dans le code multithread.

Xbox 360

Les absences de cache peuvent entraîner le retard de certaines lectures, ce qui entraîne en effet des lectures provenant de la mémoire partagée dans le désordre, et le minutage de ces absences de cache est fondamentalement imprévisible. La prérécupération et la prédiction de branche peuvent également entraîner des données provenant de la mémoire partagée dans le désordre. Ce ne sont là que quelques exemples de la façon 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 processeurs 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 de chaîne (MOVS et STOS) et les lectures SSE de 16 octets peuvent être réorganisées en interne, mais dans le cas contraire, les lectures ne sont pas réorganisées les unes par rapport aux autres.

Autres réorganisations

Même si les processeurs x86 et x64 ne réorganisent pas les écritures par rapport à d’autres écritures ou réorganisent les lectures par rapport à d’autres lectures, elles peuvent réorganiser les lectures par rapport aux écritures. Plus précisément, si un programme écrit dans un emplacement suivi d’une lecture à partir d’un autre emplacement, les données de lecture peuvent provenir de la mémoire partagée avant que les données écrites ne s’y rendent. Cette réorganisation peut interrompre certains algorithmes, tels que les algorithmes d’exclusion mutuelle de Dekker. Dans l’algorithme de Dekker, chaque thread définit un indicateur pour indiquer qu’il souhaite entrer dans la région critique, puis vérifie l’indicateur de l’autre thread pour voir si l’autre thread se trouve dans la région critique ou en essayant de l’entrer. Le code initial suit.

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 dans f0 n’arrive au stockage partagé. Pendant ce temps, la lecture de f0 dans P1Acquire peut lire à partir du stockage partagé avant que l’écriture dans f1 ne le rende dans le 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, de sorte qu’ils entrent tous les deux dans la région critique. Par conséquent, bien que les problèmes de réorganisation sur les systèmes x86 et x64 soient moins courants que sur Xbox 360, ils peuvent certainement se produire. L’algorithme de Dekker ne fonctionne pas sans barrières mémoire matérielles sur l’une de ces plateformes.

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

Les processeurs PowerPC peuvent réorganiser les lectures avant les écritures, et peuvent réorganiser les écritures avant les lectures, à condition qu’elles soient à des adresses différentes.

Récapitulatif de la réorganisation

Le processeur Xbox 360 réorganise les opérations de mémoire de manière beaucoup plus agressive que les processeurs x86 et x64, comme indiqué dans le tableau suivant. Pour plus d’informations, consultez la documentation du processeur.

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

 

Read-Acquire et Write-Release barrières

Les constructions main utilisées pour empêcher la réorganisation des lectures et des écritures sont appelées barrières de lecture-acquisition et de libération d’écriture. Une acquisition en lecture est une lecture d’un indicateur ou d’une autre variable permettant d’acquérir la propriété d’une ressource, associée à un obstacle à la réorganisation. De même, une version d’écriture est une écriture d’un indicateur ou d’une autre variable pour donner la propriété d’une ressource, associée à un obstacle à la réorganisation.

Les définitions formelles, gracieuseté de Herb Sutter, sont les suivantes :

  • Une lecture-acquisition s’exécute avant toutes les lectures et écritures par le même thread qui le suit dans l’ordre du programme.
  • Une mise en production d’écriture s’exécute après toutes les lectures et écritures par le même thread qui la précède dans l’ordre du programme.

Lorsque votre code acquiert la propriété d’une partie de la mémoire, soit en acquérant un verrou, soit en extrayant un élément d’une liste liée partagée (sans verrou), il y a toujours une lecture impliquée : testez un indicateur ou un pointeur pour voir si la propriété 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 propriété a été acquise. Une fois la propriété de la mémoire acquise, les 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 propriété. Un obstacle en lecture-acquisition garantit cela.

Lorsque la propriété d’une partie de la mémoire est libérée, soit en libérant un verrou, soit en envoyant un élément à une liste liée partagée, il y a toujours une écriture impliquée qui avertit les autres threads que la mémoire est désormais disponible. Bien que votre code ait la propriété de la mémoire, il lit probablement ou écrit dans celui-ci, et il est très important que ces lectures et écritures s’exécutent avant de libérer la propriété. Une barrière de libération d’écriture le garantit.

Il est plus simple de considérer les barrières en lecture-acquisition et en écriture comme des opérations uniques. Toutefois, ils doivent parfois être construits à partir de deux parties : une lecture ou écriture et une barrière qui n’autorise pas les lectures ou écritures à se déplacer entre elles. Dans ce cas, l’emplacement de la barrière est essentiel. Pour une barrière lecture-acquisition, la lecture de l’indicateur arrive en premier, puis la barrière, puis les lectures et écritures des données partagées. Pour une barrière de libération d’écriture, les lectures et écritures des données partagées passent en premier, 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 lecture-acquisition et une mise en production en écriture est l’emplacement de la barrière de mémoire. Une acquisition en lecture a la barrière après l’opération de verrouillage, et une libération d’écriture a 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 des obstacles sont nécessaires à la fois lors de l’acquisition et de la libération de données, il est préférable (et le plus précis) de considérer ces obstacles comme garantissant la synchronisation avec la mémoire partagée, et non avec d’autres processeurs. Si un processeur utilise une mise en production d’écriture pour libérer une structure de données en mémoire partagée, et si 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 fonctionne alors correctement. Si l’un des processeurs n’utilise pas la barrière appropriée, le partage de données peut échouer.

Il est essentiel d’utiliser la barrière appropriée pour empêcher la réorganisation du compilateur et du processeur pour votre plateforme.

L’un des avantages de l’utilisation des primitives de synchronisation fournies par le système d’exploitation est que toutes incluent les barrières de mémoire appropriées.

Empêcher la réorganisation du compilateur

Le travail d’un compilateur consiste à optimiser votre code de manière agressive afin d’améliorer les performances. Cela inclut le réorganisage des instructions partout où cela est utile et où ils ne modifient pas le comportement. Étant donné que la norme C++ ne mentionne jamais le multithreading et que le compilateur ne sait pas quel code doit être thread-safe, le compilateur suppose que votre code est à thread unique lors du choix des réorganisations qu’il peut effectuer en toute sécurité. Par conséquent, vous devez indiquer au compilateur quand il n’est pas autorisé à réorganiser les lectures et écritures.

Avec Visual C++, vous pouvez empêcher la réorganisation du compilateur à l’aide de la _ReadWriteBarrier intrinsèque du compilateur. Lorsque vous insérez _ReadWriteBarrier dans votre code, le compilateur ne déplace pas les lectures et les écritures sur celui-ci.

#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 à partir du tableau de sprites :

// 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 pas d’instructions supplémentaires et qu’elle n’empêche pas le processeur de réorganiser les lectures et les écritures: cela empêche uniquement le compilateur de les réorganiser. Par conséquent, _ReadWriteBarrier est suffisant lorsque vous implémentez une barrière de libération d’écriture sur x86 et x64 (parce que x86 et x64 ne réorganisent pas les écritures, et qu’une écriture normale suffit pour libérer un verrou), mais dans la plupart des autres cas, il est également nécessaire d’empêcher le processeur de réorganiser les lectures et les écritures.

Vous pouvez également utiliser _ReadWriteBarrier lorsque vous écrivez dans une mémoire combinée en écriture non mise en cache pour empêcher la réorganisation des écritures. Dans ce cas , _ReadWriteBarrier permet d’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 _ReadBarrier et _WriteBarrier intrinsèques pour un contrôle plus précis de la réorganisation du compilateur. Le compilateur ne déplace pas les lectures d’un _ReadBarrier, ni les écritures d’un _WriteBarrier.

Empêcher la réorganisation du processeur

La réorganisation du processeur est plus subtile que la réorganisation du compilateur. Vous ne pouvez jamais voir cela se produire directement, vous voyez simplement des bogues inexplicables. Pour empêcher la réorganisation des lectures et des écritures par le processeur, vous devez utiliser des instructions de barrière de mémoire sur certains processeurs. Le nom universel d’une instruction de barrière de 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 le __lwsync intrinsèque, qui est défini dans ppcintrinsics.h. __lwsync sert également de barrière à la mémoire du compilateur, ce qui empêche le réorganisage des lectures et des é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. Il garantit que toutes les écritures avant lwsync sont dans le cache L2 avant toutes les écritures qui suivent. Il garantit également que toutes les lectures qui suivent lwsync n’obtiennent pas de données plus anciennes de L2 que les lectures précédentes. Le seul type de réorganisation qu’il n’empêche pas est une lecture qui avance d’une écriture vers une autre adresse. Ainsi, lwsync applique l’ordre de la mémoire qui correspond à l’ordre de mémoire par défaut sur les processeurs x86 et x64. Pour obtenir le classement de la mémoire complète, vous devez utiliser l’instruction de synchronisation plus coûteuse (également appelée synchronisation lourde), mais dans la plupart des cas, cela n’est pas nécessaire. Les options de réorganisation de la mémoire sur Xbox 360 sont présentées dans le tableau suivant.

Réorganisation xbox 360 Aucune synchronisation lwsync synchronisation
Lectures en avance sur les lectures Oui Non Non
Écritures se déplaçant avant les écritures Oui Non Non
Écritures en avance sur les lectures Oui Non Non
Lit en avance sur les écritures Oui Oui Non

 

PowerPC contient également les instructions de synchronisation isync et eieio (qui sont utilisées pour contrôler la réorganisation de la mémoire inhibée par la mise en cache). Ces instructions de synchronisation ne doivent pas être nécessaires à des fins de synchronisation normale.

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 la barrière de mémoire sert de barrière complète, empêchant toute réorganisation des lectures et écritures au-delà de la barrière. Ainsi, MemoryBarrier sur Windows offre une garantie de réorganisation plus forte que sur Xbox 360.

Sur Xbox 360 et sur de nombreux autres processeurs, il existe un moyen supplémentaire d’empêcher la réorganisation en lecture par le processeur. Si vous lisez un pointeur, puis utilisez ce pointeur pour charger d’autres données, le processeur 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 sont hors du pointeur, memoryBarrier peut être omis, pour une réduction modeste des performances.

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 la réorganisation des lectures et écritures dans la mémoire pouvant être 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 d’appareil 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 synchroniser la mémoire non mise en cache. La procédure n'entre pas dans le cadre de cet article.

Fonctions verrouillées et réorganisation du processeur

Parfois, la lecture ou l’écriture qui acquiert ou libère une ressource est effectuée à l’aide de l’une des fonctions InterlockedXxx . Sur Windows, cela simplifie les choses . car sur Windows, les fonctions InterlockedXxx sont toutes des barrières mémoire complète. Ils ont effectivement une barrière de mémoire processeur avant et après eux, ce qui signifie qu’ils constituent une barrière complète en lecture-acquisition ou en écriture-libération par eux-mêmes.

Sur Xbox 360, les fonctions InterlockedXxx ne contiennent pas de barrières mémoire processeur. Ils empêchent le compilateur de réorganiser les lectures et les écritures, mais pas la réorganisation du processeur. Par conséquent, dans la plupart des cas lorsque vous utilisez des fonctions InterlockedXxx sur Xbox 360, vous devez les faire précéder ou les suivre d’un __lwsync, pour en faire un obstacle en lecture-acquisition ou en écriture-libération. Pour plus de commodité et pour faciliter la lisibilité, il existe des versions Acquire et Release de la plupart des fonctions InterlockedXxx . Ceux-ci sont fournis avec une barrière de mémoire intégrée. Par instance, InterlockedIncrementAcquire effectue un incrément verrouillé suivi d’une barrière de mémoire __lwsync pour fournir la fonctionnalité complète d’acquisition de lecture.

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

Cet exemple montre comment un thread peut transmettre des tâches ou d’autres données à un autre thread à l’aide des versions Acquire et Release des fonctions InterlockedXxxSList . Les fonctions InterlockedXxxSList sont une famille de fonctions permettant de gérer une liste liée de manière unique partagée sans verrou. Notez que les variantes Acquire et Release de ces fonctions ne sont pas disponibles sur Windows, mais que les versions régulières de ces fonctions constituent une barrière de 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éorganisation

La norme C++ indique que les lectures de variables volatiles ne peuvent pas être mises en cache, que les écritures volatiles ne peuvent pas être retardées et que les lectures et écritures volatiles ne peuvent pas être déplacées les unes des autres. Cela est suffisant pour communiquer avec les appareils matériels, ce qui est l’objectif de la mot clé volatile dans la norme C++.

Toutefois, les garanties de la norme ne sont pas suffisantes pour l’utilisation de volatiles pour le multithreading. La norme C++ n’empêche pas le compilateur de réorganiser les lectures et écritures non volatiles par rapport aux lectures et écritures volatiles, et elle ne dit rien sur la prévention de la réorganisation du processeur.

Visual C++ 2005 va au-delà du C++ standard pour définir une sémantique compatible avec plusieurs threads pour l’accès aux variables volatiles. À compter de Visual C++ 2005, les lectures à partir de variables volatiles sont définies pour avoir une sémantique lecture-acquisition, et les écritures dans des variables volatiles sont définies pour avoir une sémantique de mise en production en écriture. Cela signifie que le compilateur ne réorganisera pas les lectures et les écritures au-delà de celles-ci, et sur Windows, il s’assurera que le processeur ne le fait pas non plus.

Il est important de comprendre que ces nouvelles garanties s’appliquent uniquement à Visual C++ 2005 et aux versions ultérieures de Visual C++. Les compilateurs d’autres fournisseurs implémentent généralement une sémantique différente, sans les garanties supplémentaires de Visual C++ 2005. En outre, sur Xbox 360, le compilateur n’insère pas d’instructions pour empêcher le processeur de réorganiser les lectures et les écritures.

Exemple de canal de données Lock-Free

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 un moyen élégant et efficace de passer le travail d’un thread à un autre. Le Kit de développement logiciel (SDK) DirectX fournit LockFreePipe, un canal à lecteur unique et à écriture unique qui est disponible dans DXUTLockFreePipe.h. Le même LockFreePipe est disponible dans le Kit de développement logiciel (SDK) Xbox 360 dans AtgLockFreePipe.h.

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

Performances Xbox 360

Les performances des instructions et fonctions de synchronisation sur Xbox 360 varient en fonction de l’autre code en cours d’exécution. L’acquisition de verrous prendra beaucoup plus de temps si un autre thread est actuellement propriétaire du verrou. Les opérations interlockedIncrement et les opérations de section critique prennent beaucoup plus de temps si d’autres threads écrivent dans la même ligne de cache. Le contenu des files d’attente du magasin peut également affecter les performances. Par conséquent, tous ces nombres 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.
  • L’acquisition ou la libération d’une section critique a été mesurée comme prenant environ 345 cycles.
  • L’acquisition ou la libération d’un mutex a été mesurée comme prenant environ 2 350 cycles.

Performances Windows

Les performances des instructions et des fonctions de synchronisation sur Windows varient considérablement en fonction du type de processeur et de la configuration, ainsi que de l’autre code en cours d’exécution. Les systèmes multicœ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 est actuellement propriétaire du verrou.

Toutefois, 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.
  • L’acquisition ou la libération d’une section critique a été mesurée comme prenant 40 à 100 cycles.
  • L’acquisition ou la libération d’un mutex a été mesurée comme prenant environ 750-2 500 cycles.

Ces tests ont été effectués sur Windows XP sur une gamme de processeurs différents. Les temps courts étaient sur un ordinateur monoprocesseur, et les temps les plus longs étaient sur un ordinateur multiprocesseur.

Bien que l’acquisition et la libération de verrous soient plus coûteuses que l’utilisation de la programmation sans verrou, il est encore préférable de partager des données moins fréquemment, ce qui évite complètement le coût.

Pensées sur les performances

L’acquisition ou la libération d’une section critique se compose d’une barrière de mémoire, d’une opération InterlockedXxx et d’une vérification supplémentaire pour gérer la récursivité et revenir à un mutex, si nécessaire. Vous devez vous méfier de l’implémentation de votre propre section critique, car tourner dans une boucle en attendant qu’un verrou soit libre, sans revenir à un mutex, peut gaspiller des performances considérables. Pour les sections critiques qui sont fortement disputées mais qui ne sont pas conservées longtemps, vous devez envisager d’utiliser InitializeCriticalSectionAndSpinCount afin que le système d’exploitation tourne pendant un certain temps en attendant que la section critique soit disponible au lieu de s’en remettre 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 tirer parti d’un nombre de spins, il est nécessaire de mesurer la longueur de l’attente classique pour un verrou particulier.

Si un tas partagé est utilisé pour les allocations de mémoire (comportement par défaut), chaque allocation de mémoire et gratuite implique l’acquisition d’un verrou. À mesure que le nombre de threads et le nombre d’allocations augmentent, les performances diminuent et finissent par diminuer. L’utilisation de tas par thread ou la réduction du nombre d’allocations peut éviter ce goulot d’étranglement.

Si un thread génère des données et qu’un autre thread consomme des données, il peut finir par partager des données fréquemment. Cela peut se produire si un thread charge des ressources et qu’un autre thread effectue le rendu de 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. De meilleures performances peuvent être réalisées si chaque thread a des structures de données privées qui sont ensuite synchronisées une fois par image ou moins.

Il n’est pas garanti que les algorithmes sans verrou soient plus rapides que les algorithmes qui utilisent des verrous. Vous devez case activée pour voir si les verrous sont réellement à l’origine de vos problèmes avant d’essayer de les éviter, et vous devez mesurer pour voir si votre code sans verrou améliore réellement les performances.

Résumé des différences de plateforme

  • Les fonctions InterlockedXxx empêchent la réorganisation en lecture/écriture du processeur sur Windows, mais pas sur Xbox 360.
  • La lecture et l’écriture de variables volatiles à l’aide de Visual Studio C++ 2005 empêchent la réorganisation en lecture/écriture du processeur sur Windows, mais sur Xbox 360, cela empêche uniquement la réorganisation en lecture/écriture du compilateur.
  • Les écritures sont réorganisées sur Xbox 360, mais pas sur x86 ou x64.
  • Les lectures sont réorganisées sur Xbox 360, mais sur x86 ou x64, elles ne sont réorganisées que par rapport aux écritures, et uniquement si les lectures et écritures ciblent des emplacements différents.

Recommandations

  • Utilisez des verrous dans la mesure du possible, car ils sont plus faciles à utiliser correctement.
  • Évitez de verrouiller trop fréquemment afin que les coûts de verrouillage ne deviennent pas importants.
  • Évitez de tenir les verrous trop longtemps, afin d’éviter les longs décrochages.
  • Utilisez la programmation sans verrou le cas échéant, mais assurez-vous que les gains justifient la complexité.
  • Utilisez la programmation sans verrou ou les verrous tournants dans les situations où d’autres verrous sont interdits, par exemple lors du partage de données entre des appels de procédure différés et du code normal.
  • Utilisez uniquement des algorithmes de programmation sans verrou standard qui se sont avérés corrects.
  • Lorsque vous effectuez une programmation sans verrou, veillez à utiliser des variables d’indicateur volatiles et des instructions de barrière de mémoire si nécessaire.
  • Lorsque vous utilisez InterlockedXxx sur Xbox 360, utilisez les variantes Acquérir et Publier .

Références