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

问题描述

我需要实现一个机制，它有一个datastruture（队列在这一刻），包含一个挂起的请求对象的列表，当被使用时被不同的线程标记，并在线程完成使用它时被取消。

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?

推荐答案

引用 Herb Sutter：

Quoting Herb Sutter:

奇妙的
并发友好的数据结构
，因为它们支持高度本地化的
更新。特别是，如图1中
所示，要将一个新节点插入到
中一个双向链表，你只需要
触摸两个现有的节点;即
紧邻
位置，新节点将占据
将新节点接合到列表中。到
擦除一个节点，你只需要触摸
三个节点：正在
擦除的节点，其两个立即
相邻节点。

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屋！