试验1Alarm-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中定时器中断与线程切换的过程做一小结。定时器中断 (timer interrupt)在操作系统原理课程的学习中， 我们知道， 多线程的并发执行是通过把 CPU按时间片轮 流分配给各个线程

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

5、(汇编代码 ) 调用 intr_handker( ) 函数；( 2) 由 intr_handler( ) 调用 timer_interrupt( ) 函数。timer_interrupt( ) 原型为 (timer.c中 )：全局变量 ticks的含义：记录从系统启动到当前时刻总的定时器中断次数。 可以看出该函数的功能为：将全局变量 ticks+; 然后调用 thread_tick( ) 函数。( 3) thread_tick( ) 函数( thread.c中)代码如下：我们暂且仅关心阴影部分代码，可以看出，该函数会使得thread_ticks 变量加 1，如果增加后的 thread_tick

6、s 变量值不大于 4(一个时间片 )，则返回。否则，则调用 intr_yield_on_return( ) 函数。thread_ticks 和TIME_SLICE 变量定义如下：4) intr_yield_on_return( ) 函数该函数的功能为将 yield_on_return 变量置为 true ，并返回 intr_handler( ) 函数，定义如下：intr_handler( ) 中相关代码如下：可以看出，当 yield_on_return 为 true时，将调用 thread_yield( ) 函数。5) thread_yield( ) 函数，代码如下 (thread.c中) ：

7、该函数的功能为： 迫使当前线程 (非idle线程 )放弃 CPU ，使其进入 ready_list末尾排队， 并通过 schedule( )函数调度下一个线程执行。线程切换1) schedule( )函数定义如下：可以看到该函数通过 next_thread_to_run( ) 来选择下一个运行线程。 由于现在还没有优先 级概念，此时 ready_list 为FIFO结构，因此选择的线程即为 ready_list 中头部的线程。next_thread_to_run( ) 函数定义如下：其中 list_pop_front( ) 函数的功能为从 ready_list 中选择最前的结点 (线程 )，并

8、移除。list_entry( ) 函数的功能是进行指针格式转换，使得 LIST_ELEM 转换为 thread指针。 至此，系统已经为我们选好了下一个将要执行的线程。如果该线程符合要求，则执行switch_threads( ) 函数。(2) switch_threads( ) 函数 (threads/switch.h)switch_threads( ) 函数的功能为将一个线程放到 CPU上执行 (上下文切换 )，定义如下：其实现为汇编代码( switch.S )，这里不再详述，有兴趣的同学科自行研究。 函数执行结束后， CPU 上已经放上了即将运行的线程，此时还需要调用 thread_sche

9、dule_tail( ) 函数进行收尾工作。(3) thread_schedule_tail( ) 函数定义如下：函数将新线程的状态由 ready态改为 running ，并初始化时间片 (thead_ticks) ，执行完毕后 线程切换过程结束。2.1.3 其它基本操作(函数)主要集中在 threads/thread.c 中：thread_current()：获取当前的线程的指针。thread_foreach(thread_action_func *func, void *aux) ：遍历当前 all list 中的所有线程，并 且对于每一个线程执行一次 func 操作(注意到这里的 fun

10、c 是一个任意给定函数的指针， 参数 aux 则是你想要传给这个函数的参数) 。实际上 Pintos 中所有的线程被保存在一个 链表(all_list) 中，这个函数做得不过是遍历了一遍链表而已。注意这个函数只能在中断 关闭的时候调用。thread_block() 和 thread_unblock(thread *t) ：这是一对儿函数，区别在于第一个函数的作 用是把当前占用 CPU 的线程阻塞掉(放到 waiting queue 里面)；第二个函数作用是将 已经被阻塞掉的进程 t 唤醒到 ready 队列中。intr_disable ( ) ：这个函数在 interrupt.c 中，作用是返

11、回关中断，然后返回中断关闭前的 状态。timer_ticks( ) ：返回自从系统启动经过的时间量 (以 ticks 为单位 )。timer_elapsed( ) ：返回自某个时刻起经过的时间量(以ticks 为单位)。3.改进方案(此方案仅供参考，鼓励大家开动脑筋，设计出不同的方案来)3.1分析让我们再次审视 timer_sleep( ) 函数：可以看出造成忙等待原因在于：1)它是通过一个 while 循环来不断检测当前经过的时间是否已经达到了预期时间 (注意这个的 ticks变量为局部变量， 要与全局变量 ticks 区别开来 )来达到让线程等待 ticks时间的目的；2)timer_el

12、apse( ) 函数只在一个定时器中断到达时才加 1。由此我们知道在一个定时器中断时间内， while 循环将会执行多次， 从而形成“忙等待”。 要避免“忙等待”，需要把 timer_sleep( ) 函数中的 while 循环替换掉。3.2设计考虑在 timer_sleep( )函数中让进程暂时阻塞 (thread_block( ) ，然后等待 ticks 个定时器中 断周期结束以后再去唤醒它 (thread_unblock( ) 。当然，这个“等”不再使用循环来实现，而 是在每个定时器中断到来后去检查一下wait_list 中的线程，看是否已经到了唤醒的时机。如果时机已到，马上将其唤醒 (

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