Linux内核同步的实现方式总结
目录
1、原子操作
原子操作用来保证执行过程不被打断，是很多其他同步方法的基石。
操作系统对原子操作的实现是基于汇编的，另外现在很多处理器也提供了原子操作的原语级支持。
Linux操作系统实现了三种原子操作：32位整数原子操作、64位整数原子操作、位原子操作。
- 原子整数操作：原子整数操作的操作对象是32位的整数，常用场景是实现计数器，操作系统提供了自增1和自减1的原子操作，用于支持计数器。
- 64位整数原子操作：原子操作的目标是64位的数字。64位的操作系统通常需要64位整数的原子操作，但是大多数32位操作系统不支持，x86-32除外。
- 原子位操作：原子位操作是用来对给定指针指向的内存地址中，数据特定的位进行操作。
2、自旋锁
2.1 自旋锁
Linux最常见的锁是自旋锁。自旋锁可以保证被加锁的目标最多只被一个线程持有，如果有线程试图获取一个正在已经被持有的自旋锁，即锁竞争发生的时候，该试图持锁的线程就会进行忙等待，自旋等待锁可以重新启用。
自旋锁会关闭内核抢占，持有自旋锁的进程，不会被其他进程抢占CPU。
1、自旋锁的适用场景
由于在锁争用的时候，自旋锁会导致线程忙等待，这会浪费处理器的资源，所以自旋锁不应该长期被持有。自旋锁应该用来给等待时间很短的场景添加轻量级锁，这样可以避免线程挂起和唤醒带来的两次上下文切换的开销。
2、单处理器下的自旋锁
需要注意的是，单处理器上不需要自旋锁。单处理器在编译的时候，会将自旋锁简化为是否启用内核抢占的开关。
3、Linux的自旋锁不可重入
Linux的自旋锁是不支持递归的，换句话说，Linux的自旋锁不可重入。这一点可能和其他操作系统的实现不同。Linux下，如果持有自旋锁的任务视图获取自己已经持有的锁，则会陷入忙等待，而没有时间释放自己的锁，导致自己陷入死锁。
4、自旋锁和中断
中断处理程序中如果需要加锁，可以使用自旋锁，因为自旋锁不会陷入睡眠。当然中断处理程序获取自旋锁之前需要先禁止本地中断，因为其他中断处理程序可能会打断当前持有自旋锁的中断处理程序，并再次请求该自旋锁，并陷入忙等待无法结束。
2.2 读写自旋锁
很多时候，对于锁来说，读和写是两种不同的处理场景。写操作对并发的控制相对严格，不允许并发，包括写操作和写操作、写操作和读操作之间的并发；但是读操作的并发要求相对较低，读操作和读操作之间互不干扰，对并发没有限制。
Linux内核提供了一种读-写自旋锁，分别为读操作和写操作提供了不同的锁。多个读操作可以同时获取到读锁，但是一旦有任务获取了写锁，则其他任务不允许再获取读锁和写锁。
这种读写锁相对来说对于读锁更友好，因为一旦有大量的任务都在读锁，写任务只能陷入等待，而读任务依然可以源源不断地获取读锁，导致写任务陷入饥饿。
2.3 如何避免死锁
虽然很难保证代码一定不会出现死锁，但是一些规则对避免死锁发生有很大帮助：
- 按顺序加锁。使用嵌套的锁时，必须保证对所有获取锁的任务都以相同的顺序加锁，这样可以避免致命拥抱类型的死锁
- 防止发生饥饿。判断代码的执行是否一定会结束，如果某种情况一直不发生，是否有必要一直等待下去
- 不要重复请求同一个锁
- 设计尽量简单。越复杂的加锁方案，就越有可能造成死锁
3、信号量
3.1 信号量
Linux的信号量是一种睡眠锁。如果任务想要获取一个不可用的信号量时，信号量会将任务推进一个队列，然后让这个任务睡眠。这时处理器可以去处理其他任务。当该信号量可用后，处于等待队列的任务将被唤醒，并获得该信号量。
信号量的睡眠是可以被打断的，Linux内核同时提供了可以被打断和不允许被打断两种方式。
1、信号量的使用者数量
信号量允许任意数量的锁持有者，这个数量可以在声明信号量的时候指定。这个数量被称为信号量的使用者数量，或者数量。
2、互斥信号量和计数信号量
使用者数量为1的信号量，被称为互斥信号量，或者二值信号量。这种信号量只允许一个进程持锁，是一种Linux内核常用的锁。
如果使用者数量大于1，这种被称为计数信号量。这种运行多个进程同时持有锁，相对来说使用的机会较少。
3、信号量和自旋锁对比
- 信号量适用于锁会被长时间持有的情况。如果锁持有时间较短，自旋锁会更合适；
- 信号量只能用于进程上下文，而不能用于中断上下文。由于信号量发生争用的时候，没获取到信号量的进程会睡眠，而中断上下文不允许睡眠，所以中断上下文中只能使用自旋锁；
- 任务占用自旋锁的时候不允许请求信号量，因为持有自旋锁的时候不允许睡眠，但是等待信号量的时候会睡眠；
- 信号量允许多个进程同时持有锁，而自旋锁最多只能有一个任务持锁。
3.2 读写信号量
读写信号量和信号量的关系，与读写自旋锁和自旋锁的关系类似。
读写信号量会对写任务的数量进行约束，但是不会对读信号量的数量有任何限制。
需要注意的是，读写信号量的使用者数量只能是1，也就是说，最多只能有一个写任务持有信号量。
和信号量不同的是，读写信号量的睡眠是不允许被动打断的。
和读写自旋锁不同的是，Linux内核提供了一种锁升级的机制，可以将读信号量升级为写信号量。而读写自旋锁不能锁升级。
4、互斥体
原本，互斥体是描述任何可以睡眠的互斥锁，但是在Linux内核3.18版本中，引入了一种新的锁机制：互斥体（mutex）。这种互斥体的行为和计数为1的信号量基本相同，区别在于互斥体的接口操作更简洁、实现更高效、使用限制更强。
mutex的简洁性和高效性来源于它只实现了互斥锁的基本行为，因此也导致了它的使用场景更定向、限制更强：
- 任何时候只能有一个进程持锁。相当于计数为1的信号量
- 只能由加锁者自身来解锁。即不允许在一个上下文中加锁，在另一个上下文中解锁。这限制了mutex不能用于内核和用户空间同步的复杂场景，通常应该在同一个上下文中加锁和解锁
- 不允许递归的加锁和解锁。不允许获取已经获取的锁，也不允许解锁已经解锁的锁
- 当持有一个mutex时，进程不允许退出。
- mutex不能在中断和下半部中使用。
- mutex只能通过官方的API管理。只支持官方提供的基本操作，不允许被复制、手动初始化、或者重复初始化等。官方支持的操作包括：
互斥体和信号量的选择：
- 如果场景支持使用互斥体，则尽量使用互斥体；
- 如果场景有些限制导致不支持互斥体，这时再使用信号量。
互斥体和自旋锁的选择：
- 互斥体可能导致睡眠，则不支持睡眠的场景，例如中断、软中断等，只能使用自旋锁；
- 如果任务获取不到互斥体会陷入睡眠，如果持锁任务持锁时间较长，应该使用互斥体，避免自旋锁的忙等待消耗处理器资源；否则应该使用自旋锁，避免线程睡眠和唤醒带来的开销
5、完成变量
完成变量是一种使两个任务同步的简单方法，如果一个任务需要通知另一个任务发生了特定的事情，可以通过完成变量实现。如果一个任务去执行一项工作的时候，另一个任务就会在完成变量上面等待。当然，这种场景也可以通过信号量实现，完成变量是提供了一种简洁的、特定场景的信号量替代方案。例如当子进程执行或退出的时候，vfork()系统调用使用完成变量唤醒父进程。
完成变量定义在<linux/completion.h>中，使用完成变量的例子可以参考：kernel/sched.c和kernel/fork.c。
完成变量的官方API：
6、顺序锁
顺序锁也叫seq锁，是在2.6版本引入的新的锁。
1、加锁过程
顺序锁的实现主要依赖于序列计数器，这个序列计数器的技术是只增不减的。写任务访问添加顺序锁的数据的时候，首先会尝试获取顺序锁，如果成功获得顺序锁，则给序列计数器的计数加1 ；如果获取锁失败，则会挂起等待。获得锁的写任务执行完成写操作后，释放顺序锁之前会给序列计数器再加1。读操作不会有增加计数值的行为。
2、加锁的依据
从上面的描述可以看出，当有写任务在持有顺序锁的时候，序列计数器的计数是奇数，没有写任务执行的时候，计数是偶数。写任务判断是否能获取顺序锁的依据，就是该锁的计数是否是偶数。
对于读任务，在访问先回先判断计数是否是奇数，如果是奇数表示有写任务在执行，此时不会去执行读操作；如果计数是偶数，则去执行读操作，读完数据后会再次查询计数，检查是否和读数据之前的数据一样。如果读数据前后的计数一样，说明读数据期间没有发生写操作，读取到的数据是有效的；反之则说明读数据期间发生了写操作，读取到的数据是无效的。
3、顺序锁的特点
和读写锁相比，顺序锁对写操作更友好。读写锁是只要有源源不断的读操作存在，写操作就一直被阻塞；而对于顺序锁，读操作并不能阻塞写操作，只要有写操作存在，读操作就会一直被阻塞。所以顺序锁适合于写少读多但是写操作优先级又很高的场景。
4、顺序锁的缺点
顺序锁不能用来锁定指针，即共享资源中不允许存在指针。如果写操作操作指针的过程中，指针可能会无效，而这时如果读操作所在的任务恰好读取到了无效的指针并访问了该无效指针，就会发生异常。
7、禁止内核抢占
内核是具有抢占性的，内核中运行的任务随时有可能被优先级更高的任务抢占内核资源。有一些数据是不需要加锁但是不允许内核抢占的，例如不允许被并发访问每个处理器私有的资源。处理器私有的数据不会被其他处理器访问，所以不需要加锁；但是这些据不允许并发访问，所以需要通过禁止内核抢占来控制。实际上单核处理器上的自旋锁，就可以用禁止内核抢占来替代。
linux内核提供了一些preempt_*相关的方法，用来实现禁止内核抢占。
内核抢占相关的方法：
8、内存屏障
乱序重排：
编译器和处理器为了提升效率，可能会对读写操作重新排序。这被称为乱序重排。大多数处理器都会乱序重排，不过英特尔x86芯片不会。
对顺序有要求的场景：
- 当多处理器和硬件设备之间进行交互的时候，有时候需要以指定的顺序读内存（读入）或写内存（存储），比如可能经常需要一个读操作发生在一个写操作或者另一个读操作后面。
- 在多处理器上，可能需要按写数据的顺序读数据。
屏障：
基于以上背景，所有支持乱序重排的处理器都会提供一些机器指令来保障指令的执行顺序，这些确保顺序的指令被称为屏障。
Linux内核提供的内存屏障相关的方法：
- wmb()：提供了一种“写”内存屏障，会保障wmb()之前的存储命令不会在wmb()之后执行，同理，wmb()之后的存储命令也不会在wmb()之前执行；
- rmb()：提供了一种“读”内存屏障，和wmb()相似，区别在于rmb()保障的是读内存操作；
- mb()：同时提供了读屏障和写屏障，即mb()之前的读内存操作和写内存操作都不会在跨越mb()重新排序；
- read_barrier_depends()：和rmb()指令相似，也是提供了读内存屏障，区别在于read_barrier_depends()保障的是有依赖关系的读内存操作的顺序。比如a和b两个变量，给b赋值为a，则在a被b之间添加read_barrier_depends()指令后，可以保障a和b的读入顺序。在很多体系结构里面read_barrier_depends()执行的比rmb()快很多，因为操作系统默认保障了有依赖关系的读操作的顺序，所以read_barrier_depends()只是一个空指令。