hrn.cpp

操作系统作业调度HRN算法模拟程序。根据最高响应比优先算法调度作业进入内存运行

/*
程序采用HRN算法模拟作业运行，程序运行时先输入作业个数，并依次输入作业信息，
输入过程中作业信息顺序构成一个全局链表。运行时，先将第一个作业投入运行，运行结束
后根据HRN算法在运行结束时刻已提交的作业队列里选出最高响应比的作业投入运行
（注：在上个作业运行结束时刻还未到达的作业将不参与排序及竞争CPU） ，并将
余下的作业按最高优先比排序。作业运行结束调用释放函数计算其周转时间、带权周转时间
并显示出来，更新总周转时间、总带权周转时间 。所有作业运行完后将平均周转时间、平
均带权周转时间计算出来并显示。  
 
*/ 
#include<iostream>
#include<string>
using namespace std;
#define null 0
int Runtime=0;//CPU时刻跟踪变量 
float T_time=0;//总周转时间 
float W_time=0;//总带权周转时间
int marktime=0;//输入排队时运行标记时间 
int n;//作业个数 
typedef struct jcb{
string name;
int Ttime;
int Rtime;
int Sourse;
char State;
struct jcb *next;
}JCB;//作业信息块 
JCB *head=null,*p,*q;
void sort0(JCB *r)//作业排序递归子函数 
{
if(r->next->next==null) return;
  JCB *s,*d=r,*m=r->next;
  s=r;
  float x,y;
  x=float(Runtime-r->next->Ttime+r->next->Rtime)/(r->next->Rtime);
  
while(1)
{ if(s->next->next==null) break;
   s=s->next;
  y=float(Runtime-s->next->Ttime+s->next->Rtime)/(s->next->Rtime);
  
   if(y>x) {d=s;m=s->next;}
  
}
  d->next=m->next;
  m->next=null;
  m->next=r->next;
  r->next=m;
 sort0(m);
}
void sort()//作业排序函数 
{
 if(head==null||head->next==null) return ;
q=head;
while(1)
{if(q->next==null) break;
if(q->next->Ttime<=Runtime) q=q->next;
else break;
}
JCB *z;

    z=q;q=q->next;z->next=null;
    z=new JCB;
    z->next=head;
sort0(z);

head=z->next;
delete z;
z=head;
while(z->next)
{
  z=z->next;
}
z->next=q;
}

int randtime(int T,int R)//根据前一个作业到达时间及总完成时间产生当前作业到来的随机时间 
{
    return T+rand()%(R-T-1)+1;
}

void display(JCB *pr)//显示pr指针所指作业信息 
{
     float x=float(Runtime-pr->Ttime+pr->Rtime)/pr->Rtime;
     cout<<pr->name<<'\t'<<pr->State<<'\t'<<pr->Sourse<<'\t'<<pr->Ttime<<'\t'<<pr->Rtime<<'\t'<<x<<'\n';
}

void input()//输入函数 
{
     int T=0,R=0;
     cout<<"请输入作业个数：";
     cin>>n;
     for(int i=1;i<=n;i++)
     {
       p=new JCB; 
      cout<<"输入NO."<<i<<"作业名称：";
      cin>> p->name;
      cout<<"输入作业运行时间：";
      cin>>p->Rtime;
      cout<<"输入作业所需资源：";
      cin>>p->Sourse;
      p->State='W';
      if(i==1) p->Ttime=0;
      else p->Ttime=randtime(T,R);
      R+=p->Rtime;
      T=p->Ttime;
     if(i==1) {p->next=head;head=p;q=p;}
     else {p->next=q->next;
          q->next=p;q=p;}
      
     } 
      cout<<"\n\n输入完毕\n\n提出请求的作业队列为：\n";
    JCB *pr=head;
  cout<<"name\tstate\tSourse\tTtime\tRtime\n";
  while(pr)
  {
cout<<pr->name<<'\t'<<pr->State<<'\t'<<pr->Sourse<<'\t'<<pr->Ttime<<'\t'<<pr->Rtime<<'\n';
           pr=pr->next;
  }
 system("pause");  
 cout<<"\n\n开始运行！\n\n";
}

int getlen()//返回链表长度 
{
    int l=0;
    JCB *pr=head;
    
    while(pr)
    {
     l++;
     pr=pr->next;
    }
    return (l);
} 

void show()//显示当前CPU内作业运行状态 
{    cout<<"Runtime="<<Runtime<<endl<<endl;
     cout<<"\t正在运行的作业\n";
     cout<<"name\tState\tSourse\tTtime\tRtime\n";
     cout<<p->name<<'\t'<<p->State<<'\t'<<p->Sourse<<'\t'<<p->Ttime<<'\t'<<p->Rtime<<'\n';
     cout<<"\t等待的作业\n";
     JCB *pr=head;
     if(!pr) {cout<<"\t无就绪进程！\n";return ;}
    cout<<"name\tState\tSourse\tTtime\tRtime\t响应比\n";
     while(pr!=q)
     {
       display(pr);
       pr=pr->next;
     }
}

void destroy()//作业运行完毕，撤销并释放内存 
{  p->State='F';
  cout<<"作业运行完成\n" ;  
  cout<<"Ttime\tBegin\tDone\tZ_time\tW_time\n";
 cout<<p->Ttime<<'\t'<<Runtime-p->Rtime<<'\t'<<Runtime<<'\t'<<Runtime-p->Ttime
 <<'\t'<<(float)(Runtime-p->Ttime)/p->Rtime<<endl; 
 T_time+=(float)Runtime-p->Ttime;
 W_time+=(float)(Runtime-p->Ttime)/p->Rtime;
 system("pause");
  delete p;
}

void run()//模拟运行函数
{
     system("cls");
     p=head;
     head=p->next; 
     Runtime+=p->Rtime;
     sort();
     p->State='R';
     show();
     system("pause");
     system("cls");
     destroy();  
     
}
int main()//主函数 
{
    input();
    while(1)
    {
            run();
            if(!getlen())
            break;
    }
    system("cls");
    cout<<"所有作业都已完成后\n\n";
    cout<<"AVG_T_time\tAVG_W_time\n";
    cout<<T_time/n<<'\t'<<'\t'<<W_time/n<<endl;
    system("pause");    
}