参考程序：处理机低调度模拟系统

题目：处理机调度算法的模拟专业：网络项目班级：学号：姓名：指导教师：完成日期：一、课程设计目的1、掌握C语言数组、函数、指针、结构体的综合应用。2、掌握使用C语言，进行应用性的开发。3、掌握系统数据结构与算法的设计。二、课程设计内容课程设计题目：处理机低级调度模拟系统课程设计内容：根据操作系统处理机不同的调度算法，使用C语言模拟实现处理机调度过程。1、系统数据结构＜1）进程控制块＜pcb）：进程名称、到达时间、进程要求运行时间、进程已运行时间、指针、进程状态等等＜要根据不同算法的需要定义全面的数据结构）＜2）进程队列＜PQueue）:链表……2、调度算法＜1）先来先服务调度＜FCFS）：按照进程提交给系统的先后顺序来挑选进程，先提交的先被挑选。<2）短进程优先调度<SJF）：是以进入系统的进程所提出的“执行时间”为标准，总是优先选取执行时间最短的进程。<3）高响应比优先调度<HRN）：是在每次调度前都要计算所有被选进程<在后备队列中）的响应比，然后选择响应比最高的进程执行。<4）多级反馈队列调度（FB，第i级队列的时间片=2-1>：<a）应设置多个就绪队列，并为各个队列赋予不同的优先级。<b）当一个新进程进入内存后，首先将它放入第一队列的末尾，按FCFS的原则排队等待调度。当轮到该进程执行时，如他能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，再同样地按FCFS原则等待调度执行；如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列……，如此下去，当一个长作业进程从第一队列依次降到第N队列后，在第N队列中便采取时间片轮转的方式运行。<c）仅当第一队列空闲时，调度程序才调度第二队列中的进程运行。三、课程设计的要求1、按照给出的题目内容<1）完成系统数据结构设计与实现、系统算法设计与实现、系统模块设计与实现、系统总体的设计与实现。<2）系统需要一个简单操作界面，例如：charName[10]charName[10]。 //进程名称.先来先服务调度.短进程优先调度.高响应比优先调度.多级反馈队列调度.退出＜按数字1、2、3、4、5,选择操作）＜3）对每种调度算法都要求输出每个进程进程数不少于）开始运行时刻、完成时刻、周转时间，以及这组进程的平均周转时间。）画出每种调度算法流程图。2、写出课程设计报告，设计报告提交形式：电子文档提交3、个人独立完成。4、完成时间＜1周）四、课程设计过程1、系统中所使用的数据结构及说明// 数据结构的定义 〃定义进程控制块PCBtypedefstructPCB（charPID[5]。 〃进程标示符intPRIintPRI。 //进程的优先级（越小越高＞floatNeedTime。 //进程要求运行时间（服务时间＞floatStartTime。 //进程进入就绪队列的时间（到达时间＞floatRunBeginTime。//开始运行时间floatUpTime。//进程已运行时间floatOverTime。//进程运行完成的时间floatTurnaroundTime。//周转时间floatRightTTime。//带权周转时间structPCB*next。}PCB,*QueuePtr。//定义进程队列typedefstruct{QueuePtrfront,rear。 //队头、队尾指针}PQueue。2、系统功能结构本系统是处理机低级调度模拟系统，主要通过模拟来实现处理机调度，调度方式有先来先服务调度＜FCFS）、短进程优先调度＜SJF）、高响应比优先调度＜HRN）、多级反馈队列调度（FB＞四种调度方式。系统运行过程如下：输入进程个数，输入进程详细信息，通过简单操作界面来选择调度方式，调度的过程和结果，重新选择调度方式或者选择结束。3、调度算法流程图＜如下图所示）开始输入进程个数和进程详细信息开始进程按到达时

间进行排序令p为队

首的进程输入进程个

数和进程详

细信息找到第一个到达的

进程并排在队首以后到达的进程按到达时间和服

务时间进行综合排序令p为队

首的进程找到第一个到达的进程并排在队首以后到达的进程按响

应比大小进行排序令p为队

首的进程计算p的开始运行

时间，结束运行时

间，周转时间和带

权周转时间计算p的开始运行

时间，结束运行时

间，周转时间和带

权周转时间计算p的开始运行

时间，结束运行时

间，周转时间和带

权周转时间输出进程相关信息/输出进程相关信息/输出进程相关信息输出进程

相关信息p=p>nextp=p>nextp=p>nextYESp!=NULL?xYES p!=NULL?二NO输出平均周转时间和平均带权周转时间计算平均周转时间和平均带权周转时间结束j输出平均周转时间和平均带权周转时间NO计算平均周转时间和平均带权周转时间结束■__■YES p!=NULL?kNO计算平均周转

时间和平均带

权周转时间结束输出平均周转时间和平均带权周转时间先来先服务调度短进程优先调度高响应比优先调度开始

输入进程个

数和进程详

细信息

对进程按FCFS排序

并保存在队列Q中设置第一队列Q、第二队列M、第三队

列N的时间片T1、T2、T3的大小（2i1YESNO YES第一队列q为空？A—令p为队列Q

的头结点竺二,•二第二队列M为空?I；〉NONOp>ne这个进程的服务时间<=11？/令p为队列

M的头结点计算p>ne的已运

行时间，结束运行

时间，周转时间和

带权周转时间令P>ne）的已运行时间为T1YESNO输出进程详细运行信息输出进程详细运行信息p>ne这个进程的"J.

服务时间<=T2？/令P>ne）的已运

行时间为T1+T2将进程插入队

列M中计算p>ne）的已运

行时间，结束运行

时间，周转时间和

带权周转时间输出进程详细运行信息p=p>nexM输出进程详细运行信息将进程插入队

列N中p=p>nextp=p>next*YES--- ,-NO■,■-p—>next!=NULL?"NO YES■---p.->next!=NULL?1,YES...-YES...-'第三队列N为空？令p为队列N

的头结点计算p>ne的已运

行时间，结束运行

时间，周转时间和

带权周转时间结束输出进程详细运行信息结束p=p>nex:NO YES■---p->next!=NULL?,,多级反馈队列调度charName[10]charName[10]。 //进程名称4、程序清单及其描述#include<stdio.h>#include<stdlib.h>#include<math.h>#include<malloc.h>#include<process.h>#include<stdlib.h>#defineNULL0intProcessNum。 //进程个数floatAverageTurnoverTime。 //平均周转时间floatAverageRightTTime。 //平均带权周转时间// 函数结果状态代码 #defineTRUE1#defineFALSE0#defineOK1#defineERROR0// 数据结构的定义 〃定义进程控制块PCBtypedefstructPCB{charPID[5]。 //进程标示符intPRIintPRI。 //进程的优先级（越小越高＞//进程要求运行时间//进程要求运行时间（服务时间＞//进程进入就绪队列的时间（到达时间＞//开始运行时间//进程已运行时间//进程运行完成的时间//周转时间//带权周转时间//队头、队尾指针floatNeedTime。floatStartTime。floatRunBeginTime。floatUpTime。floatOverTime。floatTurnaroundTime。floatRightTTime。structPCB*next。}PCB,*QueuePtr。//定义进程队列typedefstruct{QueuePtrfront,rear。}PQueue。// 函数的申明intInitQueue(PQueue&Q＞。intEnQueue(PQueue&Q＞。intQueueEmpty(PQueueQ＞。回1,否则返回0voidPoolQueue(PQueue*Q＞。intprint(PQueueQ＞。//构造一个空队列//插入一个新的进程到队尾〃队列判空，若Q为空队列，则返//建立后备队列//进程队列输出voidFCFSsort(PQueue&Q＞。进行排序//先来先服务调度的对到达时间voidSPFsort(PQueue&Q＞。进行排序voidHRNsort(PQueue&Q＞。间进行排序voidDispatcher(PQueue&Q＞。voidFB(PQueue&Q＞。//短进程优先调度的对服务时间//高响应比优先调度的对服务时//先来先服务调度//多级反馈队列调度voidManagesChooses(PQueue&Q＞。//调度方式选择// 函数的定义 // 构造一个空队列 intInitQueue(PQueue&Q＞{Q.front=Q.rear=(QueuePtr＞malloc(sizeof(PCB＞＞。if(!Q.front＞exit(0＞。Q.front-＞next=NULL。return1。}// 插入一个新的进程到队尾 intEnQueue(PQueue&Q＞QueuePtrp。if(!(p=(QueuePtr>malloc(sizeof(PCB>>>>//存储分配失败exit(0>。scanf("%s",p->PID>。//输入进程标示符scanf("%s",p->Name>。//输入进程名scanf("%d%f%f",&p->PRI,&p->NeedTime,&p->StartTime>。 //输入进程优先级、要求运行时间、到达时间p->next=NULL。Q.rear->next=p。Q.rear=p。return1。}// 队列判空，若Q为空队列,则返回1,否则返回0 intQueueEmpty(PQueueQ>{//若Q为空队列,则返回1,否则返回0if(Q.front==Q.rear>return1。elsereturn0。}// 建立后备队列 voidPoolQueue(PQueue*Q>{inti。printf("请输入进程的个数：">。scanf("%d",&ProcessNum>。printf("请输入％4个进程的信息<T代表时间)\n标示符程名优先级服务T 到达T\n",ProcessNum>。for(i=1。i<=ProcessNum。i++>EnQueue(*Q>。}// 进程队列输出 intprint(PQueueQ>{QueuePtrp。if(Q.front==Q.rear>return0。p=Q.front->next。printf（"<T代表时间）\n标示符进程名优先级服务T到达T\n">。while(p!=NULL>//当队列不空{printf("%s\t%s\t%d\t%4.3f\t%4.3f\n",p->PID,p->Name,p->PRI,p->NeedTime,p->StartTime>。p=p->next。}}// 先来先服务调度的对到达时间进行排序 voidFCFSsort(PQueue&Q>{QueuePtrtail,p=Q.front。QueuePtrq=p->next。tail=NULL。for(。p->next->next!=tail。p=Q.front,q=p->next>//选择排序{while(q->next!=tail>{if(p->next->StartTime>q->next->StartTime>{p->next=q->next。q->next=q->next->next。p->next->next=q。}p=p->next。q=p->next。}tail=q。}}// 短进程优先调度的对服务时间进行排序 voidSPFsort(PQueue&Q>{floatdeltaT,Time=0。 〃deltaT是时间差QueuePtrtemp1,temp2,tail,p=Q.front。QueuePtrq=p->next。tail=NULL。//找出第for(。q->next!=tail。//找出第一个到达而且服务时间最少的进程(if(p->next->StartTime>q->next->StartTime>(temp1=p->nextotemp2=q->nextop->next=temp2oq->next=temp2->next。p->next->next=temp1。)else(q=q->nexto))if(p->next->StartTime>Time>Time=p->StartTime。Time=Time+p->next->NeedTime。for(p=p->next,q=p->next。p->next->next!=tail。p=p->next,q=p->next> 〃对队列按到达时间与服务时间长短进行选择排序〈从第二个元素开始)(temp1=p->nexttemp1=p->nextowhile(q->next!=tail>(if((p->next->StartTime<=Time>>(if((q->next->StartTime<=Time>&&(p->next->NeedTime>q->next->NeedTime>>(temp1=p->nextotemp2=q->next。p->next=temp2。q->next=temp2->next。p->next->next=temp1。}else(q=q->nexto}}elseif((p->next->StartTime>Time>&&(q->next->StartTime<=Time>>temp2=q->next。p->next=temp2。q->next=temp2->next。p->next->next=temp1。}else{q=q->next。}}if(p->next->StartTime>Time>{deltaT=p->StartTime-Time。Time=Time+deltaT。}Time=Time+p->next->NeedTime。}}// 高响应比优先调度的对服务时间进行排序-voidHRNsort(PQueue&Q>{floatdeltaT,PResponseRatio,QResponseRatio,Time=0。//deltaT是时间差,PResponseRatio、QResponseRatio是响应比QueuePtrtemp1,temp2,tail,p=Q.front。QueuePtrq=p->next。tail=NULL。for(。q->next!=tail。>//找出第一个到达而且服务时间最少的进程{if(p->next->StartTime>q->next->StartTime>{temp1=p->next。temp2=q->next。p->next=temp2。q->next=temp2->next。p->next->next=temp1。}else{q=q->next。}}if(p->next->StartTime>Time>Time=p->StartTime。Time=Time+p->next->NeedTime。for(p=p->next,q=p->next。p->next->next!=tail。p=p->next,q=p->next> 〃对队列按响应比大小排序〈从第二个元素开始)(while(q->next!=tail>(if((p->next->StartTime<=Time>&&(q->next->StartTime<=Time>>(PResponseRatio=(((Time-p->next->StartTime>+p->next->NeedTime>/(p->next->NeedTime>>。QResponseRatio=(((Time-q->next->StartTime>+q->next->NeedTime>/(q->next->NeedTime>>。if(PResponseRatio<QResponseRatio>(temp1=p->nextotemp2=q->next。p->next=temp2。q->next=temp2->next。p->next->next=temp1。}deltaT=p->StartTime-TimedeltaT=p->StartTime-Time。else(q=q->nexto))Time>&&(q->next-elseif((p->next->StartTime>Time>&&(q->next->StartTime<=Time>>(temp1=p->nextotemp2=q->nextop->next=temp2oq->next=temp2->next。p->next->next=temp1。)else(q=q->nexto))if(p->next->StartTime>Time>Time=Time+deltaT。Time=Time+p->next->NeedTime。}}// 调度 voidDispatcher（PQueue&Q>{floatSumTurnaroundTime=0。//定义周转时间总和并赋值0floatSumRightTTime=0。//定义带权周转时间总和并赋值0floatdeltaT,Time=0。//deltaT是时间差QueuePtrp=Q.front->next。printf（"<T代表时间）\n标示符进程名到达T服务T开始T完成T周转T 带权周转T\n">。for（。p!=NULL。p=p->next>{if（p->StartTime>Time>Time=deltaT。}p->RunBeginTime=Time。p->OverTime=Time+p->NeedTime。p->TurnaroundTime=p->OverTime-p->StartTime。p->RightTTime=p->TurnaroundTime/p->NeedTime。printf("%s\t%s\t%4.3f\t%4.3f\t%4.3f\t%4.3f\t%4.3f\t%4.3f\n",p->PID,p->Name,p->StartTime,p->NeedTime,p->RunBeginTime,p->OverTime,p->TurnaroundTime,p->RightTTime>。Time=p->OverTime。}for(p=Q.front->next。p!=NULL。p=p->next>//计算平均周转时间和平均带权周转时间{SumTurnaroundTime=SumTurnaroundTime+p->TurnaroundTime。SumRightTTime=SumRightTTime+p->RightTTime。}AverageTurnoverTime=SumTurnaroundTime/ProcessNum。AverageRightTTime=SumRightTTime/ProcessNum。printf("此调度方式的平均周转时间为％4.3f,平均带权周转时间^%4.3f\n",AverageTurnoverTime,AverageRightTTime>o}// 多级反馈队列调度 -voidFB(PQueue&Q>{PQueueM,NoInitQueue(M>o//初始化第二队列InitQueue(N>o //初始化第三队列FCFSsort(Q>oprintf("调度前进程排列如下:\n”>。print(Q>oQueuePtrp,q,roq=M.frontor=N.frontofloati,deltaT,Time=0o//deltaT是时间差floatT1,T2,T3oT1=2*1-1o〃第一队列Q的时间片T2=2*2-1。〃第二队列M的时间片T3=2*3-1。〃第三队列M的时间片printf("\n调度过程如下:\n">。for(p=Q.frontop->next!=NULL。p=p->next> //第一队列的调度{if(p->next->StartTime>Time>{for(i=Time+1oi<=p->next->StartTime。i++>printf("第%4.3f时刻，等待队列到来！\n",i>。deltaT=p->next->StartTime-Time。Time=Time+deltaT。}p->next->RunBeginTime=Time。if(p->next->NeedTime<=T1>{p->next->OverTime=Time+p->next->NeedTime。p->next->UpTime=p->next->NeedTime。p->next->TurnaroundTime=p->next->OverTime-p->next->StartTime。p->next->RightTTime=p->next->TurnaroundTime/p->next->NeedTime。for(i=Time+1。i<p->next->OverTime。i++>printf("第％4.3f时刻，进程标示符％s\t进程名％s运行中，已运行了％4.3f时刻！\n",i,p->next->PID,p->next->Name,i-Time>。printf("第％4.3f时刻，进程标示符％s\t进程名％s运行完成！\n”,i,p->next->PID,p->next->Name>。Time=p->next->OverTime。}else{p->next->UpTime=T1。for(i=1。i<=T1。i++>printf("第%4.3f时刻，进程标示符％s\t进程名％$运行中，已运行了％4.3f时亥lj!\n",p->next->RunBeginTime+i,p->next->PID,p->next->Name,i>。q->next=p->next。q=q->next。Time=Time+T1。)q->next=NULL。for(p=M.frontop->next!=NULL。p=p->next> //第二队列的调度(if((p->next->NeedTime-p->next->UpTime><=T2>(p->next->OverTime=Time+p->next->NeedTime-p->next->UpTime。p->next->TurnaroundTime=p->next->OverTime-p->next->StartTimeop->next->RightTTime=p->next->TurnaroundTime/p->next->NeedTimeofor(i=Time+1oi<p->next->OverTime。i++>printf("第％4.3f时刻，进程标示符％s\t进程名％s运行中，已运行了％4.3f时刻！\n",i,p->next->PID,p->next->Name,p->next->UpTime+i-Time>oprintf("第％4.3f时刻，进程标示符％s\t进程名％s运行完成！\n",i,p->next->PID,p->next->Name>。p->next->UpTime=p->next->NeedTime。Time=p->next->OverTime。else(for(i=1。i<=T2。i++>printf("第%4.3f时刻，进程标示符%s\t进程名%s运行中，已运行了%4.3f时刻！\n",Time+i,p->next->PID,p->next->Name,i+p->next->UpTime>。r->next=p->next。r=r->nextop->next->UpTime=p->next->UpTime+T2oTime=Time+T2。}}r->next=NULL。for(p=N.frontop->next!=NULL。p=p->next> //第三队列的调度(p->next->OverTime=Time+p->next->NeedTime-p->next->UpTimeop->next->TurnaroundTime=p->next->OverTime-p->next->StartTime。p->next->RightTTime=p->next->TurnaroundTime/p->next->NeedTimeofor(i=Time+1。i<p->next->OverTime。i++>printf("第%4.3f时刻，进程标示符%s\t进程名%s运行中，已运行了%4.3f时亥lj!\n”,i,p->next->PID,p->next->Name,p->next->UpTime+i-Time>。printf("第％4.3f时刻，进程标示符％s\t进程名％s运行完成！\nH,i,p->next->PID,p->next->Name>op->next->UpTime=p->next->NeedTime。Time=p->next->OverTime。}}// 调度方式选择 voidManagesChooses(PQueue&Q>{intioprintf("\n\n\n\t请选择调度方式：\n">。printf("================\n”>oprintf("1.先来先服务调度\n”>。printf("2.短进程优先调度\n”>。printf("3.高响应比优先调度\n">。printf(-4.多级反馈队列调度\n”>。printf("5.退出\n">。printf("<按数字1、2、3、4、5,选择操作)\n">。printf("================\n”>。scanf("%d",&i>。switch(i>(case1:FCFSsort(Q>oprintf("先来先服务调度的对到达时间进行排序的排序结果如下:\n">。print(Q>oprintf("\n调度后的结果如下:\n">。Dispatcher(Q>oManagesChooses(Q>obreakocase2:SPFsort(Q>。printf("短进程优先调度的对服务时间进行排序的排序结果如下:\n">。print(Q>oprintf("\n调度后的结果如下:\n">。Dispatcher(Q>oManagesChooses(Q>obreakocase3:HRNsort(Q>。printf("高响应比优先调度的对服务时间进行排序的排序结果如下:\n”＞。print(Q＞。printf("\n调度后的结果如下:\n”＞。Dispatcher(Q＞。ManagesChooses(Q＞。break。case4:FB(Q＞。ManagesChooses(Q＞。break。case5:break。}}// 主函数 voidmain(＞{intn。PQueueQ。InitQueue(Q＞。 //初始化后备队列PoolQueue(&Q＞。 //进程插入后备队列中并返回进程个数printf("\n输入的进程情况如下:\n”＞。print(Q＞。

ManagesChooses(Q＞。3、系统运行结果请选择调度方式:度度调调

调调先列

务先优队

累比馈3、度度调调

调调先列

务先优队

累比馈3、4、5,选择操作）先程应反

蠢响电

甯高多退

12345^度的对到达时间进行排序的排序结果如下:名优先级服务T 到达TTOC\o"1-5"\h\z1 4.000 0.0002 3.000 1.0003 5.000 2.0004 2.000 3.0005 4.000 4.000知名K泊才进J0镶符昌示司f、示，2到达T服务T开始T完成T周转T带权周转TA0.0004.0000.0004.0004.0001.Q00B1.0003.0004.0007.0006.0002.000C2.0005.0007.00012.00010.0002.000D3.0002.00012.00014.00011.0005.500E4.0004.00014.00018.00014.0003.500匕调度方式的平±匀周转时i可为"耐心平均带权周转时间为2.8醯请选择调度方式:先程应反、

番响器2

当高多退，

字

123455度度度度调调调调先列务先优队土溃优先级14服务T4.0002.0003.0004.0005.000到达T0.0003.0001.0004.0002.000『冷.可:『口木工口（说时闾）示示符拣轴名到达T服务T开始T元成T周转T带板周转T0.0004.0000.0004.0004.0001.0003.0002.0004.0006.0003.0001.5001.0003.0006.0009.0008.0002.6674.0004.0009.00013.0009.0002.2502.0005.00013.00018.00016.0003.200.眄电平均带权周转时间为2.123请选择调度方式:调名先.1「口王ABDcE助I0-FXg---结及£4-1冼优12435口口心口水KU德媚屋小不付世柱右AB

D到达T服务T开始T元成T周转T0.0004.0000.0004.0004.0001.0003.0004.0007.0006.0003.0002.0007.0009.0006.0002.0005.0009.00014.00012.0004.0004.00014.00018.00014.000带权周转T1.0002.0003.0002.4003.500.4萌，平均带权周转时间为2.3801.请选择调度方式:4.调度（按数字八2、3、4、5,选择操作）、匆匆刻刻,契、契FT"TFT"TFT"TFT"TFT"TFT"TFT"T了了了了了了了-丁-丁-丁-丁-丁-丁-丁.1.1_1.■.1_1.■.1_1.■.1_1.■.1_1.■.1-1.■亥时0002

了

L1T

国、契、契刻□nnnnn777

狂恁仃

运运运、匆、匆匆刻刻,契、契FT"TFT"TFT"TFT"TFT"TFT"TFT"T了了了了了了了-丁-丁-丁-丁-丁-丁-丁.1.1_1.■.1_1.■.1_1.■.1_1.■.1_1.■.1-1.■亥时0002

了

L1T

国、契、契刻□nnnnn777

狂恁仃

运运运、匆了了-T-T,-11-11运运已已已已已已已！已！已已已！已已 ，成‘：成：成成口口口口口口S元史元口口口-1元-&-&{元.{元-T-T-T-T-T-T-T-T-T-T-T-T-T-T-T-T-T-T,-11-|1-|1-|1-11--11--.1-11-|1-|1-|1-|1-|1-|1-|1-|1-