最低松弛度优先

1、青岛理工大学操作系统课程设计报告院（系）： 计算机工程学院 专业： 软件工程专业 学生姓名: 班级：软件101班学号: 题目：采用最低松弛度优先调度的实时系统调度程序 起迄日期: 2013.7.82013.7.14 设计地点: 计算机学院机房 指 导 教 师: 20122013年度 第 2 学期完成日期: 2013 年 7 月 14 日一、课程设计目的3二、课程设计内容与要求31、设计内容32、设计要求3三、系统分析与设计41、系统分析42、系统设计：42.1、模块设计：42.2、数据结构说明：42.3、算法流程图：5四、系统测试与调试分析91、系统测试92、调试分析：11五、用户手册115.

2、1使用平台115.2安装步骤115.3使用步骤11六、程序清单13七、体会与自我评价19八、参考文献19九、课程设计评价19一、课程设计目的在学习操作系统课程的基础上，在完成操作系统各部分实验的基础上，对操作系统的整体进行一个模拟，通过实践加深对各个部分的管理功能的认识，还能进一步分析各个部分之间的联系，最后达到对完整系统的理解。同时，可以提高运用操作系统知识解决实际问题的能力；锻炼实际的编程能力、创新能力及团队组织、协作开发软件的能力；还能提高调查研究、查阅技术文献、资料以及编写软件设计文档的能力。二、课程设计内容与要求 1、设计内容在实时系统中，要保证在指定的时间完成指定的任务，通常会采用

3、抢占式的调度方式。要求采用指定的调度算法，使系统中的任务能够按时完成，通过观察中系统中的抢占点，以巩固和加深对实时系统调度算法的理解。2、设计要求1) 每一个周期性实时任务必须指定周期长度与执行时间2) 可以在界面安排周期性实时任务的个数与相关的指标值，又及要求仿真的时间长度3) 系统可又对设定的任务条件进行检查，如果无法满足公式 的要求，则弹出相应的错误提示，并重新进入任务安排界面4) 可读取样例数据（要求存放在外部文件中）进行周期性实时任务数、周期长度、执行时间的初始化5) 采用可视化界面，数据载入后按最低松弛度算法进行调度，可以在运行中动态显示各进程的状态：就绪、执行、完成6) 系统上下

4、文切换时，会暂停调度，显示就绪队列中各任务的松弛度，按任意键后自动运行7) 具有一定的数据容错性三、系统分析与设计1、系统分析（1）该算法根据实时任务的松弛度来确定任务的优先级，任务的松弛度愈低，其优先级愈高，以使之优先执行。（2）松弛度=必须完成的时间-其本身的运行时间-当前时间（3）要求系统中有一个按松弛度排序的实时任务就绪队列。（4）该算法主要用于可抢占调度方式中，当一任务的最低松弛度减为0时，它便立即抢占CPU，以保证按截止时间的要求完成任务。2、系统设计：2.1、模块设计：主程序所需数据的初始化运行中动态显示各进程的状态，画出调度图2.2、数据结构说明： public class p

5、rocessprivate string pname;/进程名private int period;/周期长度private int cputime;/需要的cpu时间private int remaintime;/剩余需执行的时间private int arrivetime;/每个周期的到达时间private int pnum;/所处周期数private int laxity;/松弛度private int priority;/优先级（1）进程名用来标识一个进程（2）周期长度周期性实时任务必须有周期长度（3）需要的cpu时间周期性实时任务必须有每个周期需要的执行时间（4）剩余需执行的时间用来

6、判断是否发生抢占，假设在按松弛度排序的就绪队列中，任务a松弛度最小，任务b次之，若任务a需要的cpu时间大于任务b的松弛度，则在任务a的这次调度中会发生抢占，则任务a该周期的剩余需执行的时间大于0，反之，剩余需执行的时间等于0时，则这次调度过程中不会发生抢占。（5）每个周期的到达时间用来进行排序，系统要求有一个按松弛度排序的实时任务就绪队列，若松弛度相同，则按到达时间排序。（6）所处周期数对于周期性实时任务，应该有所处的周期数，其次，计算松弛度时算任务必须完成的时间可以用所处周期数和周期长度相乘得到。（7）松弛度最低松弛度优先调度算法肯定要求计算松弛度。（8）优先级同样也是为了排序使用，在松弛

7、度和到达时间都相同的时候，按固定的优先级进行排序，优先级在添加实时任务时动态生成。2.3、算法流程图：1、数据初始化1.1界面直接添加周期性实时任务数是否为空输出：请输入周期性实时任务的个数所添加任务数是否小于周期性实时任务数输出：超出个数限制new一个process实例，添加到实时任务数组pro中，然后将该任务在两个listview中显示所添加任务数是否等于周期性实时任务数判断系统是否可调度清空实时任务名，周期长度和执行时间三个输入框是否否是是1.2 从文件中读取数据找到需要的文件，点击打开读取文件内容，new出process实例，添加到数组，同时在两个listview中显示判断系统是否可调

8、度2、动态显示各进程的状态和画出调度图把listview2的备注一栏清空初始化一些变量，实例化sortpro，然后对sortpro进行排序找到已到达的松弛度最小的任务，如果所以任务都没到达，flag=falseflag是否为true找到松弛度最小和次小的任务，计算duration，并对其加以限制，修改本次被调度进程的remaintime画出本次调度的图形，修改curtime的值根据remaintime的值修改本次被调度进程在listview2中的显示信息，更改本次被调度进程的相关信息重新计算所有任务的松弛度，更新未被调度的进程在listview2中显示的信息当前时间大于或等于要求仿真的时间长度

9、停止计时，显示调度完成四、系统测试与调试分析1、系统测试l 测试方法：黑盒测试l 测试技术：功能测试它是从使用者的角度来编写的，它关注系统提供的功能特征及其不同的处理条件；测试功能的不同处理流程（包括正常处理的和异常处理）；一个功能测试用例仅用于测试一个功能，一个功能可能需要多个功能测试用例来覆盖。l 测试数据： （1） 课本例子（存在抢占的情况）输入：周期性实时任务的个数：2第一个实时任务(实时任务名，周期长度，执行时间)：A,20,10第二个实时任务(实时任务名，周期长度，执行时间)：B,50,25输出结果：（2） 不存在抢占输入：周期性实时任务的个数：3第一个实时任务(实时任务名，周期长

10、度，执行时间)：A,20,10第二个实时任务(实时任务名，周期长度，执行时间)：B,50,10第三个实时任务(实时任务名，周期长度，执行时间)：C,50,15输出结果：（3） 系统不可调度输入：周期性实时任务的个数：2第一个实时任务(实时任务名，周期长度，执行时间)：A,20,10第二个实时任务(实时任务名，周期长度，执行时间)：B,30,20 输出结果：提示：系统不可调度l 测试报告：（1） 课本例子（存在抢占的情况）测试结果：（2） 不存在抢占的例子测试结果：（3） 系统不可调度测试结果：测试说明测试名称采用最低松弛度优先调度的实时系统调度程序测试目的验证采用最低松弛度优先调度的实时系统调

11、度程序调度的正确性测试技术功能测试测试方法黑盒测试法测试用例测试内容系统所实现的最低松弛度优先算法的正确性测试步骤输入周期性实时任务的个数，每个任务的实时任务名，周期长度和执行时间（存在抢占）输入周期性实时任务的个数，每个任务的实时任务名，周期长度和执行时间（不存在抢占）输入周期性实时任务的个数，每个任务的实时任务名，周期长度和执行时间（系统不可调度）测试数据2a,20,10;b,50,253a,20,10;b,50,10;c,50,152a,20,10;b,30,20预期结果得出正确的调度图得出正确的调度图给出相应的提示信息测试结果与预期相符与预期相符与预期相符2、调试分析：开始调试算法，在

12、排序的时候一直有一个空引用异常，提示未将对象引用设置到对象的实例。是因为没有实例化按松弛度排序的那个数组，根本上还是自己编程比较少的原因，平时学习语言的时候应该注意要多练习。还有就是排序交换数据的时候出了点儿问题，还是因为编程不熟练的问题。还有一个费了好长时间的问题就是暂停调度时，按任意键继续的问题，解决这个问题的时候在网上找了好长时间，网上没有现成的答案，有的也是控制台下按任意键继续的问题。自己添加了一个窗体的键盘事件，可是一直没有成功触发这个事件，后来知道是焦点的问题，先得让窗体获得焦点，按任意键才能触发那个事件。最后调试的比较多的就是最后动态显示的部分，为了显示的更合理。开始以为还行，后

13、来换了个例子还发现了比较多的问题，看来，自己编程序还是要更仔细。五、用户手册5.1使用平台本系统使用操作系统为win7，需要安装visual stutio 20105.2安装步骤本系统无需安装，只需把exe文件拷贝到电脑上5.3使用步骤图1：开始运行界面图2：输入数据图3：数据可从文件中读取图4：点击开始，开始动态显示图5：动态运行中各进程状态图6：调度结束六、程序清单最低松弛度优先算法：private void timer1_Tick(object sender, EventArgs e) /清空备注中的信息 for (int i = 0; i < pro.Length; i+) li

14、stView2.Itemsi.SubItems4.Text = "" bool flag = true; int duration=0;/本次调度执行的时间 int first=0; int second=0; int ordfirst=0; sortpro=new processpro.Length; for (int i = 0; i < pro.Length; i+) sortproi = new process(proi.Pname,proi.Period,proi.Cputime,proi.Remaintime,proi.Pnum,proi.Arriveti

15、me,proi.Laxity,proi.Priority); process proc = new process(); /对sortpro中的任务按松弛度从小到大进行排序，松弛度相同时按到达次序先后排序，到达时间相同时按固定优先级排序 /固定优先级：在添加任务时，先添加的任务优先级高 for (int i = 0; i < sortpro.Length - 1; i+) for (int j = i + 1; j < sortpro.Length; j+) if (sortproj.Laxity < sortproi.Laxity) /交换所有属性信息 proc.Pname

16、 = sortproi.Pname; sortproi.Pname = sortproj.Pname; sortproj.Pname = proc.Pname; else if (sortproj.Laxity = sortproi.Laxity) if (sortproj.Arrivetime < sortproi.Arrivetime) /交换所有属性信息 proc.Pname = sortproi.Pname; sortproi.Pname = sortproj.Pname; sortproj.Pname = proc.Pname; else if (sortproj.Arrive

17、time = sortproi.Arrivetime) /交换所有属性信息 if (sortproj.Priority < sortproi.Priority) proc.Pname = sortproi.Pname; sortproi.Pname = sortproj.Pname; sortproj.Pname = proc.Pname; /外层for循环 /找到sortpro中已到达的松弛度最低的进程 for (int i = 0; i < sortpro.Length;i+ ) if (curtime < (sortproi.Pnum - 1) * sortproi.P

18、eriod) if (i != sortpro.Length - 1) continue; else /curtime到最近的周期 curtime = sortpro0.Arrivetime; for (int j = 1; j < sortpro.Length; j+) if (sortproi.Arrivetime < curtime) curtime = sortproi.Arrivetime; /重新计算松弛度 for(int j=0;j<pro.Length;j+) proj.Laxity = proj.Pnum * proj.Period - curtime -

19、proj.Remaintime; for (int j = 0; j < pro.Length; j+) /在listview2中动态显示各任务信息 if (proj.Pnum - 1) * proj.Period < curtime) | (proj.Pnum - 1) * proj.Period = curtime) listView2.Itemsj.SubItems1.Text = proj.Pnum.ToString(); listView2.Itemsj.SubItems2.Text = proj.Laxity.ToString(); listView2.Itemsj.S

20、ubItems3.Text = "就绪" else listView2.Itemsj.SubItems1.Text = "" listView2.Itemsj.SubItems2.Text = "" listView2.Itemsj.SubItems3.Text = "" listView2.Itemsj.SubItems4.Text = "尚未到达" flag = false; else ordfirst = i; break; /尚未进入该周期的for循环 /如果sortpro中所有任务都没

21、到达，则不执行if(flag)中的代码 if (flag) /找到松弛度最低和次低的任务 for (int i = 0; i < pro.Length; i+) if (ordfirst < pro.Length - 1) if (proi.Pname.Equals(sortproordfirst.Pname) first = i; if (proi.Pname.Equals(sortproordfirst + 1.Pname) second = i; else first = i; second = 0; /根据松弛度次低的任务的松弛度和松弛度最低的任务的执行时间确定durati

22、on if (profirst.Remaintime <= prosecond.Laxity) duration = profirst.Remaintime; else duration = prosecond.Laxity; /对duration的额外限制，closetime为要求仿真的时间长度 if (curtime + duration) > closetime) duration = closetime - curtime; profirst.Remaintime -= duration; /画出本次调度的图形 for (int y = 0; y < duration

23、; y+) Pen pen; pen=new Pen(Color.FromArgb(colorprofirst.Priority,0,colorprofirst.Priority,1,colorprofirst.Priority,2); grap.DrawLine(pen, (curtime + y) * 2, 0, (curtime + y) * 2, 30); grap.DrawLine(pen, (curtime + y) * 2 + 1, 0, (curtime + y) * 2 + 1, 30); /修改curtime curtime += duration; /动态修改listvi

24、ew2中的信息 if (profirst.Remaintime = 0) listView2.Itemsfirst.SubItems1.Text = profirst.Pnum.ToString(); listView2.Itemsfirst.SubItems2.Text = "" listView2.Itemsfirst.SubItems3.Text = "完成" listView2.Itemsfirst.SubItems4.Text = "第" + profirst.Pnum + "个周期运行了" + dura

25、tion + "毫秒" /更改本次被调度任务的相关属性 profirst.Pnum+; profirst.Remaintime = profirst.Cputime; profirst.Arrivetime = (profirst.Pnum - 1) * profirst.Period; else listView2.Itemsfirst.SubItems4.Text = "第" + profirst.Pnum + "个周期运行了" + duration + "毫秒" listView2.Itemsfirst.Su

26、bItems3.Text = "" listView2.Itemsfirst.SubItems2.Text = "" timer1.Enabled = false; display.Text = "上下文切换，按任意键继续" listView2.Itemssecond.SubItems4.Text = prosecond.Pname + "抢占cpu" /窗体获得焦点 this.KeyPreview = true; /暂停，等待按任意键 this.keybool = true; for (int j = 0; j

27、< pro.Length; j+) /修改所有任务的松弛度 proj.Laxity = proj.Pnum * proj.Period - curtime - proj.Remaintime; for (int i = 0; i < pro.Length; i+) /显示本次未被调度的任务的状态 if (i != first) if (proi.Pnum - 1) * proi.Period < curtime) | (proi.Pnum - 1) * proi.Period = curtime) listView2.Itemsi.SubItems1.Text = proi.

28、Pnum.ToString(); listView2.Itemsi.SubItems2.Text = proi.Laxity.ToString(); listView2.Itemsi.SubItems3.Text = "就绪" else listView2.Itemsi.SubItems1.Text = "" listView2.Itemsi.SubItems2.Text = "" listView2.Itemsi.SubItems3.Text = "" listView2.Itemsi.SubItems4.Text = "尚未到达" /if(flag) /调度完成条件 if (curtime > this.closetime|curtime=this.closetime) this.timer1.Stop(); if (MessageB