// 과제용으로 작성한 코드인데요

// 컴파일 상에서는 문제가 없는데 실행 도중에 계속 아래와 같은 에러가 납니다
// 그런데 이게 무슨 특정 기능을 사용한다든지, 몇 회 반복한다든지 정해진게 없이 불규칙하게 나와서..
// 아래 코드도 첨부해드릴테니 직접돌려보셔도 됩니다.
// 제가 malloc을 확실히 몰라서... 메모리 관련해서 free를 안 해줘서 그런가 하는 추측을 해봄니다..
// 참고로 Visual C++ 2010 Express로 돌렸습니다.



#include <stdio.h>
#include <stdlib.h>
#include <time.h>
// WINDOW system : #include <time.h>     / system("cls");
// LINUX  system : #include <sys/time.h> / system("clear");

#define NOT_USED  0 // 해당 프레임이 현재까지 사용된 적이 없다는 것을 나타냄 
#define INFINITE 1000            // timestamp와 future에 대해 원활한 비교를 위해 
                                // 초기에 상대적으로 큰값을 할당할 때 사용

int Selection(); // 시뮬레이션할 알고리즘의 종류 혹은 재시작, 종료를 선택함
int error_check(int i, int min, int max); // 사용자가 입력해야 될 값에서 벗어난 값을 입력할 경우 재입력 받음

// 알고리즘을 구현한 함수들, 인자는 레퍼런스 스트링과 스트링의 길이, 결과화면 출력 여부, 프레임 개수 
int FIFO(int page_string[], int n, int print, int framesize);
int LIFO(int page_string[], int n, int print, int framesize);
int OPT(int page_string[], int n, int print, int framesize);
int LRU(int page_string[], int n, int print, int framesize);
int CLK(int page_string[], int n, int print, int framesize);
int LFU(int page_string[], int n, int print, int framesize);
int MFU(int page_string[], int n, int print, int framesize);

void Result(int page_string[], int n, int framesize);

int result[7]; // 각 알고리즘 별로 시뮬레이션 했을 때 발생한 페이지 폴트 수 저장
int num_frames; // 사용자가 입력한 페이지 프레임 수 저장
int num_pages; // 사용자가 입력한 페이지 개수 저장
int num_seq;        // 랜덤 생성 혹은 사용자가 입력한 레퍼런스 스트링 길이 저장
int *page_string;   // 레퍼런스 스트링을 배열로 저장
int *frame;         // 배열 인덱스는 프레임 넘버를 의미하며 변수로 할당된 페이지 넘버 저장

int *timestamp;     // 배열 인덱스는 페이지 넘버를 의미하며 변수는 
                    // FIFO의 경우 처음 들어온 상대적 시간이, 
                    // LRU의 경우 마지막으로 참조된 시간이 저장됨

int *clk_val;       // 배열 인덱스는 페이지 넘버를 의미하며 변수는
                    // LRU를 대신하는 CLK(Clock) 알고리즘에서 
                    // second chance 개념을 구현하기 위해 0 또는 1을 저장

int *used_freq;     // 배열 인덱스는 페이지 넘버를 의미하며 변수는
// LFU와 MFU에서 참조된 횟수를 비교하기 위해
                    // 참조될 때마다 1씩 증가시킴

int *future; // 배열 인덱스는 페이지 넘버를 의미하며 변수는
// OPTIMAL에서 미래에 참조될 스트링에서의 인덱스 저장


int main(void) {
   while(1)
            if(Selection())
                    break;

printf("\n @ 프로그램을 종료합니다. \n @ ");
return 0;
}

int Selection()
{ int i; // 반복문을 위한 인덱스
int sel; // 메뉴선택 값을 저장 
int ifran;      // 레퍼런스 스트링을 랜덤으로 생성할지 여부 저장

srand((unsigned int)time(NULL)); // 항상 다른 랜덤 결과를 갖기 위해 현재시간 사용
system("cls");
printf("\n\n @ Starting Page Replacement Algorithms Simulation...  \n");
printf("\n @ 페이지 교체 알고리즘 시뮬레이션을 시작합니다. \n");
printf("\n @ 페이지의 개수를 입력하세요 > "); scanf("%d",&num_pages);
printf("\n @ 프레임의 개수를 입력하세요 > "); scanf("%d",&num_frames);
printf("\n @ 레퍼런스 스트링의 길이를 입력하세요 > "); scanf("%d", &num_seq);
printf("\n @ 레퍼런스 스트링의 생성 방법을 입력하세요 \n");
printf(" @ (1.프로그램이 랜덤으로 생성 2.사용자 입력) > "); scanf("%d", &ifran);

        

page_string =(int*)malloc(num_seq*sizeof(int));
frame = (int*)malloc(num_frames*sizeof(int));
clk_val =(int*)malloc(num_pages*sizeof(int));
timestamp = (int*)malloc(num_pages*sizeof(int));
used_freq=(int*)malloc(num_pages*sizeof(int));
future=(int*)malloc(num_pages*sizeof(int));

    if(ifran==1)
{
for( i = 0;  i < num_seq;  i++) // 랜덤 선택의 경우 자동 생성
page_string[i] = rand() % num_pages+1;
}
    else
{
printf("\n @ [-]개의 레퍼런스 스트링을 하나씩 입력해주세요. ",num_seq);
printf("\n @ 페이지는 [1에서 %d]까지 있습니다. \n\n", num_pages);

back:
for(i=0;i<num_seq;i++){
            printf(" * [-번] 페이지 레퍼런스 > ",(i+1));
            scanf("%d",&page_string[i]);
if(!error_check(page_string[i], 1, num_pages)){
i = 0;
goto back;
}
        }
    }
system("cls");
    printf("\n @ 페이지 레퍼런스 스트링 : ");
    for(i=0;i<num_seq;i++)
    {
        printf("%d ",page_string[i]);
    }

printf("\n"); 
    while(1)
    {
while(1)
{
printf("\n");
printf("┌--------------------------------┐\n");
printf("│ 1. FIFO (First In First Out)   │\n");
printf("│ 2. LIFO (Last In First Out)    │\n");
printf("│ 3. OPTIMAL                     │\n");
printf("│ 4. LRU  (Least Recently Used)  │\n");
printf("│ 5. CLOCK(LRU Approximation)    │\n");
printf("│ 6. LFU  (Least Frequently Used)│\n");
printf("│ 7. MFU  (Most Frequently Used) │\n");
printf("│ 8. Result !!                   │\n");
printf("│ 9. Close Program               │\n");
printf("└--------------------------------┘\n");
printf("\n @ 시뮬레이션할 페이지 교체 알고리즘을 선택하세요. > "); scanf("%d",&sel);
if(error_check(sel, 1, 9))
break;
}
                        
switch(sel)
        {
            case 1: 
system("cls"); 
printf("\n @ FIFO (First In First Out) \n");
FIFO( page_string, num_seq, 1, num_frames ); 
                break;
case 2: 
system("cls"); 
printf("\n @ LIFO (Last In First Out) \n");
LIFO( page_string, num_seq, 1, num_frames ); 
                break;
case 3: 
system("cls"); 
printf("\n @ OPTIMAL \n");
OPT( page_string, num_seq, 1, num_frames ); 
                break;
case 4: 
system("cls"); 
printf("\n @ LRU  (Least Recently Used) \n");
LRU( page_string, num_seq, 1, num_frames ); 
                break;
case 5: 
system("cls"); 
printf("\n @ CLOCK(LRU Approximation) \n");
CLK( page_string, num_seq, 1, num_frames ); 
                break;
case 6: 
system("cls"); 
printf("\n @ LFU  (Least Frequently Used) \n");
LFU( page_string, num_seq, 1, num_frames ); 
                break;
case 7: 
system("cls"); 
printf("\n @ MFU  (Most Frequently Used) \n");
MFU( page_string, num_seq, 1, num_frames ); 
                break;
case 8: 
system("cls"); 
Result( page_string, num_seq, num_frames );
break;
case 9: 
return 1;
}
}

return 0;
}

int error_check(int i, int min, int max)
{       
if(min<=i && i<=max)
        return 1;
else
    {
        printf("\n ! 잘못된 입력입니다. 다시입력해주세요.\n");
        return 0;
    }
}

int FIFO(int page_string[], int n, int print, int framesize) {
int pagefault; // 각 시점마다 페이지폴트 수 저장
int page; // 각 시점에서 참조하려는 페이지 번호
int i, j; // 반복문을 위한 인덱스
int fifo; // 페이지 별 timestamp값에서 가장 작은 값을 저장
int fifo_idx; // fifo에 해당하는 값을 timestamp로 갖는 페이지
                       // 즉, 가장 먼저 들어온 페이지의 인덱스 저장
int processed;          // 페이지가 이미 있거나 빈 프레임이 있을 경우 1로 설정되어
// 페이지 폴트가 생기지 않음을 알림

// 프레임과 타임스탬프 값, 페이지 폴트 수 초기화.
for( i = 0;  i < framesize;  i++ )
frame[i] = NOT_USED;
for( i = 0;  i < n;  i++ )
timestamp[i] = INFINITE; // 후에 상대적 비교에서 더 작은 값을 찾기 때문에 초기값은 무한
pagefault = 0;
if( print == 1 ){
printf("\n\n  Page Reference\t");
printf("Page Fault\t");
for(j = 0; j< framesize/2; j++)
printf(" ");
printf("frame");
printf("\n     String");
}

// 시뮬레이션 시작
for( i = 0;  i < n;  i++ ) {
processed = 0;
page = page_string[i]; // 레퍼런스 스트링에서 페이지 넘버 받음
// 기존에 있었다면 해당 프레임을, 없다면 빈 프레임을 찾음
for( j = 0;  j < framesize;  j++ )
if( frame[j] == page ) {
processed = 1;
break;
}
else if( frame[j] == NOT_USED ) {
frame[j] = page; // 빈 프레임에 페이지를 넣음, 즉 페이지 넘버를 저장
timestamp[page] = i; // 해당 페이지의 타임스탬프를 현재 들어온 상대적 시간으로 저장
pagefault++;
processed = 1;
break;
}
if( processed != 1 ){
// 위의 두 경우가 아닐 시 페이지 폴트 발생
fifo = timestamp[frame[0]];
fifo_idx = 0;
for( j = 1;  j < framesize;  j++ )  {
if( frame[j] == NOT_USED )
continue;
if( fifo > timestamp[frame[j]] ) { // 가장 작은 타임스탬프를 갖는 페이지 넘버 추출
fifo_idx = j;
fifo = timestamp[frame[fifo_idx]];
}
}
frame[fifo_idx] = page; // 찾은 페이지가 있던 프레임에 새 페이지 할당
timestamp[page] = i; // 지금 할당한 페이지에 대한 타임스탬프 설정
pagefault++;
}
// 단계별 화면출력
if( print == 1 ) {
printf("\n\t-\t\t", page_string[i]);
printf("-\t\t", pagefault);
for(j = 0; j< framesize; j++)
printf("- ", frame[j]);
}
}

return pagefault;
}

int LIFO(int page_string[], int n, int print, int framesize) {
int pagefault; // 각 시점마다 페이지폴트 수 저장
int page; // 각 시점에서 참조하려는 페이지 번호
int i, j; // 반복문을 위한 인덱스
int lifo; // 페이지 별 timestamp값에서 가장 큰 값을 저장
int lifo_idx; // lifo에 해당하는 값을 timestamp로 갖는 페이지
                       // 즉, 가장 나중에 들어온 페이지의 인덱스 저장
int processed;          // 페이지가 이미 있거나 빈 프레임이 있을 경우 1로 설정되어
// 페이지 폴트가 생기지 않음을 알림

// 프레임과 타임스탬프 값, 페이지 폴트 수 초기화.
for( i = 0;  i < framesize;  i++ )
frame[i] = NOT_USED;
for( i = 0;  i < n;  i++ )
timestamp[i] = -1; // 후에 상대적 비교에서 더 큰 값을 찾기 때문에 초기값은 음수
pagefault = 0;
if( print == 1 ){
printf("\n\n  Page Reference\t");
printf("Page Fault\t");
for(j = 0; j< framesize/2; j++)
printf(" ");
printf("frame");
printf("\n     String");
}

// 시뮬레이션 시작
for( i = 0;  i < n;  i++ ) {
processed = 0;
page = page_string[i]; // 레퍼런스 스트링에서 페이지 넘버 받음
// 기존에 있었다면 해당 프레임을, 없다면 빈 프레임을 찾음
for( j = 0;  j < framesize;  j++ )
if( frame[j] == page ) {
processed = 1;
break;
}
else if( frame[j] == NOT_USED ) {
frame[j] = page; // 빈 프레임에 페이지를 넣음, 즉 페이지 넘버를 저장
timestamp[page] = i; // 해당 페이지의 타임스탬프를 현재 들어온 상대적 시간으로 저장
pagefault++;
processed = 1;
break;
}
if( processed != 1 ){
// 위의 두 경우가 아닐 시 페이지 폴트 발생
lifo = timestamp[frame[0]];
lifo_idx = 0;
for( j = 1;  j < framesize;  j++ )  {
if( frame[j] == NOT_USED )
continue;
if( lifo < timestamp[frame[j]] ) { // 가장 큰 타임스탬프를 갖는 페이지 넘버 추출
lifo_idx = j;
lifo = timestamp[frame[lifo_idx]];
}
}
frame[lifo_idx] = page; // 찾은 페이지가 있던 프레임에 새 페이지 할당
timestamp[page] = i; // 지금 할당한 페이지에 대한 타임스탬프 설정
pagefault++;
}
// 단계별 화면출력
if( print == 1 ) {
printf("\n\t-\t\t", page_string[i]);
printf("-\t\t", pagefault);
for(j = 0; j< framesize; j++)
printf("- ", frame[j]);
}
}

return pagefault;
}

int OPT(int page_string[], int n, int print, int framesize) {
int pagefault; // 각 시점마다 페이지폴트 수 저장
int page; // 각 시점에서 참조하려는 페이지 번호
int i, j, k; // 반복문을 위한 인덱스
int futureval; // 페이지 별 future값에서 가장 큰 값을 저장
int futureval_idx; // futureeval에 해당하는 값을 future로 갖는 페이지
                       // 즉, 미래에 가장 나중에 참조될 페이지의 인덱스 저장
int processed;          // 페이지가 이미 있거나 빈 프레임이 있을 경우 1로 설정되어
// 페이지 폴트가 생기지 않음을 알림

// 프레임과 미래 참조될 인덱스 값, 페이지 폴트 수 초기화.
for( i = 0;  i < framesize;  i++ )
frame[i] = NOT_USED;
for( i = 0;  i < n;  i++ )
future[i] = INFINITE; // 후에 상대적 비교에서 더 작은 값을 찾기 때문에 초기값은 무한