操作系统课程设计内核定时器|江阴雨辰互联

2023年8月2日发(作者：)

学号：

课程设计

题目

学院

专业

班级

姓名

指导教师

内核定时器

计算机学院

软件工程

刘军

2013

年

月

日

课程设计任务书

学生姓名：专业班级：软件zy1101

指导教师：刘军工作单位：计算机科学与技术学院

题目: 内核定时器

初始条件：

1操作系统：Linux 或者 windows

2程序设计语言：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, 可以被抢占，信号量可以设置为同时允许的进程数。

关键字：

内核的时间管理算法内核定时器执行时间多线程程序

1．设计题目和要求

设计题目：内核定时器

设计要求：通过研究内核的时间管理算法，学习内核源代码；然后应用这些知识并且使用“信号”建立一种用户空间机制来测量一个多线程程序的执行时间

2.1.1Linux 内核定时器

定时器是管理内核时间的基础，用来计算流逝的时间，它以某种频率（节拍率）自行触发时钟中断，当时钟中断发生时，内核就通过一种特殊中断处理程序对其进行处理。

但是原来的实现只能是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 = _sec;

usec += _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_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=_sec，usec=_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)

{

/* 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是进程用来设定某个信号的处理方法，系统调用kill是用来发送信号给指定进程的。这两个调用可以形成信号的基本操作。后两个调用pause和alarm是通过信号实现的进程暂停和定时器，调用alarm是通过信号通知进程定时器到时。所以在这里，我们还要介绍这两个调用。

信号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多线程编程

进程和线程都是操作系统的概念。进程是应用程序的执行实例，每个进程是由私有的虚拟地址空间、代码、数据和其它各种系统资源组成，进程在运行过程中创建的资源随着进程的终止而被销毁，所使用的系统资源在进程终止时被释放或关闭。

线程是进程内部的一个执行单元。系统创建好进程后，实际上就启动执行了该进程的主执行线程，主执行线程以函数地址形式，比如说main或WinMain函数，将程序的启动点提供给Windows系统。主执行线程终止了，进程也就随之终止。

每一个进程至少有一个主执行线程，它无需由用户去主动创建，是由系统自动创建的。用户根据需要在应用程序中创建其它线程，多个线程并发地运行于同一个进程中。一个进程中的所有线程都在该进程的虚拟地址空间中，共同使用这些虚拟地址空间、全局变量和系统资源，所以线程间的通讯非常方便，多线程技术的应用也较为广泛。

多线程可以实现并行处理，避免了某项任务长时间占用CPU时间。要说明的一点是，目前大多数的计算机都是单处理器（CPU）的，为了运行所有这些线程，操作系统为每个独立线程安排一些CPU时间，操作系统以轮换方式向线程提供时间片，这就给人一种假象，好象这些线程都在同时运行。由此可见，如果两个非常活跃的线程为了抢夺对CPU的控制权，在线程切换时会消耗很多的CPU资源，反而会降低系统的性能。这一点在多线程编程时应该注意。

多线程是计算机同时运行多个执行线程的能力（这些线程可以是同一程序的组成部分，或者也可以是完全不同的程序）。Linux系统下的多线程遵循POSIX线程接口，称为pthread。编写Linux下的多线程程序，需要使用头文件pthread.h，连接时需要使用库libpthread.a。而Linux下pthread的实现是通过系统调用clone（）来实现的。clone（）是Linux所特有的系统调用，它的使用方式类似fork。下面展示多线程程序部分050119.c。

/* 050119.c */

„„

#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(&id,NULL,(void *) thread,NULL); 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

运行，我们得到如下结果：

This is the main process.

This is a pthread.

This is the main process.

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.4内核动态定时器机制的实现

在内核动态定时器机制的实现中，有三个操作时非常重要的：

（1）将一个定时器插入到它应该所处的定时器向量中。

（2）定时器的迁移，也即将一个定时器从它原来所处的定时器向量迁移到另一个定时器向量中。

（3）扫描并执行当前已经到期的定时器。

2.1.5 动态定时器机制的初始化

函数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( + i);

INIT_LIST_HEAD( + i); INIT_LIST_HEAD( + i); INIT_LIST_HEAD( + i); }

for (i = 0; i < TVR_SIZE; i++) INIT_LIST_HEAD( + i); }

上述函数中的宏TVN_SIZE是指timer_vec结构类型中的定时器向量指针数组vec［］的大小，值为64。

宏TVR_SIZE是指timer_vec_root结构类型中的定时器向量数组vec［］的大小，值为256。