操作系统进程调度算法课程设计报告

1操作系统原理课程设计报告题目：进程调度算法课程名称：操作系统姓名：柴婉宁学号：1133050103专业：计算机科学与技术学校：辽宁科技大学指导老师：张静日期：2014.3.12目录一．设计要求--------------------------------------3二．设计思想流程--------------------------------3三．数据结构--------------------------------------5四．程序清单--------------------------------------6五．运行结果--------------------------------------9六．实验体会--------------------------------------11七．设计心得--------------------------------------12八．参考文献--------------------------------------123进程调度算法一.设计要求1.编写一个进程调度程序，允许多个进程并行执行。2.每个进程有一个进程控制块（PCB）表示。进程控制块可以包含如下信息：进程名、优先数、到达时间、需要运行时间、已用CPU时间、进程状态等等。3.进程的优先数及需要的运行时间可以事先人为地指定（也可以由随机数产生）。进程的到达时间为输入进程的时间。二．设计思想流程1.优先权调度模拟流程图YNready-queue是否为空输入开始进程数nRunning＝逐个将redy_pc中的PCB创建n个PCB并加入ready－queue中开始Running=id4NYYNNYYNNY将Running从ready_queue中删除，再将running加入block_queueb随机对block_queue中的进程PCB询问是否要唤醒？创建新进程并加入到ready_queue中处理完了吗阻塞Running是否要唤醒是否创建新PCBRunning=idle更新新进程就绪队列进程优先数，优先数加15优先权调度模拟流程图2.按时间片轮转调度模拟流程图YNNYYN将其从blick_queuek队列是中删除，再将其加入ready_queuekready-queue是否为空将Running从ready_queue中删除，再将running加入block_queueb输入开始进程数nRunning＝逐个将redy_pc中的PCB创建n个PCB并加入ready－queue中阻塞RunningRunning=idleRunning=id开始6NYYNNYY时间片轮转调度模拟流程图三．数据结构1.进程管理程序调试好后运行进程管理程序2.优先权调度（1）输入1选择优先权调度算法模拟。（2）输入开始进程个数n，创建n个PCB并加入就绪队列ready_queue中。（3）就绪队列ready_queue不为空，调度就绪队列中第一个进程运行，否则，从闲逛队列idleprocess中调度闲逛进程运行。将其从blick_queuek队列是中删除，再将其加入ready_queuek随机对block_queue中的进程PCB询问是否要唤醒？创建新进程并加入到ready_queue中处理完了吗是否要唤醒是否创建新PCB7（4）在运行过程中，当遇到阻塞，则该进程插入到阻塞队列block_queue中，且将该进程从ready_queue中删除。（5）如果运行时间CPUtime大于等于Alltime，该进程运行完毕，释放该进程；否则插入到就绪队列中。（6）更新就绪队列中的优先级数。（7）随机对阻塞队列block_queue中的进程PCB询问是否要唤醒，唤醒，即从唤醒队列中选择第一个进程，且插入就绪队列中；阻塞队列中没有阻塞进程返回。（8）重复上述步骤，直到本次调度结束。3.按时间片轮转调度（1）输入2选择优先权调度算法模拟。（2）输入开始进程个数n，创建n个PCB并加入就绪队列ready_queue中。（3）就绪队列ready_queue不为空，调度就绪队列中第一个进程运行，否则，从闲逛队列idleprocess中调度闲逛进程运行。（4）在运行过程中，当遇到阻塞，则该进程插入到阻塞队列block_queue中，且将该进程从ready_queue中删除。（5）如果运行时间CPUtime大于等于Alltime，该进程运行完毕，释放该进程；否则插入到就绪队列中。（6）随机对阻塞队列block_queue中的进程PCB询问是否要唤醒，唤醒，即从唤醒队列中选择第一个进程，且插入就绪队列中；阻塞队列中没有阻塞进程返回。（7）如果时间到，本次调度结束，否则重复上述步骤，直到本次调度结束。四.源程序代码#includestdio.h#includestdlib.h#includetime.h#defineN5//进程个数，可改变intrt[N];//到达时间intst[N];//服务时间intct[N];//完成时间8intcyt[N];//周转时间floatrct[N];//带权周转时间floatav[2];intn,m,c=1,which;voidline()//美化程序，使程序运行时更加明朗美观{printf(------------------------------------------------------------------\n);}voidstart()//表示FCFS算法开始{line();printf(FCFS算法开始\n);printf(——DesignedbyZhangHong\n);line();}voidend()//表示FCFS算法结束{line();printf(FCFS算法结束,谢谢使用\n);line();}voidinput(){printf(请输入%d个进程的到达时间：,N);for(n=0;nN;n++)scanf(%d,&rt[n]);printf(请输入%d个进程对应的服务时间：,N);for(n=0;nN;n++)scanf(%d,&st[n]);}9voidrandom(){srand((unsigned)time(NULL));for(n=0;nN;n++){rt[n]=rand()%100;for(m=0;mn;m++)if(n!=0&&rt[n]==rt[m]){rt[n]=rand()%100;m=0;}st[n]=rand()%98+1;for(m=0;mn;m++)if(n!=0&&st[n]==st[m]){st[n]=rand()%98+1;m=0;}}}voidordination()//重新排序，应对出现输入的到达时间为乱序的情况{inttemp;for(n=0;nN;n++)for(m=0;mN-n-1;m++)if(rt[m+1]rt[m]){temp=rt[m+1];10rt[m+1]=rt[m];rt[m]=temp;temp=st[m+1];st[m+1]=st[m];st[m]=temp;}}voidfcfs()//执行fcfs算法{av[0]=0;av[1]=0;ct[0]=rt[0]+st[0];for(n=1;nN;n++){if(ct[n-1]=rt[n])//考虑当前一个进程完成而后一个进程还没有到达的情况ct[n]=ct[n-1]+st[n];elsect[n]=rt[n]+st[n];}for(n=0;nN;n++)cyt[n]=ct[n]-rt[n];for(n=0;nN;n++)rct[n]=(float)cyt[n]/(float)st[n];for(n=0;nN;n++){av[0]+=(float)cyt[n]/N;av[1]+=rct[n]/N;}}11voidoutput()//输出结果{line();printf(进程名\t);for(n=0;nN;n++)printf(\t%c,65+n);printf(\t平均\n到达时间);for(n=0;nN;n++)printf(\t%d,rt[n]);printf(\n服务时间);for(n=0;nN;n++)printf(\t%d,st[n]);printf(\n完成时间);for(n=0;nN;n++)printf(\t%d,ct[n]);printf(\n周转时间);for(n=0;nN;n++)printf(\t%d,cyt[n]);printf(\t%0.1f,av[0]);printf(\n带权周转时间);for(n=0;nN;n++)printf(\t%0.1f,rct[n]);printf(\t%0.1f,av[1]);printf(\n);line();}voidmain(){start();for(;c==1;)12{for(;;){printf(输入数据还是由系统随机产生数据？\n1、输入数据\t2、系统随机产生数据\n请输入：);scanf(%d,&which);if(which==1){input();break;}elseif(which==2){random();break;}printf(输入错误，请重新输入！);}ordination();//进程按照到达时间进行排序fcfs();output();printf(继续输入，退出输入。请输入：);scanf(%d,&c);}end();}五．运行结果13图1进程管理调试界面14图2优先调度运行结果15图3轮转调度运行结果六.实验体会1、当把该算法用于作业调度时，系统将从后备队列中选择若干个优先权最高的作业，装入内存，当用于进程调度算法时，该算法是把处理及分配给就绪队列中优先权最高的进程。2、当系统空闲（就绪队列为空）时，系统运行闲逛进程，否则运行其他进程，发生变迁（就16绪运行）3、在运行进程（包括闲逛进程）的过程中，可能发生变迁2(运行阻塞)，即将运行进程插入到阻塞队列（闲逛进程不能不被阻塞），可能有其他的进程创建PCB，还可能唤醒阻塞队列中的某些进程PCB，发生变迁3（阻塞就绪），即从阻塞队列中插入就绪队列中。4、时间片运行结束后，若进程累积占用CPU时间大于等于进程需要运行时间，则进程执行结束，释放其PCB。若进程累积占用CPU时间小于进程需要运行时间，发生变迁4（运行就绪），即将当前运行的进程插入就绪队列中。七．设计心得通过做本实验，我在以前学过的知识的基础上有了提高，学到了很多新知识：比如将用户作业和就绪进程按提交的顺序或变为就绪状态的先后排成队列，并按照先来先服务的方式进行调度。调度时从后备队列中选择若干优先权最高的个作业进入内存；或从就绪队列中选择优先权最高的进程，将处理机分配给它。对进程优先、进程或作业先来先服务、按时间片轮转调度算法以及进程调度的概念和算法，有了更深入的认识！初步理解了操作系统对于作业处理的基本思想！了解到算法很重要，又更加明白算法本身可以节约时间，而且不同的函数之间在调用的时候要注意很多的问题。在动手操作过程中，体会到了成功的喜悦和遇到问题自己解决的能力，对于我来说是一次提高，让自己多多的在实践中可以加深对理论的理解，也让我明白了以后应该如何更好，更高效的学习。七.参考文献《计算机操作系统》《计算机操作系统实验指导书》《C程序设计》《C语言程序设计_现代方法》