Linux分析报告系统定时器队列机制及相关的定时器操作

1、Linux 分析报告系统定时器队列机制及相关的定时器操作目录第一章 硬件基础1.1 时钟1.2 中断处理1.2.1可编程中断控制器1.2.2中断处理1.2.3实时时钟(RTC)中断第二章核心机制2.1bottom half 处理机制2.2系统定时器2.2.1定时器（TIMER）的原理2.2.2 定时器的系统调用机制第三章系统定时器队列机制3.1 Linux 系统管理 timer_list 结构定时器的数据模型3.1.1主要数据结构的定义(sched.c)3.1.2 tvecs：系统定时器队列的数据模型3.2 run_timer_list()分析(kernel/sched.c)3.3 inter

2、nel_add_timer(struct timer_list *timer)分析3.4 系统定时器队列的级联处理及 run_timer_list()流程3.5 小结第四章实时时间定时器的操作4.1 实时时间定时器的添加操作4.2 进程实时时间定时器的状态的获得第五章总结第一章硬件基础11时钟所有的操作系统都必须准确的得到当前时间，所以现代 PC 包含一个特殊的外设称为实时时钟(RTC)。它提供了两种服务：可靠的日期和时间以及精确的时间间隔。RTC 有其自身的电池这样即使 PC 掉电时它照样可以工作，这就是 PC总是知道正确时间和日期的原因。而时间间隔定时器使得操作系统能进行准确的调度工作。1

3、2中断处理本节主要描叙 Linux 核心的中断处理过程。尽管核心提供通用机制与接口来进行中断处理，大多数中断处理细节都是 CPU 体系结构相关的。图 1.1 级连的 8259A 控制器1.2.1 可编程中断控制器一般的 IBM PC 兼容机使用 Intel 82C59A-2 CMOS 可编程中断控制器或其派生者。图 1.1 给出了两个级连的 8 位控制器 PIC1 和 PIC2，每个控制器都有一个屏蔽与中断状态寄存器。这两个屏蔽寄存器分别位于 ISA I/O 空间 0x21 和 0xA1处，状态寄存器则位于 0x20 和 0xA0。对此屏蔽寄存器某个特定位置位将使能某一中断，写入 0 则屏蔽它

4、。当有中断产生时，中断处理代码将读取这两个中断状态寄存器（ISR）。它将 0x20 中的ISR 看成一个 16 位中断寄存器的低 8 位而将 0xA0 中的ISR 看成其高 8位。这样 0xA0 中 ISR 第 1 位上的中断将被视作系统中断 9。PIC1 上的第二位由于被用来级连 PIC2 所以不能作其它用处，PIC2 上的任何中断将导致 PIC1 的第二位被置位。1.2.2中断处理设备中断 处理过程图 1.2 Linux 中断处理数据结构Linux 核心需要将来自硬件设备的中断传递到相应的设备驱动。这个过程由设备驱动向核心注册其使用的中断来协助完成。在/proc/interrupts 文件

5、中你可以看到设备驱动所对应的中断号及类型。Linux 使用一组指针来指向包含处理系统中断的例程的调用地址。这些例程属于对应于此设备的设备驱动。设备驱动负责在设备初始化时申请其需要的中断。图 1.2 给出了一个指向一组 irqaction 的 irq_action 指针。每个 irqaction 数据结构中包含了对应于此中断处理的相关信息，包括中断处理例程的地址。而中断个数以及它们被如何处理则会根据体系结构及系统的变化而变化。Linux 中的中断处理代码就是和体系结构相关的。这也意味着 irq_action 数组的大小随于中断源的个数而变化。中断发生时Linux 首先读取系统可编程中断控制器中中

6、断状态寄存器判断出中断源，将其转换成 irq_action 数组中偏移值。例如中断控制器引脚 6 来自软盘控制器的中断将被转换成对应于中断处理过程数组中的第 7 个指针。如果此中断没有对应的中断处理过程则 Linux 核心将记录这个错误，不然它将调用对应此中断源的所有 irqaction 数据结构中的中断处理例程。当Linux 核心调用设备驱动的中断处理过程时此过程必须找出中断产生的原因以及相应的解决办法。为了找到设备驱动的中断原因，设备驱动必须读取发生中断设备上的状态寄存器。设备可能会报告一个错误或者通知请求的处理已经完成。如软盘控制器可能将报告它已经完成软盘读取磁头对某个扇区的正确定位。一

7、旦确定了中断产生的原因，设备驱动可能需要完成更多的工作。设备驱动在其中断处理过程中做得越少越好，这样 Linux 核心将能很快的处理完中断并返回中断前的状态中。为了在接收中断时完成大量工作，设备驱动必须能够使用核心的 bottom half 例程或者任务队列对以后要调用的那些例程进行排队。1.2.3 实时时钟(RTC)中断实时时钟(RTC)每隔千分之一秒(10ms)就产生一次中断。这个周期性中断被称为系统时钟滴答，它象节拍器一样来组织系统任务。实时时钟的周期性定时器被固定连接到中断控制器 PIC1 的引脚 0 上，它的中断处理例程是 timer_interrupt()arch/i386/ker

8、nel/time.c。时钟中断发生时，服务例程 timer_interrupt 马上调用 do_timer（sched.c），后者把核心的 bottom half中的 TIMER 处理过程标记为活动，使得核心的定时器队列机制能够在核心从时钟中断处理返回前（调用 bottom half 例程时）被驱动。第二章 核心机制2.2 bottom half 处理机制bottomhalf处 理过程 （定时器）图 2.1 bottom half 处理机制数据结构当中断发生时处理器将停止当前的工作, 操作系统将中断发送到相应的设备驱动上去。由于此时系统中其他程序都不能运行, 所以设备驱动中的中断处理过程不宜过

9、长。有些任务最好稍后执行。Linux 的 bottom half 处理机制可以让设备驱动和 Linux 核心其他部分将这些工作进行排序以延迟执行。图 2.1 给出了一个与 bottom half 的处理相关的核心数据结构。系统中最多可以有 32 个不同的 bottom half 处理过程；bh_base 是指向这些过程入口的指针数组。而 bh_active 和 bh_mask 用来表示那些处理过程已经安装以及那些处于活动状态。如果 bh_mask 的第 N 位置位则表示 bh_base 的 第 N 个元素包含 bottom half 处理例程。如果 bh_active 的第 N 位置位则表示第

10、 N 个 bottom half 处理例程可在调度器认为合适的时刻调用。这些索引被定义成静态的；定时器的 bottom half 处理例程具有最高优先级（索引值为 0）， 控制台 bottom half处理例程其次（索引值为 1）。典型的 bottom half 处理例程包含与之相连的任务链表。有些核心 bottom half 处理过程是设备相关的，但有些更加具有通用性：TIMER每次系统的周期性时钟中断发生时此过程被标记为活动，它被用来驱动核心的定时器队列机制。CONSOLE此过程被用来处理进程控制台消息。 TQUEUE此过程被用来处理进程 tty 消息。 NET此过程被用来做通用网络处理。

11、IMMEDIATE 这是被几个设备驱动用来将任务排队成稍后执行的通用过程。 当设备驱动或者核心中其他部分需要调度某些工作延迟完成时，它们将把这些任务加入到相应的系统任务队列中去，然后设置 bh_active 中的某些位，也就使核心获知它需要调用某个 bottom half 处理过程。如果设备驱动将某个任务加入到了immediate 队列并希望bottom half 处理过程运行和处理它,可将第8 位置1。每次系统调用结束返回前都要检查 bh_active。如果有位被置 1 则调用处于活动状态的 bottom half 处理过程。检查的顺序是从 0 位开始直到第 31 位。每次调用底层处理过程时

12、 bh_active 中的对应位将被清除。bh_active 是一个瞬态变量,在相应的 bottom half 处理过程无须工作的状态下避免了对此处理过程的调用。2.2 系统定时器2.2.1 定时器（TIMER）的原理操作系统应该能够在将来某个时刻准时调度某个任务。所以需要一种能保证任务较准时被调度运行的机制。希望支持某种操作系统的微处理器必须具有一个可周期性中断它的可编程间隔定时器。这个周期性中断被称为系统时钟滴答，它象节拍器一样来组织系统任务。Linux 的时钟观念很简单：它表示系统启动后的以时钟滴答记数的时间。所有的系统时间都基于这种量度，它和系统中的一个全局变量 jiffies 的名称

13、相同。 Linux 包含两种类型的系统定时器，它们都可以把将在某个系统时间上被调用的例程进行排列，但是它们的实现稍有区别。 图 2.2 画出了这两种机制。图 2.2 系统定时器第一种是老的定时器机制，它包含指向 timer_struct 结构的 32 位指针的静态数组以及当前活动定时器的屏蔽码 ：time_active。 此定时器表中的位置是静态定义的（类似 bottom half 的处理表 bh_base）。其入口在系统初始化时被加入到表中。 第二种是相对较新的定时器，它使用一个以升序的到期时间排列的 timer_list 结构链表。这两种方法都使用 jiffies 作为终结时间，这样，希望

14、运行 5 秒的定时器将不得不将 5 秒时间转换成jiffies 的单位并且将它和以jiffies 记数的当前系统时间相加从而得到定时器的终结时间。在每个系统时钟滴答时,定时器的 bottom half 处理过程被标记成活动状态以便调度器在下次运行时能进行系统定时器队列的处理。定时器的 bottom half 处理过程会处理两种类型的系统定时器。老的系统定时器将检查 timer_active 位是否置位。如果活动定时器已经到期则其定时器例程将被调用，同时 bottom half 中相应的活动位也被清除。新定时器位于 timer_list 结构链表中的入口也将受到检查。每个过期定时器将从链表中清除

15、，同时它的例程将被调用。新定时器机制的优点之一是能传递一个参数给定时器例程。2.2.1 定时器的系统调用机制Linux 支持几种进程相关的 interval 定时器(时间间隔定时器)。进程可以通过系统调用来设定定时器以便在定时器到时后向它发送信号。这些定时器可以是一次性的或者周期性的。这些定时器如下：Real 此定时器按照实时时钟记数，当时钟到期时，它的例程被调用，而向进程发送 SIGALRM 信号。Virtual 此定时器仅在进程运行时记数，时钟到期时向进程发送 SIGVTALRM 信号。Profile 此定时器在进程运行和核心为其运行时都记数。当时钟到期时向进程发送 SIGPROF 信号。

16、以上时间间隔定时器可以同时也可以单独运行，Linux 将所有这些信息存储在进程的 task_struct（相当于 PCB）数据结构中。通过系统调用可以设置这些时间间隔定时器并启动、终止它们或读取它们的当前值。Virtual 和 Profile 定时器以相同方式处理。每次时钟滴答后当前进程的时间间隔定时器将递减，当时钟到期之后将发送适当的信号。Real 时钟间隔定时器的机制有些不同：每个进程有其自身的一个 timer_list数据结构 real_timer，当时间间隔定时器运行时，它们被排入系统的定时器链表中。当时间间隔定时器到期后，bottom half 处理过程将把它从队列中删除并调用时间间

17、隔定时器的处理过程。此过程将向进程发送 SIGALRM 信号并重新启动定时器（指周期性的定时器），将其重新放入系统定时器队列。第三章 系统定时器队列机制在本章中，系统定时器的终结时间指的是定时器到期时以 jiffies 记数的系统时间。运行时间指的是 定时器的终结时间减去以 jiffies 记数的当前系统时间。如前所述，周期性时钟中断发生时，其服务例程 timer_interrupt 马上调用do_time（r sched.c），后者把核心的 bottom half 中的 TIMER 处理过程标记为活动，使得核心在从时钟中断处理返回前能够调用定时器 bottom half 处理例程。本章说明

18、Linux 系统组织和管理 timer_list 结构定时器的队列机制。3.1 Linux 系统管理 timer_list 结构定时器的数据模型3.1.1主要数据结构的定义(sched.c) unsigned long volatile jiffies=0; static unsigned long timer_jiffies = 0;#define TVN_BITS 6#define TVR_BITS 8#define TVN_SIZE (1 TVN_BITS) #define TVR_SIZE (1 expires timer_jiffies；根据 idx 值（体现出系统定时器的生存时间）

19、的大小，以及定时器终结时间 timer-expires 的 07、813、1419、2025 或 2631 位片段上的数值，将 timer所指示的定时器对应地添加到 tvecs0、tvecs1、tvecs2、tvecs3或 tvecs4上的定时器链上。(注：TVR_SIZE= = 256，TVN_SIZE= = 64)程序入口根据 timer-expires 的 07 位值将定时器加入 tv1 上的定时器链上准备（unsigned long idx = timer-expires timer_jiffies;）idx expires 的 813 位值将定时器加入 tv2 上的定时器链上True

20、idx (1expires expires timer_jiffies）的大小，把 idx 小于 256 的定时器加在 tv1 上由终止时间的低 8 位 (expires07)指向的定时器链上；把 idx 位于256，214)的定时器加在 tv2 上由终止时间的次低 6 位(expires813)指向的定时器链上；把 idx 位于214，220)的定时器加在 tv3 上由终止时间的较低 6 位(expires1419)指向的定时器链上；把 idx 位于220， 226)的定时器加在 tv3 上由终止时间的 6 位长的片段(expires2026)指向的定时器链上；另外，把idx 位于226，2

21、32)的定时器加在tv3 上由终止时间的高6 位(expires2732)指向的定时器链上。系统的 timer_jiffies 值在进程添加时间间隔定时器时等于 jiffies+1，而在核心对系统定时器队列进行级联处理时等于 jiffies。3.4 系统定时器队列的级联处理及 run_timer_list()流程定时器链的级联操作可以分解为将定时器链上的定时器逐个取下，并将取下来的定时器通过调用internel_add_timer(struct timer_list *timer)而添加到系统定时器队列中新的定时器链上。下面给出了对 run_timer_list()流程的分析：定时器队列的级联

22、处理如果 tv1.index 等于 0，即系统 jiffies 时间的 07 位片段上产生了进位，则对 tv2.index 所指向的定时器链进行级联操作。tv2.index 被置为其值加 1 以后的低 6 位，改变后的 tv2.index 等于在 07 位片段上产生了进位的 jiffies 的 813 位片段值加 1 以后的低 6 位数值。如果被置值以后的 tv2.index 等于 1（置值以前的 tv2.index 等于 0,且 tv1.index 等于 0，即以 jiffies 记数的系统时间在 013 位片段上产生了进位），则对tv3.index 所指向的定时器链进行级联操作， tv3.

23、index 被置为其值加 1 以后的低 6 位，改变后的 tv3.index 等于在 013 位片段上产生了进位的jiffies 的 1419 位片段值加 1 以后的低 6 位数值。如果被置值以后的 tv3.index 等于 1（置值以前的 tv3.index等于 0,且置值以前的 tv2.index 等于 0,及 tv1.index 等于 0，即以 jiffies 记数的系统时间在 019 位片段上产生了进位），则对 tv4.index 所指向的定时器链进行级联操作，tv4.index 被置为其值加 1 以后的低 6 位，改变后的 tv4.index 等于在 019 位片段上产生了进位的ji

24、ffies 的 2025 位片段值加 1 以后的低 6位数值。 如果被置值以后的 tv4.index 等于 1（置值以前的 tv4.index 等于 0,且置值以前的 tv3.index 等于 0,置值以前的 tv2.index 等于 0,及 tv1.index 等于 0，即以 jiffies记数的系统时间在 025 位片段上产生了进位），则对 tv5.index 所指向的定时器链进行级联操作，tv5.index 被置为其值加 1 以后的低 6 位，改变后的 tv5.index 等于在 025 位片段上产生了进位的jiffies 的 2631 位片段值加 1以后的低 6 位数值。否则，不调整

25、tv5.index 或 tv5 上的各定时器链表否则，不调整 tv4.index 或 tv4 上的各定时器链表否则，不调整 tv3.index 或 tv3 上的各定时器链表否则，不调整 tv2.index 或 tv2 上的各定时器链表把 tv1.index 指向的定时器链表上的过期定时器从链表中逐个清除，同时逐个调用定时器的例程。timer_jiffies 的值加 1，它等于以 jiffies 记数的下一个系统时间。tv1.index 被设置成其值加 1 后的低 8 位，它等于 timer_jiffies 值的最低 8 位，也等于 jiffies加 1 的最低 8 位。如果 jiffies=

26、= 0xffffffffUl，在这种情况下，timer_jiffies 值溢出，而核心将无法退出此次对定时器 bottom half 处理过程的调用，即核心陷入无穷循环体中，致使系统崩溃。否则，核心退出对 run_timer_list()的调用，并退出对定时器 bottom half 处理过程的调用。位于tv1 上的某个定时器链上的时间间隔定时器会在tv1.index 下一次指向此定时器链时被确认是到期的，且 timer_list 结构中的定时器被调用。在核心中的 tv1.index 从当前值变化到指向此定时器链对应的值的过程中，在可能出现的 tv1.index 为 0 的时刻，核心会进行系统

27、定时器队列的级联处理。从前面对定时器队列的级联处理的分析中可以看到，tv2.index、.、tv5.index所指向的定时器链的级联操作发生的条件分别是系统 jiffies 时间的 07 位片段、 013 位片段、019 位片段、及 025 位片段片段上产生了进位。而 jiffies 值在07 位片段、013 位片段、019 位片段及 025 位片段上产生进位分别意味着jiffies0.7、jiffies0.13、jiffies0.19、jiffies0.25 等于 0。因此，在发生对应定时器链上的级联操作时，tv2.index、tv5.index 指向的是终结时间的 813、1419、202

28、5 及 2631 位片段值对应地等于 jiffies8.13、 jiffies14.19、jiffies20.25、jiffies26.31 的定时器链表。由此看出，在发生对应定时器链上的级联操作时，tv2.index、tv5.index 指向的是生存时间处在0,256)、 0,214)、0,220)、0,226)的时间间隔定时器链表，且有 jiffies = = timer_jiffies。这样，系统定时器队列机制使位于 tvj 上的定时器链上的定时器经过定时器链上的级联操作后只会处在 tv i 上的某个定时器链上，且保证了( i= tv1.index 时)或 256 + expires0,7 t