时间片轮转、最高响应比优先调度算法剖析

1、学 号：课程设计题 学 专 班 姓曰 时间片轮转、最高响应比优先调度曰算法院计算机科学与技术业级名指导教师吴利军2013年 1 月 14 日课程设计任务书学生姓名：指导教师：吴利军工作单位： 计算机科学与技术学院题目：进程调度模拟设计 时间片轮转、最高响应比优先调度算法初始条件:1 预备内容：阅读操作系统的处理机管理章节内容，对进程调度的功能以及进程 调度算法有深入的理解。2 实践准备：掌握一种计算机高级语言的使用。要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1 模拟进程调度，能够处理以下的情形： 能够选择不同的调度算法（要求中给出的调度算法）； 能够输入进

2、程的基本信息，如进程名、到达时间和运行时间等；根据选择的调度算法显示进程调度队列； 根据选择的调度算法计算平均周转时间和平均带权周转时间。2 设计报告内容应说明：需求分析；功能设计（数据结构及模块说明）； 开发平台及源程序的主要部分； 测试用例，运行结果与运行情况分析；我评价自与总结：i）你认为你完成的设计哪些地方做得比较好或比较出色；ii）什么地方做得不太好，以后如何改正；iii） 从本设计得到的收获（在编写，调试，执行过程中的经验和教训）；iv） 完成本题是否有其他方法（如果有，简要说明该方法）；v）对实验题的评价和改进意见，请你推荐设计题目。时间安排：设计安排一周：周1、周2:完成程序分

3、析及设计。周2、周3:完成程序调试及测试。周4、周5:验收、撰写课程设计报告。（注意事项：严禁抄袭，一旦发现，一律按0分记）指导教师签名：年月日系主任（或责任教师）签名：年月日1. 需求分析1.1 模拟进程调度，能够处理以下的情形 能够选择不同的调度算法（要求中给出的调度算法） ； 能够输入进程的基本信息，如进程名、到达时间和运行时间等； 根据选择的调度算法显示进程调度队列； 根据选择的调度算法计算平均周转时间和平均带权周转时间。1.2 这个实验主要是进程调度模拟设计， 进程调度有很多方法， 这个课程设计要求我要使用时间片轮转和最高响应比两中算法，来实现对进程的模拟。 首先他要求能够用两种方法

4、实现进程调度，我们需要首先输出一个选择程 序，来选择一个调度算法， 入数据来进行运算， 这是我们首先要解决的问题。 其次，我们要接近输入数据的存放问题，毕竟我还需要数据来进行操作和调 度。我们要用结构体来存放一个进程的相关信息，例如：进程名字，进程到 达时间，进程的运行时间。但是我们在出来进程的时候，还必须要按照一定 的顺序来处理，所以我们必须要对结构体里存放的进程相关信息来进行排序。 只有经过处理过后，才能更容易的实现进程的调度，同时当不只一个进程的 时候，我们还必须设置用多个地址单元来实验对输入的数据进行存储，多个 输入就相当于的链表的插入处理，因此我们又必须要对链表之间的指针进行 处理，

5、这涉及到指针的跳转，我们 必须要运用我们所学的知识进行。 我们还必须要对程序的输出进行处理，因为按照实验要求，我们 必须显示进程调度队列；根据选择的调度算法计算平均周转时间和平均带 权周转时间。这要求我们要设计算法，将进程的调度顺序给输出，从输出 就可以检查自己的设计是否是正确的，而响应比其实进程的等待时间加上 执行时间，在除以执行时间，得到的结果就是响应比。而最高响应比就是 没当一个进程执行完成后，在这个时间比较各个时间各个进程的响应比， 响应比最大的就会执行， 而其他的进程则继续等待， 一直循环做这个操作， 这就是所谓的是最高响应比调度算法。 时间片轮转法就是将 CPU 的执行时 间分成一

6、个个大小相等的时间片，将这些时间片分别执行就绪队列中的进 程，时间片用完的进程就会回答就绪队列的队尾，等待 CPU 的再次执行。 而周转时间则是完成时间减去提交时间， 平均周转时间就是几个进程的周转 时间的平均值。而带权周转时间就是周转时间除以执行时间。2. 功能设计2.1 最高响应比的功能设计2.1.1 最高响应比的结构体struct zgxybchar name10;float arrivetime;float servicetime;floatstarttime;floatfinishtime;floatzztime;floatdqzztime;2.2.1 时间片的结构体typedef

7、struct nodedatatype Num,runtime;char Name10; / 定义成字符串struct node *next;linknode;3. 开发平台及源程序的主要部分3.1 实验的开发平台Visual C+ 6.03.2 实验的主要代码void input(zgxyb *p, int N) int i;printf( "intput the process's name & arrivetime & servicetime:nfor exmple: a 0 100n");for (i=0;i<=N-1;i+)print

8、f( "input the %dth process's information:n" ,i+1);scanf( "%s%f%f",&,&pi.arrivetime,&pi.servicetime);void Print(zgxyb *p, float arrivetime, float servicetime, float starttime, float finishtime, float zztime, float dqzztime, int N)int k;printf("run order

9、:" );printf("%s" ,);for (k=1;k<N;k+)printf( "->%s" ,);printf( "nthe process's information:n" );printf( "nnametarrivetservicetstarttfinishtzztdqzzn" );,,pk.arrivetime,pk.sfor (k=0;k<=N-1;k+) printf( "%st%-.2ft%-.2ft%-

10、.2ft%-.2ft%-.2ft%-.2ftn" ervicetime,pk.starttime,pk.finishtime,pk.zztime,pk.dqzztime);/ 按到达时间排序void sort(zgxyb *p, int N)for (int i=0;i<=N-1;i+)for (int j=0;j<=i;j+)if (pi.arrivetime<pj.arrivetime)zgxyb temp;temp=pi;pi=pj;pj=temp;/yun xing jieduanfloatvoid deal(zgxyb *p, float arriveti

11、me, float servicetime, float starttime, float finishtime, &zztime, float &dqzztime, int N) int k;for (k=0;k<=N-1;k+)if (k=0)pk.starttime=pk.arrivetime; pk.finishtime=pk.arrivetime+pk.servicetime;elsepk.starttime=pk-1.finishtime; pk.finishtime=pk-1.finishtime+pk.servicetime;for (k=0;k<=

12、N-1;k+)pk.zztime=pk.finishtime-pk.arrivetime; pk.dqzztime=pk.zztime/pk.servicetime;void ZGXYB(zgxyb *p, int N)float arrivetime=0,servicetime=0,starttime=0,finishtime=0,zztime=0,dqzztime=0; sort(p,N);for (int m=0;m<N-1;m+)if (m=0)pm.finishtime=pm.arrivetime+pm.servicetime;elsepm.finishtime=pm-1.fi

13、nishtime+pm.servicetime;int i=0,n;for (n=m+1;n<=N-1;n+)if (pn.arrivetime<=pm.finishtime)i+;/第m+个的响应float max=(pm.finishtime-pm+1.arrivetime)/pm+1.servicetime; 比int follow=m+1;for (int k=m+1;k<m+i;k+)if (max<=(pm.finishtime-pk+1.arrivetime)/pk+1.servicetime) max=(pm.finishtime-pk+1.arrive

14、time)/pk+1.servicetime;follow=k+1;zgxyb temp;temp=pm+1;pm+1=pfollow;pfollow=temp;deal(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N); Print(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N);linklist creatlinklist()linklist head,r,s;int x,y;char ch10; / 因为要输的是字符串head=

15、r=(linklist)malloc( sizeof (linknode);printf( "n 请输入一组编号，作业名，运行时间，以结尾 n" );scanf( "%d %s %d",&x,&ch,&y);while (x)int a =10;s=(linklist)malloc( sizeof (linknode); s->Num=x;s->runtime=y;/strcpy(s->Name,ch);/ 直接字符串复制 for ( int i=0;i<a; i+) s->Namei=chi;r-&

16、gt;next=s;r=s;scanf( "%d %s %d",&x,&ch,&y);r->next=NULL;return head;/* 输出带头结点的单链表 */void print(linklist head)linklist p;p=head->next;printf( "List is:n" );printf( "Num Name runtimen" );while (p)printf( "%d%5s%6dn",p->Num,p->Name,p->r

17、untime); p=p->next;printf( "n" );void main()int G; scanf( "%d",&G);if (G=1)linklist head,pre,p,r;int t,i;head=creatlinklist(); print(head);printf( " 请输入 runtime:" );scanf( "%d",&t);pre=head; p=head->next;while (p)if (p->runtime>t) /* 如果运行时间

18、大于时间片 */r=p->next;p->runtime=p->runtime-t; /* 将第一个进程的运行时间减去一个时间片的时间 */ while (r->next) /*将r指向链表的最后一个结点以便用尾插法将P结点插入到链表的最后*/r=r->next;pre->next=p->next; p->next=NULL; r->next=p;p=head->next;i=1;while (p) /* 将进程的序号重新从开始设置一遍 */p->Num=i+;p=p->next;elsepre->next=p-&g

19、t;next; /* 如果进程运行时间小于时间片，就将第一个进程删除 */free(p); p=head->next;i=1;while (p) /* 因为删了一个进程就需要重新从开始设置一遍进程的排列序号 */p->Num=i+;p=p->next;print(head); /*打印进程列表*/ pre=head;p=head->next;else int N;printf("-一- 高响应比调度算法-n");printf( "input the process's number:n");scanf( "%d&

20、quot;,&N);input(a,N);zgxyb *c=a;ZGXYB(c,N);4. 运行结果与运行情况分析程序的第一步选择最高响应比调度算法，输入进程输入 3个,进程名字提交时间运行时间a23b32c33程序的验证：第一个进程在2点提交，3个小时的执行时间，在2点没有别的进程，所以a先 执行，5点执行完后，而在5点执行前，b，c都提交了，所以就要判断响应比， 响应比是等待时间加上执行时间，除以执行时间，所以b的响应比是2，c的响应比是5/3，所以b的响应比高，b先执行，最后是c执行，周转时间是完成时间 减去提交时间，而带权周转时间是周转时间除以执行时间。经检验，平均周转时间4.

21、67,平均带权周转时间是1.67.,经检验，结果是正确的。*C: XDocuaent s and Setting£AdunistEator.Debu£v_ exev高1向应比调度算法Lnput the processfs number：Lntput the processJ s name 8r arriuetime & servicet ime -ror exmple:a0 100Inputthe1thprocess1sL 2 3Inputthe2thprocess1sL 3 2jnputthe3thprocess1sinfornation- info mat io

22、n : infornation"fcuni order：a>b-=>c:he process1s infcreation:at*Fineset*u icestartfinishdsz2.003.0Q2.005.063.001.Q03.002 .00S.007.034.032.&03 _603 _0S7.0010.807.002.33已riy losy to continuesi*ess如果是时 间 片轮转则 运行结果为：=: Dociu.en-t s and Sett xngsAdKiniist r at orDebug.es e *请输入一组编号，作业名，运行时

23、间，以B结尾1 a 53 Jb 103 c 40 0 0List is:Nurni Name runt ime1 a52 b10请输入FlintiM ：5List is：Num Hane Mint ine1 b182 c 4List is:iNum HaneruntineRjlstnum Hame runtime k b 5(List is：Hum Hamorun t imolPfess any key tocontinue5. 我评价自与总结5.1 程序好的方面本次实验的输入与输出基本满足实验所要求的， 最高响应比的调度算法的输出 结果采用表格的形式的输出， 比较清晰， 容易看懂，通过输出结

24、果能够清晰的看 出结果的正确与否。输入与输出比较明确，不会出现多种意思。结构比较清晰， 不会到处跳转， 容易理解。 指令之间的跳转不会让人难以理解。 最高响应比中进 程分为两个状态， 等待状态和完成状态， 当程序完成时候状态变成完成状态， 每 次执行只会执行等待状态的进程， 不会执行完成状态的进程。 结果中还有调度顺 序，5.2 从本设计得到的收获从本次实验中， 我学到了较多东西， 首先是结构体的定义和调用， 这次实验首先 遇到的问题结构体的定义和调用， 之后还涉及到指针的跳转， 链表的插入与删除， 因此指针的跳转是必须要飞行清楚明白的， 否则就会出现各种错误， 最终将需要 修改，而且还必须学会子函数的使用，必须实验各种子函数来实现不同的功能， 综合起来才能实现实验所要求的功能。同时函数的头文件也必须要包含多个东 西，来适应我们的要求， 同时我们还必须根据要求使用多个全局变量， 来实现我 们的各种要求。5.4 其他方法对与最高响应比的想法：前提设定：参数进程队列按顺序排好。 设置一个系统时间变量，记录当前系统时间调度算法思路：1.系统时间取得第一个进程的提交时间，并执行第一个进程；2.当某进程执行完成时，系统时间加上该完成进程的运行时间 ，并删除该节点，若第一个节点的提交时间就比当前系统时间大 或等于，此情况下，需要修改系统时间，且此时第一个进程就是 下一个该调度的进程，否侧，