进程调度算法实验报告材料

1、操作系统实验报告（二）实验题目：进程调度算法实验环境：C+实验目的：编程模拟实现几种常见的进程调度算法，通过对几组进程分别使用不 同的调度算法，计算进程的平均周转时间和平均带权周转时间，比较各种算法的性能优劣。实验内容：编程实现如下算法：1. 先来先服务算法；2. 短进程优先算法；3. 时间片轮转调度算法。设计分析：程序流程图：1. 先来先服务算法2短进程优先算法持初始化特敎組中的ia包抜到达时屈的烦序排序对获取旳 按垣作业乃所看爾 匸先邃行序得到诲程的执行序列依次执行各个iS*呈.2所有进程执行浣 威3时间片轮转调度算法实验代码：1.先来先服务算法#include <iostream.

2、h>#define n 20typedef structint id;/进程名int atime;/进程到达时间int runtime;/进程运行时间fcs;void main()int amount,i,j,diao,huan;fcs fn;cout«"请输入进程个数："endl;cin>>amount;for(i=0;i<amount;i+)cout<<"请输入进程名，进程到达时间，进程运行时间 :"<<endl;cin>>fi.id;cin>>fi.atime;cin

3、>>fi.runtime;for(i=0;i<amou nt;i+)/按进程到达时间的先后排序/如果两个进程同时到达，按在屏幕先输入的先运行for(j=0;j<amo un t-i-1;j+) if(fj.atime>fj+1.atime)diao=fj.atime;fj.atime=fj+1.atime;fj+1.atime=diao;hua n=fj.id;fj.id=fj+1.id;fj+1.id=hua n;for(i=0;i<amo un t;i+)cout<<"进程:"<<fi.id<<&q

4、uot;从"<<fi.atime<<"开始在"<<fi.atime+fi.ru ntime<<"之前结束。"<<e ndl;fi+1.atime=fi.atime+fi.ru ntime;2. 短进程优先算法#include<stdio.h>#define n 5#define num 5#define max 65535typedef struct pro int PRO_ID;int arrive_time;int sum_time;int flag;Pro;/整数排序

5、int bubble(int temp)int i,j,tem=0;for(i=1;i<num;i+) int lastX=1;for( j=0;j<num-i;j+) if(temp j>temp j+1) tem=temp j;tempj=temp j+1;tempj+1=tem;lastX=0;if(lastX=1) break;return temp0;/进程排序Pro bubble(Pro p)int i,j;Pro temp=0;Pro snum;for(i=0;i<num;i+)si=pi;for(i=1;i <nu m;i+)int lastX=1

6、;for( j=0;j<num-i;j+)if(sj.sum_time>s j+1.sum_time)temp=s j;sj=s j+1;sj+1=temp;lastX=0;if(lastX=1) break;return s0;void SPF(i nt p)if(n >0)int i,j,k,l,tc=0;Pro seq n;Pro temp_seq n;printf("短进程优先调度算法SPFn");n");printf("请依次输入5个进程的进程号、至I达时间和执行时间 printf(”成员变量用逗号隔开；进程间用回车隔开 n&

7、quot;);for(i=0;i< n;i+)sea nf("%d,%d,%d", &seqi.PRO_ID，& seqi.arrive_time，& seqi.sum_time);printf("调度顺序是：n");/初始化tcint temp nu m;for(i=0;i <nu m;i+)tempi=seqi.arrive_time;tc=bubble(temp);/tc 是断点啊/flag 表示对应i的pro的队列情况/-1表示未进入过队列，0表示在队列中，1表示被清除了for(i=0;i< n;i+)s

8、eqi.flag=-1;for(i=0;i< n;i+)for( j=0;j<n;j+)if(seq j.flag!=1 &&seq j.arrive_time<=tc)seq j.flag=0;for( j=0;j<n;j+)temp_seqj=seqj;if(seq j.flag!=0)temp_seqj.sum_time=max;l=bubble(temp_seq).PRO_ID;for( j=0;j<n;j+)if(l=seq j.PRO_ID)k=j;tc=tc+bubble(temp_seq).sum_time;seqk.flag=1;

9、prin tf("%d",l);prin tf("n");void mai n()SPF(n);3时间片轮转调度算法头文件RR.h#include<iostream>#include<stdio.h>#include<string.h>#include<stdlib.h>#include<ctype.h>#define MaxNum 100typedef struct pcb /定义进程控制块char NameMaxNum; / 进程名int arrivetime; /到达时间int runti

10、me;/运行时间int wholetime;/固定运行时间int FinishTime; /完成时间double WeightTime; / 周转时间double WeightWholeTime; / 带权周转时间char state;/运行后的状态struct pcb *next;PCB;/全局变量int N;/实际进程数double SumWT;/周转时间之和double SumWWT;/带权周转时间之和double AverageWT;/平均周转时间double AverageWWT;/平均带权周转时间typedef struct /定义队列，封装头结点，指针分别指向队头和队尾PCB *

11、front,*rear;queue;queue *init()/进程队列置空queue *head;head=(queue*)malloc(sizeof(queue);head->front=NULL;head->rear=NULL;return head;int empty(queue *head) /检验队列是否为空return (head->front?0:1);/进程队列入队，往后插入queue *appe nd(queue *head,char cMaxNum,i nt a,i nt r,char s)PCB *p;p=(PCB *)malloc(sizeof(PC

12、B);strcpy(p->Name,c);p->arrivetime=a;p->runtime=r;p->wholetime=r;p->state=s;p->FinishTime=O;p->WeightTime=O;p->WeightWholeTime=0;p->next=NULL;if(empty(head)head->front=head->rear=p;elsehead->rear->next=p;head->rear=p;return head;queue *creat(queue *head)/ 创建

13、进程队列char cMaxNum;char s='R'int a,r,i;printf("请输入共有几个进程：n");sca nf("%d",&N);for(i=1;i<=N;i+)printf("请输入第%d个进程的进程名:n",i);getchar();gets(c);printf("请输入第%d个进程的到达时间:n",i);sca nf("%d", &a);printf("请输入第%d个进程的服务时间：n",i);sca nf(&q

14、uot;%d", &r);head=appe nd(head,c,a,r,s);retur n head;void print(queue *head) /输入创建的进程队列PCB *p;p=head->front;if(!p)printf("时间片轮转调度队列为空！n");while(p)arrivetime=%druntime=%dprintf("Name=%sstate=%c",p->Name,p->arrivetime,p->runtime,p->state);printf("n"

15、;);p=p->next; void RR(queue *head,int q) *时间片轮转法调度算法的实现*int t=head->front->arrivetime, lt=head->rear->arrivetime;if(head->front->runtime<q)t=t+head->front->runtime;elset=t+q;/*进程队列为不空才可调度*/while(!empty(head)PCB *p1,*p2;printf("n 时刻 进程 运行后的状态n");/*第一种情况：当前运行的时间

16、小于最后一个进程到达时间做一下操作*/ while(t<lt)p1=head->front;printf("%2d%s",t,p1->Name);p1->runtime=p1->runtime-q;1.运行时间小于0，删除队首if(p1->runtime<=0)p1->state='C：printf("%cn",p1->state);p1->FinishTime=t;p1->WeightTime=p1->FinishTime-p1->arrivetime; p1->

17、;WeightWholeTime=p1->WeightTime/p1->wholetime;SumWT+=p1->WeightTime;SumWWT+=p1->WeightWholeTime;printf(”时刻2d 进程%s 运行结束，进程%s周转时 间=%5.2f,带权周转时间=%5.2fn",t,p1->Name,p1->Name,p1->WeightTime,p1->WeightWholeTime);head->front=p1->next;free(pl);2.运行时间大于0，向后找位置插入elseprintf(&

18、quot;%cn",p1->state);p2=p1->next;while(p2->next && p2->arrivetime != t)p2=p2->next;/此时无新进入队列的进程，有两种情况：1.不用找位置往后插入，队首不变，不做操作2.找位置往后插入if(p2->arrivetime != t)PCB *p3=p1,*p4;while(p3->next && p3->arrivetime<t)p4=p3;p3=p3->next;if(p3->arrivetime>t)

19、if(p4!=p1)p1 插在 p4 后，头为 p1->nexthead->front=p1->next;p1->next=p4->next; p4->next=p1;else /不做操作p4=p3=p2=NULL;elsep4=p3=p2=NULL;/此时有新进入队列的进程时：p1插在新进入队列的进程 p2后，队首为p1->nextelsehead->front=p1->next;p1->next=p2->next;p2->next=p1;/时刻变化if(head->fro nt->r un time<

20、q)t=t+head->fron t->ru ntime;elset=t+q；*第一种情况结束*/*第二种情况：当期运行的时间大于最后一个进程到达的时间做以下操作*/while(t>=lt)p1=head->front;printf("%2d%s",t,p1->Name);p1->runtime=p1->runtime-q;/1.运行时间小于0，删除队首if(p1->runtime<=0)p1->state='C：printf("%cn",p1->state);p1->Fin

21、ishTime=t;p1->WeightTime=p1->FinishTime-p1->arrivetime;p1->WeightWholeTime=p1->WeightTime/p1->wholetime;SumWT+=p1->WeightTime;SumWWT+=p1->WeightWholeTime;printf("时刻%2d 进程%s 运行结束，进程%s周转时 间=%5.2f,带权周转时间=%5.2fn",t,p1->Name,p1->Name,p1->WeightTime,p1->Weight

22、WholeTime);/printf(" 时刻 %2d 进程%s 运行结束",t,p1->pname);head->front=p1->next;free(p1);/2.运行时间大于0，直接插在队尾elseprintf("%cn",p1->state);/若原队列只有一个进程，不必往队尾插if(!p1-> next)head->fro nt=p1;/若原队列有多个进程elsehead->front=p1->next;head->rear->next=p1;head->rear=p1; p1

23、->next=NULL;/时刻变化，队列为空时不做时刻变化if(empty(head)return;else if(head->fro nt->run time<q)t=t+head->fro nt->ru ntime; elset=t+q;/*第二种情况结束*/主程序Main.cpp#include<iostream>#include<stdio.h> #include<string.h>#include<stdlib.h>#include<ctype.h>#include "RR.h&

24、quot;void main()queue *head;int q;head=init();head=creat(head);printf("n您输入的时间片轮转进程队列为:n");print(head);printf("n请输入时间片轮转调度的时间片为:");scanf("%d", &q);/时间片轮转调度RR(head,q);AverageWT=SumWT/N;AverageWWT=SumWWT/N;printf("平均周转时间=%5.2f,平均带权周转时间=%5.2f",AverageWT,Avera

25、geWWT);运行结果：先来先服务：SIbub昭眼冬-exm”MtefefefrH 社-JxH-丄卜情输入进程喀.进程到达时伺，建程运行时i辛 L2”或程到达时间"进程运行时闾;I之步轧 ，丿I址上阳之制樂束 空归呀址在W前结习 整从开姑”在聃之俞桔扌匚&圳94开姗在抽之型结宜 4加开始”在M玄輕就 皿斛旳.在历选舞* 卩灯开朕在1蛇之筮逋.璋在ig%N费结卷 JT坦若丄声之冋结東、=丿為!苗丄士 H7 _6 K.142b 3 Fin 在胡z立或:岂王 11圧LIMN 或纯1幼sTitb在却晾:剪虑E 均加讶姑 Saa 2*短进程:时间片轮：ns =8» i*1ub t iinB=12ne =9*aippl u<e t inB=l 3vie =113丄 me!亡：Lmt y! 4ne -11flrr lyct irnc-20lie -12arrlvct line -23ne 3 arr Ltjet ime -2 4vunina=4