进程调度算法实验报告

实验题目：进程调度算法 实验环境：C++

实验目的：编程模拟实现几种常见的进程调度算法，通过对几组进程分别使用不同的调度算法，计

算进程的平均周转时间和平均带权周转时间，比较各种算法的性能优劣。

实验内容：编程实现如下算法：

1.先来先服务算法； 2.短进程优先算法； 3.时间片轮转调度算法。

设计分析： 程序流程图： 1.先来先服务算法

开始 初始化PCB，输入进程信息 各进程按先来先到的顺序进入就绪队列 结束 就绪队列？ 运行 运行进程所需CPU时间 取消该进程 2.短进程优先算法 3.时间片轮转调度算法 实验代码：

1. 先来先服务算法

#include #define n 20 typedef struct {

int id; //进程名

int atime; //进程到达时间 int runtime; //进程运行时间 }fcs; void main()

{

int amount,i,j,diao,huan; fcs f[n];

cout<<\"请输入进程个数:\"<>amount; for(i=0;icout<<\"请输入进程名，进程到达时间，进程运行时间:\"<>f[i].id; cin>>f[i].atime; cin>>f[i].runtime; }

for(i=0;i{ //如果两个进程同时到达，按在屏幕先输入的先运行 for(j=0;jf[j+1].atime) {diao=f[j].atime; f[j].atime=f[j+1].atime; f[j+1].atime=diao; huan=f[j].id; f[j].id=f[j+1].id; f[j+1].id=huan; } } }

for(i=0;icout<<\"进程:\"<2. 短进程优先算法

#include #define n 5 #define num 5 #define max 65535 typedef struct pro { int PRO_ID; int arrive_time;

int sum_time; int flag;

}Pro;//整数排序 int bubble(int temp[]) {

int i,j,tem=0; for(i=1;i{ int lastX=1;

}

}

for(j=0;jtemp[j+1]) }

if(lastX==1) break;

{ tem=temp[j]; temp[j]=temp[j+1]; temp[j+1]=tem; lastX=0; }

return temp[0];

//进程排序

Pro bubble(Pro p[]) {

int i,j;

Pro temp={0}; Pro s[num]; for(i=0;i{ s[i]=p[i];

}

for(i=1;ireturn s[0];

int lastX=1; for(j=0;jif(lastX==1) break;

if(s[j].sum_time>s[j+1].sum_time) {

temp=s[j]; s[j]=s[j+1]; s[j+1]=temp; lastX=0; }

} void SPF(int p) {

if(n>0) {

int i,j,k,l,tc=0;

Pro seq[n]; Pro temp_seq[n];

printf(\"短进程优先调度算法SPF\\n\");

printf(\"请依次输入5个进程的进程号、到达时间和执行时间\\n\"); printf(\"成员变量用逗号隔开；进程间用回车隔开\\n\");

for(i=0;iscanf(\"%d,%d,%d\}

printf(\"调度顺序是：\\n\"); //初始化tc int temp[num]; for(i=0;itemp[i]=seq[i].arrive_time;

}

tc=bubble(temp);//tc是断点啊

//flag 表示对应i的pro的队列情况

//-1表示未进入过队列，0表示在队列中，1表示被清除了

for(i=0;iseq[i].flag=-1;

for(i=0;ivoid main() { }

SPF(n);

for(j=0;jif(seq[j].flag!=1&&seq[j].arrive_time<=tc){ }

seq[j].flag=0; }

for(j=0;jtemp_seq[j]=seq[j]; if(seq[j].flag!=0){ }

temp_seq[j].sum_time=max; }

l=bubble(temp_seq).PRO_ID;

for(j=0;jif(l==seq[j].PRO_ID){ }

k=j;

tc=tc+bubble(temp_seq).sum_time; seq[k].flag=1; printf(\"%d\}

printf(\"\\n\");

3. 时间片轮转调度算法

头文件RR.h #include

#include #include #include #include #define MaxNum 100

typedef struct pcb //定义进程控制块 {

char Name[MaxNum]; //进程名 int arrivetime; //到达时间 int runtime; //运行时间 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 *front,*rear;

}queue;

queue *init() //进程队列置空 { }

int empty(queue *head) //检验队列是否为空 { }

queue *append(queue *head,char c[MaxNum],int a,int r,char s) //进程队列入队，往后插入 {

PCB *p;

p=(PCB *)malloc(sizeof(PCB)); strcpy(p->Name,c); p->arrivetime=a; p->runtime=r; p->wholetime=r; p->state=s;

return (head->front?0:1); queue *head;

head=(queue*)malloc(sizeof(queue)); head->front=NULL; head->rear=NULL; return head;

}

//p->FinishTime=0; //p->WeightTime=0; //p->WeightWholeTime=0; p->next=NULL; if(empty(head)) else { }

return head;

head->rear->next=p; head->rear=p;

head->front=head->rear=p;

queue *creat(queue *head) //创建进程队列 { }

void print(queue *head) //输入创建的进程队列 { }

/*******************时间片轮转法调度算法的实现**************************/ void RR(queue *head,int q)

PCB *p; p=head->front; if(!p)

printf(\"时间片轮转调度队列为空!\\n\"); char c[MaxNum]; char s='R'; int a,r,i;

printf(\"请输入共有几个进程：\\n\"); scanf(\"%d\for(i=1;i<=N;i++) { }

return head;

printf(\"请输入第%d 个进程的进程名:\\n\getchar(); gets(c);

printf(\"请输入第%d 个进程的到达时间:\\n\scanf(\"%d\

printf(\"请输入第%d 个进程的服务时间:\\n\scanf(\"%d\

head=append(head,c,a,r,s);

while(p) { }

printf(\"Name=%s arrivetime=%d runtime=%d state=%c\printf(\"\\n\"); p=p->next;

{

int t=head->front->arrivetime, lt=head->rear->arrivetime; if(head->front->runtimet=t+q;

t=t+head->front->runtime;

/****进程队列为不空才可调度*****/ while(!empty(head)) {

PCB *p1,*p2;

printf(\"\\n时刻 进程 运行后的状态\\n\");

/*第一种情况：当前运行的时间小于最后一个进程到达时间做一下操作*/ while(tp1=head->front;

printf(\"%2d %s\p1->runtime=p1->runtime-q; //1.运行时间小于0，删除队首 if(p1->runtime<=0) {

p1->state='C';

printf(\" %c\\n\p1->FinishTime=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.2f\\n\

}

//2.运行时间大于0，向后找位置插入 else {

printf(\" %c\\n\p2=p1->next;

while(p2->next && p2->arrivetime != t) { }

//此时无新进入队列的进程，有两种情况：1.不用找位置往后插入，队首不变，不做操作 //2.找位置往后插入 if(p2->arrivetime != t) {

PCB *p3=p1,*p4;

while(p3->next && p3->arrivetimep2=p2->next; head->front=p1->next; free(p1);

}

}

}

p4=p3; p3=p3->next;

if(p3->arrivetime>t) { } else

p4=p3=p2=NULL;

if(p4!=p1) //p1插在p4后，头为p1->next { }

else //不做操作

p4=p3=p2=NULL; head->front=p1->next; p1->next=p4->next; p4->next=p1;

//此时有新进入队列的进程时：p1插在新进入队列的进程p2后，队首为p1->next else { }

head->front=p1->next; p1->next=p2->next; p2->next=p1;

//时刻变化

if(head->front->runtime/*************第一种情况结束**************/

/******************第二种情况：当期运行的时间大于最后一个进程到达的时间做以下操作*********************/ while(t>=lt) {

p1=head->front;

printf(\"%2d %s\p1->runtime=p1->runtime-q; //1.运行时间小于0，删除队首 if(p1->runtime<=0) {

p1->state='C';

printf(\" %c\\n\ else

t=t+q;

t=t+head->front->runtime;

p1->FinishTime=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.2f\\n\

}

}

/*******第二种情况结束*********/ }

}

//2.运行时间大于0，直接插在队尾 else {

printf(\" %c\\n\//若原队列只有一个进程，不必往队尾插

//printf(\"时刻%2d进程%s运行结束\head->front=p1->next; free(p1);

if(!p1->next) }

//时刻变化，队列为空时不做时刻变化 if(empty(head)) else { }

if(head->front->runtimet=t+q;

t=t+head->front->runtime; return;

head->front=p1;

//若原队列有多个进程 else {

head->front=p1->next;

head->rear->next=p1; }

head->rear=p1; p1->next=NULL;

主程序Main.cpp #include #include #include #include #include #include \"RR.h\" void main() {

queue *head; int q; head=init();

}

head=creat(head);

printf(\"\\n您输入的时间片轮转进程队列为:\\n\"); print(head);

printf(\"\\n请输入时间片轮转调度的时间片为:\"); scanf(\"%d\//时间片轮转调度 RR(head,q);

AverageWT=SumWT/N; AverageWWT=SumWWT/N;

printf(\"平均周转时间=%5.2f,平均带权周转时间=%5.2f\

运行结果： 先来先服务： 短进程： 时间片轮： 心得体会：

这次的实验与上次的实验相比，在很多方面都有更多的难度，所以我们参考了别人很多的程序然后稍作了修改。但是由于自身知识不够，所以没能将三个算法都弄到一个大程序中，只能通过三个程序来实现，这一点是我们的不足。虽然如此，我们还是有了一定的收获，比如更加深刻了解到了先来先服务、短进程、时间片轮这三种作业的原理，而且这一过程中我们觉得时间片轮调度算法更具优势。