#include <stdio.h>
#include <stdlib.h>

#define MAXPAGE 100
#define NUM 3

int time = 0;//完成時間
int page[NUM];//分配給進程的頁塊數

int AccessSeq(int * head);//讀取頁面訪問序列
void InitPage(int * head);//頁面初始化
void MovePage(int * head, int indix);//一個頁面移動到隊尾
int FullPage(int * head);//判斷頁面是否分配完
int MarchPage(int * page, int num);//判斷頁面是否命中
int LRU(int *page, int *head, int length);//LRU分配算法,輸入是頁塊數,頁面訪問序列和序列長度,返回是缺頁數

int main()
{
	int head[MAXPAGE], count;

	time = AccessSeq(head);//讀取頁面訪問序列
	InitPage(page);//對頁面初始化
	count = LRU(page, head, time);//計算缺頁數

	printf("The finished time is: %d\n"
		"The page fault is: %d\n"
		"The page fault ratio is: %d%%\n", time, count, count*100/time);

	return 0;
}

int AccessSeq(int * head)
{
	FILE* fp;
	int indix, count;

	if(!(fp = fopen( "page.txt","r" )))
	{//文件讀取失敗
		printf("NO THAT FILE\n");
		exit(0);
	}

	fscanf(fp, "%d", &count);//讀取訪問序列長度

	for(indix = 0; indix < count; indix++)//獲得頁面訪問序列
		fscanf(fp, "%d", &head[indix]);

	return count;//返回訪問序列長度
}

void InitPage(int * page)
{//對頁面進行初始化,未使用的頁面為-1
	for(int i = 0; i < NUM; i++)
		page[i] = -1;
}

void MovePage(int * page, int indix)
{//將最近被訪問到的頁面移到隊列的尾部
	int temp, pointer;

	temp = page[indix];
	pointer = FullPage(page);

	for(int i = indix; i < pointer - 1; i++)
		page[i] = page[i + 1];
	page[pointer - 1] = temp;//最近被訪問到的頁面移到隊尾
}

int FullPage(int * page)
{//返回隊列中還可分配頁面的指針
	for(int i = 0; i < NUM; i++)
		if(page[i] == -1)
			return i;
	return NUM;
}

int MarchPage(int * page, int num)
{//返回隊列中分配頁面的指針
	for(int i = 0; i < NUM; i++)
		if(page[i] == num)
			return i;
	return -1;
}

int LRU(int * page, int * head, int length )
{//最近最久未使用置換算法
	int count = 0, pointer1, pointer2;

	for(int i = 0; i < length; i++)
	{
		if((pointer1 = MarchPage(page, head[i])) != -1)
		{//頁面已分配,將分配的頁面移到隊尾
			MovePage(page, pointer1);
			continue;
		}
		else
			if((pointer2 = FullPage(page)) != NUM)//頁面未被分配
				page[pointer2] = head[i];//從可分配的頁面中分配一個頁面
			else
			{//無可分配的頁面,則將最久未使的頁面替換掉
				page[0] = head[i];
				MovePage(page, 0);//將頁面移動到隊尾
				count++;//缺頁數加1
			}
	}

	return count;//返回缺頁數
}