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

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;float starttime;float finishtime;float zztime;float dqzztime;2.2.1时间片的结构体typedef struct node datatype N

7、um,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+)printf("input the %dth pr

8、ocess'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:"); printf("%s",p0

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

10、k.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 jieduanvoid deal(zgxyb *p,float arrivetime,float servicetime,float starttime,float f

11、inishtime,float &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; else pk.starttime=pk-1.finishtime; pk.finishtime=pk-1.finishtime+pk.servicetime; for(k=0;k<=N-1;k+) pk.zztime=pk.finishtime-pk.arrive

12、time; 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; else pm.finishtime=pm-1.finishtime+pm.servicetime; int i=0,n;

13、for(n=m+1;n<=N-1;n+) if(pn.arrivetime<=pm.finishtime) i+; float max=(pm.finishtime-pm+1.arrivetime)/pm+1.servicetime;/第m+1个的响应比 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.arrivetime)/pk+1.servicetime; follow=k

14、+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=r=(linklist)malloc(size

15、of(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->next=s; r=s; scanf("%

16、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->runtime); p=p->next; print

17、f("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)/*如果运行时间大于时间片*/r=p->next;p->runtime=p-

18、>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->next;/*如果进程运行时间小于时间片，就将第一个进程删除*/free(p);p=head-

19、>next;i=1;while(p)/*因为删了一个进程就需要重新从开始设置一遍进程的排列序号*/p->Num=i+;p=p->next;print(head);/*打印进程列表*/pre=head;p=head->next;elseint N; printf("-高响应比调度算法-n"); printf("input the process's number:n"); scanf("%d",&N); input(a,N); zgxyb *c=a; ZGXYB(c,N);4. 运行结果与运行情况

20、分析程序的第一步选择最高响应比调度算法，输入进程输入3个，进程名字提交时间运行时间a23b32c33程序的验证：第一个进程在2点提交，3个小时的执行时间，在2点没有别的进程，所以a先执行，5点执行完后，而在5点执行前，b，c都提交了，所以就要判断响应比，响应比是等待时间加上执行时间，除以执行时间，所以b的响应比是2，c的响应比是5/3,所以b的响应比高，b先执行，最后是c执行，周转时间是完成时间减去提交时间，而带权周转时间是周转时间除以执行时间。经检验，平均周转时间4.67，平均带权周转时间是1.67.，经检验，结果是正确的。如果是时间片轮转则运行结果为：5. 我评价自与总结5.1程序好的方面

21、 本次实验的输入与输出基本满足实验所要求的，最高响应比的调度算法的输出结果采用表格的形式的输出，比较清晰，容易看懂，通过输出结果能够清晰的看出结果的正确与否。输入与输出比较明确，不会出现多种意思。结构比较清晰，不会到处跳转，容易理解。指令之间的跳转不会让人难以理解。最高响应比中进程分为两个状态，等待状态和完成状态，当程序完成时候状态变成完成状态，每次执行只会执行等待状态的进程，不会执行完成状态的进程。结果中还有调度顺序，5.2从本设计得到的收获从本次实验中，我学到了较多东西，首先是结构体的定义和调用，这次实验首先遇到的问题结构体的定义和调用，之后还涉及到指针的跳转，链表的插入与删除，因此指针的

22、跳转是必须要飞行清楚明白的，否则就会出现各种错误，最终将需要修改，而且还必须学会子函数的使用，必须实验各种子函数来实现不同的功能，综合起来才能实现实验所要求的功能。同时函数的头文件也必须要包含多个东西，来适应我们的要求，同时我们还必须根据要求使用多个全局变量，来实现我们的各种要求。5.4其他方法 对与最高响应比的想法：前提设定：参数进程队列按顺序排好。设置一个系统时间变量，记录当前系统时间调度算法思路： 1.系统时间取得第一个进程的提交时间，并执行第一个进程； 2.当某进程执行完成时，系统时间加上该完成进程的运行时间，并删除该节点，若第一个节点的提交时间就比当前系统时间大或等于，此情况下，需要修改系统时间，且此时第一个进程就是下一个该调度的进程，否侧，在从头结点开始扫描进程队列，直到某进程提交时间大于等于当前系统时间，先假设第一个的响应比最高，标志指