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

본 논문 의 사례 는 C 언어 가 페이지 교체 알고리즘 을 실현 하 는 구체 적 인 코드 를 공유 하여 여러분 께 참고 하 시기 바 랍 니 다.구체 적 인 내용 은 다음 과 같 습 니 다.
운영 체제 실험
페이지 교체 알고리즘(FIFO,LRU,OPT)
개념:
1.최 적 치환 알고리즘(OPT)(이상 치환 알고리즘):메 인 저장 소 에서 영원히 필요 하지 않 은 페이지 를 이동 합 니 다.만약 이러한 페이지 가 존재 하지 않 는 다 면,가장 오랫동안 접근 할 필요 가 없 는 페이지 를 선택 하 십시오.선택 한 탈락 페이지 는 앞으로 영원히 사용 되 지 않 거나 가장 오 랜 시간 동안 방문 되 지 않 는 페이지 로 가장 낮은 결 장 률 을 확보 할 수 있 습 니 다.
2.먼저 교체 알고리즘(FIFO):가장 간단 한 페이지 교체 알고리즘 입 니 다.이러한 알고리즘 의 기본 사상 은 한 페이지 를 도태 시 켜 야 할 때 메 인 저장 시간 이 가장 긴 페이지 를 선택 하여 도태 시 키 는 것 이다.즉,메 인 저장 페이지 에 먼저 들 어가 서 먼저 도태 시 키 는 것 이다.그 이 유 는 메 인 저장 소 에 최초 로 들 어 온 페이지 가 더 이상 사용 되 지 않 을 가능성 이 가장 크다 는 것 이다.
3.최근 가장 오랫동안 사용 되 지 않 은(LRU)알고리즘:이러한 알고리즘 의 기본 사상 은 국 지적 원 리 를 이용 하여 하나의 작업 이 수행 되 는 과정 에서 과거의 페이지 방문 역사 에 따라 미래의 행 위 를 추측 하 는 것 이다.지난 한 동안 방문 되 지 않 았 던 페이지 는 최근 에 도 다 시 는 방문 되 지 않 을 것 이 라 고 생각 합 니 다.따라서 이러한 알고리즘 은 실질 적 으로 한 페이지 를 탈락 시 켜 야 할 때 가장 오래 사용 하지 않 는 페이지 를 선택 하여 탈락 시 키 는 것 이다.
제목:
이 장 에서 말 한 FIFO,LRU,최 적 화 된 페이지 교체 알고리즘 을 실현 하 는 프로그램 을 만 듭 니 다.우선,랜 덤 페이지 참조 문자열 을 생 성 합 니 다.그 중에서 페이지 범 위 는 0-9 입 니 다.이 랜 덤 페이지 참조 문자열 을 모든 알고리즘 에 적용 하고 모든 알고리즘 으로 인 한 페이지 오류 의 수량 을 기록 합 니 다.교체 알고리즘 을 실현 하고 한 페이지 프레임 의 수량 은 1~7 입 니 다.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int numbers[20]={7,0,1,2,
   0,3,0,4,
   2,3,0,3,
   2,1,2,0,
   1,7,0,1};//    ，     ，    
int nums=0;//      ，      ，
int stack[20][7]={10};

void begin();
void randomnum();//       
void init();//   
void FIFO();//FIFO  
void LRU();//LRU  
void OPT();//        （OPT）
void print();//  

int main() {
 begin();
 FIFO();
 LRU();
 OPT();
 return 0;
}
void begin()//      
{
 int i,j,k;
 printf("         (1-7)：");
 scanf("%d",&nums);
 for(k=0;;k++)
 {
 printf("            （0： ，1： ）");
 scanf("%d",&j);
 if(j==0)
 {
  randomnum();
  break;
 }
 else if(j==1)
 {
  break;
 }
 else
 {
  printf("        ！
");
 }
 }

 printf("      ：
");
 for(i=0;i<20;i++)
 {
 printf("%d ",numbers[i]);
 }
 printf("
");
 init();
}
void randomnum()//              ，     
{
 srand(time(0));//      
 for(int i = 0; i < 20; i++) {
 numbers[i] = rand() % 10;//    0`9        
 }
}
void init()//             ，           
{
 int i,j;
 for(i=0;i<20;i++)
 for(j=0;j<nums;j++)
  stack[i][j]=10;
}

void print()//           
{
 int i,j;
 for(i=0;i<nums;i++)
 {
 for(j=0;j<20;j++)
 {
  if(stack[j][i]==10)
  printf("* ");
  else
  printf("%d ",stack[j][i]);
 }
 printf("
");
 }

}

void FIFO()//FIFO  
{
 init();
 int i,j=1,n=20,k,f,m;
 stack[0][0]=numbers[0];

 for(i=1;i<20;i++)
 {
 f=0;
 for(m=0;m<nums;m++)
 {
  stack[i][m]=stack[i-1][m];
 }
 for(k=0;k<nums;k++)
 {
  if(stack[i][k]==numbers[i])
  {
  n--;
  f=1;
  break;
  }
 }
 if(f==0)
 {
  stack[i][j]=numbers[i];
  j++;
 }
 if(j==nums)
  j=0;
 }
 printf("
");
 printf("FIFO  ：
");
 print();
 printf("       ：%d
",n);
}

void LRU()//LRU  
{
 int i,j,m,k,sum=1;
 int sequence[7]={0};//    
 init();
 stack[0][0]=numbers[0];
 sequence[0]=nums-1;
 for(i=1;i<nums;i++)//    ，       
 {
 for(j=0;j<nums;j++)
 {
  stack[i][j]=stack[i-1][j];
 }
 for(j=0;j<nums;j++)
 {
  if(sequence[j]==0)
  {
  stack[i][j]=numbers[i];
  break;
  }
 }
 for(j=0;j<i;j++)//           1
 {
  sequence[j]--;
 }
 sequence[i]=nums-1;//            
 sum++;
 }
 for(i=nums;i<20;i++)//    ，       
 {
 int f;
 f=0;
 for(j=0;j<nums;j++)
 {
  stack[i][j]=stack[i-1][j];
 }
 for(j=0;j<nums;j++)//         ，       
 {
  if(stack[i][j]==numbers[i])
  {
  f=1;
  k=j;
  break;
  }
 }
 if(f==0)//        ，   
 {
  for(j=0;j<nums;j++)//       0 
  {
  if(sequence[j]==0)
  {
   m=j;
   break;
  }
  }
  for(j=0;j<nums;j++)
  {
  sequence[j]--;
  }
  sequence[m]=nums-1;
  stack[i][m]=numbers[i];
  sum++;
 }
 else//       ，     
 {
  if(sequence[k]==0)//           
  {
  for(j=0;j<nums;j++)
  {
   sequence[j]--;
  }
  sequence[k]=nums-1;
  }
  else if(sequence[k]==nums-1)//           
  {
  //    
  }
  else//           
  {
  for(j=0;j<nums;j++)
  {
   if(sequence[k]<sequence[j])
   {
   sequence[j]--;
   }
  }
  sequence[k]=nums-1;
  }
 }
 }
 printf("
");
 printf("LRU  ：
");
 print();
 printf("       ：%d
",sum);
}

void OPT()//OPT  
{
 int i,j,k,sum=1,f,q,max;
 int seq[7]={0};//    
 init();
 stack[0][0]=numbers[0];
 seq[0]=nums-1;
 for(i=1;i<nums;i++)//    ，       
 {
 for(j=0;j<nums;j++)
 {
  stack[i][j]=stack[i-1][j];
 }
 for(j=0;j<nums;j++)
 {
  if(seq[j]==0)
  {
  stack[i][j]=numbers[i];
  break;
  }
 }
 for(j=0;j<i;j++)//           1
 {
  seq[j]--;
 }
 seq[i]=nums-1;//            
 sum++;
 }
 for(i=nums;i<20;i++)//    ，            
 {
 //k=nums-1;//         
 for(j=0;j<nums;j++)//                  
 {
  stack[i][j]=stack[i-1][j];
 }
 for(j=0;j<nums;j++)
 {
  f=0;
  if(stack[i][j]==numbers[i])
  {
  f=1;
  break;
  }
 }
 if(f==0)//     ，       
 {
  for(q=0;q<nums;q++)//                ，               
  {
  seq[q]=20;
  }
  for(j=0;j<nums;j++)//       
  {
  for(q=i+1;q<20;q++)
  {
   if(stack[i][j]==numbers[q])
   {
   seq[j]=q-i;
   break;
   }
  }
  }
  max=seq[0];
  k=0;
  for(q=0;q<nums;q++)
  {
  if(seq[q]>max)
  {
   max=seq[q];
   k=q;
  }
  }
  stack[i][k]=numbers[i];
  sum++;
 }
 else
 {
  //            ，    ，            
 }
 }
 printf("
");
 printf("OPT  ：
");
 print();
 printf("       ：%d
",sum);
}

실행 결과 캡 처:



이 코드 는 Liux 에서 달 릴 수 있 으 니 windows 에서 도 틀림없이 문제 가 없 을 것 이다.
이상 이 바로 본 고의 모든 내용 입 니 다.여러분 의 학습 에 도움 이 되 고 저 희 를 많이 응원 해 주 셨 으 면 좋 겠 습 니 다.