Thread-safe vecteur
Permettez-moi de commencer par dire que j'ai lu la plupart, et d'autres rubriques sur le sujet.
La façon dont je comprends les choses, std::vector sera réallouer la mémoire lors de la repousse de nouveaux éléments, ce qui est mon cas, à moins que j'ai réservé un espace suffisant (ce qui est pas mon cas).
Ce que j'ai est un vecteur de std::shared_ptr, et que le vecteur est titulaire d'objets uniques (ou, plus correctement, des pointeurs vers des objets uniques dans le vecteur).
À la manipulation de ces objets via des pointeurs est enroulé autour d'une Usine & classe de Gestionnaire, mais les pointeurs vers les objets sont accessibles depuis l'extérieur de la classe wrapper et peut avoir des valeurs de membre modifiés. Il n'y a pas de suppression de passe à tout moment.
Si je suis bien comprendre les questions soulevées dans la précédente, DONC des questions à propos de std::vector et le fil de sécurité, en ajoutant (push_back) de nouveaux objets peut invalider précédente pointeurs, comme le vecteur de l'interne peut réallouer de la mémoire et de la copie de tout, ce qui serait évidemment une catastrophe pour moi.
Mes intentions sont à lire à partir de ce vecteur, souvent la modification des objets à travers les pointeurs, et ajouter de nouveaux éléments dans le vecteur, à partir de threads s'exécutant de manière asynchrone.
Donc,
- À l'aide atomique ou mutex n'est pas assez? Si je pousse arrière à partir d'un fil, un autre thread de la manipulation d'un objet via un pointeur peut-être un objet invalide?
- Est-il une bibliothèque qui peut gérer cette forme de MT questions? Celui que j'ai garder la lecture sur est Intel TBB, mais depuis que je suis déjà à l'aide de C++11, j'aimerais conserver les modifications à un minimum, même si cela signifie plus de travail de ma part - je veux apprendre dans le processus, et non pas simplement copier-coller.
- Autre que le verrouillage de l'accès, tandis que la modification d'objets, je voudrais asynchrone parallèle de l'accès en lecture pour le vecteur qui ne sera pas invalidé par push_backs. Comment puis-je y parvenir?
Si il est de toute importance, tous les ci-dessus est sur linux (debian jessie) à l'aide de gcc-4.8 avec c++11 activé.
Je suis ouvert à l'aide de mini-invasive de bibliothèques.
Merci beaucoup d'avance 🙂
std::deque
à la place? Elle a les mêmes garanties de performance, mais ne pas réaffecter lorsque vous push_back
(otoh, que, vous avez encore à protéger la push_back
avec un mutex, puisque vous êtes en train de modifier l'état interne du conteneur).Je ne me dérangerait pas d'échange pour un pont, à condition que ses interchangeable avec le vecteur sans de sérieuses modifications. Est std::deque la garantie d'être contiguë à pousser en arrière, donc la résolution de ce problème?
@MatteoItalia mentionné les files d'attente sont beaucoup mieux adapté pour protéger les opérations par thread-safe producteur/consommateur de la sémantique. Ils ne sont pas thread-safe en natif, mais vous pouvez facilement construire ce dont vous avez besoin, avec un mutex ou sémaphore, ou les deux.
L'interface est sensiblement la même (O(1) random-indice d'accès, l'accès aléatoire à des itérateurs, push/pop aux deux extrémités, ...), avec l'avantage potentiel, il est tout aussi rapide à pousser au début ou à la fin du conteneur. Le stockage n'est évidemment pas toutes contiguës (généralement, c'est fait de blocs contigus), mais cela permet d'éviter les réaffectations lorsque vous appuyez éléments.
Les valeurs à l'intérieur du conteneur sont garantis pour être conservés, il est inutile de perdre vos données lorsque vous ajoutez de nouvelles valeurs!. Ce n'est PAS la garantie d'être conservés sont les itérateurs pour le conteneur. par exemple, si vous avez lancé la numérisation du conteneur de commencer(v) à(v) et en même temps, dans un autre fil, vous v. push_back(...) - l'analyse peut échouer comme les itérateurs ne peut pas être plus valable.
OriginalL'auteur | 2014-05-12
Vous devez vous connecter pour publier un commentaire.
Non, cette opération n'est pas d'invalider toute précédente pointeurs, sauf si l'on se réfère à des adresses à l'intérieur de l'vecteurs internes de gestion des données (qui clairement n'est pas votre cas).
Si vous stockez des premières pointeurs, ou
std::shared_ptr
s'il y a, ceux-ci seront tout simplement copié, et de ne pas se invalide.Comme mentionné dans les commentaires d'un
std::vector
n'est pas très approprié pour garantir la sécurité des threads pour le producteur /consommateur modèles pour un certain nombre de raisons. Ni le stockage de brut pointeurs de référence du vivant instances est!Un File d'attente sera beaucoup mieux pour le soutenir. Comme pour les normes, vous pouvez utiliser le
std::deque
avoir ceratain points d'accès (front()
,back()
) pour le producteur /consommateur.De faire de ces point d'accès est thread-safe (pour pousser/popping valeurs), vous pouvez facilement emballer avec votre propre classe et d'utiliser un mutex, de sécuriser l'insertion/suppression d'opérations sur le partage de la file d'attente de référence.
Les autres (et les grands, à partir de votre question) le point est: gérer la propriété et la durée de vie des contenus ou des renvois, des instances. Vous pouvez également transférer la propriété à la consommation, si c'est approprié pour votre cas d'utilisation (donc de descendre de la généraux avec, par exemple,
std::unique_ptr
), voir ci-dessous ...En outre, vous pouvez avoir un sémaphore (variable d'état), pour avertir le consommateur fil, que de nouvelles données sont disponibles.
La durée de vie (et donc thread-safe utilisation) des instances stockées dans la file d'attente (conteneur partagé) ont besoin d'être gérés séparément (par ex. à l'aide de pointeurs intelligents comme
std::shared_ptr
oustd::unique_ptr
qui y sont stockées).Il peut être accompli bien du tout avec l'existant de la bibliothèque standard mécanismes à mon humble avis.
Comme pour le point 3. voir ce qui est écrit ci-dessus. Comme ce que je peux en dire davantage à ce sujet, il semble que vous demandez quelque chose comme un
rw_lock
mutex. Vous pouvez fournir un substitut pour ce qui convient avec une la variable de condition.N'hésitez pas à demander plus de précisions ...
Si vous avez déjà
shared_ptr
les intances là, vous n'aurez pas besoin de s'inquiéter à mon humble avis. Toutes les opérations de redimensionnement prendra soin de copier les contenus des valeurs, et la copie/le déplacement deshared_ptr
est sûr (pas besoin de s'inquiéter à propos d'avoir besoin profond des copies ainsi, il y a encore tout compris). Même s'applique àstd::unique_ptr
comme je l'ai mentionné, mais dépend si votre cas doit être vraiment unique (ly) produite par le producteur, et sont uniques (ly) consommée par le consommateur.Nous avons des scénarios, où l'on pour, par exemple, utiliser la bonne vieille
std::auto_ptr
transfert de la propriété dans l'interface, mais utiliser des pointeurs dans la file d'attente (depuisstd::auto_ptr
n'est pas un nice de la classe). Si vous avez besoin de manipuler lestd::auto_ptr
à la surface de la push/pop de l'interface. Le moderne pointeurs intelligents commestd::shared_ptr
gérer tout ce intrinsèquement et bien fiable.Désolé manqué adresse à vous. J'ai mis quelques explications et mise à jour de ma réponse un peu. Espérons que précise au sujet de vos idées fausses.
Je n'ai pas dit qu'il n'. Le
std::deque
est tout simplement mieux adapté pour la mise en œuvre de producteur/consommateur modèles. Je l'ai dit, il est nécessaire de protéger les insérer/supprimer des opérations avec un mutex ou semblables.OriginalL'auteur πάντα ῥεῖ
Si vous être toujours juste l'ajout de nouveaux éléments dans le conteneur et puis y accéder, de ce que vous pourriez trouver utile est un vecteur avec un autre indirection, de sorte qu'au lieu de swaping la mémoire tampon interne pour une plus grande, une fois que l'espace alloué n'est jamais libéré et un nouvel espace est simplement ajoutés en quelque sorte dans un thread-safe.
Par exemple, il peut ressembler à ceci:
La classe contient un tableau fixe de pointeurs sur des morceaux individuels de la mémoire avec les éléments, avec une augmentation exponentielle de la taille. Ici, la limite est de 6 parties, de sorte 63000 éléments - mais cela peut être changé facilement.
Le conteneur démarre avec toutes les parties des pointeurs NULL. Si un élément est ajouté, le 1er bloc est créé, avec la taille
m_baseSize
, ici 1000, et enregistré àm_parts[0]
. Les éléments suivants sont écrits là.Lorsque le bloc est plein, un autre tampon est alloué, avec deux fois la taille de la précédente (2000), et stockés dans
m_parts[1]
. Ceci est répété si nécessaire.Tout cela peut être fait à l'aide d'opérations atomiques, mais c'est bien sûr délicat. Il peut être plus simple si tous les auteurs, peut être protégée par un mutex, et seuls les lecteurs sont entièrement concurrente (par exemple, si l'écriture est beaucoup plus rare). Tous les threads de lecture toujours voir valeur NULL dans
m_parts[i]
ou NULLE à l'une des tampons, ou un pointeur valide. Les éléments existants ne sont jamais déplacés dans la mémoire, invalidés ou quoi que ce soit.Autant que les bibliothèques existantes aller, vous voudrez peut-être regarder à Fil De Blocs De Construction par Intel, en particulier de sa classe concurrent_vector. Apparemment il a fait de ces caractéristiques:
Pas besoin de bibliothèques supplémentaires ou des cadres. Ce genre de choses est assez bien sovable avant droite juste en utilisant la norme des choses.
C'est une solution pour un conteneur linéaire de stockage et rapide O(1) un accès indexé comme std::vector<>, mais qui est optimisé pour le fonctionnement parallèle (principalement lit). Tout de verrouillage du lecteur (en solutions simples avec un mutex pour la lecture et l'écriture) représenterait inutile de performances. Verrouillage uniquement lors de l'écriture n'est pas assez avec les conteneurs standard, car ils ne sont pas préparés pour l'accès simultané (dépendant de l'implémentation, vous ne pouvez pas compter sur elle).
Merci de prendre le temps d'écrire la réponse, malheureusement TBB est le dernier recours et il semble un peu de trop à mon humble avis.
tout à fait raison, je ne veux pas que les lecteurs de serrure, seulement des écrivains, alors vous avez besoin d'un lock-conteneur gratuit, πάντα souligné. J'ai été dans une situation similaire (nombre de lectures qui ont besoin d'être aussi rapide que possible, écrire chaque maintenant et puis et sont allés de l'aide d'une plaine de mutex pour R/W mutex et remarqué que, bien que toujours un rendement médiocre. J'ai eu du succès en utilisant le schéma que j'ai présenté dans la réponse, et effectivement le conteneur décrit dans le rapport du papier par Stroustrup et Intel
concurrent_vector
doit utiliser plus ou moins les mêmes techniques. C'est amusant d'écrire sans verrouillage des trucs, mais testez bien!OriginalL'auteur Yirkha
Re-lecture de la question, la situation semble un peu différent.
std::vector
est mal adapté pour le stockage de objets à qui vous auriez à garder les références, depuis unpush_back
peut invalider toutes les références à des objets stockés. Mais, il s'agit d'un tas destd::shared_ptr
.La
std::shared_ptr
stockés à l'intérieur doit gérer le redimensionnement gracieusement (ils sont déplacés, mais pas les objets qu'ils pointent vers) aussi longtemps que, dans les discussions, vous ne gardez pas les références àstd::shared_ptr
s stocké à l'intérieur du vecteur, mais vous gardez copies.À la fois à l'aide de
std::vector
etstd::deque
vous devez synchroniser l'accès à la structure de données, depuis unpush_back
, mais pas de référence-l'invalider, modifie la structure interne de ladeque
, et n'est donc pas autorisé à exécuter simultanément avec une deque accès.Otoh, que,
std::deque
est probablement mieux de toute façon pour des raisons de performance; à chaque redimensionnement que vous vous déplacez autour d'un lot destd::shared_ptr
, qui peut avoir à faire à un blocage de l'incrémenter/décrémenter le refcount en cas de copier/supprimer (s'ils sont déplacés - comme ils le devraient - ce qui devrait être élidés - mais YMMV).Mais le plus important, si votre utilisation de
std::shared_ptr
est juste pour éviter les mouvements potentiels dans le vecteur, vous pouvez le déposer complètement lors de l'utilisation d'undeque
, puisque les références ne sont pas invalidées, de sorte que vous pouvez stocker vos objets directement dans ledeque
au lieu d'utiliser des tas d'allocation et de l'indirection/surcharge destd::shared_ptr
.std::shared_ptr
tandis que redimensionnement? Je peux voir la copie à partir d'un vecteur avec un bizarre allocateur de causer des problèmes, mais redimensionnement?L'important, c'est la distinction que vous faites (ce que j'ai été inquiet à propos de). Autant que je sache, des vecteurs lors de l'insertion, de les redimensionner et de les re-allouer de la mémoire. Tous mes pointeurs vers des objets proviennent de ce vecteur, comme l'usine de la classe qui s'enroule autour de lui, le fils. Ainsi, dans le cas d'un thread à l'aide de l'un de ces pointeurs, et l'autre insère un nouveau (et donc le vecteur de réallouer), ce qui se passe à l'objet en cours accessible à partir de la première thread? J'ai vu des problèmes similaires (pas de fil) lors de l'insertion d'objets dans un vecteur lors de l'itération.
s'inquiéter de ce qui se passe ...' Voir les précisions sur ma réponse. Espérons que cela résout vos malheurs ...
vous ne devriez pas garder un pointeur vers un élément dans le vecteur, mais une copie de celui - ci- c'est à dire un
std::shared_ptr
de l'objet réel qui vous intéresse. Même si l ' "original"std::shared_ptr
est déplacée autour en raison de vecteur réaffectations, chaque copie locale restera toujours, et de garder pointant vers le même objet dans le tas (ce qui est totalement épargnée par l'ensemble de la chose).Je ne sais pas, relata refero (voir Jean Dibling commentaire dans la réponse, où il remarque que la copie et supposé-déplacer les temps sont identiques).
OriginalL'auteur Matteo Italia