vlocks 用于裸机互斥¶

投票锁（Voting Locks，简称“vlocks”）提供了一种简单的底层互斥机制，对内存系统的要求合理且极低。

这些锁旨在用于在硬件不提供其他支持机制且无法使用普通自旋锁的情况下，协调在其他方面处于非一致性状态的 CPU 之间的关键活动。

vlocks 利用内存系统对单个内存位置写入操作所提供的原子性。为了进行仲裁，每个 CPU 通过向一个公共内存位置存储一个唯一的编号来“为自己投票”。当所有投票完成时，在该内存位置看到的最终值决定了获胜者。

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

算法¶

解释 vlocks 算法最简单的方法是使用一些伪代码

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 提供了一种确定选举是否正在进行的方法，其作用类似于兰波特面包店算法 [1] 中的 “entering” 数组。

然而，一旦选举开始，就会利用底层内存系统的原子性来挑选获胜者。这就避免了需要使用静态优先级规则作为决胜局判定标准，也避免了可能溢出的计数器。

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

特性与局限性¶

vlocks 并不追求公平。在存在竞争的情况下，_最后_ 试图获取锁的 CPU 最有可能获胜。

因此，vlocks 最适合于需要选出一个唯一的获胜者，但具体是哪个 CPU 获胜并不重要的场景。
与其他类似机制一样，vlocks 在面对大量 CPU 时可扩展性较差。

如有必要，vlocks 可以在投票层级中进行级联以实现更好的可扩展性，就像下面针对 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
这缩短了快速路径（fast-path）延迟，并有可能减少竞争情况下的总线竞争。

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

如果 CPU 数量太多而无法在一次事务中读取 currently_voting 数组，则仍需要多个事务。对于这种情况，该 implementation 使用了一个字大小加载的简单循环。与逐个字节加载所需的事务数量相比，此处的事务数量仍然较少。

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

currently_voting 数组的打包机制不适用于缓存内存，除非竞争锁的所有 CPU 都是缓存一致的，因为一个 CPU 的缓存写回可能会覆盖其他 CPU 写入的值。（不过，如果所有 CPU 都是缓存一致的，无论如何你可能都应该使用常规的自旋锁）。

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

为了设置此变量，会向每个 CPU 的 ID 添加一个偏移量，这样就不会有任何 CPU 将 0 用作其 ID。

结语¶

最初由 Linaro Limited 的 Dave Martin 创建并编写文档，用于基于 ARM 的 big.LITTLE 平台，在此感谢 Nicolas Pitre 和 Achin Gupta 提供的审阅和意见。感谢 Nicolas 从相关邮件讨论中提取了大部分文本并编写了伪代码。

参考资料¶

[1] Lamport, L. “A New Solution of Dijkstra’s Concurrent Programming

Problem”, Communications of the ACM 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 内核

目录

本页

vlocks 用于裸机互斥¶

算法¶

特性与局限性¶

ARM 实现¶

结语¶

参考资料¶