《操作系统原理与Linux》课程设计报告

《操作系统原理与Linux》课程设计报告专业班级学号姓名指导教师完成时间成绩进程调度算法一一、、设设计计题题目目：：进进程程调调度度算算法法二二、、设设计计目目的的通过对进程调度算法的编写加强对操作系统的加深了解，从而进一步的让我们清楚个进程之间的运行情况，对优先权算法与轮转调度算法的模拟加强对进程概念和进程的调度过程的理解，掌握进程状态之间的切换，同时掌握进程调度算法的实现方法和技巧。三三、、设设计计要要求求要求实现先来先服务,短作业优先,时间片轮转,优先权调度算法四种算法并进行对比分析.四四、、设设计计思思想想说说明明1、先来先服务算法：按照进程进入就绪队列的先后次序，分派CPU，当前进程占用CPU，直到执行完或阻塞，才出让CPU（非抢占方式）。在进程唤醒后（如I/O完成），并不立即恢复执行，通常等到当前进程让出CPU。P(s)执行指针→就绪队列队首PCB表进入选中进程的程序入口将就绪队列队首的PCB表摘下P(n)将PCB表置为执行状态,为选中进程重布现场V(s)先来先服务算法的实现过程如图所示。设置信号量：就绪队列互斥信号量s，初值为1；就绪队列中进程个数n，初值为0。2、短作业优先：选择就绪队列中估计运行时间最短的进程投入运行。通常后来的短作业不抢先正在执行的作业。比FCFS改善平均周转时间和平均带权周转时间，缩短作业的等待时间提高系统的吞吐量。3、时间片轮转调度算法：通过时间片轮转，提高进程并发性和响应时间特性，从而提高资源利用率。将系统中所有的就绪进程按照FCFS原则，排成一个队列。每次调度时将CPU分派给队首进程，让其执行一个时间片。时间片的长度从几个ms到几百ms。在一个时间片结束时，发生时钟中断。调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过CPU现场切换执行当前的队首进程。进程可以未使用完一个时间片，就出让CPU（如阻塞）。4、优先权调度算法：优先选择就绪队列中优先级最高的进程投入运行。分为：非抢占式优先级算法：仅发生在进程放弃CPU。抢占式优先级算法：可剥夺当前运行进程CPU。五五、、系系统统结结构构的的说说明明六六、、数数据据结结构构的的说说明明用C语言或C++语言来实现对N个进程采用优先算法以及轮转算法的调度。队列指针Next用来将多个进错控制块PCB链接为队列。voidinit();/*产生idle进程，输入用户进程数目，调用insert()*/voidprint(PCB*pcb);/*输出进程属性信息*/voidprint_init(PCB*pcb);/*输出所有PCB的初始值*/voidinsert();/*生成进程属性信息，插入进程就绪队列*/voidRun_priority(PCB*pcb);/*运行进程，随机阻塞进程、产生新进程，插入就绪队列，唤醒阻塞进程*/voidblock(PCB*pcb);/*调用destroy()将进程插入阻塞队列*/voidwakeup();/*唤醒进程，插入就绪队列*/voidproc_priority();/*优先权调度算法模拟*///voidRun_loop(PCB*pcb);voidproc_loop();/*轮转法调度算法模拟*/voidupdate(PCB*pcb);/*更新进程信息*/voidpushback_queue(PCB*queue,PCB*item);/*将item插入到队列的尾部*/voidinsert_queue(PCB*queue,PCB*item);/*将item插入到队列中，使得插入后，队列中按照优先级从高到低有序*/voidsort_queue(PCB*&queue);/*对queue中的结点进行排序，按照优先级从大到小*/PCB*ready_queue,*block_queue,*idleprocess;/*就绪队列，阻塞队列及闲逛进程指针变量*/七七、、程程序序清清单单：：短作业优先：#includestdio.hstructsjf{charname[10];floatarrivetime;floatservicetime;floatstarttime;floatfinishtime;floatzztime;floatdqzztime;};sjfa[100];voidinput(sjf*p,intN){inti;printf(intputtheprocess'sname&arrivetime&servicetime:\nforexmple:a0100\n);for(i=0;i=N-1;i++){printf(inputthe%dthprocess'sinformation:\n,i+1);scanf(%s%f%f,&p[i].name,&p[i].arrivetime,&p[i].servicetime);}}voidPrint(sjf*p,floatarrivetime,floatservicetime,floatstarttime,floatfinishtime,floatzztime,floatdqzztime,intN){intk;printf(runorder:);printf(%s,p[0].name);for(k=1;kN;k++){printf(--%s,p[k].name);}printf(\ntheprocess'sinformation:\n);printf(\nname\tarrive\tservice\tstart\tfinish\tzz\tdqzz\n);for(k=0;k=N-1;k++){printf(%s\t%-.2f\t%-.2f\t%-.2f\t%-.2f\t%-.2f\t%-.2f\t\n,p[k].name,p[k].arrivetime,p[k].servicetime,p[k].starttime,p[k].finishtime,p[k].zztime,p[k].dqzztime);}}//paixuvoidsort(sjf*p,intN){for(inti=0;i=N-1;i++)for(intj=0;j=i;j++)if(p[i].arrivetimep[j].arrivetime){sjftemp;temp=p[i];p[i]=p[j];p[j]=temp;}}//yunxingjieduanvoiddeal(sjf*p,floatarrivetime,floatservicetime,floatstarttime,floatfinishtime,float&zztime,float&dqzztime,intN){intk;for(k=0;k=N-1;k++){if(k==0){p[k].starttime=p[k].arrivetime;p[k].finishtime=p[k].arrivetime+p[k].servicetime;}else{p[k].starttime=p[k-1].finishtime;p[k].finishtime=p[k-1].finishtime+p[k].servicetime;}}for(k=0;k=N-1;k++){p[k].zztime=p[k].finishtime-p[k].arrivetime;p[k].dqzztime=p[k].zztime/p[k].servicetime;}}voidsjff(sjf*p,intN){floatarrivetime=0,servicetime=0,starttime=0,finishtime=0,zztime=0,dqzztime=0;sort(p,N);for(intm=0;mN-1;m++){if(m==0)p[m].finishtime=p[m].arrivetime+p[m].servicetime;elsep[m].finishtime=p[m-1].finishtime+p[m].servicetime;inti=0;for(intn=m+1;n=N-1;n++){if(p[n].arrivetime=p[m].finishtime)i++;}floatmin=p[m+1].servicetime;intnext=m+1;//m+1=nfor(intk=m+1;km+i;k++){if(p[k+1].servicetimemin){min=p[k+1].servicetime;next=k+1;}}sjftemp;temp=p[m+1];p[m+1]=p[next];p[next]=temp;}deal(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N);Print(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N);}voidmain(){intN;printf(------短作业优先调度算法------\n);printf(inputtheprocess'snumber:\n);scanf(%d,&N);input(a,N);sjf*b=a;sjf*c=a;sjff(b,N);}八八、、使使用用说说明明书书（（即即用用户户手手册册））（（内内容容包包含含如如何何登登录录、、退退出出等等操操作作说说明明））1、登陆MicrosoftVisualC++6.0编译器，创建一个新文件；2、将每个算法的程序代码逐个输入并进行试调运行。（1）、先来先服务算法程序运行结果：当3个不同的进程进入系统时，系统会根据每一个进程的到达时间的快慢对进程的先后顺序进行调整排序，依次从最快到慢的程序开始运行。（2）、短作业优先算法程序运行结果：当3个不同的进程进入到系统时，系统会根据每一个进程的作业时间长短对进程的先后顺序进行调整排序，并依次从最短作业时间开始运行直到最后一个也是作业时间最长的一个便结束调度。（3）、高优先级优先调度算法程序运行结果：当3个不同进程进入系统时，系统根据每一个进程的优先级大小对进程的先后顺序进行调整排序，通过从高优先级的进程开始调度运行到最低级的进程便结束此次进程调度。（4）、优先级时间轮转算法程序运行结果：当3个不同的进程进入系统时，系统根据进程的优先级别对每一个进程进行时间片分配，从第一个进程开始调用运行，每一个进程运行结束便销毁，接着运行下一个进程直到所有的进程结束。3、退出MicrosoftVisualC++6.0编译器九九、、体体会会，，建建议议：：通过本次综合课程设计使我体会到了团队合作的重要性，也终于明白了一个程序可以由几十个人甚至几百个人共同完成的道理。此次的课程设计对于像我这样基础不扎实的人来说确实有难度，不过好在有我们的组员的帮忙与合作，还是勉强完成了此次设计任务！而在此期间通过对各个调度算法程序代码的分析与试调运行，我也大概理解了每个算法的运行过程，也更加直观的了解了每一个进程在系统中的状态，同时也知道了系统是如何通过某一个调度算法对进程进行调度与管理的。这些对我以后该如何学好有关OS中进程部分的知识都有很大的帮助，我也很享受这一次的课程设计！希望自己能在接下来的日子里巩固好相关的基础知识并且能独立完成某些相对简单的课程设计任务！十十、、参参考考文文献献：：《《lliinnuuxx基基础础及及应应用用教教程程实实验验指指导导与与实实训训》》、、《《计计算算机机操操作作系系统统与与UUNNIIXX》》