J'ai besoin de la structure de données ci-dessus pour une application que j'écris. Je me demandais s'il y a une bibliothèque qui l'implémente déjà ou si je dois l'écrire moi-même?Liste chaînée double sécurisée C++ thread
Je ne veux pas vraiment réinventer la roue si ce n'est pas nécessaire.
J'ai besoin de cette structure pour pouvoir ajouter et supprimer des éléments en utilisant plusieurs threads sans avoir à verrouiller toute la structure en même temps.
Lien vers une recherche connexe: Is a lock (wait) free doubly linked list possible?
Comme vous ne demandez pas un conteneur sans serrure, je ne suis pas marquais cela comme une copie exacte. Remarque: bien que les caractéristiques d'interface et de performance ressemblent à une liste à double liaison, ces structures sont très complexes en interne, basées sur des tables de hachage ou d'autres structures. Il n'y a rien qui aurait une double liste liée en interne et serait verrouiller libre en même temps. Je ne me souviens pas d'avoir vu une preuve, mais je pense que ce n'est pas possible. Sur la base de vos informations supplémentaires, je pense que vous n'avez pas du tout besoin d'une double liste chaînée. Vous pouvez utiliser le Windows API single linked list instead. Pour ajouter utiliser InterlockedPushEntrySList, pour supprimer pour le traitement utiliser InterlockedPopEntrySList.
Oui! InterlockedSLists sont extrêmement rapides et sont déjà intégrés au système d'exploitation –
Peut-être, mais je pense que c'était l'une des leçons apprises au début de Java - la synchronisation des données n'est généralement pas au niveau de la fonction membre du conteneur, mais une étape ci-dessus. Vous devriez utiliser des objets de synchronisation avant d'accéder à une liste non-thread-safe à la place.
Tenir compte:
ThreadSafeQueue tsq;
tsq.push_back(...); // add lots of data
...
// Find the first element that returns true for search_criteria(elem);
auto iter = tsq.find_if(search_criteria);
// (1)
if(iter != tsq.end()) // (2)
{
tsq.erase(iter);
}
Dans cette file d'attente thread-safe, il y a encore deux "lacunes" où la file d'attente peut être modifié par un autre thread. Et, en effet, votre itérateur peut être invalidé par ces changements. Maintenant, comparez:
Queue q;
q.push_back(...); // add lots of data
...
// Create some lock around a pre-existing mutex.
Lock lock(q_mutex);
// Find the first element that returns true for search_criteria(elem);
auto iter = q.find_if(search_criteria);
if(iter != q.end())
{
q.erase(iter);
}
// lock unlocks as it goes out of scope.
ici parce que le verrou a une plus grande granularité, il est possible d'assurer la cohérence entre l'algorithme écrit.
cela fonctionnerait-il http://www.boost.org/doc/libs/1_41_0/doc/html/boost/interprocess/message_queue.html?
Il existe beaucoup de papiers sur l'écriture de files d'attente sans verrous utilisant des intrinsèques d'assemblage/de compilation pour effectuer des opérations atomiques, mais il est vraiment difficile de le faire fonctionner.
Donc, si vous pouvez utiliser des serrures, peut-être utiliser quelque chose comme ceci: Concurrent FIFO Queue with Boost
Pouvez-vous écrire ce que les opérations avez-vous vraiment besoin de la structure? Peut-être n'avez-vous pas vraiment besoin d'une double liste chaînée et une autre structure pourrait aussi fonctionner? – Suma
Comment le thread est-il sûr? Vous voulez écrire à des positions arbitraires à partir de threads arbitraires? –
À quelle vitesse souhaitez-vous que l'ajout et le retrait soient effectués? À première vue, il semble que ce soit une table de hachage qui pourrait fonctionner pour vous. Les tables de hachage sûres et évolutives sont courantes - il suffit d'en rechercher. – Suma