第11章 核心机制


本章描述了 Linux 核心的一些基本任务和机制, 有了它们, 核心中的其他部份才能够在 一起有效地运转. 11.1 Bottom Half Handling (任务的延迟处理)
图 11.1 :Bottom Half Handling 数据结构
核心中经常会遇到一些需要推迟处理的工作。 中断处理的过程就是一个很好的例子。 当中断发生时, 处理器停下正在做的工作, 操作系统把中断事件通知给相应的设备驱动 程序。 设备驱动程序不应当用过多的时间处理这个中断, 因为这时系统的其他部份全部 停了下来。 通常总是有一部份工作不必非要现在就做完, 晚一点处理也行, (从而让系 统的其他部份能够早点恢复运行)。 Linux 中设计了 bottom half handlers 使设备驱动程序和 核心的其他部份能够排队处理延迟的工作。 图11.1中给出了同 bottom half handling 有关的 核心数据结构。 核心中最多可以有32个不同的 bottom half handler, bh_base 是一个指针向量, 这些指 针就指向核心的各个 bottom half haldling 过程。 bh_active 和 bh_mask 中的 bit 位指示了系 统中安装的 handler 和正在进行处理的 handler。 如果 bh_mask 的第 N bit 位是1, 那么 bh_base 向量中的第N个指针份量就指向一个 bottom half 处理过程。 如果bh_active的第N bit 位是1, 那么核心中的调度程序就会在适当的时候调用这个 handler。 Handler 的顺序 是静态定义的: timer bottom half haldler 优先级最高, console bottom half handler 其次, ... 通常 bottom half handling 过程具有自己的 task 列表。 例如, immediate bottom half handler 就用 immediate tasks queue (tq_immediate) 来排队需要及时处理的 task。 核心中有些 bottom half handler 是设备专用的, 下面一些则是通用的: TIMER (定时器) 这个 handler 每当系统的时钟中断发生时就激活, 系统用这个 handler 来驱动核心的 timer 队列. CONSOLE (控制台) 这个 handler 处理控制台消息。 TQUEUE 这个 handler 处理 tty 消息。 NET 这个 handler 负责网络方面的处理工作。 IMMEDIATE 这是一个通用的 handler, 一些设备驱动程序用它来排队需要推迟处理的工作。 当设备驱动程序或者核心的其他部份需要安排推迟完成的工作时, 就把工作加到系统 队列去, 比如 timer队列, 然后通知核心有 bottom half handling 需要完成, 方法就是设置 bh_active 的相应的 bit 位。 如果驱动程序把工作加入了 immediate 队列并要求 immedia bottom half handler 来处理它, 就会设置 bh_active 的第8 bit位。 在每次系统调用结束,返 回调用进程之前, 核心就要检查 bh_active , 如果有某个 bit 位被设置了, 相应的 handler 就会被调用。 检查的顺序是先第0 bit, 最后是第31 bit。 当某个 handler 被调用了之后, bh_active 中的相应 bit 就被清除。 所以 bh_active 的值 只在瞬间有效。 它只在对调度器的调用之间有意义, 是为了避免无谓地调用这些 handling 例程。 11.2 Task Queues (任务队列)
图 11.2: 一个任务队列
核心中使用任务队列管理推迟的工作。 Linux 有一个通用的机制来对工作排队, 以便 以后处理。 任务队列经常和 bottom half handler 一起使用。 例如: 当 timer queue buttom half handler 运行时, 它要处理 timer 任务队列, 提供定时器服务。 任务队列是一个简单的数 据结构, 请参看图 11.2, 它包括一个 tq_struct 数据结构的单链表, tq_struct 包括一个例 程的地址以及一个指针指向一些数据。 当这个任务队列被处理的时候, 每个 tq_struct 单元中的例程就会被调用, 参数则是那 个指针。 核心的各个部份, 例如设备驱动程序, 都能创建并使用任务队列。 核心自己创建和管 理着下面3个队列: 1。 timer (定时器) 这个队列中的工作在下一次系统时钟中断发生时就会被处理。 每当时钟滴答一次, 就检查一下这个队列是不是有工作要处理, 如果有, timer queue bottom half handler 就被 标记为 active. 当调度器下次被调用的时候, 就会调用 timer queue bottom half handler。 不 要把这个队列和系统定时器混淆起来, 那是一个复杂得多的机制。 2。 immediate (尽快) 这个队列也会被调度器处理。 但是它的优先级没有定时器队列那么高。 3。 scheduler (调度器) 这个任务队列由调度器直接处理。 这是被用来支持系统中的其他任务队列的。 也就 是说, 它的任务是一个个处理任务队列的例程, 例如, 设备驱动程序的任务队列的处理 就会被添加到这里。 处理任务队列的时候, 队列中指向第一个节点的指针被删除, 代之以一个空指针。 实 际上, 这个操作不可中断, 是个 "原子" 操作。 然后队列中的每个节点的处理例程都会被 依次调用。 队列中的节点通常是静态分配的数据。 但是没有一个统一的机制来时方所分 配的内存。 负责处理任务列表的例程在调用完节点的处理例程之后, 就简单地移向下一 个节点。 那个任务自己应该担负起释放核心内存的责任。 11.3 Timers (定时器)
图 11.3: 系统定时器
操作系统经常需要能把一项活动安排在将来某个时间进行。 需要有一种机制保证能够 把任务安排到一个相对比较精确的时间进行处理。 任何能够支持操作系统的微处理器必 定有一个可编程的间隔定时器, 能够周期性地中断处理器。 这个周期性的中断就是系统 时钟的滴答。 如果把系统比作一个交响乐队, 它就像一个节拍器, Linux 对于时间的理 解很简单: 它从系统启动开始记录系统时钟的滴答数目, 以此衡量时间。 系统中用到时 间的地方都以此为衡量的基础, 这就是所说的 jiffy 单位的由来。 核心中有一个全局变量 叫 jiffies, 就是这个记录的值。 Linux 中有两种系统定时器, 都能把事务排队等到某个系统时间来处理。 但是这两者 的实现稍有不同。 图 11.3 中对比了这两种机制。 第一种是老式的定时器机制, 有一个静态的数组, 包含32个 timer_struct 数据结构以及 一个用屏蔽位指示活动定时器的整数: timer_active 。 由于定时器列表中的定时器是静态定义的, (就像 bottom half handler 表中的 bh_base), 表中的表项一般都是在系统初始化的时候加入的。 第二种新机制使用了 time_list 数据结构的链表把定时器按到达时间的早晚从早到晚链接 起来。 两种机制都使用了 jiffy 作为时间单位。 因此, 一个5秒的定时器要把5秒转换为 jiffy 单 位, 然后和当前系统时间相加, 以此设置定时器。 每当系统时钟滴答一次, timer bottom half handler 就被标记为 active, 这样当调度器被运行时, 就会处理定时器队列。 timer bottom half handler 对两种系统定时器都要处理。 对于老式的系统定时器, 要检查 timer_active 屏蔽位找出设定了相应位的定时器, 如 果某个定时器设定的时间已到(它设定的时间小于当前系统时间), 它的定时器例程就会被 调用。 并且对应的屏蔽位会被清除。 对于新式的系统定时器, 则检查 timer_list 链表中的 节点, 每个到期的定时器会被从链表中清除, 并且节点中的定时器例程会被调用。 新机 制的好处是在调用定时器例程的时候能够传递一个参数。 (当然新机制的显而易见的好处 是不限制定时器的数目, 这是老式的机制不能做到的, 译者注)。 11.4 Wait Queues (等待队列) 进程经常需要等待系统资源。 例如, 进程可能需要一个目录的 VFS i节点而这个节点 可能不在文件系统的高速缓冲区中。 这时, 进程就必须等待系统从包含这个 i节点的物理 介质上面得到这个节点的内容才能继续运行。
wait_queue

*task

*next

图 11.4: 等待队列
Linux 核心使用了一个很简单的数据结构, 叫做等待队列(见 图 11.4), 它包含一个指向 进程的 task_struct 结构的指针, 还有一个指向队列中下一个节点的指针。 被加进这个队列的进程既有不可中断的(uninterruptible)有又可以中断(interruptible)的(进 程的状态中有 UNINTERRUPTIBLE 和 INTERRUPTIBLE 来标志). 可中断的进程可能会被事 件打断, 比如它的定时器到时了, 或者有信号发送给这个进程。 因为现在这个进程不能 继续运行, 调度器会运行, 当它选择了新的进程运行时, 这个等待的进程就被暂停了。 在处理等待队列的时候, 队列中的每个进程的状态都被设置为 RUNNING (运行态)。 如 果这个进程已经被移出了运行队列(run queue), 它又会被放回去。 当调度器下次运行时, 等待队列中的进程就又有机会被选中运行了, 因为它们已经不再等待什么了。 当处于等 待队列中的进程被调度运行时, 它做的第一件事就是把自己从等待队列中移出。 等待队 列可以被用于同步对系统资源的访问, 在 Linux 系统中用于实现 semaphore (信号量, 下 面会讲到)。 11.5 Buzz Locks (Buzz 锁) 更多的叫法是转锁(spin lock)。 它是保护数据结构或者一段代码的最基本的方法。 它一 次只允许一个进程处于危险(可能产生冲突)的代码区域(临界区)。 在 Linux 中, Buzz 锁被 用于限制对数据结构中的域的访问。 使用一个整数作为锁, 初始值为1。 每个想进入临 界区的进程试图把锁的值从0改变为1。 如果当前的值就是1, 进程就会再试一次。 通过 一个紧致的循环反复尝试。 对保存锁的值的内存区域的访问必须是原子化的, 读取当前 数值, 检查是不是0以及把它改为1这些操作必须一次完成, 不能被别的进程中断。 大多 数 CPU 提供了特殊的指令来实现这一点, 但是也能够使用不缓冲的主存来实现 buzz 锁。 当拥有这个锁的进程离开临界区之后, 它需要释放锁, 把锁的值改为0。 其它正在转 这把锁的进程现在就会读出0。 第一个来读的进程将会再把它改为1并进入临界区。 11.6 Semaphores (信号量) 信号量被用于保护代码的临界区或数据结构。 请注意每次对临界数据的访问, 例如访 问一个目录的 VFS i节点, 是由核心代码代表用户进程进行的。 允许一个进程能够改变 改变另一个进程的也在使用的临界数据结构是非常危险的。 一种办法是使用 buzz 锁来防 止冲突, 但是这种最简单的方法性能很差。 Linux 系统中使用信号量来做保护: 只有得 到信号量保护的资源的那个进程能够访问临界区, 而其它等待资源的进程被暂停。 Linux 中的信号量数据结构包含下列信息: count (计数) 这里记录需要使用资源的进程的数目。 一个正的数值表明这个资源现在可用。 一个 负的数值和0表明现在有进程在等待这个资源。 如果初始数值为1, 那么同一个时刻只能 有一个进程能够使用这个资源。 如果进程需要使用这个资源, 就把计数值减1, 使用完 资源之后再把这个值加1。 waking (唤醒) 这是正在等待资源的进程的数目。 当资源被释放的时候, 就有这么多进程等待被唤 醒。 wait queue (等待队列) 当进程等待这个资源的时候, 它们被放在这个等待队列里面。 lock 一个 buzz 锁用来保护对 waking 域的访问。 假设信号量的初始值是1, 第一个来访的进程看到数值1, 并把它减1 变为0。 这个进 程就"拥有"了被信号量锁保护的资源。 当进程不再需要使用资源之后, 就把信号量的计 数加1。 最理想的情况就是没有其它的进程竞争这个资源。 Linux 对信号量的实现在这种 最常见的情况下效率很高。 当另一个进程也想同时访问临界区的时候, 它也要把计数减1。 因为现在计数为 -1, 所以这个进程不能进入临界区。 Linux 让这个等待的进程睡眠(进入等待状态)。 直到拥有 资源的进程释放资源的时候来唤醒它。 等待的进程把自己添加到信号量的等待队列上, 然后进入循环, 检查 waking 域的值并调用调度器直到 waking 域的值不为0。 拥有资源的进程在释放资源的时候, 增加信号量的计数, 并检查, 在理想情况下, 计数被恢复为1, 没有什么事情要做; 如果不大于0, 说明还有进程在等待这个资源。 这时, 就增加 waking 域的值, 并唤醒一个在信号量的等待队列里的进程。 当这个等待 的进程被唤醒的时候, waking 现在是1, 它就知道自己现在拥有这个资源, 可以进入临 界区了。 它就减少 waking 的值, 然后继续运行。 对 waking 域的访问要通过一个 buzz 锁 来保护, 这个锁使用信号量的 lock 域作为自己的值。