fsdfs.cpp

计算机专业（编译原理课程设计 原代码）

#define N 20
#define M 1000000
#define NULL 0
#include<stdio.h>
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();
	}
	(*q).rear->next=NULL;
}
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);
}
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();
		}
		printf("\npress anykey to continue.......\n");
		getch();

	}


}.