1、武汉理工大学操作系统课程设计中国好学长系列之小灰灰的爸爸学 号： 课 程 设 计课程名称操作系统学 院计算机科学与技术学院专 业软件工程专业班 级中国好学长系列姓 名小灰灰的爸爸指导教师刘 军20132014学年 第1学期课程设计任务书学生姓名： 专业班级： 指导教师： 刘军 工作单位： 计算机科学与技术学院 题目: 内核定时器 初始条件：1.操作系统：Linux2.程序设计语言：C语言3.有界缓冲区内设有20个储存单元，其初值为0，放入/取出的数据项按增序设定为1-20这20个整型数要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求） 1技术要求：通过研究内核的
2、时间管理算法学习内核源代码。然后应用这些知识并且使用“信号”建立一种用户空间机制来测量一个多线程程序的执行时间。实验条件要求：每人一台Linux主机且有超级用户权限。2. 设计说明书内容要求：1)设计题目与要求2)总的设计思想及系统平台、语言、工具等3)数据结构与模块说明（功能与流程图）4)运行结果与运行情况3. 调试报告：1)调试记录2)自我评析和总结时间安排： 序号阶段内容所需时间1消化资料、系统设计1天2编程、调试3天3撰写报告1天合计天指导教师签名： 2013年12月26日系主任（或责任教师）签名： 年 月 日内核定时器摘要每个进程包含一到多个线程。进程也可能是整个程序或者是部分程序的
3、动态执行。线程是一组指令的集合，或者是程序的特殊段，它可以在程序里独立执行。也可以把它理解为代码运行的上下文。内核时间指明线程执行操作系统代码已经经过了多少个100ns的CPU时间，linux是一个具有保护模式的操作系统。它一直工作在i386 cpu的保护模式之下。内存被分为两个单元: 内核区域和用户区域。一般地，在使用虚拟内存技术的多任务系统上，内核和应用有不同的地址空间，因此，在内核和应用之间以及在应用与应用之间进行数据交换需要专门的机制来实现，本文站在用户空间的角度，测试一个多线程程序的程序执行时间。当一个进程希望获得信号量时, 如果信号量已经被占有, 则该进程将会被放到等待队列上sle
4、ep直到cpu将其唤醒。相对于spinlock来说开销太大，适用于长时间占有的lock。不可用于中断状态，因为它拥有信号量的进程可以sleep, 可以被抢占。1 设计题目与要求11设计题目：内核定时器12设计要求：通过研究内核的时间管理算法，学习内核源代码；然后应用这些知识并且使用“信号”建立一种用户空间机制来测量一个多线程程序的执行时间。2 总的设计思想及系统平台、语言、工具2.1 设计思想：2.1.1Linux内核对定时器的描述 Linux在include/linux/timer.h头文件中定义了数据结构timer_list来描述一个内核定时器： struct timer_list str
5、uct list_head list; unsigned long expires; unsigned long data; void (*function)(unsigned long); ; 各数据成员的含义如下： （1）双向链表元素list：用来将多个定时器连接成一条双向循环队列。 （2）expires：指定定时器到期的时间，这个时间被表示成自系统启动以来的时钟滴答计数（也即时钟节拍数）。当一个定时器的expires值小于或等于jiffies变量时，我们就说这个定时器已经超时或到期了。在初始化一个定时器后，通常把它的expires域设置成当前expires变量的当前值加上某个时间间隔值（
6、以时钟滴答次数计）。 （3）函数指针function：指向一个可执行函数。当定时器到期时，内核就执行function所指定的函数。而data域则被内核用作function函数的调用参数。 内核函数init_timer()用来初始化一个定时器。实际上，这个初始化函数仅仅将结构中的list成员初始化为空。如下所示（include/linux/timer.h）： static inline void init_timer(struct timer_list * timer) timer-list.next = timer-list.prev = NULL; 由于定时器通常被连接在一个双向循环队列中等
7、待执行（此时我们说定时器处于pending状态）。因此函数time_pending()就可以用list成员是否为空来判断一个定时器是否处于pending状态。如下所示 （include/linux/timer.h）： static inline int timer_pending (const struct timer_list * timer) return timer-list.next != NULL; 时间比较操作 在定时器应用中经常需要比较两个时间值，以确定timer是否超时，所以Linux内核在timer.h头文件中定义了4个时间关系比较操作宏。这里我们说时刻a在时刻b之后，就意味
8、着时间值ab。Linux强烈推荐用户使用它所定义的下列4个时间比较操作宏（include/linux/timer.h）： #define time_after(a,b) (long)(b) - (long)(a) = 0) #define time_before_eq(a,b) time_after_eq(b,a)2.1.2Linux 内核定时器定时器是管理内核时间的基础，用来计算流逝的时间，它以某种频率（节拍率）自行触发时钟中断，当时钟中断发生时，内核就通过一种特殊中断处理程序对其进行处理。但是原来的实现只能是time_t mytime形式的，经过简单的localtime(mytime)和c
9、time(&mytime)处理.精度是不够的，为了返回高精度的时间，这里使用了gettimeofday函数。这个syscall用来供用户获取timeval格式的当前时间信息（精确度为微秒级），以及系统的当前时区信息（timezone）。结构类型timeval的指针参数tv指向接受时间信息的用户空间缓冲区，参数tz是一个timezone结构类型的指针，指向接收时区信息的用户空间缓冲区。这两个参数均为输出参数，返回值0表示成功，返回负值表示出错。函数sys_gettimeofday()的源码如下（kernel/time.c）： asmlinkage long sys_gettimeofday(st
10、ruct timeval *tv, struct timezone *tz) if (tv) struct timeval ktv; do_gettimeofday(&ktv); 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_gettimeof
11、day()函数来检索系统当前时间并保存到局部变量ktv中。然后再调用copy_to_user（）宏将保存在内核空间中的当前时间信息拷贝到由参数指针tv所指向的用户空间缓冲区中。 （2）如果tz指针有效，则说明用户要检索当前时区信息，因此调用copy_to_user()宏将全局变量sys_tz中的时区信息拷贝到参数指针tz所指向的用户空间缓冲区中。 （3）最后，返回0表示成功。 函数do_gettimeofday()的源码如下（arch/i386/kernel/time.c）： /* * This version of gettimeofday has microsecond resolutio
12、n * and better than microsecond precision on fast x86 machines 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 * (
13、1000000 / HZ); sec = xtime.tv_sec; usec += xtime.tv_usec; 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
14、上一次更新xtime的那个时刻到do_gettimeofday()函数的当前执行时刻之间的具体时间间隔长度,以便精确地修正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（jiffieswa
15、ll_jiffies）（1000000HZ） 由于全局变量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()服务函数真正执行时刻之间的时间延迟间隔。每一
16、次timer_interrupt()被执行时都会计算这一间隔，并利用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分别更新参数指针所指向的timeval结构变量。至此，整个查询过程结束。 函数d
18、o_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_fast_gettimeoffset() #endif 显然，在配置有TSC寄存器的
19、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 Time Stamp Counter */ rdtsc(eax,edx); /* . rela
20、tive 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) * * Using a mull instead of a divl saves up to 31
21、 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寄存器的值，并将其高32位保存在edx局部变量中，低32位保存在局部变量eax中。 （2）让局部变量eaxtsc_lowe
22、axlast_tsc_low；也即计算当前时刻的TSC值与上一次时钟中断服务函数timer_interrupt()执行时的TSC值之间的差值。 （3）显然，从上一次timer_interrupt()到当前时刻的时间间隔就是（tsc_lowfast_gettimeoffset_quotient）。因此用一条mul指令来计算这个乘法表达式的值。 （4）返回值delay_at_last_interrupt（tsc_lowfast_gettimeoffset_quotient）就是从上一次时钟中断发生时到当前时刻之间的时间偏移间隔值。2.1.3Linux 信号signal处理机制信号signal机制是
23、进程之间相互传递消息的一种方法，全称为软中断信号。系统调用signal用来设定某个信号的处理方法，其调用声明的格式如下： void (*signal(int signum, void (*handler)(int)(int); 成功则返回该信号以前的处理配置，出错则返回SIG_ERR。在使用该调用的进程中加入以下头文件： 几个常见信号: SIGINT: 当用户按某些终端键时, 引发终端产生的信号. 如Ctrl+C键, 这将产生中断信号(SIGINT),它将停止一个已失去控制的程序。 SIGSEGV: 由硬件异常(除数为0, 无效的内存引用等等)产生的信号。这些条件通常由硬件检测到, 并将其通知
24、内核，然后内核为该条件发生时正在运行的进程产生该信号。 SIGURG: 在网络连接上传来带外数据时产生。 SIGPIPE: 在管道的读进程已终止后, 一个进程写此管道时产生，当类型为SOCK_STREAM的socket已不再连接时, 进程写到该socket也产生此信号。 SIGALRM: 进程所设置的闹钟时钟超时的时候产生。 SIGABRT: 进程调用abort函数时产生此信号, 进程异常终止。 SIGCHLD: 在一个进程终止或停止时, 它将把该信号发送给其父进程。 按系统默认, 将忽略此信号，如果父进程希望被告知其子进程的这种状态改变, 则应该捕捉此信号。通常是用wait系列函数捕捉, 如
25、果不wait的话, 子进程将成为一个僵尸进程。 SIGIO: 此信号指示一个异步I/O事件。 SIGSYS: 该信号指示一个无效的系统调用。 SIGTSTP: 交互式停止信号. Ctrl+Z, 按下时, 终端将产生此信号, 进程被挂起。2.1.4多线程编程多线程是计算机同时运行多个执行线程的能力（这些线程可以是同一程序的组成部分，或者也可以是完全不同的程序）。Linux系统下的多线程遵循POSIX线程接口，称为pthread。编写Linux下的多线程程序，需要使用头文件pthread.h，连接时需要使用库libpthread.a。而Linux下pthread的实现是通过系统调用clone（）来
26、实现的。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=pthread_create(&id,NULL,(void *) thread,NULL);if(ret!=0)printf (Create pthread error!n);exit (1);fo
27、r(i=0;i3;i+)printf(This is the main process.n);pthread_join(id,NULL);return (0);我们编译此程序：gcc 050119.c -lpthread -o 050119.out运行050119.out，我们得到如下结果：This is the main process.This is a pthread.This is the main process.This is the main process.This is a pthread.This is a pthread.再次运行，我们可能得到如下结果：This is a
28、 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在头文件/usr/include/bits/pthreadtypes.h中定义：typedef unsigned long int pthread_t;它是
29、一个线程的标识符。函数pthread_create用来创建一个线程，它的原型为：extern int pthread_create _P (pthread_t *_thread, _const pthread_attr_t *_attr,void *(*_start_routine) (void *), void *_arg);第一个参数为指向线程标识符的指针，第二个参数用来设置线程属性，第三个参数是线程运行函数的起始地址，最后一个参数是运行函数的参数。这里，我们的函 数thread不需要参数，所以最后一个参数设为空指针。第二个参数我们也设为空指针，这样将生成默认属性的线程。对线程属性的设定和
30、修改我们将在下一节 阐述。当创建线程成功时，函数返回0，若不为0则说明创建线程失败，常见的错误返回代码为EAGAIN和EINVAL。前者表示系统限制创建新的线程，例如线程数目过多了；后者表示第二个参数代表的线程属性值非法。创建线程成功后，新创建的线程则运行参数三和参数四确定的函数，原来的线程则继续运行下一行代码。函数pthread_join用来等待一个线程的结束。函数原型为：extern int pthread_join _P (pthread_t _th, void *_thread_return);第一个参数为被等待的线程标识符，第二个参数为一个用户定义的指针，它可以用来存储被等待线程的返回值。这个函数是一个线程阻塞的函数，调用它的函数将 一直等待到被等待的线程结束为止，当函数返回时，被等待线程的资源被收回。一个线程的结束有两种途径，一种是象我们上面的例子一样，函数结束了，调用它的 线程也就结束了；另一种方式是通过函数pthread_exit来实现。它的函数原型为：ext
