06时间片轮转调度

《06时间片轮转调度》由会员分享，可在线阅读，更多相关《06时间片轮转调度（14页珍藏版）》请在金锄头文库上搜索。

1、操作系统操作系统实验报告实验报告实验题目实验题目 时间片轮转调度时间片轮转调度 学生姓名学生姓名 lee 学学 号号 专业班级专业班级 指导教师指导教师 院系名称院系名称 计算机与信息学院计算机与信息学院 2017 年年 10 月月 30 日日实验实验 6 时间片轮转调度时间片轮转调度1. 实验目的与要求实验目的与要求调试EOS的线程调度程序，熟悉基于优先级的抢先式调度。 为 EOS 添加时间片轮转调度，了解其它常用的调度算法。2. 实验原理实验原理阅读本书第5章中的第5.4节。重点理解EOS当前使用的基于优先级的抢先式调度，调度 程序执行的时机和流程，以及实现时间片轮转调度的细节。 3. 实

2、验内容实验内容 3.1 准备实验 按照下面的步骤准备实验： 1. 启动OS Lab。 2. 新建一个EOS Kernel项目。 3.2 阅读控制台命令“rr”相关的源代码 阅读ke/sysproc.c文件中第690行的ConsoleCmdRoundRobin函数，及该函数用到的第 649行的ThreadFunction函数和第642行的THREAD_PARAMETER结构体，学习“rr”命令是如何 测试时间片轮转调度的。在阅读的过程中需要特别注意下面几点： 在ConsoleCmdRoundRobin函数中使用ThreadFunction函数做为线程函数，新建了20 个优先级为8的线程，做为测试

3、时间片轮转调度用的线程。 在新建的线程中，只有正在执行的线程才会在控制台的对应行（第0个线程对应第0 行，第1个线程对应第1行）增加其计数，这样就可以很方便的观察到各个线程执行的情 况。 控制台对于新建的线程来说是一种临界资源，所以，新建的线程在向控制台输出时， 必须使用“关中断”和“开中断”进行互斥（参见ThreadFunction函数的源代码）。 由于控制台线程的优先级是24，高于新建线程的优先级 8，所以只有在控制台线程 进入“阻塞”状态后，新建的线程才能执行。 新建的线程会一直运行，原因是在ThreadFunction函数中使用了死循环，所以只能 在ConsoleCmdRoundRob

4、in函数的最后调用TerminateThread函数来强制结束这些新建的线 程。 按照下面的步骤执行控制台命令“rr”，查看其在没有时间片轮转调度时的执行效果： 1. 按F7生成在本实验3.1中创建的EOS Kernel项目。 2. 按F5启动调试。 3. 待EOS启动完毕，在EOS控制台中输入命令“rr”后按回车。 命令开始执行后，观察其执行效果（如图 1） ，会发现并没有体现“rr”命令相关源代码的设 计意图。通过之前对这些源代码的学习，20 个新建的线程应该在控制台对应的行中轮流地显示它们的计数在增加，而现在只有第 0 个新建的线程在第 0 行显示其计数在增加，说明 只有第 0 个新建的

5、线程在运行，其它线程都没有运行。造成上述现象的原因是：所有 20 个 新建线程的优先级都是 8，而此时 EOS 只实现了基于优先级的抢先式调度，还没有实现时 间片轮转调度，所以至始至终都只有第 0 个线程在运行，而其它具有相同优先级的线程都 没有机会运行，只能处于“就绪”状态。图1：没有时间片轮转调度时“rr”命令的执行效果3.3调试线程调度程序 在为EOS添加时间片轮转调度之前，先调试一下EOS的线程调度程序 PspSelectNextThread函数，学习就绪队列、就绪位图以及线程的优先级是如何在线程调度 程序中协同工作的，从而加深对EOS已经实现的基于优先级的抢先式调度的理解。 3.3.

6、1 调试当前线程不被抢先的情况 正像图 1 中显示的，新建的第 0 个线程会一直运行，而不会被其它同优先级的新建线 程或者低优先级的线程抢先。按照下面的步骤调试这种情况在 PspSelectNextThread 函数中 处理的过程。 1. 结束之前的调试。 2. 在ke/sysproc.c文件的ThreadFunction函数中，调用fprintf函数的代码行（第680行） 添加一个断点。 3. 按F5启动调试。 4. 待EOS启动完毕，在EOS控制台中输入命令“rr”后按回车。“rr”命令开始执行后，会在 断点处中断。 5. 查看ThreadFunction函数中变量pThreadParam

7、eter-Y的值应该为0，说明正在调试的 是第0个新建的线程。 图2 执行效果 6. 激活虚拟机窗口，可以看到第0个新建的线程还没有在控制台中输出任何内容，原因 是fprintf函数还没有执行。 7. 激活OS Lab窗口后按F5使第0个新建的线程继续执行，又会在断点处中断。再次激活 虚拟机窗口，可以看到第0个新建的线程已经在控制台中输出了第一轮循环的内容。可以 多按几次F5查看每轮循环输出的内容。 图3 第一轮循环 通过之前的调试，可以观察到第0个新建的线程执行的情况。按照下面的步骤调试，查 看当有中断发生从而触发线程调度时，第0个新建的线程不会被抢先的情况。 1. 在ps/sched.c文

8、件的PspSelectNextThread函数中，调用BitScanReverse函数扫描就 绪位图的代码行（第384行）添加一个断点。 2. 按F5继续执行，当有定时计数器中断发生时（每10ms一次），就会在新添加的断点处 中断。 3. 在“调试”菜单的“窗口”中选择“监视”，激活“监视”窗口（此时按F1可以获得关于“监视” 窗口的帮助）。 4. 在“监视”窗口中添加表达式“/t PspReadyBitmap”，以二进制格式查看就绪位图的值。 此时就绪位图的值应该为100000001，表示优先级为8和0的两个就绪队列中存在就绪线程。 （注意，如果就绪位图的值不是100000001，就继续按F

9、5，直到就绪位图变为此值）。 5. 在“调试”菜单中选择“快速监视”，在“快速监视”对话框的“表达式”中输入表达式“*PspCurrentThread”后，点击“重新计算”按钮，可以查看当前正在执行的线程（即被中 断的线程）的线程控制块中各个域的值。其中优先级（Priority域）的值为8；状态 （State域）的值为2（运行态）；时间片（RemainderTicks域）的值为6；线程函数 （StartAddr域）为ThreadFunction。综合这些信息即可确定当前正在执行的线程就是新 建的第0个线程。关闭“快速监视”对话框。 图4 快速“监视”窗口 6. 在“监视”窗口中添加表达式“Li

10、stGetCount( 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。 图1

11、0：进行时间片轮转调度时“rr”命令的执行效果3.4.3 提示 PspRoundRobin函数具体的流程可以参考图5-11。 在PspRoundRobin函数中，全局变量PspCurrentThread指向的线程控制块就是被定时计 数器中断的线程的线程控制块，通过对PspCurrentThread指向的线程控制块的各个域进行 修改，就可以改变被中断线程的各种属性。全局变量PspCurrentThread的定义参见 ps/sched.c的第45行。线程控制块结构体的定义参见ps/psp.h的第58行。 被中断线程的状态有可能不是“运行”状态，而是“阻塞”状态。所以，在进行时间 片轮转调度前，要先

12、判断一下被中断线程是否仍处于“运行”状态。只有当被中断线程仍 处于“运行”状态时，才需要进行时间片轮转调度。在PspRoundRobin函数中的第一行代码 可以如下（线程状态的定义可以参见ps/psp.h的第93行）： if (NULL != PspCurrentThread 函数PspReadyThread的定义参见ps/sched.c 的第107行。 3.5 修改线程时间片的大小 在成功为EOS添加了时间片轮转调度后，可以按照下面的步骤修改时间片的大小： 1. 在OS Lab的“项目管理器”窗口中找到ps/psp.h文件，双击打开此文件。 2. 将ps/psp.h第104行定义的TICKS

13、_OF_TIME_SLICE的值修改为1。 3. 在EOS控制台中输入命令“rr”后按回车。观察执行的效果。 4. 按F7生成EOS内核项目。 5. 按F5启动调试。图11 线程示意 还可以按照上面的步骤为TICKS_OF_TIME_SLICE取一些其它的极端值，例如20或100等，分 别观察“rr”命令执行的效果。通过分析造成执行效果不同的原因，理解时间片的大小对 时间片轮转调度造成的影响。 （规律：将TICKS_OF_TIME_SLICE取100时依次出现再循环依次出现）图12 时间片的大小对时间片轮转调度造成的影响。4. 思考与练习思考与练习1. 结合线程调度执行的时机，说明在Threa

14、dFunction函数中，为什么可以使用“关中断” 和“开中断”的方法来保护控制台这种临界资源。一般情况下，应该使用互斥信号量 （MUTEX）来保护临界资源，但是在ThreadFunction函数中却不能使用互斥信号量，而 只能使用“关中断”和“开中断”的方法，结合线程调度的对象说明这样做的原因。 答：关中断后CPU就不会响应任何由外部设备发出的硬中断（包括定时计数器中断和键 盘中断等）了，也就不会发生线程调度了，从而保证各个线程可以互斥的访问控制台。 这里绝对不能使用互斥信号量（mutex）保护临界资源的原因：如果使用互斥信号量， 则那些由于访问临界区而被阻塞的线程，就会被放入互斥信号量的等

15、待队列，就不会 在相应优先级的就绪列中了，而时间轮转调度算法是对就绪队列的线程进行轮转调度， 而不是对这些被阻塞的线程进行调度，也就无法进行实验了。使用“关中断”和“开 中断”进行同步就不会改变线程的状态，可以保证那些没有获得处理器的线程都在处 于就绪队列中。2. 时间片轮转调度发现被中断线程的时间片用完后，而且在就绪队列中没有与被中断线 程优先级相同的就绪线程时，为什么不需要将被中断线程转入“就绪”状态？如果此时 将被中断线程转入了“就绪”状态又会怎么样？可以结合PspRoundRobin函数和 PspSelectNextThread函数的流程进行思考，并使用抢先和不抢先两种情况进行说明。

16、答：因为由PspRoundRobin 函数和 PspSelectNextThread 函数的流程可知，当时间片 轮转调度发现被中断线程的时间片用完后，而且在就绪队列中没有与被中断线程优先 级相同的就绪线程时，PspRoundRobin 函数会直接结束，所以不需要将被中断线程转 入“就绪”状态。如果此时将被中断线程转入了“就绪”状态，那么比该中断线程更高的就绪进程就无法运行。3. 在EOS只实现了基于优先级的抢先式调度时，同优先级的线程只能有一个被执行。当实 现了时间片轮转调度算法后，同优先级的线程就能够轮流执行从而获得均等的执行机 会。但是，如果有高优先级的线程一直占用CPU，低优先级的线程就永远不会被执行。 尝试修改ke/