第十一章 核心机制
本章主要描叙Linux核心为使核心其他部分能有效工作而提供的几个常用任务与机制。
11.1 底层部分处理机制
某些特殊时刻我们并不愿意在核心中执行一些操作。例如中断处理过程中。
当中断发生时处理器将停止当前的工作,操作系统将中断发送到相应的设备驱
动上去。由于此时系统中其他程序都不能运行,所以设备驱动中的中断处理过程
不宜过长。有些任务最好稍后执行。Linux底层部分处理机制可以让设备驱动和
Linux核心其他部分将这些工作进行排序以延迟执行。图11.1给出了一个与底层
部分处理相关的核心数据结构。
系统中最多可以有32个不同的底层处理过程；bh_base是指向这些过程入口的指
针数组。而bh_active和bh_mask用来表示那些处理过程已经安装以及那些处于
活动状态。如果bh_mask的第N位置位则表示bh_base的第N个元素包含底层部分
处理例程。如果bh_active的第N位置位则表示第N个底层处理过程例程可在调度
器认为合适的时刻调用。这些索引被定义成静态的；定时器底层部分处理例程
具有最高优先级（索引值为0），控制台底层部分处理例程其次（索引值为1）。
典型的底层部分处理例程包含与之相连的任务链表。例如immediate底层部分处
理例程通过那些需要被立刻执行的任务的立即任务队列（tq_immediate）来执行。
有些核心底层部分处理过程是设备相关的，但有些更加具有通用性：
TIMER
每次系统的周期性时钟中断发生时此过程被标记为活动，它被用来驱动核
心的定时器队列机制。
CONSOLE
此过程被用来处理进程控制台消息。
TQUEUE
此过程被用来处理进程tty消息。
NET 此过程被用来做通用网络处理。
IMMEDIATE
这是被几个设备驱动用来将任务排队成稍后执行的通用过程。
当设备驱动或者核心中其他部分需要调度某些工作延迟完成时，它们将把这些任
务加入到相应的系统队列中去，如定时器队列，然后对核心发出信号通知它需要
调用某个底层处理过程。具体方式是设置bh_active中的某些位。如果设备驱动将
某个任务加入到了immediate队列并希望底层处理过程运行和处理它,可将第8位置1。
每次系统调用结束返回调用进程前都要检查bh_active。如果有位被置1则调用处于
活动状态的底层处理过程。检查的顺序是从0位开始直到第31位。
每次调用底层处理过程时bh_active中的对应位将被清除。bh_active是一个瞬态
变量，它仅仅在调用调度管理器时有意义；同时它还可以在空闲状态时避免对底
层处理过程的调用。
11.2 任务队列
任务队列是核心延迟任务启动的主要手段。 Linux
提供了对队列上任务排队以及处理它们的通用机制。
任务队列通常和底层处理过程一起使用；底层的定时器队列处理过程运行时对
定时器队列进行处理。任务队列的结构很简单，它由一个tq_struct结构链表构
成，每个节点中包含处理过程的地址指针以及指向数据的指针。
处理任务队列上元素时将用到这些过程，同时此过程还将用到指向这些数据的指针。
核心的所有部分，如设备驱动,
都可以创建与使用任务队列。但是核心自己创建与管理的任务队列只有以下三个:
timer
此队列用来对下一个时钟滴答时要求尽快运行的任务进行排队。每个时钟滴
答时都要检查此队列看是否为空，如果不为空则定时器底层处理过程将激活
此任务。当调度管理器下次运行时定时器队列底层处理过程将和其他底层处
理过程一道对任务队列进行处理。这个队列不能和系统定时器相混淆。
immediate
immediate
底层处理过程的优先级低于定时器底层处理过程，所以此类型任务将延迟运行。
scheduler
此任务队列直接由调度管理器来处理。它被用来支撑系统中其他任务队列，
此时可以运行的任务是一个处理任务队列的过程，如设备驱动。
当处理任务队列时，处于队列头部的元素将从队列中删除同时以空指针代替它。这
个删除操作是一个不可中断的原子操作。队列中每个元素的处理过程将被依次调用。
这个队列中的元素通常使用静态分配数据。然而并没有一个固有机制来丢弃已分配
内存。任务队列处理例程简单的指向链表中下一个元素。这个任务才真正清除任何
已分配的核心内存。
11.3 定时器（TIMER）
操作系统应该能够在将来某个时刻准时调度某个任务。所以需要一种能保证任务较
准时调度运行的机制。希望支持每种操作系统的微处理器必须包含一个可周期性中
断它的可编程间隔定时器。这个周期性中断被称为系统时钟滴答，它象节拍器一样
来组织系统任务。
Linux的时钟观念很简单：它表示系统启动后的以时钟滴答记数的时间。所有的系统
时钟都基于这种量度，在系统中的名称和一个全局变量相同-jiffies。
Linux包含两种类型的系统定时器，它们都可以在某个系统时间上被队列例程使用，
但是它们的实现稍有区别。
第一个是老的定时器机制，它包含指向timer_struct结构的32位指针的静态数组以
及当前活动定时器的屏蔽码：time_active。
此定时器表中的位置是静态定义的（类似底层部分处理表bh_base）。其入口在系
统初始化时被加入到表中。第二种是相对较新的定时器，它使用一个到期时间以升
序排列的timer_list结构链表。
这两种方法都使用jiffies作为终结时间，这样希望运行5秒的定时器将不得不将5秒
时间转换成jiffies的单位并且将它和以jiffies记数的当前系统时间相加从而得到
定时器的终结时间。在每个系统时钟滴答时,定时器的底层部分处理过程被标记成活
动状态以便调度管理器下次运行时能进行定时器队列的处理。定时器底层部分处理
过程包含两种类型的系统定时器。老的系统定时器将检查timer_active位是否置位。
如果活动定时器已经到期则其定时器例程将被调用同时它的活动位也被清除。新定
时器位于timer_list结构链表中的入口也将受到检查。每个过期定时器将从链表中
清除,同时它的例程将被调用。新定时器机制的优点之一是能传递一个参数给定时器
例程。
11.4 等待队列
进程经常要等待某个系统资源。例如某个进程可能需要描叙文件系统中某个目录的VFS
inode但是此inode可 能不在buffercache中。此时这个进程必须等到该inode从包含此
文件系统的物理介质中取出来才可以继续运行。
wait_queue
*task
*next
等待队列
Linux核心使用一个非常简单的队列：等待队列（见图11.4）。它包含一个指向进程
task_struct结构的指针以及等待队列中下一个元素的指针。加入到等待队列中的进程
既可以是可中断也可以是不可中断的。可中断进程能够被如定时器到期或者信号等时间
中断。此等待进程的状态必须说明成是INTERRUPTIBLE还是UNINTERRUPTIBLE。由于进程
现在不能继续运行则调度管理器将接过系统控制权并选择一个新进程运行而等待进程将
被挂起。处理等待进程时，每个处于等待队列中的进程都被置为RUNNING状态。如果此
进程已经从运行队列中删除则它将被重新放入运行队列。下次调度管理器运行时,由于
这些进程不再等待所以它们都将是运行候选者。等待队列可以用来同步对系统资源的访问,
同时它们还被Linux用于信号灯的实现中。
11.5 Buzz 锁
它使用更频繁的名字叫自旋锁。这是一种保护数据结构或代码片段的原始方式。在某个
时刻只允许一个进程访问临界区内的代码。Linux还同时将一个整数域作为锁来限制对数
据结构中某些域的存取。每个希望进入此区域的进程都试图将此锁的初始值从0改成1。
如果当前值是1则进程将再次尝试，此时进程好象在一段紧循环代码中自旋。对包含此
锁的内存区域的存取必须是原子性的，即检验值是否为0并将其改变成1的过程不能被任
何进程中断。多数CPU结构通过特殊指令提供对此方式的支持，同时我们可以在一个非缓
冲主存中实现这个流言锁。
当控制进程离开临界区时它将递减此Buzz锁。任何处于自旋状态的进程都可以读取它，
它们中最快的那个将递增此值并进入临界区。
11.6 信号灯
信号灯被用来保护临界区中的代码和数据。请记住每次对临界区数据,如描叙某个目录
VFS inode的访问,是通过代表进程的核心代码来进行的。允许某个进程擅自修改由其他
进程使用的临界区数据是非常危险的。防止此问题发生的一种方式是在被存取临界区
周围使用buzz锁，但这种简单的方式将降低系统性能。Linux使用信号灯来迫使某个时
刻只有唯一进程访问临界区代码和数据，其他进程都必须等待资源被释放才可使用。这
些等待进程将被挂起而系统中其他进程可以继续运行。
一个Linux semaphore结构包含了以下信息：
count
此域用来保存希望访问此资源的文件个数。当它为正数时表示资源可用。负数和0
表示进程必须等待。当它初始值为1时表示一次仅允许一个进程来访问此资源。当
进程需要此资源时它们必须将此count值减1并且在使用完后将其加1。
waking
这是等待此资源的进程个数，同时也是当资源可利用时等待被唤醒的进程个数。
wait queue
当进程等待此资源时，它们被放入此等待队列。
lock 访问waking域时使用的buzz锁。
假设此信号灯的初始值为1，第一个使用它的进程看到此记数为正数，然后它将其减去1
而得到0。现在此进程拥有了这些被信号灯保护的段代码和资源。当此进程离开临界区
时它将增加此信号灯的记数值，最好的情况是没有其他进程与之争夺临界区的控制权。
Linux将信号灯设计成能在多数情况下有效工作。
如果此时另外一个进程希望进入此已被别的进程占据的临界区时，它也将此记数减1。
当它看到此记数值为-1则它知道现在不能进入临界区,必须等待到此进程退出使用临界
区为止。在这个过程中Linux将让这个等待进程睡眠。等待进程将其自身添加到信号灯
的等待队列中然后系统在一个循环中检验waking域的值并当waking非0时调用调度管理器。
临界区的所有者将信号灯记数值加1，但是如果此值仍然小于等于0则表示还有等待此
资源的进程在睡眠。在理想情况下此信号灯的记数将返回到初始值1而无需做其他工作。
所有者进程将递增waking记数并唤醒在此信号灯等待队列上睡眠的进程。当等待进程醒
来时，它发现waking记数值已为1，那么它知道现在可以进入临界区了。然后它将递减
waking记数，将其变成0并继续。所有对信号灯waking域的访问都将受到使用信号灯的
buzz锁的保护。
