Linux 페이지 교체 알고리즘 C 언어 구현

Linux 페이지 교체 알고리즘 C 언어 구현
알고리즘 을 작성 하여 페이지 변환 알고리즘 FIFO,LRU,OPT 를 실현 합 니 다.메모리 주소 참조 문자열 에 대해 페이지 변환 알고리즘 을 사용 하여 페이지 변환 을 진행 합 니 다.
그 중에서 알고리즘 에 필요 한 각종 매개 변 수 는 입력 에 의 해 생 성 된다(수 동 입력 또는 난수 생 성).출력 메모리 가 상주 하 는 페이지 집합,페이지 부족 횟수 및 페이지 부족 율.

#include <stdio.h>
//#include <conio.h>
#include <stdlib.h>
#include <time.h>//   
 
#define Myprintf printf("|---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---|
")  //*    */

int M; 
int N; 

typedef struct page 
{ 
 int num; /*     */ 
 int time;  /*        */    //（lru   ）
 int index; //             // 1  （FIFO   ）
}Page;          /*       ，           */ 
Page b[10];      /*     */ // 0  

int c[10][150];  /*          ：   */ 
int queue[100];    /*      */ 
int K;       /*        */ 


/*       、   */ 
void Init(Page *b,int c[10][150]) 
{ 
 int i,j; 
 for(i=0;i<M;i++) 
 { 
 b[i].num=-1; 
 b[i].time=M-i-1; 
 b[i].index=i+1;
 } 
 for(i=0;i<M;i++) 
 for(j=0;j<N;j++) 
  c[i][j]=-1; 
} 

/*             ,             */ 
int GetMaxTime(Page *b) 
{
 int i;
 int max=-1; 
 int tag=0; 
 for(i=0;i<M;i++) 
 { 
 if(b[i].time>max) 
 { 
  max=b[i].time; 
  tag=i; 
 } 
 } 
 return tag; 
} 

/**int GetMinTime(Page *b) 
{
 int i;
 int min=1000; 
 int tag=0; 
 for(i=0;i<M;i++) 
 { 
 if(b[i].time<min) 
 { 
  min=b[i].time; 
  tag=i; 
 } 
 } 
 return tag; 
} **/

/*           */ 
int  Equation(int fold,Page *b) 
{ 
 int i; 
 for(i=0;i<M;i++) 
 { 
 if (fold==b[i].num) 
  return i; 
 } 
 return -1; 
} 

//LRU                  
void Lru(int fold,Page *b) 
{ 
 int i; 
 int val; 
 val=Equation(fold,b);  //           ，val         
 if (val>=0)    //    
 { 
 b[val].time=0;  //             0
 for(i=0;i<M;i++) 
  if (i!=val) 
  b[i].time++; //          
 } 
 else 
 { 
 queue[++K]=fold;/*      */ 
 val=GetMaxTime(b);  //             ,             ，val         
 b[val].num=fold; 
 b[val].time=0; 
 for(i=0;i<M;i++) 
  if (i!=val) 
  b[i].time++; 
 } 
} 

//FIFO               
void FIFO(int fold,Page *b)
{
 int i; 
 int val; 
 bool flag=false;
 val=Equation(fold,b);  //           ，val         

 if (val<0)    //      
 {
 queue[++K]=fold;/*      */
 for(i=0;i<M;i++)
 {
  if (b[i].num<0)//    
  {
  b[i].num=fold;
  b[i].index=i+1;
  flag=true;
  break;
  }
 }
 if (flag==false)//                 
 {
  for(i=0;i<M;i++) 
  { 
  if(b[i].index==1) 
  { 
   val=i; 
  } 
  } 
  b[val].num=fold; 
  b[val].index=M; 
  for(i=0;i<M;i++) 
  {
  if(i!=val) 
     b[i].index--; //         ，     Index     
  }
 }
 } 
}

//Optimal             
void Optimal(int a[150],int pos,Page *b)
{
 int i,j; 
 int val;
 int fold=a[pos];
 bool flag=false;

 val=Equation(fold,b);  //           ，val         
 
 if (val<0)    //      
 {
 queue[++K]=fold;/*      */
 for(i=0;i<M;i++)
 {
  if (b[i].num<0)
  {
  b[i].num=fold;
  flag=true;
  break;
  }
 }
 if (flag==false)
 {
  for(i=0;i<M;i++) 
  { 
  for(j=pos+1;j<N;j++)
  {
   if (b[i].num!=a[j])
   { b[i].time= 1000; }//                  1000
   else
   {
   b[i].time=j;//     j
   break;
   }
  }
  } 
  val=GetMaxTime(b);  //             ,             ，val         
  b[val].num=fold; 
 }
 } 
}

void LruMain(int a[150]) 
{ 
 int i,j; 
 K=-1; 
 Init(b, c); 
 for(i=0;i<N;i++) //
 { 
 Lru(a[i],b); 
 c[0][i]=a[i]; 
 /*             */ 
 for(j=0;j<M;j++) 
  c[j][i]=b[j].num; 
 } 

 /*    */ 
 printf("
     ：
"); 
 Myprintf; 
 for(j=0;j<N;j++) 
 printf("|%2d ",a[j]); 
 printf("|
");
 
 Myprintf; //#define Myprintf printf("|---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---|
")  //*    */ 
 for(i=0;i<N;i++) 
 {  
 for(j=0;j<M;j++) 
 { 
  if(c[j][i]==-1) 
  printf("%3c ",32); 
  else 
  printf("%3d ",c[j][i]); 
 } 
 printf("
"); 
 } 

 Myprintf; 
 printf("
     :"); 
 for(i=0;i<K+1;i++) 
 printf("%3d",queue[i]); 
 printf("
     ：%6d
   ：%16.6f",K+1,(float)(K+1)/N); 
}

void FIFOMain(int a[150]) 
{ 
 int i,j; 
 K=-1; 
 Init(b, c); 
 for(i=0;i<N;i++) //
 { 
 FIFO(a[i],b); 
 c[0][i]=a[i]; 
 /*             */ 
 for(j=0;j<M;j++) 
  c[j][i]=b[j].num; 
 } 
 /*    */ 
 printf("
     ：
"); 
 Myprintf; 
 for(j=0;j<N;j++) 
 printf("|%2d ",a[j]); 
 printf("|
");
 
 Myprintf; //#define Myprintf printf("|---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---|
")  //*    */ 
 for(i=0;i<N;i++) 
 {  
 for(j=0;j<M;j++) 
 { 
  if(c[j][i]==-1) 
  printf("%3c ",32);//   
  else 
  printf("%3d ",c[j][i]); 
 } 
 printf("
"); 
 } 
 
 Myprintf; 
 printf("
     :"); 
 for(i=0;i<K+1;i++) 
 printf("%3d",queue[i]); 
 printf("
     ：%6d
   ：%16.6f",K+1,(float)(K+1)/N); 
}

void OptimalMain(int a[150]) 
{ 
 int i,j; 
 K=-1; 
 Init(b, c); 
 for(i=0;i<N;i++) //
 { 
 Optimal(a,i,b); 
 c[0][i]=a[i]; 
 /*             */ 
 for(j=0;j<M;j++) 
  c[j][i]=b[j].num; 
 } 
 /*    */ 
 printf("
     ：
"); 
 Myprintf; 
 for(j=0;j<N;j++) 
 printf("|%2d ",a[j]); 
 printf("|
");
 
 Myprintf; //#define Myprintf printf("|---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---|
")  //*    */ 
 for(i=0;i<N;i++) 
 {  
 for(j=0;j<M;j++) 
 { 
  if(c[j][i]==-1) 
  printf("%3c ",32); 
  else 
  printf("%3d ",c[j][i]); 
 } 
 printf("
"); 
 } 
 
 Myprintf; 
 printf("
     :"); 
 for(i=0;i<K+1;i++) 
 printf("%3d",queue[i]); 
 printf("
     ：%6d
   ：%16.6f",K+1,(float)(K+1)/N); 
}

void main()
{
 int a[150];
 int i;
 char s;
 
 printf("       ：");
 scanf("%d",&M);

 printf("           ：");
 scanf("%d",&N);
 srand(time(NULL));
 for(i=0;i<N;i++)
 {
 a[i]=rand()%10;   /*           */
 }
 printf("           ：");
 for(i=0;i<N;i++)
 printf("%d ",a[i]);
 
 printf("
");
 printf("        ：
");
 while(1)
  {
 printf("

///");
 printf("
Please select 1:FIFO  
        2:LRU  
        3:Optimal  
        4:  
");
 scanf("%s",&s);
 switch(s)
 {
    case '1':FIFOMain(a);break;
    case '2':LruMain(a); break;
  case '3':OptimalMain(a); break;
    case '4':exit(0); break;
 }
 }
}

이상 이 바로 본 고의 모든 내용 입 니 다.여러분 의 학습 에 도움 이 되 고 저 희 를 많이 응원 해 주 셨 으 면 좋 겠 습 니 다.