Décrémentation et test atomique en C

Question

J'implémente un système de comptage de références en C qui doit fonctionner avec plusieurs threads. Par conséquent, j'ai besoin d'un moyen de décrémenter un compte de référence intégral et de tester si le résultat est zéro avec une opération atomique. Je peux utiliser C11 et stdatomic.h, mais il ne semble pas y avoir d'opération de décrémentation et de test.

Quelle est la meilleure façon (c'est-à-dire la plus portable) d'y parvenir? Puis-je utiliser les fonctions stdatomic.h pour y parvenir?

---

C'est le cœur du comptage de référence (pseudo-code):

retain(object) { 
    ++object.ref_count; // pretty easy to make this atomic 
} 

release(object) { 
    if (--object.ref_count == 0) // need this to be atomic also 
     free(object) 
} 

Answer 1

Vous semblez avoir un misconsception des Atomics de C11. Atomic qualifie un type, pas une seule opération.

Si vous déclarez votre variable avec _Atomic toutes les opérations sur elle sont atomiques. Donc, si vous êtes satisfait de la "cohérence séquentielle" par défaut des opérations atomiques (ce que vous devriez faire), une qualification additionnelle _Atomic est tout ce dont vous avez besoin. Et l'opérateur préfixe -- devrait fonctionner correctement pour ce dont vous avez besoin.

Si vous souhaitez traiter différents types de cohérence, vous pouvez utiliser atomic_fetch_sub, par ex. Seulement cela alors vous obtenez la valeur avant la modification et non celle après. Donc, au lieu de comparer à 0, vous devriez alors le comparer à 1.

Answer 2

Désolé de pleuvoir sur le défilé, mais ceci peut être fait en utilisant le mécanisme ci-dessus, quelles que soient les primitives d'incrémentation/décrémentation atomique utilisées.

L'instant que release-ce que le free, l'objet devient invalide [il faut supposer qu'un autre thread fait une malloc instantanée et réaffecte la mémoire] et pas accès futur peut être fait par un thread. Après le free, aucun retain ou release ne peut être appelé pour cet objet. Même pas simplement de sonder la valeur ref_count. Le simple ref_count inc/dec [atomique ou non] est insuffisant pour gérer/empêcher cela.

(1) Le verrou inter-thread doit résider en dehors de l'objet et ne doit pas être soumis à une allocation/libre. (2) L'accès au (x) objet (s) doit être effectué via une sorte de traversée de liste. Autrement dit, il existe une liste d'objets actifs.

(3) L'accès à la liste est contrôlé par un mutex. A cause de cela, le réel inc/dec [probablement] ne pas besoin d'être atomique [mais pourrait être pour plus de sécurité]

(4) L'utilisation de la liste assure qu'une fois qu'un objet a été détruit, aucun thread ne sera essayez d'y accéder, car il a été supprimé de la liste des objets actifs et les threads ne peuvent plus le "voir".

Le retain et release doit faire quelque chose comme:

int 
retain(List *list,Object *object) 
{ 
    int match = 0; 

    lock_list(list); 

    for (objnow in list) { 
     if (objnow is object) { 
      ++objnow.ref_count; 
      match = 1; 
      break; 
     } 
    } 

    unlock_list(list); 

    return match; 
} 

int 
release(List *list,Object *object) 
{ 
    int match = 0; 

    lock_list(list); 

    for (objnow in list) { 
     if (objnow is object) { 
      match = 1; 
      if (--objnow.ref_count == 0) { 
       unlink_from_list(list,objnow); 
       free(objnow); 
       match = -1; 
       break; 
      } 
     } 
    } 

    unlock_list(list); 

    return match; 
} 

La méthode mutex/verrouillage ci-dessus sur la liste peut aussi être fait avec RCU mais qui est un peu plus compliqué.

Bien sûr, "list" n'a pas besoin d'être une simple liste chaînée. Ce pourrait être un arbre B ou un autre type de conteneur.

Une notion: En fait, quand on pense à ce sujet, si un objet est pas attaché à une sorte de liste globale/interthread, le ref_count tend à perdre son sens. Ou plus important encore, pourquoi y aurait-il des conflits inter-threads sur ref_count?

Si nous avons simplement quelques objets « flottants » qui sont pas sur une liste [ou qui sont sur une liste locale par thread], pourquoi plusieurs threads essayer de haut/bas du ref_count car il est plus probable que un seul thread "posséderait" l'objet à ce moment-là.

Dans le cas contraire, il peut être nécessaire de réarchiver le système pour le rendre plus prévisible/stable.

---

MISE À JOUR:

Un fil peut ne pas cogner le compte de référence à moins qu'il ait déjà une référence, car il faut une référence pour accéder à l'objet.

En ayant une référence, ici, je suppose que vous voulez dire que le fil a fait un retain, fera des choses, puis faites un release. Par conséquent, si le compteur ref atteint zéro, aucun thread n'accède actuellement à l'objet et aucun thread ne le fera à l'avenir. Ainsi, il est prudent de le détruire.

Il peut être sûr de le détruire, mais il n'y a pas d'interverrouillage contre plusieurs threads accédant aux cellules de données [non verrouillées] dans l'objet et entrant en collision.

Le problème est d'avoir un sous-thread faire un free.

Considérons que nous avons un fil conducteur et il crée un objet obj1 et qui obtient transféré vers deux fils tA et tB qui s'y réfèrent en interne comme objA et objB respectivement.

Le thread principal démarre obj1 avec une référence de zéro.

Tenir compte de la chronologie suivante:

tA: retain(objA) 
tA: // do stuff ... 
tA: release(objA) 

Le refcount objet est maintenant zéro et la zone de mémoire a été libéré. Tout autre accès est invalide. tB ne peut pas accéder à la zone de mémoire pour obj1 en aucune façon.

Maintenant, nous faisons [si nous choisissons d'ignorer]:

tB: retain(objB) 
tB: // do stuff ... 
tB: release(objB) 

version de tB verra le refcount aller à zéro et fera le free. Ceci est un à doublefree de obj1

Mais, tB ne peut même pas faire la retain parce que la mémoire pour obj1 peut avoir été réaffectés par un autre fil: (1) Le fil conducteur pour un obj2 ou (2) un autre tX fil qui utilise la mémoire dans un but tout à fait sans rapport avec

Dans le cas de (1), l » objBtB est en train de changer obj2 au lieu de obj1

Dans le cas de (2), objB gribouille sur la zone de mémoire non apparentée tX. Même une inc/dec momentanée est désastreuse. Ainsi, dans ce qui précède, il existe des conditions de concurrence, l'accès à la mémoire déjà libérée, le double-libre et l'écriture (par exemple) objtype_x comme si elle était objtype_a. Alors, que se passe-t-il si le thread principal est initialisé avec un refcount de un au lieu de zéro?

Maintenant, les choses fonctionnent mieux. Les conditions de course sont éliminées. Mais, tA et tB sera jamais voir refcount drop ci-dessous un, donc ni d'entre eux fera jamais un free. Donc, ayant les threads individuels faire le free est un point discutable.

Le thread principal devra faire le free, ce qui serait sûr. Mais, principal n'a aucun moyen de savoir dans quel état obj1 est en. Autrement dit, a-t-il été traité par tA, tB, ou les deux?

Alors, peut-être l'objet a besoin d'un masque done qui obtient un OU logique [atomiquement] avec 1 << tA et 1 << tB et principal se penchera sur ce savoir quand il peut faire la free

Ou, le fil conducteur, si il sait que seuls les deux threads tA et tB accéderont à l'objet, il pourrait initialiser le refcount à deux et les deux threads pourraient simplement faire un release quand ils sont faits avec l'objet.

Cela ne fonctionne pas très bien si tB décide qu'après avoir effectué son propre traitement, il doit envoyer l'objet à tC.

Avec un refcount, si l'objet donné doit être traitée par tAavanttB, il n'y a pas moyen d'y parvenir. D'un point de vue architectural, tout ce système pourrait fonctionner mieux si chaque thread avait une file d'attente/une liste d'entrée [qui est verrouillée en mutex]. Le thread principal crée un objet, le met en file d'attente à tA.tA le supprime, fonctionne, et le met en attente à tB. Chaque thread peut faire une fourchette "Y". C'est, tA regarde l'objet et décide de l'envoyer à tC, en contournant tB entièrement. En fin de compte, l'un des threads met en file d'attente l'objet au thread principal (c'est-à-dire la liste libre pour les objets épuisés ou pour afficher un résultat à main (par exemple une forme de map/reduce)).

Mettre un objet sur une liste libre [réutilisable] (vs faire free) eas les choses un peu parce que nous n'avons pas l'effet « tapis de traction » de faire un free [avec malloc immédiat], afin que nous puissions stocker certaines informations d'état dans l'objet qui reste même si l'objet est "inactif". Donc, nous avons l'effet d'un système de pipeline inter-thread. L'une des vertus de cette approche [que j'ai utilisée avec succès dans l'expédition de systèmes de production] est qu'une fois qu'un objet est mis en file d'attente sur un thread, le thread "possède" l'objet et la majeure partie de l'accès n'est pas nécessaire. atomique.