自旋锁

2018-08-15

自旋锁是最基础的同步机制，也是系统开发过程中最先实现的锁。然而即使是这种最简单的锁，仍然有一定的复杂度。

不加锁会有哪些问题

首先考虑单核硬件上的情况。现代操作系统一般都是多任务的，而且是抢占式多任务，也就是在任务执行过程中的任何时刻，都有可能被系统换出，切换到一个新的任务运行。然而，多个任务有可能使用了相同的全局数据，这就有可能导致数据竞争（data race）。

例如我们对双链表进行操作，向这个链表的末尾增加一个节点，那么通常的流程是这样的（进行了一些简化）：

node_t *tail = list->tail;
newnode->prev = tail;
newnode->next = NULL;
tail->prev = newnode;
list->tail = newnode;

然而，系统是抢占式的，在任何时刻这个任务都有可能被换出，如果恰好在最后一句之前切换了任务，而新的任务恰好也操作了这个链表，就会导致链表状态错误。这种问题就是“任务切换导致的数据竞争”。

除了任务，中断上下文执行的代码也有可能访问全局变量，因此任务与 ISR、ISR 与 ISR 之间都有可能产生竞争，这种竞争称作“中断导致的数据竞争”。

多核环境下，还有另外一种竞争情况。由于每个处理器核心独立运行，即使禁用中断，多个 CPU 仍然有可能同时访问/操作共享的数据。这种竞争情况称作“多核导致的数据竞争”。

因此总结下来，产生数据竞争有三种可能的原因：

任务切换
中断
多核

接下来讨论如何防止竞争，同样是从这三个原因入手。

防止任务切换导致的竞争

既然竞争是由于任务之间的切换引发的，那么最本质的解决方案就是禁用任务切换，确保执行临界区的时候不会切换到其他的任务，也就保证了这种类型的竞争不会发生。

那么现在的问题就是如何禁用任务切换。任务切换分为两种情况，一种是主动任务切换，例如当前任务执行了一个阻塞操作，主动由就绪态变为阻塞状态；另一种情况是被动切换，例如产生了一个新的更高优先级的任务，或者当前任务的时间片用完，需进行轮转调度。可以看出，并不是所有的任务切换都是中断导致的，因此单纯禁用中断是不能防止任务切换的。

因此，我们只能修改调度器，在每个任务的控制结构 TCB 中增加一个标识 lock。如果 tid->lock 非零，表示当前任务处在临界区内部，那么即使按正常逻辑应该进行任务切换，调度器也会保持当前任务继续运行，直到任务退出临界区。

我们可以为任务引入两个函数：task_lock() 和 task_unlock()，前者在进入临界区时调用，负责将 tid->lock 的值加一；后者在退出临界区的时候执行，负责将 tid->lock 的值减一，另外执行一次调度（因为可能应该发生任务切换，但由于 tid->lock 导致没有切换，那么在我们退出临界区之后，就应该立即切换到目标任务）。

void task_lock() {
    atomic_inc(&tid_current->lock);
}

void task_unlock() {
    atomic_dec(&tid_current->lock);
    schedule();
}

需要说明的是，对 tid_current->lock 执行加一、减一操作的时候，需要保证原子性，因此这里使用了 atomic_***() 函数。不然 tid_current->lock 又会产生竞争情况。关于这种原子操作，在后面还会说到。

在临界区内，我们并没有关闭中断，因此中断仍有可能发生。但是，中断处理函数不会操作相同的全局数据，就不会有问题。而且，不关闭中断能保证系统的高响应性，感受上运行速度更快。

另外，关闭中断并不能组织任务切换，因为禁用中断只是屏蔽了任务被动切换的情况，如果是由于任务状态改变或产生新的高优先级任务导致的切换，是禁用中断无法屏蔽的。

防止中断导致的竞争

在中断上下文，需要执行注册的 ISR 函数，在时钟中断内还有可能要执行看门狗函数。如果某些全局变量被 ISR/看门狗和任务代码共享，就可能产生中断导致的竞争。

为了防止这种类型的数据竞争，我们只需要禁用中断。现代操作系统往往支持中断重入，也就是在中断内部，仍然是中断开启的状态，允许中断的嵌套。

在任务代码中禁用中断，可以保证临界区内不会产生中断，也就不会执行 ISR 函数；在 ISR 中禁用中断，可以保证在临界区内部不会产生新的中断，不会执行其他的 ISR 函数。

防止多核导致的竞争

多核导致的竞争与前两者有很大区别，因为这是真正意义的并行。多核的同步问题，最终还是要处理器厂商提供解决方案，于是就有了原子性操作。所谓原子性操作，就是一些基本代数运算，但是能够保证运算过程是原子性的。以对一个变量执行加一（inc）并获取原值操作为例，通常的流程是这样的：

load    [$var], %a      # 将变量读取到寄存器
add     %a, 1, %b       # 将寄存器的值加一，并保存在另一个寄存器里
store   %b, [$var]      # 将寄存器的值写回到内存

可以看到，C 语言中一个简单的 a = x++ 操作，实际的汇编操作也是由多条指令完成的，那么这三条指令就有可能和其他 CPU 上正在运行的代码发生竞争。正常情况下，应该满足 (%a + 1) == [$var]。如果上面的代码在执行过程中，恰好另一个 CPU 上的代码也在执行相同的操作，很有可能不再满足这个条件。

多核 CPU 通常提供了某种原子性操作，可以用一条指令实现代数运算，同时获取变量的原值。例如函数 atomic_inc() 可以将一个变量的值加一，同时获取这个变量在加一之前的值，整个过程能够确保原子性。在 x86 架构下，这是通过锁住总线，阻止其他 CPU 对这个内存单元的访问实现的（需要专门的硬件支持）。

锁变量（最朴素的自旋锁）

在多核环境下实现临界区，最简单的方法就是使用一个锁变量 lock。如果 lock == 0，表示还没有 CPU 进入这个临界区。如果 lock == 1，表示有 CPU 正在执行临界区。当一个 CPU 准备进入临界区时，首先通过原子性操作 atomic_set() 将锁变量 lock 的值置为 1，并获取这个变量的原值。如果原值为 0，说明之前没有其他 CPU 进入临界区，那么该 CPU 成功进入临界区；如果变量的原值是 1，说明有另外一个 CPU 正在执行临界区，当前 CPU 未能成功进入临界区。

两种情况，lock 的结束状态都是 1，但根据 atomic_set() 函数的返回值，我们可以判断这条指令之前的锁变量状态，从而判断 lock 的值是由 0 变为 1（成功进入临界区），还是一直保持为 1（未成功进入临界区）。

实际上，这就是一个最朴素的自旋锁实现。如果进入临界区失败之后，继续不断循环执行 atomic_set，直到返回值为 0，表示当前 CPU 成功进入临界区。这种忙等待，死循环的过程就被称作“自旋”。

退出临界区很直接，将 lock 变量的值置为 0 即可。

Service-Ticket 自旋锁（保证先到先得）

朴素的自旋锁可以解决多核环境下，多个 CPU 之间的竞争，但是却有一个很严重的问题，那就是公平性。

如果有多个 CPU 都在尝试获取这个自旋锁，也就是有多个 CPU 在执行 atomic_set，那么当自旋锁的持有者释放锁时，所有等待的 CPU 中智能有一个成功获得自旋锁（因为原子性）。但是，哪一个 CPU 才能得到这把自旋锁，这是不确定的。我们没有办法确定哪个 CPU 最先开始自旋，因此不能实现先到先得，不能确保公平性。

为此，NT 内核实现了 Queued Spinlock，VxWorks 则实现了 service-ticket 锁。二者本质上是一样的，都是通过两个计数器，来确保先到先得。

这个自旋锁内部有两个关键变量：

service_counter，表示当前自旋锁属于票据编号是多少的 CPU
ticket_counter，表示如果有下一个 CPU 等待获取锁，它的票据编号是多少

这两个变量可以用银行营业厅的窗口进行类比。尝试获取自旋锁，就像顾客进入银行之后，等待窗口为自己服务。每个客户首先取一张号码排队，而这个号码就是 ticket_counter 的值，使用 atomic_inc() 操作。顾客拿到号码之后，不断关注服务窗口上方的显示屏，检查是否显示到了自己的号码，这个不断检查的过程就是“自旋”的过程。如果发现显示屏上的数字变成了自己的编号，那就说明成功获取到了锁。

准备释放锁的时候，也就是顾客完成业务，准备起身离开，此时将 service_counter 的取值加一，表示现在窗口可以服务下一个排队的顾客了。

获取锁和释放锁过程的伪代码如下：

void spinlock_take(lock) {
    ticket = atomic_inc(&lock->ticket_counter);
    while (ticket != atomic_get(&lock->service_counter)) {}
}
void spinlock_give(lock) {
    atomic_inc(&lock->service_counter);
}

使用 service_counter 和 ticket_counter 模拟了排队的过程，各个 CPU 严格按照自己的 ticket 顺序等待，这样，能够确保最先等待的 CPU 最早得到锁。

我们不妨将这样的自旋锁称作 raw spinlock，因为这种锁只能防止多核之间的竞争，并没有禁用抢占和中断。

综合分析

前面分别考虑了三种竞争原因，并给出了相应的防止手段。禁用抢占可以防止任务切换导致的竞争，关闭中断可以防止中断导致的竞争，raw spinlock 可以防止多核导致的竞争。然而实际很多情况下，多种竞争因素是同时存在的。例如在一个多核系统中，多个 CPU 之间可能会有数据竞争，同时在该 CPU 内部还会发生任务切换和中断，因此，常用的自旋锁往往是 raw spinlock 再加上禁用抢占或禁用中断。

使用自旋锁的目的是防止访问共享数据产生竞争，不同的共享数据有不同的访问模式，应该使用的自旋锁变种也不尽相同。

禁用抢占不禁用中断

如果共享的数据可能被多个任务访问，而且这些任务可能运行在不同 CPU 上，那么我们应该使用 raw spinlock 加禁用抢占。具体来说，就是首先禁用当前任务的抢占，然后获取自旋锁。

这种自旋锁可以称作 task spinlock，因为它可以防止任务切换和多核带来的竞争。这种自旋锁没有关闭中断，但这对程序的逻辑没有影响，即使在临界区内发生中断，中断处理函数也不会操作这个共享的全局数据，而且即使创建了新的任务也不可能抢占当前的任务。因此，当前任务的临界区得以顺利执行完毕。

保持中断开启能提高系统的响应性，避免丢失中断。对于实时操作系统而言，这是非常关键的。

禁用抢占和中断

如果有一个全局数据，被任务所使用，同时也会被 ISR 函数操作，那么这样的数据，我们就需要一种更强的自旋锁，不仅关闭抢占，还要禁用中断。这种类型的自旋锁在获取的时候，首先关闭当前 CPU 的中断，然后禁用当前任务的抢占，最后获取 raw spinlock。

由于临界区内抢占和中断均关闭，因此当前执行的代码不会被打断，即使创建了一个新的优先级更高的任务，也不会进行任务切换，保证在当前 CPU 范围内的独占权。同时 raw spinlock 还保证了不同 CPU 之间的互斥。