首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >无锁多线程编程?

无锁多线程编程?
EN

Stack Overflow用户
提问于 2018-05-09 07:28:17
回答 2查看 0关注 0票数 0

我看到有人说他们为多线程使用设计了自己的“无锁”容器。假设他们没有使用性能命中模数技巧(即每个线程只能根据某种模数插入),数据结构如何可以是多线程的,但也是无锁的?

这个问题是针对C和C ++的。

EN

回答 2

Stack Overflow用户

发布于 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_*同时调用该函数。在锁定版本中,锁定线程解锁互斥锁之前,没有线程可以进展。相比之下,在无锁版本中,所有线程都可以取得进展。如果一个线程被阻止,它就不会完成它的工作份额,但其他人都可以继续工作。

值得注意的是,一般来说,无锁编程可以为可预测的延迟交易吞吐量和平均延迟吞吐量。也就是说,如果没有太多的争用(因为原子操作很慢并影响系统的其他部分),那么无锁程序通常会比相应的锁定程序做得少,但它保证永远不会产生不可预测的大的延迟。

票数 0
EN

Stack Overflow用户

发布于 2018-05-09 17:11:56

对于锁,这个想法是,你获得一个锁,然后做你的工作,知道没有人会干涉,然后释放锁。

对于“无锁”,这个想法是,你在其他地方做你的工作,然后试图自动地将这项工作提交到“可见状态”,如果你失败了,重试。

“无锁”的问题是:

  • 很难为一些不平凡的东西设计一个无锁算法。这是因为只有很多方法才能执行“原子性提交”部分(通常依赖于使用不同指针替换指针的原子“比较和交换”)。
  • 如果存在争用,它会比锁更糟糕,因为你反复做着被丢弃/重试的工作
  • 设计一个既无误又“公平”的无锁算法几乎是不可能的。这意味着(在争论中)一些任务可能是幸运的(并且一再承诺他们的工作并取得进展),有些可能非常不幸(并且一再失败并重试)。

这些事情的结合意味着它只适用于低争用情况下相对简单的事情。

研究人员设计了无锁链表(以及FIFO / FILO队列)和一些无锁树。我认为没有比这些更复杂的东西。对于这些事情是如何工作的,因为这很难做到这一点很复杂。最明智的方法是确定您感兴趣的数据结构类型,然后在网络上搜索相关的数据结构无锁算法的研究。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/-100004052

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档