操作系统课程设计内核定时器

1、摘要摘要.11设计题目与要求设计题目与要求.21 11 1 设计题目设计题目：内核定时器.21 12 2 设计要求设计要求：通过研究内核的时间管理算法，学习内核源代码；然后应用这些知识并且使用“信号”建立一种用户空间机制来测量一个多线程程序的执行时间。.22 2 总的设计思想及系统平台、语言、工具总的设计思想及系统平台、语言、工具.2设计思想：.2内核对定时器的描述.22.1.2Linux 内核定时器.32.1.3Linux 信号signal处理机制.6多线程编程.7内核定时器机制的实现.92.2.系统平台：.122.3. 编程工具：.123数据结构与模块说明（功能与流程图）数据结构与模块说明

2、（功能与流程图）.12定时器使用：.123.2 多线程程序：.13程序流程图：.144.4. 源程序：源程序：.145 5运行结果与运行情况运行结果与运行情况.156 6调试记录：调试记录：.167 7自我评析和总结：自我评析和总结：.178.8.参考文献参考文献.17内核定时器内核定时器摘要摘要每个正在系统上运行的程序都是一个进程。每个进程包含一到多个线程。进程也可能是整个程序或者是部分程序的动态执行。线程是一组指令的集合，或者是程序的特殊段，它可以在程序里独立执行。也可以把它理解为代码运行的上下文。内核时间指明线程执行操作系统代码已经经过了多少个 100ns 的 CPU 时间，linux

3、是一个具有保护模式的操作系统。它一直工作在 i386 cpu 的保护模式之下。内存被分为两个单元: 内核区域和用户区域。一般地，在使用虚拟内存技术的多任务系统上，内核和应用有不同的地址空间，因此，在内核和应用之间以及在应用与应用之间进行数据交换需要专门的机制来实现，本文站在用户空间的角度，测试一个多线程程序的程序执行时间。当一个进程希望获得信号量时, 如果信号量已经被占有, 则该进程将会被放到等待队列上 sleep 直到 cpu 将其唤醒。相对于 spinlock 来说开销太大，适用于长时间占有的 lock。不可用于中断状态，因为它拥有信号量的进程可以 sleep, 可以被抢占，信号量可以设置

4、为同时允许的进程数。1设计题目与要求设计题目与要求11 设计题目：内核定时器12 设计要求：通过研究内核的时间管理算法，学习内核源代码；然后应用这些知识并且使用“信号”建立一种用户空间机制来测量一个多线程程序的执行时间。2 2 总的设计思想及系统平台、语言、工具2.12.1设计思想：Linux 内核对定时器的描述 Linux 在头文件中定义了数据结构 timer_list 来描述一个内核定时器： struct timer_list struct list_head list; unsigned long expires; unsigned long data; void (*function)

5、(unsigned long); ; 各数据成员的含义如下： （1）双向链表元素 list：用来将多个定时器连接成一条双向循环队列。 （2）expires：指定定时器到期的时间，这个时间被表示成自系统启动以来的时钟滴答计数（也即时钟节拍数）。当一个定时器的 expires 值小于或等于 jiffies 变量时，我们就说这个定时器已经超时或到期了。在初始化一个定时器后，通常把它的 expires 域设置成当前expires变量的当前值加上某个时间间隔值（以时钟滴答次数计）。 （3）函数指针 function：指向一个可执行函数。当定时器到期时，内核就执行 function所指定的函数。而 dat

6、a 域则被内核用作 function 函数的调用参数。 内核函数 init_timer()用来初始化一个定时器。实际上，这个初始化函数仅仅将结构中的list 成员初始化为空。如下所示（）： static inline void init_timer(struct timer_list * timer) timer-list.next = timer-list.prev = NULL; 由于定时器通常被连接在一个双向循环队列中等待执行（此时我们说定时器处于 pending状态）。因此函数 time_pending()就可以用 list 成员是否为空来判断一个定时器是否处于pending 状态。如

7、下所示 （）： static inline int timer_pending (const struct timer_list * timer) return timer-list.next != NULL; 时间比较操作 在定时器应用中经常需要比较两个时间值，以确定 timer 是否超时，所以 Linux 内核在头文件中定义了 4 个时间关系比较操作宏。这里我们说时刻 a 在时刻 b 之后，就意味着时间值 ab。Linux 强烈推荐用户使用它所定义的下列 4 个时间比较操作宏（）： #define time_after(a,b) (long)(b) - (long)(a) = 0) #de

8、fine time_before_eq(a,b) time_after_eq(b,a)2.1.2Linux 内核定时器定时器是管理内核时间的基础，用来计算流逝的时间，它以某种频率（节拍率）自行触发时钟中断，当时钟中断发生时，内核就通过一种特殊中断处理程序对其进行处理。但是原来的实现只能是 time_t mytime 形式的，经过简单的 localtime(mytime)和ctime(&mytime)处理.精度是不够的，为了返回高精度的时间，这里使用了 gettimeofday 函数。这个 syscall 用来供用户获取 timeval 格式的当前时间信息（精确度为微秒级） ，以及系统的

9、当前时区信息（timezone） 。结构类型 timeval 的指针参数 tv 指向接受时间信息的用户空间缓冲区，参数 tz 是一个 timezone 结构类型的指针，指向接收时区信息的用户空间缓冲区。这两个参数均为输出参数，返回值 0 表示成功，返回负值表示出错。函数 sys_gettimeofday()的源码如下（kernel/time.c）： asmlinkage long sys_gettimeofday(struct timeval *tv, struct timezone *tz) if (tv) struct timeval ktv; do_gettimeofday(&k

10、tv); if (copy_to_user(tv, &ktv, sizeof(ktv) return -EFAULT; if (tz) if (copy_to_user(tz, &sys_tz, sizeof(sys_tz) return -EFAULT; return 0; 显然，函数的实现主要分成两个大的方面： （1）如果 tv 指针有效，则说明用户要以 timeval 格式来检索系统当前时间。为此，先调用do_gettimeofday()函数来检索系统当前时间并保存到局部变量 ktv 中。然后再调用copy_to_user（）宏将保存在内核空间中的当前时间信息拷贝到由参数

11、指针 tv 所指向的用户空间缓冲区中。 （2）如果 tz 指针有效，则说明用户要检索当前时区信息，因此调用 copy_to_user()宏将全局变量 sys_tz 中的时区信息拷贝到参数指针 tz 所指向的用户空间缓冲区中。 （3）最后，返回 0 表示成功。 函数 do_gettimeofday()的源码如下（arch/i386/kernel/time.c）： /* * This version of gettimeofday has microsecond resolution * and better than microsecond precision on fast x86 machi

12、nes with TSC. */ void do_gettimeofday(struct timeval *tv) unsigned long flags; unsigned long usec, sec; read_lock_irqsave(&xtime_lock, flags); usec = do_gettimeoffset(); unsigned long lost = jiffies - wall_jiffies; if (lost) usec += lost * (1000000 / HZ); sec = xtime.tv_sec; usec += xtime.tv_use

13、c; read_unlock_irqrestore(&xtime_lock, flags); while (usec = 1000000) usec -= 1000000; sec+; tv-tv_sec = sec; tv-tv_usec = usec; 该函数的完成实际的当前时间检索工作。由于 gettimeofday()系统调用要求时间精度要达到微秒级，因此 do_gettimeofday()函数不能简单地返回 xtime 中的值即可，而必须精确地确定自从时钟驱动的 Bottom Half 上一次更新 xtime 的那个时刻到 do_gettimeofday()函数的当前执行时刻

14、之间的具体时间间隔长度,以便精确地修正 xtime 的值.假定被 do_gettimeofday()用来修正 xtime 的时间间隔为 fixed_usec，而从 wall_jiffies 到 jiffies之间的时间间隔是 lost_usec，而从 jiffies 到 do_gettimeofday()函数的执行时刻的时间间隔是offset_usec。则下列三个等式成立： fixed_usec（lost_usecoffset_usec） lost_usec（jiffieswall_jiffies）TICK_SIZE（jiffieswall_jiffies）（1000000HZ） 由于全局变量

15、 last_tsc_low 表示上一次时钟中断服务函数 timer_interrupt()执行时刻的 CPU TSC 寄存器的值，因此我们可以用 X86 CPU 的 TSC 寄存器来计算 offset_usec 的值。也即： offset_usec=delay_at_last_interrupt（current_tsc_lowlast_tsc_low）fast_gettimeoffset_quotient 其中，delay_at_last_interrupt 是从上一次发生时钟中断到 timer_interrupt()服务函数真正执行时刻之间的时间延迟间隔。每一次 timer_interrup

16、t()被执行时都会计算这一间隔，并利用 TSC的当前值更新 last_tsc_low 变量（可以参见 7.4 节） 。假定 current_tsc_low 是 do_gettimeofday()函数执行时刻 TSC 的当前值，全局变量 fast_gettimeoffset_quotient 则表示 TSC 寄存器每增加1 所代表的时间间隔值，它是由 time_init()函数所计算的。 根据上述原理分析，do_gettimeofday()函数的执行步骤如下： （1）调用函数 do_gettimeoffset()计算从上一次时钟中断发生到执行 do_gettimeofday()函数的当前时刻之间

17、的时间间隔 offset_usec。 （2）通过 wall_jiffies 和 jiffies 计算 lost_usec 的值。 （3）然后，令 sec=xtime.tv_sec，usec=xtime.tv_usec+lost_usec+offset_usec。显然，sec 表示系统当前时间在秒数量级上的值，而 usec 表示系统当前时间在微秒量级上的值。 （4）用一个 while循环来判断 usec 是否已经溢出而超过 106us1 秒。如果溢出，则将usec 减去 106us 并相应地将 sec 增加 1，直到 usec 不溢出为止。 （5）最后，用 sec 和 usec 分别更新参数指针

18、所指向的 timeval 结构变量。至此，整个查询过程结束。 函数 do_gettimeoffset()根据 CPU 是否配置有 TSC 寄存器这一条件分别有不同的实现。其定义如下（arch/i386/kernel/time.c）： #ifndef CONFIG_X86_TSC static unsigned long do_slow_gettimeoffset(void) static unsigned long (*do_gettimeoffset)(void) = do_slow_gettimeoffset; #else #define do_gettimeoffset() do_fas

19、t_gettimeoffset() #endif 显然，在配置有 TSC 寄存器的 i386 平台上，do_gettimeoffset（）函数实际上就是do_fast_gettimeoffset()函数。它通过 TSC 寄存器来计算 do_fast_gettimeoffset()函数被执行的时刻到上一次时钟中断发生时的时间间隔值。其源码如下（arch/i386/kernel/time.c）： static inline unsigned long do_fast_gettimeoffset(void) register unsigned long eax, edx; /* Read the T

20、ime Stamp Counter */ rdtsc(eax,edx); /* . relative to previous jiffy (32 bits is enough) */ eax -= last_tsc_low; /* tsc_low delta */ /* * Time offset = (tsc_low delta) * fast_gettimeoffset_quotient * = (tsc_low delta) * (usecs_per_clock) * = (tsc_low delta) * (usecs_per_jiffy / clocks_per_jiffy) * *

21、 Using a mull instead of a divl saves up to 31 clock cycles * in the critical path. */ _asm_(mull %2 :=a (eax), =d (edx) :rm (fast_gettimeoffset_quotient), 0 (eax); /* our adjusted time offset in microseconds */ return delay_at_last_interrupt + edx; 对该函数的注释如下： （1）先调用 rdtsc()函数读取当前时刻 TSC 寄存器的值，并将其高 3

22、2 位保存在 edx 局部变量中，低 32 位保存在局部变量 eax 中。 （2）让局部变量 eaxtsc_loweaxlast_tsc_low；也即计算当前时刻的 TSC 值与上一次时钟中断服务函数 timer_interrupt()执行时的 TSC 值之间的差值。 （3）显然，从上一次 timer_interrupt()到当前时刻的时间间隔就是（tsc_lowfast_gettimeoffset_quotient） 。因此用一条 mul 指令来计算这个乘法表达式的值。 （4）返回值 delay_at_last_interrupt（tsc_lowfast_gettimeoffset_quot

23、ient）就是从上一次时钟中断发生时到当前时刻之间的时间偏移间隔值。2.1.3Linux 信号 signal 处理机制信号 signal 机制是进程之间相互传递消息的一种方法，全称为软中断信号。系统调用signal 用来设定某个信号的处理方法，其调用声明的格式如下： void (*signal(int signum, void (*handler)(int)(int); 成功则返回该信号以前的处理配置，出错则返回 SIG_ERR。在使用该调用的进程中加入以下头文件：几个常见信号:SIGINT: 当用户按某些终端键时, 引发终端产生的信号. 如 Ctrl+C 键, 这将产生中断信号(SIGINT

24、),它将停止一个已失去控制的程序。SIGSEGV: 由硬件异常(除数为 0, 无效的内存引用等等)产生的信号。这些条件通常由硬件检测到, 并将其通知内核，然后内核为该条件发生时正在运行的进程产生该信号。SIGURG: 在网络连接上传来带外数据时产生。SIGPIPE: 在管道的读进程已终止后, 一个进程写此管道时产生，当类型为SOCK_STREAM 的 socket 已不再连接时, 进程写到该 socket 也产生此信号。SIGALRM: 进程所设置的闹钟时钟超时的时候产生。SIGABRT: 进程调用 abort 函数时产生此信号, 进程异常终止。SIGCHLD: 在一个进程终止或停止时, 它将

25、把该信号发送给其父进程。 按系统默认, 将忽略此信号，如果父进程希望被告知其子进程的这种状态改变, 则应该捕捉此信号。通常是用 wait 系列函数捕捉, 如果不 wait 的话, 子进程将成为一个僵尸进程。SIGIO: 此信号指示一个异步 I/O 事件。SIGSYS: 该信号指示一个无效的系统调用。SIGTSTP: 交互式停止信号. Ctrl+Z, 按下时, 终端将产生此信号, 进程被挂起。2.1.4 多线程编程多线程是计算机同时运行多个执行线程的能力（这些线程可以是同一程序的组成部分，或者也可以是完全不同的程序） 。Linux 系统下的多线程遵循 POSIX 线程接口，称为pthread。编

26、写 Linux 下的多线程程序，需要使用头文件 pthread.h，连接时需要使用库libpthread.a。而 Linux 下 pthread 的实现是通过系统调用 clone（）来实现的。clone（）是Linux 所特有的系统调用，它的使用方式类似 fork。下面展示多线程程序部分 050119.c。/* 050119.c */#include #include void thread(void)int i;for(i=0;i3;i+)printf(This is a pthread.n);int pthread (void)pthread_t id;int i,ret;ret=pthr

27、ead_create(&id,NULL,(void *) thread,NULL);if(ret!=0)printf (Create pthread error!n);exit (1);for(i=0;i3;i+)printf(This is the main process.n);pthread_join(id,NULL);return (0);我们编译此程序：运行 050119.out，我们得到如下结果：This is the main process.This is a pthread.This is the main process.This is the main proce

28、ss.This is a pthread.This is a pthread.再次运行，我们可能得到如下结果：This is a pthread.This is the main process.This is a pthread.This is the main process.This is a pthread.This is the main process.前后两次结果不一样，这是两个线程争夺 CPU 资源的结果。上面的示例中，我们使用到了两个函数，pthread_create 和 pthread_join，并声明了一个 pthread_t 型的变量。pthread_t 在头文件/us

29、r/include/bits/pthreadtypes.h 中定义：typedef unsigned long int pthread_t;它是一个线程的标识符。函数 pthread_create 用来创建一个线程，它的原型为：extern int pthread_create _P (pthread_t *_thread, _const pthread_attr_t *_attr,void *(*_start_routine) (void *), void *_arg);第一个参数为指向线程标识符的指针，第二个参数用来设置线程属性，第三个参数是线程运行函数的起始地址，最后一个参数是运行函数的

30、参数。这里，我们的函 数 thread 不需要参数，所以最后一个参数设为空指针。第二个参数我们也设为空指针，这样将生成默认属性的线程。对线程属性的设定和修改我们将在下一节 阐述。当创建线程成功时，函数返回 0，若不为 0 则说明创建线程失败，常见的错误返回代码为 EAGAIN 和 EINVAL。前者表示系统限制创建新的线程，例如线程数目过多了；后者表示第二个参数代表的线程属性值非法。创建线程成功后，新创建的线程则运行参数三和参数四确定的函数，原来的线程则继续运行下一行代码。函数 pthread_join 用来等待一个线程的结束。函数原型为：extern int pthread_join _P

31、(pthread_t _th, void *_thread_return);第一个参数为被等待的线程标识符，第二个参数为一个用户定义的指针，它可以用来存储被等待线程的返回值。这个函数是一个线程阻塞的函数，调用它的函数将 一直等待到被等待的线程结束为止，当函数返回时，被等待线程的资源被收回。一个线程的结束有两种途径，一种是象我们上面的例子一样，函数结束了，调用它的 线程也就结束了；另一种方式是通过函数 pthread_exit 来实现。它的函数原型为：extern void pthread_exit _P (void *_retval) _attribute_ (_noreturn_);唯一的参

32、数是函数的返回代码，只要 pthread_join 中的第二个参数 thread_return 不是NULL，这个值将被传递给 thread_return。最后要说明的是，一个线程不能被多个线程等待，否则第一个接收到信号的线程成功返回，其余调用 pthread_join 的线 程则返回错误代码ESRCH。2.1.5 内核定时器机制的实现.1 动态定时器机制的初始化 函数 init_timervecs()实现对动态定时器机制的初始化。该函数仅被 sched_init()初始化例程所调用。动态定时器机制初始化过程的主要任务就是将 tv1、tv2、tv5 这 5 个结构变量中的定时器向量指针数组 v

33、ec初始化为 NULL。如下所示（kernel/timer.c）： void init_timervecs (void) int i; for (i = 0; i TVN_SIZE; i+) INIT_LIST_HEAD(tv5.vec + i); INIT_LIST_HEAD(tv4.vec + i); INIT_LIST_HEAD(tv3.vec + i); INIT_LIST_HEAD(tv2.vec + i); for (i = 0; i expires; unsigned long idx = expires - timer_jiffies; struct list_head * v

34、ec; if (idx TVR_SIZE) int i = expires & TVR_MASK; vec = tv1.vec + i; else if (idx 1 TVR_BITS) & TVN_MASK; vec = tv2.vec + i; else if (idx 1 (TVR_BITS + TVN_BITS) & TVN_MASK; vec = tv3.vec + i; else if (idx 1 (TVR_BITS + 2 * TVN_BITS) & TVN_MASK; vec = tv4.vec + i; else if (signed lon

35、g) idx 0) /* can happen if you add a timer with expires = jiffies, * or you set a timer to go off in the past */ vec = tv1.vec + tv1.index; else if (idx (TVR_BITS + 3 * TVN_BITS) & TVN_MASK; vec = tv5.vec + i; else /* Can only get here on architectures with 64-bit jiffies */ INIT_LIST_HEAD(&

36、timer-list); return; /* * Timers are FIFO! */ list_add(&timer-list, vec-prev); 对该函数的注释如下： （1）首先，计算定时器的 expires 值与 timer_jiffies 的插值（注意！这里应该使用动态定时器自己的时间基准） ，这个差值就表示这个定时器相对于上一次运行定时器机制的那个时刻还需要多长时间间隔才到期。局部变量 idx 保存这个差值。 （2）根据 idx 的值确定这个定时器应被插入到哪一个定时器向量中。其具体的确定方法我们在节已经说过了，这里不再详述。最后，定时器向量的头部指针 vec 表示这

37、个定时器应该所处的定时器向量链表头部。 （3）最后，调用 list_add()函数将定时器插入到 vec 指针所指向的定时器队列的尾部。 .3 修改一个定时器的 expires 值 当一个定时器已经被插入到内核动态定时器链表中后，我们还可以修改该定时器的 expires值。函数 mod_timer()实现这一点。如下所示（kernel/timer.c）： int mod_timer(struct timer_list *timer, unsigned long expires) int ret; unsigned long flags; spin_lock_irqsave(&timer

38、list_lock, flags); timer-expires = expires; ret = detach_timer(timer); internal_add_timer(timer); spin_unlock_irqrestore(&timerlist_lock, flags); return ret; 该函数首先根据参数 expires 值更新定时器的 expires 成员。然后调用 detach_timer()函数将该定时器从它原来所属的链表中删除。最后调用 internal_add_timer()函数将该定时器根据它新的 expires 值重新插入到相应的链表中。 函数

39、 detach_timer()首先调用 timer_pending()来判断指定的定时器是否已经处于某个链表中，如果定时器原来就不处于任何链表中，则 detach_timer()函数什么也不做，直接返回 0值，表示失败。否则，就调用 list_del()函数将定时器从它原来所处的链表中摘除。如下所示（kernel/timer.c）： static inline int detach_timer (struct timer_list *timer) if (!timer_pending(timer) return 0; list_del(&timer-list); return 1; 2

40、.2.系统平台：系统平台：一台 Linux 主机且有超级用户权限2.3. 编程工具：编程工具：VI 编辑器，Gedit 编辑器3数据结构与模块说明（功能与流程图）数据结构与模块说明（功能与流程图）3.1定时器使用：int gettimeofday(struct timeval *tv,struct timezone *tz); strut timevallong tv_sec; /*秒数*/ long tv_usec; /*微秒数*/ ;这个 syscall 用来供用户获取 timeval 格式的当前时间信息（精确度为微秒级） ，以及系统的当前时区信息（timezone） 。结构类型 time

41、val 的指针参数 tv 指向接受时间信息的用户空间缓冲区，参数 tz 是一个 timezone 结构类型的指针，指向接收时区信息的用户空间缓冲区。这两个参数均为输出参数，返回值 0 表示成功，返回负值表示出错。实现过程如下：main() struct timeval tpstart,tpend; /*申请 struct timeval 的变量，tv_sec 返回的是秒数，tv_usec 返回的是微秒数*/float timeuse; gettimeofday(&tpstart,NULL); pthread(); gettimeofday(&tpend,NULL); timeu

42、se=1000000*(tpend.tv_sec-tpstart.tv_sec)+ tpend.tv_usec-tpstart.tv_usec; timeuse/=1000000; printf(Used Time:%f secn,timeuse); exit(0); 3.2 多线程程序：进行多线程程序设计时，我们使用到了两个函数，pthread_create 和 pthread_join，并声明了一个 pthread_t 型的变量。pthread_t 在头文件/usr/include/bits/pthreadtypes.h 中定义，它是一个线程的标识符。函数 pthread_create 用

43、来创建一个线程，函数 pthread_join 用来等待一个线程的结束。实现过程如下：int pthread_create(&id,NULL,(void *) thread,NULL);pthread_join(id,NULL);void thread(void)int i;for(i=0;i3;i+)printf(This is a pthread.n);int pthread(void)pthread_t id; /* 声明了一个 pthread_t 型的变量*/int i,ret;ret=pthread_create(&id,NULL,(void *) thread,NU

44、LL);if(ret!=0)printf(Create pthread error!n);exit(1);for(i=0;i3;i+)printf(This is the main process.n);pthread_join(id,NULL);return(0);3.3 程序流程图：获取进程开始时间获取进程结束时间开始计算使用时间功能函数结束4.4. 源程序：源程序： #include #include #include int gettimeofday(struct timeval *tv,struct timezone *tz); int pthread_create(&id,

45、NULL,(void *) thread,NULL);/pthread_join(id,NULL);strut timevallong tv_sec; /*秒数*/ long tv_usec; /*微秒数*/ ;void thread(void)int i;for(i=0;i3;i+)printf(This is a pthread.n);int pthread(void)pthread_t id; /* 声明了一个pthread_t型的变量*/int i,ret;ret=pthread_create(&id,NULL,(void *) thread,NULL);if(ret!=0)p

46、rintf(Create pthread error!n);exit(1);for(i=0;i3;i+)printf(This is the main process.n);pthread_join(id,NULL);return(0);main() struct timeval tpstart,tpend; /*申请struct timeval的变量，tv_sec返回的是秒数，tv_usec返回的是微秒数*/float timeuse; gettimeofday(&tpstart,NULL); pthread(); gettimeofday(&tpend,NULL); timeuse=1000000*(tpend.tv_s