进程模拟调度算法课程设计报告

WORD格式可编辑专业知识分享一．课程概述1.1.设计构想程序能够完成以下操作：创建进程：先输入进程的数目，再一次输入每个进程的进程名、运行总时间和优先级，先到达的先输入；进程调度：进程创建完成后就选择进程调度算法，并单步执行，每次执行的结果都从屏幕上输出来。1.2.需求分析在多道程序环境下，主存中有着多个进程，其数目往往多于处理机数目，要使这多个进程能够并发地执行，这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之执行。分配处理机的任务是由处理机调度程序完成的。由于处理机是最重要的计算机资源，提高处理机的利用率及改善系统必（吞吐量、响应时间），在很大程度上取决于处理机调度性能的好坏，因而，处理机调度便成为操作系统设计的中心问题之一。本次实验在VC++6.0环境下实现先来先服务调度算法，短作业优先调度算法，高优先权调度算法，时间片轮转调度算法和多级反馈队列调度算法。1.3.理论依据为了描述和管制进程的运行，系统为每个进程定义了一个数据结构——进程控制块PCB(ProcessControlBlock),PCB中记录了操作系统所需的、用于描述进程的当前情况以及控制进程运行的全部信息，系统总是通过PCB对进程进行控制，亦即，系统是根据进程的PCB而不是任何别的什么而感知进程的存在的，PCB是进程存在的惟一标志。本次课程设计用结构体Process代替PCB的功能。1.4.课程任务一、用C语言（或C++）编程实现操作模拟操作系统进程调度子系统的基本功能；运用多种算法实现对进程的模拟调度。二、通过编写程序实现进程或作业先来先服务、高优先权、按时间片轮转、短作业优先、多级反馈队列调度算法，使学生进一步掌握进程调度的概念和算法，加深对处理机分配的理解。三、实现用户界面的开发WORD格式可编辑专业知识分享1.5.功能模块分析：1、进程概念：进程是被独立分配资源的最小单位。进程是动态概念，必须程序运行才有进程的产生。2、进程的状态模型：（1）运行：进程已获得处理机，当前处于运行状态。（2）就绪：进程已经准备好，一旦有处理器就可运行。3、处理机调度：在多道程序设计系统中，内存中有多道程序运行，他们相互争夺处理机这一重要的资源。处理机调度就是从就绪队列中，按照一定的算法选择一个进程并将处理机分配给它运行，以实现进程并发地执行。4、进程调度算法的功能：记录系统中所有进程的执行情况选择占有处理机的进程进行进程的上下文切换5、进程调度的算法：（1）先来先服务算法：如果早就绪的进程排在就绪队列的前面，迟就绪的进程排在就绪队列的后面，那么先来先服务总是把当前处于就绪队列之首的那个进程调度到运行状态。（2）优先数算法：即进程的执行顺序由高优先级到低优先级。系统或用户按某种原则为进程指定一个优先级来表示该进程所享有的确调度优先权。该算法核心是确定进程的优先级。（3）时间片轮转算法：固定时间片，每个进程在执行一个时间片后，轮到下一进程执行，知道所有的进程执行完毕。处理器同一个时间只能处理一个任务。处理器在处理多任务的时候，就要看请求的时间顺序，如果时间一致，就要进行预测。挑到一个任务后，需要若干步骤才能做完，这些步骤中有些需要处理器参与，有些不需要（如磁盘控制器的存储过程）。不需要处理器处理的时候，这部分时间就要分配给其他的进程。原来的进程就要处于等待的时间段上。经过周密分配时间，宏观上就象是多个任务一起运行一样，但微观上是有先后的，就是时间片轮换。(4)多级反馈队列法：又称反馈循环队列或多队列策略，主要思想是将就绪进程分为两级或多级，系统相应建立两个或多个就绪进程队列，较高优先级的队列一般分配给较短的时间片。处理器调度先从高级就绪进程队列中选取可占有处理器的进程，只有在选不到时，才从较低级的就绪进程队列中选取。（5）短作业优先法：对短进程优先调度的算法，它是从后备队列中选择一个或者若干个进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再重新调度。WORD格式可编辑专业知识分享二．设计方案2.1．先来先服务调度2.1.1．算法思想先来先服务调度算法的思想是按照进程进入就绪队列的先后顺序调度并分配处理机执行。先来先服务调度算法是一种不可抢占的算法，先进入就绪队列的进程，先被处理机运行。一旦一个进程占有了处理机，它就一直运行下去，直到该进程完成工作或者因为等待某事件而不能继续运行时才释放处理机。2.1.2．算法流程图调度队首的作业投入运行：（更改队首指针，使作业的状态为R，记住作业开始运行的时刻Tb等等）初始化所有JCB使JCB按作业提交时刻的先后顺序排队时间量T:=0计算并打印运行作业i的完成时刻Tc,周转时间Ti，带权周转时间Wi(完成时刻Tc=开始运行时刻+运行时间周转时间Ti=完成时间-提交时间带权周转时间Wi=周转时间÷运行时间)更改时间量T的值（T:=T+作业1的运行时间）等待队列空？计算并打印这组作业的平均周转时间及带权平均周转时间结束开始不空空图1.先来先服务算法流程图WORD格式可编辑专业知识分享2.1.3．程序代码#includestdio.h#includestdlib.h#includestring.htypedefstructnode{charname[10];/*进程名*/intcputime;/*占用cpu时间*/charstarttime[5];//进程开始时间intneedtime;/*要求运行时间*/charstate;/*状态*/structnode*next;/*指针*/}PCB;PCB*ready,*run,*finish;//就绪、执行、结束指针intN;//进程数量voidprint()//输出函数{PCB*p;printf(NAMECPUTIMESTARTTIMENEEDTIMESTATUS\n);if(run!=NULL)printf(%-10s%-10d%-10s%-10d%c\n,run-name,run-cputime,run-starttime,run-needtime,run-state);/*输出执行的进程的信息*/p=ready;while(p!=NULL){printf(%-10s%-10d%-10s%-10d%c\n,p-name,p-cputime,p-starttime,p-needtime,p-state);/*输出就绪进程的信息*/p=p-next;}p=finish;while(p!=NULL){printf(%-10s%-10d%-10s%-10d%c\n,p-name,p-cputime,WORD格式可编辑专业知识分享p-starttime,p-needtime,p-state);/*输出结束队列的信息*/p=p-next;}getchar();/*使用getchar()函数可以让输出时停留画面，等待人按回车继续*/}voidinsert(PCB*q)/*插入新进程，把进程按进程到来时间大小排序*/{PCB*p1,*s,*r;intb;s=q;/*指针s指向新要插入的进程*/p1=ready;/*指针p1指向原来的进程队列的队首*/r=p1;/*使用指针r是指向p1前面的进程*/b=1;while((p1!=NULL)&&b)if(strcmp(p1-starttime,s-starttime)0){r=p1;p1=p1-next;}/*新进程的开始时间大，则p1指向下一个进程继续比*/elseb=0;if(r!=p1){r-next=s;s-next=p1;}/*新进程找到位置，插在r和p1之间*/else{s-next=p1;ready=s;}/*新进程的开始时间按最小，插在队首，并修改就绪队首ready指针*/}voidcreate(){PCB*p;inti;ready=NULL;run=NULL;finish=NULL;printf(PleaseenterthenameandtimeandstarttimeofPCB:\n);/*输入进程名、运行时间和开始时间*/for(i=0;iN;i++){p=(PCB*)malloc(sizeof(PCB));/*为新进程开辟空间*/WORD格式可编辑专业知识分享scanf(%s,p-name);/*输入进程名*/scanf(%d,&p-needtime);/*输入进程要求运行时间*/scanf(%s,p-starttime);//输入进程开始时间p-cputime=0;p-state='W';/*表示就绪队列中未在队首先执行，但也是就绪状态*/if(ready!=NULL)insert(p);/*就绪队首不为NULL，插入新进程*/else{/*否则先插在NULL前*/p-next=ready;ready=p;}}printf(Displayisgoingtostart:\n);printf(***********************************************\n);print();getchar();run=ready;/*队列排好，run指向就绪队列队首*/ready=ready-next;/*ready指向下一个进程*/run-state='R';/*队首进程的状态为就绪*/}voidFCFS(){while(run!=NULL){run-cputime=run-cputime+run-needtime;run-needtime=0;run-next=finish;finish=run;run-state='E';run=NULL;if(ready!=NULL){run=ready;run-state='R';ready=ready-next;}print();}}voidmain(){printf(PleaseenterthetotalnumberofPCB:\n);scanf(%d,&N);WORD格式可编辑专业知识分享create();/*模拟创建进程，并输入相关信息*/FCFS();/*先来先服务调度算法*/}2.1.4．测试结果及说明首先输入进程个数（为5个），这里命名为A,B,C,D,E，然后分别输入运行时间和开始时间所有进程都在队列中，并都处于等待状态其中一个进程执行完毕所有进程都执行完毕2.2．优先级调度2.2.1．算法思想进程的执行顺序由高优先级到低优先级，系统或用户按某种原则为进程指定WORD格式可编辑专业知识分享一个优先级来表示该进程所享有的确调度优先权。该算法核心是确定进程的优先级。2.2.2．算法流程图图2.优先级调度流程图2.2.3．程序代码#includestdio.h#includestdlib.h#includestring.htypedefstructnode{charname[10];/*进程名*/intprio;/*优先数*/intcputime;/*占用cpu时间*/intneedtime;/*要求运行时间*/charstate;/*状态*/structnode*next;/*指针*/}PCB;PCB*ready,*run,*finish;/*就绪执行结束指针*/intN;voidprt()/*输出函数，可以方便看到进程执行的演示*/{PCB*p;printf(NAMECPUTIMENEEDTIMEPRIORITYSTATUS\n);WORD格式可编辑专业知识分享if(run!=NULL)printf(%-10s%-10d%-10d%-10d%c\n,run-name,run-cputime,run-needtime,run-prio,run-state);/*输出执行的进程的信息*/p=ready;while(p!=NULL){printf(%-10s%-10d%-10d%-10d%c\n,p-name,p-cputime,p-needtime,p-prio,p-s