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

1、题目：处理机调度算法的模拟专业：网络项目班级：学号：姓名：指导教师：完成日期：一、课程设计目的1、掌握C语言数组、函数、指针、结构体的综合应用。2、掌握使用C语言，进行应用性的开发。3、掌握系统数据结构与算法的设计。二、课程设计内容课程设计题目：处理机低级调度模拟系统课程设计内容：根据操作系统处理机不同的调度算法，使用C语言模拟实现处理机调度过程。1、系统数据结构<1）进程控制块vpcb）:进程名称、至U达时间、进程要求运行时间、进程已运行时间、指针、进程状态等等 <要根据不同算法的需要 定义全面的数据结构）<2）进程队列vPQueue :链表2、调度算法<1）先来先服

2、务调度vFCFS）:按照进程提交给系统的先后顺序 来挑选进程， 先提交的先被挑选。<2）短进程优先调度 <SJF）： 是以进入系统的进程所提出的 “执 行时间 ”为标准，总是优先选取执行时间最短的进程。<3）高响应比优先调度 <HRN ）：是在每次调度前都要计算所有 被选进程 <在后备队列中）的响应比，然后选择响应比最高的进程执 行。<4）多级反馈队列调度（FB，第i级队列的时间片=2i-1>: <a）应 设置多个就绪队列，并为各个队列赋予不同的优先级。<b）当一个新进程进入内存后，首先将它放入第一队列的末尾，按 FCFS 的原 则排队等待

3、调度。当轮到该进程执行时，如他能在该时间片内完 成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调 度程序便将该进程转入第二队列的末尾，再同样地按 FCFS 原则等 待调度执行；如果它在第二队列中运行一个时间片后仍未完成，再 依次将它放入第三队列 ，如此下去，当一个长作业进程从第一 队列依次降到第 N 队列后，在第 N 队列中便采取时间片轮转的方式 运行。VC ）仅当第一队列空闲时，调度程序才调度第二队列中的进 程运行。三、课程设计的要求1、按照给出的题目内容 <1）完成系统数据结构设计与实现、系统算法设计与实现、系统模 块设计与实现、系统总体的设计与实现。<2）系统需要一

4、个简单操作界面，例如:1. 先来先服务调度2. 短进程优先调度3. 高响应比优先调度4. 多级反馈队列调度5. 退出<按数字 1、2、 3、 4、5，选择操作） <3）对每种调度算法都要求输出每个进程 <进程数不少于 5）开始运 行时刻、完成时刻、周转时间，以及这组进程的平均周转时间。 <4）画出每种调度算法流程图。2、写出课程设计报告，设计报告提交形式：电子文档提交3、个人独立完成。4、完成时间 <1 周）四、课程设计过程1、系统中所使用的数据结构及说明/ 数据结构的定义 /定义进程控制块 PCBtypedef struct PCBchar PID5。/进程标示

5、符int PRI/进程的优先级 （越小越高 >float NeedTime。float StartTime。间float RunBeginTime。float UpTime。float OverTime 。float TurnaroundTime。 float RightTTime 。 struct PCB *next。 PCB,*QueuePtr。 /定义进程队列 typedef struct QueuePtr front,rear。PQueue。2、系统功能结构/ 进程要求运行时间 （服务时间 > /进程进入就绪队列的时间 （ 到达时/ 开始运行时间/ 进程已运行时间/ 进程运

6、行完成的时间/周转时间/ 带权周转时间/队头、队尾指针本系统是处理机低级调度模拟系统，主要通过模拟来实现处理机调度，调度方式有先来先服务调度VFCFS）、短进程优先调度<SJF）、高响应比优先调度<HRN）、多级反馈队列调度 （FB>四种 调度方式。系统运行过程如下：输入进程个数，输入进程详细信息，通过简单操作界面来选择调度方式，调度的过程和结果，重新选择调度方式或者选择结束开始3、调度算法流程图 如下图所示）开始输入进程个 数和进程详 细信息找到第一个到达的进程并排在队首以后到达的进程按到达时间和服务时间进行综合排序令p为队首的进程计算p的开始运行时间，结束运行时间，周转时

7、间和带权周转时间p=p_>next输出进程 相关信息NOYES p!=NULL?>输出平均周转 时间和平均带 权周转时间计算平均周转时间和平均带权周转时间结束输入进程个数和进程详细信息找到第一个到达的进程并排在队首以后到达的进程按响应比大小进行排序令P为队首的进程计算P的开始运行时间，结束运行时间，周转时间和带权周转时间输出进程 相关信息p=p_>nextYESp!=NULL? ii计算平均周转 时间和平均带权周转时间输出平均周转 时间和平均带 权周转时间结束开始输入进程个 数和进程详细信息对进程按FCFS序 并保存在队列Q中设置第一队列Q、第二队列M、第三队列N的时间片T1

8、、T2、T3的大小（2i-1）NOYES第一队列Q为空？ 令p为队列Q的头结点YES一 第二队列M为空？、二;NOYES叩->n ext这个进程的<=T1？服务时间*计算p->next的已运 行时间，结束运行 时间，周转时间和 带权周转时间输出进程详 细运行信息NO令P-> next的已运行时间为T1输出进程详 细运行信息将进程插入队列M中> p=p->next "<YE乞：p->next!=NULL? 一：；-结束令p为队列 M的头结点YESNO_.”P>next这个进程的""耳 服务时间<=T2?&g

9、t;计算p-> next的已运行时间，结束运行 时间，周转时间和带权周转时间YES "、*-第三队列N为空?令P-> next的已运行时间为T1+T2输出进程详 细运行信息输出进程详 细运行信息将进程插入队列N中Hp=p->nextp->next!=NULL?NO令p为队列N的头结点计算p-> next的已运行时间，结束运行时间，周转时间和带权周转时间输出进程详 细运行信息YESp=p->nextNOYES,p-> next!=NULL?4、程序清单及其描述#include<stdio.h>#include<stdlib.h

10、>#include<math.h>#include<malloc.h>#include<process.h>#include<stdlib.h>#define NULL 0int ProcessNum。/进程个数float AverageTurnoverTime。 /平均周转时间float AverageRightTTime。 /平均带权周转时间/ 函数结果状态代码 #define TRUE 1#define FALSE 0#define OK 1#define ERROR 0/ 数据结构的定义 /定义进程控制块 PCBtypedef st

11、ruct PCBchar PID5。/进程标示符char Name10。/进程名称int PRI/进程的优先级 （越小越高 >/进程要求运行时间 （服务时间 > /进程进入就绪队列的时间 （到达时间 >/开始运行时间/进程已运行时间/进程运行完成的时间/周转时间/带权周转时间/队头、队尾指针float NeedTime。 float StartTime。float RunBeginTime。float UpTime。 float OverTime 。float TurnaroundTime。 float RightTTime 。 struct PCB *next。PCB,*Q

12、ueuePtr。 /定义进程队列 typedef structQueuePtr front,rear。PQueue。/ 函数的申明int InitQueue(PQueue &Q。 int EnQueue(PQueue &Q。int QueueEmpty(PQueue Q。 回 1,否则返回 0 void PoolQueue(PQueue *Q。 int print(PQueue Q。/构造一个空队列/插入一个新的进程到队尾队列判空，若Q为空队列，则返/建立后备队列/进程队列输出void FCFSsort(PQueue &Q>。 进行排序void SPFsort(P

13、Queue &Q>。进行排序void HRNsort(PQueue &Q>。 间进行排序void Dispatcher(PQueue &Q>。void FB(PQueue &Q>。/先来先服务调度的对到达时间/短进程优先调度的对服务时间/高响应比优先调度的对服务时/先来先服务调度/多级反馈队列调度void ManagesChooses(PQueue &Q。 / 调度方式选择/ 函数的定义 / 构造一个空队列 int InitQueue(PQueue &Q>Q.front=Q.rear=(QueuePtr>mal

14、loc(sizeof(PCB>>。 if(!Q.front>exit(0> 。Q.front->next=NULL 。return 1。/ 插入一个新的进程到队尾 int EnQueue(PQueue &Q>QueuePtr p。if(!(p=(QueuePtr>malloc(sizeof(PCB>>>>/存储分配失败exit(0> 。 scanf("%s",p->PID>。/输入进程标示符 scanf("%s",p->Name>。/输入进程名scan

15、f("%d %f %f",&p->PRI,&p->NeedTime,&p->StartTime>。 /输入进程优先级、要求运行时间、到达时间 p->next=NULL 。Q.rear->next=p。Q.rear=p。return 1。/ 队列判空， 若 Q 为空队列 ,则返回 1,否则返回 0int QueueEmpty(PQueue Q>/若Q为空队列，则返回1,否则返回0if(Q.front=Q.rear>return 1。elsereturn 0。/ 建立后备队列 void PoolQueue(

16、PQueue *Qint i 。printf(" 请输入进程的个数： "。 scanf("%d",&ProcessNum。printf("请输入d个进程的信息T代表时间)n标示符 程名 优先级 服务 T 到达 Tn",ProcessNum。for(i=1。i二ProcessNum。i+ EnQueue(*Q。/ 进程队列输出 int print(PQueue QQueuePtr p。if(Q.front=Q.rearreturn 0。p=Q.front-next。printf("<T 代表时间) n 标示符 进

17、程名 优先级 服 务 T 到达 Tn"> 。while (p!=NULL>/当队列不空printf("%st%st%dt%4.3ft%4.3fn",p->PID,p->Name,p- >PRI,p->NeedTime,p->StartTime>。p=p->next。/ 先来先服务调度的对到达时间进行排序 void FCFSsort(PQueue &Q>QueuePtr tail,p=Q.front。QueuePtr q=p->next。tail=NULL 。for(。p->next-&

18、gt;next!二tail。p=Q.front,q=p->next>/选择排序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 。/ 短进程优先调度的对服务时间进行排序 void SPFsort(PQueue &Q>/deltaT 是时间float deltaT,Time=0。差Qu

19、euePtr temp1,temp2,tail,p=Q.fro n。QueuePtr q=p->next。tail=NULL 。一个到达而且服务时间最少的进程if(p->next->StartTime > q->next->StartTime>temp1=p->next。temp2=q->next。p->next=temp2。q->next=temp2->next。p->next->next=temp1。elseq=q->next。if(p->next->StartTime > Time

20、>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>>if(q->next->StartTime <= Time>&am

21、p;&(p->next- >NeedTime > q->next->NeedTime>>temp1=p->next。temp2=q->next。p->next=temp2。q->next=temp2->next。p->next->next=temp1。elseq=q->next。else if(p->next->StartTime > Time>&&(q->next- >StartTime <= Time>>temp2=q-&g

22、t;next。p->next=temp2。q->next=temp2->next。p->next->next=temp1。elseq=q->next。if(p->next->StartTime > Time>deltaT=p->StartTime-Time。Time=Time+deltaT。Time=Time+p->next->NeedTime。/ 高响应比优先调度的对服务时间进行排序 - void HRNsort(PQueue &Q>float deltaT,PResp on seRatio,QRes

23、p on seRatio,Time=0/deltaT是时间差,PResponseRatio QResponseRatic是响应比QueuePtr temp1,temp2,tail,p=Q.fro n。QueuePtr q=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->n

24、ext=temp2->next。p->next->next=temp1。elseq=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>

25、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-&g

26、t;NeedTime>>。 if(PResponseRatio<QResponseRatio> temp1=p->next。temp2=q->next。p->next=temp2。 q->next=temp2->next。 p->next->next=temp1。elseq=q->next。else if(p->next->StartTime > Time>&&(q->next- >StartTime <= Time>>temp1=p->next。

27、temp2=q->next。p->next=temp2。q->next=temp2->next。 p->next->next=temp1。elseq=q->next。if(p->next->StartTime > Time>Time=Time+deltaT。Time=Time+p->next->NeedTime。/ 调度 void Dispatcher（PQueue &Q>float SumTurnaroundTime=0。 /定义周转时间总和并赋值 0float SumRightTTime=0。/定义

28、带权周转时间总和并赋值 0float deltaT,Time=0。/deltaT 是时间差QueuePtr p=Q.front->next。printf（"<T 代表时间） n 标示符进程名 到达 T务 T 开始 T 完成 T 周转 T 带权周转 Tn"> 。for（。p!二NULL。p=p->next>if（p->StartTime>Time>Time=deltaT。p->RunBeginTime=Time。p->OverTime=Time+p->NeedTime。p->TurnaroundTime=

29、p->OverTime-p->StartTime。 p->RightTTime=p->TurnaroundTime/p->NeedTime。printf("%st%st%4.3ft%4.3ft%4.3ft%4.3ft%4.3ft%4.3fn",p->PID,p->Name,p->StartTime,p->NeedTime,p->RunBeginTime,p->OverTime,p->TurnaroundTime,p->RightTTime>。Time=p->OverTime。for(p

30、二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.

31、3fn",AverageTurnoverTime,AverageRightTTime。/多级反馈队列调度 void FB(PQueue &QPQueue M,N。InitQueue(M。/初始化第二队列InitQueue(N。/初始化第三队列FCFSsort(Q。printf(" 调度前进程排列如下 :n"。print(Q。QueuePtr p,q,r。q=M.front。r=N.front。float i,deltaT,Time=0。/deltaT是时间差float T1,T2,T3。T1=2*1-1 。第一队列Q的时间片T2=2*2-1 。/第二队列

32、M 的时间片T3=2*3-1 。/第三队列 M 的时间片 printf("n 调度过程如下 :n"> 。for(p二Q.front。p->next!二NULL。p=p->next>/第一队列的调度if(p->next->StartTime>Time>for(i=Time+1 。 i<=p->next->StartTime。 i+> printf("第4.3f时刻，等待队列到来！ n",i>。deltaT=p->next->StartTime-Time。Time=Ti

33、me+deltaT。p->next->RunBeginTime=Time。 if(p->next->NeedTime<=T1>p->next->OverTime=Time+p->next->NeedTime。 p->next->UpTime=p->next->NeedTime。>next->StartTime。p->next->RightTTime=p->next->TurnaroundTime/p->next->NeedTime。for(i二Time+1。i&l

34、t;p->next->OverTime。i+>printf("第4.3f时刻，进程标示符 st进程 名 %s 运行中,已运行了 %4.3f 时刻！ n",i,p->next->PID,p->next- >Name,i-Time>。printf("第%4.3f时刻，进程标示符 %st进程名%s 运行完成！ n",i,p->next->PID,p->next->Name>。Time=p->next->OverTime。elsep->next->UpTime=

35、T1 。for(i=1 。 i<=T1 。 i+>printf("第%4.3f时刻，进程标示符 %st进程 名 %s 运行中，已运行了 %4.3f 时刻！ 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.front。p->next!二NULL。p=p->next>/第二队列的调度if(p-&

36、gt;next->NeedTime-p->next->UpTime><=T2>p->next->OverTime=Time+p->next->NeedTime-p- >next->UpTime。p->next->TurnaroundTime=p->next->OverTime-p- >next->StartTime。p->next->RightTTime=p->next->TurnaroundTime/p- >next->NeedTime。for(i=

37、Time+1 。 i<p->next->OverTime。 i+>printf("第4.3f时刻，进程标示符 st进程 名 %s 运行中,已运行了 %4.3f 时刻！ n",i,p->next->PID,p->next- >Name,p->next->UpTime+i-Time> 。printf("第%4.3f时刻，进程标示符 %st进程名%s 运行完成！ n",i,p->next->PID,p->next->Name>。p->next->UpTi

38、me=p->next->NeedTime。elsefor(i=1。i<=T2。i+>printf("第4.3f时刻，进程标示符 st进程 名 %s 运行中,已运行了 %4.3f 时刻！ n",Time+i,p->next->PID,p- >next->Name,i+p->next->UpTime>。r->next=p->next。r=r->next。 p->next->UpTime=p->next->UpTime+T2 。 Time=Time+T2。r->nex

39、t=NULL 。for(p=N.front。 p->next!=NULL 。 p=p->next>/第三队列的调度 p->next->OverTime=Time+p->next->NeedTime-p->next- >UpTime。p->next->TurnaroundTime=p->next->OverTime-p->next- >StartTime。>NeedTime。for(i二Time+1。i<p->next->OverTime。i+>printf("第4.

40、3f时刻，进程标示符 st进程名%s 运行中，已运行了 %4.3f 时刻！ n",i,p->next->PID,p->next->Name,p- >next->UpTime+i-Time> 。printf("第%4.3f时刻，进程标示符%st进程名%s运行完 成！ n",i,p->next->PID,p->next->Name> 。p->next->UpTime=p->next->NeedTime。 Time=p->next->OverTime。/ 调度方式

41、选择 void ManagesChooses(PQueue &Q>int i 。printf("nnnt 请选择调度方式： n">。 printf("=n"> 。printf("1.先来先服务调度 n">。printf("2.短进程优先调度 n">。printf("3.高响应比优先调度 n">。printf("4.多级反馈队列调度 n">。prin tf(" 5.退出 n">。printf("

42、;< 按数字 1、2、3、4、5,选择操作)n">。n">printf(" scanf("%d",&i 。switch(icase 1:FCFSsort(Q。printf(" 先来先服务调度的对到达时间进行排序的排序 结果如下 :n" 。print(Q 。printf("n 调度后的结果如下 :n" 。Dispatcher(Q。Man agesChooses(Qbreak。case 2:SPFsort(Q。printf(" 短进程优先调度的对服务时间进行排序的排序 结果

43、如下 :n"。print(Q。printf("n 调度后的结果如下 :n" 。Dispatcher(Q。ManagesChooses(Q 。break。case 3:HRNsort(Q。printf(" 高响应比优先调度的对服务时间进行排序的排序结果如下 :n">print(Q 。printf("n 调度后的结果如下 :n" 。 Dispatcher(Q。Man agesChooses(Qbreak。case 4:FB(Q。ManagesChooses(Q 。break。case 5:break。/ 主函数 void

44、main(int n。PQueue Q。InitQueue(Q。/初始化后备队列PoolQueue(&Q。/ 进程插入后备队列中并返回进程个数printf("n 输入的进程情况如下 :n"。print(Q。Man agesChooses(Q>3、系统运行结果"E:M SDev98MyProjectsll 冃 2 了曰 iDe bugl 1月对曰己.exe"g无口王 哥一 5 方入符 圍幕1;4 5呈名E标示符123标手符123A间T夷服4代优魏1234请选择调度方式:度度、卫 度度调调亦 调调先列 桑优队4馈冬 先程应反 、 盍高多退12

45、3 4服务T4. HUB3.0005 B0Q2.BB04.000到达T0.0001.3002*0004*盹0优救12服务T4- dt)03-AO05- 0002.00040附到达T0.0001-Q902.B&&3.0004,000训痘后的结果如下:撕軀名1Ab B司）到达T0.000l.oee2.see3.000 4.000服务T4.0003.0005.0002.004.B00开始T0.0004.0007,000 12.000 丄4B00完成T4.00012.00014.B0018.000周转T4.QQQJ 00010.00011 14,000带权周转T1.0002.&

46、Q&2.8005.5003.590此调度方式的平均周转时间为以込平均带权周转时间为“翻先程应反 盡响番 奩高多退4度度 度度调调 调调先列 务先优队度的对展务时间迸行排序的排序结果如下)呈名优先级服务T到达T14.0000.00042.0003 00023.0001 00054.0004.00035.0002 000到达T0 000服务T4 000开始T0 000完成T4 000周转T4.000带权周转T1.0004D3.0002.0004.0006.0003.00012B1.0003.0006.0009.0008.00025E4.0004.0009.00013.0009.00023C2.0005.0001