Kernel Mechanisms （核心机制）
本章描述了 Linux 核心需要提供的一些一般的任务和机制，让核心的其余部分可以有效地工作。
11.1 Bottom Half Handling
通常在核心中会有这样的时候：你不希望执行工作。一个好例子是在中断处理的过程中。当引发了中断，处理器停止它正在执行的工作，操作系统把中断传递到适当的设备驱动程序。设备驱动程序不应该花费太多时间来处理中断，因为在这段时间，系统中的其他东西都不能运行。通常一些工作可以在稍后的时候进行。 Linux 发明了 boffom half 处理程序，这样设备驱动程序和 Linux 核心的其它部分可以把可以稍后作的工作排队。图 11.1 显示了同 bottom half 处理相关的核心数据结构。有多达 32 个不同的 bottom half 处理程序： bh_base 是一个指针的向量表，指向核心的每一个 bottom half 处理例程， bh_active 和 bh_mask 按照安装和激活了哪些处理程序设置它们的位。如果 bh_mask 的位 N 设置，则 bh_base 中的第 N 个元素会包含一个 bottom half 例程的地址。如果 bh_active 的第 N 位设置，那么一旦调度程序认为合理，就会调用第 N 位的 bottom half 处理程序。这些索引是静态定义的： timer bottom half 处理器优先级最高（索引 0 ）， console bottom half 处理程序优先级次之（ index 1 ）等等。通常 bottom half 处理例程会有和它关联的任务列表。例如这个 immediate buttom half handler 通过包含需要立即执行的任务的 immediate 任务队列（ tq_immediate ）来工作。
参见 include/linux/interrupt.h
核心的一些 bottom half 处理程序和设备有关，但是其它的是更一般的：
TIMER 这个处理程序在每一次系统定时时钟中断被标记成为激活，用来驱动核心的时钟队列机制
CONSOLE 这个处理程序用来处理控制台消息
TQUEUE 这个处理程序用来处理 TTY 消息
NET 这个处理程序用来处理通用的网络处理
IMMEDIATE 通用的处理程序，一些设备驱动程序用来排列稍后进行的工作
设备驱动程序或者核心的其它部分，需要调度稍后进行的工作的时候，它就在适当的系统队列中增加这个工作，例如时钟队列，然后就发送信号到核心，一些 bottom half 处理需要进行。它通过设置 bh_active 中的合适的位来做到这点。如果驱动程序在 immediate 队列排列了一些东西并希望 immediate bottom half 处理程序会运行并处理它的时候就设置第 8 位。每一次系统调用的最后，把控制权返回调用程序之前都检查 bh_active 的位掩码。如果有任意位被设置，相应的激活的 bottom half 处理例程就被调用。首先检查位 0 ，然后 1 直到位 31 。调用每一个 bottom half 处理例程调用的时候就清除 bh_active 中相应的位。 Bh_active 是易变的：它只在调用调度程序之间有意义，通过设置它，当没有需要作的工作的时候可以不调用相应的 bottom half 处理程序。
Kernel/softirq.c do_bottom_half()
11.2 Task Queues （任务队列）
任务队列是核心用来把工作推迟到以后的方法。 Linux 由一个通用的机制，把工作排列在队列中并在稍后的时间进行处理。任务队列通常和 bottom half 处理程序一起使用：当 timer bottom half 处理程序运行的时候处理计时器任务队列。任务队列是一个简单的数据结构，参见图 11.2 ，包括一个 tq_struct 数据结构的单链表，每一个包括例程的指针和指向一些数据的指针。
参见 include/linux/tqueue.h 当这个任务队列的单元被处理的时候调用这个例程，数据的指针会传递给它。
核心的任何东西，例如设备驱动程序，都可以创建和使用任务队列，但是有三个任务队列是由核心创建和管理的：
timer 这个队列用于排列在下一个系统时钟之后尽可能运行的工作。每一个时钟周期，都检查这个队列，看是否有条目，如果有，时钟队列的 bottom half 处理程序被标记为激活。当调度在一次运行的时候，就处理这个时钟队列 bottom half 处理程序以及其它 bottom half 处理程序。不要把这个队列和系统计时器混淆，那是一个更复杂的机制
immediate 这个队列也是在调度程序处理激活的 bottom half 处理程序的时候被处理。这个 immediate bottom half 处理程序没有 timer 队列 bottom half 处理程序优先级高，所以这些任务会迟疑写运行。
Scheduler 这个任务队列由调度程序直接处理。它用于支持系统中的其它任务队列，这种情况下，要运行的任务会是一个处理任务队列（例如设备驱动程序）的例程。
当处理任务队列的时候，指向队列中的一个单元的指针从队列中删除，用一个 null 指针代替。实际上，这种删除是一个不能被中断的原子操作。然后为队列中的每一个单元顺序调用它的处理例程。队列中的单元通常是静态分配的数据。但是没有一个固有的机制来废弃分配的内存。任务队列处理例程只是简单地移到列表中的下一个单元。保证正确地清除任何分配的核心内存是任务本身的工作。
11.3 Timers
一个操作系统都需要有能力把一个活动调度到将来的一个时间，这需要一种机制让活动可以调度到相对准确的时间去运行。任何希望支持一个操作系统的微处理器都需要一个可编程间隔适中，定期中断处理器。这个定期的中断就是系统时钟周期（ system clock tick ），它就象一个节拍器，指挥系统的活动。 Linux 用非常简单的方式看待时间：它从系统启动的时候开始用时钟周期测量时间。任何系统时间都基于这种量度，叫做 jiffers ，和全局变量同名。
Linux 有两种类型的系统计时器，每一种都排列例程，在特定的系统时间调用，但是实现的方式上它们有轻微的不同。图 11.3 显示了两种机制。第一种，旧的计时器机制，有一个静态的数组，有 32 个指向 timer_struct 数据结构的指针和一个激活的时钟的掩码， timer_active 。计时器放在这个计时器表中的什么位置是静态定义的（和 bottom half 处理程序中的 bh_base 不同）。条目在系统初始化的时候被加到这个表中。第二种机制，使用一个 timer_list 数据结构的链接表中，按照过期时间的数据排列。
参见 include/linux/timer.h
每一种方法都使用 jiffies 中的时间作为过期时间，这样一个希望运行 5 秒的计时器会有一个可以换算为 5 秒的 jiffies 单元加上当前系统时间得到计时器过期时的系统时间（以 jiffies 为单位）。每一次系统时钟周期， timer bottom half 处理程序被标记为激活，所以当下一次调度程序运行的时候，会处理计时器队列。 Timer bottom half 处理程序会处理全部两种类型的系统计时器。对于旧的系统计时器，检查 timer_active 位掩码中置了位的。如果一个激活的计时器过期（过期时间小于当前的系统 jiffies ），就调用它的计时器例程，并清除它的激活位。对于新的系统计时器，检查 timer_list 数据结构的链接表中的条目。每一个过期的计时器从这个列表中删除并调用它的例程。新的计时器机制的优点在于它可以向计时器例程传递参数。
参见 kernel/sched.c timer_bh() run_old_timers() run_timer_list()
11 ． 4 Wait Queues （等待队列）
许多时候一个进程必须等待一个系统资源。例如，一个进程可能需要描述文件系统中一个目录的 VFS inode ，但是这个 inode 可能不在 buffer cache 钟。这时，系统必须等待这个 inode 从包含这个文件系统的物理介质中取出来，然后才能继续。
Linux 核心使用一个简单的数据结构，一个等待队列（见图 11.4 ），包含一个指向进程的 task_struct 的指针和一个指向等待队列中下一个元素的指针。
参见 include/linux/wait.h
当进程被增加到了一个等待队列的结尾的时候，它们可能时可被中断或者不可中断的。可中断的进程在等待队列等待的过程中可以被事件中断，例如过期的计时器或者发送来的信号等事件。等待进程的状态会反映出来，可以是 INTERRUPTIBLE 或者 UNINTERRUPTIBLE 。因为这个进程现在不能继续运行，就开始运行调度程序，当它选择了一个新的进程运行的时候，这个等待的进程就会被挂起。
当处理等待队列的时候，等待队列中的每一个进程的状态都被设置位 RUNNING 。如果进程从运行队列中删除了，它就被放回到运行队列。下一次运行调度程序的时候，在等待队列的进程现在就成为运行的候选，因为它们不再等待了。当一个等待队列的进程被调度的时候，首先要作的是把自己从等待队列中删除。等待队列可以用于同步访问系统资源， Linux 用这种方式实现它的信号灯。
11.5 Buzz Locks
通常叫做 spin locks ，这是保护一个数据结构或代码段的一个原始方法。它们一次只允许一个进程处于一个重要的代码区域。 Linux 使用它们来限制对于数据结构中的域的访问，它利用一个整数字段作为锁。每一个希望进入这个区域的进程试图把锁的起始值从 0 变为 1 。如果当前致使 1 ，进程重新尝试，在一个紧凑的代码循环中旋转（ spin ）。对于保存这个锁的内存位置的访问必须具有原子性，读取它的值、检查它是 0 然后把它改为 1 ，这个动作不能被其他任何进程打断。多数 CPU 结构通过特殊的指令为此提供支持，但是你也可以使用未缓存的主内存实现这种 buzz lock 。
当属主进程离开这个重要的代码区域的时候，它减小这个 buzz lock ，让它的值返回到 0 。任
