Chapter 11
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 。任何在这个锁上循环的进程现在会读到 0 ，第一个做到的进程会把它增加到 1 并进入这个重要区域。

11.6 Semaphores （信号灯）

    信号灯用于保护重要的代码区域或数据结构。记住，对于重要数据结构例如描述一个目录的 VFS inode 的每一次访问都是通过核心为进程执行的。如果允许一个进程改变另一个进程使用的重要的数据结构是非常危险的。实现的方法之一是在要访问的重要的代码片上使用一个 buzz lock ，虽然这是最简单的方法但是不会有太好的系统性能。 Linux 使用信号灯实现一次只允许一个进程访问重要的代码和数据区域：所有其它希望访问这个资源的进程会被迫等待直到信号灯空闲。等待的进程被刮起，系统中的其它进程和平时一样正常运行。

一个 Linux 信号灯数据结构包括以下信息：

参见 include/asm/semaphore.h

    count 这个字段记录了希望使用这个资源的进程数。正的数值表示这个资源可用。负值或 0 表示有进程在等待。起始值 1 表示同一时间有一个且只有一个进程可以使用这个资源。当进程希望使用这个资源的时候它们减小这个 count ，当结束对这个资源的使用的时候，它们增加这个 count

waking 等待这个资源的进程数，这也是等待当资源空闲的时候被唤醒的进程数。

Wait queue 当进程等待这个资源的时候它们被放到这个等待队列

Lock 当访问 waking 域所用的 buzz lock

    假设信号灯的起始值是 1 ，第一个到来的进程会看到 count 是正的，把它减少 1 ，成为 0 。这个进程现在“拥有”这个受到信号灯保护的重要的代码片或资源。当进程离开这个重要区域的时候它增加信号灯的 count 。最理想的情况是没有其它进程竞争这个重要区域的所有权。 Linux 实现的信号灯在这种最常见的情况下工作的非常高效。

    如果另一个进程希望进入这个重要区域，而它已经被一个进程拥有，它也会减少这个 count 。因为这个 count 现在是 -1 ，这个进程不能进入这个重要区域。它必须等待直到拥有的进程退出来。 Linux 让等待的进程睡眠直到拥有权的进程退出这个重要区域把它唤醒。等待进程把它自己加到信号灯的等待队列中，并循环检查 waking 字段的值，调用调度程序直到 waking 非 0 。

    这个重要区域的属主增加信号灯的 count ，如果它小于或等于 0 ，那么还有进程在睡眠，等待这个资源。理想情况下，信号灯的 count 会返回到它的起始值 1 ，这样就不需要做什么工作。所有权的进程增加 waking 计数器并唤醒在信号灯等待队列中睡眠的进程。当等待的进程被唤醒之后， waking 计数器现在是 1 ，它知道它现在可以进入这个重要区域。它减少 waking 计数器，把它返回 0 并继续。所有对于这个信号灯的 waking 字段的访问都用信号灯的 lock 这个 buzz lock 来保护。