#10 自旋锁内核设计
目标：多个CPU同时执行内核，提高并行度，让CPU线性增长得到线性的性能。
本站是考虑使用已经有的自旋锁来保护数据结构。
##10.1 背景需求
内核交互频繁的应用:
- 交互性应用
- 大量文件IO应用
- 频繁缺页错误应用
不同处理器不同进程，同时执行系统调用（systemcall）。 一种内核，一次执行内核活动的多个线程。 （从原来内核只有一个CPU执行，主从内核，单CPU内核），进化到多个线程提供服务，一个进程内变量交互方便，进程内的互斥比跨进程互斥消耗更多的时间（所以考虑多线程内核）。
锁粒度（granularity） －－ 使用几个自旋锁，每个锁保护多少数据结构。
- 粗粒度（coarse－grained）－－ 少数锁，保护很大一部分。
- 细粒毒（fine－grained） －－ 很多锁，一次保护一个数据结构。
选择哪种锁，要在时间和空间进行权衡。 细粒度自旋锁，需要消耗每个结构体一个字。 粗粒度自旋锁，需要消耗CPU等待时间。 执行简单活动需要多个锁，等待锁的时间太长了。
##10.2 巨型锁 giant lock，少量自旋锁，每个锁保护很多数据结构。(coarse-grained 粗粒度锁 )
简单实现，一把锁保护全部内核数据，防止一个以上进程在内核态执行，类似主从内核，效率比主从内核低，
什么时候需要用这把唯一的锁？ 进入内核的地方（系统调用或陷阱，进程上下文切换或返回用户态）的时候。
进程上下文切换过程：
- 占用锁，
- 保护待运行任务队列，
- 选好要执行的任务，
- 从队列移除，
- 这个任务内核态，继续占有巨型锁
- 这个任务用户态，释放巨型锁
中断问题 中断发生在内核，而当时内核正在修改共享的数据结构，内核被破坏。
关键点：
- 任何时刻在任何处理器上发生。
- 每个进程可能收到时钟中断，IO中断。
- 多CPU主机，spl（屏蔽中断优先级的方式）只能屏蔽当前CPU，其他CPU仍然可以接受处理中断。
设备驱动正在执行（内核态），中断在另一个CPU上执行，发生了竞争。 答： 中断处理也需要获得巨型锁，需要进入内核处理。
在一个处理器，正在执行内核处理A，突然来了中断B，A被切换出去但是没有释放内核巨型锁，于是中断B拿不到锁自旋死等，发生死锁。必须在占有内核锁的处理器上屏蔽中断，解决死锁。
设备驱动正在执行（内核态），中断B在另一个CPU上执行，中断B要先拿到内核锁，拿不到自旋等待，中断会被延时，这种延时可能是很长时间。 IO设备，延时太长性能下降厉害，使用单独的自旋锁分别保护不同的设备，避免延时。（更细粒度 granularity ）
巨型锁与主从内核区别
相同点：
内核活动限制在一个时刻在一个CPU上发生。
不同：
任何处理器都能执行内核代码。
巨型锁缺点：
主从内核如果进程无法获得内核运行，被放入内核队列，等待运行让出当前CPU资源。 巨型锁，没有等待内核队列，需要使用内核的进程会自旋等待内核的巨型锁，等不到一直自旋，浪费CPU资源。 最糟糕情况，处理器A上占有内核巨型锁（自旋锁）任务1执行完了，本来要释放锁，结果任务2又在处理器A上内核执行，处理器A长期占有锁，其他处理器一直等待。
有条件的锁定一个自旋锁－－－－解决让处理器不死等内核的自旋锁，让他换一个用户态程序去运行，不浪费CPU。（解决最糟糕情况）
//如果锁是空闲的，拿到锁，返回真。
//如果锁已经在用，返回假。
int
cond_lock( volatile lock_t * lock_status )
{
if(test_and_set(lock_status) == 1 )
return false;
else
return true;
} cond_lock（） 判断内核巨型锁是否拿到，拿到锁继续执行，如果没拿到锁执行上下文切换，换另外一个用户态进程执行。－－引出一个问题，如果内核的巨型锁，如果也负责待运行进程队列管理，那么切换任务也无法拿到锁而无法实现。 解决，运行队列的锁和内核锁分开。
小结 一系列的改进只能让巨型锁内核实现主从内核的水平。 思路是提高内核并行度，超越主从内核限制。
##10.3 不需要上锁的多线程
找到内核中无需上锁的部分，就可以放开锁对这部分模块的保护。
例如：
-
9.5.1 系统调用不用锁也能运行。
-
用户进程私有数据。 （注意，书是讨论os系统多进程互斥的角度，至于进程内多线程互斥不是他考虑的问题，所以书中的视角是进程间相互影响，或内核与进程相互影响）
-
每个进程的用户区（user area），包含的数据私有内核数据结构。（当前信号处理器，当前系统调用参数，寄存器保存（系统调用前的值）），这个区是私有的。
-
每个进程的内核栈（kernel stack），用户进程执行系统调用会用到内核栈，也包括C局部变量 （自动变量）和函数参数。
每个进程的进程表项，系统其他进程可能会修改这个进程表项的数据，需要锁。其他进程向你这个进程发送信号，首先会去查询是否有这个进程的发送信号权限，这个数据项只需要读取就行了。
有一种竞争无需加锁，读在写之前，读到旧数据，读在写之后，读到旧数据。上锁对这种竞争毫无印象。 这种场景一直向前走，无所谓读到新旧值，只要读到的是真实存在的值。
只有一个字写的时候是可以忽略锁的。
调试器产生的互斥问题？ 对进程进行调试，进程的内存都会被调试器访问和修改，通常要挂起该进程，防止调试器和被调试进程发生互斥现象。
必须要锁:
-
对一个以上的字进行原子更新
-
读－改－写
##10.4 粗粒度上锁
针对不同子系统分别加锁，增加并行性。
借用一个例子来讲解，不同模块各自独立的锁，任务需要多把锁，可能会产生死锁的问题。 A－B B－A 引发的死锁 文件IO系统和虚拟机内存文件映射，这里面有2个锁分别管理2个子系统，不同的操作可能需要这2把锁， 但是获得锁的顺序可能相反，然后就可能死锁。
解决办法： 一致的定义和一样的上锁顺序。
实现方式（A代表虚拟内存，B代表文件系统）
-
同时获得A系统锁和B系统锁，如果B不用锁，立刻释放B。相当于一个锁保护2个系统，没有更好并行度。不推荐。
-
A－B－A方式，释放一个锁以维护正确的上锁次序，（释放锁A时，A系统必须数据结构完整性），拿到B锁完成后释放，再拿A锁完成未完成事物。（在此执行A的时候，要判断上次做到一半的事情是否被别的进程破坏。如果没有被破坏，那么继续完成A，如果被破坏，那么要恢复？或者压根就保护住A这部分数据结构，但是A的其它部分可以被修改掉。）这种方式需要确保A的一致性的工作。
-
条件加锁技术来避免释放已经拿到的锁。先拿到A处理，条件判断是否能拿到B锁，B空闲那么拿到A和B锁。获得B锁失败，那么释放A变成 A－B－A模式。有可能不需要释放A，是这个变种的优势。
A－B有可能就完成了（B没被占用），条件上锁机制避免死锁，而这种情况没有按照顺序加锁！如果B锁已经被占用了，B－A 这种方式确保了加锁顺序。
系统调用频繁的系统，条件上锁操作成功的机会很小，基本上又变成了 A－B－A问题。
进程不能切换上下文（占用内核模块的自旋锁），但是这个进程占有自旋锁不能休眠，否则会引发死锁，必须先释放掉子系统的自旋锁。但是进程任务还未执行完，锁被拿走，修改到一半，等休眠结束，重新工作的时候要恢复上一半保持一致性。或者压根就释放锁。 实现上，占有锁的次序这个进程的U用户区中，上下文切换代码负责释放正在挂起进程的，重新执行，获得以前占有的锁。
##10.5 细粒度加锁
##10.5.1 短期互斥
目标：提高不同处理器的内核并行程度。 一个读一个写，加不加锁无所谓。 举例分析：
- 每个子系统，分配一个自旋锁。
- 每个文件分配一个自旋锁。
- 每个进程，需要修改的进程表项，保护挂起的位掩码。
- 保护内核数据结构和列表。（分配一个自旋锁保护列表的搜索，删除，添加都是临界区。进程编号PID折返问题，需要遍历进程列表。）
多处理器被某个锁给串行化，避免锁太多节省空间和加锁开销。 做一个事情要处理很多步骤，如果某个关键点上串行，前面就非必要加锁？
multi－reader lock，多读锁。
obfuscate
##10.5.2 长期互斥
长互斥的原因是IO操作长时间互斥，为了节约CPU，让给别的进程用。
长期互斥 sleep／walkup 在单处理时代没问题因为假设内核非抢占 ，但是多CPU进入出现检查开关变量有并发问题，所以需要短互斥保护并发。
参考： （8.5.3 长期加锁代码放在多CPU 或 8.6 ）
- 长期互斥失效 长期互斥依靠短期互斥（内核非前瞻） 长期加锁面临2个问题
- 2个或更多的进程都以为自己获得了锁，都去关门，都在执行。 同时有N个线程进入，都执行了了①和② 。
- 一个进程判断到锁被占用准备自己睡眠，另外一个进程正在释放锁和唤醒，那么睡眠的进程将不被唤醒，直到下一个用完锁释放的人。 A线程做完①还没做②，B线程在③和④并且一起做完了，那么②就陷入无人唤醒的睡眠中。
void lock_object(char * flag_ptr){ while (*flag_ptr) ① sleep(flag_ptr)；② ＊flag_ptr = 1 ; //上锁 }
void unlock_object(char * flag_ptr){ * flag_ptr = 0 ; //解锁 ③ walkup( flag_ptr ); //手工唤醒 ④ }
多核可以进入的代码
void lock_object(char * flag_ptr){
lock( &object_lock_method ) //代码段保护,短期互斥几行代码（参考9.2自旋锁）
while (*flag_ptr)
sleep(flag_ptr)；
＊flag_ptr = 1 ; //上锁
unlock( &object_lock_method );
}
void unlock_object(char * flag_ptr){
lock( &object_lock_method )
* flag_ptr = 0 ; //解锁
walkup( flag_ptr ); //手工唤醒
unlock( &object_lock_method );
}自旋锁函数附
typedef int lock_t; void initlock( volatile lock * lock_status) { *lock_status = 0 ; //初始化锁 }
void lock （ volatile lock * lock_status ) { while (test_and_set(lock_status ) == 1 ) ; //借助test_and_set 原子操作，独一无二的获得锁，如果没获得锁，那那么不停的尝试，直到拿到锁。 ｝
void unlock ( volatile lock * lock_status ) { *lock_status = 0 ; //释放锁 ｝
// voliatile 告诉编译器，addr指向的地址，可能被别的CPU修改。 // 请不要addr放入寄存器和缓存和优化，避免被别人改了。无法试试拿到最新的值。 // 处理器优化，可能将多余的LOAD和store优化称一个操作。 // 多处理器编程声明变量 volatile 良好编程习惯 int test_and_set ( volatile int * addr ) { int old_value; old_value = swap_atomic( addr,1 ); //原子操作 //addr值取出放入寄存器A， //1放入addr中， //寄存器A在把值给old_vlaue if ( old_value == 0 ) return 0 ; //拿到锁返回0 return 1; //未拿到锁返回1 }
为什么加了自旋锁，还需要sleep？因为如果去掉sleep，就完全变成了短互斥，然后短互斥浪费等待进入的CPU时间。
引入自旋锁解决了2个问题后引发了其它问题？
-
拿到自旋锁，再申请长期锁失败后sleep，sleep会和 unlock_object 休眠唤醒之间造成争用。 （unlock_object 时候想要拿到自旋锁，但是拿不到，无法释放).
解决方案： 如果A程序sleep那么需要发生上下文切换，切换程序负责保存自旋锁，到用户U区，然后释放自旋锁（让B 占有长期锁的进程，在unlock函数中，拿到短期自旋锁来释放长期锁），当A被唤醒时，重新获得锁。
-
改造sleep函数，把自旋锁放入参数，避免使用U区。
##10.5.3 带中断处理的互斥
中断会引发2个线程修改一个数据结构被损坏。 中断互斥时间可长可短，硬件设备读取磁盘，但是通常设计考虑平衡性。
驱动程序代码和中断处理程序之间共享数据结构竞争问题。
在单核，临界区屏蔽中断函数spl()来阻止中断函数，但是只能降低本处理器上的中断优先级到最低。 在多核，一个处理器屏蔽中断没用，因为其它处理器上也可以执行中断，发生了2个CPU代表驱动程序和中断程序分别运行在不同处理器上造成了竞争。
解决多核中断问题？ 使用自旋锁保护防止多个CPU修改共享数据结构，在中断处理函数无法阻挡别的CPU的时候;
驱动程序
int s = splhi(); //防止同一个处理器中断屏蔽
lock( &driver_lock ) ; //防止不同处理器修改数据
counter++;
unlock( &driver_lock );
splx(s); //中断处理函数
lock( &driver_lock );
counter++;
unlock( &driver_lock );为什么不是下面这方式？
驱动程序
lock( &driver_lock ) ; //防止不同处理器修改数据
int s = splhi(); //防止同一个处理器中断屏蔽
counter++;
splx(s);
unlock( &driver_lock );中断B函数如果在同一个CPU上发生，会切换掉已经在执行A的任务，让任务A被切换出CPU。 如果A函数先执行的是拿到自旋锁，而这时候中断来了A被切换走了但是未释放自旋锁或释放了自旋锁（但是到时候还要恢复自旋锁），然后执行中断函数B， 然后再切换回去执行A函数。这样A函数很无辜，因为本来是先进入的结果反而后执行恢复自旋锁很麻烦。
##10.5.4 锁的粒度
内核中添加了自旋锁，任何处理器都可以内核态来执行进程。 锁的粒度： 它不能比操作许可的语意更细。 例如： 锁文件子系统，还是锁一个文件，锁文件读，锁文件写，这些都是符合操作的，如果锁一个文件数据块或者锁一个文件数据行，因为锁的粒度太细了过头了。
不同的锁粒度实现比较方式：
- 保持外部编程模型，上层接口是否需要改动？
- 操作系统的完整性
- 性能上的差别
锁粒度的思考？ 处理器个数 应用个数
例如，每个进程表项一个自旋锁确保进程信号修改互斥，所有的进程表项共用一个自旋锁， 临界区太小，2～3个处理器不太可能同时执行，一个锁效率更佳高。 处理器增加以后，信号量使用的频繁程度增加，单个全局自旋锁争用加剧，情况变的不合适，每个进程独立锁变的更好。 独立锁的好处，增加锁的空间，降低锁的争用。当代2015年，锁空间的占用根本不是事情。93年的时候内存消耗可能会考虑。
目标：让多线程内核有潜力比主从内核以及巨型锁内核实现更佳的性能。
##10.5.5 锁的性能
2种极端场景：
1. 受限计算的进程数。（需要大量进程并行计算，本身不会争用）
2. 受限系统调用的进程。 （需要IO，网络传输，频繁和内核交互。）
多线程内核对第一类，没好处也没坏处。 system－call－intensive 系统调用敏感性应用，各自数据结构上独立的锁保护，最好的情况各自在不同cpu上使用不发生锁争用，负载可以随CPU增加而性能增加。 进程间总会遇到一些争用，不同文件上分别加锁，但是保存在相同驱动器上，争用共享的资源（磁盘本身），也会限制多线程进程内核性能。 为了获得最大性能，需要根据应用特点来调优。
##10.5.6 内核抢占 单处理器，内核不让抢断。 多处理器，一个进程没有占有自旋锁，没有屏蔽中断，代表没有在临界区中运行，可以被抢占。假如这个进程是内核进程，那么被抢占了。 抢占内核的好处：可以给运行优先级更高的进程降低执行延迟。 注意： 被抢占进程之前正在占有长期锁，没有释放长期锁，仍然在保护互斥。
##10.6 休眠唤醒对多CPU的影响
wakeup函数，一次唤醒这个事件上的所有函数，进程颠簸。
进程颠簸（ thundering herd 群用纷争 惊群 ）
步骤：
1. 进入lock函数，先拿到短期互斥锁。
2. 再拿到长期锁
2.1 拿到长期锁以后，放弃短期互斥锁，退出拿锁函数，执行长期任务。
2.2 没拿到长期锁，sleep，放弃短期锁
3. 下一个进程，还是 1－2-2.2步骤。也没拿到锁，白白浪费了一圈资源。
sleep队列中有5个进程，每次walkup_one()唤醒一个进程，去拿锁，拿到锁工作，工作完walkup_one()下一个进程。FIFO唤醒顺序。
如果修改walk（）函数实现成walk-one（）不合适，walk全部唤醒的特性被用在很多地方需要。 例如：一个进程读完管道数据，唤醒所有写进程，写相互竞争。如果替换成walk——one，那么只有一个写着会醒来，等它写完后，即使管道中有空间，别的写进程也不会被唤醒，除非读进程读完后重新walk_one().这样效率太低。
替换walkup_one引起的惊群问题？
- 先拿到管道写锁。
- 判断是非有写入空间。 3.1 有空间写入。 3.2 没空间，重新去拿写锁。
- 唤醒walk_one()唤醒一下一个进程。 ？？
[保留] 惊群(thundering herd)问题在linux上可能是莫须有的问题 http://www.chinaunix.net/old_jh/23/946261.html
##10.7 总结
自旋锁，短期互斥保护临界区，把单核os改造成多处理器运行。 一个进程有私有数据是不需要保护的。 多线程内核是优势，
如果没使用下面,3种手段的保护的进程可能被抢占（正在执行的被重新返回等待队列），但是让内核具备可以被抢占，支持实时系统特点。（优先级高的任务，立刻可以获得CPU资源）
没使用3种手段，进程会被抢占。
- 持有自旋锁。
- 长期锁。
- 提高中断优先级保护。
不足够，单处理器walkup唤醒所有进程，但是CPU只有一个，还是一个一个来执行的。 但是多CPU时代，被唤醒的进程在不同的CPU上执行，锁竞争加剧了，但是一个时刻只有一个人拿到锁，没拿到锁的人，就sleep，白白被叫醒。导致颠簸。walkup_one一次叫醒一个来解决这个问题。