深入理解Linux内核--内核同步（阅读笔记）（原创）
深入理解Linux内核--内核同步（阅读笔记）（原创）
?
由 王宇 原创并发布 ：
?
??????? 每当读到书中的这一章节时，都使我产生放弃的想法。原因是这章中的内容是我认为最复杂，最难以理解的一章（对充分理解Linux操作系统，也是非常重要的一部分）。我是将中断（包括可延迟函数）、信号、系统调用、进程、内存、文件系统，这些部分的内容阅读完成后，在阅读此章的，所以我推荐和我有同样感受的读者，在没有搞清楚其他章节的内容时，可以先放弃这章的阅读。
?
第五章内核同步
你可以把内核看作是不断对请求进行响应的服务器，这些请求可能来自在CPU上执行的进程，也可能来自发出中断请求的外部设备。我们用这个类比来强调内核的各个部分并不是严格按照顺序依次执行的，而是采用交错执行的方式。因此，这些请求可能要求竞争条件，而我们必须采用适当的同步机制对这种情况进行控制。
1、内核如何为不同的请求提供服务
??? 我们把内核看作必须满足两种请求的侍者：一种请求来自顾客，另一种轻轻来自数量有限的几个不同的老板。策略：
??? ??? 1、老板提出请求时，如果侍者正空闲，则侍者开始为老板服务
??? ??? 2、如果老板提出请求时侍者正在为顾客服务，那么侍者停止为顾客服务，开始为老板服务。
??? ??? 3、如果一个老板提出请求时侍者正在为另一个老板服务，那么侍者停止为第一个老板提供服务，而开始为第二个老板服务，服务完毕再继续为第一个老板服务。
??? ??? 4、一个老板可能命令侍者停止正在为顾客提供的服务。侍者在完成对老板最近请求的服务之后，可能会暂时不理会原来的顾客而去为新选中的顾客服务
??? 侍者提供的服务对应于CPU处于内核态时所执行的代码。如果CPU在用户态执行，则侍者被认为处于空闲状态。
??? 老板的请求相当于中断，而顾客的请求相当于用户态进程发出的系统调用或异常
??? [1]内核抢占
??? ??? 如果进程执行内核函数时，即它的内核态运行时，允许发生内核切换（被替换的进程是正执行内核函数的进程），这个内核就是抢占的。
??? ??? 抢占内核的主要特点是：一个在内核态运行的进程，可能在执行内核函数期间被另外一个进程取代
??? ??? 使内核可抢占的目的是减少用户态进程的分配延迟，即从进程变为可执行状态到它实际开始运行之间的时间间隔。内核抢占对执行及时被调度的任务（如：电影播放器）的进程确实是有好处的，因为它降低了这种进程被另一个运行在内核态的进程延迟的风险
??? ??? 以下原则告诉我们：只有内核正在执行异常处理程序（尤其是系统调用），而且内核抢占没有被显式地禁用时，才可能抢占内核。
??? ??? thread_info描述符的preempt_count字段大于0时
??? ??? 1、内核正在执行中断服务例程
??? ??? 2、可延迟函数被禁止（当内核正在执行软中断或tasklet时经常如此）
??? ??? 3、通过把抢占计数器设置为正数而显式地禁用内核抢占
??? ??? 内核抢占会引起不容忽视的开销。因此Linux2.6独具特色地允许用户在编译内核时通过设置选项来禁用或启用内核抢占
??? [2]什么时候同步是必需的
??? ??? 当计算的结果依赖于两个或两个以上的交叉内核控制路径的嵌套方式时，可能出现竞争条件。临界区是一段代码，在其他的内核控制路径能够进入临界区前，进入临界区的内核控制路径必须全部执行完这段代码。
??? ??? 交叉内核控制路径使内核开发者的工作变得复杂：他们必须特别小心地识别出异常处理程序、中断处理程序、可延迟函数和内核线程中的临界区。一旦临界区被确定，就必须对其采用适当的保护措施，以确保在任何时刻只有一个内核控制路径处于临界区。
??? ??? 如果是单CPU的系统，可以采取访问共享数据结构时关闭中断的方式来实现临界区，因为只有在开中断的情况下，才可能发生内核控制路径的嵌套。
??? ??? 另外，如果相同的数据结构仅被系统调用服务例程所访问，而且系统中只有一个CPU，就可以非常简单地通过在访问共享数据结构时禁用内核抢占功能来实现临界区。
??? ??? 正如你们所预料的，在多处理器系统中，情况要复杂得多。由于许多CPU可能同时执行内核路径，因此内核开发者不能假设只要禁用内核抢占功能，而且中断、异常和软中断处理程序都没有访问过该数据结构，就能保证这个数据结构能够安全地被访问。
??? [3]什么时候同步是不必需的
??? ??? 所有的中断处理程序响应来自PIC的中断并禁用IRQ线。此外，在中断处理程序结束之前，不允许产生相同的中断事件
??? ??? 中断处理程序、软中断和tasklet既不可以被抢占也不能被阻塞，所以它们不可能长时间处于挂起状态。在最坏的情况下，它们的执行将有轻微的延迟，因此在其执行的过程中可能发生其他的中断（内核控制路径的嵌套执行）
??? ??? 执行中断处理的内核控制路径不能被执行可延迟函数或系统调用服务例程的内核控制路径中断
??? ??? 软中断和tasklet不能在一个给定的CPU上交错执行
??? ??? 同一个tasklet不可能同时在几个CPU上执行。
??? ??? 简化的例子：(???)
??? ??? ??? 中断处理程序和tasklet不必编写成可重入的函数
??? ??? ??? 仅被软中断和tasklet访问的每CPU变量不需要同步
??? ??? ??? 仅被一种tasklet访问的数据结构不需要同步
2、同步原语
??? 我们考察一下在避免共享数据之间的竞争条件时，内核控制路径是如何交错执行的。**表5-2列出了Linux内核使用的同步技术。“适用范围”一栏表示同步技术是适用于系统中的所有CPU还是单个CPU
??? [1]每CPU变量
??? ??? 事实上每一种显式的同步原语都有不容忽视的性能开销。
??? ??? 最简单也是最重要的同步技术包括把内核变量声明为每CPU变量（per-cpuvariable）每CPU变量主要是数据结构的数组，系统的每个CPU对应数组的一个元素。
??? ??? 一个CPU不应该访问与其他CPU对应的数组元素，另外，它可以随意读或修改它自己的元素而不用担心出现竞争条件，因为它是唯一有资格这么做的CPU，但是，这也意味着每CPU变量基本上只能在特殊情况下使用，也就是当它确定在系统的CPU上的数据在逻辑上是独立的时候。
??? ??? 每CPU的数组元素在主存中被排列以使每个数据结构存放在硬件高速缓存的不同行，因此，对每CPU数组的并发访问不会导致高速缓存行的窃用和实效
??? ??? 虽然每CPU变量为来自不同CPU的并发访问提供保护，但对来自异步函数（中断处理程序和可延迟函数）的访问不提供保护，在这种情况下需要另外的同步原语。
??? ??? 总的原则是内核控制路径应该在禁用抢占的情况下访问每CPU变量。
??? ??? 表5-3每CPU变量的函数和宏
??? [2]原子操作
??? ??? 若干汇编语言指令具有“读-修改-写”类型--也就是说，它们访问存储器单元两次，第一次读原值，第二次写新值
??? ??? 假定运行在两个CPU上的两个内核控制路径试图通过执行非原子操作来同时“读-修改-写”同一存储器单元。首先，两个CPU都试图读同一单元，但是存储器仲裁器（对访问RAM芯片的操作进行串行化的硬件电路）插手，只允许其中的一个访问而让另一个延迟。然而，当第一次读操作已经完成后，延迟的CPU从那个存储器单元正好读到同一次被存储器仲裁器串行化，最终，两个写操作都成功。但是，全局的结果是不对的，因为连个CPU写入同一（新）值。因此，两个交错的“读-修改-写”操作成了一个单独的操作。
??? ??? 避免由于“读-修改-写”指令引起的竞争条件的最容易的办法，就是确保这样的操作在芯片级是原子的。任何一个这样的操作都必须以单个指令执行，中间不能中断，且避免其他的CPU访问同一存储器单元。这些很小的原子操作可以建立在其他更灵活机制的基础之上以创建临界区。
??? ??? 在你编写C代码程序时，并不能保证编译器会为a=a+1或甚至像a++这样的操作使用一个原子指令。因此，Linux内核提供了一个专门的atomic_t类型（一个原子访问计数器）和一些专门的函数和宏（参见表5-4）
??? [3]优化和内存屏蔽
??? ??? 当使用优化的编译器时，你千万不要认为指令会严格按它们在源代码中出现的顺序执行。例如，编译器可能重新安排汇编语言指令以使寄存器以最优的方式使用。此外，现代CPU通常并行地执行若干条指令，且可能重新安排内存访问。这种重新排序可以极大地加速程序的执行
??? ??? 然而，当处理同步时，必须避免指令重新排序。如果放在同步原语之后的一条指令在同步原语本身之前执行，事情很快就会变得失控。事实上，所有的同步原语起优化和内存屏蔽的作用。
??? ??? 优化屏障（optimizationbarrier）原语保证编译程序不会混淆放在原语操作之前的汇编语言指令和放在原语操作之后的汇编语言指令，这些汇编语言指令在C中都有对应的语句。在Linux中，优化屏障就是barrier()宏。volatile关键字禁止编译器把asm指令与程序中的其他指令重新组合。memory关键字强制编译器假定RAM中的所有内存单元已经被汇编语言指令修改；因此编译器不能使用存放在CPU寄存器中的内存单元的值来优化asm指令前的代码。注意，优化屏障并不保证不使当前CPU把汇编语言指令混在一起执行---这是内存屏障的工作
??? ??? 内存屏障（memorybarrier）原语确保，在原语之后的操作开始执行之前，原语之前的操作已经完成。因此，内存屏蔽类似于防火墙，让任何汇编语言指令都不能通过。
??? ??? Linux使用六个内存屏障原语，如表5-6所示。这些原语也被当作优化屏障，因为我们必须保证编译程序不在屏障前后移动汇编语言指令。
??? ??? “读内存屏障”仅仅作用于从内存读的指令，而“写内存屏障”仅仅作用于写内存的指令。
??? [4]自旋锁
??? ??? 当内核控制路径必须访问共享数据结构或进入临界区时，就需要为自己获取一把“锁”。由锁机制保护的资源非常类似于限制于房间内的资源，当某个进入房间时，就把门锁上。如果内核控制路径希望访问资源，就试图获取钥匙“打开门”。当且仅当资源空闲时，它才能成功。然后，只要它还想使用这个资源，门就依然锁着。当内核控制路径释放了锁时，门就打开，另一个内核控制路径就可以进入房间。图5-1
??? ??? 自旋锁（spinlock）是用来在多处理器环境中工作的一种特殊的锁。如果内核控制路径发现自旋锁“开着”就获取并继续自己的执行。相反，如果内核控制路径发现锁由运行在另一个CPU上的内核控制路径“锁着”，就在周围“旋转”，反复执行一条紧凑的循环指令，直到锁被释放。
??? ??? 一般来说，由自旋锁所保护的每个临界区都禁止内核抢占的。在单处理器系统上，这种锁本身并不起锁的作用，自旋锁语言仅仅是禁止或启用内核抢占。请注意，在自旋锁忙等期间，内核抢占还是有效的，因此，等待自旋锁释放的进程有可能被更高优先级的进程替代。
??? ??? 在Linux中，每个自旋锁都用spinlock_t结构表示，其中包含两个字段：
??? ??? ??? slock:该字段表示自旋锁的状态：值为1表示“未加锁”状态，而任何负数和0都表示“加锁”状态
??? ??? ??? break_lock:表示进程正在忙等自旋锁
??? ??? 表5-7自旋锁宏
??? ??? (1)具有内核抢占的spin_lock宏
??? ??? ??? 操作：
??? ??? ??? ??? 1、调用preempt_disable()以禁用内核抢占
??? ??? ??? ??? 2、调用函数_raw_spin_trylock()，它对自旋锁的slock字段执行原子性的测试和设置操作
??? ??? ??? ??? 3、如果自旋锁中的旧值是正数，宏结束：内核控制路径已经获得自旋锁
??? ??? ??? ??? 4、否则，内核控制路径无法获得自旋锁，因此宏必须执行循环一直到其他CPU上运行的内核控制路径释放自旋锁。
??? ??? ??? ??? 5、如果break_lock字段等于0，则把它设置为1.通过检测该字段，拥有锁并在其他CPU上运行的进程可以知道是否有其他进程在等待这个锁。如果进程把持某个自旋锁时间太长，它可以提前释放锁以使等待相同自旋锁的进程能够继续向前运行
??? ??? ??? ??? 6、执行等待循环
??? ??? ??? ??? 7、跳转回到第1步，再次试图获取自旋锁
??? ??? (2)非抢占式内核中的spin_lock宏
??? ??? ??? 如果在内核编译时没有选择内核抢占选项，spin_lock宏就与前面描述的spin_lock宏有很大的区别。在这种情况下，宏生成一个汇编语言程序片段，它本质上等价于下面紧凑的忙等待
??? ??? ??? 1：lock;decbslp->slock
??? ??? ??? jns3f
??? ??? ??? 2:pause
??? ??? ??? cmpb$0,slp->slock
??? ??? ??? jle2b
??? ??? ??? jmp1b
??? ??? ??? 汇编语言指令decb递减自旋锁的值，该指令是原子的，因为它带有lock字节前缀。随后检测符号标志，如果它被清0，说明自旋锁被设置1（未锁），因此从标记3处继续正常执行（后缀f表示标签是“向前的”，它在程序的后面出现）。否则，在标签2处（后缀b表示，“向后的”标签）执行紧凑循环直到自旋锁出现正值。然后从标签1处开始重新执行，因为不检查其他的处理器是否抢占了锁就继续执行是不安全的。
??? ??? (3)spin_unlock宏
??? ??? ??? 释放以前获得的自旋锁
??? [5]读写自旋锁???
??? ??? 读写自旋锁的引入是为了增加内核的并发能力。只要没有内核控制路径对数据结构进行修改，读写自旋锁就允许多个内核控制路径同时读同一数据结构。如果一个内核控制路径想对这个结构进行写操作，那么它必须首先获取读写锁得写锁，写锁授权独占访问这个资源。当然，允许对数据结构并发读可以提高系统性能。
??? ??? 图5-2**
?
??? ??? 每个读写自旋锁都是是一个rwlock_t结构，其lock字段是一个32位的字段，分为两个不同的部分：
??? ??? ??? 24位计数器，表示对受保护的数据结构并发地进行读操作的内核控制路径的数目。这个计数器的二进制补码存放在这个字段的0-23位
??? ??? ??? “未锁”标志字段，当没有内核控制路径在读或写时设置该位，否则清0.这个“未锁”标志存放在lock字段的第24位
??? ??? (1)为读获取和释放一个锁：read_lock宏
??? ??? (2)为写获取和释放一个锁：write_lock宏
??? [6]顺序锁
??? ??? 当使用读写自旋锁时，内核控制路径发出的执行read_lock或write_lock操作的请求具有相同的优先权：读者必须等待，直到写操作完成。同样地，写者也必须等待，直到读操作完成
??? ??? Linux2.6中引入了顺序锁(seqlock)，它与读写自旋锁非常相似，只是它为写者赋予了较高的优先级：事实上，即使在读者正在读的时候也允许写者继续运行。这种策略的好处是写者永远不会等待（除非另外一个写者正在写），缺点是有些时候读者不得不反复多次读相同的数据直到它获得有效的副本
??? ??? 每个顺序锁都是包括两个字段的seqlock_t结构；一个类型为spinlock_t的lock字段和一个整型的sequence字段，第二个字段是一个顺序计数器
??? ??? 注意，当读者进入临界区时，不必禁用内核抢占；另一方面，由于写者获取自旋锁，所以它进入临界区时自动禁用内核抢占
??? ??? 并不是每一种资源都可以使用顺序锁来保护。一般来说，必须在满足下述条件时才能使用顺序锁：
??? ??? ??? 被保护的数据结构不包括被写者修改和被读者间接引用的指针
??? ??? ??? 读者的临界区代码没有副作用
??? ??? 此外，读者的临界区代码应该简短，而且写着应该不常获取顺序锁，否则，反复的读访问会引起严重的开销???
??? [7]读-拷贝-更新
??? ??? 读-拷贝-更新（RCU）是为了保护在多数情况下被多个CPU读的数据结构而设计的另一种同步技术。RCU允许多个读者和写者并发执行（相对于只允许一个写者执行的顺序锁有了改进）。而且，RCU是不使用锁的，就是说，它不使用被所有CPU共享的锁或计数器，在这一点上与读写自旋锁和顺序锁（由于高速缓存行窃用和失效而有很高的开销）相比，RCU具有更大的优势。??? ???
??? ??? 关键的思想包括限制RCU的范围，如下：
??? ??? ??? 1、RCU只保护被动态分配并通过指针引用的数据结构
??? ??? ??? 2、在被RCU保护的临界区中，任何内核控制路径都不能睡眠
??? ??? 当内核控制路径要读取被RCU保护的数据结构时，执行宏rcu_read_lock()，它等同于preempt_disable()
??? ??? 我们还可以想象，由于读者几乎不做任何事情来防止竞争条件的出现，所以写者不得不做得更多一些。事实上，当写者要更新数据结构时，它间接引用指针并生成整个数据结构的副本。接下来，写者修改这个副本。一但修改完毕，写者改变指向数据结构的指针，以使它指向被修改后的副本。由于修改指针值的操作是一个原子操作，所以旧副本和新副本对每个读者或写者都是可见的，在数据结构中不会出现数据崩溃。尽管如此，还需要内存屏蔽来保证：只有在数据结构被修改之后，已更新的指针对其他CPU才是可见的。如果把自旋锁与RCU结合起来以禁止写者的并发执行，就隐含地引入了这样的内存屏蔽。然后，使用RCU技术的真正困难在于：写者修改指针时不能立即释放数据结构的旧副本。实际上，写着开始修改时，正在访问数据结构的读者可能还在读旧副本。只有在CPU上的所有（潜在的）读者都执行完宏rcu_read_unlock()之后，才可以释放旧副本。内核要求每个潜在的读者在下面的操作之前执行rcu_read_unlock()宏：
??? ??? ??? CPU执行进程切换
??? ??? ??? CPU开始在用户态执行
??? ??? ??? CPU执行空循环
??? ??? 对上述每种情况，我们说CPU已经经过了静止状态???
??? [8]信号量
??? ??? 从本质上说，它们实现了一个枷锁原语，即让等待者睡眠，直到等待的资源变为空闲。
??? ??? ??? 内核信号量，由内核控制路径使用
??? ??? ??? SystemVIPC信号量，由用户态进程使用
??? ??? 内核信号量类似于自旋锁，因此当锁关闭着时，它不允许内核控制路径继续进行。然而，当内核控制路径试图获取内核信号所保护的忙资源时，相应的进程被挂起。只有在资源被释放时，进程才再次变为可运行的。因此，只有可以睡眠的函数才能获取内核信号量；中断处理程序和可延续函数都不能使用内核信号量。
??? ??? 内核信号量是struct semaphore类型的对象，包含下面这些字段：
??? ??? ??? count:存放atomic_t类型的一个值
??? ??? ??? wait:存放等待队列链表的地址，当前等待资源的所有睡眠进程都放在这个链表中。当然，如果count大于或等于0,等待队列就为空
??? ??? ??? sleepers:存放一个标志，表示是否有一些进程在信号量上睡眠。
??? ??? 可以用init_MUTEX()和init_MUTEX_LOCKED()函数来初始化互斥访问所需的信号量：这两个宏分别把count字段设置成1（互斥访问的资源空闲）和0（对信号量进行初始化的进程当前互斥访问的资源忙）。宏DECLEAR_MUTEX和DECLARE_MUTEX_LOCKED完成同样的功能，但它们也静态分配semaphore结构的变量。注意也可以把信号量中的count初始化为任意的正数值n,在这种情况下，最多有n个进程可以并发地访问这个资源。???
??? ??? (1)获取和释放信号量
??? ??? ??? 当进程希望释放内核信号量锁时，就调用up()函数
??? ??? ??? up()函数增加*sem信号量count字段的值，然后，检查它的值是否大于0.
??? ??? ??? 当进程希望获取内核信号量锁时，就调用down()函数
??? ??? ??? down()函数减少*sem信号量的count字段的值，然后检查该值是否为负。
??? [9]读写信号量
??? ??? 读写信号量类似于前面“读写自旋锁”一节描述的读写自旋锁，有一点不同：在信号量再次变为打开之前，等待进程挂起而不是自旋。
??? ??? 每个读写信号量都是由rw_semaphore结构描述的
??? ??? ??? count:存放两个16位的计数器
??? ??? ??? wait_list:指向等待进程的链表
??? ??? ??? wait_lock:一个自旋锁，用于保护等待队列链表和rw_semaphore结构本身
??? ??? init_rwsem()函数初始化rw_semaphore结构，即把count字段置为0，wait_lock自旋锁置为未锁，而把wait_list置为空链表
??? ??? down_read()和down_write()函数分别为读或写获取读写信号量。同样，up_read()和up_write()函数为读或写释放以前获取的读写信号量。down_read_trylock()和down_write_trylock()函数分别类似于down_read()和down_write()函数，但是，在信号量忙的情况下，它们不阻塞进程。最后，函数downgrade_write()自动把写锁转换成读锁。这5个函数的实现代码比较长，但因为它与普通信号量的实现类似，所以容易理解。
??? [10]补充原语
??? ??? Linux2.6还使用了另一种类似于信号量的原语：补充（completion）引入这种原语是为了解决多处理器系统上发生的一种微妙的竞争条件，当进程A分配了一个临时信号量变量，把它初始化为关闭的MUTEX，并把其地址传递给进程B，然后在A之上调用down(),进程A打算一但被唤醒就撤销该信号量。随后，运行在不同CPU上的进程B在同一信号量上调用up()。然而，up()和down()的目前实现还允许这两个函数在同一个信号量上并发执行。因此，进程A可以被唤醒并撤销临时信号量，而进程B还在运行up()函数。结果，up()可能试图访问一个不存在的数据结构
??? ??? 当然，也可以改变up()和down()的实现以禁止在同一信号量上并发执行。然而，这种改变可能需要另外的指令，这对于频繁使用的函数来说不是什么好事。
??? ??? 补充是专门设计来解决以上问题的同步原语.completion数据结构包含一个等待队列头和一个标志
??? ??? 与up()对应的函数叫做complete()
??? ??? 与down()对应的函数叫wait_for_completion()
??? ??? 补充原语和信号量之间的真正差别在于如何使用等待队列中包含的自旋锁。在补充原语中，自旋锁用来确保completion()和wait_for_completion()不会并发执行。在信号量中，自旋锁用于避免并发执行的down()函数弄乱信号量的数据结构
??? [11]禁止本地中断
??? ??? 确保一组内核语句被当作一个临界区处理的主要机制之一就是中断禁止。即使当硬件设备产生了一个IRQ信号时，中断禁止也让内核控制路径继续执行，因此，这就提供了一种有效的方式，确保中断处理程序访问的数据结构页受到保护。然而，禁止本地中断并不保护运行在另一个CPU上的中断处理程序对数据结构的并发访问，因此，在多处理器系统上，禁止本地中断经常与自旋锁结合使用。
??? ??? 宏local_irq_disable()使用cli汇编语言指令关闭本地CPU上的中断，宏local_irq_enable()使用sti汇编语言指令打开被关闭的中断
??? [12]禁止和激活可延续函数
??? ??? 可延续函数可能在不可预知的时间执行（实际上是在硬件中断处理程序结束时）。因此，必须保护可延续函数访问的数据结构使其避免竞争条件
??? ??? 禁止可延迟函数在一个CPU上执行的一种简单方式就是禁止在那个CPU上的中断。因为没有中断处理程序被激活，因此，软中断操作就不能异步地开始。
??? ??? 内核有时需要只禁止可延续函数而不禁止中断。通过操纵当前thread_info描述符preempt_count字段中存放的软中断计数器，可以在本地CPU上激活或禁止可延续函数。
3、对内核数据结构的同步访问
??? 系统性能可能随所选择同步原语种类的不同而有很大变化。通常情况下，内核开发者采用下述由经验得到的法则：把系统中的并发度保持在尽可能高的程度。
??? 系统中的并发度又取决于两个主要因素：
??? ??? 同时运转的IO设备数
??? ??? 进行有效的工作的CPU数
??? 为了是IO吞吐量最大化，应该使中断禁止保持在很短的时间。
??? 为了有效地的利用CPU，应该尽可能避免使用基于自旋锁的同步原语。当一个CPU执行紧指令循环等待自旋锁打开时，是在浪费宝贵的机器周期。就像我们面前所描述的，更糟糕的是：由于自旋锁对硬件高速缓存的影响而使其对系统的整体性能产生不利影响
??? 让我们举例说明在下列两种情况下，既可以维持较高的并发度，也可以达到同步
??? ??? 共享的数据结构时一个单独的整数值，可以把它声明为atomic_t类型并使用原子操作对其更新。原子操作比自旋锁和中断禁止都快，只有在几个内核控制路径同时访问这个数据结构是速度才会慢下来
??? ??? 把一个元素插入到共享链表的操作决不是原子的，因为这至少涉及两个指针赋值。不过，内核有时并不用锁或禁止中断就可以执行这种插入操作
??? ??? 在C语言中，插入链表通过下列指针赋值实现的：
??? ??? ??? new->next=list_element->next；
??? ??? ??? list_element->next=new;
??? ??? 第一条指令建立new元素的next指针，但不修改链表。因此，如果中断处理程序在第一条指令和第二条指令执行的中间查看这个链表，看到的就是没有新元素的链表。如果该处理程序在第二条指令执行后查看链表，就会看到有新元素的链表。关键是，在任一种情况下，链表都是一致的且处于未损坏状态。然后，只有在中断处理程序不修改链表的情况下才能确保这种完整性。如果修改了链表，那么在new元素内刚刚设置的next指针就可能变为无效的
??? ??? 需要加一个写内存屏蔽原语：
??? ??? ??? new->next=list_element->next;
??? ??? ??? wmb();
??? ??? ??? list_element->next=new;
??? [1]在自旋锁、信号量及中断禁止之间选择
??? ??? 同步原语的选取取决于访问数据结构的内核控制路径的种类，如表5-8所示。记住，只要内核控制路径获得自旋锁（还有读、写锁、顺序锁或RCU“读锁”），就禁用本地中断或本地软中断，自动禁用内核抢占
??? ??? 表：5-8****
?
?
??? ??? (1)保护异常所访问的数据结构
??? ??? ??? 当一个数据结构仅由异常程序访问时，竞争条件通常是易于理解也易于避免的。最常见的产生同步问题的异常就是系统调用服务例程，在这种情况下，CPU运行在内核态而为用户态程序提供服务。因此，仅由异常访问的数据结构通常表示一种资源，可以分配给一个或多个进程。
??? ??? ??? 竞争条件可以通过信号量避免，因为信号量原语允许进程睡眠到资源变为可用。注意，信号量工作方式在单处理器系统和多处理器系统上完全相同。
??? ??? (2)保护中断所访问的数据结构
??? ??? ??? 假定一个数据结构仅被中断处理程序的“上半部分”访问。中断处理程序本身不能同时多次运行。因此，访问数据结构就无需任何同步原语。
??? ??? ??? 但是，如果多个中断处理程序访问一个数据结构，情况就有所不同了。一个处理程序可以中断另一个处理程序，不同的中断处理程序可以在多个处理器系统上同时运行。没有同步，共享的数据结构就很容易被破坏。
??? ??? ??? 在单处理器系统上，必须通过在中断处理程序的所有临界区上禁止中断来避免竞争条件。只能用这种方式进行同步，因为其他的同步原语都不能完成这件事。
??? ??? ??? 多处理器系统上，避免竞争条件最简单的方法是禁止本地中断，并获取保护数据结构的自旋锁或读、写自旋锁。注意，这些附加的自旋锁不能冻结系统，因为即使中断处理程序发现锁被关闭，在另一个CPU上拥有锁得中断处理程序最终也释放这个锁。
??? ??? (3)保护可延迟函数所访问的数据结构
??? ??? ??? 只被可延迟函数访问的数据结构需要那种保护呢？这主要取决于可延迟函数的种类。软中断和tasklet本质上有不同的并发度。
??? ??? ??? 在单处理器系统上不存在竞争条件。这是因为可延迟函数执行总是在一个CPU上串行进行---也就是说，一个可延迟函数不会被另一个可延迟函数中断。因此，根本不需要同步原语。
??? ??? ??? 在多处理器系统上，竞争条件的确存在，因为几个可延迟函数可以并发运行：表5-10***
??? ??? ??? 由软中断访问的数据结构必须受到保护，通常使用自旋锁进行保护，因为同一个软中断可以在两个或多个CPU上并发运行。相反，仅有一种tasklet访问的数据结构不需要保护，因为同种tasklet不能并发运行。但是，如果数据结构被几种tasklet访问，那么，就必须对数据结构进行保护。
??? ??? (4)保护异常和中断访问的数据结构
??? ??? ??? 在单处理器系统上，竞争条件的防止是相当简单的，因为中断处理程序不是可重入的且不能被异常中断。只要内核以本地中断禁止访问数据结构，内核在访问数据结构的过程中就不会被中断。不过，如果数据结构正好是被一种中断处理程序访问，那么，中断处理程序不用禁止本地中断就可以自由地访问数据结构。
??? ??? ??? 在多处理器系统上，我们必须关注异常和中断在其他CPU上的并发执行。本地中断禁止还必须外加自旋锁，强制并发的内核控制路径进行等待，直到访问数据结构的处理程序完成自己的工作。
??? ??? (5)保护异常和可延迟函数访问的数据结构
??? ??? ??? 异常和可延迟函数都访问的数据结构与异常和中断处理程序访问的数据结构处理方式类似。事实上，可延迟函数本质上是由中断的出现激活的，而可延迟函数执行时不可能产生异常。因此，把本地中断禁止与自旋锁结合起来就足够了。
??? ??? (6)保护中断和可延迟函数所访问的数据结构
??? ??? ??? 类似于中断和异常处理程序访问的数据结构：本地中断禁用与自旋锁
??? ??? (7)保护异常、中断和可延迟函数所访问的数据结构
??? ??? ??? 类似于前面的情况，禁止本地中断和获取自旋锁几乎总是避免竞争条件所必需的。注意，没有必要显式地禁止可延迟函数，因为当中断处理程序终止执行时，可延迟函数才能被实质激活；因此，禁止本地中断中断就做够了。
4、避免竞争条件的实例
??? [1]引用计数器
??? ??? 引用计数器广泛地用在内核中以避免由于资源的并发分配和释放而产生的竞争条件。引用计数器（referencecounter）只不过是一个atomic_t计数器，与特定的资源，如内存页，模块或文件相关。当内核控制路径开始使用资源是就原子地减少计数器的值，当内核控制路径使用完资源时就原子地增加计数器。当引用计数器变为0时，说明该资源未被使用，如果必要，就释放该资源
??? [2]大内核锁
??? ??? 从2.6.11开始，用一个叫做kernel_sem的信号量来实现大内核锁（在较早的版本中，大内核锁是通过自旋锁来实现的）。但是，大内核锁比简单的信号量要复杂一些。详细内容参见：p225-226
??? [3]内存描述符读/写信号量
??? ??? mm_struct类型的每个内存描述符mmap_sem字段中都包含了自己的信号量。由于几个轻量级进程之间可以共享一个内存描述符，因此，信号量保护这个描述符以避免可能产生的竞争条件
??? [4]slab高速缓存链表的信号量
??? ??? slab高速缓存描述符链表是通过cache_chain_sem信号量保护的，这个信号量允许互斥地访问和修改该链表
??? [5]索引节点的信号量
??? ??? Linux把磁盘文件的信息存放在一种叫做索引节点(inode)的内核对象中。相应的数据结构也包括有自己的信号量，存放在i_sem字段中。
??? ??? 在文件系统的处理过程中会出现很多竞争条件。实际上，磁盘上的每个文件都是所有用户共有的一种资源，因此所有进程都（可能）会存取文件的内容、修改文件名或文件位置、删除或复制文件等等。
??? ??? 只要一个程序使用了两个或多个信号量，就存在死锁的可能，因为两个不同的控制路径可能互相死等着释放信号量。一般来说，Linux在信号量请求上很少会发生死锁问题，因为每个内核控制路径通常一次只需要获得一个信号量。然而在有些情况下，内核必须获得两个或更多的信号量锁。索引点信号量倾向于这种情况。例如：在rename()系统调用的服务例程中就会发生这种情况。在这种情况下，操作涉及两个不同的索引节点，因此，必须采用两个信号量。为了避免这样的死锁，信号量的请求按预先确定的地址顺序进行
?
---------------------------------------------
附录：
并发，竞争与同步：并发，竞争和同步的概念，我们假定大家都有所了解，本文不再重申。我们讨论的重点放在什么情况会发生内核并发上？如何防止内核并发？有那些同步方法？以及这些方法的行为有何特点和如何使用它们？
下面一段描述了上述几个概念之间的大致关系，这种关系在内核中同样适用。
对于多线程程序的开发者来说，往往会利用多线程访问共享数据，避免繁琐的进程间通讯。但是多线程对共享数据的并发访问有可能产生竞争，使得数据处于不一致状态，所以需要一些同步方法来保护共享数据。多线程的并发执行是由于线程被抢占式的调度——一个线程在对共享数据访问期间（还未完成）被调度程序中断，将另一个线程投入运行——如果新被调度的线程也要对这个共享数据进行访问，就将产生竞争。为了避免竞争产生，需要使线程串行地访问共享数据，也就是说访问需要同步——在一方对数据访问结束后，另一方才能对同一数据进行访问。
内核并发原因上述情况是用户空间并发产生的普遍原因，对于内核来说并发原因也大致类似，但是情况要更多样，也更复杂。
对于单处理机器来说情况相对简单一些。在2.6版本内核之前，Linux内核是非抢占式的——在内核任务没有执行完之前不能被打断，这样的话，内核中程序并发执行的情况很少，准确地讲只有两种可能：
一：中断发生?，因为中断执行是异步的，而且中断是在非抢占式内核中打断当前运行内核代码的唯一方法，所以中断显然是可以和其它内核代码并发执行的。因此如果中断操作和被中断的那内核代码都访问同样的内核数据，那么就会发生竞争。
二?：睡眠和再调度,处于进程上下文（下面会进行讲述）的内核任务可以睡眠（睡眠意味放弃处理器），这时调度程序会调度其它程序去执行（首先执行调度任务队列中的内核任务，然后执行软中断等，最后从运行队列中选择一个高优先级的用户进程运行）。显然这里也会造成内核并发访问，当睡眠的内核任务和新投入运行的内核任务访问同一共享数据时，就发生了竞争。请看参考资料1
2.6版本的内核变成了抢占式内核——内核可能在任何时刻抢占正在运行的内核代码。所以内核中发生并发执行的情况大大增加了。内核抢占成为了内核程序并发的又一种可能，所以在开发抢占式内核代码时需要时刻警惕抢占产生的竞争。
单处理器上的并发是逻辑上的伪并发，事实上所谓并发的内核程序其实是交错地占用处理器。真正的并发执行程序，必须依靠对称多处理器。但无论是逻辑上的并发还是真正的并发，都会产生竞争，而且它们的处理也是相同的。但是对于对称多处理器来说，由于两个或多个处理器可以在同一时刻执行代码，所以会不可避免地给内核带来并发可能，如果分别在不同处理器上执行的内核代码同时访问同一共享数据，竞争就产生了。因此，不用说对称多处理是内核并发的又一种可能。请看参考资料2
可以看到随着Linux内核不断演化，在内核对系统支持更加全面，对任务调度更加高效的同时，也给内核带来了更多的并发可能，更容易引起竞争。上面提到的各种并发情况在内核中都必须得到有效的处理，才能确保内核有高稳定性。
无论是中断产生的并发或是睡眠引起的并发，还是内核抢占引起的并发，要想在内核开发中很好地避免，就必须从本质上了解它们的并发原因。只有在掌握内核任务的调度机制后，才可以真正的达到对并发可能的预测，进而能够采取合适的同步方法——锁——来避免并发。
下面我们就对任务调度进行讨论。对比并发产生的条件，分析内核中的调度发生的条件。
