进程调度(C语言实现).doc

#include<stdio.h>
#include<stdio.h>
#include<malloc.h>

typedef struct ProcessNode{ // 进程结点的基本结构
char name; //进程名
int service_time; //服务时间
int arrive_time; //到达时间
int priority; //优先级

struct FCFS_time{ //先到先服务
int finish_time; //完成时间
int turnaround_time; //周转时间
float weigtharound_time;//带权周转时间
}FCFS_time;

struct SJF_time{ //短作业优先
int finish_time;
int turnaround_time;
float weigtharound_time;
int flag;
}SJF_time;

struct RR_time{ //时间片轮转的结点
int finish_time;
int turnaround_time;
float weigtharound_time;
int flag_time;//赋值为进程的服务时间，为0则进程完成
}RR_time;

struct Pri_time{ //优先权非抢占式
int finish_time;
int turnaround_time;
float weigtharound_time;
}Pri_time;

struct ProcessNode*next;
}ProcessNode,*Linklist;

void main()
{

int choice;
Linklist p,head;
Linklist read_information();
Linklist FCFS_scheduling(Linklist head);
Linklist SJF_scheduling(Linklist head);
Linklist RR_scheduling(Linklist head);
Linklist Pri_scheduling(Linklist head);

head=read_information();//读入进程的基本信息
do{

p=head->next;
printf("\n");
printf("**********进程初始信息输出********** \n"); //输出初始化后的进程基本信息
printf("\n");
printf("进程名称 ");
printf("到达时间 ");
printf("服务时间 ");
printf("优先级 ");
printf("\n");
while(p)
{
printf(" %c ",p->name);
printf(" %d ",p->arrive_time);
printf(" %d ",p->service_time);
printf(" %d ",p->priority);
printf("\n");
p=p->next;
}

printf("\n");
printf("************************************ \n");//输出进程的调用选择项
printf("\n");
printf("1、FCFS----先到先服务\n");
printf("2、SJF-----短作业优先\n");
printf("3、RR------时间片轮转\n");
printf("4、Pri-----优先权调度\n");
printf("5、退出\n");
printf("\n");
printf("************************************ \n");
printf("\n");
printf("请在1—5之间选择: ");
scanf("%d",&choice);
printf("\n");
printf("\n");
switch(choice)
{
case 1: FCFS_scheduling(head);
break;
case 2: SJF_scheduling(head);
break;
case 3: RR_scheduling(head);
break;
case 4: Pri_scheduling(head);
break;
// case 5: exit();
}

}while(choice!=5);

}

Linklist read_information()//进程读入函数
{
int i;
int num;
// ProcessNode ;
Linklist pro;
Linklist p;
Linklist head;
printf("\n");
printf("************进程调度算法************ \n");
printf("\n");
printf("请输入进程的个数:");
scanf("%d",&num);
printf("\n");
printf("*************初始化信息************* \n");
printf("\n");

head=(Linklist)malloc(sizeof(ProcessNode));//头结点
head->next=NULL;
p=head;
for(i=1;i<=num;i++)
{
pro=(Linklist)malloc(sizeof(ProcessNode));//创建进程结点

printf(" 输入第%d个进程信息:\n",i);
printf(" 请输入进程名: ");
fflush(stdin);
scanf("%c",&pro->name);
printf(" 到达时间: ");
scanf("%d",&pro->arrive_time);
printf(" 服务时间: ");
scanf("%d",&pro->service_time);
printf(" 优先级↑: ");
scanf("%d",&pro->priority);
//pro->next=head->next; head->next=pro;//逆序建链

p->next=pro; p=pro;//顺序建链
//p++;
pro->next=NULL;

}
printf("\n");
return head;
}

Linklist FCFS_scheduling(Linklist head)//先到先服务算法函数
{

Linklist p;
Linklist q;//指向前一进程
p=head->next;

while(p) //初始化进程的完成时间、周转时间、带权周转时间，初值均赋为0
{
p->FCFS_time.finish_time=0;
p->FCFS_time.turnaround_time=0;
p->FCFS_time.weigtharound_time=0;
p=p->next;
}

p=q=head->next;
p->FCFS_time.finish_time=p->arrive_time;//避免第一个进程到达时间不为0
while(p)
{
if(p->arrive_time<=q->FCFS_time.finish_time)//下一进程已到达，在等待中
{
p->FCFS_time.finish_time=(p->service_time)+(q->FCFS_time.finish_time);//服务时间
p->FCFS_time.turnaround_time=(p->FCFS_time.finish_time)-(p->arrive_time);//周转时间
p->FCFS_time.weigtharound_time=(float)(p->FCFS_time.turnaround_time)/(p->service_time);//带权周转时间
}
else
{
p->FCFS_time.finish_time=p->service_time+p->arrive_time;//服务时间
p->FCFS_time.turnaround_time=(p->FCFS_time.finish_time)-(p->arrive_time);//周转时间
p->FCFS_time.weigtharound_time=(float)(p->FCFS_time.turnaround_time)/(p->service_time);//带权周转时间
}
q=p;
p=p->next;

}

p=head->next;
printf("******************************** FCFS ******************************** \n");//输出先到先服务调度后的进程信息
printf("\n");
printf("进程名称 ");
printf("到达时间 ");
printf("服务时间 ");
printf("优先级 ");
printf("完成时间 ");
printf("周转时间 ");
printf("带权周转时间 ");
printf("\n");
while(p)
{
printf(" %c ",p->name);
printf(" %d ",p->arrive_time);
printf(" %d ",p->service_time);
printf(" %d ",p->priority);
printf(" %d",p->FCFS_time.finish_time);
printf(" %d",p->FCFS_time.turnaround_time);
printf(" %0.2f",p->FCFS_time.weigtharound_time);
printf("\n");
p=p->next;
}
printf("\n");
printf("********************************************************************** \n");
printf("\n");
return head;
}

Linklist SJF_scheduling(Linklist head)//短作业优先算法
{
Linklist p,r;
Linklist q;//指向前一进程结点
int num=0;//记录进程个数
int add_flag=0;//进程完成服务个数
int service_time_min;
int arrive_time;
int k;
p=head->next;//首元结点

while(p) //初始化进程的完成时间、周转时间、带权周转时间，初值均赋为0
{
p->SJF_time.finish_time=0;
p->SJF_time.turnaround_time=0;
p->SJF_time.weigtharound_time=0;
p->SJF_time.flag=0;
++num;
q=p;
p=p->next;
}
q->next=head->next;//将创建的进程队列变为循环队列
p=head->next;q=p;
p->SJF_time.finish_time=p->arrive_time+p->service_time;
p->SJF_time.turnaround_time=(p->SJF_time.finish_time)-(p->arrive_time);//周转时间
p->SJF_time.weigtharound_time=(float)(p->SJF_time.turnaround_time)/(p->service_time);//带权周转时间
q->SJF_time.finish_time=p->SJF_time.finish_time;
p->SJF_time.flag=1; add_flag=1;
p=p->next;

do{
if(p->SJF_time.flag==1){p=p->next;}
else if((p->arrive_time)>(q->SJF_time.finish_time))
{
service_time_min=p->service_time;
arrive_time=p->arrive_time;
while(p->arrive_time==arrive_time&&p->SJF_time.flag==0)//寻找最短的作业
{
if((p->next->service_time)<(p->service_time)){service_time_min=p->next->service_time;p=p->next;}
else {p=p->next;}
}
p=q->next;
r=q;
while(p->service_time!=service_time_min){p=p->next;}//指针指向最短作业
p->SJF_time.finish_time=p->arrive_time+p->service_time;
p->SJF_time.flag=1;++add_flag;
p->SJF_time.turnaround_time=(p->SJF_time.finish_time)-(p->arrive_time);//周转时间
p->SJF_time.weigtharound_time=(float)(p->SJF_time.turnaround_time)/(p->service_time);//带权周转时间
q=p;p=r->next;
}
else
{
k=0;
service_time_min=p->service_time;
while(((p->arrive_time)<=(q->SJF_time.finish_time))&&k<=num)//寻找最短的作业
{
if(p->SJF_time.flag==1) {p=p->next;++k;}
else if((p->SJF_time.flag!=1)&&((p->service_time)<service_time_min))
{ service_time_min=p->service_time;
p=p->next;++k;}
else { p=p->next;++k; }
}
p=q->next;
r=q;
while(p->service_time!=service_time_min){p=p->next;}//指针指向最短作业
p->SJF_time.finish_time=q->SJF_time.finish_time+p->service_time;
p->SJF_time.turnaround_time=(p->SJF_time.finish_time)-(p->arrive_time);//周转时间
p->SJF_time.weigtharound_time=(float)(p->SJF_time.turnaround_time)/(p->service_time);//带权周转时间
p->SJF_time.flag=1;++add_flag;
//q=p;p=p->next;
q=p;p=r->next;
}
}while(add_flag!=num);

for(p=head->next;num>0;num--)//断开循环队列
{
q=p;p=p->next;
}
q->next=NULL;

p=head->next;//指向链首，输出短作业调度后的进程信息
printf("\n");
printf("******************************** SJF ********************************* \n");
printf("\n");
printf("进程名称 ");
printf("到达时间 ");
printf("服务时间 ");
printf("优先级 ");
printf("完成时间 ");
printf("周转时间 ");
printf("带权周转时间 ");
printf("\n");
while(p)
{
printf(" %c ",p->name);
printf(" %d ",p->arrive_time);
printf(" %d ",p->service_time);
printf(" %d ",p->priority);
printf(" %d",p->SJF_time.finish_time);
printf(" %d",p->SJF_time.turnaround_time);
printf(" %0.2f",p->SJF_time.weigtharound_time);
printf("\n");
p=p->next;
}
printf("\n");
printf("********************************************************************** \n");
printf("\n");
return head;
}

Linklist RR_scheduling(Linklist head)//时间片轮转算法
{
Linklist q;//指向前一进程结点
Linklist p;
int q_time;//时间片大小
int num=0;//记录进程个数
int add_flag=0;//进程完成服务个数

printf("请输入时间片的大小: ");
scanf("%d",&q_time);

p=head->next;
while(p) //初始化进程的完成时间、周转时间、带权周转时间，初值均赋为0
{
p->RR_time.finish_time=0;
p->RR_time.turnaround_time=0;
p->RR_time.weigtharound_time=0;
p->RR_time.flag_time=p->service_time;
q=p;
++num;
p=p->next;
}

q->next=head->next;//将创建的进程队列变为循环队列
p=head->next;
q->RR_time.finish_time=p->arrive_time;
do{
/* printf("\n");
printf("************************************************************** \n");
printf(" %c ",p->name);
printf(" %d ",p->arrive_time);
printf(" %d ",p->service_time);
printf(" %d ",p->priority);
printf(" %d",p->RR_time.finish_time);
printf("\n"); */

if((p->RR_time.flag_time)>(q_time))//服务时间大于时间片
{
p->RR_time.finish_time=(q->RR_time.finish_time)+(q_time);//累加完成时间
p->RR_time.flag_time=(p->RR_time.flag_time)-(q_time);
if((p->next->arrive_time)<=(p->RR_time.finish_time))//有进程等待
{ q=p;p=p->next; }
else //当前进程未完成，无进程等待，指针不向后移
{ q=p; }
}
else if((p->RR_time.flag_time)==0)//进程已经完成
{
p=p->next;
}
else
{
p->RR_time.finish_time=(q->RR_time.finish_time)+(p->RR_time.flag_time);
p->RR_time.flag_time=0; ++add_flag;
p->RR_time.turnaround_time=(p->RR_time.finish_time)-(p->arrive_time);//周转时间
p->RR_time.weigtharound_time=(float)(p->RR_time.turnaround_time)/(p->service_time);//带权周转时间
if((p->next->arrive_time)<(p->RR_time.finish_time))//有进程等待
{ q=p;p=p->next; }
else //当前进程完成，无进程等待，指针向后移
//{ q=p; q->RR_time.finish_time=p->next->arrive_time; }
{p=p->next;q=p;q->RR_time.finish_time=p->arrive_time;}
}
}while(add_flag!=num);
//}while(p->RR_time.flag==0);

for(p=head->next;num>0;num--)//断开循环队列
{
q=p;p=p->next;
}
q->next=NULL;

p=head->next;//指向链首，输出时间片轮转调度后的进程信息
printf("\n");
printf("******************************** RR ********************************** \n");
printf("\n");
printf("进程名称 ");
printf("到达时间 ");
printf("服务时间 ");
printf("优先级 ");
printf("完成时间 ");
printf("周转时间 ");
printf("带权周转时间 ");
printf("\n");
while(p)
{
printf(" %c ",p->name);
printf(" %d ",p->arrive_time);
printf(" %d ",p->service_time);
printf(" %d ",p->priority);
printf(" %d",p->RR_time.finish_time);
printf(" %d",p->RR_time.turnaround_time);
printf(" %0.2f",p->RR_time.weigtharound_time);
printf("\n");
p=p->next;
}
printf("\n");
printf("********************************************************************** \n");
printf("\n");
return head;
}

Linklist Pri_scheduling(Linklist head)//优先权调度算法
{

printf(" 优先权调度算法 \n");
return head;
}