4

我只阅读了一点关于这个主题的内容，但似乎唯一的好处是解决争用问题，但它不会对死锁问题产生任何重要影响，因为无锁代码是如此之小和基本（fifos， lifos, hash) 从来没有出现过死锁问题。

所以这一切都与性能有关——对吗？

4

7 回答 7

9

无锁编程（据我所知）始终与性能有关，否则在大多数情况下使用锁要简单得多，因此更可取。

但是请注意，使用无锁编程，您最终可能会用死锁换取活锁，这很难诊断，因为我所知道的没有工具可以用来诊断它（尽管我可能错了）。

我想说，只有在必要时才走无锁的道路；也就是说，您有一个场景，您有一个竞争激烈的锁，这会损害您的性能。（如果它没有损坏，请不要修复它）。

于 2009-09-06T11:48:19.773 回答
9

几个问题。

我们很快将面临具有 64、128 和 256 核的桌面系统。这个领域的并行与我们目前的 2、4、8 核体验不同；由于争用，在这种小型系统上成功运行的算法将在高度并行的系统上运行得更慢。

从这个意义上说，无锁​​很重要，因为它有助于解决可伸缩性问题。

还有一些非常特殊的领域，无锁非常方便，例如 Windows 内核，其中存在禁止任何类型的睡眠（例如等待）的执行模式，这对于数据结构而言显然是非常有限的，但无锁提供了一个很好的解决方案。

此外，无锁数据结构通常没有故障模式。它们实际上不会失败，基于锁的数据结构当然可能无法获得它们的锁。不必担心失败简化了代码。

我编写了一个无锁数据结构库，我将很快发布。我认为如果开发人员能够掌握一个经过充分验证的 API，那么他就可以使用它——不管它是否是无锁的，他不需要担心底层实现的复杂性——并且这就是要走的路。

于 2009-09-09T08:31:46.990 回答
1

这也与可扩展性有关。如今，为了获得性能提升，您必须并行处理您正在处理的问题，以便可以跨多个内核扩展它们 - 越多越好。

这样做的传统方法是锁定需要并行访问的数据结构，但是真正并行运行的线程越多，瓶颈就越大。

所以是的，这是关于性能...

于 2009-09-06T11:46:09.710 回答
1

对于抢占式线程，在持有锁的同时挂起的线程可能会阻塞原本会向前推进的线程。Lock-free 没有这个问题，因为根据 Herlihy 的定义，其他一些线程总是可以向前推进。

对于非抢占式线程，这并不重要，因为根据 Herlihy 的定义，即使基于自旋锁的解决方案也是无锁的。

于 2009-09-07T10:52:55.983 回答
1

这与性能有关——但也与承受多线程负载的能力有关：

  • 锁授予对部分代码的独占访问权限：当一个线程有锁时，其他线程正在旋转（在尝试获取锁时循环）或阻塞，休眠直到锁被释放（如果旋转持续时间过长，通常会发生这种情况） ;

  • 原子操作通过使用不间断的内在 CPU 指令授予对资源（通常是字大小的变量或指针）的独占访问权限。

当锁阻塞其他线程的执行时，程序就会变慢。由于原子操作是串行执行的（一个接一个），因此没有阻塞*。

(*) 只要尝试访问同一资源的并发 CPU的数量不会造成瓶颈 - 但我们还没有足够的 CPU 内核来将其视为问题。

我一直致力于为我正在处理的服务器编写一个无等待（无等待状态的无锁）键值存储。

像 Tokyo Cabinet 之类的库（甚至是 TC-FIXED，一个简单的数组）依赖锁来保持数据库的完整性：

“当一个写入线程正在操作数据库时，其他读取线程和写入线程被阻塞”（东京内阁文档）

没有并发的测试结果（单线程测试）：

SQLite   time: 56.4 ms (a B-tree)
TC       time: 10.7 ms (a hash table)
TC-FIXED time:  1.3 ms (an array)
G-WAN KV time:  0.4 ms (something new which works, but I am not sure a name is needed)

在并发性（多个线程在同一个数据库中读写）的情况下，只有 G-WAN KV 在相同的测试中幸存下来，因为（与其他的相比）它永远不会阻塞。

所以，是的，这个 KV 存储让开发人员更容易使用它，因为他们不必关心线程问题。然而，让它以这种方式工作并非易事。

于 2011-05-12T19:17:32.390 回答
0

我相信我看过一篇文章，它在数学上证明了任何算法都可以以无等待的方式编写（这基本上意味着您可以确信每个线程总是朝着其目标前进）。这意味着它可以应用于任何大规模应用程序（毕竟，程序只是一个具有许多参数的算法）并且因为等待免费确保其中不会发生死锁/活锁（只要它没有没有阻止它真正免费等待的错误），它确实简化了程序的那一侧。另一方面，数学证明与实际实现代码本身相去甚远（AFAIK，甚至没有可以在 PC 上运行的完全无锁链表，我见过涵盖大部分内容的链表，但是他们通常要么不能处理一些常见的功能，

顺便说一句，我还发现了另一个证明，表明由于概率定律和其他各种因素，任何无锁算法实际上都可以被认为是无等待的。

于 2009-10-15T12:23:48.090 回答
0

  1. 可扩展性是高效的多/manicore 编程中一个非常重要的问题。最大的限制因素实际上是应该串行执行的代码部分（参见阿姆达尔定律）。然而，关于锁的争用也很成问题。

  2. 无锁算法解决了传统锁的可扩展性问题。所以，我可以说无锁主要是为了性能，而不是减少死锁的可能性。

  3. 但是，请记住，在当前的 x86 架构下，编写通用的无锁算法是不可能的。这是因为我们不能在当前 x86 中原子地交换任意大小的数据（对于除 Sun 的 ROCK 之外的其他架构也是如此）。因此，当前的无锁数据结构非常有限，并且非常专门用于特定用途。

  4. 我认为当前的无锁数据结构在十年内将不再使用。我强烈期望硬件辅助的通用无锁机制（是的，即事务内存，TM）将在十年内实现。如果实现任何一种TM，虽然不能完美解决锁的问题，但会消除很多问题（包括优先级倒置和死锁）。然而，在硬件中实现 TM 仍然非常具有挑战性，而在 x86 中，刚刚提出了一个草案。

还是太长了：2句话总结。

无锁数据结构不是基于锁的多线程编程的灵丹妙药（甚至TM也不是。如果你真的需要可扩展性并且有锁争用的麻烦，那么考虑无锁数据结构。

于 2009-11-09T17:52:57.053 回答