进程调度

沈阳工程学院学生实验报告（课程名称：操作系统）实验题目：进程调度班级学号姓名地点实训F606指导教师吕海华刘娜实验日期:2015年10月10日1一、实验题目进程调度模拟实验。二、实验要求设计一段程序来模拟优先级调度算法和时间片轮转算法。要求可以指定进程的数量、各进程需要CPU的时间和各进程的优先级。三、实验目的通过模拟进程调度算法，了解进程调度的过程并比较不同的调度算法的区别。四、实验原理分析⑴进程调度算法是指处理机的分配策略。优先数调度算法是指对每个进程确定一个优先数，进程调度总是让具有最高优先数的进程先使用处理机。如果进程具有相同的优先数，再按先来先服务的次序分配处理机。在本实例中采用动态优先数算法。时间片轮转算法是指就绪进程按就绪的先后次序排成队列，每次总是选择就绪队列中的第一个进程占用处理机，但规定只能使用一个“时间片”。⑵系统中的进程可以用进程控制块PCB来表示，PCB的结构定义如表5-8所示：表5-8PCB结构进程标识符charname进程占用CPU时间intcputime进程优先数intprio完成进程还需要的时间intneedtime链指针structpcb*next⑶在进程调度时进程会交替的出现在运行、就绪和完成三种状态。可以定义三个链表来存放三种状态的进程。当进程运行时就把进程放入到运行链表中；当进程处于就绪状态时就将进程放入到就绪链表中；当进程运行完毕时就将进程放入到完成链表中。由于同一时刻运行的进程只能有一个，所以运行链表只能有一个结点。在实例程序中为了使程序更简洁忽略了进程的等待状态，仅运行了优先数调度算法，由于篇幅有限，仅显示部分结果，对于时间片轮转调度算法，请读者自行运行。2⑷主要变量及函数说明如表5-9所示：表5-9主要变量及函数说明structpcb进程控制块结构RUN、READY、FINSH运行、就绪、完成对列voidPRINTLINK(intt)显示三个队列，t为运行的次数PCB*CPCBLINK()建立就绪队列voidJXDLPX()将队列按优先级排序voidYXS()优先数调度算法voidSJP()时间片轮转算法五、实验分析1、流程图3先来先服务4优先级调度算法时间片轮转调度算法52、实验结果截图先来先服务：6时间轮转片：7优先级：893、结果分析先来先服务：根据算法可知，系统按照作业到达的顺序执行，在前作业未执行完成前，后续作业只能等待，所以执行顺序是A—B—C—D优先级：已知该算法是根据作业的等待时间调整优先级，所以该程序减少执行程序的优先级来调整。所以执行顺序是A—B—C时间轮转：该算法是给一个时间片，队首程序先使用，当时间片使用完时，不管程序是否执行完，换下一个程序执行时间片。以此循环，直至所有程序执行完毕。10六、成绩评定优良中及格不及格出勤内容格式分析总评指导教师：年月日11源代码：#includestdio.h#includestring.h#includestdlib.h/********************这是先来先服务的程序*********************************/structfcfs{//定义先来先服务结构体、参数charname[10];floatdaodatime;//到达时间floatfuwutime;//服务时间floatkaishitime;//开始时间floatwanchengtime;//完成时间floatzhouztime;//周转时间floatdaiquantime;//带权周转时间};fcfsa[100];voidinput(fcfs*p,intN)//构造一个输入进程的信息的函数，定义结构体指针{inti;for(i=0;i=N-1;i++){printf(输入第%d个进程的名字、到达时间、服务时间:\n,i+1);scanf(%s%f%f,&p[i].name,&p[i].daodatime,&p[i].fuwutime);//把输入的信息保存到结构体指针所对应的内存中}}//构造一个输出函数voidPrint(fcfs*p,floatdaodatime,floatfuwutime,floatkaishitime,floatwanchengtime,floatzhouztime,floatdaiquantime,intN){intk;printf(执行顺序:\n);printf(%s,p[0].name);12for(k=1;kN;k++){printf(--%s,p[k].name);}printf(\n进程的相关信息如下:\n);printf(\n名字\t到达\t服务\t开始\t完成\t周转\t带权周转\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].daodatime,p[k].fuwutime,p[k].kaishitime,p[k].wanchengtime,p[k].zhouztime,p[k].daiquantime);}//题目中加入-.2是保留双精度的两位。一般f默认保留六位小数的。}voidsort(fcfs*p,intN)//进程根据到达时间进行排序{for(inti=0;i=N-1;i++)for(intj=0;j=i;j++)if(p[i].daodatimep[j].daodatime)//如果i的时间到达时间小于j的到达时间，就交换{fcfstemp;//在结构体中定义第三个变量进行交换temp=p[i];p[i]=p[j];p[j]=temp;}}//核心的运行阶段voiddeal(fcfs*p,floatdaodatime,floatfuwutime,floatkaishitime,floatwanchengtime,floatzhouztime,floatdaiquantime,intN){intk;for(k=0;k=N-1;k++){if(k==0)//K=0,表示第一个进程到达{p[k].kaishitime=p[k].daodatime;//那么开始时间=到达时间p[k].wanchengtime=p[k].daodatime+p[k].fuwutime;//完成时间=到达时间+服务时间}13else{p[k].kaishitime=p[k-1].wanchengtime;//下一个进程的开始时间=上一个进程的完成时间p[k].wanchengtime=p[k-1].wanchengtime+p[k].fuwutime;//完成时间=上一个进程的完成时间+服务时间}}for(k=0;k=N-1;k++)//计算周转时间和带权周转时间{p[k].zhouztime=p[k].wanchengtime-p[k].daodatime;//周转时间=完成时间-到达时间p[k].daiquantime=p[k].zhouztime/p[k].fuwutime;//带权周转时间=周转时间/服务时间}}voidFCFS(fcfs*p,intN)//定义先来先服务函数{floatdaodatime=0,fuwutime=0,kaishitime=0,wanchengtime=0,zhouztime=0,daiquantime=0;//初始化变量为0sort(p,N);//声明排序函数deal(p,daodatime,fuwutime,kaishitime,wanchengtime,zhouztime,daiquantime,N);//声明运行函数Print(p,daodatime,fuwutime,kaishitime,wanchengtime,zhouztime,daiquantime,N);//声明输出函数}/***********************这是算法时间片轮转法的代码*****************************************/14structshijian{//定义时间片的结构体charname;//定义进程名intdaodatime;//到达时间intfuwutime;//服务时间intshengyutime;//剩余时间char*state;//所处状态structshijian*next;};structshijian*time(){inta,i;structshijian*head,*rear,*p,*q,*t;//定义队首、队尾、P是队尾指针、Q是队首指针和执行时间head=rear=NULL;//初始化队首和队尾为空printf(请输入进程数目：);scanf(%d,&a);for(i=0;ia;i++){p=(structshijian*)malloc(sizeof(structshijian));//初始化一个空间给进程进入printf(输入第%d个进程的名字、到达时间、服务时间:\n,i+1);scanf(%s%d%d,&p-name,&p-daodatime,&p-fuwutime);p-shengyutime=p-fuwutime;p-state=就绪;if(rear==NULL)//当输入结束时，把P的数据放到队首，以便执行下一步{head=p;p-next=NULL;rear=p;}else//否则执行时间就为空，队首变成Q{t=NULL;q=head;while(q&&q-daodatimep-daodatime)//当Q和Q的到达时间小于P的到达时间时，把执行时间给Q{t=q;15q=q-next;}if(q==head)//而当Q是队首时，则下一个队首变成P，以便每个进程都能够得到时间片{p-next=head;head=p;}elseif(t==rear)//当执行时间片到达队尾时（执行完时），返回给队首P{rear-next=p;p-next=NULL;rear=p;}else//否则给队首P占用执行时间，P执行完后到Q{t-next=p;p-next=q;}}}returnhead;//返回队首}voidoutput(structshijian*head)//定义输出函数{structshijian*p,*t,*r;intnum;printf(请输入时间片:);scanf(%d,&num);while(head!=NULL)//当队首不为空时，把P给队首{r=p=head;while(p!=NULL)//把执行时间给队首{t=head;p-shengyutime=p-shengyutime-num;//P的剩余时间=剩余时间-时间片p-state=运行;//状态变成运行态16if(p-shengyutime0)//当P运行完，即剩余时间小于0时，仍然把它当做0处理p-shengyutime=0;printf(\n************程序开始运行*****************\n);printf(进程到达时间服务时间剩余时间当前状态\n);while(t!=NULL)//时间不为空时，输出当前进程的信息，并把时间片交给下一个进程{printf(%2c%8d%8d%14d%10s\n,t-name,t-daodatime,t-fuwutime,t-shengyutime,t-state);t=t-next;}getchar();//按住回车键观看if(p-shengyutime==0)//当队首的剩余时间为0时，先把队首改成P的下一个，然后释放内存，删除队首节点{if(p==head){head=p-next;free(p);p=head;}else//否则返回执行，把队尾的下一个指针变成P的下一个指针，队尾的位置移动到队首{r-next=p-next;p=r-next;r=p;}}else//否则把队首的位置给队尾，把队首的状态显示为“就绪