학부시절 운영체제 수업을 들었던 기억이 가물 가물한데,...
LRU 알고리즘이 갑자기 생각나서 수업 자료들을 뒤지는 중 시뮬레이션 소스를 발견하였다.
10년 정도 지나고 나서 보니, 대체 왜 이런식으로 코딩을 했을까 하고 생각도 들긴하지만, 그때 당시 열심히 공부했었구나 싶기도 하다.
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// 2002년 11월 20일
// 운영체제론 Report #2
// PageFault Simulation.
// Algorithm : FIFO
// Optimal
// LRU
// Compiler : MS Visual C++ 6.0
// Test : Pentium III 866Mhz, 512Mb SDRAM, VIA694 Board
// 실행 시 유의 사항 : 윈도우즈에서 실행 시킬 경우 도스명령창이 뜨는데 그때 그 창의 속성을 너비 84이상으로 할것
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#include <stdio.h> // 표준 입출력함수를 사용하기 위해서 포함시킴
#include <stdlib.h> // rand()를 사용하기 위해서 포함시킴
#include <time.h> // rand()의 seed를 time을 사용하기 위해서 포함시킴
#include <malloc.h> // 메모리 할당함수인 malloc 함수의 사용을 위해
#define MAX_FRAME 10 // 프레임의 수를 최대 10로 설정
// 페이지가 1~7까지라서 7이면 충분하지만, test를 위해 여유 있게 10으로 함.
#define MAX_REF_SIZE 60 // reference string의 길이를 60으로 한다.
#define default_of_frame 3 //frame의 수를 default 값으로 3으로 한다.
int ref_string[MAX_REF_SIZE]; // reference string의 길이를 60으로 한다.
int frame[MAX_FRAME]={0}; // FIFO와 Optimal 방식에서 사용될 frame 배열(초기화 시킴)
int number_of_frame=0; // 입력 받을 프레임의 수
int cfifo=0; //fifo 방식의 pagefault 발생횟수
int coptimal=0; //optimal 방식의 pagefault 발생횟수
int clru=0; //LRU 방식의 pagefault 발생횟수
typedef struct stack_dlist *stack_ptr; //LRU방식에서 사용될 이중연결 리스트 구조체 선언
typedef struct stack_dlist{
stack_ptr uplink;
stack_ptr downlink;
int data;
};
stack_ptr top=NULL; // 일종의 stack형식이므로 top값을 지정
stack_ptr bottom=NULL; // 접근 편리를 위해 bottom값을 지정(pagefault 때에는 bottom에 있는 값을 victim으로 한다.
void init(); // reference string 만들기, 프레임의 수 입력 받기 ,screen 만들기, 각 함수 호출하기
void fifo(); // fifo replacement 방식을 구현한 함수
void optimal(); // optimal replacement 방식을 구현한 함수
void lru(); // LRU replacement 방식을 구현한 함수
short int pagefault(int); // pagefault를 검사하는 함수
short int lru_pagefault(int); // LRU 방식에서 pagefault 검사하는 함수
int flength(int,int); // optimal 에서 현재위치 i에서 프레임의 각 원소들이 얼마나 멀리 있는지 검사하는 함수
void main(void)
{
init();
}
void init()
{
int number=0; // 프레임의 수를 저장한다.
int i=0; // loop에 사용될 변수
char *cnumber;// frame 의 갯수를 입력받아서 저장할 포인터
cnumber=(char *)malloc(3*sizeof(char)); // 크기를 3으로한다.
printf("Number of Frame (Maximum value is %d, Default value is %d) : ",MAX_FRAME,default_of_frame);
gets(cnumber); // frame의 수를 사용자로부터 입력받아서 number변수에 저장한다.
if(cnumber[0]==NULL) //default값으로 대치한다.
{
number=default_of_frame;
}
else // 문자열을 정수형으로 변환한다.
{
number=atoi(cnumber);
}
if((number > 0) && (number < MAX_FRAME+1))
{
number_of_frame=number;
}
else //범위에 벗어나는 입력이 들어 왔을경우 디폴트 값으로 한다.
{
number_of_frame=default_of_frame;
}
// 화면을 구성한다.
printf("\nNumber of Frame : %d PageFault: F",number_of_frame);
printf("\n┌────┬──────────────────────────────┬───┐");
printf("\n│ Method │Reference String │Counts│");
printf("\n│ │");
srand( (unsigned)time( NULL ) ); // 랜덤하게 Reference String을 만들것이므로 rand()의 seed를 넣어준다.
for(i=0;i<MAX_REF_SIZE;i++) // Reference String의 길이를 MAX_REF_SIZE로 해서 만든다.
{
ref_string[i]=rand()%7+1;
printf("%d",ref_string[i]);
}
printf("│ │");
printf("\n");
printf("├────┼──────────────────────────────┼───┤");
printf("\n");
printf("│FIFO │");
fifo(); // fifo함수 호출
if(cfifo>9) // fifo카운터의 자릿수가 두 자리 일 때
{
printf("│ %d │",cfifo);
}
else // fifo카운터의 자릿수가 한 자리 일 때
{
printf("│ %d │",cfifo);
}
printf("\n");
printf("├────┼──────────────────────────────┼───┤");
printf("\n");
for(i=0;i<MAX_FRAME;i++) // frame을 0으로 초기화 시킨다.(fifo에서 사용했던 프레임의 내용을 제거)
{
frame[i]=0;
}
printf("│Optimal │");
optimal();
if(coptimal>9) // optimal 카운터의 자릿수가 두 자리 일 때
{
printf("│ %d │",coptimal);
}
else // optimal 카운터의 자릿수가 한 자리 일 때
{
printf("│ %d │",coptimal);
}
printf("\n");
printf("├────┼──────────────────────────────┼───┤");
printf("\n");
printf("│LRU │");
lru(); // LRU함수 호출
if(clru>9) // LRU 카운터의 자릿수가 두 자리 일 때
{
printf("│ %d │",clru);
}
else // LRU 카운터의 자릿수가 한 자리 일 때
{
printf("│ %d │",clru);
}
printf("\n└────┴──────────────────────────────┴───┘");
printf("\n");
}
void fifo()
{
int i=0,f=0;
for(i=0;i<MAX_REF_SIZE;i++)
{
if(pagefault(ref_string[i])) // pagefault발생하면
{
cfifo++; // 그 카운터를 증가시키고
frame[f]=ref_string[i]; // replacement한다.
printf("F"); // pagefault가 발생했다는 표시한다.
f=(f+1)%number_of_frame; // frame의 인덱스를 프레임의 수에 맞게 바꾼다.(fifo)
}
else
{
printf(" "); // 아무일도 없다.
}
}
}
void optimal()
{
int i=0,f=0,k=0;
int length[MAX_FRAME]={0}; // 프레임내의 어떤 원소의 위치가 어디 인지를 저장하는 변수
int max=0; // 가장 늦게 나오는 프레임인덱스를 저장하게 된다.
for(i=0;i<MAX_REF_SIZE;i++)
{
max=0;
if(pagefault(ref_string[i])) // pagefault발생하면
{
coptimal++;//카운터 증가
if(frame[f]==-1)//frame에 비어 있는 공간이 있으면 그냥 넣어도 됨,처음에는 프레임이 비어 있음
{
frame[f]=ref_string[i];
f=f+1;
}
else// frame에 빈 공간이 없을때, 프레임에 있는 item들이 다음의 refrence string에서 어디에 위치하는지 알아보고
// 가장 늦게 나오는 item을 replacement한다.
{
for(k=0;k<number_of_frame;k++)// 각 아이템들이 지금 위치에서 얼마나 멀리 떨어져 있는지 검사
{
length[k]=flength(i,k);
}
for(k=0;k<number_of_frame-1;k++)
{
if(length[max]<length[k+1]) // 가장 늦게 나오는 원소를 replacement하기 위해서 골라 낸다.
{
max=k+1;
}
}
frame[max]=ref_string[i]; // replacement
}
printf("F");
}
else
{
printf(" ");
}
}
}
void lru()
{
int i=0,stack_count=0;
for(i=0;i<MAX_REF_SIZE;i++)
{
if(lru_pagefault(ref_string[i])) // pagefault발생하면
{
clru++;// 카운터 증가
if(number_of_frame==1)// 만약에 프레임의 수가 1 이라면
{
stack_ptr temp=(stack_ptr)malloc(sizeof(stack_dlist)); // 임시 노드를 하나 선언한다.
temp->downlink=NULL; // 프레임 노드가 하나만 있으므로 replacement는 그 data만 바꾸면 된다.
temp->uplink=NULL;
temp->data=ref_string[i];
top=temp;
bottom=temp;
}
else if(stack_count<number_of_frame) // 스택이 비어 있다면(프레임에 빈공간이 있다면)
{
stack_ptr temp=(stack_ptr)malloc(sizeof(stack_dlist)); // 임시 노드 선언
stack_count++;// 스택 카운터를 증가시킨다.
temp->downlink=top;// 이중연결 리스트 구조 이므로
temp->uplink=NULL; // 이중연결 리스트 구조 이므로 (리포트에 따로 정리)
if(top) // 노드가 하나라도 존재하면
{
top->uplink=temp; //존재하는 노드의 uplink를 새로운 노드로 포인팅한다.
}
temp->data=ref_string[i];// 데이터 저장
top=temp; // top를 새로운 노드로 한다.
if(!bottom) // 노드의 밑부분의 노드를 bottom으로 한다.
{
bottom=temp;
}
}
else // 프레임에 빈공간이 없을 경우
{
stack_ptr temp=(stack_ptr)malloc(sizeof(stack_dlist));
temp=bottom; // 교과서에 나온대로 제일 밑의 노드를 희생량으로 삼는다.
// 링크의 조정(자료구조 책에 나옴)
temp->uplink->downlink=temp->downlink;
bottom=temp->uplink;
temp->data=ref_string[i];
temp->downlink=top;
temp->uplink=top->uplink;
top->uplink=temp;
top=temp;
}
printf("F");
}
else
{
printf(" ");
}
}
}
short int pagefault(int item)
{
int i=0;
short int flag=1; // pagefault가 발생하면 1
for(i=0;i<number_of_frame;i++)
{
if(frame[i]==item)
flag=0; // 그렇지 않으면 0
}
return flag;
}
int flength(int now,int item_pos) // 현재 위치에서 얼마나 떨어져 있는지 검사
{
int i=0;
i=now+1;
while(i<MAX_REF_SIZE)
{
if(ref_string[i]==frame[item_pos])
{
return i;
}
i++;
}
return MAX_REF_SIZE+1;
}
short int lru_pagefault(int item) // LRU 의 pagefault검사
{
int flag=1;
stack_ptr temp=(stack_ptr)malloc(sizeof(stack_dlist));
stack_ptr position=(stack_ptr)malloc(sizeof(stack_dlist));
position=top;
temp=top;
while(position!=NULL) // 리스트에서 데이터를 찾는 방식과 같음
{
if(position->data==item)// 프레임에 지금 들어온 페이지가 존재하면 그 노드를 top으로하고 링크를 조정한다.
{
temp=position;
flag=0; // pagefault발생 안함
if((temp->uplink)&&(temp->downlink)) // 노드가 리스트의 중간에 있을 경우(top나 bottom이 아닐경우)
{
temp->uplink->downlink=temp->downlink;
temp->downlink->uplink=temp->uplink;
temp->downlink=top;
temp->uplink=top->uplink;
top->uplink=temp;
top=temp;
}
else if(!(temp->downlink)&&temp->uplink) // 노드가 bottom에 있을 경우(노드가 하나만 있다면 안된다)
{
temp->uplink->downlink=temp->downlink;
bottom=temp->uplink;
temp->uplink=top->uplink;
top->uplink=temp;
temp->downlink=top;
top=temp;
}
}
position=position->downlink;//리스트의 처음부터 끝까지 다 스캔해서 페이지를 검색.
}
return flag;
}
'코딩하고 > C,C++' 카테고리의 다른 글
| 큰 정수 계산하기 (0) | 2016.03.27 |
|---|---|
| cocosdx 사용해서 게임 개발하기 -1- (0) | 2012.11.19 |
| 자료구조 - 계산기 만들기 (10) | 2012.10.12 |
| C언어로 만든 객체 (0) | 2012.10.11 |
| 자료구조 - 다항식 연산하기 (2) | 2012.10.10 |
커뉴
이 세상에서 꿈 이상으로 확실한 것을, 인간은 가지고 있는 것일까?