Linux内核同步

内核抢占

抢占内核的主要特点是: 一个在内核态运行的进程，可能在执行内核函数期间被另外一个进程取代。

用实例来说明抢占内核和非抢占内核的区别:

在进程A执行异常处理程序时，一个具有较高优先级的进程B变为可执行状态。这种情况是有可能出现的，例如，发生了中断请求而且相应的处理程序唤醒了进程B。如果内核是抢占的，就会发生强制性进程切换，让进程B取代进程A。异常处理程序的执行被暂停，直到调度程序再次选择进程A时才恢复它的执行。相反，如果内核是非抢占的，在进程A完成异常处理程序的执行之前，是不会发生进程切换的，除非进程A自动放弃CPU。

一个执行异常处理程序的进程已经用完了它的时间配额，如果内核是抢占的，进程可能会立即被取代，但如果内核是非抢占的，进程继续运行直到它执行完异常处理程序或自动放弃CPU。

使内核可抢占的目的是减少用户态进程的分派延迟(dispatch letency)，即从进程变为可执行状态到它实际开始运行之间的时间间隔。

只有当内核正在执行异常处理程序(尤其是系统调用)，而且内核抢占没有显式地禁用时，才可能抢占内核。

同步原语

技术	说明	适用范围
每CPU变量	在CPU之间复制数据结构	所有CPU
原子操作	对一个计数器原子地"读-修改-写"的指令	所有CPU
内存屏障	避免指令重新排序	本地CPU或所有CPU
自旋锁	加锁时忙等	所有CPU
信号量	加锁时阻塞等待(睡眠)	所有CPU
顺序锁	基于访问计数器的锁	所有CPU
本地中断的禁止	禁止单个CPU上的中断处理	本地CPU
本地软中断的禁止	禁止单个CPU上的可延迟函数处理	本地CPU
读-拷贝-更新(RCU)	通过指正而不是锁来访问共享数据结构	所有CPU

每CPU变量

最简单也是最重要的同步技术包括把内核变量声明为每CPU变量(per-cpu variable)。每CPU变量主要是数据结构的数组变量主要是技术结构的数组，系统的每个CPU对应数组的一个元素。

虽然每CPU变量为来自不同CPU的并发访问提供保护，但对来自异步函数(中断处理程序和可延迟函数)的访问不提供保护，在这种情况下需要另外的同步原语。

此外，在单处理器和多处理器系统中，内核抢占都可能是每CPU变量产生竞争条件。总的原则是内核控制路径应该在禁用抢占的情况下访问每CPU变量。

原子操作

通过原子操作指令完成。

80x86 指令:

• 进行零次或一次对齐内存访问的汇编指令是原子的。
• 如果在读操作之后，写操作之前没有其他处理器占用内存总线，那么从内存中读取数据，更新数组并把更新后数组写回内存中的这些"读-修改-写"汇编语言指令(例如inc或dec)是原子的。当然，在单处理器系统中，永远都不会发生内存总线窃用的情况。
• 操作吗前缀是 lock 字节(0xf0)的"读-修改-写"汇编语言指令即使在多处理器系统中也是原子的。当控制单元检测到这个前缀时，就"锁定"内存总线，知道这条指令执行完成为止。因此，当加锁的指令执行时，其他处理器不能访问这个内存单元。
• 操作码前缀是一个rep字节(0xf2,0xf3)的汇编语言执行不是原子的，这条指令强行让控制单元多次重复执行相同的指令。控制单元在执行新的循环之前要检查挂起的中断。

Linux 内核提供了一个专门的 atomic_t 类型(一个原子访问计数器)和一些专门的函数和宏，这些函数和宏作用于 atomic_t 类型的变量，并当作单独的、原子的汇编语言指令来使用。在多处理器系统中，每条这样的指令都有一个 lock 字节的前缀。

另一类原子函数操作作用于位掩码

优化和内存屏障

当使用优化的编译器时，编译器可能重新安排汇编语言指令已使寄存器以最优的方式使用。此外，现代CPU通常并行地执行若干条指令，且可能重新安排内存访问。然而，当处理同步时，必须避免指令重新排序。

优化屏障(optimization barrier) 原语保证编译程序不会混淆放在原语操作之前的汇编语言指令和放在原语操作之后的汇编语言指令，这些汇编语言指令在C中都有对应的语句。在Linux中，优化屏障就是 barrier() 宏，它展开 asm volatile("":::"memory") 。指令 asm 告诉编译程序要插入汇编语言片段(这种情况下为空)。volatile 关键字禁止编译器把asm指令与程序中的其他指令重新组合。memory 关键字强制编译器假定RAM中的所有内存单元已经被汇编语言指令修改。

内存屏障(memory barrier)原语确保，在原语之后的操作开始执行之前，原语之前的操作已经完成。因此，内存屏障类似于防火墙，让任何汇编语言指令都不能通过。

自旋锁

自旋锁(spin lock)是用来在多处理器环境中工作的一种特殊的锁。如果内核控制路径发现自旋锁"开着"，就获取锁并继续自己的执行。相反，如果内核控制路径发现锁由运行在另一个CPU上的内核控制路径"锁着"，就在周围"旋转"，反复执行一条紧凑的循环指令，直到锁被释放。

自旋锁的循环指令表示"忙等"。即使等待的内核控制路径无事可做，它也在CPU上保持运行。不过，自旋锁通常非常方便，因为很多内核资源只锁1毫秒的时间片段；所以说，释放CPU和随后有获得CPU都不会消耗多少时间。

一般来说，由自旋锁保护的每个临界区都是禁止内核抢占的。在单处理器系统上，这中锁本身并不起锁的作用，自旋锁原语仅仅是禁止或启用内核抢占。需要注意的是，自旋转忙等期间，内核抢占还是有效的，因此，等待自旋锁释放的进程有可能被更高优先级的进程替代。

读/写自旋锁

读/写自旋锁的引入是为了增加是内核的并发能力。只要没有内核控制路径对数据结构进行修改，读/写自旋锁就允许多个内核控制路径同时读同一数据结构。如果一个内核控制路径想对这个结构进行写操作，那么它必须首先获取读/写锁的写锁，写锁授权独占访问这个资源。当然，允许对数据结构并发读可以提高系统性能。

顺序锁

Linux 2.6 中引入顺序锁(seqlock)，它与读/写自旋锁非常相似，只是它为写者赋予了较高的优先级；事实上，即使在读者正在读的时候，也允许写者继续运行。这种策略的好处是写者永远不会等待(除非另外一个写者正在写)，缺点是有些时候读者不得不反复多次读相同的数据直到它获得有效的副本。

每个读者都必须在读数据前后两次读顺序计数器，并检查零次读到的值是否相同，如果不相同，说明新的写者已经开始写并增加了顺序计数器，因此暗示读者刚读到的数据是无效的。

一般来说，必须在满足下述条件是才能使用顺序锁:

• 被保护的数据结构不包括被写者修改和被读者间接引用的指针。
• 读者的临界代码没有副作用。

读-拷贝-更新(RCU)

读-拷贝-更新(RCU)是为了保护在多数情况下被多个CPU读的数据结构而设计的零一种同步技术。RCU允许多个读者和写者并发执行(相对于只允许一个写者执行的顺序锁有了改进)。而且，RCU是不使用锁的，就是说，它不使用被所有CPU共享的锁或计数器，在这一点上与读/写自旋锁和顺序锁(由于高速缓存行窃用和失效有很高的开销)相比，RCU 具有更大的优势。

RCU 是如何不是用共享数据结构而令人惊讶地实现多个CPU同步呢？其关键的思想包括限制RCU的范围，如下所述:

• RCU 只保护被动态分配并通过指针引用的数据结构。
• 在被 RCU 保护的临界区中，任何内核控制路径都不能睡眠。

当内核控制路径要读取 RCU 保护的数据结构时，执行 rcu_read_lock()，它等同于 preempt_disable()。接下来，读者间接引用该数据结构指针所对应的内存单元并开始读这个数据结构。正如在前面所强调的，读者在完成对数据结构的读操作之前，是不能睡眠的。用等同于 preempt_enable() 的宏 rcu_read_unlock() 标记临界区的结束。

由于读者几乎不做任何事情来防止竞争条件的出现，所以写者不得不做得更多一些。事实上，当写者要更新数据结构是，它间接引用指针并生成整个数据结构的副本。接下来，写者修改这个副本。一旦修改完毕，写者改变指向数据结构的指针，以使它指向被修改后的副本。由于修改指针值的操作是一个原子操作，所以旧副本和新副本对每个读者或写者都是可见的，在数据结构中不会出现数据崩溃。尽管如此，还需要内存屏障来保证: 只有在数据结构被修改之后，已更新的指针对其他CPU才是可见的，如果把自旋锁与RCU结合起来以禁止写者的并发执行，就隐含地引入了这样的内存屏障。

然而，使用 RCU 技术的真正困难在于: 写者修改指针时不能立即释放数据结构的就副本。实际上，写者开始修改时，正在访问数据结构的读者可能还在读副本。只有在CPU上所有(潜在的)读者都执行完宏 rcu_read_unlock() 之后，才可以释放就副本。内核要求每个潜在的读者在下面的操作之前执行 rcu_read_unlock() 宏:

• CPU 执行进程切换
• CPU 开始在用户态执行
• CPU 执行空循环

对上述每种情况，我们说CPU已经过了静止状态(quiescent state)。

写者调用函数 call_rcu() 来释放数据结构的就副本。当所有的 CPU 都通过静止状态之后，call_rcu() 接受 rcu_head 描述符的地址和将要调用的回调函数的地址作为参数。一旦回调函数被执行，它通常释放数据结构的就副本。

函数 call_rcu() 把回调函数和其参数的地址存放在 rcu_head 描述符中，然后把描述符插入回调函数的每个 CPU (per-CPU) 链表中。内核每经过一个时钟滴答就周期性地检查本地CPU是否进过了一个静止状态。如果所有CPU都经过了静止状态，本地 tasklet (它的描述符存放在每CPU变量 rcu_tasklet 中)就执行链表中的所有回调函数。

RCU 是 Linux 2.6 中新加的功能，用在网络层和虚拟文件系统中。

信号量

Linux 提供两种信号量 :

• 内核信号量，由内核控制路径使用。
• System V IPC 信号量，由用户态进程使用。

内核信号量类似于自旋锁，因为当锁关闭着时，它不允许内核控制路径继续进行。然而，当内核控制路径试图获取内核信号量所保护的忙资源时，相应的进程被挂起。只有在资源被释放时，进程才再次变为可运行的。因此，只有可以睡眠的函数才能获取内核信号量；中断处理程序和可延迟函数都不能使用内核信号量。

内核信号量是 struct semaphore 类型的对象，包含下面这些字段:

• count: 存放 atomic_t 类型的一个值。如果该值大于 0，那么资源就是空闲的，也就是说，该资源现在可以使用。相反，如果 count 等于0。那么信号量是忙的，但没有进程等待这个被保护的资源。最后，如果 count 为负数，则资源时不可用的，并至少有一个进程等待资源。
• wait: 存放等待队列链表的地址，当前等待资源的所有睡眠进程都放在这个链表中。当然，如果 count 大于或等于 0，等待队列就为空。
• sleepers: 存放一个标志，表示是否有一些进程在信号量上睡眠。

可以用 init_MUTEX() 和 init_MUTEX_LOCKED() 函数来初始化互斥访问所需的信号量。

当进程希望释放内核信号量锁时，就调用 up() 函数。相反，当进程希望获取内核信号获取内核信号量锁时，就调用 down() 函数。

读/写信号量类似于"读/写自旋锁"，不同的是：在信号量再次变为打开之前，等待进程挂起而不是自旋。

很多内核控制路径为读可以并发地获取读/写信号量。但是，任何写者内核控制路径必须有被保护资源的互斥访问。因此，只有在没有内核控制路径为读访问或写访问持有信号量时，才可以为写获取信号量。读/写信号量可以提供内核中的并发度，并改善了这个系统的性能。

内核以严格的FIFO顺序处理等待读/写信号量的所有进程。如果读者或写者进程发现信号量关闭，这些进程就被插入到信号量等待队列链表的末尾。当信号量被释放时，就检查处于等待队列链表第一个位置的进程。第一个进程常被唤醒。如果是一个写者进程，等待队列上其他的进程就继续睡眠。如果是一个读者进程，那么紧跟第一个进程的其他所有读者进程也被唤醒并获得锁。不过，在写者进程之后排队的读者进程继续睡眠。

每个读/写信号量都是由 rw_semaphore 结构描述的，它包含下列字段:

• count: 存放两个16位计数器。其中最高16位计数器以二进制补码形式存放非等待写者进程的总数(0或1)和等待的写内核控制路径数。最低16位计数器存放非等待的读者和写者的总数。
• wait_list: 指向等待进程的链表。链表中的每个元素多是一个 rwsem_waiter 结构，该结构包含一个指针和一个标志，指针指向睡眠进程的描述符，标志表示进程是为读需要信号量还是为需要信号量。
• wait_lock: 一个自旋锁，用户保护等待队列链表和 rw_semphore 结构本身。

down_read() 和 down_write() 函数分别为读或写获取读/写信号量。同样，up_read() 和 up_write() 函数为读或写释放以前获取的读/写信号量。 down_read_trylock() 和 down_write_trylock() 函数分别类似于 down_read() 和 down_write() 函数，但是，在信号量忙的情况下，它们不阻塞进程。最后，函数 downgrade_write() 自动把写锁转换成读锁。