【Kernel】内核同步
一、什么是内核同步
同步是指用于实现控制多个进程按照一定的规则或顺序访问某些系统资源的机制。
内核同步这里有一个官方形式的说法，但个人认为这一解释对理解其实际功能没什么帮助，这里仅仅对其进行引用。为了便于理解，这里介绍两个概念，临界区和竞争条件。
临界区：访问和操作共享数据的代码段。
竞争条件：两个执行线程在同一临界区中同时执行。
使用内核同步解决共享资源并发访问的问题。如果多个执行线程同时访问和操作数据，就有可能发生各线程之间相互覆盖共享数据的情况，造成被访问数据处于不一致状态，且这种问题难以跟踪和调试。所以这里就能够简单的理解什么是同步，即：避免并发和防止竞争条件。
二、内核中并发的主要来源
- 中断、软中断、tasklet：例如，当进程在访问某个临界资源的时候发生了中断，随后进入中断处理程序，如果在中断处理程序中，也访问了该临界资源。虽然不是严格意义上的并发，但是也会造成了对该资源的竞态。
- 内核态抢占：例如，当进程在访问某个临界资源的时候发生内核态抢占，随后进入了高优先级的进程，如果该进程也访问了同一临界资源，那么就会造成进程与进程之间的并发。
- 睡眠及与用户空间的同步：在内核执行的进程可能会睡眠，这就会唤醒调度程序，从而导致调度一个新的用户进程执行。
- 多处理器的并发：多处理器系统上的进程与进程之间是严格意义上的并发，每个处理器都可以独自调度运行一个进程，在同一时刻有多个进程在同时运行 。
三、内核同步方法
原子操作
原子操作不可分割，不可中断，不会出现资源竞争现象，也就可以实现同步。
锁机制
为了保证数据的一致性，在多线程编程中会用到锁，使得在某一时间点，只有一个线程进入临界区代码。就像是上厕所，一次只能有一个人进入，然后其他人进行等待，关闭厕所门上锁，其他人则无法进入。所谓的锁，本质上只是内存中的一个整形数，不同的数值表示不同的状态，比如1表示空闲状态和加锁状态。加锁时，判断锁是否空闲，如果空闲，修改为加锁状态，返回成功，如果已经上锁，返回失败，解锁时，就把锁状态修改为空闲状态。
既然提到了锁，那么下面顺便说明一下死锁。
这里首先也简单举个例子，现在有一双筷子，饭桌上有两个人，只有同时拿到两根筷子才可以吃饭，但两人都各拿一根，都在等待对方放下筷子，所以就造成了都无法吃饭。死锁与之类似，下面是比较官方的说法：有一个或多个执行线程和一个或多个资源的条件下，每个线程都在等待其中的一个资源，但所有的资源都已经被占用了，所有线程都在互相等待，但他们永远不会释放已经占有的资源，导致任何线程都无法继续，这便是发生了死锁。
总结一下就是操作系统中经常出现的产生死锁的四个必要条件：互斥、请求与保持、不剥夺、循环等待。（此处不再进行解释)
如何避免死锁
- 按顺序加锁。使用嵌套的锁时必须保证以相同的顺序获取锁。
- 防止发生饥饿。
- 不要重复请求同一个锁。
- 设计简单的加锁方案。
①自旋锁（spin lock）
是指当一个线程在获取锁的时候，如果锁已经被其它线程获取，那么该线程将循环等待，然后不断的判断锁是否能够被成功获取，直到获取到锁才会退出循环。
自旋锁注意事项：
- 自旋锁可以使用在中断处理程序中
（不能使用信号量，会导致睡眠），在中断处理程序中使用自旋锁时，一定要在获取锁之前，首先禁止本地中断（在当前处理器上的中断请求），否则中断处理程序就会打断正持有锁的内核代码，有可能去争用这个已经被持有的自旋锁。从而发生死锁。
- 自旋锁是一种忙等待
Linux中，自旋锁当条件不满足时，会一直不断地循环条件是否被满足。如果满足，就解锁，继续运行下面的代码。这种忙等待机制是否对系统的性能有所影响呢?答案是肯定的。内核这样设计自旋锁确定对系统的性能，有所影响，所以在实际编程中，程序员应该注意自旋锁不应该长时间地持有，它 "是一种适合短时间锁定的轻量级的加锁机制。
- 自旋锁不能递归使用（即已经拿到锁的线程，不应该再等待拿到的那个锁）
这是因为， 自旋锁被设计成在不同线程或者函数之间同步。如果一个线程在已经持有自旋锁时，其处于忙等待状态，则已经没有机会释放自己持有的锁了。如果这时再调用自身，则自旋锁永远没有执行的机会了。
下面是自旋锁内核源码说明，官方这里有个整理的自旋锁头文件和说明：
/*
* include/linux/spinlock.h - generic spinlock/rwlock declarations
*
* here's the role of the various spinlock/rwlock related include files:
*
* on SMP builds:
*
* asm/spinlock_types.h: contains the arch_spinlock_t/arch_rwlock_t and the
* initializers
*
* linux/spinlock_types_raw:
* The raw types and initializers
* linux/spinlock_types.h:
* defines the generic type and initializers
*
* asm/spinlock.h: contains the arch_spin_*()/etc. lowlevel
* implementations, mostly inline assembly code
*
* (also included on UP-debug builds:)
*
* linux/spinlock_api_smp.h:
* contains the prototypes for the _spin_*() APIs.
*
* linux/spinlock.h: builds the final spin_*() APIs.
*
* on UP builds:
*
* linux/spinlock_type_up.h:
* contains the generic, simplified UP spinlock type.
* (which is an empty structure on non-debug builds)
*
* linux/spinlock_types_raw:
* The raw RT types and initializers
* linux/spinlock_types.h:
* defines the generic type and initializers
*
* linux/spinlock_up.h:
* contains the arch_spin_*()/etc. version of UP
* builds. (which are NOPs on non-debug, non-preempt
* builds)
*
* (included on UP-non-debug builds:)
*
* linux/spinlock_api_up.h:
* builds the _spin_*() APIs.
*
* linux/spinlock.h: builds the final spin_*() APIs.
*/
以下源码使用介绍只对通用形式进行介绍，且只进行表层调用介绍，底层详细介绍推荐看linux内核源码分析-同步原语-自旋锁spinlock
声明一个自旋锁结构体
/* Non PREEMPT_RT kernels map spinlock to raw_spinlock */
typedef struct spinlock {
union {
struct raw_spinlock rlock;
// 此处省略调试结构体
};
} spinlock_t;
spin_lock_init 自旋锁初始化
spinlock_check检查_lock，__SPIN_LOCK_UNLOCKED将锁设置为释放状态。
# define spin_lock_init(_lock) \
do { \
spinlock_check(_lock); \
*(_lock) = __SPIN_LOCK_UNLOCKED(_lock); \
} while (0)
spin_lock上锁
获得自旋锁，无法获得时自旋等待
static __always_inline void spin_lock(spinlock_t *lock)
{
raw_spin_lock(&lock->rlock);
}
进程中用来禁止抢断和禁止软中断（关下半部）
static __always_inline void spin_lock_bh(spinlock_t *lock)
{
raw_spin_lock_bh(&lock->rlock);
}
尝试上锁，能上锁返回true否则返回false，不自旋。
static __always_inline int spin_trylock(spinlock_t *lock)
{
return raw_spin_trylock(&lock->rlock);
}
既禁止本地中断，又禁止内核抢占（关中断）
static __always_inline void spin_lock_irq(spinlock_t *lock)
{
raw_spin_lock_irq(&lock->rlock);
}
关中断并保存状态字
#define spin_lock_irqsave(lock, flags) \
do { \
raw_spin_lock_irqsave(spinlock_check(lock), flags); \
} while (0)
spin_lock解锁
这是上面几种上锁函数相对应的解锁函数。
释放自旋锁
static __always_inline void spin_unlock(spinlock_t *lock)
{
raw_spin_unlock(&lock->rlock);
}
开下半部
static __always_inline void spin_unlock_bh(spinlock_t *lock)
{
raw_spin_unlock_bh(&lock->rlock);
}
开中断
static __always_inline void spin_unlock_irq(spinlock_t *lock)
{
raw_spin_unlock_irq(&lock->rlock);
}
开中断并恢复状态字
static __always_inline void spin_unlock_irqrestore(spinlock_t *lock, unsigned long flags)
{
raw_spin_unlock_irqrestore(&lock->rlock, flags);
}
②信号量
Linux中的信号量是一种睡眠锁。如果有一个任务试图获得一个不可用（已经被占用）的信号量时，信号量会将其推进一个等待队列，然后让其睡眠。这时处理器能重获*，从而去执行其他代码。当持有的信号量可用（被释放）后，处于等待队列中的那个任务将被唤醒，并获得该信号量。
这里再举一个小例子，到银行取钱，一次只能有一个人到窗口进行取钱，其他人可以坐着去打盹。当前面一个人取完了，那么大厅进行叫号，让下一个人去取钱。
信号量注意事项：
-
信号量适用于锁会被长时间持有的情况。
-
信号量不会禁止内核抢占，不会对调度的等待时间带来负面影响。
-
计数信号量可以同时允许任意数量的锁持有者，而自旋锁同一时刻最多允许一个任务持有它（互斥信号量一次也为一个）。
信号量的定义在该文件中：
include/linux/semaphore.h
创建一个信号量
struct semaphore {
raw_spinlock_t lock;
unsigned int count;
struct list_head wait_list;
};
创建一个互斥信号量
#define DEFINE_SEMAPHORE(name) \
struct semaphore name = __SEMAPHORE_INITIALIZER(name, 1)
信号量初始化
static inline void sema_init(struct semaphore *sem, int val)
{
static struct lock_class_key __key;
*sem = (struct semaphore) __SEMAPHORE_INITIALIZER(*sem, val);
lockdep_init_map(&sem->lock.dep_map, "semaphore->lock", &__key, 0);
}
获取指定信号量，若不可用将其睡眠
extern int __must_check down_interruptible(struct semaphore *sem);
试图获取指定信号量，若信号量被争用，立刻返回非0值，否则返回0并持有信号量锁
extern int __must_check down_trylock(struct semaphore *sem);
释放指定信号量，若睡眠队列不空，则唤醒其中一个任务
extern void up(struct semaphore *sem);
③互斥锁
互斥锁是一种简单的加锁的方法来控制对共享资源的访问，互斥锁只有两种状态,即上锁( lock )和解锁( unlock )。互斥锁与互斥信号量的行为类似，但是其操作接口更简单，实现更高效，使用限制更强。
互斥锁注意事项：
- 任何时刻只有一个任务可以持有mutex
- 给mutex上锁者负责给其解锁，必须在同一上下文中上锁和解锁
- 不能递归上锁和解锁
- 当持有一个mutex时，进程不允许退出
- 不能在中断或者下半部中使用
- 只能通过官方API管理，不可拷贝、手动初始化或重复初始化
互斥锁的定义在该文件中：
include/linux/mutex.h
互斥锁结构
struct mutex {
atomic_long_t owner;
raw_spinlock_t wait_lock;
// 省略debug内容
};
互斥锁初始化
/**
* mutex_init - initialize the mutex
* @mutex: the mutex to be initialized
*
* Initialize the mutex to unlocked state.
*
* It is not allowed to initialize an already locked mutex.
*/
#define mutex_init(mutex) \
do { \
static struct lock_class_key __key; \
\
__mutex_init((mutex), #mutex, &__key); \
} while (0)
#define __MUTEX_INITIALIZER(lockname) \
{ .owner = ATOMIC_LONG_INIT(0) \
, .wait_lock = __RAW_SPIN_LOCK_UNLOCKED(lockname.wait_lock) \
, .wait_list = LIST_HEAD_INIT(lockname.wait_list) \
__DEBUG_MUTEX_INITIALIZER(lockname) \
__DEP_MAP_MUTEX_INITIALIZER(lockname) }
#define DEFINE_MUTEX(mutexname) \
struct mutex mutexname = __MUTEX_INITIALIZER(mutexname)
extern void __mutex_init(struct mutex *lock, const char *name,
struct lock_class_key *key);
为指定的mutex加锁，如果锁不可用则睡眠
extern void mutex_lock(struct mutex *lock);
为指定的mutex解锁
extern void mutex_unlock(struct mutex *lock);
试图获取指定的mutex，如果成功返回1，否则返回0
extern int mutex_trylock(struct mutex *lock);
判断锁是否被争用，是返回1，否返回0
extern bool mutex_is_locked(struct mutex *lock);
④大内核锁(BKL)
大内核锁从Linux 2.6.39 开始正式彻底踢出内核，未踢出前是在include\linux\smp_lock.h 文件中定义。主要提供了两个函数，lock_kernel可锁定整个内核，unlock_kernel对应解锁。大内核锁的一个特性是它的锁深度会进行计数。这意味着在内核已经被锁定时，仍然可以调用lock_kernel。当然对应的解锁函数unlock_kernel也必须调用同样的次数，以解锁内核，使其它处理器能够进入内核。整个过程简言之就是能够实现递归获得锁。
内核锁本质上也是自旋锁，但是它又不同于自旋锁，不同点在于自旋锁是不可以递归获得锁的（会导致死锁），而大内核锁则可以递归获得锁。大内核锁作用是保护整个内核，而对应自旋锁则用于保护非常特定的某一共享资源。由于一般情况下使用大内核锁的时候保持该锁的时间较长，导致了它严重影响系统的性能和可伸缩性，笔者认为这是它被踢出内核的重要原因之一。BKL是一个全局自旋锁，使用它主要是为了方便实现从Linux最初的SMP过渡到细粒度加锁机制。
BKL注意事项：
- 持有BKL的任务仍然可以睡眠。睡眠不会造成任务死锁。
- BKL是一种递归锁。一个进程可以多次请求一个锁，不会像自旋锁一样产生死锁现象。
- BKL只可以用在进程上下文中。和自旋锁不同，不可以在中断上下文申请BLK。
- 新用户不允许使用BKL。
⑤顺序锁（seq锁）
这种锁提供了一种用于读写共享数据的机制。实现这种锁主要依靠一个序列计数器，当有疑义的数据被写入时，会得到一个锁，并且序列值会增加。在读取数据之前和之后，序列号都被读取。如果读取的序列号值相同，说明在读操作进行的过程中没有被写操作打断过。此外，如果读取的值是偶数，那么就表明写操作没有发生。适用于读者很多，写者很少且写优先与读，数据结构简单。
完成变量
完成变量概念与信号量相似，如果内核中一个任务需要发出信号通知另一个任务发生了某个特定事件，一个任务执行一些工作时，另一个任务就会在完成变量上等待。当这个任务完成工作后，会使用完成变量去唤醒在等待的任务。例如，子进程退出时vfork()系统调用即是使用完成变量唤醒父进程的。
完成变量所在文件
/include/linux/completion.h
动态创建并初始化完成变量
/**
* init_completion - Initialize a dynamically allocated completion
* @x: pointer to completion structure that is to be initialized
*
* This inline function will initialize a dynamically created completion
* structure.
*/
static inline void init_completion(struct completion *x)
{
x->done = 0;
init_swait_queue_head(&x->wait);
}
等待指定的完成变量接收信号
extern void wait_for_completion(struct completion *);
当发生特定事件后，产生事件的任务调用complete()来发送信号唤醒正在等待的任务
extern void complete(struct completion *);
完成变量的通常用法是，将完成变量作为数据结构中的一项动态创建，而完成数据结构初始化工作的内核代码将调用wait_for_completion()等待。初始化完成后，初始化函数调用completion()唤醒在等待的内核任务。
禁止抢占
个人理解禁止抢占和原语的意义相同，通过限制内核抢占机制达到内核同步的过程。
可以通过preempt_disable()禁止内核抢占。这是一个可以嵌套调用的函数，可以调用任意次。每次调用都必须有一个相应的preempt_enable()调用。当最后一次preempt_enable()被调用后，内核抢占才重新启用。
| 函数 | 描述 |
|---|---|
| preempt_disable() | 增加抢占计数值从而禁止内核抢占 |
| preempt_enable() | 减少抢占计数，并当该值降为0时检查和执行被挂起的需调度的任务 |
| preempt_enable_no_resched() | 激活内核抢占但不再检查任何被挂起的需调度任务 |
| preempt_count() | 返回抢占计数 |
屏障
当处理多处理器之间或硬件设备之间的同步问题时，有时需要在程序代码中以指定的顺序发出读内存和写内存指令。在和硬件交互时，时常需要确保一个给定的读操作发生在其他读或写操作之前。另外，在多处理器上，可能需要按写数据的顺序读数据。但是编译器和处理器为了提高效率，可能对读和写重新排序，这样无疑使问题复杂化了，幸好，所有可能重新排序和写的处理器提供了机器指令来确保顺序要求。同样也可以指示编译器不要对给定点周围的指令序列进行重新排序。这些确保顺序的指令称作屏障。
| 屏障 | 描述 |
|---|---|
| rmb() | 阻止跨越屏障的载入动作发生重排序 |
| read_barrier_depends() | 阻止跨越屏障的具有数据依赖关系的载入动作重排序 |
| wmb() | 阻止跨越屏障的存储动作发生重排序 |
| mb() | 阻止跨越屏障的载入和存储动作发生重排序 |
| smp_rmb() | 在smp上提供rmb()功能，在UP上提供barrier()功能 |
| smp_read_barrier_depends() | 在smp上提供smp_read_barrier_depends()功能，在UP上提供barrier()功能 |
| smp_wmb() | 在smp上提供smp_wmb()功能，在UP上提供barrier()功能 |
| smp_mb() | 在smp上提供smp_mb()功能，在UP上提供barrier()功能 |
| barrier() | 阻止编译器跨屏障对载入或存储操作进行优化 |
四、参考资料与补充
参考
《Linux内核设计与实现》