#include<stdio.h>
#include<stdlib.h>
#include<windows.h>
#include<conio.h>
#define N 20
#define M 1000000
#define NULL 0
typedef struct qNode
{ int name;
float arrive;
float runtime;
float response;
struct qNode *next;
}qNode,*linkPtr;
typedef struct linkQueue /*定义队列*/
{ linkPtr front;
linkPtr rear;
}linkQueue;
initQueue(linkQueue *q)
{ (*q).front=(*q).rear=(linkPtr)malloc(sizeof(qNode));
if(!(*q).front)
{ printf("creat fail!\n");
exit(0);
}
(*q).rear->next=NULL;
return;
}
createWork(linkQueue *work) /*按输入创建工作队列*/
{ qNode p;
qNode *ptr;
int i,n;
char get='1';
ptr=(*work).rear;
printf("how many work do you want to do:\n");
scanf("%d",&n);
printf("input the work as:name arrive-time runtime,as: 6 8.9 3.1\n");
/*printf("Press Twice when input the work's name,'q' to quit input\n");*/
for(i=0;i<n;i++)
{ ptr=(linkPtr)malloc(sizeof(qNode));
scanf("%d %f %f",&p.name,&p.arrive,&p.runtime);
p.next=NULL;
*ptr=p;
(*work).rear->next=ptr;
(*work).rear=ptr;
}
return n;
}
prinInf()
{ printf("input your choice\n");
printf("\t1 first come first server\t\t2 shortest job first\n");
printf("\t3 shortest surplus_time first\t\t4 high response_ratio next\n");
printf("\t0 to quit\n");
printf(": ");
}
printJob(linkPtr ptr) /*打印输入作业*/
{ ptr=ptr->next;
printf("input work were:\n");
while(ptr)
{ printf("%d %10.3f %10.3f\n",ptr->name,ptr->arrive,ptr->runtime);
ptr=ptr->next;
}
}
fcfs(int n,linkPtr avp) /*先来先服务*/
{ linkQueue fcfs;
linkPtr ptr,tmp;
int i;
float t,T,Tw,Tt[N][2];
T=Tw=0.0;
i=0;
initQueue(&fcfs);
avp=avp->next;
while(avp) /*按到达时间排序*/
{ ptr=fcfs.front;
tmp=(linkPtr)malloc(sizeof(qNode));
while(ptr->next->arrive<=avp->arrive&&ptr->next)
{ ptr=ptr->next;
}
tmp->name=avp->name;
tmp->arrive=avp->arrive;
tmp->runtime=avp->runtime;
tmp->next=ptr->next;
ptr->next=tmp;
if(ptr==fcfs.rear)
{ fcfs.rear=tmp;
}
avp=avp->next;
}
ptr=fcfs.front->next;
t=ptr->arrive;
while(ptr) /*按先来先服务进行相关计算*/
{ if(ptr->arrive<=t)
{ t=t+ptr->runtime;
Tt[i][0]=t-ptr->arrive;
Tt[i][1]=Tt[i][0]/ptr->runtime;
ptr=ptr->next;
++i;
}
else
{ t=ptr->arrive;
t=t+ptr->runtime;
Tt[i][0]=t-ptr->arrive;
Tt[i][1]=Tt[i][0]/ptr->runtime;
ptr=ptr->next;
++i;
}
}
ptr=fcfs.front->next;
for(i=0;i<n;i++)
{ T=T+Tt[i][0];
Tw=Tw+Tt[i][1];
}
T=T/n;
Tw=Tw/n;
printf("\nturn:\n");
while(ptr)
{ printf("%d ",ptr->name);
ptr=ptr->next;
}
printf("\njob cost time cost time with weight\n");
ptr=fcfs.front->next;
for(i=0;i<n;i++)
{ printf("%d %10.3f %10.3f\n",ptr->name,Tt[i][0],Tt[i][1]);
ptr=ptr->next;
}
printf("\naverage cost time: %10.3f\naverage cost time with weight: %10.3f\n",T,Tw);
}
sjf(int n,linkPtr avp) /*短作业优先*/
{ linkQueue fcfs;
linkPtr ptr,tmp,temp;
int i,j,k,num,turn;
double t,T,Tw,Tt[N][2];
int R[2*N],Rr[N];
T=Tw=0.0;
turn=num=k=i=0;
initQueue(&fcfs);
avp=avp->next;
while(avp) /*按到达时间排序*/
{ ptr=fcfs.front;
tmp=(linkPtr)malloc(sizeof(qNode));
while(ptr->next->arrive<=avp->arrive&&ptr->next)
{ ptr=ptr->next;
}
tmp->name=avp->name;
tmp->arrive=avp->arrive;
tmp->runtime=avp->runtime;
tmp->next=ptr->next;
ptr->next=tmp;
if(ptr==fcfs.rear)
{ fcfs.rear=tmp;
}
avp=avp->next;
}
fcfs.front->arrive=fcfs.front->runtime=M;
ptr=fcfs.front->next;
t=ptr->arrive;
temp=fcfs.front;
while(ptr!=NULL) /*到达最后一个作业之后停止第一步计算*/
{ tmp=fcfs.front->next;
temp=fcfs.front;
j=0;
while(ptr->arrive<=t)
{ ptr=ptr->next;
}
while(tmp!=ptr)
{ if(tmp->runtime<temp->runtime)
{ temp=tmp;
}
tmp=tmp->next;
}
if(temp->runtime!=M)
{ R[i]=Rr[k]=temp->name;
Tt[k][0]=t+temp->runtime-temp->arrive;
Tt[k][1]=Tt[k][0]/temp->runtime;
turn=i;
t=t+temp->runtime;
temp->runtime=M;
while(ptr->arrive<=t)
{ ptr=ptr->next;
}
k++;
i++;
}
tmp=fcfs.front->next;
while(tmp!=ptr) /*查看在PTR指针指向作业之前有没有作业还未运行完*/
{ if(tmp->runtime!=M)
j++;
tmp=tmp->next;
}
if(j==0) /*若在PTR之前作业都已做完，将时间置为PTR指向的作业的时间*/
{ t=ptr->arrive;
}
}
ptr=fcfs.front->next;
for(j=0;j<n;j++) /*统计第一步进行完后剩余未完成作业数*/
{ if(ptr->runtime!=M)
{ num++;
}
ptr=ptr->next;
}
for(j=0;j<num;j++) /*在剩下作业中进行作业调度*/
{ ptr=fcfs.front->next;
while(ptr)
{ while(ptr) /*找第一个未完成的作业*/
{ if(ptr->runtime<M)
{ temp=ptr;
break;
}
ptr=ptr->next;
}
while(ptr) /*找最短作业时间*/
{
if(ptr->runtime<temp->runtime)
temp=ptr;
ptr=ptr->next;
}
}
if(temp->runtime!=M)
{ Rr[k]=temp->name;
Tt[k][0]=t+temp->runtime-temp->arrive;
Tt[k][1]=Tt[k][0]/temp->runtime;
R[i]=temp->name;
turn=i;
i++;
k++;
t=t+temp->runtime;
temp->runtime=M;
}
}
for(i=0;i<n;i++)
{ T=T+Tt[i][0];
Tw=Tw+Tt[i][1];
}
T=T/n;
Tw=Tw/n;
printf("\ntrun:\n");
for(i=0;i<=turn;i++)
{ printf("%d ",R[i]);
}
printf("\n");
printf("\njob cost time cost time with weight\n");
for(i=0;i<n;i++)
{ printf("%d %10.3f %10.3f\n",Rr[i],Tt[i][0],Tt[i][1]);
}
printf("\naverage cost time: %10.3f\naverage cost time with weight: %10.3f\n",T,Tw);
}
rsjf(int n,linkPtr avp) /*最短剩余时间优先*/
{ linkQueue fcfs;
linkPtr ptr,tmp,temp;
int i,j,k,num,turn;
double t,T,Tw,Tt[N][2];
int R[2*N],Rr[N];
T=Tw=0.0;
turn=num=k=i=0;
initQueue(&fcfs);
avp=avp->next;
while(avp) /*按先来先服务排序，便于以后调度用*/
{ ptr=fcfs.front;
tmp=(linkPtr)malloc(sizeof(qNode));
while(ptr->next->arrive<=avp->arrive&&ptr->next)
{ ptr=ptr->next;
}
tmp->name=avp->name;
tmp->arrive=avp->arrive;
tmp->runtime=avp->runtime;
tmp->next=ptr->next;
ptr->next=tmp;
if(ptr==fcfs.rear)
{ fcfs.rear=tmp;
}
avp=avp->next;
}
fcfs.front->arrive=fcfs.front->runtime=M;
ptr=fcfs.front->next;
t=ptr->arrive;
while(ptr!=fcfs.rear)
{ T=ptr->next->arrive-ptr->arrive; /*作业调度时间差*/
while(T>0.0)
{ tmp=temp=fcfs.front;
while(tmp!=ptr)
{ if(tmp->next->runtime<temp->runtime)
{ temp=tmp->next;
}
tmp=tmp->next;
}
if(temp->runtime>T)
{ temp->runtime=temp->runtime-T;
R[i]=temp->name;
t=t+T;
T=0.0;
turn=i;
i++;
}
else if(temp->runtime==T)
{ R[i]=Rr[k]=temp->name;
Tt[k][0]=t+temp->runtime-temp->arrive;
Tt[k][1]=Tt[k][0]/temp->runtime;
temp->runtime=M;
t=t+T;
T=0.0;
turn=i;
i++;
k++;
}
else
{ R[i]=Rr[k]=temp->name;
Tt[k][0]=t+temp->runtime-temp->arrive;
Tt[k][1]=Tt[k][0]/temp->runtime;
turn=i;
i++;
k++;
t=t+temp->runtime;
T=T-temp->runtime;
temp->runtime=M;
}
}
ptr=ptr->next;
}
ptr=fcfs.front->next;
for(j=0;j<n;j++)
{ if(ptr->runtime!=M)
{ num++;
}
ptr=ptr->next;
}
for(j=0;j<num;j++)
{ ptr=fcfs.front->next;
while(ptr)
{ while(ptr) /*找第一个未完成的作业*/
{ if(ptr->runtime<M)
{ temp=ptr;
break;
}
ptr=ptr->next;
}
while(ptr) /*找最短作业时间*/
{
if(ptr->runtime<temp->runtime)
temp=ptr;
ptr=ptr->next;
}
}
if(temp->runtime!=M)
{ R[i]=Rr[k]=temp->name;
Tt[k][0]=t+temp->runtime-temp->arrive;
Tt[k][1]=Tt[k][0]/temp->runtime;
turn=i;
i++;
k++;
t=t+temp->runtime;
temp->runtime=M;
}
}
for(i=0;i<n;i++)
{ T=T+Tt[i][0];
Tw=Tw+Tt[i][1];
}
T=T/n;
Tw=Tw/n;
printf("\ntrun:\n");
for(i=0;i<=turn;i++)
{ if(R[i]<1000)
printf("%d ",R[i]);
}
printf("\n");
printf("\njob cost time cost time with weight\n");
for(i=0;i<n;i++)
{ printf("%d %10.3f %10.3f\n",Rr[i],Tt[i][0],Tt[i][1]);
}
printf("\naverage cost time: %10.3f\naverage cost time with weight: %10.3f\n",T,Tw);
return;
}
hrn(int n,linkPtr avp) /*最高响应比优先*/
{ linkQueue fcfs;
linkPtr ptr,tmp,temp;
int i,j,k,done;
float t,T,Tw,tempRes,Tt[N][2];
int R[N];
T=Tw=0.0;
k=i=0;
initQueue(&fcfs);
avp=avp->next;
while(avp) /*按先来先服务排序，便于以后调度用*/
{ ptr=fcfs.front;
tmp=(linkPtr)malloc(sizeof(qNode));
while(ptr->next->arrive<=avp->arrive&&ptr->next)
{ ptr=ptr->next;
}
tmp->name=avp->name;
tmp->arrive=avp->arrive;
tmp->runtime=avp->runtime;
tmp->next=ptr->next;
ptr->next=tmp;
if(ptr==fcfs.rear)
{ fcfs.rear=tmp;
}
avp=avp->next;
}
fcfs.front->response=0.5;
tmp=ptr=fcfs.front->next;
temp=fcfs.front;
t=ptr->arrive;
done=n;
while(done>0)
{ j=0;
tmp=fcfs.front->next;
temp=fcfs.front;
while(t>=ptr->arrive&&ptr!=NULL)
ptr=ptr->next;
while(tmp!=ptr)
{ if((tmp->response)!=0.5)
{ tmp->response=1+(t-tmp->arrive)/tmp->runtime;
}
if(tmp->response>temp->response&&tmp->response>=1.0)
temp=tmp;
tmp=tmp->next;
}
if((temp->response)!=0.5)
{ t=t+temp->runtime;
R[k]=temp->name;
Tt[k][0]=t-temp->arrive;
Tt[k][1]=Tt[k][0]/temp->runtime;
temp->response=0.5; /*将完成作业的响应比置为0.5*/
k++;
}
tmp=fcfs.front->next;
while(tmp!=ptr)
{ if((tmp->response)!=0.5)
++j;
tmp=tmp->next;
}
if(j==0&&t<ptr->arrive)
{ t=ptr->arrive;
}
--done;
}
for(i=0;i<n;i++)
{ T=T+Tt[i][0];
Tw=Tw+Tt[i][1];
}
T=T/n;
Tw=Tw/n;
printf("\nturn:\n");
for(i=0;i<n;i++)
{ printf("%d ",R[i]);
}
printf("\n");
printf("\njob cost time cost time with weight\n");
for(i=0;i<n;i++)
{ printf("%d %10.3f %10.3f\n",R[i],Tt[i][0],Tt[i][1]);
}
printf("\naverage cost time: %10.3f\naverage cost time with weight: %10.3f\n",T,Tw);
}
main()
{ linkQueue work;
linkPtr ptr;
int num;
char choice;
choice='5';
initQueue(&work);
num=createWork(&work);
ptr=work.front;
while(choice!='0')
{ system("cls");
prinInf();
choice=getchar();
printJob(work.front); /*打印作业程序使用者输入的作业*/
switch(choice)
{ case '1': fcfs(num,ptr);break;
case '2': sjf(num,ptr);break;
case '3': rsjf(num,ptr);break;
case '4': hrn(num,ptr);break;
case '0': exit(0);
}
printf("\npress anykey to continue.......\n");
system("pause");
}
}
