Echange atomique avec CAS (utilisant les builtins de synchronisation gcc)

Question

La fonction compare-and-swap peut-elle être utilisée pour échanger des variables atomiquement? J'utilise C/C++ via gcc sur x86_64 RedHat Linux, en particulier les builtins __sync. Exemple:

int x = 0, y = 1; 
    y = __sync_val_compare_and_swap(&x, x, y); 

Je pense que cela se résume à si x peut changer entre & x et x; par exemple, si & x constitue une opération, il peut être possible pour x de changer entre & x et x dans les arguments. Je veux supposer que la comparaison implicite ci-dessus sera toujours vraie; Ma question est de savoir si je peux. Évidemment, il y a la version booléenne de CAS, mais je ne peux pas écrire le vieux x dans y.

Un exemple plus utile peut-être insérer ou de retirer de la tête d'une liste chaînée (demandes gcc pour soutenir les types de pointeurs, donc supposer que est ce que élém et la tête sont):

elem->next = __sync_val_compare_and_swap(&head, head, elem); //always inserts? 
    elem = __sync_val_compare_and_swap(&head, head, elem->next); //always removes? 

Référence: http://gcc.gnu.org/onlinedocs/gcc/Atomic-Builtins.html

Answer 1

Non. L'instruction CAS sur x86 prend une valeur dans un registre et la compare/écrit par rapport à une valeur dans la mémoire. Pour échanger deux variables de manière atomique, il faudrait travailler avec deux opérandes de mémoire.

Comme si x peut changer entre &x et x? Oui, bien sûr que c'est possible.

Même sans le &, cela pourrait changer.

Même dans une fonction telle que Foo(x, x), vous pourriez obtenir deux valeurs différentes de x, car pour appeler la fonction, le compilateur doit:

• prendre la valeur de x, et le stocker dans la première position de paramètre, en fonction de la convention d'appel
• prendre la valeur de x, et la stocker dans la seconde position de paramètre, en fonction de la convention d'appel

entre ces deux opérations, un autre fil pourrait facilement modifier th La valeur de x.

Answer 2

L'opération peut ne pas stocker réellement la nouvelle valeur dans la destination en raison d'une course avec un autre thread qui modifie la valeur au même moment que vous essayez. La primitive CAS ne garantit pas que l'écriture se produit - seulement que l'écriture se produit si la valeur est déjà ce qui est attendu. La primitive ne peut pas savoir quel est le comportement correct si la valeur n'est pas celle attendue, donc rien ne se produit dans ce cas - vous devez corriger le problème en vérifiant la valeur de retour pour voir si l'opération a fonctionné.

Ainsi, votre exemple:

elem->next = __sync_val_compare_and_swap(&head, head, elem); //always inserts? 

insérera pas nécessairement le nouvel élément. Si un autre thread insère un élément au même moment, une condition de concurrence peut provoquer l'appel de ce thread à __sync_val_compare_and_swap() pour ne pas mettre à jour head (mais ni l'élément de ce thread ni celui de l'autre thread n'est perdu si vous le gérez correctement).

Mais, il y a un autre problème avec cette ligne de code - même si head ne soient mis à jour, il y a un bref moment de temps où head des points à l'élément inséré, mais le pointeur next de cet élément n'a pas été mis à jour pour pointer vers le tête précédente de la liste. Si un autre fil s'infiltre pendant ce moment et essaie de marcher sur la liste, de mauvaises choses arrivent.

Pour mettre à jour correctement la liste changer cette ligne de code à quelque chose comme:

whatever_t* prev_head = NULL; 
do { 
    elem->next = head; // set up `elem->head` so the list will still be linked 
         // correctly the instant the element is inserted 
    prev_head = __sync_val_compare_and_swap(&head, elem->next, elem); 
} while (prev_head != elem->next); 

Ou utiliser la variante bool, que je pense est un peu plus pratique:

do { 
    elem->next = head; // set up `elem->head` so the list will still be linked 
         // correctly the instant the element is inserted 
} while (!__sync_bool_compare_and_swap(&head, elem->next, elem)); 

Il est le genre de laid, et j'espère que je l'ai bien fait (il est facile de se trébucher dans les détails du code thread-safe). Il devrait être enveloppé dans une fonction insert_element() (ou mieux encore, utiliser une bibliothèque appropriée).

face au problème de l'ABA:

Je ne pense pas que le problème de l'ABA est pertinent à ce code « ajouter un élément à la tête d'une liste ». Disons qu'un thread veut ajouter l'objet X à la liste et lorsqu'il exécute elem->next = head, head a la valeur A1.

Alors avant que le __sync_val_compare_and_swap() est exécuté, un autre ensemble de fils arrive et:

• supprime A1 de la liste, ce qui rend le point head à B
• fait tout avec un objet A1 et le libère
• alloue un autre objet, A2 qui se trouve être à la même adresse que A1 était
• ajoute A2 à la liste de sorte que les points head maintenant A2

Depuis A1 et A2 ont le même identifiant/adresse, ceci est une instance du problème de l'ABA.

Cependant, il n'a pas d'importance dans ce cas puisque le thread ajoutant objet X ne se soucie pas que les head pointe vers un objet différent de celui qu'il a commencé avec - tout ce qu'il prend soin est que quand X est mis en attente:

• la liste est cohérente,
• aucun objet sur la liste ont été perdus, et
• pas d'objets autres que X ont été ajoutés à la liste (par ce fil)

Answer 3

Il semble que vous soyez à la recherche de la primitive d'échange interlockée, pas de l'échange interlock-compare-exchange. Cela va échanger de manière inconditionnelle atomiquement le registre de maintien avec l'emplacement de la mémoire cible.

Cependant, vous avez toujours un problème avec les conditions de course entre les affectations au y.Parfois y est un local, auquel cas ce sera sûr, mais si les deux x et y sont partagés vous avez un problème majeur et aurez besoin d'un verrou pour le résoudre.