atomique swap avec SAE (avec gcc synchroniser les builtins)

L'opération risque de ne pas enregistrer la nouvelle valeur dans la destination en raison d'une course avec un autre thread que des changements à la valeur, au même moment où vous essayez de. Le CAS primitive ne garantit pas que l'écriture se produit uniquement que l'écriture se produit si la valeur est déjà ce que l'on attend. Le primitif ne peut pas savoir ce que le comportement correct est si la valeur n'est pas ce qui est prévu, rien ne se passe dans ce cas, vous devez corriger le problème en vérifiant la valeur de retour voir si l'opération a fonctionné.

Donc, votre exemple:

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

ne sont pas nécessairement insérer le nouvel élément. Si un autre thread insère un élément dans le même moment, il y a une condition de concurrence qui pourrait causer ce thread appel à __sync_val_compare_and_swap() ne pas mettre à jour head (mais ni ce thread ou l'autre thread de l'élément est encore perdu si vous la manipulez correctement).

Mais, il y a un autre problème avec cette ligne de code (même si head obtenir la mise à jour, il y a un bref instant dans le temps où head points de l'élément inséré, mais que l'élément next pointeur n'a pas été mis à jour pour pointer à la précédente à la tête de la liste. Si un autre thread fonce dans le moment et tente de marcher sur la liste, les mauvaises choses se produisent.

Correctement mise à jour de la liste de changement de la 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 le bool variante, qui 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));

C'est un peu moche, et j'espère que j'ai bien compris (il est facile de trébucher dans les détails de thread-safe code). Il doit être enveloppé dans un insert_element() fonction (ou mieux encore, utiliser une bibliothèque appropriée).

Aborder l'ABA problème:

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

Puis avant l' __sync_val_compare_and_swap() est exécuté, un autre ensemble de threads arrive et:

• supprime A1 de la liste, en faisant head point de B
• n'quel que soit l'objet A1 et la libère
• alloue un autre objet, A2 qui arrive à être à la même adresse que A1 était
• ajoute A2 à la liste, de sorte que head maintenant les points à A2

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

Cependant, il n'a pas d'importance dans ce cas puisque le thread de l'ajout de l'objet X ne se soucie pas que la head points à un autre objet qu'il a commencé avec tous il se soucie est que lorsque X est mis en file d'attente:

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

OriginalL'auteur Michael Burr

Il semble que vous êtes à la recherche pour le contrefil-échange primitif, pas le contrefil-comparer-échange. Qui sera inconditionnellement atomiquement swap de la tenue de s'inscrire auprès de la cible emplacement de mémoire.

Toutefois, vous avez toujours un problème avec les conditions de concurrence entre les missions de y. Parfois y est un local, dans ce cas, ce sera en sécurité, mais si les deux x et y sont partagés vous avez un problème majeur et aura besoin d'une serrure pour le résoudre.

OriginalL'auteur Ben Voigt