并发编程网 - ifeve.com

原文链接，译文连接，译者：梁海舰，校对：李任

注意，我将在这篇文章中说一些关于“无锁”和“无等待”算法的坏话。在我们开始之前，让我来问你一个问题：

你之前有过需要无锁算法来解决问题吗？为什么必须使用无锁算法来解决？

这是一个意味深长的问题，在某种意义上，我们尝试区分哪些问题需要“无锁”或者受益于“无锁”提供的保证，哪些问题使用阻塞解决方案就已经足够了。那么，什么样的问题可以利用无锁算法解决呢？

你会说高竞争下的扩展性？是的，听起来无锁算法确实是合适的候选方案，但是，实际上它很大程度取决于算法的某一些特征。

例如：如果循环中有很多CAS操作，当你增加线程数量时候，那些CAS操作将增加大量的重试，记住CAS操作的代价是很高的，并且很有可能成为该算法的瓶颈。实际上，这意味着CAS操作上越多的线程竞争，你的代码运行的整体速度越慢，不管你添加多少线程。

如果你一开始没有很多线程，那为什么不使用阻塞的方式呢？在这个例子中使用阻塞的方式通常更简单、更快实现。

如果问题允许，你甚至可以使用读写锁，不同于大部分无锁算法，读写锁已经展示了读线程的数量可扩展。

还有人说用在解决高竞争下的低延迟，好吧，无锁仅仅保证了某些线程能够执行，但让我们假设你没有一个高优先级的线程或一个高于其他线程优先级的线程，未必当前线程就在执行它的任务（在这种情况下你需要无等待算法实现低延迟保证）。

对于这样的情况，无锁确实给了你比阻塞更好的保证，但是除此之外不要期望得太多。首先，你很可能丢失一些性能（但不是很多），其次，如果其他线程持续的执行，那么特定的任务可能耗费无限的时间直至完成并且导致当前操作重启。这意味着那些循环中包含很多CAS操作的无锁算法，执行起来慢得离谱，其原因在于重试的次数，并不是所谓的复杂性。

现在我们知道为什么使用无锁，值得注意的是，许多无锁算法在它们执行的一些步骤中会暗自分配和释放内存。

我所知道的，没有一个系统使用“无锁”算法进行内存管理，事实上，在大部分系统中，内存分配有时候执行得非常慢。想象一下你申请一个对象，系统需要为你获得一个新的内存页，更糟糕的是，内存不足，需要将它旧的内容从内存中交换到硬盘中。

如果你关注的是扩展能力，那么偶尔的阻塞，内存分配慢并不是太坏，但问题是你需要的是低延迟，使用无锁进行内存分配、释放没有使用到任何“无锁”算法自身提供的保证。不管使用有内存管理或无内存管理的系统都有这个棘手的问题，换而言之有没有使用内存回收也是一样。

我认为无锁算法的适用性影响非常大，大到我们需要有两个清楚的分类来为无锁算法命名：

无界无锁：这个算法是无锁的，但是它的方法中或多或少需要为新的对象分配内存或者释放一些对象占用的内存。

有界无锁：这个算法是无锁定，并且它的方法中没有涉及到对象分配内存或者是有限制分配并且一开始预先分配，然后使用一个池设计模式，池也是采用无锁方式实现的。

对于“无界无锁”，如果我们教条主义，我们甚至可以说“无界无锁”算法完全不是无锁，因为算法中会有操作被阻塞，并且会导致任务阻塞。

我不会那么教条主义，毕竟内存分配通常是很快的，并且垃圾回收器只是偶尔执行。

有一件事是可以肯定的，那就是给定一个需要解决低延迟的问题，它有两个解决方案可选，一个是“无界无锁”，另一个是“有界无锁”，我会选择有界的那个，即便它性能更低。

顺便说一下，把上面所有段落中的“无锁”字眼替换成“无等待”，它仍然适用。

话虽如此，我想再重申一下我偏爱的并发算法的顺序，下面的算法中最上面的是你可以实现的最好的算法：

1. 有界集居数无关无等待
2. 有界无等待
3. 有界无锁
4. 无界集居数无关无等待
5. 无界无等待
6. 无界无锁
7. 阻塞