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来保护。
发布人:netbull 来自:非常Linux