实验1：Alarm-Clock指导手册

1、 西安电子科技大学 操作系统课程设计实验指导手册名称Alarm-Clock作者西电Linux研究小组创建时间2013-09-20修改时间2013-10-221.任务描述源代码devices/timer.c中有一个timer_sleep()函数。定义如下：该函数的功能是让调用它的线程睡眠一段时间(ticks)，然后唤醒。事实上，Pintos已经实现该函数，只是使用的是“忙等待”的方法(见while循环)。本实验的要求：重新实现timer_sleep( )函数，避免“忙等待”的发生（策略有多种，请大家设计一种并实现即可）2.背景知识2.1源码阅读为顺利完成本实验，你至少需要阅读以下源代码文件(并非

2、每一行都要读懂)，并了解其中关键数据结构和函数的含义，它们是：./src/threads/目录下：- thread.h, thread.c：有关线程初始化、阻塞、解除阻塞，线程调度等内容；- interrupt.h, interrupt.c：与中断有关的处理函数。./src/devices/目录下：- timer.h, timer.c：本实验要修改的time_sleep( )函数就在其中，同时请注意理解定时器中断的处理过程。2.1.1线程数据结构在thread.h中定义了一个结构体struct thread，这个结构体用于存放线程的基本信息，实验中可能(依你的方案而定)需要修改/扩充此结构。请

3、注意enum thread_status这个枚举类型的变量，用于表示线程当前所处的状态。2.1.2线程状态Pintos中线程的状态有四种，在threads.h中定义如下：2.1.3中断要完成Alarm_clock任务，你还需要对Pintos中有关线程切换的过程比较熟悉。这对于后面的实验也很重要。为了帮助大家更快地读懂这些代码，这里把Pintos中定时器中断与线程切换的过程做一小结。l 定时器中断(timer interrupt)在操作系统原理课程的学习中，我们知道，多线程的并发执行是通过把CPU按时间片轮流分配给各个线程来实现的，Pintos也不例外。在Pintos中，定时器中断频率定义为TI

4、MER_FREQ，也就是说，每秒有TIMER_FREQ个定时器中断。在time.h中定义为：由此可知一个定时器中断的时长大约为10ms，这里称为一个ticks。Pintos中一个时间片的长度 = 4*ticks 40ms。当一个线程运行了一个时间片后，它必须放弃处理器给其它的线程。那么系统是如何知道当前线程的运行时间，以及何时进行线程切换呢？现在我们便来进行一个分析。事实上，当每个定时器中断(ticks)到来时，便会引发一次中断，系统对于这种中断的处理过程为：（1） 通过中断管理器(汇编代码)调用intr_handker( )函数；（2） 由intr_handler( )调用timer_int

5、errupt( )函数。timer_interrupt( )原型为(timer.c中)：全局变量ticks的含义：记录从系统启动到当前时刻总的定时器中断次数。可以看出该函数的功能为：将全局变量ticks+; 然后调用thread_tick( )函数。（3） thread_tick( )函数（thread.c中）代码如下：我们暂且仅关心阴影部分代码，可以看出，该函数会使得thread_ticks变量加1，如果增加后的thread_ticks变量值不大于4(一个时间片)，则返回。否则，则调用intr_yield_on_return( )函数。thread_ticks和TIME_SLICE变量定义如

6、下：（4） intr_yield_on_return( )函数该函数的功能为将yield_on_return变量置为true，并返回intr_handler( )函数，定义如下：intr_handler( )中相关代码如下：可以看出，当yield_on_return为true时，将调用thread_yield( )函数。（5） thread_yield( )函数，代码如下(thread.c中)：该函数的功能为：迫使当前线程(非idle线程)放弃CPU，使其进入ready_list末尾排队，并通过schedule( )函数调度下一个线程执行。l 线程切换（1） schedule( )函数定义如下

7、：可以看到该函数通过next_thread_to_run( )来选择下一个运行线程。由于现在还没有优先级概念，此时ready_list为FIFO结构，因此选择的线程即为ready_list中头部的线程。next_thread_to_run( )函数定义如下：其中list_pop_front( )函数的功能为从ready_list中选择最前的结点(线程)，并移除。list_entry( )函数的功能是进行指针格式转换，使得LIST_ELEM转换为thread指针。至此，系统已经为我们选好了下一个将要执行的线程。如果该线程符合要求，则执行switch_threads( )函数。（2） switch

8、_threads( )函数(threads/switch.h)switch_threads( )函数的功能为将一个线程放到CPU上执行(上下文切换)，定义如下：其实现为汇编代码（switch.S），这里不再详述，有兴趣的同学科自行研究。函数执行结束后，CPU上已经放上了即将运行的线程，此时还需要调用thread_schedule_tail( )函数进行收尾工作。（3） thread_schedule_tail( )函数定义如下：函数将新线程的状态由ready态改为running，并初始化时间片(thead_ticks)，执行完毕后线程切换过程结束。2.1.3其它基本操作（函数）：主要集中在th

9、reads/thread.c中：l thread_current()：获取当前的线程的指针。l thread_foreach(thread_action_func *func, void *aux)：遍历当前all list中的所有线程，并且对于每一个线程执行一次func操作（注意到这里的func是一个任意给定函数的指针，参数aux则是你想要传给这个函数的参数）。实际上Pintos中所有的线程被保存在一个链表(all_list)中，这个函数做得不过是遍历了一遍链表而已。注意这个函数只能在中断关闭的时候调用。l thread_block()和thread_unblock(thread *t)：这

10、是一对儿函数，区别在于第一个函数的作用是把当前占用CPU的线程阻塞掉（放到waiting queue里面）；第二个函数作用是将已经被阻塞掉的进程t唤醒到ready队列中。l intr_disable ( )：这个函数在interrupt.c中，作用是返回关中断，然后返回中断关闭前的状态。l timer_ticks( )：返回自从系统启动经过的时间量(以ticks为单位)。l timer_elapsed( )：返回自某个时刻起经过的时间量（以ticks为单位）。3.改进方案（此方案仅供参考，鼓励大家开动脑筋，设计出不同的方案来）3.1分析让我们再次审视timer_sleep( )函数：可以看出造

11、成忙等待原因在于：（1） 它是通过一个while循环来不断检测当前经过的时间是否已经达到了预期时间(注意这个的ticks变量为局部变量，要与全局变量ticks区别开来)来达到让线程等待ticks时间的目的；（2） timer_elapse( )函数只在一个定时器中断到达时才加1。由此我们知道在一个定时器中断时间内，while循环将会执行多次，从而形成“忙等待”。要避免“忙等待”，需要把timer_sleep( )函数中的while循环替换掉。3.2设计考虑在timer_sleep( )函数中让进程暂时阻塞(thread_block( )，然后等待ticks个定时器中断周期结束以后再去唤醒它(t

12、hread_unblock( )。当然，这个“等”不再使用循环来实现，而是在每个定时器中断到来后去检查一下wait_list中的线程，看是否已经到了唤醒的时机。如果时机已到，马上将其唤醒(进入ready_list)；如反之则不做任何操作。没有了循环调用，其他线程就可以充分在CPU上运行。那么如何在每个定时器中断到来时去检查wait_list呢？我们可以通过改进timer_interrup( )函数实现：加入遍历链表的操作，检查每个线程等待的时间。还有一个问题需要解决：怎么样才能知道一个线程被阻塞了多长时间？事实上，Pintos自身没有提供这样的信息，因此需要对thread这个结构体进行改造，可加入一个整形变量来记录当前线程需要等待的时间，之后每次中断的时候检查一次，并自减1，当它等于0时，意味着等待结束，将其调入ready_list。基本原理图如下：3.3实现请大家尝试自行完成（鼓励采用新思想，新策略实现）。4.结果测试完成代码改写后，大家可以进