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

摘要摘要 1 1设计题目与要求设计题目与要求 2 1 1 1 1 设计题目设计题目 内核定时器 2 1 1 2 2 设计要求设计要求 通过研究内核的时间管理算法 学习内核源代码 然后应用这些知识并且 使用 信号 建立一种用户空间机制来测量一个多线程程序的执行时间 2 2 2 总的设计思想及系统平台 语言 工具总的设计思想及系统平台 语言 工具 2 2 1设计思想 2 2 1 1Linux内核对定时器的描述 2 2 1 2Linux 内核定时器 3 2 1 3Linux 信号signal处理机制 6 2 1 4多线程编程 7 2 1 5内核定时器机制的实现 9 2 2 系统平台 12 2 3 编程工具 12 3 数据结构与模块说明 功能与流程图 数据结构与模块说明 功能与流程图 12 3 1 定时器使用 12 3 2 多线程程序 13 3 3 程序流程图 14 4 4 源程序 源程序 14 5 5 运行结果与运行情况 运行结果与运行情况 15 6 6 调试记录 调试记录 16 7 7 自我评析和总结 自我评析和总结 17 8 8 参考文献参考文献 17 内核定时器内核定时器 摘要摘要 每个正在系统上运行的程序都是一个进程 每个进程包含一到多个线程 进程也可能是 整个程序或者是部分程序的动态执行 线程是一组指令的集合 或者是程序的特殊段 它可 以在程序里独立执行 也可以把它理解为代码运行的上下文 内核时间指明线程执行操作系 统代码已经经过了多少个 100ns 的 CPU 时间 linux 是一个具有保护模式的操作系统 它一 直工作在 i386 cpu 的保护模式之下 内存被分为两个单元 内核区域和用户区域 一般地 在使用虚拟内存技术的多任务系统上 内核和应用有不同的地址空间 因此 在内核和应用 之间以及在应用与应用之间进行数据交换需要专门的机制来实现 本文站在用户空间的角度 测试一个多线程程序的程序执行时间 当一个进程希望获得信号量时 如果信号量已经被占 有 则该进程将会被放到等待队列上 sleep 直到 cpu 将其唤醒 相对于 spinlock 来说开销太大 适用于长时间占有的 lock 不可用于中断状态 因为它拥有信号量的进程可以 sleep 可以被 抢占 信号量可以设置为同时允许的进程数 1设计题目与要求设计题目与要求 1 1 设计题目 内核定时器 1 2 设计要求 通过研究内核的时间管理算法 学习内核源代码 然后应用这些知识并 且使用 信号 建立一种用户空间机制来测量一个多线程程序的执行时间 2 2 总的设计思想及系统平台 语言 工具 2 12 1设计思想 2 1 1Linux 内核对定时器的描述 Linux 在 include linux timer h 头文件中定义了数据结构 timer list 来描述一个内核定 时器 struct timer list struct list head list unsigned long expires unsigned long data void function unsigned long 各数据成员的含义如下 1 双向链表元素 list 用来将多个定时器连接成一条双向循环队列 2 expires 指定定时器到期的时间 这个时间被表示成自系统启动以来的时钟滴答计 数 也即时钟节拍数 当一个定时器的 expires 值小于或等于 jiffies 变量时 我们就说这 个 定时器已经超时或到期了 在初始化一个定时器后 通常把它的 expires 域设置成当前 expires 变量的当前值加上某个时间间隔值 以时钟滴答次数计 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 由于定时器通常被连接在一个双向循环队列中等待执行 此时我们说定时器处于 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 之后 就意味 着 时间值 a b 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 do gettimeofday if copy to user tv if tz if copy to user tz 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 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 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 usec offset usec lost usec jiffies wall jiffies TICK SIZE jiffies wall jiffies 1000000 HZ 由于全局变量 last tsc low 表示上一次时钟中断服务函数 timer interrupt 执行时刻的 CPU TSC 寄存器的值 因此我们可以用 X86 CPU 的 TSC 寄存器来计算 offset usec 的值 也即 offset usec delay at last interrupt current tsc low last 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 是否已经溢出而超过 106us 1 秒 如果溢出 则将 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 让局部变量 eax tsc low eax last tsc low 也即计算当前时刻的 TSC 值与上一次 时钟中断服务函数 timer interrupt 执行时的 TSC 值之间的差值 3 显然 从上一次 timer interrupt 到当前时刻的时间间隔就是 tsc low fast gettimeoffset quotient 因此用一条 mul 指令来计算这个乘法表达式的值 4 返回值 delay at last interrupt tsc low fast 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 i 3 i printf This is a pthread n int pthread void pthread t id int i ret ret pthread create if ret 0 printf Create pthread error n exit 1 for i 0 i 3 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 vec tv1 vec i else if idx 1 TVR BITS vec tv2 vec i else if idx 1 TVR BITS TVN BITS vec tv3 vec i else if idx 1 TVR BITS 2 TVN BITS 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 vec tv5 vec i else Can only get here on architectures with 64 bit jiffies INIT LIST HEAD return Timers are FIFO list add 对该函数的注释如下 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 timer expires expires ret detach timer timer internal add timer timer spin unlock irqrestore 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 return 1 2 2 系统平台 系统平台 一台 Linux 主机且有超级用户权限 2 3 编程工具 编程工具 VI 编辑器 Gedit 编辑器 3 数据结构与模块说明 功能与流程图 数据结构与模块说明 功能与流程图 3 1 定时器使用 int gettimeofday struct timeval tv struct timezone tz strut timeval long 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 pthread gettimeofday timeuse 1000000 tpend tv sec tpstart tv sec tpend tv usec tpstart tv usec timeuse 1000000 printf Used Time f sec n 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 pthread join id NULL void thread void int i for i 0 i 3 i printf This is a pthread n int pthread void pthread t id 声明了一个 pthread t 型的变量 int i ret ret pthread create if ret 0 printf Create pthread error n exit 1 for i 0 i 3 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 pthread join id NULL strut timeval long tv sec 秒数 long tv usec 微秒数 void thread void int i for i 0 i 3 i printf This is a pthread n int pthread void pthread t id 声明了一个pthread t型的变量 int i ret ret pthread create if ret 0 printf Create pthread error n exit 1 for i 0 i 3 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 pthread gettimeofday timeuse 1000000 tpend tv sec tpstart tv sec tpend tv usec tpstart tv usec timeuse 1000000 printf Used Time f sec n timeuse exit 0 5 5 运行结果与运行情况 运行结果与运行情况 运行截图如下 运行结果记录如下 root localhost gcc 050119 c lpthread o 050119 out 050119 c In function pthread 050119 c 17 警告 隐式声明与内建函数 exit 不兼容 root localhost 050119 out This is the main process This is the main process This is the main process This is a pthread