HBO

如果存在锁争用限制了Linux的可扩展性，那么到目前为止使用的方法是更改​​Linux内核中自旋锁的使用方式。

锁可以分解为多个锁，可以更改算法来避免锁（例如上面讨论的用于解剖页面表输入操作的方法）等等。

尽管这些都是有效的方法：对于具有4个以上处理器的系统，为什么不看到自旋锁争用的一般性问题，而是寻求对自旋锁算法本身进行修改以解决争用？

我们需要的是一种反向偏移算法，该偏移算法会使处理器在NUMA互连中停留一段时间，以允许其他处理器完成其工作，避免无用的高速缓存行反弹，同时又不损害无用的情况。

Zoran Radovic已经开发了一种用于处理大型NUMA系统中的锁争用的算法，我已经在Itanium上实现了他的算法。

Radovic 将他的算法称为“分层退避算法”（HierarchicalBack off Algorithm），简称HBO。

  • 图3使用HBO锁定的平均故障时间（ms）

HBO锁定的平均故障时

NUMA意识

标准Linux Spinlock实现使用0表示自旋锁已解锁，使用1表示处于锁定状态的锁。

锁定值是一个32位实体，我们可以将更多信息放入该锁定值中。

因此，我们不是简单地将1写入锁，而是将节点ID（加上1，以便将节点0与未使用的锁混淆）写入锁。

这意味着持有锁的处理器的节点号将在争用期间可用，并且尝试获取锁的处理器可以根据距持有锁的处理器的节点的距离来调整其行为。

通过NUMA链接进行的操作比较昂贵，因此不应像尝试内部节点锁定那样频繁地进行尝试。

本地争用的最佳退避期为3微秒，远程争用的最佳退避期为8微秒。

不同的退避时间段优先于本地锁而不是远程锁，以避免过多移动带有锁定的高速缓存行。对于每次未能获得锁定的失败，退避期都会增加50％，直到达到限制为止。

限制节点争用

在执行 CMPXCHG 获取锁之前，将针对节点特定的本地锁块地址检查该锁地址。

如果锁地址等于本地块值，那么处理器将在该地址而不是锁上旋转。

本地锁定块地址是特定于节点的。

它将位于处理器缓存中，从而仅需最小的开销即可进行比较。

如果来自一个节点的处理器发现它无法获取远程锁，则它将设置本地锁块地址。

然后，将禁止来自同一节点的其他处理器获取相同的节点外锁定。

这限制了在激烈竞争的环境中进行节点锁定获取的尝试。

  • Drawing 9 HBO lock acquisition

HBO lock acquisition

饥饿和愤怒程度

退避算法可能导致饥饿。

如果本地处理器不断访问同一锁，则锁的所有权可以保留在一个节点上。

在某个时候，移动锁会变得更加有利，因为进程在远程节点上停滞了太长时间。

为此，节点外锁获取首先要经过一系列补偿。

但是，如果节点在一定数量的尝试中未获得锁定，则它将增加其“愤怒级别”。

最后，当愤怒级别达到预定的限制（在我们的测试案例中为50次尝试）时，它将远程访问远程节点的块地址并将其设置为要获取的锁。

这将使远程节点上的处理器在下次尝试获取锁时处于锁定状态，并且该节点会将锁的所有权释放给愤怒的节点，这将在获取锁后清除远程节点的块地址。

这意味着锁所有权将被转移到另一个节点，然后可能会有多个处理器等待新节点上的锁。

理想情况下（如果正确调整了锁定逻辑），该方法可能导致节点之间的锁定重复移动。

希望所有本地挂起的锁都将在移至下一个节点之前得到处理，从而最大程度地减少NUMA链接上的流量。

内联无争用的情况，以使锁获取与标准自旋锁一样快。

有一个额外的加载和比较，以及加载节点ID的需求，这会产生开销，但是在我尝试过的测试案例中，这种开销是无法测量的。

如果出现争用，则将调用函数来处理争用的原因。

这些功能可能包含更广泛的逻辑并执行指数回退并包含愤怒逻辑。

当前的实现还包含一个proc接口，该接口允许调整退避周期以及查看有关锁获取的统计信息。

如果需要在生产系统中实现，则必须进行其他调整。

结论

自旋锁的现有实现不适用于可能遇到大量自旋锁争用的大型NUMA机器。

HBO锁的建议逻辑比Linux中的简单自旋锁更复杂。

在不满意的情况下，它将在CMPXCHG之前增加额外负载的开销。

但是，不会造成性能损失，因为所有锁定都使用相同的加载地址，并且加载是从缓存的条目进行的。

随着16个处理器的争夺，争夺高性能的性能开始变得意义重大，并且对于越来越多的处理器，这种竞争越来越多。

对于大型系统，使用HBO锁可能会带来不错的性能提升。

参考资料

linux 锁实现