荔园在线
荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀
[回到开始]
[上一篇][下一篇]
发信人: igmp (igmp), 信区: Security
标 题: 论文集（1）
发信站: 荔园晨风BBS站 (Wed Jun 27 23:09:49 2001), 转信
Linux 的定时服务分析
计算机962 高庆 李贵宾
时钟中断向量的设定
系统进行一系列初始化工作后进入保护模式，保护模式下的核心初始化模块从
0X1000或0X100000（对于BIG_KERNEL）开始进行的初始化，同时再进行一些必要的
状态检查。最后，在汇编语言文件"arch/i386/kernel/head.S"中执行以下命令：
call SYMBOL_NAME(start_kernel)
从而，进入start_kernel()函数。
在start_kernel()函数中，各种初始工作继续进行。
首先，他调用request_region（）函数来申请I/O空间。即在iotable[]中找出合适
的表项，在iolist中找出足够大的I/O空间。
然后，调用trap_init()设置各种trap入口，而后，调用"arch/i386/kernel/irq.
c"中的"init_IRQ()"设置中断门。
start_kernel()接着调用sched_init()(kernel/sched.c"中定义)，它设置、启动
第一个进程init_task。设置用于管理bottom half机制的数据结构bh_base[]，规
定三类事件的中断处理函数（即时钟TIMER_BH、设备TQUEUE_BH和IMMEDIATE_BH）
：具体形式如下:
init_bh(TIMER_BH, timer_bh);
Bottom Half 是一个队列，它最多可保存32种不同的Bottom Half 句柄，它使某
些设备驱动程序或者其它的Linux内核可以排队保存下来，以待晚些时候执行.
bh_base 是一指向32个指向内核的Bottom Half 操纵函数的向量（地址），
bh_mask，bh_active都与之相关联，若bh_mask的第n位被置位，表明bh_base表中
的第n项指向某一Bottom Half函数，若bh_active的第n位被置位，表明bh_base表
中的第n项指向的Bottom Half函数须尽快被执行。bh_base表中的下标是被静态定
义的，Timer bottom half 函数具有最高的优先权，如bh_base的第一项状态是激
活的，时钟中断立即被执行。
在函数sched_init（）中调用的init_bh(TIMER_BH,timer_bh)函数是在
interrupt.h中定义的内联函数，在这个头文件中还定义了枚举量：
enum {
TIMER_BH = 0, CONSOLE_BH, TQUEUE_BH, DIGI_BH,
SERIAL_BH, RISCOM8_BH, SPECIALIX_BH, BAYCOM_BH,
NET_BH, IMMEDIATE_BH, KEYBOARD_BH, CYCLADES_BH,
CM206_BH
};
init_bh()有两个参数：nr是整型的，调用时赋予它的是上述枚举量，另一参数是
指向函数的指针：void (*routine)(void)，下面语句是该函数的定义：
extern inline void init_bh(int nr, void (*routine)(void))
{
bh_base[nr] = routine;
bh_mask_count[nr] = 0;
bh_mask |= 1 << nr;
}
其中第三条语句"bh_mask |= 1 << nr;"使bh_mask第nr位置位，表明与该位相关联
的bottom half 函数已被bh_base[nr]指向了。
做完以上工作以后，"start_kernel"调用time_init()函数,此处设置时钟中断为零
号中断。最后，调用setup_x86_irq(0, &irq0);设置中断向量。
start_kernel()在设置完irq0中断向量后，继续各方面的初始化工作。
系统转入init进程。
首先，init（）调用创建后台进程bdflush。接着，用调用函数
init_swap_timer()，这个函数设置定时时钟表（timer_table）的SWAP_TIMER表项
，并设定时钟中断响应函数为"swap_tick" 。 swap_tick函数在每个时间片满时被
调用，它首先判断是否free page不够或swap间隔时间到，若是的话，唤醒睡眠在
kswapd_awake队列的进程并告诉CPU需要重新调度。在该程序末尾，程序执行：
timer_active |= (1<<SWAP_TIMER);
它再次激活timer_table[SWAP_TIMER]表项，在下一时间片再调用该函数。并且这
也是必需的，执行一激活的timer程序以后，此程序对应的timer_table[]中的表项
将复位为0。
定时服务的数据结构
与timer有关的主要的数据结构定义在文件timer.h里：
Linux 有两种系统定时器，两者有略微的区别：
老式：用一静态的timer_struct数据结构的32元素数组，以及一长整型的变量
timer_active实现。相关代码为（在timer.h中）：
struct timer_struct {
unsigned long expires;
void (*fn)(void);
};
在timer_table[]中的每一表项所对应的定时器都是静态定义的，其对应的定时服
务程序也应是操作系统所设立的。例如,Linux 定义的其中一个表项如下:
#define SWAP_TIMER 3 /*用于后台页面切换的定时器*/
这与botton half 机制非常相象，timer_table的每一个表项都包含一个
timer_struct类型的结构，以在第二节提到的如下程序段为例：
timer_table[SWAP_TIMER].expires = 0;
timer_table[SWAP_TIMER].fn = swap_tick;
timer_active |= (1<<SWAP_TIMER);
显然，timer_table[]的第SWAP_TIMER项，即第3项已指向swap_tick函数，expire
数据段在定时服务程序与timer_table[]相关联的一开始就被指定了，当其小于变
量jiffies，并且timer_active的相关联位置位时，相应的定时服务程序被调用，
同时timer_active的相关联位被清零。
新式：采用一种叫做timer_list的数据结构，Linux还面向用户定义了增加或删除
定时服务的add_timer（）与del_timer（）函数,因此用户定义的定时服务程序应
该使用这种数据结构，其定义如下所示：
struct timer_list {
struct timer_list *next;
struct timer_list *prev;
unsigned long expires;
unsigned long data;
void (*function)(unsigned long);
};
在sched.c中的定义有：
struct timer_vec {
int index;
struct timer_list *vec[TVN_SIZE];
};
struct timer_vec_root {
int index;
struct timer_list *vec[TVR_SIZE];
};
static struct timer_vec tv5 = { 0 };
static struct timer_vec tv4 = { 0 };
static struct timer_vec tv3 = { 0 };
static struct timer_vec tv2 = { 0 };
static struct timer_vec_root tv1 = { 0 };
static struct timer_vec * const tvecs[] = {
(struct timer_vec *)&tv1, &tv2, &tv3, &tv4, &tv5
};
#define NOOF_TVECS (sizeof(tvecs) / sizeof(tvecs[0]))
static unsigned long timer_jiffies = 0;
这样，tvecs便是指向timer_vec类型的指针数组，而提timer_vec则是timer_list
链表的表头。
在timer_list结构中，expires与function数据段与老式的timer_struct中的相应
数据段意义没有区别， next与prev用于在不同超时设定中使用同一函数时传递给
定时服务程序的参数。在所有连在链表中的函数都是处于激活态的，但是只有在
tvecs[0]中的程序才有资格被调用，一旦其expire 小于变量jiffies， 相应的定
时服务程序被调用，该结点被删除。
定时服务程序的流程 分析
由前所述，系统设定时钟中断后，每隔一定的时间，系统调用时钟中断服务程序，
这一层由硬件实现。在timer_interrupt()函数体的开头，调用函数：
do_timer(regs);
do_timer()函数在kernel/sched.c中被定义，其原型为：
void do_timer(struct pt_regs * regs)
在前面，多次出现一全局变量jiffies,该变量提供了一种系统计时工具，初始值为
0，每调用一次do_timer()函数，该值增1（也就是约每毫秒增1）：
(*(unsigned long *)&jiffies)++;
接着，do_timer（）函数调用mark_bh(TIMER_BH);
mark_bh（）是在interrupt.h 中定义的内联函数，它非常简单，原型如下：
extern inline void mark_bh(int nr)
{
set_bit(nr, &bh_active);
}
这儿，Linux采用老风格的timer结构，mark_bh将bh_active的第nr位置位，由第一
节讨论可知，它表明bottom half的bh_base[TIMER_BH]被激活，应立即执行
timer_bh()函数。
在第二节提到"interruptible_sleep_on(&kswapd_wait)"是在kswapd（）中调用的
，在interruptible_sleep_on（）函数体（在kernel/sched内定义）调用语句：
__sleep_on(p,TASK_UNINTERRUPTIBLE);
__sleep_on（）函数也是在"kernel/sched"内定义的内联函数，其中通过语句
"schedule();"调用schedule()函数，schedule()函数在"kernel/sched"内定义为
：
asmlinkage void schedule(void)
其中有语句：
if (bh_active & bh_mask) {
intr_count = 1;
do_bottom_half();
intr_count = 0;
}
bh_active 和 bh_mask的意义在这儿已经很清楚了，"if (bh_active &
bh_mask)"条件表明Bottom half结构的bh_base有东西要做，再来看
do_bottom_half()函数，此函数在"interrupt.h "中说明，"kernel/softirq.c"
中被定义，它先取出bh_active 和 bh_mask均为1的位组成一新的长整型变量
active：
active = bh_active & bh_mask;
然后逐位判断active是否为1，具体实现方法是：用一变量mask，赋初值为1，通过
自加的方法进行左移位：mask += mask。
若某一位置位，则通过"if (mask & active)"检测，将bh_active中相应位清零，
判断bh_base中的相应表项是否已与函数相连，若否，打印出错信息，否则，
timer_bh()函数就被调用了。
timer_bh()函数流程很简单，在kernel/sched.c中定义如下：
static void timer_bh(void)
{
update_times();
run_old_timers();
run_timer_list();
}
update_times()重新设置与系统计时所用的一些参数，与定时服务程序没有直接关
系，这儿，相关的是run_old_timers()与run_timer_list()函数。
与第三节所述的两种timer数据结构相对应，Linux提供了上述两种函数，下面将分
析run_old_timers()与run_timer_list()函数！
run_old_timers()非常简单，在第三节中，提到过使timer_table[]的第
SWAP_TIMER项，即第3项与函数swap_tick（）相关联的实现方法，由代码：
"timer_active |= (1<<SWAP_TIMER);"
可知，timer_active的第三位置位，使用老风格timer struct的中断服务程序都是
类似与timer_active相关联的。与检查bh_base并执行对应函数类似，
run_old_timers（）函数也使用了一变量"mask"来检查timer_active各位是否为1
，如果是的话，接着判断timer_table[]中该项的expires值是否已被jiffies超过
（jiffies在每次do_timer（）执行时增1），如果答案是肯定的，那么就调用与之
相对应的函数，下面是其代码：
static inline void run_old_timers(void)
{
struct timer_struct *tp;
unsigned long mask;
for (mask = 1, tp = timer_table+0 ; mask ; tp++,mask += mask) {
if (mask > timer_active)
break;
if (!(mask & timer_active))
continue;
if (tp->expires > jiffies)
continue;
timer_active &= ~mask;
tp->fn();
sti();
}
}
run_timer_list()函数与timer_list数据结构相对应，由于它是用于用户定义的定
时服务程序的，因此，Linux还提供了在tvecs[i]->vec中增加与删除timer_list节
点的函数add_timer（）与del_timer（）函数。
del_timer（）函数比较简单，它以待删除timer_list节点的指针"timer"为参数，
关中后调用detach_timer（）来实际删除"timer"，关于基本的双向链表的删除这
里不再赘述。
add_timer（）函数略微复杂，它首先判断欲加入的timer_list节点是否合法(这只
是在调试是是有效的)，如是的话，调用函数internal_add_timer(timer)。
internal_add_timer(timer)函数根据timer的expires数据项（即设定定时时间的
值）与timer_jiffies的差判断应插入到tvecs中的那一项，其中变量
imer_jiffies初始为0，每次处理完一组中断服务程序后增1，它是作为插入时的一
中间值，在看到run_timer_list（）函数后可以对之有一个较为清楚的了解。
tvecs[0]到tvecs[5]中所挂的定时服务程序按定时时间，即expires的增序排列，
且采取对expires - timer_jiffies关于（TVR_MASK+1）或（TVN_MASK+1）取模的
办法指定tvecs[i]->vec的某一项。并且调用insert_timer（）函数进行实际插入
。这里也不再赘述关于基本的双向链表的插入了。
run_timer_list（）函数首先进行判断：
while ((long)(jiffies - timer_jiffies) >= 0)
该判断若成立的话，表明还有需要执行的定时服务程序，于是进入循环体。
在循环体内，首先通过语句"if (!tv1.index)"判断tvecs[0]即tv1中是否没有关联
的定时服务程序或有剩余时间为0，即需要立即执行的程序，若是，对tvecs进行了
调整，把tvecs[n]-> vec（n=2，3，4，5）所挂的应该放入tvecs[0]的表项挂到
tvecs[0]，并使tvecs[n]->index加1（以上动作通过调用函数cascade_timers（）
实现）。
这里，由于在执行run_timer_list（）时是关中的，jiffies的值在此期间固定不
变，timer_jiffies提供了一种计时工具，它使cascade_timers（）内调用
internal_add_timer()有效的把在tvecs[2…4]的队列定时程序移到tvecs[0]中。
接下去把tv1.vec [tv1.index]所有的中断服务函数调用，然后把对应的
timer_list节点删除。并且做以下操作：
++timer_jiffies;
tv1.index = (tv1.index + 1) & TVR_MASK;
其中，++timer_jiffies表明原来的在timer_jiffies以前所应调用的中断服务函数
都已调用，现将其增1，去执行对应expire为新的timer_jiffies的中断服务函数。
此处,我们可以看出,Linux 所采用的定时服务的数据结构是非常高效的。在数组
tvecs[]中,把当前要做的定时服务都放到tvecs[0]中,采取高效率的的机制。为选
择服务事件节省了大量的时间。而把系统所必须耗费的工作放到把服务事件从
tvecs[2…4]的队列定时程序移到tvecs[0]中去。而由实践经验证明,系统所要做的
这种大规模的移动(或通俗地称为搬家)的繁杂工作的次数是可以令人接受的。他的
总体表现是令人满意的,Linux的这种精妙设计也是其风行的一个重要原因。
--
小小人物
没有过去，没有将来
只有你与我
※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 192.168.43.46]
[回到开始]
[上一篇][下一篇]
荔园在线首页 友情链接：深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店