Je recherche un équivalent de Lwarx et de STWCX (comme l'indique les processeurs PowerPC) ou un moyen de mettre en œuvre des fonctionnalités similaires sur la plate-forme X86. De plus, où serait le meilleur endroit pour découvrir de telles choses (c'est-à-dire des bons articles / sites Web / forums pour la programmation de verrouillage / sans attente).
Modifier J'ai vraiment besoin de quelque chose qui imite lwarx et stwcx assez précisément pour retirer cela (je ne peux pas Déterminez un moyen de faire cela avec le comparaisonxchange, échanger ou ajouter des fonctions que j'ai jusqu'à présent trouvées pour le x86). merci
Je pense que je devrais peut-être donner plus de détails car il est supposé que je cherche simplement une opération de CAS (comparer et échanger). Ce que j'essaie de faire est d'implémenter un système de comptage de référence sans verrouillage avec des pointeurs intelligents pouvant être accessibles et modifiés par plusieurs threads. J'ai essentiellement besoin d'un moyen de mettre en œuvre la fonction suivante sur un processeur X86.
6 Réponses :
x86 ne supporte pas directement "la simultané optimiste" comme PPC, la prise en charge de la concurrence de X86 est plutôt basée sur un "préfixe de verrouillage", voir ICI . (Certaines instructions "atomiques" telles que XCHG obtiennent en fait leur atomicité en affirmant intrinsèquement le préfixe de verrouillage, que le programmateur de code de montage ait réellement codé ou non). Ce n'est pas exactement "anti-bombe", de le dire diplomatiquement (en effet, c'est plutôt sujet à un accident, je dirais; -).
Vous recherchez probablement la famille d'instructions CMPXCHG.
Vous devez précéder ceux-ci avec une instruction de verrouillage pour obtenir un comportement équivalent.
aperçu ici pour un aperçu rapide de ce qui est disponible.
Vous vous retrouverez probablement avec quelque chose de similaire à celui-ci: vous devez lire Ce papier ... < / p> En réponse à la question mise à jour, cherchez-vous à faire quelque chose comme le Boost Shared_ptr ? Si tel est le cas, consultez ce code et les fichiers dans ce répertoire - ils vous obtiendront certainement.
Ces 2 liens sont assez bons (effectivement trébuchés sur ces mêmes pages il y a quelques jours), mais malheureusement pas ce que je cherche (j'ai mis à jour la question pour mieux refléter cela)
Comme Michael mentionné, ce que vous recherchez probablement est l'instruction Il est important de souligner que la méthode PPC d'accomplissement de cela est connue sous le nom de Charger le lien / Store conditionnel (LL / SC), tandis que l'architecture X86 utilise comparer et échanger (CAS). LL / SC a une sémantique plus forte que la CAS dans laquelle toute modification de la valeur à l'adresse conditionnée entraînera l'échec du magasin, même si l'autre modification remplace la valeur de la même valeur que la charge a été conditionnée. CAS, d'autre part, réussirait dans ce cas. Ceci est connu comme le problème ABA (voir le lien CAS pour plus d'informations).
Si vous avez besoin de la sémantique la plus forte sur l'architecture X86, vous pouvez l'approcher de l'instruction X86S à double largeur de comparaison-and-Swap (DWCAS) CMPXCHG .
CMPXCHG8B ou CMPXCHG16B sous x86_64. Cela vous permet d'échanger atmériquement deux mots consécutifs de «taille naturelle» à la fois, au lieu de simplement l'habitude. L'idée de base est l'un des deux mots contient la valeur d'intérêt, et l'autre contient un «nombre de mutations» toujours incrémenté. Bien que cela n'éliminait pas techniquement le problème, la probabilité que le compteur de mutation envelopper entre tentatives est si faible qu'il s'agit d'un substitut raisonnable à la plupart des fins.
Dcas a presque l'air à droite, sauf que je dois changer 1 mot que si un pointeur sur ce mot ne change pas en faisant cela (c'est un peu déroutant, espérons que la mise à jour de la question aide à clarifier cela).
J'ai réussi à trouver une solution de contournement à l'aide de Dcas, ce n'est pas infaillible, car il utilise une carte d'identité unique (4 octets de taille), mais les chances de la rupture sont minces car les 4 octets UID et le compteur 4 octets adjacents doivent être reproduits exactement. Ce n'est qu'un problème si quelque chose supprime que l'objet réaffecte de la mémoire à quelque chose d'autre, puis parvient à dupliquer ces 8 octets, tandis qu'un autre thread tente de copier un pointeur, qui est une opération relativement courte (fonctionnement sage qui est la longueur de la longueur. assez si le fil est interrompu)
Je ne connais pas le PPC en particulier, mais sur la plupart des machines, les instructions exclusives / stockées de stockage / stockage ne vous aident pas vraiment au problème ABA, car les opérations de mémoire effectuées entre une charge exclusive et conditionnelle de stockage peuvent provoquer le magasin. - Fonctionnement maîtressaire pour échouer spontanément. Si on relie l'emplacement gardé et voit que cela a changé, on peut dire que quelque chose d'autre l'a écrit avec une nouvelle valeur, mais s'il tient la même valeur que sur la lecture précédente, il n'y aura aucun moyen de distinguer une défaillance spontanée de un aba écrit.
Lorsque vous faites quelque chose comme un insert de liste liée, dont le protocole nécessiterait de lire un ancien pointeur, le stockant dans un nouvel élément de la liste, puis mettant à jour l'ancien pointeur pour référencer le nouvel article, une écriture ABA externe pourrait être un danger, mais sur du code de machines qui tente de lx l'ancien pointeur, stockez-le sur le nouvel élément et SC Le nouveau pointeur pourrait boucler sans fin, même sans interférence extérieure, si, par exemple, Les anciens et les nouveaux objets habitent la même ligne de cache ou habitent des lignes de cache qui ont certaines bits d'adresse en commun. Notez qu'une implémentation LL / SC pourrait légitimement ...
... J'ai n'importe quel magasin à une mémoire partagée qui a lieu entre un LX et un SC invalidez ce dernier [une telle mise en œuvre, bien que simple, suffisait dans de nombreuses situations, en particulier dans les architectures numa où les transformateurs seraient Gardez la plupart de leurs données dans la mémoire locale, ou dans les cas où il n'y a qu'un seul noyau de processeur principal et que des périphériques peuvent mettre à jour la mémoire mais ne l'inverse généralement pas avec un flux continu d'écritures de mémoire.
@supercat Cela remonte à une foire alors que maintenant (n'ont pas travaillé sur PPC en années) mais IIRC, l'instruction LWARX gère correctement le problème ABA car elle devient invalide sur toute opération de mémoire de la ligne de cache cible, à l'exception de la correspondance STWCX. appel. Cela ne vérifie pas la valeur de l'adresse, mais si elle a été consultée. Considérant que c'est le seul moyen de mettre en œuvre des opérations atomiques sur le PPC, ce serait idiot si ce n'était pas aba
@GantTreters: pour une séquence LX / SC pour être utile pour n'importe quoi Il doit toujours être possible pour le SC de réussir en l'absence d'interférences d'autres threads, et pour deux ou plusieurs threads qui tentent simultanément Lx / sc d'avoir au moins un succès. Sur de nombreuses plates-formes, cela impose de graves limites sur quel code peut faire entre un LX et SC. Si le code a besoin de lire une variable et de stocker les choses en dérivées dans d'autres variables avant de mettre à jour de manière conditionnelle l'original, il se peut que l'acte de mise à jour de ces autres variables entraînerait le LX / SC toujours échoue ( Dans une simpliste ...
... Mise en œuvre, Tout magasin pourrait invalider un LX / SC en attente). Un LX / SC restreint à une telle mode pourrait toujours être utilisable pour synthétiser des opérations telles que le compartiment et le swap, mais les CAS ne sont pas en sécurité. D'autres implémentations pourraient être en mesure de faire davantage entre un LX et SC, mais je ne connais pas les conventions standard pour ce qui serait garanti. Par exemple, si l'on essaie de faire une mise à jour de liste liée et que le nouvel élément arrive à partager une ligne de cache avec l'ancien, la séquence "lx (temp = old_item.link); new_item.link = Temp; SC (old_item .Link = new_item) "pourrait ne jamais être capable de réussir.
Si on avait un système où charges ne pourrait jamais invalider un LX en attente, il pourrait être possible de coder des algorithmes entièrement aba-sûreté de manière à ce qu'aucun magasin ne soit nécessaire entre un LX et un SC, Mais je ne sais pas que de tels algorithmes pouvaient être immunisés à la serrure en direct sans ajouter de retards aléatoires.
Qu'est-ce que vous essayez de faire ne fonctionnera pas comme vous vous attendez. Ce que vous avez implémenté ci-dessus peut être effectué avec la fonction InterlockedIncrement (fonction Win32; Assemblage: XADD).
La raison pour laquelle votre code ne fait pas ce que vous pensez que c'est qu'un autre thread peut toujours modifier la valeur entre la deuxième lecture de * PTR et STWCX sans invalider le STWCX.
le "if (pval! = PTR) continue;" est en sécurité parce que chaque fois qu'un autre thread change un pointeur intelligent, il modifiera également le compteur que sa pointe de pointe, il va également invalider le STWCX comme cette valeur est modifiée et que Ce qui est surveillé pour le changement (nécessite juste une structuration minutieuse)
Vous avez vraiment besoin de poster de l'autre côté aussi, alors. J'ai juste essayé de construire une réponse, mais il y avait trop de devinations impliquées. Habituellement, ces types de problèmes peuvent être résolus à l'aide de CAS.
Si vous êtes sur 64 bits et limitez-vous à dire 1 To de tas, vous pouvez emballer le compteur dans les 24 bits supérieurs inutilisés. Si vous avez des pointeurs alignés par Word, les 5 bits inférieurs sont également disponibles.
La mémoire ne doit pas nécessairement être attribuée au tas le plus bas, vous ne pouvez donc pas en être sûr, sauf si vous spécifiez les adresses vous-même (que je suis), malheureusement, je ne suis pas sur une plate-forme 64 bits, Mais cela pourrait être utile à l'avenir.
Je ne sais pas si Lwarx et STWCX invalident toute la ligne de cache, CAS et DCAS. Ce qui signifie que si vous êtes prêt à jeter beaucoup de mémoire (64 octets pour chaque pointeur "verrouillable" indépendant), vous ne verrez pas beaucoup d'amélioration si vous poussez vraiment votre logiciel dans le stress. Les meilleurs résultats que j'ai vus jusqu'à présent étaient lorsque les gens sont consciemment basés à 64b, ont planifié leurs structures autour de celle-ci (des trucs d'emballage qui ne feront pas l'objet de contentions), ont gardé tout allant sur les limites de 64b et ont utilisé des barrières de données de lecture et d'écriture explicites. La ligne de cache Invalidation peut coûter environ 20 à 100 cycles, ce qui en fait un problème de performance réel plus important, puis il suffit de verrouiller l'évitement.
En outre, vous devez planifier une stratégie de répartition de la mémoire différente pour gérer l'une ou l'autre des fuites contrôlées (si vous pouvez partitionner du code dans le traitement de la requête logique - une demande "fuites" puis libère tout ce qu'il est en vrac de mémoire à la fin) ou Gestion de l'allocation de datailed, de sorte qu'une structure de la conflit ne reçoive jamais de mémoire réveillé par des éléments de la même structure / collection (pour empêcher ABA). Une partie de cela peut être très intuitive mais c'est soit ça, soit payer le prix de GC.
Oui, c'est une sorte de non-question de nos jours, à la fin, j'ai opté pour plus de gestion manuelle et de former le reste des codeurs de l'entreprise comment faire correctement le multi-threading via un couple de structures libres de verrouillage facilitant inter -Thread Communication.