06时间片轮转调度

《操作系统》实验报告实验题目时间片轮转调度学生姓名lee学号专业班级指导教师院系名称计算机与信息学院2017年10月30日实验6时间片轮转调度1.实验目的与要求调试EOS的线程调度程序，熟悉基于优先级的抢先式调度。为EOS添加时间片轮转调度，了解其它常用的调度算法。2.实验原理阅读本书第5章中的第5.4节。重点理解EOS当前使用的基于优先级的抢先式调度，调度程序执行的时机和流程，以及实现时间片轮转调度的细节。3.实验内容3.1准备实验按照下面的步骤准备实验：1.启动OSLab。2.新建一个EOSKernel项目。3.2阅读控制台命令“rr”相关的源代码阅读ke/sysproc.c文件中第690行的ConsoleCmdRoundRobin函数，及该函数用到的第649行的ThreadFunction函数和第642行的THREAD_PARAMETER结构体，学习“rr”命令是如何测试时间片轮转调度的。在阅读的过程中需要特别注意下面几点：在ConsoleCmdRoundRobin函数中使用ThreadFunction函数做为线程函数，新建了20个优先级为8的线程，做为测试时间片轮转调度用的线程。在新建的线程中，只有正在执行的线程才会在控制台的对应行（第0个线程对应第0行，第1个线程对应第1行）增加其计数，这样就可以很方便的观察到各个线程执行的情况。控制台对于新建的线程来说是一种临界资源，所以，新建的线程在向控制台输出时，必须使用“关中断”和“开中断”进行互斥（参见ThreadFunction函数的源代码）。由于控制台线程的优先级是24，高于新建线程的优先级8，所以只有在控制台线程进入“阻塞”状态后，新建的线程才能执行。新建的线程会一直运行，原因是在ThreadFunction函数中使用了死循环，所以只能在ConsoleCmdRoundRobin函数的最后调用TerminateThread函数来强制结束这些新建的线程。按照下面的步骤执行控制台命令“rr”，查看其在没有时间片轮转调度时的执行效果：1.按F7生成在本实验3.1中创建的EOSKernel项目。2.按F5启动调试。3.待EOS启动完毕，在EOS控制台中输入命令“rr”后按回车。命令开始执行后，观察其执行效果（如图1），会发现并没有体现“rr”命令相关源代码的设计意图。通过之前对这些源代码的学习，20个新建的线程应该在控制台对应的行中轮流地显示它们的计数在增加，而现在只有第0个新建的线程在第0行显示其计数在增加，说明只有第0个新建的线程在运行，其它线程都没有运行。造成上述现象的原因是：所有20个新建线程的优先级都是8，而此时EOS只实现了基于优先级的抢先式调度，还没有实现时间片轮转调度，所以至始至终都只有第0个线程在运行，而其它具有相同优先级的线程都没有机会运行，只能处于“就绪”状态。图1：没有时间片轮转调度时“rr”命令的执行效果3.3调试线程调度程序在为EOS添加时间片轮转调度之前，先调试一下EOS的线程调度程序PspSelectNextThread函数，学习就绪队列、就绪位图以及线程的优先级是如何在线程调度程序中协同工作的，从而加深对EOS已经实现的基于优先级的抢先式调度的理解。3.3.1调试当前线程不被抢先的情况正像图1中显示的，新建的第0个线程会一直运行，而不会被其它同优先级的新建线程或者低优先级的线程抢先。按照下面的步骤调试这种情况在PspSelectNextThread函数中处理的过程。1.结束之前的调试。2.在ke/sysproc.c文件的ThreadFunction函数中，调用fprintf函数的代码行（第680行）添加一个断点。3.按F5启动调试。4.待EOS启动完毕，在EOS控制台中输入命令“rr”后按回车。“rr”命令开始执行后，会在断点处中断。5.查看ThreadFunction函数中变量pThreadParameter-Y的值应该为0，说明正在调试的是第0个新建的线程。图2执行效果6.激活虚拟机窗口，可以看到第0个新建的线程还没有在控制台中输出任何内容，原因是fprintf函数还没有执行。7.激活OSLab窗口后按F5使第0个新建的线程继续执行，又会在断点处中断。再次激活虚拟机窗口，可以看到第0个新建的线程已经在控制台中输出了第一轮循环的内容。可以多按几次F5查看每轮循环输出的内容。图3第一轮循环通过之前的调试，可以观察到第0个新建的线程执行的情况。按照下面的步骤调试，查看当有中断发生从而触发线程调度时，第0个新建的线程不会被抢先的情况。1.在ps/sched.c文件的PspSelectNextThread函数中，调用BitScanReverse函数扫描就绪位图的代码行（第384行）添加一个断点。2.按F5继续执行，当有定时计数器中断发生时（每10ms一次），就会在新添加的断点处中断。3.在“调试”菜单的“窗口”中选择“监视”，激活“监视”窗口（此时按F1可以获得关于“监视”窗口的帮助）。4.在“监视”窗口中添加表达式“/tPspReadyBitmap”，以二进制格式查看就绪位图的值。此时就绪位图的值应该为100000001，表示优先级为8和0的两个就绪队列中存在就绪线程。（注意，如果就绪位图的值不是100000001，就继续按F5，直到就绪位图变为此值）。5.在“调试”菜单中选择“快速监视”，在“快速监视”对话框的“表达式”中输入表达式“*PspCurrentThread”后，点击“重新计算”按钮，可以查看当前正在执行的线程（即被中断的线程）的线程控制块中各个域的值。其中优先级（Priority域）的值为8；状态（State域）的值为2（运行态）；时间片（RemainderTicks域）的值为6；线程函数（StartAddr域）为ThreadFunction。综合这些信息即可确定当前正在执行的线程就是新建的第0个线程。关闭“快速监视”对话框。图4快速“监视”窗口6.在“监视”窗口中添加表达式“ListGetCount(&PspReadyListHeads[8])”，查看优先级为8的就绪队列中就绪线程的数量，值为19。说明除了正在执行的第0个新建的线程外，其余19个新建的线程都在优先级为8的就绪队列中。ListGetCount函数在文件rtl/list.c中定义。7.按F10单步调试，BitScanReverse函数会从就绪位图中扫描最高优先级，并保存在变量HighestPriority中。查看变量HighestPriority的值为8。图5“监视”窗口8.继续按F10单步调试，直到在PspSelectNextThread函数返前停止（第465行），注意观察线程调度执行的每一个步骤。第0个新建的线程在执行线程调度时没有被抢先的原因可以归纳为两点：(1)第0个新建的线程仍然处于“运行”状态。(2)没有比其优先级更高的就绪线程。3.3.2调试当前线程被抢先的情况如果有比第0个新建的线程优先级更高的线程进入就绪状态，则第0个新建的线程就会被抢先。按照下面的步骤调试这种情况在PspSelectNextThread函数中处理的过程（注意，接下来的调试要从本实验3.3.1调试的状态继续调试，所以不要结束之前的调试）。1.选择“调试”菜单中的“删除所有断点”，删除之前添加的所有断点。2.在ps/sched.c文件的PspSelectNextThread函数的第395行添加一个断点。3.按F5继续执行，激活虚拟机窗口，可以看到第0个新建的线程正在执行。4.在虚拟机窗口中按下一次空格键，EOS会在之前添加的断点处中断。5.在“监视”窗口中查看就绪位图的值为1000000000000000100000001，说明此时在优先级为24的就绪队列中存在就绪线程。在“监视”窗口中添加表达式“ListGetCount(&PspReadyListHeads[24])”，其值为1，说明优先级为24的就绪队列中只有一个就绪线程。扫描就绪位图后获得的最高优先级的值HighestPriority也就应该是24。图6“监视”窗口就绪位图为10000000000000001000000016.按F10单步调试一次，执行的语句会将当前正在执行的第0个新建的线程，放入优先级为8的就绪队列的队首。“监视”窗口中显示的优先级为8的就绪队列中的线程数量就会增加1，变为20。图7“监视”窗口线程数量7.继续按F10单步调试，直到在第444行中断执行，注意观察线程调度执行的每一个步骤。此时，正在执行的第0个新建的线程已经进入了“就绪”状态，让出了CPU。线程调度程序接下来的工作就是选择优先级最高的非空就绪队列的队首线程作为当前运行线程，也就是让优先级为24的线程在CPU上执行。8.按F10单步调试一次，当前线程PspCurrentThread指向了优先级为24的线程。可以在“快速监视”窗口中查看表达式“*PspCurrentThread”的值，注意线程控制块中StartAddr域的值为IopConsoleDispatchThread函数（在文件io/console.c中定义），说明这个优先级为24的线程是控制台派遣线程。图8快速“监视”窗口9.继续按F10单步调试，直到在PspSelectNextThread函数返回前（第465行）中断执行，注意观察线程调度执行的每一个步骤。此时，优先级为24的线程已经进入了“运行”状态，在中断返回后，就可以开始执行了。在“监视”窗口中，就绪位图的值变为100000001，优先级为24的就绪队列中线程的数量变为0，就绪位图和就绪队列都是在刚刚被调用过的PspUnreadyThread函数（在文件ps/sched.c中定义）内更新的。图9“监视”窗口10.删除所有断点后结束调试。3.4为EOS添加时间片轮转调度3.4.1要求修改ps/sched.c文件中的PspRoundRobin函数(第337行)，在其中实现时间片轮转调度算法。代码如下：VOIDPspRoundRobin(VOID)/*++功能描述：时间片轮转调度函数，被定时计数器中断服务程序KiIsrTimer调用。参数：无。返回值：无。--*/{//在此添加代码，实现时间片轮转调度算法。if(NULL!=PspCurrentThread&&Running==PspCurrentThread-State){PspCurrentThread-RemainderTicks--;if(0==PspCurrentThread-RemainderTicks){PspCurrentThread-RemainderTicks=TICKS_OF_TIME_SLICE;if(BIT_TEST(PspReadyBitmap,PspCurrentThread-Priority)){PspReadyThread(PspCurrentThread);}}}//return;}3.4.2测试方法1.代码修改完毕后，按F7生成EOS内核项目。2.按F5启动调试。3.在EOS控制台中输入命令“rr”后按回车。应能看到20个线程轮流执行的效果，如图10。图10：进行时间片轮转调度时“rr”命令的执行效果3.4.3提示PspRoundRobin函数具体的流程可以参考图5-11。在PspRoundRobin函数中，全局变量PspCurrentThread指向的线程控制块就是被定时计数器中断的线程的线程控制块，通过对PspCurrentThread指向的线程控制块的各个域进行修改，就可以改变被中断线程的各种属性。全局变量PspCurrentThread的定义参见ps/sched.c的第45行。线程控制块结构体的定义参见ps/psp.h的第58行。被中断线程的状态有可能不是“运行”状态，而是“阻塞”状态。所以，在进行时间片轮转调度前，要先判断一下被中断线程是否仍处于“运行”状态。只有当被中断线程仍处于“运行”状态时，才需要进行时间片轮转调度。在PspRoundRobin函数中的第一行代码可以如下