Barrières de mémoire contre les opérations interverrouillées

Question

J'essaie d'améliorer ma compréhension des barrières de la mémoire. Supposons que nous ayons un modèle de mémoire faible et nous adaptons Dekker's algorithm. Est-il possible de le faire fonctionner correctement sous le modèle de mémoire faible en ajoutant des barrières de mémoire?

Je pense que la réponse est un non surprenant. La raison (si je me trompe) est que même si une barrière de mémoire peut être utilisée pour s'assurer qu'une lecture ne soit pas déplacée, elle ne peut pas garantir qu'une lecture ne voit pas de données périmées (comme dans un cache). Ainsi, il pourrait voir un certain temps dans le passé lorsque la section critique a été déverrouillée (par le cache du processeur), mais à l'heure actuelle, d'autres processeurs pourraient le voir verrouillé. Si ma compréhension est correcte, il faut utiliser des opérations imbriquées telles que celles communément appelées test-and-set ou compare-and-swap pour assurer l'accord synchronisé d'une valeur à un emplacement mémoire entre plusieurs processeurs.

Ainsi, pouvons-nous à juste titre nous attendre à ce qu'aucun système de modèle de mémoire faible ne fournisse que des barrières de mémoire? Le système doit fournir des opérations comme test-and-set ou compare-and-swap pour être utile. Je me rends compte que les processeurs populaires, y compris x86, fournissent des modèles de mémoire beaucoup plus forts qu'un modèle de mémoire faible. Veuillez concentrer la discussion sur les modèles à mémoire faible.

(Si l'algorithme de Dekker est un mauvais choix, choisir un autre algorithme d'exclusion mutuelle où les barrières de mémoire peuvent réussir à atteindre la synchronisation correcte, si possible.)

Answer 1

Vous avez raison de dire qu'une barrière de mémoire ne peut pas garantir qu'une lecture voit des valeurs mises à jour. Ce qu'il fait est d'imposer un ordre entre les opérations, à la fois sur un seul thread, et entre les threads. Par exemple, si le thread A effectue une série de mémoires, puis exécute une barrière de libération avant un stockage final vers un emplacement de drapeau, le thread B lit à partir de l'emplacement du drapeau puis exécute une barrière d'acquisition avant de lire les autres valeurs les autres variables ont les valeurs enregistrées par le thread A:

// initially x=y=z=flag=0 

// thread A 
x=1; 
y=2; 
z=3; 
release_barrier(); 
flag=1; 

// thread B 
while(flag==0) ; // loop until flag is 1 
acquire_barrier(); 
assert(x==1); // asserts will not fire 
assert(y==2); 
assert(z==3); 

Bien sûr, vous devez vous assurer que la charge et le stockage à flag est atomique (qui instructions de chargement et de stockage simples sont sur les processeurs les plus courants, à condition que les variables soient correctement alignées). Sans la boucle while sur le thread B, le thread B peut lire une valeur périmée (0) pour flag, et vous ne pouvez donc garantir aucune des valeurs lues pour les autres variables. Les clôtures peuvent ainsi être utilisées pour imposer la synchronisation dans l'algorithme de Dekker.

Voici un exemple d'implémentation en C++ (en C++ 0x les variables atomiques):

std::atomic<bool> flag0(false),flag1(false); 
std::atomic<int> turn(0); 

void p0() 
{ 
    flag0.store(true,std::memory_order_relaxed); 
    std::atomic_thread_fence(std::memory_order_seq_cst); 

    while (flag1.load(std::memory_order_relaxed)) 
    { 
     if (turn.load(std::memory_order_relaxed) != 0) 
     { 
      flag0.store(false,std::memory_order_relaxed); 
      while (turn.load(std::memory_order_relaxed) != 0) 
      { 
      } 
      flag0.store(true,std::memory_order_relaxed); 
      std::atomic_thread_fence(std::memory_order_seq_cst); 
     } 
    } 
    std::atomic_thread_fence(std::memory_order_acquire); 

    // critical section 


    turn.store(1,std::memory_order_relaxed); 
    std::atomic_thread_fence(std::memory_order_release); 
    flag0.store(false,std::memory_order_relaxed); 
} 

void p1() 
{ 
    flag1.store(true,std::memory_order_relaxed); 
    std::atomic_thread_fence(std::memory_order_seq_cst); 

    while (flag0.load(std::memory_order_relaxed)) 
    { 
     if (turn.load(std::memory_order_relaxed) != 1) 
     { 
      flag1.store(false,std::memory_order_relaxed); 
      while (turn.load(std::memory_order_relaxed) != 1) 
      { 
      } 
      flag1.store(true,std::memory_order_relaxed); 
      std::atomic_thread_fence(std::memory_order_seq_cst); 
     } 
    } 
    std::atomic_thread_fence(std::memory_order_acquire); 

    // critical section 


    turn.store(0,std::memory_order_relaxed); 
    std::atomic_thread_fence(std::memory_order_release); 
    flag1.store(false,std::memory_order_relaxed); 
} 

Pour une analyse complète, voir mon entrée de blog à http://www.justsoftwaresolutions.co.uk/threading/implementing_dekkers_algorithm_with_fences.html

Answer 2

Certains obstacles (comme le isync powerpc, et une charge de .acq sur ia64) ont également un effet sur les charges suivantes. c'est-à-dire: si une charge était disponible avant l'isync à cause de la pré-extraction, elle doit être rejetée. Lorsqu'il est utilisé correctement, cela suffit peut-être pour que l'algorithme de Dekker fonctionne sur un modèle de mémoire faible.

Vous avez également une logique d'invalidation de cache qui fonctionne pour vous. Si vous savez que votre charge est en cours à cause de quelque chose comme un isync et que la version mise en cache des données est invalidée si un autre processeur la touche, est-ce suffisant?

Des questions intéressantes mises à part, l'algorithme de Dekker est pour le moins pratique. Vous allez vouloir utiliser des interfaces matérielles atomiques et des barrières de mémoire pour toute application réelle, donc se concentrer sur la façon de réparer Dekker avec des atomiques ne me semble pas utile;)

Answer 3

Dites que vous avez chargé et stocké barrière après chaque déclaration, et en plus vous avez veillé à ce que le compilateur n'a pas réorganiser vos magasins. Ne serait-ce pas, sur une architecture raisonnable, fournir une cohérence stricte? Les travaux de Dekker sur des architectures cohérentes séquentiellement. La cohérence séquentielle est une condition plus faible que la cohérence stricte.

http://www.cs.nmsu.edu/~pfeiffer/classes/573/notes/consistency.html

Même sur une unité centrale de traitement qui a un modèle de cohérence faible, vous vous attendez toujours la cohérence du cache. Je pense que là où les choses déraillent, c'est le comportement des buffers de magasins et des lectures spéculées, et quelles opérations sont disponibles pour vider les écritures stockées et invalider les lectures spéculées. S'il n'y a pas de barrière de chargement qui peut invalider les lectures spéculées, ou s'il n'y a pas de barrière d'écriture qui vide un tampon de stockage, en plus de ne pas pouvoir implémenter Dekker, vous ne pourrez pas implémenter un mutex!

Voici donc ma réclamation. Si vous disposez d'une barrière d'écriture et d'une barrière de lecture et que le cache est cohérent entre les processeurs, vous pouvez uniformément rendre cohérents tous les codes en rinçant les écritures (store fence) après chaque instruction et en expulsant les spéculations (read clôture) avant chaque instruction. Donc, je prétends que vous n'avez pas besoin d'atomiques pour ce dont vous parlez, et que vous pouvez faire ce dont vous avez besoin avec Dekker seulement. Bien sûr, vous ne voudriez pas.BTW, Corensic, la société pour laquelle je travaille, écrit des outils géniaux pour le débogage des problèmes de simultanéité. Découvrez http://www.corensic.com.