sy4-z.c

操作系统五种置换算法 LRU OPT 等

# define TRUE 1
# define FALSE 0
# define INVALID -1
# define NULL 0

# define total_instruction 320
# define total_vp 32
# define clear_period 50

typedef struct {
    int pn,pfn,counter,time;
}pl_type;

pl_type pl[total_vp];

struct pfc_struct {
    int pn,pfn;
    struct pfc_struct *next;
};

typedef struct pfc_struct pfc_type;
pfc_type pfc[total_vp],*freepf_head,*busypf_head,*busypf_tail;

int diseffect,a[total_instruction];
int page[total_instruction],offset[total_instruction];

void initialize();
void FIFO();
void LRU();
void OPT();
void LFU();
void NUR();

main()
{
    int S,i,j;

    S=(float)319*rand()/32767+1;

    for (i=0;i<total_instruction;i+=4)
    {
        a[i]=S;
        a[i+1]=a[i]+1;
        a[i+2]=(float)a[i]*rand()/32767;
        a[i+3]=a[i+2]+1;
        S=(float)rand()*(318-a[i+2])/32767+a[i+2]+2;
    }

   for (i=0;i<total_instruction;i++)
   {
      page[i]=a[i]/10;
      offset[i]=a[i]%10;
   }

   for (i=4;i<=32;i++)
   {
      printf("%2d page frames ",i);
      FIFO(i);
      NUR(i);
      LFU(i);
      LRU(i);
      OPT(i);
      printf("\n");
   }

}

void FIFO(int total_pf)
{ int i;
  initialize(total_pf);
  busypf_head=freepf_head;
  for(i=0;i<total_instruction;i++)
  {  
     if (pl[page[i]].pfn==INVALID)
       { 
         diseffect++;
         if(freepf_head==NULL)
         { 
           pl[busypf_head->pn].pfn=INVALID;
           pl[page[i]].pfn=busypf_head->pfn;
           busypf_head->pn=page[i];
           busypf_head=busypf_head->next;
         }
         else
         {
           pl[page[i]].pfn=freepf_head->pfn;
           freepf_head->pn=page[i];
           if(freepf_head->next==NULL)
              { freepf_head->next=busypf_head;
                freepf_head=NULL;
              }
           else
              freepf_head=freepf_head->next;
         }
       }
  }
  printf("FIFO:%6.4f ",1-(float)diseffect/320);
}        

void NUR(int total_pf)
{ int i;
  initialize(total_pf);
  busypf_head=freepf_head;
  for(i=0;i<total_instruction;i++)
  {  
     if (pl[page[i]].pfn==INVALID)
     {   diseffect++;
         if(freepf_head==NULL)
         { while(busypf_head!=NULL)
           { if(pl[busypf_head->pn].pn==0)
             { pl[busypf_head->pn].pfn=INVALID;
               busypf_head->pn=page[i];
               pl[page[i]].pn=0;
               pl[page[i]].pfn=busypf_head->pfn;
               busypf_head=busypf_head->next;
               break;
             }
             else
             { pl[busypf_head->pn].pn=0;
               busypf_head=busypf_head->next;
             }
           }
         }
        else
        { pl[page[i]].pfn=freepf_head->pfn;
          pl[page[i]].pn=0;
          freepf_head->pn=page[i];
          if(freepf_head->next==NULL)
          { freepf_head->next=busypf_head;
            freepf_head=NULL;
          }
          else
         freepf_head=freepf_head->next;
        }
     }
     else
       pl[page[i]].pn=1;
  }
  printf("NUR:%6.4f ",1-(float)diseffect/320);
}  


void LFU( int total_pf)
{ 
    int i,min;
    pfc_type *p;
    initialize(total_pf);
    busypf_head=NULL;
    busypf_head=freepf_head;
    for (i=0;i<total_instruction;i++)
    {
       if (pl[page[i]].pfn==INVALID)
       {  
          p=freepf_head;
          diseffect++;
          if(freepf_head==NULL)
          { p=busypf_head;
            min=pl[busypf_head->pn].counter;
            freepf_head=busypf_head->next;
            while(freepf_head!=NULL)
            { if(pl[freepf_head->pn].counter<min)
                 { min=pl[freepf_head->pn].counter;
                   p=freepf_head;
                 }
              freepf_head=freepf_head->next;
            }
            pl[p->pn].pfn=INVALID;
            pl[p->pn].counter=0;
          }
          pl[page[i]].pfn=p->pfn;
          pl[page[i]].counter++;
          p->pn=page[i];
          if(freepf_head!=NULL)
             freepf_head=freepf_head->next;
       }
       else
        pl[page[i]].counter++;
    }
    printf("LFU:%6.4f ",1-(float)diseffect/320);
}

void LRU(int total_pf)
{ int i,max;
  pfc_type *p;
  initialize(total_pf);
  busypf_head=freepf_head;
  for(i=0;i<total_instruction;i++)
  {  
     if (pl[page[i]].pfn==INVALID)
       { 
         diseffect++;
         if(freepf_head==NULL)
         { 
           p=busypf_head;
           max=++pl[busypf_head->pn].time;
           freepf_head=busypf_head->next;
           while(freepf_head!=NULL)
           { pl[freepf_head->pn].time++;
             if(pl[freepf_head->pn].time>max)
              {  p=freepf_head;
                 max=pl[freepf_head->pn].time;
              }
             freepf_head=freepf_head->next;
           }
           pl[p->pn].pfn=INVALID;
           pl[p->pn].time=-1;
           p->pn=page[i];
           pl[page[i]].time=0;
           pl[page[i]].pfn=p->pfn;
         }
        else
        {
          p=busypf_head;
          while(p!=busypf_head)
          {
           pl[p->pn].time++;
           p=p->next;
          }
          freepf_head->pn=page[i];
          pl[page[i]].pfn=freepf_head->pfn;
          pl[page[i]].time=0;
          freepf_head->pn=page[i];
          freepf_head=freepf_head->next;
        }
     }
   else
     pl[page[i]].time=0;
  }
  printf("LRU:%6.4f ",1-(float)diseffect/320);
}

void OPT(int total_pf)
{ int i,j,k,maxdistance;
  pfc_type *p;
  initialize(total_pf);
  busypf_head=freepf_head;
  for(i=0;i<total_instruction;i++)
  {  
     if (pl[page[i]].pfn==INVALID)
       { 
         diseffect++;
         if(freepf_head==NULL)
         { p=busypf_head;
           maxdistance=pl[busypf_head->pn].pn;
           freepf_head=busypf_head->next;
           while(freepf_head!=NULL)
           { 
             if(pl[freepf_head->pn].pn>maxdistance)
               { 
                 maxdistance=pl[freepf_head->pn].pn;
                 p=freepf_head;
               }
             freepf_head=freepf_head->next;
           }
           pl[p->pn].pfn=INVALID;
           p->pn=page[i];
           pl[page[i]].pfn=p->pfn;
           for(j=i+1;j<total_instruction;j++)
               if(page[j]==page[i])
                  break;
           if(j==total_instruction&&page[j-1]!=page[i])
             pl[page[i]].pn=total_instruction;
           else  
             pl[page[i]].pn=j-i+1;
         }
         else
         {
           pl[page[i]].pfn=freepf_head->pfn;
           freepf_head->pn=page[i];
           if(freepf_head->next==NULL)
             {
              p=busypf_head;
              while(p!=NULL)
              { 
                for(j=i+1;j<total_instruction;j++)
                if(page[j]==p->pn)
                     break;
                if(j==total_instruction&&page[j-1]!=page[i])
                   pl[p->pn].pn=total_instruction;
                else  
                   pl[p->pn].pn=j-i+1;
                p=p->next;
              }
             }
          freepf_head=freepf_head->next;
        }
       }
     else
     {
        if(freepf_head==NULL)
         { for(j=i+1;j<total_instruction;j++)
               if(page[j]==page[i])
                  break;
           if(j==total_instruction&&page[j-1]!=page[i])
             pl[page[i]].pn=total_instruction;
           else  
             pl[page[i]].pn=j-i+1;
         }
    }
    if(busypf_head==NULL)
     { p=busypf_head;
       while(p!=NULL)
       { 
         pl[p->pn].pn--;
         p=p->next;
       }
     }
  }
  printf("OPT:%6.4f",1-(float)diseffect/320); 
}

void initialize(int total_pf)
{
     int i;
     diseffect=0;
     for (i=0;i<total_vp;i++)
     {
         pl[i].pn=i;
         pl[i].pfn=INVALID;
         pl[i].counter=0;
         pl[i].time=-1;
     }
     for (i=1;i<total_pf;i++)
     {
         pfc[i-1].next=&pfc[i];
         pfc[i-1].pfn=i-1;
     }
     pfc[total_pf-1].next=NULL;
     pfc[total_pf-1].pfn=total_pf-1;
     freepf_head=&pfc[0];
}