《深入理解Linux内核》--第五章 内核同步：读书笔记

同步：识别出异常处理、中断处理、可延迟函数、内核线程中的临界区，采用适当的保护措施，以确保在任意时刻只有一个内核控制路径处于临界区。
如果是但CPU系统，可以采取访问共享数据结构时关闭中断的方式实现临界区，因为只有在开中断的情况下，才能发生内核控制路径的嵌套。
但是在多处理器系统中，许多CPU可能同时执行内核路径，不能假设只要禁止内核抢占功能，而且中断、异常和软中断处理程序都没有访问过该数据结构，就能保证这个数据结构能够安全地访问。

一、内核抢占
内核抢占:如果进程执行内核函数时（内核态运行），允许发生内核切换。
使用内核抢占的目的：减少用户态进程的分派延迟（dispatch latency），即从进程变为可执行状态到它实际开始运行之间的时间间隔。
二、同步原语
Linux内核有多种内核同步技术：每CPU变量(Per-CPU),原子操作、内存屏障、自旋锁、信号量、顺序锁、本地中断禁止、本地软中断（可延迟函数）禁止、读-拷贝-更新（RCU）
1）Per-CPU（每CPU）变量
总的原则:内核控制路径应该在禁用抢占的情况下访问Per-CPU变量。
2）原子操作
“读 - 修改 - 写”类型：若干汇编语言指令都是这种类型，访问存储器单元两次，第一次读原值，第二次写新值。
存储器仲裁器：对访问RAM芯片的操作进行串行化的硬件电路。
避免由于“读 - 修改 - 写”类型引起竞争的方法:确保这样的操作在芯片级是原子的。避免其他CPU访问同一存储单元。
3）优化和内存屏障
(1)编译器优化，用barrier（）优化屏障 防止
(2)CPU取指优化，用 wmb/rmb等防止
优化屏障（optimization barrier)：barrier()宏， 原语保证编译程序不会混淆 原语之前 的汇编语言指令 和 原语之后 的汇编语言指令。
内存屏障(memory barrier)：保证原语之后 的操作 一定要在 原语之前的操作已经完成后 才执行。Pentium4引入lfence、sfence、mfence等汇编指令，有效的实现 读内存屏障、写内存屏障 和读-写内存屏障。
asm volatile(“lfence”) 等同于
asm volatile("lock; addl $0, 0(%%esp)”::”memory”)
lock使得这条指令成为CPU的一个内存屏障。
4）自旋锁
自旋锁：如果内核控制路径发现锁由运行在另一个CPU的内核控制路径”锁着“，就在当前CPU”旋转“，反复执行一条紧凑的循环指令，直到锁被释放。
一般来说：自旋锁所保护的每个临界区都是禁止内核抢占的。但是分为：具有内核抢占的spin_lock宏；非抢占式内核中的spin_lock宏。
spin_unlock宏: movb $1,slp->slock
5)读/写自旋锁
读/写自旋锁：允许多个内核控制路径 同时 读 同一个数据结构；如果一个内核控制路径想对这个结构进行写操作，那么它必须首先获得 读/写锁的 写锁，写锁 独占访问这个资源。
6)顺序锁(seqlock)
顺序锁(seqlock):读者正在读的时候也允许写者继续运行，读者需要反复多次（读之前一次 读完之后一次 读取一个标志位，每个读者都必须在读数据前后两次读顺序计数器[seqlock_t中sequence字段],写者通过write_seqlock(){是sequence加1}和write_sequnlock()获取和释放锁）相同的数据直到它获得有效的副本。类似 读/写自旋锁， 为 写者 赋予了较高的优先级。
7）RCU（读-拷贝-更新）
RCU（读-拷贝-更新）:保护被多个CPU 读 的数据结构而设计的同步技术。写者更新数据结构时，它间接引用指针并生成整个数据结构的副本；写者修改这个副本；一旦修改完，写者改变指向数据结构的指针（需要使用内存屏障 来保证，只有数据结构被修改后，已更新的指针对其他CPU才是可见的。其中内存屏障一种方法：自旋锁和RCU结合 禁止写者的并发执行），写者必须在读者执行完rcu_read_unlock()之后，才可以释放旧副本。
a)RCU只保护被动态分配并通过指针引用的数据结构；b)在被RCU保护的临界区中，任何内核控制路径都不能睡眠。
静止状态（quiescent state),CPU经历以下一种状态即为静止状态：
a）CPU执行进程切换
b）CPU开始在用户态执行
c）CPU执行空循环
写者调用call_rcu()释放旧副本.当所有CPU都通过quiescent state之后，call_rcu()接受rcu_head描述符的地址和将要调用的回调函数的地址作为参数。回调函数执行，写者释放数据结构的旧副本。
内核没经过一个时钟滴答，就周期性检查本地CPU是否进经过了一个quiescent state。
8）信号量
9）读/写信号量
10)补充原语
11)禁止本地中断
12）禁止和激活可延迟函数
三、避免竞争条件
1）引用计数器
2）大内核锁
每个进程描述符都含有lock_depth字段，允许同一个进程几次获取大内核锁。