[系统运维][一文搞懂]深入浅出linux同步机制

因为现代操作系统是多处理器计算的架构，必然更容易遇到多个进程，多个线程访问共享数据的情况，如下图所示：

图中每一种颜色代表一种竞态情况，主要归结为三类：

1. 进程与进程之间：单核上的抢占，多核上的SMP；
2. 进程与中断之间：中断又包含了上半部与下半部，中断总是能打断进程的执行流；
3. 中断与中断之间：外设的中断可以路由到不同的CPU上，它们之间也可能带来竞态；

本章主要是学习的内容如下：

• 原子锁解决什么问题，有什么缺陷
• 自旋锁解决什么问题，原理和应用场景
• 睡眠锁解决什么问题，mutex和Semaphore原因和应用场景
• 各个锁之间的区别和联系

1 原子操作

1.1 产生起源

我们的程序逻辑经常遇到这样的操作序列：

1、读一个位于memory中的变量的值到寄存器中

2、修改该变量的值（也就是修改寄存器中的值）

3、将寄存器中的数值写回memory中的变量值

如果这些操作是一个串行化的操作(在一个thread中串行执行)，那么一切是OK的，但是世界总不能如我们所愿，在现在的多CPU架构和支持抢占的内核系统中，总会出现各种奇怪的现象。

处理器在访问共享资源时，必须对临界区进行同步，即保证同一时间内，只有一个对临界区的访问者。当共享资源为一内存地址时，原子操作是对该类型共享资源同步访问的最佳方式。随着应用的日益复杂和SMP的广泛使用，处理器都开始提供硬件同步原语以支持原子地更新内存地址。

从ARMv6架构开始，ARM处理器提供了Exclusive accesses同步原语，包含两条指令： LLDREX和STREX指令，将对一个内存地址的原子操作拆分成两个步骤，同处理器内置的记录exclusive accesses的exclusive monitors一起，完成对内存的原子操作。详细见http://www.lujun.org.cn/?p=4148

LDREX

LDREX与LDR指令类似，完成将内存中的数据加载进寄存器的操作。与LDR指令不同的是，该指令也会同时初始化exclusive monitor来记录对该地址的同步访问。例如
LDREX R1, [R0]

会将R0寄存器中内存地址的数据，加载进R1中并更新exclusive monitor。

STREX

该指令的格式为：
STREX Rd, Rm, [Rn]

STREX会根据exclusive monitor的指示决定是否将寄存器中的值写回内存中。如果exclusive monitor许可这次写入，则STREX会将寄存器Rm的值写回Rn所存储的内存地址中，并将Rd寄存器设置为0表示操作成功。如果exclusive monitor禁止这次写入，则STREX指令会将Rd寄存器的值设置为1表示操作失败并放弃这次写入。应用程序可以根据Rd中的值来判断写回是否成功。

所以对于那些有多个内核控制路径进行read-modify-write的变量，内核提供了一个原子变量的操作函数在Linux内核文件arch\arm\include\asm\atomic.h中。

typedef struct {
	int counter;
} atomic_t;

• volatile修饰字段告诉gcc不要对该类型的数据做优化处理，对它的访问都是对内存的访问，而不是对寄存器的访问。

特殊的地方在于它的操作函数，如下(下表中v都是atomic_t指针)：

1.2 原子变量内核实现

我们以atomic_add为例，描述linux kernel中原子操作的具体代码实现细节,我们以ARM为例，arch/arm/include/asm/atomic.h

#define ATOMIC_OPS(op, c_op, asm_op)					\
	ATOMIC_OP(op, c_op, asm_op)					\
	ATOMIC_OP_RETURN(op, c_op, asm_op)				\
	ATOMIC_FETCH_OP(op, c_op, asm_op)

ATOMIC_OPS(add, +=, add)
ATOMIC_OPS(sub, -=, sub)

我们以ATOMIC_OP(add, +=, add)为例，看它是如何实现atomic_add函数的，对于UP系统、SMP系统，分别有不同的实现方法。

ATOMIC_OP在UP系统中的实现

对于ARMv6以下的CPU系统，不支持SMP。原子变量的操作简单粗暴：关中断，中断都关了，谁能来打断我？代码如下(arch/arm/include/asm/atomic.h)：

ATOMIC_OP在SMP系统中的实现

对于ARMv6及以上的CPU，有一些特殊的汇编指令来实现原子操作，不再需要关中断，代码如下(arch\arm\include\asm\atomic.h)：

在ARMv6及以上的架构中，有ldrex、strex指令，ex表示exclude，意为独占地。这2条指令要配合使用，举例如下

1. 读出：ldrex %0, [%3] 意思是将&v->counter指向的数据放入result中，并且（分别在Local monitor和Global monitor中）设置独占标志，如果有其他的程序再次执行该指令，一样会成功，一样会标记所指向的内存为独占访问

• 其中％3就是input operand list中的"r" (&v->counter)，r是限制符（constraint）

  ％0对应output openrand list中的"=&r" (result)，=表示该操作数是write only的，&表示该操作数是一个earlyclobber operand

1. 修改r0的值， result = result + i
   

• ％0这个output操作数已经被赋值为atomic_t变量的old value， 这里的操作是要给old value加上i

  这里％4对应"Ir" (i)，这里“I”这个限制符对应ARM平台，表示这是一个有特定限制的立即数，该数必须是0～255之间的一个整数通过rotation的操作得到的一个32bit的立即数

1. 写入：strex %1, %0, [%3] 意思是将result保存到&v->counter指向的内存中，此时 Exclusive monitors会发挥作用，将保存是否成功的标志放入tmp中。

2. teq %1, #0 测试strex是否成功（tmp == 0 ？？）

3. bne 1b 如果发现strex失败，从（1）再次执行。

• 如果％3的“独占访问”标记还存在，则把％0的新值写入％1所指内存，并且清除“独占访问”的标记，把％1设为0表示成功

  如果％3的“独占访问”标记不存在了，就不会更新内存，并且把％1设为1表示失败。

通过上面的分析，可知关键在于strex的操作是否成功的判断上。而这个就归功于ARM的Exclusive monitors和ldrex/strex指令的机制。

假设这样的抢占场景：
① 程序A在读出、修改某个变量时，被程序B抢占了；
② 程序B先完成了操作，程序B的strex操作会清除“独占访问”的标记；
③ 轮到程序A执行剩下的写入操作时，它发现独占访问”标记不存在了，于是取消写入操作。
这就避免了这样的事情发生：程序A、B同时修改这个变量，并且都自认为成功了。

1.3 原子位的内核实现

能操作原子变量，再去操作其中的某一位，不过内核为我们做好了支持原子位的同步机制，其原子位的操作函数在Linux内核文件arch/arm/include/asm/bitops.h，在ARMv6以下的架构里，不支持SMP系统，原子位的操作函数也是简单粗暴：关中断。以set_bit函数为例，如下

在ARMv6及以上的架构中，不需要关中断，有ldrex、strex等指令，这些指令的作用在前面介绍过。还是以set_bit函数为例，代码如下：

2 linux内核锁的原理介绍

原子锁解决了我们对于变量的访问，例如在SMP系统中，如果仅仅是需要串行地访问一个变量的值，那么使用原子操作的函数（API）就可以了。但现实中更多的场景并不会那么简单，比如需要将一个结构体A中的数据提取出来，然后格式化、解析，再添加到另一个结构体B中，这整个的过程都要求是「原子的」，也就是完成之前，不允许其他的代码来读/写这两个结构体中的任何一个。

这时，相对轻量级的原子操作API就无法满足这种应用场景的需求了，我们需要一种更强的同步/互斥机制，那就是软件层面的「锁」的机制。

Linux内核提供了很多类型的锁，它们可以分为两类：
① 自旋锁(spinning lock): 无法获得锁时，不会休眠，会一直循环等待
② 睡眠锁(sleeping lock): 无法获得锁时，当前线程就会休眠

2.1 自旋锁spinlock

2.1.1 spinlock原理介绍

自旋锁最初的设计就是为了SMP系统设计，实现多处理器情况下保护临界区。对于UP系统，只需要关闭中断和抢占就可以了，没有实现真正的自旋操作。

Linux内核中最常见的锁是自旋锁，自旋锁最多只能被一个可执行线程持有。如果一个线程试图获取一个已被持有的自旋锁，这个线程会进行忙循环——旋转等待(会浪费处理器时间)锁重新可用，自旋锁持有期间不可被抢占。所有自旋锁有以下特点

• spin lock是一种死等的锁机制。当发生访问资源冲突的时候，可以有两个选择：一个是死等，一个是挂起当前进程，调度其他进程执行。spin lock是一种死等的机制，当前的执行thread会不断的重新尝试直到获取锁进入临界区。
• 只允许一个thread进入。semaphore可以允许多个thread进入，spin lock不行，一次只能有一个thread获取锁并进入临界区，其他的thread都是在门口不断的尝试。
• 执行时间短。由于spin lock死等这种特性，因此它使用在那些代码不是非常复杂的临界区（当然也不能太简单，否则使用原子操作或者其他适用简单场景的同步机制就OK了），如果临界区执行时间太长，那么不断在临界区门口“死等”的那些thread是多么的浪费CPU啊（当然，现代CPU的设计都会考虑同步原语的实现，例如ARM提供了WFE和SEV这样的类似指令，避免CPU进入busy loop的悲惨境地）
• 可以在中断上下文执行。由于不睡眠，因此spin lock可以在中断上下文中适用。
• 要想在用户态实现竞争一个共享资源, 必须借助cpu提供的原子操作指令. 如果是SMP多cpu,还需要lock指令锁总线

从保护临界区访问原子性的目的来考虑，自旋锁应该阻止在代码运行过程中出现的任何并发干扰，这些干扰包括以下内容：

• 中断(关中断)： 保护硬件中断和软件中断（仅在中断代码可能访问临界区时需要），对于这种干扰存在任何系统中，一个中断的到来导致了中断服务程序的执行，如果中断访问了临界区，原子性被打断。对于不同的中断类型（硬件中断和软件中断）对应于不同版本的自旋锁实现，其中包含了中断禁用和开启的代码。但是如果你保证没有中断代码会访问临界区，那么使用不带中断禁用的自旋锁API即可。
• 内核抢占(关抢占)： 在linux2.6以后的内核，开始支持内核抢占，在内核态的并发执行，这种情况下进入临界区就需要避免因抢占造成的并发，所以解决的方法就是在加锁时禁用抢占（preempt_disable()），在开锁时开启抢占（preempt_enable();注意此时会执行一次抢占调度）（仅存在于可抢占内核中）
• 其他处理器对同一临界区的访问(原子指令)： 在SMP系统中，多个物理处理器同时工作，导致可能有多个进程物理上的并发。这样就需要在内存加一个标志，每个需要进入临界区的代码都必须检查这个标志，看是否有进程已经在这个临界区中。这种情况下检查标志的代码也必须保证原子和快速，这就要求必须精细地实现，正常情况下每个构架都有自己的汇编实现方案，保证检查的原子性，这就需要芯片实现物理上的内存地址独占访问才能实现多核访问临界区的问题。

所以对于自旋锁针对抢占是通过关抢占，就会涉及到调度，对于中断，就会关中断，也涉及到调度，对于同一临界区是通过独占访问来自旋，在原地“忙等”，反复执行一条紧凑的循环检测指令，直到锁被释放，每一个操作都是很危险的，会影响系统的性能和稳定性，所以它保护的临界区必须小，且操作必须短。

2.1.2 自旋锁的内核函数

如果被保护的临界区只在进程上下文中访问，不会在任何的中断上下文中操作临界区，那么对共享资源的访问仅需要用spin_lock和spin_unlock来保护，如下的接口实现

如果保护的临界区可能在中断上下文和进程上下文中访问，那么可以使用如下的接口实现

• 如果被保护的共享资源在进程上下文和软中断(taskle等)上下文，那么当在进程上下文访问共享资源时，可能被软中断打断，从而可能进入软中断上下文对保护的共享资源访问，因此这种情况下，对共享资源的访问必须使用spin_lock_bh和spin_unlock_bh来保护。当然使用spin_lock_irq和spin_unlock_irq以及spin_lock_irqsave和spin_unlock_irqrestore也可以，它们失效了本地硬中断，失效硬中断隐式地也失效了软中断。但是使用spin_lock_bh和spin_unlock_bh是最恰当的，它比其他两个快。
• 如果被保护的共享资源在软中断（包括tasklet和timer）或进程上下文和硬中断上下文访问，那么在软中断或进程上下文访问期间，可能被硬中断打断，从而进入硬中断上下文对共享资源进行访问，因此，在进程或软中断上下文需要使用spin_lock_irq和spin_unlock_irq来保护对共享资源的访问。
• 但是如果有不同的中断处理句柄访问该共享资源，那么需要在中断处理句柄中使用spin_lock_irq和spin_unlock_irq来保护对共享资源的访问。
• 在使用spin_lock_irq和spin_unlock_irq的情况下，完全可以用spin_lock_irqsave和spin_unlock_irqrestore取代
• 如果可以确信在对共享资源访问前中断是使能的，那么使用spin_lock_irq更好一些。因为它比spin_lock_irqsave要快一些，但是如果你不能确定是否中断使能，那么使用spin_lock_irqsave和spin_unlock_irqrestore更好，因为它将恢复访问共享资源前的中断标志而不是直接使能中断

2.1.3 内核实现

spinlock对应的结构体如下定义，不同的架构可能有不同的实现：

上述__raw_tickets结构体中有owner、next两个成员，这是在SMP系统中实现spinlock的关键。

对于单CPU系统，没有“其他CPU”；如果内核不支持preempt，当前在内核态执行的线程也不可能被其他线程抢占，也就“没有其他进程/线程”。所以，对于不支持preempt的单CPU系统，spin_lock是空函数，不需要做其他事情。

对于单CPU系统的内核支持preempt，即当前线程正在执行内核态函数时，它是有可能被别的线程抢占的。这时spin_lock的实现就是调用“preempt_disable()”：你想抢我，我干脆禁止你运行。

对于SMP系统， 要让多CPU中只能有一个获得临界资源，使用原子变量就可以实现。但是还要保证公平，先到先得。比如有CPU0、CPU1、CPU2都调用spin_lock想获得临界资源，谁先申请谁先获得。这个过程中很像我们去营业厅办理业务的叫号系统

在整个过程中，每个使用者维护自己的onwer和全局的next，即使同时上锁，也能保证不冲突，当next=owner的时候，表示该CPU获得锁

在ARMv6及以上的ARM架构中，支持SMP系统。它的spinlock结构体定义如下：

类比我们生活中的叫号系统，onwer相当于现在电子叫号，现在该谁在进行服务，next就相当于下下一个服务，每个CPU从取号机上取得号码都保存在spin_lock函数中的局部变量。spin_lock函数调用关系如下，核心是arch_spin_lock：

• 首先当然是调用preempt_disable()关闭抢占，spin_acquire是和运行时检查锁的有效性有关，如果没有定义CONFIG_LOCKDEP，这个函数为空 函数，
• LOCK_CONTENDED 是一个通用的加锁流程。do_raw_spin_trylock
  和do_raw_spin_lock的实现依赖于具体的体系结构，以 x86 为例，do_raw_spin_trylock最终调用，而ARM则调用do_raw_spin_lock

我们已ARM为例，并且CONFIG_DEBUG_SPINLOCK未定义情况下，arch_spin_lock/arch_spin_unlock最终调用如下

2.2 信号量semaphore

关于信号量的内容，实际上它是与自旋锁类似的概念，只有得到信号量的进程才能执行临界区的代码；不同的是获取不到信号量时，进程不会原地打转而是进入休眠等待状态。

2.2.1 内核函数

一个任务要想访问共享资源，首先必须得到信号量，获取信号量的操作将把信号量的值减1，若当前信号量的值为负数，表明无法获得信号量，该任务必须挂起在该信号量的等待队列等待该信号量可用；若当前信号量的值为非负数，表示可以获得信号量，因而可以立刻访问被该信号量保护的共享资源。

当任务访问完被信号量保护的共享资源后，必须释放信号量，释放信号量通过把信号量的值加1实现，如果信号量的值为非正数，表明有任务等待当前信号量，因此它也唤醒所有等待该信号量的任务。

semaphore函数在内核文件include\linux\semaphore.h中声明，如下表：

2.2.2 内核实现

信号量的定义及操作函数都在Linux内核文件include\linux\semaphore.h中定义，如下：

初始化semaphore之后，就可以使用down函数或其他衍生版本来获取信号量，使用up函数释放信号量。我们只分析down、up函数的实现。

如果有其他进程在等待信号量，则count值无需调整，直接取出第1个等待信号量的进程，把信号量给它，把它唤醒。如果没有其他进程在等待信号量，则调整count

2.3 互斥量mutex

互斥量用于线程的互斥，信号量用于线程的同步： 一个互斥量只能用于一个资源的互斥访问不能实现多个资源的多线程互斥问题； 一个信号量可以实现多个同类资源的多线程互斥和同步。

2.3.1 内核函数

mutex函数在内核文件include\linux\mutex.h中声明，如下表：

2.3.2 内核实现

semaphore中可以指定count为任意值，比如有10个厕所，所以10个人都可以使用厕所。
而mutex的值只能设置为1或0，只有一个厕所。看一下mutex的结构体定义，如下：

它里面有一项成员“struct task_struct *owner”，指向某个进程。一个mutex只能在进程上下文中使用：谁给mutex加锁，就只能由谁来解锁。而semaphore并没有这些限制，它可以用来解决“读者-写者”问题：程序A在等待数据──想获得锁，程序B产生数据后释放锁，这会唤醒A来读取数据。semaphore的锁定与释放，并不限定为同一个进程。

fastpath

mutex的设计非常精巧，比semaphore复杂，但是更高效。首先要知道mutex的操作函数中有fastpath、slowpath两条路径(快速、慢速)：如果fastpath成功，就不必使用slowpath。

大部分情况下，mutex当前值都是1，所以通过fastpath函数可以非常快速地获得mutex。

might_sleep(): 指示当前函数可以睡眠。当CONFIG_DEBUG_ATOMIC_SLEEP开启，如果它所在的函数处于原子上下文(atomic context)中(如，spinlock, irq-handler…)，将打印出堆栈的回溯信息。这个函数主要用来做调试工作，在你不确定不期望睡眠的地方是否真的不会睡眠时，就把这个宏加进去。默认这个为空，内核只是用它来做一件事，就是提醒你，调用该函数的函数可能会sleep。
slowpath

如果mutex当前值是0或负数，则需要调用__mutex_lock_slowpath慢慢处理：可能会休眠等待。

_mutex_lock_common函数也是在内核文件kernel/locking/mutex.c中实现的，分析第一段代码：

mutex_unlock函数中也有fastpath、slowpath两条路径(快速、慢速)：如果fastpath成功，就不必使用slowpath。

大部分情况下，加1后mutex的值都是1，表示无人等待mutex，所以通过fastpath函数直接增加mutex的count值为1就可以了。
如果mutex的值加1后还是小于等于0，就表示有人在等待mutex，需要去wait_list把它取出唤醒，这需要用到slowpath的函数：__mutex_unlock_slowpath。

__mutex_unlock_common_slowpath函数代码如下，主要工作就是从wait_list中取出并唤醒第1个进程：

?在 Linux kernel 中，一开始是只有 semaphore 这个 structure，直到 2.6.16 版当中才把 mutex 从 semaphore 中分离出来 （这点可以从 LDD3e* 看出来）。 虽然 Mutex 与 Semaphore 两者都是休眠锁，但是 Linux kernel 在实作 Mutex 的时候，有用到一些加速的技巧，将上锁分为3个步骤：?

1. ?Fast path： 尝试使用 atomic operation 直接减少 counter 数值来获得锁。?
2. ?Mid path： 第一步失败的话，尝试使用特化的 MCS spinlock 等待然后取锁。 ?? 当持锁的 thread 还在运行，而且没有存在更高 priority 的 task 时，我们可以大胆假设，持锁 thread 很快就会把 thread 释放出来 （看看 code 就知道了），因此会使用一个特化的 MCS spinlock 等待锁被释放。 特化的MCS spinlock可以在被 reschedule 的时候退出 MCS spinlock queue。 当走到这步时，就会到 Slow path。?
3. ?Slow path： 锁没有办法取得，只好把自己休眠了。 ?? ??走到这一步，mutex 才会将自己加入 wait-queue 然后休眠，等待有人 unlock 后才会被唤醒。?

总结

Mutex 与 Semaphore 最大的差异是：?

• 最大的差异在于 Mutex 只能由上锁的 thread 解锁，而 Semaphore 没有这个限制，可以由原本的 thread 或是另外一个 thread 解开
• Mutex 只能让一个 thread 进入 critical section，Semaphore 的话则可以设定要让几个 thread 进入
• 而 Semaphore 更常是用在同步两个 thread 或功能上面，因为 Semaphore 实际上使用的是 signal 的 up 与 down，让 Semaphore 可以变成是一种 notification 的作用，例如 A thread 执行到某个地方时 B thread 才能继续下去，就可以使用 Semaphore 来达成这样的作用。
• Mutex用于线程的互斥，Semaphore 用于线程的同步： 一个互斥量只能用于一个资源的互斥访问不能实现多个资源的多线程互斥问题； 一个信号量可以实现多个同类资源的多线程互斥和同步。

参考文档

深入分析Linux自旋锁

[Linux内核ARM构架中原子变量的底层实现研究 ]

Linux中的spinlock机制 - CAS和ticket spinlock

韦东山锁机制