Pile sans verrouillage: problème de visibilité lors de la vérification des indicateurs de danger pendant le bruit()?

Question

Je suis en train de lire les d'Anthony William en simultané en action. Le chapitre 7 décrit le processus de développement d'une pile sans verrou et illustre les problèmes courants qui rendent la programmation sans verrous difficile. Plus précisément, la section 7.2.3 (Détecter les nœuds qui ne peuvent pas être récupérés à l'aide des pointeurs de danger) décrit comment les pointeurs de danger peuvent être utilisés pour éviter une course de données et s'assurer que les autres threads ne sont pas référencés par un autre thread.

Ce code est l'une des itérations de pop() illustrés dans ce chapitre:

std::shared_ptr<T> pop() 
{ 
    std::atomic<void*>& hp = get_hazard_pointer_for_current_thread(); 
    node* old_head = head.load(); 

    do 
    { 
    node* temp; 

    do 
    { 
     temp = old_head; 
     hp.store(old_head); 
     old_head = head.load(); 
    } while(old_head != temp); 
    } 
    while(old_head && 
    !head.compare_exchange_strong(old_head,old_head->next)); 

    hp.store(nullptr); 
    std::shared_ptr<T> res; 

    if(old_head) 
    { 
    res.swap(old_head->data); 

    if(outstanding_hazard_pointers_for(old_head)) 
    { 
     reclaim_later(old_head); 
    } 
    else 
    { 
     delete old_head; 
    } 

    delete_nodes_with_no_hazards(); 
    } 

    return res; 
} 

J'ai un doute sur ce fragment:

if(outstanding_hazard_pointers_for(old_head)) 
    { 
     reclaim_later(old_head); 
    } 
    else 
    { 
     delete old_head; 
    } 

Le but des pointeurs de danger est de se assurer old_head est supprimé lorsque aucun autre thread ne l'utilise encore. La mise en œuvre proposée de outstanding_hazard_pointers_for est la suivante:

unsigned const max_hazard_pointers=100; 
struct hazard_pointer 
{ 
    std::atomic<std::thread::id> id; 
    std::atomic<void*> pointer; 
}; 
hazard_pointer hazard_pointers[max_hazard_pointers]; 

bool outstanding_hazard_pointers_for(void* p) 
{ 
    for(unsigned i=0; i < max_hazard_pointers; ++i) 
    { 
    if(hazard_pointers[i].pointer.load() == p) 
    { 
     return true; 
    } 
    } 

    return false; 
} 

Fondamentalement, le tableau de pointeurs de risque est analysé pour vérifier si le pointeur vers le noeud recherché est présent. Je me demande pourquoi cette opération est sûre. Un load() atomique est effectué et même si l'ordre séquentiellement cohérent est utilisé, load() peut charger une valeur périmée. En conséquence, p peut ne pas être trouvé, et pop() supprimerait un nœud qui est toujours utilisé.

Imaginez ce qui suit se produit:

• thread A commence à exécuter pop() et est préempté juste avant d'exécuter:

  while(old_head && 
      !head.compare_exchange_strong(old_head,old_head->next)); 
  

  Discussion A voit donc la tête actuelle comme old_head, qui est enregistré dans son indicateur de danger. old_head sera déréférencé lorsque le thread se réveille et tente de faire apparaître la tête head.compare_exchange_strong(old_head, old_head->next).

• Fil B commence l'invocation pop() jusqu'à

  if(outstanding_hazard_pointers_for(old_head)) 
  

  old_head sera la tête courant de la pile, qui est le même nœud que le fil A fait référence en tant que old_head. Discussion B pasdelete old_head ssi a load() sur le pointeur de danger de fil Renvoie la dernière valeur stockée par fil A.

En gros: Je me demande si le thread B peut load() une valeur rassis au lieu de la plus récente . Dit d'une autre manière, je ne sais pas pourquoi a pour retourner la valeur définie par Thread A (old_node).

Où est la faille dans ce raisonnement? Je ne peux pas trouver une justification pour savoir pourquoi hp.store(old_head) sur un autre thread arrivera avant hazard_pointers[i].pointer.load().

Answer 1

Je réponds à ma propre question pour deux raisons: je pense que la réponse que j'ai acceptée n'est pas très claire, et JJ15k's comment confirme cette impression.

Fondamentalement, la clé est que pour un autre observe fil pour le faire à travers if(outstanding_hazard_pointers_for(old_head))et voir le même old_head vu par un autre thread qui a été préempté avant d'exécuter while(old_head && !head.compare_exchange_strong(old_head, old_head->next)), il doit avoir exécuté head.compare_exchange_strong(old_head, old_head->next) avec le même old_head. Mais (en supposant < indique une arrive, avant relation):

thread A: hp.store(old_head)  < 
thread A: old_head = head.load() < 
thread B: head.compare_exchange_strong(old_head, old_head->next) 

Rappelez-vous que le fil B voit le mêmeold_head nous avons chargé dans la première instruction et il est permutant sa valeur à old_head->next. Nous voyons toujours la même valeur dans head.load(), c'est pourquoi il Thread A hp.store(old_head) arrive-avant le fil B compare_exchange_strong.

Le fil qui est sur le point de vérifier si la tête contenue dans le pointeur de danger peut être supprimée a pour voir old_head. Notez également le rôle fondamental joué par old_head = head.load() (et la boucle qui contient ces instructions qui peuvent sembler redondantes à première vue). Sans cette opération load, il n'y aurait aucune relation qui se produit avant entre store de old_head en hp et le compare_exchange_strong.

J'espère que cela répond à votre question.

Answer 2

Ma compréhension du code est la suivante.

Si hp.store(old_head) dans un autre thread NE PAS se produire-avant l'appel hazard_pointers[i].pointer.load() dans ce fil, cela signifie que ce fil a effectué avec succès head.compare_exchange_strong(old_head,old_head->next) appel. Cela signifie que pour un autre thread old_head != temp, il effectuera une autre tentative pour stocker un old_head approprié en tant que hp d'un thread.

Et cela signifie que le pointeur old_head d'origine dans le thread en cours peut être supprimé en toute sécurité, car il n'est pas réellement utilisé par un autre thread.