dynamic.cpp

操作系统的动态分区存储管理模拟程序。程序将分区说明表分散为可用队列与已用队列

#include<iostream>
#include<string>
#include<iomanip>
#define null 0
using namespace std;
struct PCB{//进程信息块 
       string name;
       int Rtime;
       int size;
       };
struct MemoryTable{//存储区信息块 
       int num;//分区号 
       bool state;//分区状态 
       int size;//分区大小 
       int BePos;//分区起始位置 
       PCB *pcb;
       struct MemoryTable *next;
       struct MemoryTable *ahead;
       };
typedef MemoryTable MT;
MT *empty=null,*use=null;
bool F=false,T=false;
int n,Time=0;
void displayMT()//显示分区说明表 
{   MT *p,*q;
   cout<<"分区说明表：\n";
   cout<<"区号  分区长度  起始地址  状态    |进程  大小  完成时间\n";
   cout<<"__________________________________|____________________\n";
   p=use;q=empty;
   for(int i=1;i<=n;i++)
     {  
        if(p==null)        
           {cout<<right<<setw(4)<<q->num<<setw(9)<<q->size<<'k'<<setw(9)
          <<q->BePos<<'k'<<"  未分配  |"<<setw(4)<<"无"<<setw(5)
                <<0<<'k'<<setw(10)<<0<<endl;
                q=q->next;}
          else if(p->num==i)   {cout<<right<<setw(4)<<p->num<<setw(9)<<p->size<<'k'<<setw(9)
          <<p->BePos<<'k'<<"  已分配  |"<<setw(4)<<p->pcb->name<<setw(5)
                <<p->pcb->size<<'k'<<setw(10)<<p->pcb->Rtime<<endl;
                p=p->next;} 
        else      {cout<<right<<setw(4)<<q->num<<setw(9)<<q->size<<'k'<<setw(9)
          <<q->BePos<<'k'<<"  未分配  |"<<setw(4)<<"无"<<setw(5)
                <<0<<'k'<<setw(10)<<0<<endl;
                q=q->next;}
         
     }
     cout<<"\n";
     system("pause");
}
void createMT()//建立分区说明表 
{     
   n=1;empty=new MT;
   empty->num=1;
   empty->state=false;
   empty->BePos=20;
   empty->pcb=null;
   empty->next=null;
   empty->ahead=null;
   empty->size=1024;
   displayMT();
     
} 
 MT* refresh0(MT* s)
 {
    MT *p=use,*t;
    int x=s->num;
    s=s->next;
    while(s)
    {s->num+=1;
    s=s->next;
    }  
    n+=1;
    if(p==null) return p;
    while(p)
    {
      if(p->num>=x) break;
      t=p;
      p=p->next;
    }
    if(p==null) {F=true;return t;}
    t=p;
    while(t)
    {t->num+=1;
    t=t->next;
    }
    return p;
    
 }
void divid( PCB *r)
{
  MT *p=use,*q=empty;
  while(1){
           if(q==null) {cout<<"无足够内存分配此进程！";delete r ;return;}
           if(q->size==r->size){T=true;
                                if(q==empty){
                                           empty=empty->next;
                                           if(empty!=null)empty->ahead=null;
                                           q->state=true;q->pcb=r;
                                           break;
                                           }
                                else if(q->next==null){
                                               q->ahead->next=null;
                                               q->state=true;q->pcb=r;
                                               break;
                                                      }
                                else {q->ahead->next=q->next;
                                          q->next->ahead=q->ahead;
                                          q->state=true;q->pcb=r;
                                          break; 
                                      }
                                 }
           else if(q->size>r->size){if(q==empty){
                                                MT *s=new MT;
                                                s->size=q->size-r->size;
                                                s->num=q->num+1;
                                                s->BePos=q->BePos+r->size;
                                                s->state=false;
                                                s->pcb=null;
                                                s->next=q->next;
                                                if(s->next) s->next->ahead=s;
                                                s->ahead=null;
                                                empty=s;
                                                q->size=r->size;
                                                q->state=true;
                                                q->pcb=r;
                                                p=refresh0(s); 
                                               }
                                else if(q->next==null){
                                               MT *s=new MT;
                                               s->size=q->size-r->size;
                                               s->num=q->num+1;
                                               s->BePos=q->BePos+r->size;
                                               s->state=false;
                                               s->pcb=null;
                                               s->ahead=q->ahead;
                                               s->ahead->next=s;
                                               s->next=null;
                                               q->size=r->size;
                                               q->state=true;
                                               q->pcb=r;
                                               p=refresh0(s);                                               
                                }       
                                     else { 
                                              MT *s=new MT;
                                              s->size=q->size-r->size;
                                               s->num=q->num+1;
                                               s->BePos=q->BePos+r->size;
                                               s->state=false;
                                               s->pcb=null;
                                               s->ahead=q->ahead;
                                               s->ahead->next=s;
                                               s->next=q->next;
                                               s->next->ahead=s;
                                               q->size=r->size;
                                               q->state=true;
                                               q->pcb=r;
                                               p=refresh0(s);     
                                           } 
                                   break;
                              }
             q=q->next;
          }
   
   if(T==true&&p!=null) {
                        MT *t;
     while(1)
       {
       if(p->num>q->num) break;
       t=p;
       p=p->next;
       }
    if(p==null) {F=true;p= t;}
    T=false;
   }
   if(p==null) {q->next=null;q->ahead=null;use=q;} 
   else if(F==true){q->next=null;p->next=q;q->ahead=p;F=false;}
   else if(p->ahead==null){use=q;q->next=p;p->ahead=q;q->ahead=null;}
   else {p->ahead->next=q;q->next=p;q->ahead=p->ahead;p->ahead=q;}
   }

void input()
{ 
 cout<<"CPU时刻： "<<Time<<endl<<endl;
  cout<<"是否有进程请求？[Y/N]   ";
  char y;
  cin>>y;
  Time+=10;
  if(y=='N'||y=='n') return;
  else 
  {
   int x;
    cout<<"输入进程个数：";
    cin>>x;
    cout<<"输入各进程名、要求空间、完成时间：\n";
    for(int i=1;i<=x;i++)
    {
      PCB* r=new PCB;
      cin>>r->name;
      cin>>r->size;
      cin>>r->Rtime;
      divid(r);
    }
  }
 
  displayMT();
}
void refresh1(MT *q,MT *p)
{
     MT *t,*z=empty;
     if(z==null) {q->next=null;q->ahead=null;empty=q;return;}
     while(z)
     {
       if(z->num>q->num)break;
       t=z;
       z=z->next; 
     }
   if(z==null){t->next=q;q->next=null;q->ahead=t;
          if(q->num+1==t->num)
          {
             t->size+=q->size;t->next=null;
             delete q;
          while(p){p->num-=1;p=p->next;}
          n=n-1;
          }
   }
   else if(z->ahead==null){q->next=z;z->ahead=q;q->ahead=null;empty=q;
                           if(q->num==q->next->num-1) {q->size+=q->next->size;
                            q=q->next;
                            empty->next=empty->next->next;
                            if(q->next!=null) empty->next->ahead=empty;
                            delete q;
                            q=empty->next;
                            while(q)
                            {q->num-=1;q=q->next;}
                            while(p){p->num-=1;p=p->next;}
                             n=n-1;
                            }
   }
   else {q->next=z;q->ahead=z->ahead;z->ahead=q;q->ahead->next=q;
          if(q->num+1==q->next->num&&q->num-1==q->ahead->num)
          {
             t=q->ahead;t->size+=q->size;
             t->next=q->next;delete q;
             q=t->next;t->size+=q->size;
             t->next=q->next;delete q;
             if(t->next) t->next->ahead=t;
             q=t->next;
             while(q){q->num-=2;q=q->next;}
             while(p){p->num-=2;p=p->next;}
             n=n-2;
          }
     else if(q->num+1==q->next->num)
                     {t=q;q=q->next;t->size+=q->size;t->next=q->next;
                      delete q;if(t->next!=null) t->next->ahead=t;
                        q=t->next;
                        while(q){q->num-=1;q=q->next;}
                        while(p){p->num-=1;p=p->next;}              
                         n=n-1;
                      }
   else if(q->num-1==q->ahead->num)
                   {
                      t=q->ahead;t->size+=q->size;t->next=q->next;
                      q->next->ahead=t;delete q;
                      q=t->next;
                       while(q){q->num-=1;q=q->next;}
                       while(p){p->num-=1;p=p->next;}
                   n=n-1;
                   }
   }
   
}

 void reclaim()
 {
    MT *p=use,*q=null;
    int t=Time;
    while(p)
    {
      if(p->pcb->Rtime<=t) {t=p->pcb->Rtime;q=p;}
      p=p->next;
    }
  if(q==null) {input();return;}
  cout<<"CPU时刻："<<t<<"\n\n";
  cout<<"进程"<<q->pcb->name<<"执行结束\n";
  PCB *z=q->pcb;
  q->pcb=null;
  q->state=false;
  p=q->next;
  if(q==use) {use=q->next;if(use!=null)
                     use->ahead=null;
 }
 else if(q->next==null){
          q->ahead->next=null;
 }
 else{ q-> next->ahead=q->ahead;
       q->ahead->next=q->next;
 }
 delete z;
 refresh1(q,p);
 displayMT();
 }
 
 int main()
 {  createMT();
 do{
   reclaim();
   }while(use);
   return 0;
   
 }