# include
# include
# include
# include
struct process //定义一个进程的结构体
{
int name; //作业名
int DTime; //到达时间
int STime; //服务时间
int FTime; //完成时间
float CTime; //周转时间
float PTime; //带权周转时间
float Rp; //优先级
struct process *next; //指向下一个作业
};
# define LEN sizeof(struct process) //宏定义结构体的字符长度
int nprocess; //作业数目
process *MIN(process *j,int i)
{ //若i=0，求出j中完成时间最小的作业并返回；若i=1，求出j中服务时间最短的作业并返回;若i=2，求出j中优先权最高的作业并返回
process *p=j->next;
process *q=p;
while(p->next)
{
if(i==0) //完成时间最小的
{
if(q->DTime>=p->next->DTime)
q=p->next;
}
else if(i==1) //服务时间最小的
{
if(q->STime>=p->next->STime)
q=p->next;
}
else if(i==2) //响应比最高的
{
if(q->Rp<=p->next->Rp)
q=p->next;
}
p=p->next;
}
return q;
}
void Delete_process(process *J,process *q,process *j) //删除J中与q相等的结点，并将其插入到j中
{
process *p=J;
while(p->next!=q)
{
p=p->next;
}
process *L=p->next;
p->next=L->next;
L->next=j->next;
j->next=L;
}
int FCFS(process *j1) //先来先服务算法
{
int i;
float sum=0; //周转时间求和
float ctime=0,pctime=0; //ctime为平均周转时间,pctime为带权平均周转时间
int time=0; //当前时间
process *j2= (struct process*)malloc(LEN); //j2中存放已经执行完的作业
j2->next=NULL;
for(i=1;i<=nprocess;i++)
{
process * p=MIN(j1,0);
if(time
time=p->DTime;
p->FTime=time + p->STime;
p->CTime=p->FTime - p->DTime;
time+=p->STime;
p->PTime=p->CTime/p->STime;
printf("%d",p->name);
Delete_process(j1,p,j2); //更新j1
}
j1->next=j2->next; //还原作业序列
printf("\n用FCFS算法，平均周转时间为:\n");
process *q =j2;
while(q->next) //求所有作业的周转时间总和
{
process *p1=q->next;
sum+=p1->CTime;
q=q->next;
}
ctime=sum/nprocess; //平均周转时间
printf("%f\n",ctime);
q =j2; //重新初始化
sum=0; //重新初始化
printf("用FCFS算法，平均带权周转时间为:\n");
while(q->next) //所有作业的带权
周转时间总和
{
process *p2=q->next;
sum+=p2->PTime;
q=q->next;
}
pctime=sum/nprocess; //平均带权周转时间
printf("%f\n",pctime);
return 0;
}
int SPN(process *j1) //短作业优先调度算法
{
int i;
float sum=0;
float ctime=0,pctime=0; //ctime为平均周转时间,pctime为带权平均周转时间
int time=0; //当前时间
process *j2=(struct process*)malloc(LEN); //j2用来存放已经到达的作业的队列
process *j3=(struct process*)malloc(LEN); //j3用来存放已经执行完成的作业序列
j2->next=NULL;
j3->next=NULL;
for(i=1;i<=nprocess;i++)
{
process *p1=j1;
while(p1->next) //求出已经到达的作业，并将其放入j2中
{
if(p1->next->DTime<=time)
Delete_process(j1,p1->next,j2);
else
if(p1->next)
p1=p1->next;
}
if(j2->next==NULL) //若当前没有已经到达的作业，选择到达时间最短的作业执行并更新当前时间
{
process *p=MIN(j1,0);
time=p->DTime;
p->FTime=time+p->STime;
p->CTime=p->FTime - p->DTime;
p->PTime=p->CTime/p->STime;
time += p->STime;
printf("%d",p->name);
Delete_process(j1,p,j3); //更新j1
}
else //从已到达作业中选择服务时间最短的作业执行并更新当前时间
{
process *p2=MIN(j2,1);
p2->FTime=time+p2->STime;
p2->CTime=p2->FTime-p2->DTime;
p2->PTime=p2->CTime/p2->STime;
time += p2->STime;
printf("%d",p2->name);
Delete_process(j2,p2,j3);
process *p3=j1;
while(p3->next) p3=p3->next;
p3->next=j2->next; //将未执行的作业全部放入j1中
j2->next=NULL; //j2清零
}
}
j1->next=j3->next; //还原作业序列
printf("\n用SPN算法，平均周转时间为:\n");
process *q =j3;
while(q->next) //所有作业的周转时间总和
{
process *p1=q->next;
sum+=p1->CTime;
q=q->next;
}
ctime=sum/nprocess; //平均周转时间
printf("%f\n",ctime);
q =j3;
sum=0;
printf("用SPN算法，平均带权周转时间为:\n");
while(q->next) //所有作页的带权周转时间总和
{
process *p2=q->next;
sum+=p2->PTime;
q=q->next;
}
pctime=sum/nprocess; //平均带权周转时间
printf("%f\n",pctime);
return 0;
}
int HRRN(process *j1) //最高响应比优先调度算法
{
int i;
float sum=0;
float ctime=0,pctime=0; //ctime为平均周转时间,pctime为带权平均周转时间
int time=0; //当前时间
process *j2=(struct process*)malloc(LEN); //j2中存放当前时间已经到达的作业
process *j3=(struct process*)malloc(LEN); //j3
中存放已经执行完的作业
j2->next=NULL;
j3->next=NULL;
for(i=1;i<=nprocess;i++)
{
process *p1=j1;
while(p1->next) //求出已经到达的作业，计算响应比后将其放入j2中
{
if(p1->next->DTime<=time)
{
p1->next->Rp=1+float((time - p1->next->DTime))/p1->next->STime;//计算响应比
Delete_process(j1,p1->next,j2);
}
else
if(p1->next)
p1=p1->next;
}
if(j2->next==NULL) //若当前没有已经到达的作业，选择到达时间最短的作业执行并更新当前时间
{
process *p=MIN(j1,0);
time=p->DTime;
p->FTime=time+p->STime;
p->CTime=p->FTime - p->DTime;
p->PTime=p->CTime/p->STime;
time += p->STime;
printf("%d",p->name);
Delete_process(j1,p,j3);//更新j1
}
else //从已到达作业中选择响应比最高的作业执行并更新当前时间
{
process *p2=MIN(j2,2);
p2->FTime=time+p2->STime;
p2->CTime=p2->FTime-p2->DTime;
p2->PTime=p2->CTime/p2->STime;
time += p2->STime;
printf("%d",p2->name);
Delete_process(j2,p2,j3);
process *p3=j1;
while(p3->next) p3=p3->next;
p3->next=j2->next; //将未执行的作业全部放入j1中
j2->next=NULL; //j2清零
}
}
j1->next=j3->next; //还原作业序列
printf("\n用HRRN算法，平均周转时间为:\n");
process *q =j3;
while(q->next) //所有作业的周转时间总和
{
process *p1=q->next;
sum+=p1->CTime;
q=q->next;
}
ctime=sum/nprocess; //平均周转时间
printf("%f\n",ctime);
q =j3;
sum=0;
printf("用HRRN算法，平均带权周转时间为:\n");
while(q->next) //所有作业的带权周转时间总和
{
process *p2=q->next;
sum+=p2->PTime;
q=q->next;
}
pctime=sum/nprocess; //平均带权周转时间
printf("%f\n",pctime);
return 0;
}
int main()
{
int i,x2,x3,x1;
process *J=(struct process*)malloc(LEN);
J->next=NULL;
printf("请输入进程数:\n");
scanf("%d",&nprocess);
for(i=nprocess;i>0;i--) //输入各进程的到达时间与服务时间
{
process *p=(struct process*)malloc(LEN);
printf("请输入新进程的名称:");
scanf("%d",&x1);
p->name=x1;
printf("请输入该进程的到达时间:");
scanf("%d",&x2);
p->DTime=x2;
printf("请输入该进程的运行时间:");
scanf("%d",&x3);
p->STime=x3;
p->Rp=0;
p->next=J->next;
J->next=p;
}
printf("用FCFS调度顺序为:");
FCFS(J);
printf("用SPN调度顺序为:");
SPN(J);
printf("用HRRN调度顺序为:");
HRRN(J);
system("pause");
return 0;
}