操作系统大作业-内核定时器.doc

学 号： 0120910680115课 程 论 文课程名称操作系统A学 院计算机科学与技术学院专 业软件工程专业班 级软件0901姓 名指导教师向广利20112012学年 第1学期目录1设计题目和要求.32. 总体设计思想及系统平台、语言、工具.33. 数据结构与模块说明（功能与流程图）.134. 源代码（见附录）.155. 运行结果以运行情况.156. 调试记录.167. 自我评价和总结：.168. 参考资料：.169. 附录.17课程设计任务书学生姓名： 专业班级： 软件0901 指导教师： 向广利 工作单位： 计算机科学与技术学院 题目: 内核定时器初始条件：1操作系统：Linux 或者 windows2程序设计语言：C,java语言要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求） 1技术要求：1）分析操作系统内核源码。2）研究内核的时间管理算法。3）建立一种用户空间机制来测量一个多线程程序的执行时间。2 设计说明书内容要求：1)设计题目与要求2)总的设计思想及系统平台、语言、工具等。3）数据结构与模块说明（功能与流程图）4）给出用户名、源程序名、目标程序名和源程序及其运行结果。（要注明存储各个程序及其运行结果的主机IP地址和目录。）5）运行结果与运行情况（提示: (1)编译命令可用：cc -lpthread -o 目标文件名源文件名(2)多线程编程方法参见附件。）3. 调试报告：1) 调试记录2） 自我评析和总结上机时间安排：19周一 五 下午14：00 18：00 指导教师签名： 年 月 日系主任（或责任教师）签名： 年 月 日摘要：每个正在系统上运行的程序都是一个进程。每个进程包含一到多个线程。进程也可能是整个程序或者是部分程序的动态执行。线程是一组指令的集合，或者是程序的特殊段，它可以在程序里独立执行。也可以把它理解为代码运行的上下文。内核时间指明线程执行操作系统代码已经经过了多少个100ns的CPU时间，linux是一个具有保护模式的操作系统。它一直工作在i386 cpu的保护模式之下。内存被分为两个单元: 内核区域和用户区域。一般地，在使用虚拟内存技术的多任务系统上，内核和应用有不同的地址空间，因此，在内核和应用之间以及在应用与应用之间进行数据交换需要专门的机制来实现，本文站在用户空间的角度，测试一个多线程程序的程序执行时间。当一个进程希望获得信号量时, 如果信号量已经被占有, 则该进程将会被放到等待队列上sleep直到cpu将其唤醒。相对于spinlock来说开销太大，适用于长时间占有的lock。不可用于中断状态，因为它拥有信号量的进程可以sleep, 可以被抢占，信号量可以设置为同时允许的进程数。关键字：操作系统、内核、cpu、定时器1设计题目和要求 设计题目：内核定时器 设计要求：通过研究内核的时间管理算法，学习内核源代码；然后应用这些知识并且使用“信号”建立一种用户空间机制来测量一个多线程程序的执行时间2总体设计思想及系统平台、语言、工具Linux内核定时器：时钟中断：有系统定时的硬件以周期性的时间间隔产生 比如HZ=1000.即1S中产生1000次中断。一次1/1000s每当时钟中断产生一次，jiddise（ulong）就加一，驱动程式根据jiffise值计算时间及间隔关机之后jiffse清零。一个延时程序：ulong j=jiffise+jit_delay*HZ;/延时jit_delay秒while(jiffiselist.next = timer-list.prev = NULL; 由于定时器通常被连接在一个双向循环队列中等待执行（此时我们说定时器处于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之后，就意味着时间值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)和ctime(&mytime)处理.精度是不够的，为了返回高精度的时间，这里使用了gettimeofday函数。这个syscall用来供用户获取timeval格式的当前时间信息（精确度为微秒级），以及系统的当前时区信息（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(&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_gettimeofday()函数来检索系统当前时间并保存到局部变量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 resolution * 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 * (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上一次更新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（jiffieswall_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()服务函数真正执行时刻之间的时间延迟间隔。每一次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()函数的当前时刻之间的时间间隔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结构变量。至此，整个查询过程结束。 函数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_fast_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 Time 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) * * 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寄存器的值，并将其高32位保存在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_quotient）就是从上一次时钟中断发生时到当前时刻之间的时间偏移间隔值。2.1.3Linux 信号signal处理机制信号signal机制是进程之间相互传递消息的一种方法，全称为软中断信号。系统调用signal用来设定某个信号的处理方法，其调用声明的格式如下： void (*signal(int signum, void (*handler)(int)(int); 成功则返回该信号以前的处理配置，出错则返回SIG_ERR。在使用该调用的进程中加入以下头文件：几个常见信号:SIGINT: 当用户按某些终端键时, 引发终端产生的信号. 如Ctrl+C键, 这将产生中断信号(SIGINT),它将停止一个已失去控制的程序。SIGSEGV: 由硬件异常(除数为0, 无效的内存引用等等)产生的信号。这些条件通常由硬件检测到, 并将其通知内核，然后内核为该条件发生时正在运行的进程产生该信号。SIGURG: 在网络连接上传来带外数据时产生。SIGPIPE: 在管道的读进程已终止后, 一个进程写此管道时产生，当类型为SOCK_STREAM的socket已不再连接时, 进程写到该socket也产生此信号。SIGALRM: 进程所设置的闹钟时钟超时的时候产生。SIGABRT: 进程调用abort函数时产生此信号, 进程异常终止。SIGCHLD: 在一个进程终止或停止时, 它将把该信号发送给其父进程。 按系统默认, 将忽略此信号，如果父进程希望被告知其子进程的这种状态改变, 则应该捕捉此信号。通常是用wait系列函数捕捉, 如果不wait的话, 子进程将成为一个僵尸进程。SIGIO: 此信号指示一个异步I/O事件。SIGSYS: 该信号指示一个无效的系统调用。SIGTSTP: 交互式停止信号. Ctrl+Z, 按下时, 终端将产生此信号, 进程被挂起。2.1.4多线程编程多线程是计算机同时运行多个执行线程的能力（这些线程可以是同一程序的组成部分，或者也可以是完全不同的程序）。Linux系统下的多线程遵循POSIX线程接口，称为pthread。编写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=pthread_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);我们编译此程序：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 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;它是一个线程的标识符。函数pthread_create用来创建一个线程，它的原型为：extern int pthread_create _P (pthread_t *_thread, _const pthread_attr_t *_attr,void *(*_start_routine) (void *), void *_arg);第一个参数为指向线程标识符的指针，第二个参数用来设置线程属性，第三个参数是线程运行函数的起始地址，最后一个参数是运行函数的参数。这里，我们的函 数thread不需要参数，所以最后一个参数设为空指针。第二个参数我们也设为空指针，这样将生成默认属性的线程。对线程属性的设定和修改我们将在下一节 阐述。当创建线程成功时，函数返回0，若不为0则说明创建线程失败，常见的错误返回代码为EAGAIN和EINVAL。前者表示系统限制创建新的线程，例如线程数目过多了；后者表示第二个参数代表的线程属性值非法。创建线程成功后，新创建的线程则运行参数三和参数四确定的函数，原来的线程则继续运行下一行代码。函数pthread_join用来等待一个线程的结束。函数原型为：extern int pthread_join _P (pthread_t _th, void *_thread_return);第一个参数为被等待的线程标识符，第二个参数为一个用户定义的指针，它可以用来存储被等待线程的返回值。这个函数是一个线程阻塞的函数，调用它的函数将 一直等待到被等待的线程结束为止，当函数返回时，被等待线程的资源被收回。一个线程的结束有两种途径，一种是象我们上面的例子一样，函数结束了，调用它的 线程也就结束了；另一种方式是通过函数pthread_exit来实现。它的函数原型为：extern void pthread_exit _P (void *_retval) _attribute_ (_noreturn_);唯一的参数是函数的返回代码，只要pthread_join中的第二个参数thread_return不是NULL，这个值将被传递给 thread_return。最后要说明的是，一个线程不能被多个线程等待，否则第一个接收到信号的线程成功返回，其余调用pthread_join的线 程则返回错误代码ESRCH。2.1.5内核定时器机制的实现2.1.5.1动态定时器机制的初始化 函数init_timervecs()实现对动态定时器机制的初始化。该函数仅被sched_init()初始化例程所调用。动态定时器机制初始化过程的主要任务就是将tv1、tv2、tv5这5个结构变量中的定时器向量指针数组vec初始化为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 * vec; 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 long) 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(&timer-list); return; /* * Timers are FIFO! */ list_add(&timer-list, vec-prev); 对该函数的注释如下： （1）首先，计算定时器的expires值与timer_jiffies的插值（注意！这里应该使用动态定时器自己的时间基准），这个差值就表示这个定时器相对于上一次运行定时器机制的那个时刻还需要多长时间间隔才到期。局部变量idx保存这个差值。 （2）根据idx的值确定这个定时器应被插入到哪一个定时器向量中。其具体的确定方法我们在7.6.2节已经说过了，这里不再详述。最后，定时器向量的头部指针vec表示这个定时器应该所处的定时器向量链表头部。 （3）最后，调用list_add()函数将定时器插入到vec指针所指向的定时器队列的尾部。 2.1.5.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(&timerlist_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值重新插入到相应的链表中。 函数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.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）。结构类型timeval的指针参数tv指向接受时间信息的用户空间缓冲区，参数tz是一个timezone结构类型的指针，指向接收时区信息的用户空间缓冲区。这两个参数均为输出参数，返回值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_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用来创建一个线程，函数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,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);3.3程序流程图：4. 源代码（附录）5.运行结果以运行情况运行截图如下：6. 调试记录rootlocalhost # gcc 050119.c050119.c: In function pthread:050119.c:17: 警告：隐式声明与内建函数 exit 不兼容/tmp/ccarv1uC.o: In function pthread:050119.c:(.text+0x4d): undefined reference to pthread_create050119.c:(.text+0xa0): undefined reference to pthread_joincollect2: ld 返回 1分析得知，编写Linux下的多线程程序，需要使用头文件pthread.h，连接时需要使用库libpthread.a，加编译参数-lpthread。7. 自我评价和总结：经过这次操作系统课程设计，让我真正理解了Linux内核定时器的本质。虽然过程中遇到了困难，但是通过上网查阅资料很好的解决了问题。本程序是在Linux系统平台下运行的。但是原来的实现只能是time_t mytime形式的，经过简单的localtime(mytime)和ctime(&mytime)处理.精度是不够的，为了返回高精度的时间，这里使用了gettimeofday函数。其程序结构相对简单，实现了题目的基本要求，测量了多线程的进程执行时间。 进行多线程程序设计时，使用到了两个函数，pthread_create和pthread_join，并声明了一个pthread_t型的变量。pthread_t在头文件/