kernel定时器.doc

定时器的分析
一． 概述
何为定时器？
定时器（timer）是unix 中提供的一种定时服务的机制。它所起的作用是在某个特定的时间唤醒某个进程来做一些工作。用到定时器的unix 指令有sleep, at, …etc.在windows 95,windows 98中也有类似的机制。
在硬件中，有一个系统时钟，可以称为硬时钟。同时，linux 还维护一个软件时钟称为软时钟。软时钟使用jiffies这个全程变量来维持服务。使用两套时钟的原因是因为硬时钟的读取太麻烦。所消耗的时间太长。Os 通过跟踪软时钟来提供定时服务。并在每次开机时，软时钟读取一次硬时钟，此后各不相关。
定时器服务过程简介。
定时器的初始化过程在开机时就初始化完毕。（详细分析见后）
要求软件定时服务的进程（如sleep,at）申请timer资源，申请成功后它将它所对应的timer加入到timer_list链表中，并把这个定时器的timeout值交给timer->expires,timer->*fn()对应与该进程的定时服务程序。
随着时钟硬中断的发生，timer->expires越来越小，当expires <=jiffies 时（也就是说，到了定时服务的预定时间，当最后一次时间中断发生时，激活该定时器，转入定时器中断处理程序，并把定时服务程序放入bottom_half（一个中断响应的缓冲机制）删除该定时器。
然后中断返回。在bottom_half缓冲区中的定时服务程序由sched.c中的调度算法决定何时执行（一般马上就执行）。
分析简介
综观定时器的整个流程，我决定把我的分析分成3个部分：
1. 定时器的初始化过程。
2. 定时器的数据结构以及定时服务程序的主体。
3. 定时器的辅助数据结构以及他们所起的作用。
备注：本文使用redhat 2.0.34的代码，故与原文可能有出入，请谅解。
本文参考:
linux 电子书籍 linux talking
李善平老师的讲义（linux2）。。
二。定时器的初始化过程
一：定时服务中断向量的设定：

系统进行一系列初始化工作后进入保护模式，保护模式下的核心初始化模块从0X1000或0X100000（对于BIG_KERNEL）开始执行，负责数据区（BSS）、中断向量表、页表和寄存器的初始化，同时再进行一些必要的状态检查（详见prof.李善平的《linux定时服务》）。
最后，在汇编语言文件“arch/i386/kernel/head.S”中执行以下命令：
call SYMBOL_NAME(start_kernel)
从而，进入start_kernel()函数。
在start_kernel()函数中，各种初始工作继续进行。
首先，它调用“setup_arch(&command_line, &memory_start, &memory_end);”执行各种工作，其中的一项是调用request_region（）函数来申请I/O空间。即在iotable[]中找出合适的表项，在iolist中找出足够大的I/O空间，下面简单介绍request_region（）。
该函数在“/kernel/resource.c“中被定义，它有三个参数：from指定起始地址，num指定欲申请空间大小，name指定申请对象名。该函数首先找到第一个空表项，然后对其进行赋值。
在setup_arch()中调用了5次该函数：

因此，此时系统申请I/O空间的有：
申请对象
起始地址
长度
dma1
0X0
0X20
Timer
0X40
0X20
Dma page reg.
0X80
0X20
dma2
0XC0
0X20
npu等
0XF0
0X10
然后，setup_arch()调用paging_init()（arch/i386/mm/init.c）初始化所有页表。接着调用trap_init()（arch/i386/kernel/traps.c）设置各种trap入口，而后，调用"arch/i386/kernel/irq.c"中的"init_IRQ()"设置中断门，此函数设置了第2号和第13号中断向量：
setup_x86_irq(2, &irq2);
setup_x86_irq(13, &irq13);
并且又申请了两个IO空间：
加上在setup_arch()中申请的，共已申请7块IO空间。
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);
init_bh(TQUEUE_BH, tqueue_bh);
init_bh(IMMEDIATE_BH, immediate_bh);
做完以上工作以后，“start_kernel”调用time_init()函数，该函数在time.c中被定义，在time.c中，Linux首先定义了函数“timer_interrupt()”函数，本文后续部分将会再提到此函数，这儿，只需知道该函数就是时钟中断服务程序。接着，time.c中又定义了irqaction 结类型的变量irq0:
static struct irqaction irq0 = { timer_interrupt, 0, 0, "timer", NULL, NULL};
其中struct irqaction结构在interrupt.h 中被定义，它包含与中断服务程序有关的一些信息，如处理中断的函数入口地址（即第一项：void (*handler)(int, void *, struct pt_regs *);）。
除timer_inmterrupt()外，time.c中还定义了pentium_timer_interrupt（），这个函数与timer_inmterrupt相类似，但另外保存了中断服务程序发生时的一些信息。最后，time.c定义了time_init()函数，该函数用一个宏（# ifndef CONFIG_APM与#endif对）包括如计算机中有CPU hardware time counter时须编译的指令，它包括将中断处理改为pentium_timer_interrupt（），最后，调用setup_x86_irq(0, &irq0);设置中断向量。

二：转入init进程

start_kernel()在设置完irq0时间- 3 -中断向量后，继续各方面的初始化工作，且在此函数末尾调用：kernel_thread(init, NULL, 0);在初始化进行顺利的前提下，函数必将执行到这一步。
kernel_thread(程序名，参数，环境变量)是一个汇编语言函数。只有在核心态运行，且没有调用过execve()的进程，才可使用该函数。kernel_thread()利用linux/i386的系统调用（第0X80号）创建一个新进程。该系统调用返回后，可比较esp寄存器和esi寄存器的值来判断父、子进程。父进程通过kernel_thread()函数返回，执行task[0]进程。子进程则调用由参数“程序名”指定的程序。
系统转入init进程。
首先，init（）调用kernel_thread(bdflush, NULL, 0)创建后台进程bdflush。bdflush（fs/buffer）不断循环写出文件系统缓冲区中“脏”的内容。
接着，用调用函数init_swap_timer()，这个函数设置定时时钟表（timer_table）的SWAP_TIMER表项，并设定时钟中断响应函数为“swap_tick”，在源代码中为：
timer_table[SWAP_TIMER].expires = 0;
timer_table[SWAP_TIMER].fn = swap_tick;
timer_active |= (1<<SWAP_TIMER);
关于timer_table的数据结构，在下节有较详细的讨论。
swap_tick函数在每个时间片满时被调用，它首先判断是否free page不够或swap间隔时间到，若是的话，唤醒睡眠在kswapd_awake队列的进程并告诉CPU需要重新调度。在该程序末尾，程序执行：
timer_active |= (1<<SWAP_TIMER);
它再次激活timer_table[SWAP_TIMER]表项，以在下一时间片再调用该函数。并且这也是必需的，因为下一节中将解释，执行一激活的timer程序以后，此程序对应的timer_table[]中的表项将复位为0。

三．定时器的数据结构以及定时服务函数。
定时服务的数据结构(include/linux/timer.h)
Linux 有两种系统定时器，两者有略微的区别：
1． Timer_table结构。（timer.h）
用一静态的指向timer_struct数据结构的32指针数组，以及一长整型的变量timer_active实现。相关代码为（在timer.h中）：该结构是为了兼容以前的旧版本而设置的，但在现在的系统中，一些要求精确的定时器还在用它。其数据结构如下：
struct timer_struct {
unsigned long expires; // 时间片计数器
void (*fn)(void); // 定时服务处理函数指针
};
extern unsigned long timer_active;
extern struct timer_struct timer_table[32];

其中，timer_active和timer_table 是在sched.c中定义的外部变量，它的原型是：
unsigned long timer_active = 0;
struct timer_struct timer_table[32];
在timer_table[]中的每一表项所对应的定时器都是静态定义的，这与要讲的Bottom half机制非常相象，下面是timer.h中定义的一些宏，该宏很直观的把timer_table[]表项中对应的的定时器与其操作函数地址在timer_table[]表项中的位置表现出来了。
#define BLANK_TIMER 0 /*控制台屏幕保护定时器*/
#define BEEP_TIMER 1 /*控制台笛声定时器*/
#define RS_TIMER 2 /*RS-232端口定时器*/
#define SWAP_TIMER 3 /*用于后台页面切换的定时器*/

#define HD_TIMER 16 /*硬盘定时器*/
#define FLOPPY_TIMER 17 /*软盘定时器*/
#define SCSI_TIMER 18 /*微机系统接口传输超时定时器*/
#define NET_TIMER 19 /*tcp/ip超时定时器*/
#define SOUND_TIMER 20 /*声音接口定时器*/
#define COPRO_TIMER 21 /*387协处理器定时器*/

#define QIC02_TAPE_TIMER 22 /*QIC-02磁带驱动器定时器*/
#define MCD_TIMER 23 /*Mitsumi CD-ROM定时器*/

#define HD_TIMER2 24 /*第二硬盘定时器*/
#define GSCD_TIMER 25 /*Goldstar CD-ROM定时器*/

#define DIGI_TIMER 29 /*可能是与数字有关的定时器*/
下图是老式风格的定时服务数据结构图：
timer_table timer_struct
0 expires
*fn（）

expires
*fn（）

timer_active
31 0
31 这显然与botton half 机制非常相象，timer_tabel的每一个表项都包含一个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的相关联位被清零。详细的流程将在下节讨论。
2． Timer_list结构。（/timer.h）
定义如下所示：
struct timer_list {
struct timer_list *next; // 双向链表的连接指针
struct timer_list *prev; // 双向链表的连接指针
unsigned long expires; // 时间片计数器
unsigned long data; //
void (*function)(unsigned long); // 定时服务处理函数指针
};

timer_list结构是为了弥补timer_table只有32个timer的不足而创建的。一般来说，现在timer_table中的只有一些系统定时器，而用户的定时器都在timer_list中，timer_list的链表结构允许有无限多个timer,方便了用户。
在timer_list结构中，expires与function数据段与老风格的timer_struct中的相应数据段意义没有什么区别，next与prev用于在不同超时设定中使用同一函数时传递给定时服务程序的参数。在所有连在链表中的函数都是处于激活态的，一旦其expire 小于变量jiffies， 相应的定时服务程序被调用，该timer被删除。
timer data段是为了多个不同的timer 想使用同一个定时服务处理函数时，用来区分这个定时服务函数要为哪一个timer 服务。
从结构的定义可以看出，它用一种双向链表的数据结构，另外，值得一提的是它有一个head，head.expires初值为max_init（在sched.c中定义）
在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 TVN_BITS 6
#define TVR_BITS 8
#define TVN_SIZE (1 << TVN_BITS)
#define TVR_SIZE (1 << TVR_BITS)
这样，tvecs便是指向timer_vec类型的指针数组，而提timer_vec则是timer_list链表的表头。
定时服务程序的函数。
1． 定时服务函数调用的大概流程
start_kernel <init/main.c>

time_init <time.c> 初始化工作

setup_x86_irq(0,&irq0) <time.c>
irqaction irq0 = {timer_interrupt, ......} 。

系统硬中断引起timer_interrupt的调用

timer_interrupt <time.c>

do_timer <sched.c>

mark_bh(TIMER_BH) <softirq.h>

定时服务响应工作

if(bh_active & bh_mask)
do_bottom_half <softirq.c>

run_bottom_halves <softirq.c>

timer_bh <sched.c>

run_old_timers run_timer_list

补充：
l mark_bh()的原形定义在sched.c中。
extern inline void mark_bh(int nr)
{
set_bit(nr, &bh_active);
}
mark_bh的作用是将bh_active的第nr位置位，由前面的讨论可知，它表明bottom half的bh_base[TIMER_BH]被激活，应立即执行timer_bh()函数。

l 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()函数。
l if (bh_active & bh_mask)”条件表明Bottom half结构的bh_base有东西要做
2． 针对timer_table老结构的函数。
run_old_timers() (defined in ///timer.h immplement in sched.c)
3． 针对timer_list的函数。
函数的定义。
定义在timer.h中。实现在sched.c中。
以下定义在timer.h中。
extern void add_timer(struct timer_list * timer);
extern int del_timer(struct timer_list * timer);
extern inline void init_timer(struct timer_list * timer)
void mod_timer(struct timer_list *timer, unsigned long expires);
extern void it_real_fn(unsigned long);
static inline void run_timer_list(void)
函数的作用。
l Add_timer(),del_timer()的作用就是维护双向链表，负责向链表中加，减，timer.
l mod_timer(a,b) 是更新一个活动定时器的expire段的一个更有效的方法（如果该定时器没有活动，它将被激活。）否则，得用
del_timer(a);
a->expires = b;
add_timer(a)
来代替mod_timer(a,b).
l Timer_list在实际中有一个timer_head
The head for the timer-list has a "expires" field of MAX_UINT,
and the sorting routine counts on this..

函数的流程
1． Add_timer()
设信号量flags // save_flags(flags)
关中断 // cli()
以expires为keywork 顺序查找。
找到位置，向双向链表中加入timer.
释放信号量flags // restore_flags(flags);
返回。

2． Del_timer()
设信号量flags // save_flags(flags)
关中断 // cli()
以expires为keywork 顺序查找。
找到位置，在双向链表中删除timer.
释放信号量flags // restore_flags(flags);
返回。

3． Init_timer()
初始化timer ,使timer的前后指针为null.
4． Run_old_timer()
在前面的分析中，我提到过timer_active 的设置。
timer_active |= (1<<SWAP_TIMER);
使timer_active 只有一个bit为1。
Timer_active 是一个32位的选择器，32位中为1的bit表示该位对应的timer 有效。
在本程序中mask =1; mask +=mask使得mask也只有一个bit为1。
这样。Mask 作为 timer_active 的选择位。来控制timer_table 的选择。

流程 for run_old_timer()
l 关中断。
l 进入for循环。由mask来按位选择timer_active标志位。使有效的timer（并且服务时间到了）得到服务。
有效： !(mask & timer_active)
时间到：tp->expires> jiffies
l 将得到服务的timer 置为无效，并调用处理程序。（tp->fn()）
l 开中断。
5． Run_timer_list()

l 进入程序。
l 关中断
l 进入while循环：如果timer存在。//（timer = timer_head.next）!= & timer_head)
(如果head.next指向head,说明timer_list 中没有timer.)
并且timer 的引发时间到了（timer->expires<=jiffies）就为
该timer的定时服务程序做准备，并且把该timer从timer_list中删除。
l Timer_list指针下下移一格。
l 开中 /// 为了让定时服务程序fn(data)执行时。可以响应中断。
l 调用定时服务程序fn(data)。
l 关中断。 // 以便循环while
l 退出while 循环后，关中断并返回。
定时器的辅助数据结构及其作用。
Bottom_half 机制。
Bottom_half机制是一个中断响应的缓冲机制，当中断服务程序较长时（因为可以由用户指定的处理函数可能会很长。）就把该服务程序加入缓冲区，在恰当的时间交由cpu重新调度。以便中断处理程序可以快速返回。
Bottom Half 是一个队列，它最多可保存32种不同的Bottom Half 句柄，它使某些设备驱动程序或者其它的Linux内核可以排队保存下来，以待晚些时候执行，下面是Bottom Half的数据结构图：
bh_base
(timers)
bh_active
0 Bottom Half handlers
31 0

bh_mask
31 0

31

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]指向了。

bh_active 和 bh_mask的意义在schedule()函数中的（在“kernel/sched”内定义）
asmlinkage void schedule(void)函数中
说明的很清楚了，“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中的相应表项是否已与函数相连，若否，打印出错信息，否则，调用该函数，相关原代码如下：
if (mask & active) {
void (*fn)(void);
bh_active &= ~mask;
fn = *bh;
if (!fn)
goto bad_bh;
fn();
}
…………
bad_bh:
printk ("irq.c:bad bottom half entry %08lx\n", mask);
因为bh_base的第一项即与函数timer_bh()相关联，因此，timer_bh()函数就被调用了。

四．一些问题及思考。
注：
答案是自己瞎掰的，如果不对，请老师指点。
expires 在哪里被增加？

jiffies的用途。？
答： 在前面，多次出现一全局变量jiffies,该变量提供了一种时钟单位，初始值为0，每调用一次do_timer()函数，该值增1：
(*(unsigned long *)&jiffies)++; // defined in sched.c

Add_timer,del_timer关中断后，由谁来开中？
不知道。
Timer_interrupt()由谁调用？
是否由硬中断引发？
时钟硬中断发生后，如何影响jiffies和timer_table and timer_list中的expires?
会不会有同一个定时器在timer_table 和timer_list中同时存在，如果存在，那么会不会出现一个timer被调用两次的情况。
Run_timer_list() 和 run_timer_table()中都有关中断指令，为什么？
答： 可能是因为jiffies 是软时钟，有一套机制始终在增加jiffies的值，在以上两个函数中都不希望jiffies变动，所以就关中断，使软时钟机制不起作用。
那么，当定时器起作用时，软时钟不就停下了吗？！不.jiffies 只是软时钟的一个表象，在timer 起作用时被lock。软时钟另外有一套机制保证系统时间的正确性。

Timer 调用。
Jiffies

Actual jiffies
13
徐骏 王峥嵘 第 13 页 2024/12/28 周六