同步语义

只要有共享资源的地方，编写代码时就需要特别注意，防止并发访问时造成数据不一致的问题。多个线程并发访问共享数据是造成系统不稳定的一类隐患，而这类隐患往往难以跟踪和调试。

内核中并发执行的原因有：

• 中断：中断是异步的，几乎可以在任何时刻发生，打断当前正在执行的代码。
• 抢占：正在执行的任务可能会被其他任务抢占。
• 睡眠：进程在等待某个事件的过程中会睡眠，这会唤醒内核的调度程序，让另一个进程投入运行。
• SMP：多核处理器可以同时执行同一段代码。

同步概念

临界区

所谓临界区就是访问和操作共享资源的代码。多个线程同时访问临界区是不安全的，因此临界区必须加以保护。考虑一个非常简单的情况。假设我们有一个全局变量i，操作仅仅是对其加1。

i++;

一条简单的自增操作在CPU执行的时候却需要三条汇编指令：

1. 从内存中读出变量i的值并放在一个寄存器内。
2. 将寄存器中的值+1。
3. 把i的值写回到内存。

实际上，在多线程并发的情况下，其他线程有可能在这三条指令间隙的任意时刻“插队”。这种概率虽然很小，但是计算机每秒运行上百万条指令，“插队”可能每过几秒就发生一次。假设有两个线程按照我们期望的那样，依次操作这个全局变量，若i的初始值为1，那么最终结果应该是3。但是假如第二个线程在第一个线程执行到最后一步之前——也就是i的值还没有回写，就去内存中读取了i的值（此时i的值仍然为1），我们最后得到的i的值就是2而不是3，这与我们预期的结果不符。

多线程访问共享资源

#include <stdio.h>
#include <pthread.h>

int i = 0;

void *thread_func(void *arg)
{
    for(int j = 0 ;j < 1000000; j++)
    {
        i++;
    }

}

int main(int argc, char *argv[])
{

    pthread_t tid1, tid2;
    pthread_create(&tid1, NULL, thread_func, NULL);
    pthread_create(&tid2, NULL, thread_func, NULL);

    pthread_join(tid1, NULL);
    pthread_join(tid2, NULL);

    printf("i = %d\n", i);
    return 0;
}

以上是一段示例代码，在编译时请加上-lpthread，以链接正确的库。多次执行该程序后你会发现最终的结果是不确定的。

这是最简单的临界区例子，对于这种简单的竞争条件，我们不需要用到复杂的锁机制，因为锁对于CPU的性能有很大的影响。多数处理器都提供了指令来原子地读、写变量。我们称之为原子指令。使用原子指令可以解决一些简单的并发问题。两条原子指令不可能交错执行，因为处理器会从硬件上禁止这种可能性。

加锁

当共享资源是一个复杂的数据结构比如结构体，而不是简单的整型数据时，原子指令就无能为力了。此时我们必须引入锁来保护共享资源。锁有多种形式，锁的粒度也各不相同。Linux内核提供了多种不同的锁机制，它们之间的主要区别在于：当锁被占用时其他等待锁的线程的表现形式——有一些锁会在原地等待，而有一些锁会直接睡眠。锁没有优劣之分，在不同场景下需要用不同的锁。

当一个锁被占用时，若有其他线程试图获得该锁，我们称之为锁的争用。由于锁是让程序以串行的方式对资源进行访问，被长时间持有的锁无疑会降低系统的性能。于是锁的粒度就显得尤为重要。

Info

锁的粒度是指加锁的范围。锁的粒度越小，并发性能越好，但是加锁的次数也越多。锁的粒度越大，加锁的次数越少，但是并发性能越差。

死锁

死锁是编写同步代码时经常会遇到的问题，表现在多个线程因为争夺资源而卡死。如果没有外部因素介入，这些线程将永远处于等待状态。

一个最简单的例子就是自死锁：如果一个线程试图去获得一个自己已经持有的锁，那么它将永远等待下去。

另一个常见的例子叫ABBA死锁：线程1持有锁A，线程2持有锁B，线程1试图去获得锁B，而线程2试图去获得锁A。由于每个线程都在等待另一个线程释放锁，但是谁都不想释放自己的锁，于是就造成了死锁。预防死锁的发生非常重要，虽然你不知道自己的代码会不会发生死锁，但是遵循一些简单的规则对于避免死锁大有帮助：

• 按顺序加锁。使用多个锁时必须保证以相同的顺序获取锁，否则就有可能造成 ABBA 死锁。
• 防止饥饿。
• 不要重复请求同一个锁。
• 代码设计越简洁越好。

原子操作

原子操作从硬件上(由体系结构实现)保证指令以不可分割的形式执行——执行过程不可被打断。内核提供了两组原子操作接口——一组针对整数，一组针对位。在Linux支持的所有体系结构上都实现了这两组接口。ARM使用 LDREX 和 STREX 指令。

有的时候我们会要求某些指令按照特定的顺序执行，这被称为顺序性，以屏障（barrier）指令来实现。

原子整数操作

针对整数的原子操作使用一个特殊的atomic_t类型的数据，定义在<linux/types.h>中：

typedef struct{
    int counter;
}atomic_t;

使用原子整数操作的声明在<asm/atomic.h>中定义：

• 设置原子变量的值：

void atomic_set(atomic *v, int i);
atomic_t v = ATOMIC_INIT(0);

• 获取原子变量的值

atomic_read(atomic_t *v);

• 原子加减

void atomic_add(int i, atomic_t *v);
void atomic_sub(int i, atomic_t *v);

• 原子自增/自减

void atomic_inc(atomic_t *v);
void atomic_dec(atomic_t *v);

• 操作并测试

int atomic_inc_and_test(atomic_t *v);
int atomic_dec_and_test(atomic_t *v);
int atomic_sub_and_test(int i, atomic_t *v);

• 操作并返回

int atomic_add_return(int i, atomic_t *v);
int atomic_sub_return(int i, atomic_t *v);
int atomic_inc_return(atomic_t *v);
int atomic_dec_return(atomic_t *v);

原子操作通常是内联函数，且是用内嵌汇编指令来实现的。gcc内嵌汇编代码请参考：ARM GCC Inline Assembler。

atomic64_t类型是64位的原子变量，其功能和32位一致，区别是接口以atomic64前缀命名。

typedef struct {
    volatile long counter;
}atomic64_t;

原子位操作

atomic_t类型对整数算术来讲比较有用。但是当需要以原子形式来操作单个的位时，这种类型就无法派上用场了。Linux内核提供了对位的原子操作。

原子位的操作非常快，只要硬件底层硬件支持，这种操作可以使用单个机器指令来执行。这些函数与体系结构相关，定义在<asm/bitops.h>中。即使是在 SMP 计算机上，这些函数依旧可以确保是原子的。原子位的参数是一个位号+指针。

• 设置位

void set_bit(int nr, void *addr);

• 清除位

void clear_bit(int nr, void *addr);

Note

所谓设置位，就是将addr指向的内存地址中的第nr位设置为1。

所谓清除位，就是将addr指向的内存地址中的第nr位设置为0。

• 切换位

void change_bit(int nr, void *addr);

• 测试位：

test_bit(int nr, void *addr);

• 测试并操作位：

int test_and_set_bit(int nr, void *addr);
int test_and_clear_bit(int nr, void *addr);
int test_and_change_bit(int nr, void *addr);

上述操作等同于执行test_bit()后再执行xxx_bit()。

自旋锁

原子操作只能针对一些简单的场景，复杂的场景必须得用锁。

Linux内核中最常见的锁是自旋锁（spinlock）。自旋锁只能同时被一个线程持有，如果另一个线程试图获得一个已经被占用的自旋锁，那么该线程将会进入忙等待，直到锁可用。如果临界区代码执行得比较快，那么就适合用自旋锁。

总结自旋锁的特点是：

1. 当发生资源冲突时，原地死等直到获取锁。
2. 同一时间只允许一个线程访问。
3. 执行时间短。
4. 由于不会睡眠，因此可以在中断上下文中使用。

场景分析

自旋锁保护的资源可能来自多个CPU的进程上下文以及中断上下文中的访问。其中进程上下文包括：用户态进程，内核态线程，工作队列中的work function。中断上下文包括：中断handler，软中断，tasklet，定时器的callback。

先来看最简单的未开启内核抢占选项的单CPU进程上下文。该场景下，所有的系统调用按照顺序执行，在内核态也不会发生进程调度。因此，共享资源根本就不需要保护，因为没有并发场景。

当打开了内核抢占选项之后，事件变得略微复杂：

• 进程A需要访问共享资源R
• 进程B需要访问共享资源R

假设进程A在访问过程中发生了中断，唤醒了优先级更高的进程B。在中断返回现场时，进程从A切换至B运行，B开始访问共享资源R。如果没有锁的保护，就会出现两个进程同时访问共享资源的情况。但是如果我们加上了自旋锁，当A访问时获取了自旋锁，B仍试图获取自旋锁，由于进程A的持有导致了死锁。内核在这种场景下的处理很简单：直接禁止本地CPU上的抢占。如果是在多核场景下，A和B运行在不同的CPU上，虽然A持有了自旋锁导致B进入了等待状态，但是由于运行在不同CPU上，很快A就会释放锁从而让B运行。

如果我们加上了中断上下文的访问，事情将会变得更加复杂：

• 运行在CPU0上的进程A需要访问共享资源R
• 运行在CPU1上的进程B需要访问共享资源R
• 外设P的中断handler也需要访问共享资源R

在这种场景下，假设CPU0上的进程A持有自旋锁进入了临界区。这时候外设P发生了中断，并且调度到了CPU1上执行，由于CPU0上的进程A持有锁，它会稍等一会直到进程A释放。但是如果是调度到CPU0上执行，就会发生死锁。为了解决这样的问题，在涉及到中断上下文的访问时，使用自旋锁的同时需要禁止本地CPU上的中断。

当然，如果外设P延后到了中断下半部之后去执行，直接禁止本地中断就显得不必要了，因为可能会有其他的中断到来，粗暴地禁止会影响系统的性能。这时我们只需要禁止中断下半部即可。

内核中的spinlock_t定义如下：

typedef struct spinlock{
    struct raw_spinlock rlock;
}spinlock_t;

typedef struct raw_spinlock{
    arch_spinlock_t raw_lock;
}raw_spinlock_t;

为什么会有两个？这是因为内核实时补丁PREEMPT_RT。该补丁试图为linux内核增加硬实时功能，比如高精度定时器就是应用之一。实时内核希望将spinlock分成可以睡眠和不可以睡眠两种。于是，最终的命名规则是：

1. spinlock，在配置了PREEMPT_RT时，表示可以睡眠。
2. raw_spinlock，即便是配置了PREEMPT_RT时，也不可以睡眠。
3. arch_spinlock，与架构相关。

对于UP平台，所有的arch_spinlock_t的定义都是一样的：

typedef struct {}arch_spinlock_t;

函数接口

接口API描述	spinlock	raw_spinlock
定义并初始化	DEFINE_SPINLOCK	DEFINE_RAW_SPINLOCK
动态初始化	spin_lock_init	raw_spin_lock_init
获取锁	spin_lock	raw_spin_lock
尝试获取锁	spin_trylock	raw_spin_trylock
获取锁并禁止本地CPU中断	spin_lock_irq	raw_spin_lock_irq
获取锁并保存当前irq状态，同时禁止本地CPU中断	spin_lock_irqsave	raw_spin_lock_irqsave
获取锁并禁止本地CPU下半部	spin_lock_bh	raw_spin_lock_bh
释放锁	spin_unlock	raw_spin_unlock
释放锁并激活本地CPU中断	spin_unlock_irq	raw_spin_unlock_irq
释放锁并恢复当前irq状态	spin_unlock_irqrestore	raw_spin_unlock_irqrestore
释放锁并激活本地CPU下半部	spin_unlock_bh	raw_spin_unlock_bh
判断锁是否被占用	spin_is_locked	raw_spin_is_locked

Info

使用自旋锁的代码在进入临界区的时候，还会受到中断和下半部的干扰。所以就有了自旋锁的中断衍生版本。在多核编程中，如果进程和中断需要访问同一资源，我们一般需要在进程上下文中调用spin_lock_irqsave()，在中断上下文中调用spin_lock()。

读/写自旋锁

有时，对共享资源的访问可以明确地分为读和写两个场景，尤其是那些需要大量读操作，而写操作很少的情况时，引入读写锁可以很大地改善系统的性能。读写锁的基本逻辑是：读模式是共享的，写模式是独占的。也就是说当进行写操作的时候，只能由单个任务进行。而进行读操作的时候，可以同时进行多个任务。

读写锁在文件系统中被大量应用，因为许多操作只是简单地读取文件数据，而不会涉及到更新。

凡事皆有利弊，读写锁虽然在有大量读操作的场景下会带来显著的性能提升，但是其锁的逻辑复杂度也会增加，并且会造成写者饥饿现象。

场景分析

加锁逻辑：

• 临界区没有任何线程，此时读者或者写者都允许进入，但不能同时进入。
• 临界区有一个读者，此时新来的读者可以任意进入，但是不允许写者进入。
• 临界区有一个写者，此时任何读者或者写者都不允许进入。
• 临界区有多个读者，此时后续的读者可以任意进入，但是写者不能进入，这就是写者饥饿现象。

解锁逻辑：

• 一个写者离开临界区，此时所有读者和写者都可以竞争进入临界区。
• 一个读者离开临界区，如果临界区仍然有读者，那么写者还是需要等待，直到所有的读者离开临界区。

函数接口

接口API描述	rw_spinlock
定义并初始化	DEFINE_RW_SPINLOCK
动态初始化	rwlock_init
获取锁	read_lock write_lock
获取锁并禁止本地CPU中断	read_lock_irq write_lock_irq
获取锁并保存当前irq状态，同时禁止本地CPU中断	read_lock_irqsave write_lock_irqsave
获取锁并禁止本地CPU下半部	read_lock_bh write_lock_bh
释放锁	read_unlock write_unlock
释放锁并恢复当前irq状态	read_unlock_irq write_unlock_irq
释放锁并恢复本地CPU状态	read_unlock_irqrestore write_unlock_irqrestore
释放锁并激活本地CPU下半部	read_unlock_bh write_unlock_bh
尝试获取锁	read_trylock write_trylock

顺序锁

读/写自旋锁给读者赋予了更高的权限，容易造成写者饥饿的现象。而顺序锁对读写的优先级进行了调整，让写者的优先级始终高于读者。

顺序锁的特点：

• 读者并发执行，写者互斥
• 临界区只有读者时，写者可以进入
• 临界区有写者时，读者不能进入

场景分析

读者加锁：

1. 临界区没有读者时，获取锁
2. sequence counter++

读者解锁：

1. 释放锁
2. sequence counter++

由上面的操作可知，当临界区没有读者时，sequence counter为偶数，否则为奇数。

写者操作：

1. 获取sequence counter的值，如果是偶数则可以进入临界区，否则等待
2. 进入临界区后，读取数据
3. 获取sequence counter的值，如果等于原来的值，说明没有写者进入，则表示OK，否则返回至第一步

函数接口

顺序锁的写操作使用与自旋锁相同，读操作模式如下：

do {
    seq = read_seqbegin(&seqlock);
    ...
}while(read_seqretry(&seqlock, seq);

信号量

信号量是一种睡眠锁。相比于自旋锁，它内部维护了一个count值，该count值等同于同一时间能够持有信号量的进程数量。如果这个值是1，那么信号量又被称为互斥信号量。信号量支持两个操作：

1. down():

   • 如果信号量的值大于1，则减去1
   • 如果值等于0，进程进入等待队列睡眠，然后CPU调度其他进程运行

2. up()：

   • 如果等待队列为空，则加1
   • 如果等待队列不为空，从队列中唤醒一个进程

由于信号量会睡眠，因此有以下结论：

• 信号量适用于锁会被长时间占有的场景。
• 信号量只能在进程上下文中使用，因为中断上下文禁止睡眠。
• 多个进程试图获得信号量不会死锁。
• 如果已经占用了信号量，不能再使用自旋锁，因为自旋锁禁止睡眠。

信号量是与体系结构相关的，定义在<asm/semaphore.h>中。

函数接口

接口API描述	semaphore
初始化	sema_init
获取信号量	down down_interruptible
尝试获取信号量	down_trylock
释放信号量	up

对于关心具体数值的生产者/消费者问题，使用信号量比较合适。

互斥锁

在多数情况下，信号量只是作为一个计数为1的允许睡眠的自旋锁存在。为了找到一个更简单且可以睡眠的锁，开发者们引入了互斥锁（mutex）。其行为和计数为1的信号量类似，但是操作的接口更简单，实现也更高效。基本使用方法如下：

接口API描述	mutex
静态初始化互斥锁	DEFINE_MUTEX
动态初始化互斥锁	mutex_init
申请互斥锁	mutex_lock
申请互斥锁，如果该锁被占有则进入轻度睡眠	mutex_lock_interruptible
申请互斥锁，如果该锁被占有则进入中度睡眠	mutex_lock_killable
申请互斥锁，如果该锁被占有，则不等待，进程返回	mutex_trylock
释放互斥锁	mutex_unlock

mutex的简洁与高效源于相比使用信号量更多的受限性：

• 任何时刻只能有一个任务持有mutex。
• 必须由上锁者解锁——这意味着你不能在一个线程上锁，而在另一个线程解锁。
• 递归地上锁和解锁是不被允许的。
• 当持有一个mutex时，进程不能退出。
• mutex不能在中断或者下半部中使用。

锁的使用总结

需求	建议的加锁方式
低开销加锁	优先使用自旋锁
短期加锁	优先使用自旋锁
长期加锁	优先使用互斥锁
中断上下文加锁	使用自旋锁
持有锁需要睡眠	使用互斥锁

完成变量

如果在内核中一个任务需要发送信号通知另一个任务发生了某种特定事件，此时可以用完成变量（completion variable）。当某个任务完成工作后，会使用完成变量去唤醒正在等待的任务。

完成变量由结构体completion表示，定义在<linux/completion.h>中。其创建方法如下：

DECLARE_COMPLETION(comp);

或者使用init_completion()动态创建。需要等待的任务调用wait_for_completion()来等待特定事件。当事件发生后，产生事件的任务调用complete()来发送信号唤醒正在等待的任务。

RCU机制

读取-复制-更新（read-copy-update）是一种高级的保护共享数据结构的机制，特别是用在多核处理器系统中。它允许一个CPU安全地读取数据，而另一个CPU同时更新这些数据。由于在更新数据时不需要用到锁，因此极大地提高了系统的性能。

RCU的主要使用方法如下：

• 在需要修改数据时，写者首先复制一份副本，在副本上修改，最后一次性替换数据。写者完成了数据的修改之后，通过特定的API将更新后的数据指针赋值回原来的位置，这个过程称为“更新完成”。如果存在多个写者，在写者把更新后的“副本”覆盖到原数据时，写者之间需要利用其他同步机制保证同步。

• 多个读者可以同时随意地读写数据，但读取的是原始地址。内存屏障指令用于保证只有在数据结构被修改之后，已更新的指针才对其他CPU可见。读取端的代码必须放置于rcu_read_lock()和rcu_read_unlock()之间。

在RCU的实现过程中，我们主要解决以下问题：

1. 在读取过程中，另外一个线程删除了一个节点。删除线程可以把这个节点从链表中移除，但它不能直接销毁这个节点，必须等到所有的读取线程读取完成以后，才进行销毁操作。RCU中把这个过程称为宽限期（Grace period）。

2. 在读取过程中，另外一个线程插入了一个新节点，而读者读到了这个节点，那么需要保证读到的这个节点是完整的。这里涉及到了发布-订阅机制（Publish-Subscribe Mechanism）。

3. 保证读取链表的完整性。新增或者删除一个节点，不至于导致遍历一个链表从中间断开。但是RCU并不保证一定能读到新增的节点或者不读到要被删除的节点。

对于被RCU保护的共享数据结构，读者不需要获得任何锁就可以访问它，但写者在访问它时首先拷贝一个副本，然后对副本进行修改，最后使用一个回调（callback）机制在适当的时机把指向原来数据的指针重新指向新的被修改的数据。那么这个“适当的时机”是怎么确定的呢？这是由内核确定的。

使用RCU技术的难点在于：写入端修改指针时不能立刻释放数据结构的旧指针，因为还有其他的读取端在使用。只有当所有的读取端执行完宏rcu_read_unlcok()之后，才可以释放旧指针。写入端调用函数call_rcu()来释放旧指针。

禁止抢占

Linux是抢占式内核，其主要特点是：一个在内核态运行的进程，可能在执行内核态函数期间被另外一个进程抢占。在进程A执行异常处理程序时（此时位于内核态），一个更有优先级的进程B变为可执行状态。如果内核是可抢占的，就会发生强制性任务切换，让B取代A。再比如，一个进程已经用完了它的时间片配额，抢占式内核会立刻让另一个进程取代它。

内核使用thread_info中的preempt_count字段表示抢占计数。当这个值大于0时，就禁止内核抢占。它在以下任何一种情况发生时，取值都大于0：

1. 内核正在执行中断服务程序。

2. 可延迟函数被禁止（当内核正在执行软中断或tasklet）。

3. 显示设置抢占计数器为正数。

宏	说明
preempt_count()	返回抢占计数值
preempt_disable()	使抢占计数+1
preempt_enable()	使抢占计数-1，并检查TIF_NEED_RESCHED标志
preempt_enable_no_resched()	使抢占计数-1

Note

preempt_enable()宏首先递减抢占计数器，并且检查TIF_NEED_RESCHED标志是否被设置。当这个标志为1时表示需要执行调度程序。于是我们还会调用preempt_schedule()来调用schedule()选择另外一个进程运行。

内存屏障

为什么需要内存屏障指令？

• 防止编译器优化导致的重排：现代编译器会进行各种优化以提高程序的执行效率，包括指令重排。在不考虑内存操作顺序的情况下，编译器可能会改变指令的执行顺序，这可能导致程序的行为与预期不符。通过使用内存屏障指令，可以限制编译器对某些关键代码段的优化。

• 保证并发操作的一致性：在多核处理器和多线程编程中，为了提高性能，操作系统的调度器可能会在不同的处理器核心上并行执行多个线程。为了保持一致性，需要确保所有核心上的内存操作都按照程序指定的顺序执行。

• 解决CPU缓存一致性问题：CPU缓存是处理器速度的关键部分，但它的存在也带来了缓存一致性的问题。当一个CPU核心写入数据，而这个数据又被另一个核心的缓存所缓存时，没有屏障指令的话，另一个核心可能会读取到旧的数据版本。内存屏障能够确保所有核心看到内存操作的最终一致性。

Linux中的内存屏障指令：

宏	说明
barrier()	优化屏障
mb()	适用于SMP和UP的内存屏障
rmb()	适用于SMP和UP的读内存屏障
wmb()	适用于SMP和UP的写内存屏障
smp_mb()	仅适用于SMP的内存屏障
smp_rmb()	仅适用于SMP的读内存屏障
smp_wmb()	仅适用于SMP的写内存屏障

此类指令与体系结构密切相关，请参考ARM内存屏障指令。

Per-CPU变量

Per-CPU是基于空间换时间的方法，让每个CPU都有自己的私有数据段(放在L1中)，并将一些变量私有化到 每个CPU的私有数据段中。单个CPU在访问自己的私有数据段时，不需要考虑其他CPU之间的竞争问题，也不存在同步的问题。