《时间片轮转调度.doc》由会员分享,可在线阅读,更多相关《时间片轮转调度.doc(4页珍藏版)》请在三一办公上搜索。
1、时间片轮转调度实验性质:设计建议学时:2学时一、实验目的l 为EOS调度器添加时间片轮转调度算法,了解常用调度算法。二、预备知识阅读EOS实验指南5.4节。重点理解EOS当前使用的基于优先级的抢先式调度,调度程序执行的过程和时机,以及时间片轮转调度实现的方法。三、实验内容3.1 准备实验按照下面的步骤准备实验:1. 启动OS Lab。2. 新建一个EOS Kernel项目。3. 在“项目管理器”窗口中双击Floppy.img文件,使用FloppyImageEditor工具打开此软盘镜像。4. 将本实验文件夹中的multi.exe文件添加到软盘镜像的根目录中。5. 点击FloppyImageEd
2、itor工具栏上的保存按钮,关闭该工具。3.2 阅读multi.exe的源代码在本实验文件夹中找到multi.exe的源代码文件multi.c,使用OS Lab打开此文件,仔细阅读此文件中的源代码。在阅读的过程中需要注意下面的问题:l 在main函数中使用ThreadFunction线程函数创建了23个新线程。这样在该应用程序创建的进程中,算上主线程后就会包括24个线程。l 主线程会在控制台的第0行循环输出计数,其它的线程也会在控制台的对应行循环输出计数,这样就可以很方便的观察各个线程执行的情况。l 各个线程在向控制台输出时使用“关中断”和“开中断”进行了互斥。原则上在应用程序中是不能使用“关
3、中断”和“开中断”指令的,这里是为了保证各个线程不进行让权等待,保证实验的效果。l 为了保证实验效果,所有的线程(包括主线程)都是死循环。也就是说所有的线程都不会结束执行。3.3 执行multi.exe按照下面的步骤执行multi.exe,查看其运行效果:1. 按F7生成在3.1中创建的EOS Kernel项目。2. 按F5启动调试。3. 在EOS控制台中输入“A:multi.exe”后按回车。在multi.exe开始执行后,观察其执行结果(如图1)会发现multi.exe的执行没有体现其源代码的设计意图。通过之前对multi.c的分析,multi进程中的24个线程应该在控制台对应的行中不停地
4、输出字符。而这里只有主线程在运行,其它线程都没有运行。图1:不进行时间片轮转调度时multi.exe的执行效果造成上述现象的原因:进程内的所有线程在被创建时都采用了默认优先级8,这就造成这24个线程的优先级都是相同的。而此时EOS只实现了基于优先级的抢先式调度算法,还没有实现时间片轮转调度算法,所以至始至终都只有主线程在运行,其它具有相同优先级的线程都没有运行。3.4 为EOS添加时间片轮转调度算法3.4.1 要求修改EOS内核项目ps/sched.c文件中的PspRoundRobin函数(第335行),在其中实现时间片轮转调度算法。3.4.2 测试方法1. 代码修改完毕后,按F7生成EOS内
5、核项目。2. 按F5启动调试。3. 在EOS控制台中输入“A:multi.exe”后按回车。应能看到24个线程并发执行的效果,如图2。图2:进行时间片轮转调度时multi.exe的执行效果图3:PspRoundRobin函数的流程图3.4.3 提示l 在EOS操作系统运行过程中,TCB指针变量PspCurrentThread始终指向当前线程。所以,当发生中断时,PspCurrentThread就指向被中断的线程。PspCurrentThread的定义参见ps/sched.c的第44行。TCB结构体定义参见ps/psp.h的第58行。l PspRoundRobin函数在被调用时,被中断线程(Ps
6、pCurrentThread指向的线程)的状态可能已经改变(例如从运行状态转变为等待状态)。所以要先判断一下被中断线程是否仍处于运行状态,只有当被中断线程处于运行状态时才能进行时间片轮转调度。在PspRoundRobin中的第一行代码可以如下:if (NULL != PspCurrentThread & Running = PspCurrentThread-State) / 在此实现时间片轮转调度算法线程状态的定义可以参见ps/psp.h的第93行。l PspRoundRobin函数具体的流程可以参考图3。l 被中断线程所拥有的时间片保存在PspCurrentThread-RemainderT
7、icks中。l 重新为被中断线程分配时间片时,可以使用头文件ps/psp.h中第104行的宏定义TICKS_OF_TIME_SLICE,目前为6。注意,此宏定义表示每次给线程分配的时钟滴答(Tick)数量,多个时钟滴答组成了线程的时间片。时钟滴答的大小是由定时器中断的频率确定的,目前每秒触发100次定时器中断,所以每个时钟滴答的大小是10ms。l 在检查是否存在和被中断线程优先级相同的就绪线程时,只需要扫描32位就绪位图即可。可以使用下面的代码作为判断语句中的布尔表达式:BIT_TEST(PspReadyBitmap, PspCurrentThread-Priority)BIT_TEST是一个
8、宏定义函数,其定义参见inc/eosdef.h的第219行。如果存在和被中断线程优先级相同的就绪线程,此函数返回非0(TURE),否则返回0(FALSE)。变量PspReadyBitmap是32为就绪位图,其定义参见ps/sched.c的第28行。l 可以使用下面的代码将被中断线程转入就绪状态:PspReadyThread(PspCurrentThread);函数PspReadyThread的定义参见ps/sched.c的第106行。3.5 修改线程的时间片大小 在成功为EOS添加了时间片轮转调度算法后,可以按照下面的步骤修改时间片的大小:1. 在OS Lab的“项目管理器”窗口中找到ps/p
9、sp.h文件,并双击打开此文件。2. 将ps/psp.h第104行定义的TICKS_OF_TIME_SLICE的值修改为1。4. 按F7生成EOS内核项目。5. 按F5启动调试。3. 在EOS控制台中输入“A:multi.exe”后按回车。观察multi.exe执行的效果。你还可以按照上面的步骤为TICKS_OF_TIME_SLICE取一些极端值,例如20和100等,分别观察multi.exe运行的效果。通过分析造成运行效果不同的原因,理解时间片的大小对时间片轮转调度造成的影响。四、思考与练习l 开始EOS只实现了基于优先级的抢先式调度,这导致同优先级的线程只能有一个被执行。当实现了时间片轮转
10、调度算法后,同优先级的线程就能够轮流执行从而获得均等的执行机会。但是,如果有高优先级的线程一直占用CPU,低优先级的线程就永远不会被执行,请设计一种调度算法来解决此问题,让低优先级的线程也能获得被执行的机会。l EOS内核时间片大小取60ms(和Windows操作系统完全相同),在线程比较多时,就可以观察出线程轮流执行的情况(因为此时一次轮转需要61060ms,24个线程轮流执行一次需要60241440ms,也就是需要1秒多的时间,所以EOS的控制台上我们可以清楚地观察到线程轮流执行的情况)。但是在Windows、Linux等操作系统启动后,正常情况下都有上百个线程在并发执行,为什么觉察不到它们被轮流执行,并且每个程序都运行的很顺利呢?