Linux内核并发与同步机制解读（arm64）上

关键词原子操作、自旋锁、信号量、mutex、读写锁、percpu-rwsem

概述

从浅到深，逐步分析各种同步机制的功能。

1、原子操作

解决“读-修改-回写”的完整性，一般用于静态全局变量的保护，静态全局变量的操作过程.

例如，我们写一行代码把变量a加1，编译器把代码编译成3条汇编指令。

（1）把变量a从内存加载到寄存器。

（2）把寄存器的值加1。

（3）把寄存器的值写回内存。

由于是三条指令，无法保障三条指令中间不会被抢占。通过一个实际的案例场景来帮助理解。

在上面的执行场景，进程2对a+1的结果被进程1覆盖了，最终看到的结果是a仅被+1，我们期望a被+2。

1.1.1常用原子操作函数

函数原型	语义
atomic_read(v)	读取原子变量v的值
atomic_add_return(i, v)	把原子变量v的值加上i，并且返回新值
atomic_add(i, v)	把原子变量v的值加上i
atomic_inc(v)	把原子变量v的值加上1
int atomic_add_unless(atomic_t *v, int a, int u);	如果原子变量v的值不是u，那么把原子变量v的值加上a，并且返回1，否则返回0
atomic_inc_not_zero(v)	如果原子变量v的值不是0，那么把原子变量v的值加上1，并且返回1，否则返回0。
atomic_sub_return(i, v)	把原子变量v的值减去i，并且返回新值
atomic_sub(i, v)	把原子变量v的值减去i
atomic_dec(v)	把原子变量v的值减去1
atomic_cmpxchg(v, old, new)	执行原子比较交换，如果原子变量v的值等于old，那么把原子变量v的值设置为new。返回值总是原子变量v的旧值
{}_relaxed	不内嵌内存屏障原语
{}_acquire	内置了加载-获取内存屏障园原语
{}_release	内置了存储-释放内存屏障原语

在这些基础原子操作函数上，又进行了一些演进，得到了很多的原子操作函数。所有的原子操作函数可以直接查看atomic-fallback.h

2、经典自旋锁

2.1原理介绍

自旋锁用于处理器之间的互斥，适合保护很短的临界区，并且不允许在临界区睡眠。申请自旋锁的时候，如果自旋锁被其他处理器占有，本处理器自旋等待（也称为忙等待）。

进程、软中断和硬中断都可以使用自旋锁。

目前内核的自旋锁是排队自旋锁（queued spinlock，也称为“FIFO ticket spinlock”），算法类似于银行柜台的排队叫号。

（1）锁拥有排队号和服务号，服务号是当前占有锁的进程的排队号。

（2）每个进程申请锁的时候，首先申请一个排队号，然后轮询锁的服务号是否等于自己的排队号，如果等于，表示自己占有锁，可以进入临界区，否则继续轮询。

（3）当进程释放锁时，把服务号加1，下一个进程看到服务号等于自己的排队号，退出自旋，进入临界区。

2.2代码实现

2.2.1关键数据结构

数据结构中除了owner是指针变量，其他都是实体变量，也就是说spinlock 结构体定义一个spinlock变量，那么结构体里的变量都会被实例化。

2.2.2关键函数接口

2.2.2.1spin_lock_init

如果没有开debug宏，初始化函数仅对raw_lock初始化为0

2.2.2.2spin_lock

spin_lock() -> raw_spin_lock() -> _raw_spin_lock() -> __raw_spin_lock() -> do_raw_spin_lock() -> arch_spin_lock()

代码实现很简单，lock->slock先读一份保存在本地lockval，然后lock->slock的next位域+1，然后在while循环中判断owner域是否等于本地记录的next域，如果相等就表示拿锁成功。

2.2.2.3spin_unlock

spin_unlock->__raw_spin_unlock->do_raw_spin_unlock->arch_
spin_unlock

释放锁的逻辑也非常简单直接对ower位域+1.

2.3稳定性维测能力介绍

假设某个thread拿了spinlock后长时间不释放，引发了稳定性问题，
如何来定位具体是哪个线程拿了锁。可以通过CONFIG_DEBUG_SPINLOCK开关打开持锁的owner跟踪。

2.4应用场景

保护执行路径短且快。

2.5思考

2.5.1开CONFIG_DEBUG_SPINLOCK是否会引入性能问题

Debug的原理就是增加了一个owner指针变量来记录拿锁的task，对owner的操作仅是简单的赋值，因此对性能的影响可以忽略不计。

2.5.2raw_spinlock与spinlock的区别？

在arm64上，两个函数完全等价。

3、信号量

3.1原理介绍

锁创建时通过count（钥匙数量）值定义了最多可以有多少条路径同时访问临界区。假设初始时count值初始化为n（制造n把进入临界区的钥匙），那么允许有n个thread同时获得锁，n把钥匙都用完了，还有想申请钥匙的线程，就只能放到等待队列中了。

这个机制没有定义进入临界区的线程的具体行为（read，write），如果拿到钥匙的线程都写临界区的数据，那么临界区最终的数据是不可预测的。这也就导致了这个机制无法推广使用（不是不用，实在没法用）。一些铁杆粉丝非要使用它，那么只能将count值初始化为1，当互斥信号量使用。

为了对后续其他锁理解，简要说明信号量机制关键数据结构与关键函数接口。

3.2代码实现

3.2.1关键数据结构

3.2.2关键函数接口

3.2.2.1semaphore 的初始化

主要完成struct semaphore的3个变量初始化，DEFINE_SEMAPHORE初始化宏，给count值默认为1.

3.2.2.2down

实现逻辑比较简单，count > 0就可以快速拿到锁，如果count = 0，就走慢速路径__down，慢路径里可能会睡眠。慢速路径不再做详细分析。

3.2.2.3up

释放锁，对count++，如果wait_list不为null，唤醒第一个waiter。

3.3应用场景

不推荐使用。

3.4思考

Count是个全局变量，多个CPU可能并行操作，可能造成致命的同步问题。
如果出现死锁造成稳定性问题，无法根据问题现场定位出问题根因。

4、互斥锁-mutex

4.1原理介绍

主要实现资源的互斥操作，确保在一个时刻只有一个线程可以操作临界资源。

Mutex在变量owner上做较多文章。通过判断owner是0与非0来区分锁是否空闲状态。当有线程进入临界区（获得锁），将该线程的task赋值给owner，方便定位死锁问题。通过flag标记位实现乐观自旋与handoff机制。

为了快速理解代码的实现，下面用问答的形式，来帮助深度理解锁的实现原理。

4.1.1互斥锁与互斥信号量原理类似，为什么还要实现互斥锁？

互斥锁相对互斥信号量要轻便一些，数据结构比信号量小，执行速度比信号量快，加入了乐观自旋等待机制。

互斥锁最先实现自旋等待；
互斥锁在睡眠之前会尝试获取锁；
互斥锁通过实现MCS锁避免多个CPU争用锁导致的CPU高速缓存颠簸；
互斥锁允许睡眠，不能在中断处理函数等实时性要求高的场景使用；
互斥锁用owner（原子变量）替换了count（全局变量），避免“读-写”的同步问题，同时便于定位死锁问题。

互斥信号量是一个简陋的同步机制。

4.1.2什么是偷锁，偷锁是怎么产生的

锁的持有者A，用完锁理应传递给B，B去A这里接手锁的时候发现锁已经在C那里了。锁在交接的过程中被C偷走了。

进程A释放锁，并把B唤醒让B持锁，但是巧了，C在A释放锁的时候正在申请锁，在看B这会儿还睡者，A一释放，C就抢走了，等B醒来，没自己啥事了。如果不好理解，举一个乌鸦与狐狸的故事，乌鸦嘴里衔着一块肉，乌鸦准备把这块肉给正再睡觉的小乌鸦，乌鸦张嘴叫小乌鸦的时候，而正好被狐狸路过看见，等小乌鸦醒来肉已不见了只能继续睡。

4.1.3为什么要引入乐观自旋

假设一种场景：持锁的进程A即将放锁，进程B发起锁的申请，B看锁已被占用，立即就会睡眠，睡眠后立即又被A唤醒，这期间在调度上的开销不可忽略。也就是说进程B不睡眠乐观的忙等，开销可能比睡眠要小得多。这就是乐观自旋机制的作用。

4.1.4什么情况下该乐观且乐观多久

还有剩余时间片且owner仍然在CPU上运行。一般是50us。用户可以根据自行的实际情况来设置。

4.1.5为什么需要handoff机制

乐观自旋加剧了偷锁的概率。乐观自旋机制的加入改变了“乌鸦与狐狸”剧本，上文中的狐狸恰巧撞上一块肉，加入乐观自旋后，狐狸盯着乌鸦嘴里的肉一段时间，狐狸偷走肉的概率大大提升了。要命的是如果运气不好接下来的几天肉都被狐狸偷走，小乌鸦就活活被饿死了。经过反思后就设计了HANDOFF机制来避免waiter饿死悲剧的发生。

4.1.6HANDOFF机制的原理

Wait_list上第一个waiter被唤醒后立即设置HANDOFF标记位，如果锁此时被偷，小偷释放锁时，直接把锁交给第一个waiter（在__mutex_unlock_slowpath中直接将第一个waiter的task赋值给lock->owner）,这就保证了第一个waiter的锁最多被偷一次。