C 언어 구현 페이지 교체 선진 알고리즘(FIFO)

본 논문 의 사례 는 C 언어 가 페이지 교체 알고리즘 을 실현 하 는 구체 적 인 코드 를 공유 하여 여러분 께 참고 하 시기 바 랍 니 다.구체 적 인 내용 은 다음 과 같 습 니 다.
1.디자인 목적   
요청 페이지 식 저장 관리 실현 원리 에 대한 이 해 를 강화 하고 페이지 교체 알고리즘 중의 선진 적 인 선 출 알고리즘 을 파악 합 니 다.
2.디자인 내용
가상 저장 소 와 메모리 작업 공간 이 있 는 프로그램 을 설계 하여 다음 세 가지 알고리즘 중 임의의 두 가 지 를 실현 하고 방문 명중률(명중률=1-페이지 실효 횟수/페이지 주소 흐름 길이)을 계산 합 니 다.추가 요구:페이지 교체 과정 을 표시 할 수 있 습 니 다.
이 시스템 페이지 의 주소 흐름 길 이 는 320 이 고 페이지 의 실효 횟수 는 해당 명령 에 접근 할 때마다 해당 페이지 가 메모리 에 없 는 횟수 입 니 다.   
프로그램 은 먼저 srand()와 rand()함수 로 각각 초기 화,난수 정의 와 명령 서열 을 만 든 다음 에 명령 서열 을 해당 하 는 페이지 주소 흐름 으로 바 꾸 고 서로 다른 알고리즘 에 대해 해당 하 는 명중률 을 계산한다.
무 작위 수 를 통 해 명령 시퀀스 를 생 성 합 니 다.총 320 개의 명령,명령 의 주 소 는 다음 과 같은 원칙 에 따라 생 성 됩 니 다.
(1)50%의 명령 은 순서대로 집행 된다.
(2)25%의 명령 은 앞 주소 부분 에 골 고루 분포 한다.
(3)25%의 지령 은 뒷 주소 부분 에 고 르 게 분포 한다.
구체 적 인 실시 방법 은 다음 과 같다.
[0,319]의 명령 주소 사이 에서 랜 덤 으로 출발점 m 를 선택 합 니 다.
주 소 를 m+1 로 실행 하 는 명령 을 순서대로 실행 합 니 다.
이전 주소[0,m+1]에서 무 작위 로 명령 을 선택 하고 실행 합 니 다.이 명령 의 주 소 는 m 입 니 다.
순서대로 명령 을 실행 합 니 다.주 소 는 m'+1 입 니 다.
뒤쪽 주소[m'+2,319]에서 무 작위 로 명령 을 선택 하여 실행 합 니 다.
명령 320 회 까지 절차(1)-(5)를 반복 합 니 다.
명령 시퀀스 를 페이지 주소 흐름 으로 변환 합 니 다.
설정:
페이지 크기 는 1KB 입 니 다.
사용자 의 메모리 용량 은 4 페이지 에서 32 페이지 이다.
사용자 가상 저장 용량 은 32KB 다.
사용자 가 가상 으로 저장 할 때 K 당 10 개의 명령 어 를 가상 으로 저장 합 니 다.즉,320 개의 명령 어 를 가상 으로 저장 하 는 방식 은 다음 과 같 습 니 다.
0 조~9 조 명령 은 0 페이지(가상 저장 주 소 는[0,9])이다.
제10 조~19 조 명령 은 1 페이지(가상 저장 주 소 는[10,19])이다.
……
제3 10 조～319 조 명령 은 31 페이지(대응 하 는 가상 주 소 는[310,319])이다.
이상 의 방식 에 따라 사용자 명령 은 32 페이지 를 구성 할 수 있다.
각 알고리즘 이 서로 다른 메모리 용량 에서 의 명중률 을 계산 하 다.
3.절차 구조
우선,srand()와 rand()함수 로 각각 초기 화,난수 정의 와 명령 시퀀스 생 성 을 진행 합 니 다.
이어서 지령 서열 을 상응하는 페이지 주소 흐름 으로 변환 한다.
그 다음 에 먼저 알고리즘 을 만들어 해당 하 는 명중률 과 출력 페이지 의 교체 과정 을 계산한다.
원본 프로그램:

#include<stdio.h>
#include<stdlib.h>
#define N 320
int num[N]; //      
int page[N]; //       
int mc[33]; //memory capacity     ，     0 
 
void randomnumber()//random number         ，  320      
{ 
 int pc;
 int flag=0; 
 scanf("%d",&pc); 
 printf("
 0-319     320      :
"); 
 for(int i=0;i<320;i++) 
 { 
 num[i]=pc; 
 if(flag%2==0) pc=++pc%320; //flag=0||2 50%          
 if(flag==1) pc=rand()% (pc-1); //flag=1 25%               
 if(flag==3) pc=pc+1+(rand()%(320-(pc+1))); //flag=3 25%               
 flag=++flag%4; 
 printf("%3d ",num[i]); 
 if((i+1)%10==0) printf("
"); //    10   
 } 
} 
 
void pageaddress() //pageaddress         ，             
{ 
 for(int i=0;i<320;i++) 
 { 
 printf("%3d ",page[i]=num[i]/10); 
 if((i+1)%10==0) printf("
"); //    10   
 } 
}
 
int FIFO(int capacity)
{
 int j,x,y,m;
 int sum=0; //mc       
 int exist=0; //     
 int flag; //       flag=0    flag=1   
 int ep=1; //elimination position     
 mc[1]=page[0];
 printf(" %2d   \t",page[0]);
 for(m=1;m<=capacity;m++) //             
 printf("%2d ",mc[m]);
 printf("
");
 sum+=1; 
 for(j=1;j<320;j++)
 { 
 flag=0; 
 for(y=1;y<=sum;y++) //             
 if(mc[y]==page[j]) {
 exist++;
 flag=1;
 printf(" %2d   \t",page[j]);
 for(m=1;m<=capacity;m++) //             
 printf("%2d ",mc[m]);
 printf("
");
 break;} 
 //    
 if(flag==0) 
 {
 if(sum<capacity) //     
 {for(x=1;x<=capacity;x++) //            
 if(mc[x]==-1) {
 mc[x]=page[j];
 sum++;
 printf(" %2d   \t",page[j]);
 for(m=1;m<=capacity;m++) //             
 printf("%2d ",mc[m]);
 printf("
");
 break;}
 }
 else if(sum>=capacity)
 {
 int t=mc[ep];
 mc[ep]=page[j];
 printf(" %2d  %2d\t",page[j],t);
 for(m=1;m<=capacity;m++) //             
 printf("%2d ",mc[m]);
 printf("
");
 ep+=1;
 if(ep==capacity+1) ep=1; 
 } 
 }
 } 
 printf("
exist=%d
   =%lf",exist,exist/320.0);
} 
int main()
{
 int capacity; //     
 printf("         (0~319):");
 randomnumber();
 printf("
           :
"); 
 pageaddress(); 
 printf("


\t\t      (FIFO):

");
 printf("       （4-32）：");
 scanf("%d",&capacity);
 for(int i=1;i<=32;i++) //       
 mc[i]=-1;
 FIFO(capacity); 
 return 0;
}

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