호야의 블로그
[C] 운영체제-Page Replacement 알고리즘 만들기
개요
글을 읽기에 앞서 이전에 올려드렸던 가상 메모리에 관한 설명을 먼저 보신다면 보다 수월하게 이해할 수 있을 것입니다. 아래 링크를 클릭하시면 됩니다.
LRU는 가장 최근에 사용한 메모리만 사용하는 알고리즘으로 페이지 실패(Page Fault)가 일어날 때 가장 오래된 메모리와 교체하는 알고리즘입니다. 만약 기존 테이블에 페이지 'aaa'가 들어가있는데 다시 'aaa'가 페이징 한다면 페이지 참조가 되며 가장 최근으로 초기화 됩니다. 따라서 각 페이지의 나이를 기억하는 변수도 있어야 할 것입니다. 또한 페이지 갯수는 10개로 1이면 'aaa', 2이면 'bbb' 3이면 'ccc'와 같은 방식으로 10까지 대응됩니다.
최종 출력화면은 다음과 같습니다. 프로그램 실행 후 테이블 크기를 정하는 숫자를 입력하면 메인으로 넘어가며, 메뉴 번호를 입력할 수 있는 입력 공간이 나옵니다.
Enter Your Table Size: <ANY_NUMBER>
1. Insert
2. Show
3. Exit
Enter Your Choice: <SELECT_MENU_NUM>
구현
선언
헤더는 다음과 같이 2가지를 선언하겠습니다. 기본적인 헤더만으로도 알고리즘 구현이 가능합니다.
#include <stdio.h> #include <stdlib.h>
각 페이지의 이름이 들어가는 2차원 배열을 선언합니다. 메모리의 초기 값은 0으로 'NONE'를 출력하도록 합니다.
char str[11][5]={"NONE","aaa", "bbb", "ccc", "ddd", "eee", "fff", "ggg", "hhh", "iii", "jjj"};
알고리즘
1. int insert()
페이지를 추가하는 함수입니다. 페이지 번호를 1~10 중에 입력합니다. 먼저 1번째 메모리가 공백인지 페이지 참조 가능한지 페이지 폴트인지 판단하는 check 조건을 넣습니다.저는 처음에 이렇게 하지 않고, 모든 조건을 따지며 짜니 코드가 많이 복잡하고 지저분해져 보기가 힘들었습니다.(자칫 잘 못하면 스파게티 코드가 되어 다시 보면 못 알아보기 일쑤) 이 후 각 상태에 맞게 간단한 연산을 몇 번 해주면 끝납니다. 페이지 폴트 시 나이는 제일 어려지고, 페이지 참조 시 페이지 카운트가 증가하는 아주 간단한 공식입니다.
참고로 제 코드의 나이는 상대적인 나이만 필요하여 실제 나이와 같지 않습니다. 약간 수정하시면 매 시간 나이가 몇인지도 구할 수 있을 것 입니다. 아래에 주석을 참고하시면 감사하겠습니다. 복잡해 보이지만 몇 번 응용하시면 매우 간단하다는 것을 알 수 있을 것입니다. 천천히 따라해주세요.
int insert(int* arr, int* cnt, int* oldd, int size){ //arr 현재 메모리 공간, cnt 페이징 횟수, oldd 페이지 나이, size 메모리 크기 int i, j, l, ent, temp, check, high; //ent 현재 입력 값 int k=i+1; printf("Enter page no between 1to10: "); //페이지 번호를 1~10 중에서 입력합니다. scanf("%d",&ent); printf("\n"); for(i=0;i<size;i++){ //현재 들어온 페이지가 첫 번째 페이지와 어떤 관계인지 상태를 체크하기 위한 조건문입니다.(0-빈 메모리, 1-페이지 참조, 2-페이지 폴트) if(arr[i]==0){ check=0; //첫 번째에 공백이 있음(빈 자리가 있는 경우) 함수 빠져나가서 체크 0 조건에 들어갑니다. break; } else if(arr[i]==ent){ check=1; //페이지가 있음(페이지 참조) 함수 빠져나가서 체크 1조건에 들어갑니다. break; } else{ check=2; //다 다름(페이지 폴트) } } if(check==0&&ent<=10&&ent>=1){ //첫 메모리 공간에 공백이 있는 경우(1~10) for(l=0;l<size&&arr[l]!=0;l++){ ++oldd[l]; //일단 나이를 한 칸씩 올립니다 } for(i=0;i<size;i++){ if(arr[i]==0){ //새 것인 경우(빈 공간에 페이징을 합니다) arr[i]=ent; cnt[i]++; //페이지 했으니 페이지 카운트 1올림 oldd[i]++; //나이도 당연 1올림 break; } else if(arr[i]==ent){ //만약 페이지 참조가 발생하면 나이를 1로 초기화합니다. arr[i]=ent; //페이지 입력 값으로 대체 cnt[i]++; //페이지 횟수 1 올림 oldd[i]=1; //페이지 발생했으니 나이를 초기화 break; } } } if(check==1&&ent<=10&&ent>=1){ //첫 메모리 만에 페이지 성공 for(l=0;l<size&&arr[l]!=0;l++){ ++oldd[l]; } for(i=0;i<size;i++){ if(arr[i]==ent){ cnt[i]++; //페이지 발생했으니 페이지 1올림
oldd[i]=1; //나이 1 초기화 break; //빠져나감 } } } if(check==2&&ent<=10&&ent>=1){ //첫 메모리 페이지 실패 for(l=0;l<size&&arr[l]!=0;l++){ ++oldd[l]; //일단 전부 나이 올리고 } high=0; for(i=0;i<size;i++){ //제일 나이 많은 페이지를 찾습니다. if(high<oldd[i]){ high=oldd[i]; temp=i; //temp 번지가 가장 나이가 많군요 } } arr[temp]=ent; //temp 자리에 입력한 값으로 대체합니다 cnt[temp]=1; //페이징 횟수 초기화 oldd[temp]=1; //나이 초기화 } }
메뉴 UI
1. int show()
현재까지 입력한 페이지 테이블을 보여줍니다. 나이 많은 것이 가장 위로 출력되도록 하며 만약 새로운 페이지 삽입 시 제일 위의 페이지가 없어지고, 제일 아래에 새로운 페이지가 추가됩니다.
int show(int* arr, int* cnt, int* oldd,int size){ int i, j, k, temp, temp2, temp3; for(j=0;j<size-1;j++) { for(k=0;k<size-1-j;k++) { if(oldd[k] < oldd[k+1]) //페이지를 나이 내림차순 정렬합니다. { temp = oldd[k]; oldd[k]=oldd[k+1]; oldd[k+1] = temp; temp2 = arr[k]; arr[k]=arr[k+1]; arr[k+1] = temp2; temp3 = cnt[k]; cnt[k]=cnt[k+1]; cnt[k+1] = temp3; } } } printf("Contain Pageno Pagecount\n"); //출력부분 for(i=0;i<size;i++){ printf("%s %d %d\n",str[arr[i]], arr[i], cnt[i]); } }
메인 함수
1. int main()
메인에서 테이블, 페이지 횟수, 나이를 동적 선언합니다. 이 후 테이블을 초기화하며 while문을 통해 프로그램이 종료될 때까지 동작하게 됩니다.
int main(){ int choice=0; int size, i; //table size int* table; int* page_count; int* old; printf("Enter Your Table Size: "); scanf("%d",&size); table= (int*)malloc(size*sizeof(int)); page_count= (int*)malloc(size*sizeof(int)); old= (int*)malloc(size*sizeof(int)); for(i=0;i<size;i++){ table[i]=0; //table 초기화 page_count[i]=0; old[i]=0; } while(1){ printf("1. Insert\n2. Show\n3. Exit\nEnter Your Choice: "); scanf("%d",&choice); printf("\n"); switch(choice){ case 1: //1번 입력 메뉴 insert(table, page_count, old, size); continue; case 2: //2번 출력 메뉴 show(table, page_count, old, size); continue; case 3: //3번 종료메뉴 printf("3\n"); break; default: //1~10의 수가 아니면 경고문 출력 printf("Insert 1 to 3\n"); continue; } break; } return 0; }
전체 코드
#include <stdio.h> #include <stdlib.h> char str[11][5]={"NONE","aaa", "bbb", "ccc", "ddd", "eee", "fff", "ggg", "hhh", "iii", "jjj"}; //int cur=0; int insert(int* arr, int* cnt, int* oldd, int size){ int i, j, l, ent, temp, check, high; int k=i+1; //printf("현재 10번 중 %d번째\n",cur); printf("Enter page no between 1to10: "); scanf("%d",&ent); printf("\n"); for(i=0;i<size;i++){ if(arr[i]==0){ check=0; //공백이 있음 break; } else if(arr[i]==ent){ check=1; //페이지가 있음 break; } else{ check=2; //다 다름 } } //printf("모드: %d\n\n",check); if(check==0&&ent<=10&&ent>=1){ //메모리 공백이 있는 경우 for(l=0;l<size&&arr[l]!=0;l++){ ++oldd[l]; } for(i=0;i<size;i++){ if(arr[i]==0){ //새 것인 경우 arr[i]=ent; cnt[i]++; //새것이 아니면 있는지 비교 후 있으면 카운트 업, 없으면 카운트 낮은 것 대체 oldd[i]++; break; } else if(arr[i]==ent){ arr[i]=ent; cnt[i]++; oldd[i]=1; break; } } } if(check==1&&ent<=10&&ent>=1){ //페이지 성공 for(l=0;l<size&&arr[l]!=0;l++){ ++oldd[l]; } for(i=0;i<size;i++){ if(arr[i]==ent){ cnt[i]++; oldd[i]=1; break; } } } if(check==2&&ent<=10&&ent>=1){ //페이지 실패 for(l=0;l<size&&arr[l]!=0;l++){ ++oldd[l]; } high=0; for(i=0;i<size;i++){ if(high<oldd[i]){ high=oldd[i]; temp=i; } } arr[temp]=ent; cnt[temp]=1; oldd[temp]=1; } //cur++; } int show(int* arr, int* cnt, int* oldd,int size){ int i, j, k, temp, temp2, temp3; for(j=0;j<size-1;j++) { for(k=0;k<size-1-j;k++) { if(oldd[k] < oldd[k+1]) //연달아있는 두수중 앞에 있는수가 크다면 { temp = oldd[k]; oldd[k]=oldd[k+1]; oldd[k+1] = temp; temp2 = arr[k]; arr[k]=arr[k+1]; arr[k+1] = temp2; temp3 = cnt[k]; cnt[k]=cnt[k+1]; cnt[k+1] = temp3; } } } printf("Contain Pageno Pagecount\n"); for(i=0;i<size;i++){ printf("%s %d %d\n",str[arr[i]], arr[i], cnt[i]); } } int main(){ int choice=0; int size, i; //table size int* table; int* page_count; int* old; printf("Enter Your Table Size: "); scanf("%d",&size); table= (int*)malloc(size*sizeof(int)); page_count= (int*)malloc(size*sizeof(int)); old= (int*)malloc(size*sizeof(int)); for(i=0;i<size;i++){ table[i]=0; //table 초기화 page_count[i]=0; old[i]=0; } while(1){ printf("1. Insert\n2. Show\n3. Exit\nEnter Your Choice: "); scanf("%d",&choice); printf("\n"); switch(choice){ case 1: insert(table, page_count, old, size); continue; case 2: show(table, page_count, old, size); continue; case 3: printf("3\n"); break; default: printf("Insert 1 to 3\n"); continue; } break; } return 0; }
실습
프로그램 실행 시 나타나는 첫 화면입니다. 번호 선택으로 메뉴 선택이 가능합니다. 저는 초기 테이블 사이즈를 3으로 잡았습니다. 크기는 상관없이 동작합니다.
초기의 출력입니다. 텅 비어있는 상태로 3개의 공간에 NONE를 표시합니다.
1번 insert를 눌러 5라는 페이지를 집어 넣습니다.
2번을 눌러 출력하면 아래와 같이 보여집니다. 페이지가 되었으므로 페이지 카운트가 1증가했습니다.
추가로 3과 2를 페이지 테이블에 추가합니다.
아래와 같이 보여집니다. 참고로 가장 오래된 것이 제일 위에 보여집니다.
추가로 3, 6, 2 순서로 추가합니다.
이때 기존에 있던 3과 2에서 페이지 참조가 일어나 페이지 카운트가 1 상승하고, 6은 페이지 폴트가 발생하여 가장 오래된 5('eee')를 대체(Replacement)합니다.
이후 7을 넣으면 가장 오래된 3이 빠지고 7이 새로 삽입됩니다.
7을 5번 더 추가하여 페이지 참조를 시키겠습니다.
이후 가장 나이가 많은 6을 추가하여 페이지 카운트 1 상승시키고, 나이를 초기화 시켜 가장 아래로 내려갔습니다.
후기 및 정리
이렇게 간단한 Page Replacement 알고리즘을 C로 구현해보았습니다. 참고하셔서 더 좋은 알고리즘으로 더 나은 프로그램을 구현해보시길 바라겠습니다. 감사합니다.
(소스는 댓글로 남겨주시면 드리겠습니다.)
C 4번째 글: 2018/11/02 - [IT/C] - [C] 운영체제-Page Replacement 알고리즘 만들기
C 3번째 글: 2018/10/31 - [IT/C] - [C] 운영체제-CPU 스케줄링 시뮬레이터 만들기
C 2번째 글: 2018/10/30 - [IT/C] - [C++] 영상처리-이미지 Sobel 경계 검출 및 영상 이진화
C 1번째 글: 2018/10/19 - [IT/C] - [C] 리눅스 환경에서 fork() 함수를 이용한 자식 프로세스 생성하기
조금의 도움이 되셨다면 로그인 없이도 가능한 댓글과
왼쪽 아래 ♥공감 버튼을 꾹 눌러주세요!
'IT > C' 카테고리의 다른 글
| CPU 스케줄링 시뮬레이터 C로 만들기 (10) | 2018.10.31 |
|---|---|
| 영상처리-C++로 이미지 Sobel 경계 검출 및 영상 이진화 (1) | 2018.10.30 |
| 리눅스 환경에서 fork() 함수를 이용한 자식 프로세스 생성하기 (0) | 2018.10.19 |