logo标签列表

我该如何编写无锁结构？

multithreadingmulticorelock-free
36

在我的多线程应用程序中，我发现有很严重的锁争用问题，这阻碍了在多个核心上实现良好的可扩展性。我决定使用无锁编程来解决这个问题。

我该如何编写一个无锁结构？

6
我认为你的意思是线程安全的无锁结构。 - Paul van Brenk
21个回答
45

简短的回答是：

您无法创建无锁数据结构。

长的回答是：

如果您正在问这个问题，您可能还不了解足够的知识来创建一个无锁数据结构。创建无锁数据结构非常困难，只有这个领域中的专家才能做到。与其编写自己的结构，不如搜索现有的实现。当您找到它时，请检查它的广泛使用程度、文档是否完善、是否经过充分验证以及存在哪些限制 - 即使其他人发表的一些无锁数据结构也存在缺陷。

如果您没有找到相应于当前正在使用的结构的无锁结构，则改进算法，以便可以使用某个现有的结构。

如果您仍然坚持创建自己的无锁数据结构，请确保：

  • 从简单的开始
  • 了解目标平台的内存模型（包括读/写重排序约束，哪些操作是原子操作）
  • 研究其他人在实现无锁数据结构时遇到的问题
  • 不要猜测它是否会工作，必须证明它
  • 对结果进行严格测试

了解更多：

维基百科上的无锁和无等待算法

Herb Sutter：无锁代码：虚假的安全感

1
正是我想要写的 :) - gabr
12
我请他们帮助其他可能在这里寻找答案的人。 - Suma
1
请参阅以下论文，获取一个健壮的伪代码示例： http://www.research.ibm.com/people/m/michael/podc-1996.pdf 该示例实现了一个元素的链表，允许多个并发访问而无需使用锁。 - Howard May
16

使用像Intel Threading Building Blocks这样的库，它包含了相当多的无锁结构和算法。我真的不建议您尝试编写自己的无锁代码，这非常容易出错且难以正确实现。

12
12
正如所指出的，如果所有对象都是不可变的、只读的，你就不需要担心锁了，但这意味着你可能需要经常复制对象。复制通常涉及到malloc，而malloc使用锁来同步跨线程的内存分配，因此不可变对象可能没有你想象的那么有效（malloc本身的性能缩放相当糟糕，malloc很慢；如果你在性能关键区域进行大量的malloc操作，请不要期望良好的性能）。
当你只需要更新简单变量（例如32位或64位整数或指针），对它们执行简单的加减操作或仅交换两个变量的值时，大多数平台都提供了"原子操作"（GCC还提供了这些功能）。但是，原子操作与线程安全不同。然而，原子操作确保，如果一个线程将一个64位值写入内存位置，并且另一个线程从其中读取，读取者要么得到写操作之前的值，要么得到写操作之后的值，但永远不会得到中间的“损坏”的值（例如，其中前32位已经是新值，最后32位仍然是旧值！如果你不在这样的变量上使用原子访问，这种情况可能会发生）。
然而，如果你有一个具有3个值的C结构体，想要更新它们，即使你使用原子操作更新了所有三个值，这些仍然是独立的操作，因此读者可能会看到结构体中一个值已经被更新，而另外两个值还没有被更新。在这种情况下，如果你必须确保读者要么看到结构体的所有值都是旧值，要么都是新值，那么就需要锁。
让锁更好地扩展的一种方法是使用读写锁。在许多情况下，数据的更新相对不频繁（写操作），但访问数据非常频繁（读取数据），例如集合（哈希表、树形结构）。在这种情况下，读写锁将为你带来巨大的性能提升，因为许多线程可以同时持有读锁（它们不会相互阻塞），只有当一个线程想要写锁时，所有其他线程才会被阻塞，直到完成升级为止。避免线程问题的最佳方法是不要在线程之间共享任何数据。如果每个线程大部分时间都处理其他线程无权访问的数据，则完全不需要为该数据进行锁定（也不需要原子操作）。因此，尽可能少地在线程之间共享数据。只有当你真正需要时才需要快速移动数据的方法来在线程之间进行通信（ITC，线程间通信）。根据你的操作系统、平台和编程语言（遗憾的是你没有告诉我们这些信息），可能存在各种强大的ITC方法。
最后，另一个处理共享数据但不需要任何锁定的技巧是确保线程不访问共享数据的相同部分。例如，如果两个线程共享一个数组，但其中一个仅访问偶数索引，另一个仅访问奇数索引，则不需要锁定。或者，如果两个线程共享同一内存块，但其中一个仅使用其上半部分，另一个仅使用其下半部分，则不需要锁定。尽管这并不意味着会带来良好的性能，特别是在多核CPU上。一个线程对这个共享数据（在一个核心上运行）的写操作可能会强制刷新另一个线程（在另一个核心上运行）的缓存，而这些缓存刷新通常是现代多核CPU上运行的多线程应用程序的瓶颈。
这里如果你必须确保，就需要一个锁。不要直接在原地进行操作，而是要创建一个新的结构副本，并将其作为原子操作来切换活动状态。 - moonshadow
但这意味着您将不得不再次进行malloc，假设这不是堆栈数据（它很可能不是），并且像我说的那样，malloc可能成为一个巨大的瓶颈。在我们的软件中，每次重复使用相同的内存块与每次使用malloc相比，导致速度提高了80％。 - Mecki
你可以改用一个线程优化的 malloc，它使用每个线程的 arena。 - Zan Lynx
10

正如我的教授（来自《多处理器编程艺术》的Nir Shavit）告诉班上的同学们：请不要这样做。主要原因在于可测试性-您无法测试同步代码。您可以运行模拟，甚至可以进行压力测试。但这只是最好的粗略估计。您真正需要的是数学正确性证明。能够理解它们的人很少，更不用说写它们了。

因此，正如其他人所说：使用现有库。Joe Duffy的博客概述了一些技术（第28节）。您应该尝试的第一个技术是树分裂-将其分解为较小的任务并结合起来。

7

不可变性是避免锁定的一种方法。请参阅Eric Lippert的讨论和实现，例如不可变栈和队列。

6

关于Suma的回答，在《多处理器编程艺术》一书中，Maurice Herlithy展示了实际上所有都可以不使用锁来实现（见第6章）。如果我没记错，这主要涉及将任务拆分为处理节点元素（类似于函数闭包），并将每个节点入队。线程将通过跟踪从最新缓存的节点开始的所有节点来计算状态。显然，这可能在最坏情况下导致顺序性能，但它具有重要的无锁特性，可以防止线程在持有锁时长时间被调度出去的情况。Herlithy还实现了理论上的无等待性能，这意味着一个线程不会永远等待赢得原子入队（这是很复杂的代码）。

一个多线程队列/栈是出奇的困难（请检查 ABA问题）。其他事情可能非常简单。熟悉 while(true) { atomicCAS直到我交换了它 } 块；它们非常强大。对于CAS正确性的直觉可以帮助开发，尽管您应该使用良好的测试和更强大的工具（也许 SKETCH，即将推出的MIT Kendo或spin？）来检查正确性，如果您可以将其简化为一个简单的结构。
请发布有关您的问题的更多信息。没有详细信息很难给出一个好的答案。
编辑不可变性是很好的，但它的适用性有限，如果我理解正确的话。它并不能真正克服写后读的危险；考虑两个线程执行“mem = NewNode(mem)”；他们都可以读取 mem，然后都写入它；这对于经典增量函数来说不正确。此外，由于堆分配（需要在线程之间同步），它可能会很慢。
5

不可变性会产生这种效果。对对象的更改会导致新对象的生成。Lisp在底层以这种方式工作。

Effective Java的第13条解释了这种技术。

4

Cliff Click利用有限状态机进行了无锁数据结构的重大研究，并在Java中发布了许多实现。您可以在他的博客上找到他的论文、幻灯片和实现：http://blogs.azulsystems.com/cliff/

2
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接