最低松弛度优先

1、青岛理工大学操作系统课程设计报告院（系）： 计算机工程学院 专业： 网络工程 学生姓名: 班级： 学号: 题目：采用最低松弛度优先调度的实时系统调度程序 起迄日期: 2013.07.082013.07.19 设计地点: 计算机工程学院机房 指 导 教 师: 20122013年度 第 2 学期完成日期: 2013 年 7 月 19 日一、 课程设计目的由于在实时系统中都存在着若干个实时进程或任务，它们用来反应或控制某个外部事件，往往带有某种程序的紧迫性，因此采用一种新的调度：实时调度才能实现合理合法的调度。而最低松弛度优先，是一种抢占式的实时调度，根据任务的松弛程度来确定任务的优先级。任务的松弛

2、度愈低，愈优先执行。通过实现利用最低松弛度对作业进行调度的模拟，我可以清楚的了解操作系统的相关任务调度原理和操作系统的任务调度过程。此次的课程设计让我对该调度算法有了更加深入的理解同时对以编程实现该算法和可视化编程有了更深一步的了解和巩固。二、 课程设计内容与要求 1、在实时系统中，要保证在指定的时间完成指定的任务，通常会采用抢占式的调度方式。要求采用指定的调度算法，使系统中的任务能够按时完成，通过观察中系统中的抢占点，以巩固和加深对实时系统调度算法的理解。2、设计要求：1) 每一个周期性实时任务必须指定周期长度与执行时间。2) 可以在界面安排周期性实时任务的个数与相关的指标值，又及要求仿真的

3、时间长度。3) 系统可又对设定的任务条件进行检查，如果无法满足公式 的要求，则弹出相应的错误提示，并重新进入任务安排界面。4) 可读取样例数据（要求存放在外部文件中）进行周期性实时任务数、周期长度、执行时间的初始化。5) 采用可视化界面，数据载入后按最低松弛度算法进行调度，可以在运行中动态显示各进程的状态：就绪、执行、完成。6) 系统上下文切换时，会暂停调度，显示就绪队列中各任务的松弛度，按任意键后自动运行。7) 具有一定的数据容错性。三、 系统分析与设计1、系统分析 在系统中，通过界面输入或文件读取来向系统录入数据，由输入各个任务的相关信息来计算出最低松弛度。对于每一个任务，当最低松弛度减小

4、到零时便开始抢占处理机，对于多个任务最低松弛度相同的情况下，采用先来先服务的辅助调度算法。最后动态显示运行的实时结果，从而直观的表现出采用最低松弛度调度算法的工作原理和调度过程。（1） 信息：输入信息为任务总数，仿真时间，各任务编号，周期时间，和运行时间。输出信息为各任务的开始时间，结束时间，运行次数，当前状态，任务当前松弛度，以及当前任务还需运行时间。（2） 行为：系统通过调用，动态显示各个实时任务的最低松弛度。当某个实时任务的最低松弛度=0的时候，则抢占执行。当多个实时任务的最低松弛度各不相等时，则予以该实时任务正常执行，而无需抢占。当多个实时任务的最低松弛度相等时，则采用先来先服务的方式

5、执行。执行结果动态的显示在各个表格中，清楚的展现接下来该调度哪个实时任务，等待调度的实时任务有哪些和完成目前周期的实时任务有哪些。（3） 表示：程序运行期间的显示布局如下图所示：选择数据输入方式，包括文件读取和界面输入界面键入总任务信息和各任务详细信息控制按钮，包括开始，结束，暂停，终止，退出系统信息（当前时间）和提示上下文切换动态显示运行过程，包括就绪，完成，执行2、系统设计：概要设计：（1）输入模块：用户处方选择文件读取和界面输入，文件读取仅要求用户选定相关文件，前提是编程者事先存储符合要求的信息。界面输入要求用户输入正确的总任务信息和各个任务的详细信息，系统也将检查信息的合法性才予以调度

6、。（2）算法模块：调度算法模块主要设计出根据最低松弛度进行调度的算法，以及予以任务抢占时的条件和调度过程（3）输出模块：用列表控件动态显示各个任务的就绪，执行，完成列表的属性信息。（4）任务合法性检查模块：检查提交给系统的任务的周期时间和运行时间是否都大于0，以及周期时间是否都大于运行时间（5）可调度性检查模块：检查提交给系统的所有任务是否满足可调度性公式。（6）运行控制模块：程序运行时的功能选择和相关控制功能。2.1、模块设计：在该系统中，由用户提交给系统总任务信息和各任务的信息，系统将就此检查各任务的合法性，合法则显示在就绪队列，再检查所有任务的可调度性，若可调度则进行演示。演示的结果将动

7、态显示在就绪，执行，完成的三个列表控件上。模块调用关系图：输入模块可调度性检查模块算法模块任务合法性检查模块输出模块控制模块主模块2.2、数据结构说明： 1、每一个任务对应一个work类型的结构体变量typedef struct workCString job_id;/任务的ID，唯一标志一个任务intjob_beginTime;/任务的开始时间intjob_llf;/任务当前低松弛度CStringjob_state;/任务当前状态intjob_period;/任务的周期intjob_runTime;/任务的运行时间intjob_RneedTime;/任务完成还需的运行时间intjob_end

8、Time;/任务的结束时间intjob_flag;/本周期内首次运行标识intjob_doneTimes;/任务的执行次数intjob_identify;/任务是否完成的标识intjob_MissTimes;/任务错过次数struct work * next;/指向结构体变量work的指针 work,*POINT_work;2、由任务排成的队列typedef struct QNodePOINT_work data; /指向结构体类型数据的数据项指针struct QNode *next;/指向下一个队列元素的指针QNode, *POINT_QNode;typedef structPOINT_QN

9、ode front;/任务队列的对头指针POINT_QNode rear;/任务队列队尾指针Queue;Queue Qon,Qready,Qdone;/定义三个队列，其中Qon表示正在执行的队列，该队列最多只有一个队列元素，Qready表示就绪的队列，Qdone表示已经执行完成的队列程序中用到的对上述数据结构的一些操作：int InitQueue(Queue &Q)/构造空队列，成功返回1，否则返回0void OrderJob(Queue &Q,POINT_work job)/按照低松弛度对进入队列的任务进行排序int DeleteHead(Queue &Q,POINT

10、_work job)/若队列不空，则删除Q的头元素，用job保存，操作成功返回1，否则返回0void DestroyQueue(Queue &Q) /销毁一个队列int QueueEmpty(Queue Q)/判断队列是否为空若为空则返回1，否则返回0int GetHeadElem(Queue Q,POINT_work job)/取队列的第一个元素的值，成功返回1，否则返回0int DeleteDefineQueue(Queue &Q,CString str,POINT_work job)/删除指定任务编号的队列节点，用结构体变量job保存，操作成功返回1，否则返回02.3、算

11、法流程图：（1）控制函数流程图：开始界面输入？输入任务总数输入仿真时间输入任务信息选择文件可以调度？进入就绪队列提示不可调度重新输入模拟开始，激活计时器计算松弛度执行调度算法刷新定时器，任务信息终止运行？新任务？结束否 是否是否是否是 (2)检查函数流程图：输入任务信息周期T、运行时间R>0运行时间<周期？float j=0.0j=j+R/T;最后一个任务？ j>1.0 ?可调度，进入队列是是输入任务非法否否是否是否任务不可调度 开始计算任务松弛度计时开始，flag=0 计时开始 松弛度小的任务优先运行 计数器更新 抢占变量flag加1是是否设定松弛度进入就绪队列，flag-

12、； 模拟结束？显示结果否 否是任务抢占？ 任务抢占？flag=1？否是（3）调度函数流程图：（4）输入函数流程图:是 否是 否开始文件读取？输入任务总数选择文件提交后隐藏按键输入仿真时间输入后隐藏按键输入任务信息最后的作业？隐藏点击提交按键进行合法性检查四、系统测试与调试分析1、系统测试l 测试方法：黑盒l 测试技术：单元测试、功能测试、l 测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。1、 验证提交任务的可调度性测试说明测试名称采用最低松弛度优先调度的实时系统调度程序测试目的验证提交任务的可调度性测试技术单元测试测试方法黑盒测试法测试用例测试内容通过文件读取的方式提交一批

13、任务，测试系统对任务可调度性的判断测试步骤输入可调度的一批任务输入不可调度任务输入含非法任务测试数据任务数目：3任务编号 NO.1周期时间20 s运行时间 4s任务编号 NO.2周期时间 30 s运行时间 6s任务编号 NO.3周期时间 45 s运行时间 8s任务数目：3任务编号 NO.1周期时间20 s运行时间 4s任务编号 NO.2周期时间 20 s运行时间 6s任务编号 NO.3周期时间 5 s运行时间3s任务数目：3任务编号 NO.1周期时间20 s运行时间 4s任务编号 NO.2周期时间 20 s运行时间 6s任务编号 NO.3周期时间 5 s运行时间8s预期结果任务可调度，在就绪队

14、列中排队显示任务不可调度提示含有非法任务测试结果与预期相符与预期相符与预期相符2、 验证任务调度顺序的正确性测试说明测试名称采用最低松弛度优先调度的实时系统调度程序测试目的任务调度顺序的正确性验证测试技术单元测试测试方法黑盒测试法测试用例测试内容通过文件读取的方式提交一批任务，验证对任务的调度是否正确测试步骤输入可调度的一批任务测试数据任务总数：3仿真时间100s任务编号 NO.1周期时间 20 s运行时间 6s任务编号 NO.2周期时间 10 s运行时间 4s任务编号 NO.3周期时间 5 s运行时间 1s预期结果调度程序先执行NO.3任务1s，然后执行NO.2任务4s，最后执行NO.1任务

15、6s测试结果与预期相符3、验证当两个任务松弛度同时减为0时的执行结果测试说明测试名称采用最低松弛度优先调度的实时系统调度程序测试目的验证两个任务松弛度同时减为0时的执行结果是否正确测试技术功能测试测试方法黑盒测试法测试用例测试内容通过文件读取的方式提交一批任务，其中同时有两个任务的松弛度减为0测试步骤输入可上述任务测试数据任务总数：3 仿真时间100s 任务编号 NO.1周期时间 10 s运行时间 1s任务编号NO.2周期时间 10 s运行时间 1s任务编号NO.3周期时间18 s运行时间10s预期结果调度程序先执行NO.3任务9s，后执行NO.1任务1s，任务NO.2被错过测试结果与预期相符

16、2、调试分析：在程序的调试中，遇到了如下的问题：1. 在程序读取文件的任务信息时，无法读入仿真时间，OnRadio1() 在该按钮中的函数中一步步用MessageBox输出每一步读取的参数信息的值，发觉每一步的输出没有问题，最终发觉，在Onshuru()将全局变量SumTime又定义了一遍，在此函数中相当于局部变量在使用，因此无法传参。最终删掉该定义，而直接使用，运行成功。2. 在程序的最后性能测试中，如果程序接收到任务队列，运行一段时间的后，有两个任务的松弛度同时减为零了，程序就会运行出错，到后来发现了程序出现这个问题的原因，就是程序始终是在选取松弛度最小的任务调入运行队列，当遇到两个松弛度

17、同时为0的任务时，程序就不知道怎么调用了。后来我在算法中添加了先来先服务的调度算法来辅助实现，当出现上述情况时就先调入第一个任务，然后将第二个任务的松弛度=1000，在将其压入就绪队列中。这样第二个任务就被错过一次，在下个周期中，自动更新该任务的最低松弛度，然后重新参与任务的调度，具体参照Show_Qready()和Job_Qiangdiao()五、用户手册1、本程序的开发平台是VC 6.0 ，无需下载。2、本程序的运行无需任何安装。3、运行程序：（1）在工程中找到最低松弛度优先.exe 的文件双击开始运行程序。 图 1 程序运行的初始界面2）在选项栏的“选择数据输入方式”中选择文件读取选项，

18、弹出选择文件的对话框，选定要运行的文件后点击确定即可。 图2 点击界面输入按键后，选定文件（3）如果选定文件的数据中含有运行周期小于运行时间的非法任务，系统会通过弹出 MessageBox的方式提示用户输入错误。 图 3 输入含有非法任务（4） 若用户输入的任务中不含有非法任务，此时系统会先将任务放入就绪队列中，然后调用可调度性检测函数来判断该批任务是否可以调度，若不可调度则提示用户，并将就绪队列记录清空，再初始化Qready。 图 4 输入任务不可调度（5） 若输入任务可以调度，系统不会给出任何提示，可直接在就绪队列的列表中显示就绪队列的各任务信息 图 5 输入正确的任务信息，检查就绪队列（

19、6） 点击开始运行按键即开始任务调度的模拟，三个动态显示控件分别用来显示运行任务，就绪队列和完成队列里面各任务的属性信息，上下文切换时，提示用户按下任意键继续。 图 6 动态显示任务的调度过程（7） 若选择从当前的界面输入时，系统会在用户输入运行任务总数和运行时间后，隐藏和锁定这两个按键，从而不再接受关于这两个变量的任何输入。之后用户只可依次输入任务的信息，非法的输入数据在输入时将会被自动忽略，以及对任务编号是否重名的检查。当任务输入完成时，隐藏“点击提交本次任务”。 图 7 用户从界面输入任务信息(8) 在运行过程中点击暂停运行继续运行终止运行按键依次实现程序运行的暂停运行、继续运行、和退出

20、当前任务运行的功能。当用户点击暂停时，就算没有上下文切换，系统的运行也会停下来，直到用户点击继续。 图 8 运行过程中暂停六、程序清单/-文件读取-void CMyDlg:OnRadio1() / TODO: Add your control notification handler code hereCString s1,s2,name,period,runtime,stuTime;/总时间int sum_job;/限定文件格式CFileDialog dlg(true,NULL,NULL,OFN_HIDEREADONLY | OFN_OVERWRITEPROMPT,"text fi

21、les|*.txt|");if(IDOK=dlg.DoModal()/正常打开s1=dlg.GetPathName();/获取文件路径CStdioFile file;/C 运行时流式文件if(!file.Open(s1,CFile:modeRead)/只读的方式打开失败,参数：获取路径，打开方式MessageBox("文件打开失败 ");return ;file.ReadString(s2);/开始文件第一行，总任务数sum_job=atoi(s2);/转换为整数file.ReadString(stuTime);/仿真时间SumTime=atoi(stuTime)

22、;legal=0;for(int i=0;i<sum_job;i+)file.ReadString(name);file.ReadString(period);file.ReadString(runtime);/完全读取文件中一个任务的信息CMyDlg:DuQu(name, period, runtime);if(legal!=0)/含有错误文件内容KillTimer(1);DestroyQueue(Qon);DestroyQueue(Qready);DestroyQueue(Qdone);m_list1.DeleteAllItems();m_list2.DeleteAllItems()

23、;m_list3.DeleteAllItems();count=0;/系统时间GetDlgItem(IDC_showtime)->SetWindowText("");InitQueue(Qon);InitQueue(Qdone);InitQueue(Qready);n2=0;/n2启动定时器的标识 n=0;/若n为0，则从就绪队列中取出一个满足要求的作业运行return ;CMyDlg:DiaoDu();/-读取任务信息-int CMyDlg:DuQu(CString s1, CString s2, CString s3) int i,j;i=atoi(s2);j=a

24、toi(s3);if(i<=0|j<=0|i<j)legal+; MessageBox("输入任务为非法，请重新输入");return 0;else POINT_work job; job=new(work); job->job_beginTime=0; job->job_doneTimes=0; job->job_flag=0; job->job_id=s1; job->job_identify=0; job->job_llf=i-j; job->job_MissTimes=0; job->job_peri

25、od=i; job->job_RneedTime=j; job->job_runTime=j; job->job_state="就绪" if(SameFileName(Qready,job)/若没有重名OrderJob(Qready,job);/进入的作业，按照最低松弛度进行排序 CMyDlg:Show_Qready();/读取成功，作业显示在就绪队列return 1;elseMessageBox("任务编号有重名,请重新输入!");return 0;/-任务调度性检查-int CMyDlg:DiaoDu() float judge=0

26、.0;if(!QueueEmpty(Qready)POINT_QNode p;p=Qready.front->next;while(p) judge=judge+(float)p->data->job_runTime/(float)p->data->job_period;p=p->next;if(judge>1.0)MessageBox("输入不符合要求，不可调度!");DestroyQueue(Qready);InitQueue(Qready);m_list2.DeleteAllItems();return 0; else ret

27、urn 1; else return 0;/-正在执行的作业在正常结束的情况下作业切换-int CMyDlg:Job_Diao() POINT_work job; job=new(work);if(!QueueEmpty(Qon)/将已完成的任务投入完成队列 DeleteHead(Qon,job); job->job_flag=0; job->job_identify=1; job->job_doneTimes+; job->job_llf=(job->job_doneTimes+1)*job->job_period-count-job->job_ru

28、nTime; job->job_state="完成" job->job_endTime=count; GetFirstPosition(Qdone,job);/放入完成队列的首位置if(job->job_MissTimes+job->job_doneTimes)*job->job_period=int(count)/完成队列的任务进入下一周期，需投入到就绪队列 DeleteHead(Qdone,job); job->job_llf=(job->job_MissTimes+job->job_doneTimes+1)*job-&g

29、t;job_period-count-job->job_runTime; job->job_state="就绪" OrderJob1(Qready,job);if(!QueueEmpty(Qready)/就绪队列不空，取队头任务 DeleteHead(Qready,job); job->job_state="执行" OrderJob(Qon,job); left_Time=job->job_RneedTime;return 1;/-实现抢占时作业的上下文切换-int CMyDlg:Job_Qiangdiao() POINT_wor

30、k job;job=new(work);if(!QueueEmpty(Qon)/若队列不为空，则取出已经运行过的作业，再投入就绪队列等待DeleteHead(Qon,job);job->job_llf=(job->job_MissTimes+job->job_doneTimes+1) * (job->job_period) - count -job->job_RneedTime;job->job_state="就绪"job->job_flag=1;job->job_identify=0;OrderJob(Qready,job)

31、;if(!QueueEmpty(Qready)/若就绪队列不空，则取出队头作业运行DeleteHead(Qready,job);job->job_state="执行"OrderJob(Qon,job);/left_Time=job->job_RneedTime;return 1;/-显示就绪队列-int CMyDlg:Show_Qready() CString period,runtime,llf,rneedtime;CMyDlg:Show_Qdone();/Q.ready的很多作业是有Q.done传递过去的if(!QueueEmpty(Qready)/如果不为

32、空int flag=0;m_list2.DeleteAllItems();/所有的显示都是静态的，要清除显示POINT_QNode p;loop1:p=Qready.front->next; int i=0;/记录表的行数 while(p)/p指向第一个有效元素 if(QueueEmpty(Qon) && count!=0)/没有正在执行的且运行时间不为0 都在完成队列中，没有进入下一周期n1=0;n0=1;/要进行上下文切换，将n0置为1CMyDlg:Job_Qiangdiao();/上下文切换，但Q.ready也没有作业，所以执行了也看不出来goto loop1;if

33、(p->data->job_identify=1)/若果该作业已经完整地运行过，则应重新开始运行，将剩余时间变为需执行时间，不属于切换p->data->job_RneedTime=p->data->job_runTime;if(p->data->job_llf=1000)if(p->data->job_period *(p->data->job_MissTimes+ p->data->job_doneTimes)=int (count)p->data->job_llf=(p->data->

34、;job_MissTimes+p->data->job_doneTimes+1)*(p->data->job_period)-count-(p->data->job_RneedTime);p->data->job_llf=(p->data->job_MissTimes+p->data->job_doneTimes+1)*(p->data->job_period)-count-(p->data->job_RneedTime);period.Format("%d",p->dat

35、a->job_period);runtime.Format("%d",p->data->job_runTime);llf.Format("%d",p->data->job_llf);rneedtime.Format("%d",p->data->job_RneedTime);if(flag=0)if(p->data->job_llf=0)/如果就绪队列里的一个作业最低松弛度变为0,且正在执行队列里的作业没执行完,则抢断,否则为正常执行POINT_work job;flag=1;job

36、=new(work);/先申请一块内存，使得GetHeadElem(Qon,job);的头结点得以保存GetHeadElem(Qon,job);if(job->job_RneedTime!=0)/抢占的情况n1=0;/是否被抢断的标志 此次周期内第一次执行n0=1;/n0是在上下文切表示，kill时钟CMyDlg:Job_Qiangdiao();/先来先服务的上下切换goto loop1;else;if(flag=1)if(p->data->job_llf=0)p->data->job_MissTimes+;p->data->job_llf=1000;

37、OrderQueue(Qready);/放入就绪队列m_list2.DeleteAllItems();goto loop1;m_list2.InsertItem(i,NULL);m_list2.SetItemText(i,0,p->data->job_id);m_list2.SetItemText(i,1,p->data->job_state);m_list2.SetItemText(i,2,period);m_list2.SetItemText(i,3,runtime);m_list2.SetItemText(i,4,llf);m_list2.SetItemText(

38、i,5,rneedtime);i+;p=p->next; else m_list2.DeleteAllItems();return 1;七、体会与自我评价这次操作系统课设题目是采用最低松弛度优先调度的实时系统调度程序的模拟，刚开始对他的了解仅限于课本上的算法例子，未曾想过用可视化的界面呈现出一个完整的运行过程。由于是大二下做C+的课程设计才用到过MFC，之后就没有用过，所以当决定用MFC做以呈现可视化时，决定重新温习一遍MFC的知识。包括去网上找孙鑫视频（讲MFC部分）以及去图书馆借相关书籍。由于此次课程设计要求以动态结果显示各任务的完成情况，所以免不了要运用到队列相关知识。之前学习数据结构的基础不是很强，尤其是对于指针部分。所以这次特别再看了一遍数据结构书本和以前的PPT，还有参考了一本数据结构与算法(C语言版