학부시절 운영체제 수업을 들었던 기억이 가물 가물한데,...

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; 


}
저작자 표시
신고

+ Recent posts

티스토리 툴바