我看到有人说他们为多线程使用设计了自己的“无锁”容器。假设他们没有使用性能命中模数技巧(即每个线程只能根据某种模数插入),数据结构如何可以是多线程的,但也是无锁的?
这个问题是针对C和C ++的。
发布于 2018-05-09 15:36:36
无锁编程的关键是使用硬件固有的原子操作。
事实上,即使锁本身也必须使用这些原子操作!
但是锁定和无锁编程的区别在于,无锁程序不能完全由任何单线程停顿。相比之下,如果在一个锁定程序中一个线程获得了一个锁,然后无限期地暂停,那么整个程序就会被阻塞,并且无法取得进展。相反,即使单个线程被无限期暂停,一个无锁程序也可以取得进展。
这里有一个简单的例子:并发计数器增量。我们提出了两个“线程安全”的版本,即可以同时调用多个版本。首先是锁定版本:
int counter = 0;
std::mutex counter_mutex;
void increment_with_lock()
{
std::lock_guard<std::mutex> _(counter_mutex);
++counter;
}
现在无锁版:
std::atomic<int> counter(0);
void increment_lockfree()
{
++counter;
}
现在想象数百个线程都increment_*
同时调用该函数。在锁定版本中,锁定线程解锁互斥锁之前,没有线程可以进展。相比之下,在无锁版本中,所有线程都可以取得进展。如果一个线程被阻止,它就不会完成它的工作份额,但其他人都可以继续工作。
值得注意的是,一般来说,无锁编程可以为可预测的延迟交易吞吐量和平均延迟吞吐量。也就是说,如果没有太多的争用(因为原子操作很慢并影响系统的其他部分),那么无锁程序通常会比相应的锁定程序做得少,但它保证永远不会产生不可预测的大的延迟。
发布于 2018-05-09 17:11:56
对于锁,这个想法是,你获得一个锁,然后做你的工作,知道没有人会干涉,然后释放锁。
对于“无锁”,这个想法是,你在其他地方做你的工作,然后试图自动地将这项工作提交到“可见状态”,如果你失败了,重试。
“无锁”的问题是:
这些事情的结合意味着它只适用于低争用情况下相对简单的事情。
研究人员设计了无锁链表(以及FIFO / FILO队列)和一些无锁树。我认为没有比这些更复杂的东西。对于这些事情是如何工作的,因为这很难做到这一点很复杂。最明智的方法是确定您感兴趣的数据结构类型,然后在网络上搜索相关的数据结构无锁算法的研究。
https://stackoverflow.com/questions/-100004052
复制相似问题