zuoyedd.cpp

采用FCFS、SJF、响应比高者优先算法模拟设计作业调度程序。 [提示]： （1）每个作业的JCB中包括作业名、提交时刻、要求运行时间； （2）假设第一个作业提交时

#define error 0
#define ok 1
#define NULL 0
#define job_num 10

#include<stdio.h>




typedef struct JNode
{
char       name;
float		arrive;/*/到达时间*/

float		demand;/*需要运行的时间*/
float      priority;
char        state;
float        Tb; /*开始运行时刻*/
float        Tc; /*完成时刻 */
float        Ti;           /*周转时间*/
float        Wi;          /*带权周转时间*/
struct JNode   *next;
}JNode, *JCB;


typedef struct JList
{                  /*带头结点的JCB链表指针*/

	JCB head;
}JList;


int InitJCB(JCB L)
{
  L=new(JNode);

  L->next=NULL;
  return ok;
}         /*创建空JCB链表*/

int InitJList(JList *L)
{
  L->head=new(JNode);
  if(!L->head) return error;
  L->head->next=NULL;
  return ok;
}       /*创建空带头接点的JCB链表*/

int ListInsert_FCFS(JList *L,JCB e)/*先到先服务*/
{
    JCB p;
    p=L->head;
    while (p->next!=NULL&&e->arrive>p->next->arrive)/*找到最先到达的*/
    p=p->next;
    e->next=p->next;
    p->next=e;
    return ok;
}/*将一个结点插入到表中，表的顺序为从提交时间早到晚*/
//到达时间早叉早前面，完叉在后面



void Do_FCFS(JList L,JCB j[],int n)  
{    int i;
     float T;
	 JCB p;
	 char S[job_num];
	 float addWi=0;
	 float addTi=0;

	for (i=0;i<n;i++)
	{
       ListInsert_FCFS(&L,j[i]);
	}/*创建先到先服务的相关链表*/

T=L.head->next->arrive;/*当前时间设置为最早的提交时间*/
p=L.head->next;/*第一个接点*/

for (i=0;i<n;i++)
{
      if (p->arrive<T)/*提交时间大于当前时刻*/
       p->Tb=T;/*当前接点开始运行时间等于当前时间,当前接点的开始时间置为当前时间*/
      else p->Tb=p->arrive;
	  /*当前接点的提交时间大于等于T，当前接点得到响应，开始执行时间等于当前时间*/
      S[i]=p->name;
	  p->Tc=p->Tb+p->demand;/*完成时刻*/
      p->Ti=p->Tc-p->arrive;/*周转时间*/
      addTi+=p->Ti;
      p->Wi=p->Ti/p->demand;/*周转时间/需要运行的时间*/
      addWi+=p->Wi;
	  T=p->Tc;
      p=p->next;
}
 addTi=addTi/n;
 addWi=addWi/n;
printf("FCFS调度结果------------------------------------------------------------------\n\n");

printf("作业名 提交时刻 运行时间 开始运行时刻 完成时刻 等待时间 周转时间 带权周转时间 \n");

        for (i=0;i<n;i++)
        {
	  printf("%c  %f  %f  %f  %f  %f  %f  %f\n",j[i]->name,j[i]->arrive,j[i]->demand,j[i]->Tb,j[i]->Tc,(j[i]->Tb)-(j[i]->arrive),j[i]->Ti,j[i]->Wi);
        }
printf("调度顺序:");
        for(i=0;i<n;i++)
        {
		 printf("%c--------",S[i]);
		}
printf("平均周转时间 ：%f   平均带权周转时间 ：%f ",addTi,addWi);

}


int ListInsert_SJF(JList *L,JCB e)/*最短作业优先算法，选择运行时间最短的作业先运行*/
{
    JCB p;
    p=L->head;
    while (p->next!=NULL&&e->demand>p->next->demand)
      p=p->next;
    e->next=p->next;
    p->next=e;
    return ok;
}/*将一个结点插入到表中，表的顺序为从运行时间短到长*/
//运行时间短叉早前面，长叉在后面


void Do_SJF(JList L,JCB j[],int n) 
{   
	int i;
	float T,t;
    T=0;
	t=0; /*SJF时间初始化*/
	int IsFinish=1; /*标志是否所有作业都已经完成*/
    InitJList(&L); /*重新初始化JCB链表*/
				  
	 JCB p;
	 char S[job_num];
	 int numer=0;
	 float addWi=0;
	 float addTi=0;
while (IsFinish)
{
      p=L.head;
      for ( i=0;i<n;i++)
      {
       if (t<j[i]->arrive&&j[i]->arrive<=T)/*避免再插入已插入过的JCB，
		                         //第一次，只有（t）T-1到T这一个时间片内的作业可以链入*/
					             //以后每次在上一个链入的接点提交时间和完成时间之间的接点才能链入
        
		   ListInsert_SJF(&L,j[i]);
      }//该循环第一次完成时T的值为最早的提交时间
	  //即当前接点的 到达时间 大于 上个接点的到达时间 并且 小于等于 上个接点的完成时间
	  //大于上个接点完成时间则，T需要++
      t=T;
      if(p->next==NULL)
      {
        float time=j[0]->arrive;
	    for(i=1;i<n;i++)
		{ 
			if(j[i]->arrive<time&&j[i]->state!='F')
				time=j[i]->arrive;
		}
          T=time;//T加到大于等于最早的提交时间是，上层的if条件成立
        continue;//返回for，判断下个时间片内提交的作业
		/*队列为空时重新循环并且时间片自动加*/
       }
        
	    

		
         p->next->Tb=T;/*开始运行时刻等于当前时刻*/
         S[numer]=p->next->name;
		  numer++;
          p->next->Tc=p->next->Tb+p->next->demand;/*完成时刻 */
       p->next->Ti=p->next->Tc-p->next->arrive;//周转时间 完成时间-提交时间
       addTi+=p->next->Ti;
       p->next->Wi=p->next->Ti/p->next->demand;//带权周转时间  周转时间/完成所需时间
       addWi+=p->next->Wi;
	   T=p->next->Tc;//当前时间重置为完成时间
       p->next->state='F';//状态改为完成
       L.head=L.head->next;//头接点变为第一个接点
       IsFinish=0;
       for (i=0;i<n;i++)
		if (j[i]->state!='F')
        IsFinish=1;//还有作业未完成

}




addTi=addTi/n;
addWi=addWi/n;
printf("SJF调度结果------------------------------------------------------------------\n\n");

printf("作业名 提交时刻 运行时间 开始运行时刻 完成时刻 等待时间 周转时间 带权周转时间 \n");

        for (i=0;i<n;i++)
        {
	  printf("%c  %f  %f  %f  %f  %f  %f  %f\n",j[i]->name,j[i]->arrive,j[i]->demand,j[i]->Tb,j[i]->Tc,(j[i]->Tb)-(j[i]->arrive),j[i]->Ti,j[i]->Wi);
        }
       printf("调度顺序:");
        for(i=0;i<n;i++)
        {
		 printf("%c--------",S[i]);
		}
printf("平均周转时间 ：%f   平均带权周转时间 ：%f ",addTi,addWi);

}






int ListInsert_HRN(JList *L,JCB e)//响应比高者优先算法，响应比Rp=1+等待时间/运行时间
{
   JCB p;
   p=L->head;
   while ((p->next!=NULL)&&(e->priority<p->next->priority))
      p=p->next;
   e->next=p->next;
   p->next=e;
   return ok;
}/*将一个结点插入到表中，表的顺序为从响应比高到响应比低*/
//响应比高插在前面，低插在后面


void Do_HRN(JList L,JCB j[],int n) 
{   
	float T;
    T=1;/*HRN时间初始化*/
	int IsFinish=1;
    InitJList(&L); /*重新初始化JCB链表*/
     char S[job_num];
	 int numer=0;
	 float addWi=0;
	 float addTi=0;
	 JCB p;
	 int i;
	
	while (IsFinish)
	{ 
      p=L.head;
      for (i=0;i<n;i++)
      {
       j[i]->priority=1+(T-j[i]->arrive)/j[i]->demand;//上一个作业的完成时间即
	                                                  //开始时间-提交时间
	   if (j[i]->arrive<=T&&j[i]->state!='F')
       {//提交时间比上一个晚并且状态不为完成
        ListInsert_HRN(&L,j[i]);
       }
      }

      if(p->next==NULL)
      {
        float time=j[0]->arrive;
	    for(i=1;i<n;i++)
		{ 
			if(j[i]->arrive<time&&j[i]->state!='F')
				time=j[i]->arrive;
		}
          T=time;//T加到大于等于最早的提交时间是，上层的if条件成立
        continue;//返回for，判断下个时间片内提交的作业
		/*队列为空时重新循环并且时间片自动加*/
       }
      p->next->Tb=T;/*开始运行时刻等于当前时刻*/  
	  
	   //第一个提交的作业，开始运行的时间即其提交的时间，
	   //以后开始的时间为上一个接点的完成时间

	   S[numer]=p->next->name;
	   numer++;      
       p->next->Tc=p->next->Tb+p->next->demand;//完成时间
       p->next->Ti=p->next->Tc-p->next->arrive;//周转时间
       addTi+=p->next->Ti;
       p->next->Wi=p->next->Ti/p->next->demand;//带权周转时间
       addWi+=p->next->Wi;
       T=p->next->Tc;//当前时间置为本作业完成时间
       p->next->state='F';//当前作业状态改为
       InitJList(&L);
       IsFinish=0;
       for (i=0;i<n;i++)
		if (j[i]->state!='F')
        IsFinish=1;

}


printf("HRN调度结果------------------------------------------------------------------\n\n");

addTi=addTi/n;
addWi=addWi/n;

printf("作业名 提交时刻 运行时间 开始运行时刻 完成时刻 等待时间 周转时间 带权周转时间 \n");

        for (i=0;i<n;i++)
        {
	  printf("%c  %f  %f  %f  %f  %f  %f  %f\n",j[i]->name,j[i]->arrive,j[i]->demand,j[i]->Tb,j[i]->Tc,(j[i]->Tb)-(j[i]->arrive),j[i]->Ti,j[i]->Wi);
        }
printf("调度顺序:");
        for(i=0;i<n;i++)
        {
		 printf("%c--------",S[i]);
		}
printf("\n平均周转时间 ：%f   平均带权周转时间 ：%f ",addTi,addWi);

}


void main()
{
  JList L;
  int n;
  JCB j[job_num];   //指针类型的数组，每个元素都是一个JCB类型的指针
  //JCB p;
  JCB temp[job_num]; /*临时存储作业信息以备多次算法都需读取初始信息*/
  int i;
  //float T,t;
  int IsFinish=1;

  InitJList(&L);
  for(i=0;i<job_num;i++)
	   InitJCB(j[i]);
  printf("请输入各作业的相关信息：\n");
  printf("请输入作业的个数(<10)：");
  scanf("%d",&n);

  for(i=0;i<n;i++)//初始化每个作业的相关信息

  {    flushall();
	   j[i]=new(JNode);

	   printf("请输入第%d个作业的名字:",i+1);
	   scanf("%c",&(j[i]->name));
	   
	   printf("请输入第%d个作业的提交时间:",i+1);
	   scanf("%f",&(j[i]->arrive));
	   printf("请输入第%d个作业的需要运行时间:",i+1);
	   scanf("%f",&(j[i]->demand));
       j[i]->state='W';/*状态初始化为等待*/
       j[i]->priority=1;/*等待时间初始为零所以响应比初始化为1*/
       j[i]->Tb=0;
	   j[i]->Tc=0;
	   j[i]->Ti=0;
	   j[i]->Wi=0;
	   j[i]->next=NULL;

	   printf("\n");
}


int a=1;

while(a){
for (i=0;i<job_num;i++)
{
      temp[i]=j[i];
}//对输入信息做一次备份


printf("请选择相关调度算法：\n");
printf("1 先到先服务FCFS    2最短作业优先SJF     3响应比高者优先HRN     0退出");

scanf("%d",&a);
 
switch(a)
{
	case 1: Do_FCFS(L,temp,n) ;    break;
	case 2: Do_SJF(L,temp,n)  ;    break;
	case 3: {
		         for (i=0;i<n;i++)
				 {
                    temp[i]=j[i];
	                temp[i]->state='W';  
             /*不知道为什么，按理TEMP里保存的state应该已经都是W了，但是我不加下面这句运行就得不到下面的结果*/
			}
			 Do_HRN(L,temp,n) ; }    break;

}	   
} 
}