Linu内核 对称多处理

第10章对称多处理(SMP)在全书的讨论过程中，我一直在忽略SMP代码，而倾向于把注意力集中在只涉及一个 处理器的相对简单的情况现在已经到了重新访问读者已经熟悉的一些内容的时候了，不过 要从一个新的角度来审视它：当内核必须支持多于一个CPU的机器时将发生什么？在一般情况下，使用多于一个CPU来完成工作被称为并行处理(parallel processing), 它可以被想象成是一段频谱范围，分布式计算(distributed computing)在其中一端，而对称 多处理(SMP一symmetric multiprocessing)在另一端通常，当你沿着该频谱从分布式计算 向SMP移动时，系统将变得更加紧密耦合——在CPU之间共享更多的资源——而且更加均 匀在一个典型的分布式系统中，每个CPU通常都至少拥有它自己的高速缓存和RAM每 个CPU还往往拥有自己的磁盘、图形子系统、声卡，监视器等等在极端的情形下，分布式系统经常不外乎就是一组普通的计算机，虽然它们可能具有完 全不同的体系结构，但是都共同工作在某个网络之上——它们甚至不需要在同一个LAN里 读者可能知道的一些有趣的分布式系统包括：Beowulf，它是对相当传统而又极其强大的分 布式系统的一个通用术语称谓；SETI@home，它通过利用上百万台计算机来协助搜寻地外 生命的证据，以及,它是类似想法的另一个实现，它主要关注于地球上产生的 密码的破解。

SMP是并行处理的一个特殊情况，系统里所有CPU都是相同的举例来说，SMP就 是你共同支配两块80486或两块Pentium (具有相同的时钟速率)处理器，而不是一块80486 和一块Pentium,或者一块Pentium和一块PowerPC0在通常的用法中，SMP也意味着所有 CPU 都是“在相同处境下的”一一那就是它们都在同一个计算机里，通过特殊用途的硬件 进行彼此通信SMP系统通常是另一种平常的单一(single)计算机——只不过具有两个或更多的CPU 因此，SMP系统除了 CPU以外每样东西只有一个——一块图形卡、一个声音卡，等等之类 诸如RAM和磁盘这样以及类似的资源都是为系统的CPU们所共享的尽管现在SMP系 统中每个CPU都拥有自己的高存缓存的情况已经变得愈发普遍了)分布式配置需要很少的或者甚至不需要来自内核的特殊支持；节点之间的协同是依靠用 户空间的应用程序或者诸如网络子系统之类未经修改的内核组件来处理的但是SMP在计 算机系统内创建了一个不同的硬件配置，并由此需要特殊用途的内核支持比如，内核必须 确保CPU在访问它们的共享资源时要相互合作一一这是一个读者在UP世界中所不曾遇到 的问题。

SMP的逐渐普及主要是因为通过SMP所获得的性能的提高要比购买几台独立的机器再 把它们组合在一起更加便宜和简单，而且还因为它与等待下一代CPU面世相比要快的多非对称多 CPU 的配置没有受到广泛支持，这是因为对称配置情况所需的硬件和软件支 持通常较为简单不过，内核代码中平台无关的部分实际上并不特别关心是否CPU是相同 的一一即，是否配置是真正对称的一一尽管它也没有进行任何特殊处理以支持非对称配置 例如，在非对称多处理系统中，调度程序应该更愿意在较快的而不是较慢的CPU上运行进 程，但是Linux内核没有对此进行区别谚语说得好，“天下没有白吃的午餐”对于SMP，为提高的性能所付出的代价就是内 核复杂度的增加和协同开销的增加 CPU 必须安排不互相干涉彼此的工作，但是它们又不 能在这种协同上花费太多时间以至于它们显著地耗费额外的CPU能力代码的SMP特定部分由于UP机器存在的缘故而被单独编译，所以仅仅因为有了 SMP寄存器是不会使UP寄存器慢下来的这满足两条久经考验的原理：“为普遍情况进行优化” （UP机器远比SMP机器普遍的多）以及“不为用不着的东西花钱”并行程序设计概念及其原语具有两个CPU的SMP配置可能是最简单的并行配置，但就算是这最简单的配置也揭 开了未知问题的新领域一一即使要两块相同的CPU在一起协调的工作，时常也都像赶着猫 去放牧一样困难。

幸运的是，至少30 年前以来，就在这个项目上作了大量和非常熟悉的研 究工作考虑到第一台电子数字计算机也只是在50年前建造的，那这就是一段令人惊讶的 相当长的时间了在分析对SMP的支持是如何影响内核代码之前，对该支持所基于的若干 理论性概念进行一番浏览将能够极大的简化这个问题注意：并非所有这些信息都是针对SMP内核的一些要讨论的问题甚至是由UP内核 上的并行程序设计所引起的，既要支持中断也要处理进程之间的交互因此即使你对 SMP 问题没有特别的兴趣，这部分的讨论也值得一看原子操作在一个并行的环境里，某些动作必须以一种基本的原子方式（atomically）执行 即不可中断这种操作必须是不可分割的，就象是原子曾经被认为的那样作为一个例子，考虑一下引用计数如果你想要释放你所控制的一份共享资源并要了解 是否还有其它（进程）仍在使用它，你就会减少对该共享资源的计数值并把该值与0 进行对 照测试一个典型的动作顺序可能如下开始：1. CPU把当前计数值（假设是2）装载进它的一个寄存器里2. CPU在它的寄存器里把这个值递减；现在它是13. CPU把新值（1）写回内存里4. CPU推断出：因为该值是1，某个其它进程仍在使用着共享对象，所以它将不会释 放该对象。

对于UP,应不必在此考虑过多（除了某些情况）但是对于SMP就是另一番景象了： 如果另一个CPU碰巧同时也在作同样的事情应如何处理呢？最坏的情形可能是这样的：1. CPU A把当前计数值（2）装载进它的一个寄存器里2. CPU B 把当前计数值（2）装载进它的一个寄存器里3. CPU A在它的寄存器里把这个值递减；现在它是14. CPU B 在它的寄存器里把这个值递减；现在它是15. CPU A把新值（1）写回内存里6. CPU B把新值（1）写回内存里7. CPU A推断出：因为该值是1，某个其它进程仍在使用着共享对象，所以它将不会 释放该对象8. CPU B推断出：因为该值是1，某个其它进程仍在使用着共享对象，所以它将不会 释放该对象内存里的引用计数值现在应该是0，然而它却是1两个进程都去掉了它们对该共享对 象的引用，但是没有一个能够释放它这是一个有趣的失败，因为每个CPU都作了它所应该做的事情，尽管这样错误的结果 还是发生了当然这个问题就在于CPU没有协调它们的动作行为一一右手不知道左手正在 干什么你会怎样试图在软件中解决这个问题呢？从任何一个CPU的观点来看待它一一比如说 是CPU A。

需要通知CPU B它不应使用引用计数值，由于你想要递减该值，所以不管怎样 你最好改变某些CPUB所能见到的信息一一也就是更新共享内存位置举例来说，你可以 为此目的而开辟出某个内存位置，并且对此达成一致：若任何一个CPU正试图减少引用计 数它就包含一个1，如果不是它就为0使用方法如下：1. CPU A从特殊内存位置出取出该值把它装载进它的一个寄存器里2. CPU A检查它的寄存器里的值并发现它是0 （如果不是，它再次尝试，重复直到该 寄存器为 0为止3. CPU A把一个1写回特殊内存位置4. CPU A访问受保护的引用计数值5. CPU A把一个0写回特殊内存位置糟糕，令人不安的熟悉情况又出现了以下所发生的问题仍然无法避免：1. CPU A从特殊内存位置出取出该值把它装载进它的一个寄存器里2. CPU B 从特殊内存位置出取出该值把它装载进它的一个寄存器里3. CPU A检查它的寄存器里的值并发现它是04. CPU B 检查它的寄存器里的值并发现它是05. CPU A把一个1写回特殊内存位置6. CPU B 把一个1 写回特殊内存位置7. CPU A访问受保护的引用计数值8. CPU B 访问受保护的引用计数值。

9. CPU A把一个0写回特殊内存位置10. CPU B 把一个0写回特殊内存位置好吧，或许可以再使用一个特殊内存位置来保护被期望保护初始内存位置的那个特殊内 存位置„„面对这一点吧：我们在劫难逃这种方案只会使问题向后再退一层，而不可能解决它 最后，原子性不可能由软件单独保证一一必须要有硬件的特殊帮助在x86平台上，lock指令正好能够提供这种帮助准确地说，lock是一个前缀而非一 个单独的指令，不过这种区别和我们的目的没有利害关系lock指令用于在随后的指令执 行期间锁住内存总线一一至少是对目的内存地址因为x86可以在内存里直接减值，而无需 明确的先把它读入一个寄存器中，这样对于执行一个减值原子操作来说就是万事俱备了： lock内存总线然后立刻对该内存位置执行decl操作函数atomic_dec （10241行）正好为x86平台完成这样的工作LOCK宏的SMP版本 在第10192行定义并扩展成lock指令在随后的两行定义的UP版本完全就是空的——单 CPU 不需要保护自己以防其它 CPU 的干扰，所以锁住内存总线将完全是在浪费时间通 过把LOCK宏放在内嵌编译指令的前边，随后的指令就会为SMP内核而被锁定。

如果CPU B在CPU A发挥作用时执行了 atomic_dec函数，那么CPU B就会自动的等待CPU A把锁 移开这样就能够成功了！这样还只能说是差不多最初的问题仍然没有被很好的解决目标不仅是要自动递减引 用计数值，而且还要知道结果值是否是0现在可以完成原子递减了，可是如果另一个处理 器在递减和结果测试之间又“偷偷的”进行了干预，那又怎么办呢？幸运的是，解决这个部分问题不需要来自CPU的特殊目的的帮助不管加锁还是未锁， x86的decl指令总是会在结果为0时设置CPU的Zero标志位，而且这个标志位是CPU私 有的，所以其它CPU的所为是不可能在递减步骤和测试步骤之间影响到这个标志位的相 应的，atomic_dec_and_test （10249行）如前完成一次加锁的递减，接着依据CPU的Zero 标志位来设置本地变量c如果递减之后结果是0函数就返回非零值（真）如同其它定义在一个文件里的函数一样， atomic_dec 和 atomic_dec_and_test 都对一个 类型为atomic_t的（10205行）对象进行操作就像LOCK，atomic_t对于UP和SMP也 有不同的定义方式 不同之处在于SMP情况里引入了 volatile限定词，它指示gcc不要对被标记的变量做某种假定（比如，不要假定它可以被安全的保存在一个寄存器里）。

顺便提及一下，读者在这段代码里看到的垃圾代码__atomic_fool_gcc 据报告已不再需 要了；它曾用于纠正在gcc的早期版本下代码生成里的一个故障Test-And-Set经典的并行原语是 test-and-set test-and-set 操作自动地从一个内存位置读取一个值然后 写入一个新值，并把旧值返回典型的，该位置可以保存0或者1,而且test-and-set所写的 新值是1 因此是“设置（set）”与test-and-set对等的是test-and-clear,它是同样的操作除了写入的是0而不是1一些test-and-set的变体既能写入1也可以写入0,因此test-and-set 和test-and-clear就能够成为一体，只是操作数不同而已test-and-set 原语足以实现任何其它并行安全的操作 （实际上，在某些 CPU 上 test-and-set是唯一被提供的此类原语比如，原本test-and-set是能够用于前边的例子之中 来保护引用计数值的相似的方法以被尝试——从一个内存位置读取一个值，检查它是否为 0，如果是则写入一个 1，然后继续访问受保护的值这种尝试的失败并不是因为它在逻辑 上是不健全的，而是因为没有可行的方法使其自动完成。

假使有了一个原子的test-and-set， 你就可以不通过使用lock来原子化decl的方法而顺利通过了然而， test-and-set 也有缺点：• 它是一个低级的原语一一在所有与它打交道时，其它原语都必须在它之上被执行• 它并不经济一一当机器测试该值并发现它已经是1 了怎么办呢？这个值在内存里 不会被搞乱，因为只要用同样的值复写它即可可事实是它已被设置就意味着其它 进程正在访问受保护的对象，所以还不能这样执行额外需要的逻辑一一测试并循 环——会浪费CPU时钟周期并使得程序变得更大一些（它还会浪费高速缓存里的 空间）x86的lock指令使高级指令更容易执行，但是你也可以在上执行原子test-and-set操作 最直接的方式是把lock和btsl指令（位test-and-set）联合起来使用这种方法要被本章后 边介绍的自旋锁（spinlock ）所用到另一种在x86上实现的方法是用它的xchg （exchange）指令，它能够被x86自动处理， 就好像它的前面有一个lock指令一样 只要它的一个操作数是在内存里xchg要比lock/ btsl组合更为普遍，因为它可以一次交换8、16,或者32位而不仅仅是1位。

除了一个在 arch/i386/kernel/entry.S里的使用之外，内核对xchg指令的使用都隐藏在xchg宏（13052行） 之后，而它又是在函数__xchg（13061 行）之上实现的这样是便于在平台相关的代码里内 核代码也可以使用xchg宏；每种平台都提供它自己对于该宏的等价的实现有趣的时，xchg宏是另一个宏，tas （test-and-set 13054行）的基础然而，内核代码的任何一个地方都没有用到这个宏内核有时候使用xchg宏来完成简单的test-and-set操作（尽管不必在锁变得可用之前一 直循环，如同第22770行），并把它用于其它目的（如同第27427行）信号量第9 章中讨论了信号量的基本概念并演示了它们在进程间通信中的用法内核为达自己 的目的有其特有的信号量实现，它们被特别的称为是“内核信号量”在这一章里，未经修 饰的名词“信号量”应被理解为是“内核信号量”第9 章里所讨论的基本信号量的概念同 样适用于内核信号量：允许一个可访问某资源用户的最大数目（最初悬挂在吊钩上钥匙的特 定数目），然后规定每个申请资源者都必须先获得一把钥匙才能使用该资源到目前为止，你大概应该已经发现信号量如何能够被建立在 test-and-set 之上并成为二 元（“唯一钥匙”）信号量，或者在像 atomic_dec_and_test 这样的函数之上成为计数信号量 的过程。

内核正好就完成着这样的工作：它用整数代表信号量并使用函数down （11644行） 和 up（11714 行）以及其它一些函数来递减和递增该整数读者将看到，用于减少和增加 整数的底层代码和atomic_dec_and_test及其它类似函数所使用的代码是一样的作为相关历史事件的提示，第一位规范信号量概念的研究者，Edsger Dijistra是荷兰人， 所以信号量的基础操作就用荷兰语命名为：Proberen和Verhogen,常缩写成P和V这对术 语被翻译成“测试（test）”（检查是否还有一把钥匙可用，若是就取走）和“递增（increment）”（把一个钥匙放回到吊钩之上） 那些词首字母正是在前一章中所引入的术语“获得（procure）”和“交出（vacate）”的来源Linux内核打破了这个传统，用操作down和up 的称呼取代了它们内核用一个非常简单的类型来代表信号量：定义在11609行的struct semaphore他只 有三个成员：• count—跟踪仍然可用的钥匙数目如果是0,钥匙就被取完了；如果是负数， 钥匙被取完而且还有其它申请者在等待它另外，如果count是0或负数，那么其 它申请者的数目就等于count的绝对值。

Sema_init 宏（11637 行）允许 count 被初始化为任何值，所以内核信号量可以是 二元的（初始化 count 为 1）也可以是计数型的（赋予它某个更大的初始值）所 有内核信号量代码都完全支持二元和计数型信号量，前者可作为后者的一个特例 不过在实践中count总是被初始化为1,这样内核信号量也总是二元类型的尽管 如此，没有什么能够阻止一个开发者将来增加一个新的计数信号量要顺便提及的是，把count初始化为正值而且用递减它来表明你需要一个信号量的 方法并没有什么神秘之处你也可以用一个负值（或者是0）来初始化计数值然后 增加它，或者遵循其它的方案使用正的数字只是内核所采用的办法，而这碰巧和 我们头脑中的吊钩上的钥匙模型吻合得相当好的确，正如你将看到的那样，内核 锁采用的是另一种方式工作——它被初始化为负值，并在进程需要它时进行增加• waking 在up操作期间及之后被暂时使用；如果up正在释放信号量则它被设置为 1 ，否则是 0• wait—因为要等待这个信号量再次变为可用而不得不被挂起的进程队列down11644： down操作递减信号量计数值你可能会认为它与概念里的实现一样简单，不过实际 上远不是这样简单。

11648：减少信号量计数值——要确保对SMP这是自动完成的对于SMP来说（当然也适 于UP），除了被访问的整数是在一个不同类型的 struct之内以外，这同在atomic_dec_and_test中所完成的工作本质上是相同的读者可能会怀疑count是否会下溢它不会：进程总是在递减count之后进入休眠，所以一个给定的进程一次只能获得一个信号量，而且 int 具有的负值要比进程的数 目多的多11652：如果符号位被设置，信号量就是负值这意味着甚至它在被递减之前就是0 或者负 值了，这样进程无法得到该信号量并因此而应该休眠一直到它变成可用接下来的 几行代码十分巧妙地完成了这一点如果符号位被设置则执行 js 跳转（即若 decl 的结果是负的它就跳转）， 2f 标识出跳转的目的地 2f 并非十六进制值——它是特 殊的 GNU 汇编程序语法： 2 表示跳转到本地符号“2”， f 表示向前搜索这个符号2b将表示向后搜索最近的本地符号“2”这个本地符号在第11655行11653：分支转移没有执行，所以进程得到了信号量虽然看起来不是这样，但是这实际已 经到达down的末尾稍后将对此进行解释11654： down的技巧在于指令.section紧跟在跳转目标的前面，它表示把随后的代码汇编到 内核的一个单独的段中——该段被称为.textJock。

这个段将在内存中被分配并标识 为可执行的这一点是由跟在段名之后的 ax 标志字符串来指定的——注意这个 ax 与 x86 的 AX 寄存器无关这样的结果是，汇编程序将把11655和11656行的指令从down所在的段里转移到 可执行内核的一个不同的段里所以这些行生成的目标代码与其前边的行所生成的 代码从物理上不是连续的这就是为什么说11653行是down的结尾的原因11655:当信号量无法得到时跳转到的这一目的行Pushl $1b并不是要把十六进制值1b压 入栈中 如果要执行那种工作应该使用pushl $0x1b （也可以写成是不带$的）正确的解释是，这个1b和前边见到的2f 一样都是GNU汇编程序语法——它指向一个 指令的地址；在此情形中，它是向后搜索时碰到的第一个本地标识“1”的地址所 以，这条指令是把11653行代码的地址压入栈中；这个地址将成为返回地址，以便 在随后的跳转操作之后，执行过程还能返回到down的末尾1 1656：开始跳转到__down_failed （不包括在本书之内）这个函数在栈里保存几个寄存器 并调用后边要介绍的__down （26932 行）来完成等待信号量的工作。

一旦__down 返回了，__down_failed就返回到down,而它也随之返回一直到进程获得了信号 量__down才会返回；最终结果就是只要down返回，进程就得到信号量了，而不管 它是立刻还是经过等待后获得的它11657:伪汇编程序指令.previous的作用未在正式文档中说明，但是它的意思肯定是还原到 以前的段中，结束11654行里的伪指令.section的作用效果down_interruptible11664： down_interruptible函数被用于进程想要获得信号量但也愿意在等待它时被信号中断 的情况这个函数与down的实现非常相似，不过有两个区别将在随后的两段里进 行解释11666：第一个区别是down_interruptible函数返回一个int值来指示是否它获得了信号量或 者被一个信号所打断在前一种情况里返回值（在result里）是0,在后一种情况 里它是负值这部分上是由11675行代码完成的，如果函数未经等待获得了信号量 则该行把result设置为011679：第二个区别是 down_interruptible 函数跳转到—down_failed_interruptible （不包括 在本书之内）而不是_down_failed。

因循—down_failed建立起来的模式，—down _failed_interruptible 只 是 调 整 几 个 寄 存 器 并 调 用 将 在 随 后 进 行 研 究 的 __down_interruptible 函数（ 26942 行）要注意的是 11676 行为__down_failed_interruptible设置的返回目标跟在xorl之后，xorl用于在信号量可以被立刻获得的 情况中把result归0down_interruptible函数的返回值再被复制进result中down_trylock11687：除了调用—down_failed_trylock 函数（当然还要调用 26961 行的__down_trylock 函 数，我们将在后面对它进行检查）之外， down_trylock 函数和 down_interruptible 函数相同因此，在这里不必对down_trylock函数进行更多解释DOWN_VAR26900：这是作为—down和_down_interruptible共同代码因子的三个宏中的第一个它只 是声明了几个变量DOWN_HEAD26904:这个宏使任务tsk （被DOWN_VAR所声明）转移到task_state给出的状态，然后 把 tsk 添加到等待信号量的任务队列。

最后，它开始一个无限循环，在此循环期间 当__down和__down_interruptible准备退出时将使用break语句结束该循环DOWN_TAIL26926：这个宏完成循环收尾工作，把 tsk 设置回 task_state 的状态，为再次尝试获得信号 量做准备26929:循环已经退出；tsk已或者得到了信号量或者被一个信号中断了（仅适于__down_ interruptible）无论哪一种方式，任务已准备再次运行而不再等待该信号量了，因 此它被转移回TASK_RUNNING并从信号量的等待队列里被注销down26932： __down 和__down_interruptible 遵循以下模式：1. 用DOWN_VAR声明所需的本地变量，随后可能还有补充的本地变量声明2. 以DOWN_HEAD开始进入无穷循环3. 在循环体内完成函数特定的（function-specific）工作4. 重新调度5. 以DOWN_TAIL结束注意对schedule的调用（26686行，在第7章里讨论过） 可以被移进DOWN_TAIL宏中6. 完成任何函数特定的收尾工作 我将只对函数特定的步骤（第3和第6步）进行讨论。

26936： __down的循环体调用waking_non_zero （未包括），它自动检查sem->waking来判 断是否进程正被up唤醒如果是这样，它将waking归零并返回1 （这仍然是同一 个原子操作的一部分）；如果不是，它返回0因此，它返回的值指示了是否进程获 得了信号量如果它获得了值，循环就退出，接着函数也将返回否则，进程将继 续等待顺便要说明的是，观察一下__down 尝试获得信号量是在调用 schedule 之前如果 信号量的计数值已知为负值时，为什么不用另一种相反的方式来实现它呢？实际上 它对于第一遍循环之后的任何一遍重复都是没有影响的，但是去掉一次没有必要的 检查可以稍微加快第一遍循环的速度如果需要为此提出什么特别的理由的话，那 可能就是因为自从信号量第一次被检查之后的几个微秒内它就应该可以被释放（可 能是在另一个处理器上），而且额外获取标志要比一次额外调度所付出的代价少得 多因此__down 可能还可以在重新调度之前做一次快速检查down_interruptible26942： __down_interruptible除了允许被信号中断以外，它和__down在本质上是一样的。

26948：所以，当获取信号量时对waking_non_zero_interruptible （未包括）进行调用如 果它没能得到信号量就返回0，如果得到就返回1，或者如果它被一个信号所中断就 返回-EINTR在第一种情况下，循环继续26958：否则， __down_interruptible 退出，如果它得到信号量就返回 0（不是 1），或者假 如被中断则返回-EINTRdown_trylock26961：有时在不能立刻获得信号量的情况下，内核也需要继续运行所以， __down_trylock 不在循环之内它仅仅调用waking_nonzero_trylock （未包括），该函数夺取信号量, 如果失败就递增该信号量的count （因为内核不打算继续等待下去）然后返回up11714：我们已经详尽的分析了内核尝试获得信号量时的情况，也讨论了它失败时的情况 现在是考察另一面的时候了：当释放一个信号量时将发生什么这一部分相对简单11721：原子性地递增信号量的计数值 11722：如果结果小于等于0，就有某个进程正在等待被唤醒 up 向前跳转到11725行11724： up采用了 down里同样的技巧：这一行进入了内核的单独的一段，而不是在up本 身的段内。

up的末尾的地址被压入栈然后up跳转到__up_wakeup （未包括）这里 完成如同__down_failed 一样的寄存器操作并调用下边要讨论的__up函数up26877： __up函数负责唤醒所有等待该信号量的进程26897:调用wake_one_more （未包括在本书中），该函数检查是否有进程在等待该信号量, 如果有，就增加waking成员来通知它们可以尝试获取它了26880：利用wake_up宏（16612行），它只是调用_wake_up函数（26829行）来唤醒所有 等待进程wake_up26829:正如在第2章中所讨论的那样，__wake_up函数唤醒所有传递给它的在等待队列上 的进程，假如它们处于被mode所隐含的状态之一的话当从wake_up被调用时， 函数唤醒所有处于 TASK_UNINTERRUPTIBLE 或 TASK_INTERRUPTIBLE 状态 的进程；当从 wake_up_interruptible（16614 行） 被调用时， 它只唤醒处于 TASK_INTERRUPTIBLE 状态的任务26842:进程用wake_up_process （26356行）被唤醒，该函数曾在以前提到过，它将在本章 随后进行详细介绍。

现在所感兴趣的是唤醒所有进程后的结果因为__wake_up 唤醒所有队列里的进程， 而不仅仅是队列里的第一个，所以它们都要竞争信号量一一在SMP里，它们可以精确的同 时做这件事通常，获胜者将首先获得CPU这个进程将是拥有最大“goodness”的进程（回 忆一下第 7 章中 26338 行对 goodness 的讨论） 这一点意义非常重大，因为拥有更高优先 权的进程应该首先被给予继续其工作的机会这对于实时进程尤其重要这种方案的不足之处是有发生饥饿（starvation）的危险，这发生在一个进程永远不能得 到它赖以继续运行的资源时这里可能会发生饥饿现象：假如两个进程反复竞争同一个信号 量，而第一个进程总是有比第二个更高的优先权，那么第二个进程将永远不会得到 CPU 这种场景同它应该的运行方式存在一定差距——设想一个是实时进程而另一个以 20 的 niceness 运行我们可以通过只唤醒队列里第一个进程的方法来避免这种饥饿的危险，可是 那样又将意味着有时候会耽误从各个方面来说都更有资格的进程对CPU的使用以前对此没有讨论过，可是Linux的调度程序在适当的环境下也能够使得CPU的一个 进程被彻底饿死。

这不完全是一件坏事——只是一种设计决策而已——而且至少应用于通篇 内核代码的原则是一致的，这就很好还要注意的是使用前边讨论过的其它机制，饥饿现象 也同样会发生例如说，test-and-set原语就是和内核信号量一样的潜在饥饿根源无论如何，在实际中，饥饿是非常少见的——它只是一个有趣的理论案例Spinlocks这一章里最后一个重要的并行程序设计原语是自旋锁（spinlock）自旋锁的思想就是在 一个密封的循环里坚持反复尝试夺取一个资源（一把锁）直到成功为止这通常是通过在类 似test-and-set操作之上进行循环来实现的 即，旋转（spinning） 一直到获得该锁如果这听起来好像是一个二元信号量，那是因为它就是一个二元信号量自旋锁和二元 信号量唯一的概念区别就是你不必循环等待一个信号量——你可以夺取信号量，也可以在不 能立刻得到它时放弃申请因此，自旋锁原本是可以通过在信号量代码外再包裹一层循环来 实现的不过，因为自旋锁是信号量的一个受限特例，它们有更高效的实现方法自旋锁变量——其中的一位被测试和设置——总是 spinlock_t 类型（12785 行）只有 spinlock_t 的最低位被使用；如果锁可用，则它是 0，如果被取走，则它是 1。

在一个声明 里，自旋锁被初始化为值SPIN_LOCK_UNLOCKED（ 12789行）；它也可以用spin_lock_init 函数（12791行）来初始化这两者都把spinlock_t的lock成员设置成0 也就是未锁状 态注意 12795 行代码简洁地对公平性进行了考虑并最后抛弃了它——公平是饥饿的背面， 正如我们前面已经介绍过的（使得一个CPU或进程饥饿应被认为是“不公平的”）自旋锁的加锁和解锁宏建立在spin_lock_string和sping_unlock_string函数之上，所以 这一小节只对spin_lock_string和sping_unlock_string函数进行详述其它宏如果有的话只 是增加了 IRQ 加锁和解锁spin_lock_string 12805：这个宏的代码对于所有自旋锁加锁的宏都是相同的它也被用于 x86 专用的 lock_ kernel 和 unlock_kernel 版本之中（它们不在本书之列，不过其常规版本则是包括的 ——参见10174和 10182行）12807：尝试测试和设置自旋锁的最低位，这要把内存总线锁住以便对于任何其它对同一个 自旋锁的访问来说这个操作都是原子的。

12808：如果成功了，控制流程就继续向下运行；否则，spin_lock_string函数向前跳转到第 12810行（btsl把这一位的原值放入CPU的进位标志位（Carry flag），这正是这里使 用 jc 的原因）同样的技巧我们已经看到过三次了：跳转目标放在内核的单独一段 中12811：在封闭的循环里不停地检测循环锁的最低位注意btsl和testb以不同方式解释它 们第一个操作数 对于btsl,它是一个位状态（bit position），而对于testb,它是一个位屏蔽（bitmask）因此，12811行在测试spin_lock_string曾在12807行已经 试图设置（但失败了）的同一位,尽管一个使用$0而另一个使用$112813:该位被清除了，所以spin_lock_string应该再次夺取它函数调转回第12806行这个代码可以只用加上lock前缀的两条代码加以简化：1: lock ; btsl $0, %0jc 1b不过，使用这个简化版本的话，系统性能将明显受到损害，这因为每次循环重复内 存总线都要被加锁内核使用的版本虽然长一些，但是它可以使其它CPU运行的更 有效，这是由于该版本只有在它有充分理由相信能够获得锁的时候才会锁住内存总 线。

spin_unlock_string12816：并不很重要：只是重新设置了自旋锁的锁定位（lock bit）读/写自旋锁自旋锁的一个特殊情况就是读/写自旋锁这里的思想是这样的：在某些情况中，我们 想要允许某个对象有多个读者，但是当有一个写者正在写入这个对象时，则不允许它再有其 它读者或者写者遵循基于spinlock_t的自旋锁的同样模式，读/写自旋锁是用rwlock_t （12853行）来代 表的，它可以在有RW_LOCK_UNLOCKED（12858行）的声明里被初始化与rwlock_t 一起工作的最低级的宏是 read_lock、read_unlock、write_lock,以及 write_unlock,它们 在本小节中进行描述很明显，那些跟随在这些宏之后并建立在它们之上的宏，自然要在你 理解了最初的这四个宏之后在去接触正如第12860行注释中所声明的，当写锁（write lock）被占有时，rwlock_t的lock成 员是负值当既没有读者也没有写者时它为0，当只有读者而没有写者时它是正值——在这 种情况下，lock将对读者的数目进行计数read_lock12867：开始于rwlock_t的lock成员的自动递增。

这是推测性的操作 它可以被撤销12868：如果它在增量之后为负，表示某个进程占用了写锁——或者至少是某个进程正试图 得到它read_lock向前跳到第12870行（注意，在一个不同的内核段里）否则， 没有写者退出（尽管还有可能有，或者也有可能没有其它读者——这并不重要），所 以可以继续执行读锁定（read-locked）代码12870： 一个写者出现了read_lock取消第12867行增值操作的影响12871：循环等待rwlock_t的lock变为0或正值 12873：跳回到第12866行再次尝试read_unlock12878：不太复杂：只是递减该计数值write_lock12883:表示出有一个进程需要写锁：检测并设置lock的符号位并保证lock的值是负的 12884：如果符号位已经被设置，则另外有进程占有了写锁；write_lock向前跳转到第12889 行（同以前一样，那是在一个不同的内核段里）12885：没有别的进程正试图获得该写锁，可是读者仍可以退出因为符号位被设置了，读 者不能获得读锁，但是 write_lock 仍然必须等待正在退出的读者完全离开它通过 检查低端的31位中是否任何一位被设置过开始，这可以表示lock以前曾是正值。

如果没有，则lock在符号位反转之前曾是0,这意味着没有读者；因而，这对于写 者的继续工作是很安全的，所以控制流程就可以继续向下运行了不过，如果低端 31位中任何一位被设置过了，也就是说有读者了，这样write_lock就会向前跳转到 第 12888 行等到它们结束12888：该进程是仅有的写者，但是有若干读者 write_lock 会暂时清除符号位（这个宏稍 后将再次操纵它）有趣的是，对符号位进行这样的胡乱操作并不会影响读者操纵 lock的正确性考虑作为示例的下列顺序事件：1. 两个读者增加了 lock； lock用十六进制表示现在是0x000000022. 一个即将成为写者的进程设置了符号位；lock现在是0x800000023. 读者中的一个离开；lock现在是0x800000014. 写者看到剩余的位不全部是 0——仍然有读者存在这样它根本没有写锁，因 此它就清除符号位；lock现在是0x00000001这样，读和写可以任何顺序交错尝试操作而不会影响结果的正确程度 12889：循环等待计数值降到0——也就是等待所有读者退出实际上， 0除了表示所有读者 已离开之外，它还表示着没有其它进程获得了写锁。

12891：所有读者和写者都结束了操作；write_lock又从头开始，并再次获得写锁write_unlock12896：不太重要：只是重置符号位APICs 和 CPU-To-CPU 通信Intel多处理规范的核心就是高级可编程中断控制器（Advanced Programmable Interrupt Controllers——APICs）的使用CPU通过彼此发送中断来完成它们之间的通信通过给中 断附加动作（actions），不同的CPU可以在某种程度上彼此进行控制每个CPU有自己的 APIC（成为那个CPU的本地APIC）,并且还有一个I/O APIC来处理由I/O设备引起的中断 在普通的多处理器系统中，I/O APIC取代了第6章里提到的中断控制器芯片组的作用这里有几个示例性的函数来让你了解其工作方式的风格smp_send_reschedule5019：这个函数只有一行，其作用将在本章随后进行说明，它仅仅是给其ID以参数形式 给出了的目标CPU发送一个中断函数用CPU ID和RESCHEDULE_VECTOR向 量调用 send_IPI_single 函数（4937 行）RESCHEDULE_VECTOR与其它 CPU 中 断向量是一起在第1723行开始的一个定义块中被定义的。

send_IPI_single4937： send_IPI_single 函数发送一个 IPI 那是 Intel 对处理器间中断（interprocessorinterrupt）的称呼 给指定的目的CPU在这一行，内核以相当低级的方式与发送CPU的本地APIC对话4949：得到中断命令寄存器（ICR）高半段的内容——本地APIC就是通过这个寄存器进行 编程的一一不过它的目的信息段要被设置为dest尽管__prepare_ICR2（4885行） 里使用了 “2” CPU实际上只有一个ICR而不是两个但是它是一个64位寄存器, 内核更愿意把它看作是两个32位寄存器一一在内核代码里，“ICR”表示这个寄存 器的低端32位，所以“ICR2”就表示高端32位我们想要设置的的目的信息段就 在高端32位，即ICR2里4950：把修改过的信息写回ICR现在ICR知道了目的CPU4953：调用_prepare_ICR （4874行）来设置我们想要发送给目的CPU的中断向量注 意没有什么措施能够保证目的CPU不是当前CPU——ICR完全能够发送一个IPI给 它自己的CPU尽管这样，我还是没有找到有任何理由要这样做。

4957:通过往ICR里写入新的配置来发送中断SMP 支持如何影响内核既然读者已经学习了能够成功支持SMP的若干原语，那么就让我们来纵览一下内核的 SMP支持吧本章剩余的部分将局限于对分布在内核之中的那些具有代表性的SMP代码进 行讨论对调度的影响schedule （26686行）正是内核的调度函数，它已在第7章中全面地介绍过了schedule 的SMP版本与UP的相比有两个主要区别：. 在schedule里从第26780开始的一段代码要计算某些其它地方所需的信息• 在SMP和UP上都要发生的对_schedule_tail的调用（26638行）实际上在UP上 并无作用，因为_schedule_tail完全是为SMP所写的代码，所以从实用的角度来 说它就是SMP所特有的schedule26784：获取当前时间，也就是自从机器开机后时钟流逝的周期数这很像是检查 jiffies， 不过是以CPU周期而不是以时钟滴答作为计时方法的一一显然，这要精确得多26785：计算自从 schedule 上一次在此 CPU 上进行调度后过去了多长时间，并且为下一次 的计算而记录下当前周期计数schedule_data是每个CPU aligned_data数组的一 部分，它在 26628 行定义。

26790：进程的avg_slice成员（16342行）记录该进程在其生命周期里占有CPU的平均时间 可是这并不是简单的平均一一它是加权平均，进程近期的活动远比很久以前的活动 权值大因为真实计算机的计算是有穷的，“很久以前”的部分在足够远以后，将 逐渐趋近于 0这将在 reschedule_idle 中（26221 行，下文讨论）被用来决定是否 把进程调入另一个CPU中因此，在UP的情况下它是无需而且也不会被计算的26797：记录哪一个CPU将运行next （它将在当前的CPU上被执行），并引发它的has_cpu 标志位26803：如果上下文环境发生了切换， schedule 记录失去 CPU 的进程——这将在下文的 __schedule_tail 中被使用到schedule_tail26654：如果失去CPU的任务已经改变了状态（这一点在前边的注释里解释过了），它将被 标记以便今后的重新调度26664：因为内核已经调度出了这个进程,它就不再拥有CPU 了一一这样的事实也将被记录reschedule_idle26221：当已经不在运行队列里的进程被唤醒时，wake_up_process将调用reschedule_idle, 进程是作为p而被传递进reschedule_idle中的。

这个函数试图把新近唤醒的进程在 一个不同的CPU上进行调度——即一个空闲的CPU上26225：这个函数的第一部分在SMP和UP场合中都是适用的它将使高优先级的进程得到 占用CPU的机会，同时它也会为那些处于饥饿状态的进程争取同样的机会如果该 进程是实时的或者它的动态优先级确实比当前占有 CPU 进程的动态优先级要高某 个量级（强制选定的），该进程就会被标记为重新调度以便它能够争取占用CPU26263：现在来到SMP部分，它仅仅适用于在上述测试中失败了的那些进程一一虽然这种现 象经常发生reschedule_idle必须确定是否要在另一个CPU上尝试运行该进程正如在对schedule的讨论中所提到的那样，一个进程的avg_slice成员是它对CPU 使用的加权平均值;因此，它说明了假如该进程继续运行的话是否它可能要控制CPU 一段相对来说较长的时间26264:这个if条件判断的第二个子句使用related宏（就在本函数之上的第26218行）来 测试是否CPU都在控制着一一或想要控制一一内核锁如果是这样，那么不管它们 生存于何处，都将不大可能同时运行，这样把进程发送到另一个CPU上将不会全面 提高并行的效能。

因此，假如这条子句或者前一条子句被满足，函数将不会考虑使 进程在另一 CPU上进行调度并简单的返回26267：否则，reschedule_idle_slow （接下来讨论）被调用以决定是否进程应当被删除reschedule_idle_slow26157：正如注释中所说明的，reschedule_idle_slow试图找出一个空闲CPU来贮存p这个 算法是基于如下观察结果的，即task数组的前n项是系统的空闲进程，机器的n个 CPU中每个都对应一个这样的空闲进程这些空闲进程当（且仅当）对应CPU上 没有其它进程需要处理器时才会运行如果可能，函数通常是用hlt指令使CPU进 入低功耗的“睡眠”状态因此，如果有空闲CPU存在的话，对任务数组的前n个进程进行循环是找出一个空 闲 CPU 所必须的 reschedule_idle_slow 函数只需简单的查询每个空闲进程是否此 刻正在运行着；如果是这样，它所在的CPU就一定是空闲的，这就为进程p提供了 一个很好的候选地点来运行当然，这个被选中的明显空闲的CPU完全有可能只是暂时空闲而且必定会被一堆拥 有更高优先级的，CPU绑定的进程所充满，这些进程可能在一纳秒后就会被唤醒并 在该CPU上运行。

所以，这并不是完美的解决方法，可是从统计的角度来说它已经相当好了 要记住，像这样的选择是很符合调度程序“快餐店式（q uick-and-dirty）”的处理方式的26180：建立本地变量best_cpu是此时正在运行的CPU；它是“最佳”的CPU，因为p 在其上会避免缓冲区溢出或其它的开销麻烦this_cpu是运行reschedule_idle_slow 的 CPU26182： idle和tsk将沿task数组进行遍历，target_tsk将是所找到的最后一个正在运行的空 闲进程（或者假如没有空闲进程它就为 NULL）26183： i从smp_num_cpus （前边被叫作n）开始并且在每一次循环后都递减26189：假如这个空闲进程的has_cpu标志被设置，它就正在它的CPU上运行着（我们将称 这样的CPU为“目标（target）CPU”）如果该标志没有被设置，那么目标CPU就 正被某个其它进程占用着；因而，它也就不是空闲的，这样reschedule_idle_slow将 不会把p发送到那里刚刚提及问题的反面在这里出现了：现在仅因为CPU不空闲 并不能表示它所有的进程都不会死亡而使其空闲下来。

可是reschedule_idle_slow无 法知道这种情形，所以它最好还是假定目标CPU将要被占用一段时间无论如何， 这都是可能的，就算并非如此,某个其它的进程也将很快会被调度到另一个空闲CPU 上运行26190：不过假如CPU目标就是当前CPU，它就会被跳过这看来很怪，不过无论怎样这 都是“不可能发生”的情况：一个空闲进程的counter是负值，在第26226行的测 试将早已阻止这个函数执行到这一步了26192:找到一个可用的空闲CPU；相关的空闲进程被保存在target_tsk中既然已找到了空闲CPU，为什么现在不中断循环呢？这是因为继续循环可能会发现 p当前所在的处理器也是空闲的，在两个CPU都空闲时，维持在当前处理器上运行 要比把它送往另一个好一些26193：这一步 reschedule_idle_slow 检查是否 p 所在的处理器空闲如果刚才找到的空闲 CPU就是p所在的，函数将向前跳转到send标记处（26203行）来在那个CPU上 对p进行调度26199:函数已经转向另一个CPU ；它要递减26204：如果循环遍历了所有空闲的CPU,该CPU的空闲任务就被标记为重新调。