适用于普通人的无锁算法

LWN订户已向您提供以下仅限订阅的内容。数以千计的用户依赖LWN获取来自Linux和自由软件社区的最好消息。如果您喜欢这篇文章，请考虑接受右边的试用报价。感谢您访问LWN.net！

免费试用LWN 1个月：无需付款或信用卡。现在激活您的试用订阅，看看为什么成千上万的读者订阅LWN.net。

正如一些人所说，时间是大自然阻止一切同时发生的方式。然而，在今天高度并发的计算机中，时间安排不足以保持事件的有序；这项任务落在一组广泛的锁定原语上，在这些原语之下，是被称为Linux内核内存模型的形式化的内存视图。然而，要真正理解内存模型，需要一种特殊的头脑；内核开发人员在内存模型发挥作用的领域工作时，松懈这一特定的超能力很可能会出错。不过，出于性能目的，在该级别工作的必要性越来越大；最近的一次对话指出了内核可以使普通内核开发人员更轻松地完成这类工作的方法。当多个执行线程同时访问相同的数据时，并发性就开始发挥作用。即使在一个简单的世界里，在这样的情况下保持一切的连贯性也可能是一项具有挑战性的任务。内核通过使用自旋锁、互斥锁和其他可以控制并发的锁定原语来防止错误的事情同时发生。这一级别的锁可以被认为类似于城市中的红绿灯：只要观察得当，它们就可以防止事故发生，但代价是阻止大量的交通。(自旋锁、互斥锁和其他可以控制并发的锁定原语)这一级别的锁可以被认为类似于城市中的红绿灯：只要正确观察，它们就可以防止事故发生，但代价是阻止大量交通。等待锁所花费的时间是有害的；即使在内存缓存之间反弹锁数据的时间也会破坏可伸缩性，因此开发人员经常寻找避免锁定的方法。考虑一个高度简化的示例：将一个元素插入到一个高度链接的列表中。一种可能的解决方案是使用互斥锁来保护整个列表；任何遍历列表的线程都必须首先获取该互斥锁。如果插入元素的线程获得此锁，它知道没有其他线程会同时遍历该列表，因此更改将是安全的。但是如果这个列表被大量使用，这个锁定很快就会变得昂贵。因此，人们可以考虑一种无锁的替代方案。如果列表最初看起来是这样的：可以从将新元素的传出指针链接到列表中紧随其后的现有元素开始：此时，列表对于遍历它的任何其他线程看起来都是一样的。为了完成操作，代码将把指针从列表中前面的元素重定向到新元素：现在每个人都可以看到新的列表；不需要锁定，并且列表的视图始终是一致和正确的。或者说人们希望如此。问题是，现代硬件打着性能的旗号让事情变得更加困难。执行一系列操作的顺序可能不是这些操作对系统中的其他线程可见的顺序。因此，例如，系统中的其他线程很可能以相反的顺序看到上面两个指针的赋值，结果是，从它们的观点来看，有一个时间窗口，在这段时间内列表看起来是这样的：新元素中的传出指针将包含赋值发生之前的所有内容，导致列表进入杂草。世界上几乎没有确定性，但人们可以合理地自信地说，这种情况不会带来什么好处。考虑这一问题的另一种方式是，锁定提供了一种牛顿物理学的世界观；在给定的情况下，人们总是知道会发生什么。在较低的层次上，生活开始类似于量子物理学，在那里可能会发生令人惊讶的事情，很少有人能令人信服地声称理解所有的事情。在这个世界上，一个人通常可以在不了解量子物理的情况下很好地工作，但在某些情况下，有专家在身边是很好的。Linux内核有几位这样的专家；多年来，他们在内核内存模型的创建上投入了大量的工作，该模型描述了内核如何看待内存，以及如何在并发可能发挥作用的情况下安全地执行操作。在这种情况下，Linux内核有一些专家；他们多年来投入了大量的工作来创建内核的内存模型，该模型描述了内核如何看待内存，以及如何安全地执行并发可能发挥作用的操作。结果就是臭名昭著的Memory-barriers.txt