Google 关于“无锁矢量”的第一个结果是由 Damian Dechev、Peter Pirkelbauer 和 Bjarne Stroustrup 合着的一篇研究论文，描述了理论上的无锁矢量。是否已经实现了这个或任何其他无锁向量？
问问题
5625 次
2 回答
0
MS 提供 ppl::concurrent_vector，英特尔提供 tbb::concurrent_vector。在 Windows 上，至少 ppl 和 tbb 是 C-Runtime 的一部分。
于 2012-02-21T22:14:30.410 回答
-8
我刚刚在维基百科中查找了向量是什么。
我认为（请注意，只需一两分钟的思考）完全无锁的版本有点问题。
考虑; 您创建数组，按正常方式访问它等。为此，您不需要无锁。当您需要调整大小时，问题就来了。进来并发现这一点的线程需要malloc。这是一个真正独特的操作——此时其他线程必须阻塞/旋转。如果他们试图提供帮助，例如自己做 malloc，您可能会有很多线程发出 malloc。现在可能在实践中执行的线程数量是如此之低，这没关系 - 在这种情况下，您可能有许多线程执行 malloc，获胜者原子地激活新内存，失败者看到这个然后释放（ ) 记忆。
然后执行复制，当一个线程访问一个元素时，我们需要跟踪列表中所有分配的数组，我们通过列表访问它们，最旧的在先，直到找到元素我们想要，如果它不在最新的数组中，我们移动它然后访问它。
然后我们还需要一种方法让线程知道它已经移动了最后一个元素并可以释放该数组，所以我们必须计算元素；所以我们有潜在的无限分配要求的风险。更重要的是，数据结构（我说过一个列表，但它可能是其他东西，虽然它们不会那么好，prolly）将需要是原子的（因为也许线程可以同时删除一个数组）直到最近，原子无锁列表还是无锁数据结构的顶峰，尽管它们变得如此复杂，但需要 SMR 并具有复杂的实现。
（我说直到最近 - 有人最近发明了无锁红黑树，整个事情，添加和删除！）
TBH，我不明白为什么有人会使用矢量。为什么不只使用平衡二叉树或哈希？
于 2012-07-23T01:01:37.873 回答