自旋锁

参考资料:

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

不加锁会有哪些问题

首先考虑单核硬件上的情况。现代操作系统一般都是多任务的,而且是抢占式多任务,也就是在任务执行过程中的任何时刻,都有可能被系统换出,切换到一个新的任务运行。然而,多个任务有可能使用了相同的全局数据,这就有可能导致数据竞争(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_counterticket_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 之间的互斥。