裸机互斥的 vlock¶

投票锁，或 “vlock”，提供一种简单的低级互斥机制，对内存系统的要求合理但最低。

它们旨在用于协调 CPU 之间的关键活动，这些 CPU 在其他情况下是不连贯的，在硬件没有提供其他机制来支持这一点且无法使用普通自旋锁的情况下。

vlock 利用内存系统为写入单个内存位置提供的原子性。为了仲裁，每个 CPU 通过将一个唯一的数字存储到公共内存位置来“为自己投票”。当所有投票都投完后，在该内存位置看到的最终值标识了获胜者。

为了确保选举在有限的时间内产生明确的结果，CPU 只有在没有选出获胜者并且选举似乎尚未开始的情况下才会首先参加选举。

算法¶

解释 vlock 算法最简单的方法是一些伪代码

int currently_voting[NR_CPUS] = { 0, };
int last_vote = -1; /* no votes yet */

bool vlock_trylock(int this_cpu)
{
        /* signal our desire to vote */
        currently_voting[this_cpu] = 1;
        if (last_vote != -1) {
                /* someone already volunteered himself */
                currently_voting[this_cpu] = 0;
                return false; /* not ourself */
        }

        /* let's suggest ourself */
        last_vote = this_cpu;
        currently_voting[this_cpu] = 0;

        /* then wait until everyone else is done voting */
        for_each_cpu(i) {
                while (currently_voting[i] != 0)
                        /* wait */;
        }

        /* result */
        if (last_vote == this_cpu)
                return true; /* we won */
        return false;
}

bool vlock_unlock(void)
{
        last_vote = -1;
}

currently_voting[] 数组提供了一种让 CPU 确定选举是否正在进行的方法，并且在 Lamport 的面包店算法 [1] 中扮演着类似于 “entering” 数组的角色。

但是，一旦选举开始，就会使用底层内存系统的原子性来选出获胜者。这避免了使用静态优先级规则来充当决胜局，或任何可能溢出的计数器。

只要 last_vote 变量对所有 CPU 全局可见，它将只包含一个值，一旦每个 CPU 清除了其 currently_voting 标志，该值就不会改变。

特性和局限性¶

vlock 并非旨在公平。在竞争情况下，_最后_尝试获取锁的 CPU 最有可能获胜。

因此，vlock 最适合用于必须选出唯一获胜者，但实际上哪个 CPU 获胜并不重要的情况。
与其他类似机制一样，vlock 不能很好地扩展到大量 CPU。

如果需要，vlock 可以按投票层次结构级联，以允许更好的扩展，如下面 4096 个 CPU 的假设示例所示
/* first level: local election */
my_town = towns[(this_cpu >> 4) & 0xf];
I_won = vlock_trylock(my_town, this_cpu & 0xf);
if (I_won) {
        /* we won the town election, let's go for the state */
        my_state = states[(this_cpu >> 8) & 0xf];
        I_won = vlock_lock(my_state, this_cpu & 0xf));
        if (I_won) {
                /* and so on */
                I_won = vlock_lock(the_whole_country, this_cpu & 0xf];
                if (I_won) {
                        /* ... */
                }
                vlock_unlock(the_whole_country);
        }
        vlock_unlock(my_state);
}
vlock_unlock(my_town);

ARM 实现¶

当前的 ARM 实现 [2] 包含一些超出基本算法的优化

通过将 currently_voting 数组的成员紧密地打包在一起，我们可以一次事务读取整个数组（前提是可能争夺锁的 CPU 数量足够小）。这减少了外部内存所需的往返次数。

在 ARM 实现中，这意味着我们可以使用单个加载和比较
LDR     Rt, [Rn]
CMP     Rt, #0
...代替等效于以下代码
LDRB    Rt, [Rn]
CMP     Rt, #0
LDRBEQ  Rt, [Rn, #1]
CMPEQ   Rt, #0
LDRBEQ  Rt, [Rn, #2]
CMPEQ   Rt, #0
LDRBEQ  Rt, [Rn, #3]
CMPEQ   Rt, #0
这减少了快速路径延迟，并可能减少竞争情况下的总线争用。

该优化依赖于 ARM 内存系统保证不同大小的重叠内存访问之间的一致性的事实，类似于许多其他架构。请注意，我们不关心 currently_voting 的哪个元素出现在 Rt 的哪个位中，因此无需担心此优化中的字节序。

如果有太多 CPU 无法在一个事务中读取 currently_voting 数组，则仍然需要多个事务。该实现为此情况使用简单的字大小加载循环。事务的数量仍然少于单独加载字节所需的数量。

原则上，我们可以通过使用 LDRD 或 LDM 进行进一步聚合，但为了使代码简单，在初始实现中未尝试这样做。
vlock 目前仅用于无法启用其缓存的 CPU 之间的协调。这意味着该实现删除了在缓存内存中执行该算法时所需的许多屏障。

除非争夺锁的所有 CPU 都具有缓存一致性，否则 currently_voting 数组的打包不适用于缓存内存，因为来自一个 CPU 的缓存回写会破坏其他 CPU 写入的值。（尽管如果所有 CPU 都是缓存一致的，那么您可能应该使用适当的自旋锁）。

last_vote 变量使用的“尚未投票”的值为 0（而不是伪代码中的 -1）。这允许通过简单地将它们放入 .bss 中，将静态分配的 vlock 隐式初始化为未锁定状态。

为了设置此变量，每个 CPU 的 ID 都会添加一个偏移量，以便没有 CPU 将值 0 用于其 ID。

版权页¶

最初由 Dave Martin 为 Linaro Limited 创建并记录，用于基于 ARM 的 big.LITTLE 平台，并衷心感谢 Nicolas Pitre 和 Achin Gupta 的审查和意见。感谢 Nicolas 从相关邮件线程中提取了大部分文本并编写了伪代码。

参考资料¶

[1] Lamport, L. “Dijkstra 并发编程的新解决方案

问题”，美国计算机协会通讯 17, 8（1974 年 8 月），453-455。

https://en.wikipedia.org/wiki/Lamport%27s_bakery_algorithm

[2] linux/arch/arm/common/vlock.S, www.kernel.org。

Linux 内核

目录

本页

裸机互斥的 vlock¶

算法¶

特性和局限性¶

ARM 实现¶

版权页¶

参考资料¶