我今天花了很多时间研究无锁队列.我有一个多生产者,多个消费者的情况.为了测试,我使用Win32下的Interlocked SList实现了一个系统,它使我基于线程的高度基于任务的代码的性能翻了一番.不幸的是,我希望支持多个平台.在多个平台上联锁本身不是问题,我可以安全地假设我可以毫无问题地互锁.然而,实际的实施失去了我.
最大的问题似乎是您需要保证列表推送/弹出只使用一个互锁呼叫.否则你会留下空间让另一个线程夹入并搞砸了.我不确定微软的实现如何在幕后工作,并希望了解更多.
任何人都可以指出我有用的信息(平台和语言是非常无关紧要的)？
除此之外,我很想知道它是否可以实现无锁向量.这对我来说有很大的用处:)干杯!
编辑:阅读了草药的DDJ文章,我可以看到一个减少的锁定队列,它与我已经拥有的非常相似.但是我注意到最后有一些文件可以使用双重比较和交换(DCAS)操作进行真正的无锁队列.有没有人使用cmpxchg8b(或cmpxchg16b)实现队列？
我只是在这一点上思考(没有读过论文),但你可以使用这个系统同时更新头部和尾部指针,从而避免在2个原子操作之间跳过另一个线程的任何问题.但是你仍然需要获得下一个头指针来测试尾部指针,看看你是否刚刚修改了尾部.当另一个线程准备这样做时,你如何避免另一个线程更改此信息？这是如何以无锁方式实现的？或者我最好还是阅读一篇研究论文的难以理解的内容？;)
我试图实现一个线程安全的无锁容器,类似于std :: vector,根据这个https://software.intel.com/en-us/blogs/2008/07/24/tbbconcurrent_vector-secrets-of-记忆组织
根据我的理解,为了防止重新分配并使所有线程上的所有迭代器无效,而不是单个连续数组,它们会添加新的连续块.
他们添加的每个块都具有增加2的幂的大小,因此他们可以使用log(index)来找到[index]处的项目所在的正确段.
从我收集的内容来看,他们有一个静态的指向段的指针,因此他们可以快速访问它们,但是他们不知道用户想要多少段,所以他们做了一个小的初始段,如果段的数量超过了当前计数,他们分配一个巨大的,并切换到使用那个.
问题是,添加新段不能以无锁线程安全方式完成,或者至少我还没弄明白如何.我可以原子地增加当前大小,但仅限于此.
而且从小型指针到大型段指针的切换涉及大量的分配和内存副本,所以我无法理解它们是如何做到的.
他们有一些在线发布的代码,但所有重要的功能都没有可用的源代码,它们都在他们的Thread Building Blocks DLL中.以下是一些演示此问题的代码:
template<typename T>
class concurrent_vector
{
private:
int size = 0;
int lastSegmentIndex = 0;
union
{
T* segmentsSmall[3];
T** segmentsLarge;
};
void switch_to_large()
{
//Bunch of allocations, creates a T* segmentsLarge[32] basically and reassigns all old entries into it
}
public:
concurrent_vector()
{
//The initial array is contiguous just for the sake of cache optimization
T* initialContiguousBlock = new T[2 + 4 + 8]; //2^1 + 2^2 …我正在进行我的Clojure任务(在4clojure.com上解决了大约80个问题)并继续阅读和编码并试图"得到它".
现在我对Clojure被设计为"无锁并发"感到困惑.我非常了解死锁(例如:"我编写了糟糕的Java代码,最终导致死锁",而不是"我是并发专家").我也读过这个:
我意识到Clojure程序不会陷入僵局.
但是我有点困惑:通过在引擎盖下无锁算法实现或使用可能的"死锁"算法实现了这样的壮举,但使用正确的实现保证永远不会死锁(这将以某种方式"隐藏"给Clojure程序员)？
最近讨论过关于无锁算法的黑客新闻:
http://news.ycombinator.com/item?id=4103921
在1024cores.net上引用以下"无锁算法"页面:
http://www.1024cores.net/home/lock-free-algorithms
我不明白这篇文章与Clojure下的并发工作方式之间的关系.
它让我完全糊涂了:当我在Clojure中开发并发程序时,它是否意味着"锁定和无锁算法"对我来说不是问题？
我在想,当多个线程正在读写时,是否有可能拥有无锁队列？我已经看到了一个带有无锁队列的实现,它可以使用一个读取线程和一个写入线程但不会超过一个.可能吗？我认为不是.可以/有人想要证明吗？
在一些关于算法的文章中,有些使用了这个词lockfree,有些则使用了lockless.lockless和之间有什么区别lockfree？谢谢!
更新
http://www.intel.com/content/dam/www/public/us/en/documents/guides/intel-dpdk-programmers-guide.pdf
第5.2节 - "Linux*中的无锁环缓冲区",这是使用"无锁"一词的一个例子
我一直试图谷歌我的问题,但老实说,我不知道如何简洁地陈述问题.
假设我在多核Intel系统中有两个线程.这些线程在同一个NUMA节点上运行.假设线程1写入X一次,然后只是偶尔读取它向前移动.进一步假设,线程2连续读取X. 如果我不使用内存栅栏,在线程1写入X和线程2看到更新值之间可以有多长时间？
我知道X的写入将转到存储缓冲区并从那里到缓存,此时MESIF将启动,线程2将通过QPI查看更新的值.(或者至少这是我收集到的).我假设存储缓冲区将被写入存储围栏中的缓存或者是否需要重用该存储缓冲区条目,但我不知道存储缓冲区是否已分配给写入.
最终我要为自己回答的问题是,如果线程2有可能在一个相当复杂的应用程序中看到线程1的写入几秒钟而正在做其他工作.
有没有原子|=或原子或？如果没有什么建议的技术来设置需要线程安全的变量中的位？(我在避免锁)
我有多个线程需要使用TCP流中的数据.我希望在共享内存中使用循环缓冲区/队列来从TCP套接字读取.TCP接收将直接写入循环队列.消费者将从队列中读取.
此设计应启用零复制和零锁定.但是这里有两个不同的问题.
从TCP套接字读取1条逻辑消息是否可能/有效？如果没有,并且我阅读了多条消息,我将不得不将残差复制到此 - >下一步.
是否真的可以实现无锁队列？我知道有原子操作,但这些也很昂贵.因为所有CPU缓存都需要无效.这将影响我所有24个内核的所有操作.
我在低级TCP中有点生疏,并不清楚如何判断消息何时完成.我是在寻找\ 0还是具体实现？
TY
我有一个问题,需要我使用高度并发,无等待的堆栈实现.我必须事先预先分配所有内存(没有垃圾收集或mallocs),并且堆栈的大小是可接受的(如果堆栈满,则push可能返回false).
我熟悉Nir Shavit的堆栈实现:http://citeseerx.ist.psu.edu/viewdoc/summary？doi = 10.1.1.156.8728 ......但这依赖于链表和垃圾收集.我需要一些基于数组的东西.
看起来ACM上有一个:http://dl.acm.org/citation.cfm？ id = 1532611虽然我对低下载速率和引用持怀疑态度.
理想的答案是参考代码(在C/C++中)我可以简单地窃取:-)
存在三种不同类型的“无锁”算法。并发实践中给出的定义是：
\n\n\n非正式地，“无锁”\xe2\x89\x88“不使用互斥体”==其中任何一个。
\n
我不明白为什么基于锁的算法不能落入上面给出的无锁定义。这是一个简单的基于锁的程序：
\n#include <iostream>\n#include <mutex>\n#include <thread>\n\nstd::mutex x_mut;\n\nvoid print(int& x) {\n std::lock_guard<std::mutex> lk(x_mut);\n std::cout << x;\n}\n\nvoid add(int& x, int y) {\n std::lock_guard<std::mutex> lk(x_mut);\n x += y;\n}\n\nint main() {\n\n int i = 3;\n\n std::thread thread1{print, std::ref(i)};\n\n std::thread thread2(add, std::ref(i), 4);\n\n thread1.join();\n\n thread2.join();\n\n}\n如果这两个线程都在运行，那么在有限数量的步骤之后，其中一个必须完成。为什么我的程序不满足“无锁”的定义？
\n