new_diaodu.cpp

操作系统中作业调度程序

#include  <iostream.h>
#include  <fstream.h>
#include  <iomanip.h>
#include  <stdlib.h>
#include  <string.h>

typedef  struct  job   //job information PCB    
{
    double	arrive_time, excute_time,start_time,finish_time;
	struct  job  *next;
}JOB;

struct t_w     // 周转时间t 与带权周转时间w
{
	double  t;
	double  w;
};

void  Insert_by_arrive_time(JOB *&L,JOB *&m)  //jobs will sorted by its arrive time
{
	JOB  *r = L;
	while(r->next)
	{
	   if(m->arrive_time >= r->next->arrive_time )
		   r = r->next ;
	   else
		   break;
	}
	if(!(r->next))
	{
	   r->next = m;
	}
	else
	{
	   m->next = r->next;  //pay attention there
	   r->next = m;
	}
}

bool  Input_the_Jobs_by_Console(JOB *&L,int  &job_num)   //read the jobs information from the Console
{

   JOB  *r = L;
   cout<<"Input:"<<endl;
   
   while(1)
   {
       JOB  *s = new JOB;
	   if(!s)
	   {
		   cout<<"Memory apply failed!"<<endl;
		   exit(-1);
	   }
	   
	   cin>>s->arrive_time ;
	   
	   if(s->arrive_time < 0.0)
	   {
	       delete s;
		   break;
	   }
	   
	   cin>>s->excute_time;
	   
	   s->next = NULL;
       Insert_by_arrive_time(L,s);
	   ++job_num ;
   }

   if(L->next)
   {   
		JOB  *p,*q;   
		p = L->next;
		
        
        p->start_time = p->arrive_time;
		p->finish_time = p->start_time + p->excute_time;

		q = p->next;  //pointer p is the prior pointer of q

		while(q)   
		{
			if(q->start_time <= p->finish_time)
				q->start_time = p->finish_time;
			else
				q->start_time = q->arrive_time;
            q->finish_time = q->start_time + q->excute_time;

			p = p->next;
			q = q->next;
		}
		
		return  true;
   }
   else
		return  false;
}

bool  Input_the_Jobs_by_file(JOB *&L,int &job_num)  //read the job information from the file
{
	ifstream  tfile("input.txt"); //打开一个已经存在的文本文档(创建一个ifstream流对象)
	if(!tfile)
	{ 
		cerr<<"Can't open the file of input.txt!!"<<endl;
		exit(1);
	}

	while(1)   
	{
	    //if(tfile.eof())
	  	//	break;
		JOB  *s = new JOB;
		if(!s)
		{
			cout<<"Memory apply failed!"<<endl;
			exit(-1);
		}
		
		tfile>>s->arrive_time>>s->excute_time;
		if(tfile.eof())  //pay attention there. if we don't do that, the file will
		{				// read one more data which will do harm to the system
			delete  s;
			break;
		}
		
		s->next = NULL;
		Insert_by_arrive_time(L,s);
		++job_num;
	}
    
	if(L->next)
	{  
	    JOB  *p,*q;   
		p = L->next;
		
        
        p->start_time = p->arrive_time;
		p->finish_time = p->start_time + p->excute_time;

		q = p->next;  //pointer p is the prior pointer of q

		while(q)   
		{
			if(q->start_time <= p->finish_time)
				q->start_time = p->finish_time;
			else
				q->start_time = q->arrive_time;
                q->finish_time = q->start_time + q->excute_time;

			p = p->next;
			q = q->next;
		}

		tfile.close();
		return  true;
	}
	else
	{
		tfile.close();
		return  false;
	}
}

void  Short_job_first(JOB  *&L,JOB *&Short) //we will use short job first 
{
    JOB  *w = Short;        // in this fuction, every time when I find the proper crunode,
							// I will connect it to the new List, with the head crunode of
    JOB  *r = L->next;     // Short. Then I will delete this crunode from the old list

	r->start_time = r->arrive_time;
	r->finish_time = r->start_time + r->excute_time;
    
	double finish_time = r->finish_time;

	w->next = r;
	w = r;

    L->next = r->next ;

	r = r->next;
    
	JOB   *flag;
       
	while(r)
	{
		double  min_excute_time = 99999999.99;
		
		flag = L;

		while(r)
		{
		   if(r->arrive_time <= finish_time)
		   {
				if(r->excute_time<min_excute_time)
				{
					flag = r;
					min_excute_time = r->excute_time;
				}
				r = r->next;
           }
		   else
			   break;
		}
		if(flag==L)
		{
			r = L->next;
            r->start_time = r->arrive_time;
			r->finish_time = r->start_time + r->excute_time;
            
			finish_time = r->finish_time ;

			
			w->next = r;
			w = w->next;

			L->next = L->next->next;
            
			r  =L->next;

			//t->next = r->next;
			//r = t->next;
			
			//t = r;
            //r = r->next;
		}
		else
		{
			JOB  *x = L;    //delete the pointer of flag from the job list
			while(x->next)        //I want to insert it into the list of short job first 
			{    
				if(x->next == flag)   //find the prior point of the pointer of flag
					break;
				x = x->next;
			}
            
			x->next->start_time = finish_time;
			x->next->finish_time = x->next->start_time + x->next->excute_time;
            
			finish_time = x->next->finish_time ;

			w->next = x->next;
			w = w->next;
            
			x->next = x->next->next;

	    	r = L->next;
			
			/*r = t->next;
			t = r;
			r = r->next;*/
		}
	}

	w->next = NULL;
}			




void  Rate_high_first(JOB  *&L,JOB *&Rate)  //in this function I have used the same 
{                                    //algorithm as void  Short_job_first(JOB  *&L,JOB *&Short)
	JOB  *v = Rate;   

    JOB  *r = L->next;

	r->start_time = r->arrive_time;
	r->finish_time = r->start_time + r->excute_time;
    
	double finish_time = r->finish_time;

	v->next = r;
	v = r;

    L->next = r->next ;

	r = r->next;
    
	JOB   *flag;
       
	while(r)
	{
		double  High_Rate = -100.00;   //init the small value 
		
		flag = L;

		while(r)
		{
		   if(r->arrive_time <= finish_time)
		   {    //maybe there is something wrong with the defination of wait_time
			    double  wait_time = finish_time - r->arrive_time;  
                double  xiang_ying = wait_time / r->excute_time;	
			    if(xiang_ying >= High_Rate)
				{
					flag = r;
				    High_Rate = xiang_ying; 	
				}
				r = r->next;
           }
		   else
		   {
			   
			   break;
		   }
		}
		if(flag==L)
		{
			r = L->next;
            L->next->start_time = L->next->arrive_time;
			L->next->finish_time = L->next->start_time + L->next->excute_time;
            
			finish_time = L->next->finish_time ;
      
	        		
			v->next = L->next;
			v = v->next;

			L->next = L->next->next;
            
			r  =L->next;

			//t->next = r->next;
			//r = t->next;
			
			//t = r;
            //r = r->next;
		}
		else
		{
			JOB  *x = L;    //delete the pointer of flag from the job list
			while(x->next)        //I vant to insert it into the list of short job first 
			{    
				if(x->next == flag)   //find the prior point of the pointer of flag
					break;
				x = x->next;
			}
            
			x->next->start_time = finish_time;
			x->next->finish_time = x->next->start_time + x->next->excute_time;
            
			finish_time = x->next->finish_time ;

			v->next = x->next;
			v = v->next;
            
			x->next = x->next->next;

	    	r = L->next;
			
			/*r = t->next;
			t = r;
			r = r->next;*/
		}
	}

	v->next = NULL;

}

struct  t_w   x[3];    

void  Cal_t_and_w(JOB  *q,int kind)  
{
	JOB  *r = q->next;
	
    while(r)
	{
		double  zhou_zhuan_time = r->finish_time - r->arrive_time;
        double  quan_zhou_zhuan_time  = zhou_zhuan_time/r->excute_time;
		x[kind].t +=  zhou_zhuan_time;
		x[kind].w +=  quan_zhou_zhuan_time;

		r = r->next;
	}
}

void  Copy(JOB *L,JOB *&New_L) //copy the list
{
	JOB  *r = L->next,*t = New_L;
	while(r)
	{
		JOB  *s = new JOB;
		if(!s)
		{
			cout<<"Memory apply failed!"<<endl;
			exit(-1);
		}

		s->arrive_time = r->arrive_time;
		s->excute_time = r->excute_time;
        
		s->next = NULL;
		t->next = s;
		t = s;

		r = r->next;
	}
}

int  Best()   //choose the best
{           
	t_w  min = x[0];
	int   m = 0;
	for(int i=1;i<3;++i)
	{
		if(x[i].t < min.t && x[i].w < min.w)  //maybe there is some errors in my algorithm
		{
			m = i;
			min = x[i];
		}
	}

	return m;
}

void  main()
{
   JOB  *L = new JOB;   //Produce the head node
   JOB  *Short = new JOB; 
   JOB  *Rate = new JOB;
   if(!L||!Short||!Rate)
   {
		cout<<"Memory apply failed"<<endl;
		exit(-1);
   }
   L->next = NULL;
   Short->next = NULL;
   Rate->next = NULL;

   int  job_num = 0;
   cout<<"请输入数据读入方式：1：控制台；2：文件 ";
   int  choose;
   cin>>choose;
   bool  kind;
   if(choose==1)
   {
     	   cout<<"with a negative number to finish your input."<<endl;
	   kind = Input_the_Jobs_by_Console(L,job_num);
   }
   else 
	   kind = Input_the_Jobs_by_file(L,job_num);
   if(!kind)   
   {
		cout<<"There isn't any jobs for insert!"<<endl;
		return;
   }
   
   
   //L = L->next;

   JOB  *Second_L = new JOB;  //Copy the list which was sorted by
   if(!Second_L)     //arrive_time, I will use it in the function of Short_job_first()     
   {
		cout<<"Memory apply failed"<<endl;
		exit(-1);
   }

   Second_L->next = NULL;
   Copy(L,Second_L);
   
   

   JOB  *third_L = new JOB; //Copy the list which was sorted by
   if(!third_L)  //arrive_time, I will use it in the function of Rate_high_first()
   {
		cout<<"Memory apply failed"<<endl;
		exit(-1);
   }
   third_L->next = NULL;
   Copy(L,third_L);
    
   for(int i=0;i<3;++i)
  	   x[i].t = x[i].w = 0.0;
    
   Cal_t_and_w(L,0);

   Short_job_first(Second_L,Short);
   
   Cal_t_and_w(Short,1);
   
   Rate_high_first(third_L,Rate);
   Cal_t_and_w(Rate,2);

   int m = Best();
   
   cout<<"最佳调度为：";
   
   JOB   *r;
   switch(m)
   {
   case 0: cout<<"先来先服务。"<<endl; r = L->next; break;
	   case 1: cout<<"短作业优先。"<<endl; r = Short->next; break;
		   case 2: cout<<"响应比优先。"<<endl; r = Rate->next; break;
		   default:  cout<<"调度算罚出错！"<<endl; return;
   }
   cout<<"提交时间"<<'\t'<<"执行时间"<<'\t'<<"开始时间"<<'\t'<<"完成时间"<<endl;
   while(r)
   {
		cout<<r->arrive_time <<'\t'<<'\t'<<r->excute_time <<'\t'<<'\t'<<r->start_time <<'\t'<<'\t'<<r->finish_time <<endl;	
		r = r->next;
   }
   cout<<endl;
   cout<<"平均周转时间为："<<x[m].t / job_num<<endl;
   cout<<"平均带权周转时间为："<<x[m].w / job_num<<endl;
}