Une solution populaire au problème ABA dans les structures de données sans verrouillage consiste à étiqueter des pointeurs avec une étiquette supplémentaire d'incrémentation monotoniquement. Cependant, cette approche a un problème. C'est vraiment lent et a d'énormes problèmes de cache. Je peux obtenir une accélération de deux fois plus si je fesse le champ Tag. Mais ceci est dangereux? P> Donc, mon prochain essai de tentative pour 64 bits plate-forme trucs des bits dans le champ PTR. P> struct aba {
uintptr __ptr;
};
uint32_t get_tag(struct aba aba) { return aba.__ptr >> 48U; }
3 Réponses :
selon le papier
http: //web.cecs.pdx. EDU / ~ WALPOLE / Classe / CS510 / Papiers / 11.PDF Pointeurs de danger: récupération de la mémoire sans danger pour les objets sans verrouillage (transactions IEEE sur des systèmes parallèles et distribués, vol. 15, no. 6, juin 2004 p. 491) par PhD Maged M. Michael
Les bits d'étiquette doivent être dimensionnés pour rendre l'enveloppe d'enveloppe dans des scénarios libres réels (je peux lire ceci comme si vous pouviez avoir des threads en cours d'exécution et que chacun peut accéder à la structure, vous devez avoir N + 1 états différents pour les étiquettes au moins):
6.1.1 Tags IBM ABA-PREVENTION
La méthode la plus ancienne et la plus simple sans verrouillage de la réutilisation du nœud est la méthode de la balise (mise à jour) introduite avec le Documentation de CAS sur le système IBM 370 [11]. Ce nécessite d'associer une étiquette avec chaque emplacement qui est le Cible des opérations de comparaison ABA-PRONE. En incrémentant La balise lorsque la valeur de l'emplacement associé est Les opérations écrites, de comparaison (par exemple, CAS) peuvent déterminer si L'emplacement a été écrit depuis qu'il a été accédé par la dernière fois par le même fil, empêchant ainsi le problème de l'ABA. La méthode nécessite que la balise contienne suffisamment de morceaux pour faire remplacement complet impossible pendant l'exécution de tout Tentative sans verrouillage unique. Cette méthode est très efficace et permet la réutilisation immédiate des nœuds à la retraite.
Il n'y a aucune garantie qu'un autre thread ne peut modifier qu'une seule fois, je pense donc que toute limite basée sur le nombre de threads ne serait pas sûre.
Le papier répertorie la condition. Avez-vous un autre papier avec un état différent?
La condition indiquée est correcte, mais je l'interprète différemment. En particulier, "l'exécution d'une tentative sans verrouillage unique" comprend le temps pendant lequel un thread est préempté et d'autres threads peuvent faire beaucoup plus qu'une opération unique pendant cette période. J'ai composé une réponse pour clarifier cela.
La quantité de bits de balises pratiquement sûres peut être estimée en fonction du temps de préemption et de la fréquence des modifications du pointeur.
Pour rappeler, le problème ABA se produit lorsqu'un thread lit la valeur qu'il souhaite modifier avec comparer-and-swap, est préempté, et lorsqu'il reprend la valeur réelle du pointeur se trouve être égal à ce que le fil a été lu avant . Par conséquent, l'opération de comparaison-et-swap peut réussir malgré les modifications de la structure de données éventuellement effectuée par d'autres threads pendant le temps de préemption.
L'idée d'ajouter l'étiquette incrémenée monotone est de faire chaque modification du pointeur unique. Pour que cela réussisse, les incréments doivent produire des valeurs d'étiquette uniques au cours du moment où un fil de modification pourrait être préempté; I.e. Pour la correction garantie, la balise peut ne pas envelopper pendant toute la durée de préemption.
Supposons que la préemption dure une seule tranche de temps de planification du système d'exploitation, qui est typiquement des dizaines de centaines de millisecondes. La latence de la CAS sur les systèmes modernes est des dizaines de centaines de nanosecondes. Une estimation si difficile la pire des cas est qu'il pourrait y avoir des millions de modifications de pointeur alors qu'un thread est préempté, et il devrait donc y avoir plus de 20 bits dans la balise afin de ne pas envelopper.
En pratique, il peut être possible de rendre une meilleure estimation pour un cas d'utilisation réel particulier, basé sur la fréquence connue des opérations de CAS. Il faut également estimer le temps de préemption du pire des cas plus précisément; Par exemple, un fil à faible priorité préempté par un travail de priorité plus élevé pourrait se retrouver avec beaucoup de temps de préemption beaucoup plus long.
Sur une note subjective, je trouve l'approche avec l'utilisation de bits d'adresse de rechange pour les valeurs de balises assez fragiles et plutôt non portable et non à la preuve future (par exemple, que si les générations de processeur futures utiliseront plus de 48 bits pour l'adressage de la mémoire) - et donc dangereux pour une utilisation pratique.
Selon votre structure de données, vous pourriez être capable de voler des bits supplémentaires des pointeurs. Par exemple, si les objets sont 64 octets et toujours alignés sur des limites de 64 octets, les 6 bits inférieurs de chaque pointeur pourraient être utilisés pour les étiquettes (mais c'est probablement ce que vous avez déjà suggéré pour votre nouveau plan).
Une autre option serait d'utiliser un index dans vos objets au lieu des pointeurs.
En cas d'objets contigus qui seraient bien sûr simplement un index dans une matrice ou un vecteur. En cas de listes ou d'arbres avec des objets alloués sur le tas, vous pouvez utiliser un allocator personnalisé et utiliser un index dans votre bloc (s) alloué (s).
Pour dire des objets 17m, vous n'auriez besoin que de 24 bits, laissant 40 bits pour les balises.
Cela aurait besoin d'un calcul supplémentaire (petit et rapide) pour obtenir l'adresse, mais si l'alignement est une puissance de 2 seulement un décalage et une addition est nécessaire.
Je sais que vous avez commencé avec une stratégie d'attribution de balises croissante monotone et que j'avoue que je ne connais pas grand chose à propos du problème, mais en général, une fonction de type hash bon marché (disons, des godets numériques distribués d'hyperlog) garantissent que le Les tags ne sont pas entrés en collision?
@ Bright-star, j'avais envisagé d'utiliser une fonction de hachage moi-même mais je ne peux pas construire un bon argument pour en utiliser un sur une incrémentation de l'étiquette. Cela semble toutefois une idée très intéressante.