多线程访问的高效结构 [英] Efficient structure for Multiple Thread access

问题描述

我需要实现一个具有数据流（此时队列）的机制，该机制包含一系列挂起请求对象的列表，这些请求对象在线程完成后被使用和取消时被不同的线程标记。

I need to implement a mechanism which has a datastruture (Queue at this moment) that contains a list of pending request objects which are marked by different threads when being used and taken off when a thread is finished using it.

这个数据结构在任何给定的时间都可以有多达几千个项目，N个线程将会从中获取请求（基本上将其标记为采用）当线程完成后，它会在结构中找到相同的请求并将其删除。

This datastructure could have up to a few thousand items in it at any given time and N threads will be taking requests from it (essentially marking it as 'taken') then when the thread is finished it will find that same request in the structure and remove it.

现在我想知道C ++ STL队列在执行此操作方面有多有效，而在需要从队列中删除相同项目时呢？

Now I was wondering how effective a C++ STL Queue would be in terms of doing this, and in terms of having to look for the same item again when needing to remove it from the queue?

我不希望这个数据结构被一个线程锁定同步机制太长，因为一个线程正在寻找一个内部的一个项目。这可能会锁定我的整个程序。 （程序需要非常高的性能和快速）

I don't want this datastructure to be locked by a Thread Synchronization mechanisms for too long because a thread is looking for an items somewhere within it. This could lock up my entire program. (The program needs to be very high performance and fast)

任何人都可以就如何在多线程环境中最佳地实现这一点建议，以使结构不会得到需要执行搜索时长时间锁定？

Can anyone advice on how to best implement this in a multi-threading environment so that the structure doesn't get locked up for long times when a search needs to be performed?

推荐答案

引用草药Sutter：

链接列表令人惊奇的是
并发友好的数据结构
，因为它们支持高度本地化的
更新。特别是，如图1所示
，要将一个新节点插入
双向链表中，您只需要
即可触摸两个现有节点;即，新节点将占用
的
将直接将新节点拼接到列表中。要
擦除一个节点，您只需要触摸
三个节点：$ b​​ $ b被删除，而它的两个立即
个相邻节点。

Linked lists are wonderfully concurrency-friendly data structures because they support highly localized updates. In particular, as illustrated in Figure 1, to insert a new node into a doubly linked list, you only need to touch two existing nodes; namely, the ones immediately adjacent to the position the new node will occupy to splice the new node into the list. To erase a node, you only need to touch three nodes: the one that is being erased, and its two immediately adjacent nodes.

除此之外，我同意您应该在处理之前将其从队列中删除的注释。但是我可能错了，因为我不知道你的申请的细节。

That aside, I agree with the comments that you should probably remove the item from the queue before processing it. But I may be wrong as I don't know the finer details of your application.

这篇关于多线程访问的高效结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！