#include <stdio.h>

void Fifo()
{
	int p = 0;                                  //物理塊的數(shù)量
    int physical[7] = {-1,-1,-1,-1,-1,-1,-1};   //存入物理塊中的頁(yè)號(hào)
    int num = 0;                                //頁(yè)面數(shù)
    int page[20] = {0};                         //要運(yùn)行的進(jìn)程的頁(yè)號(hào)
    int i,j,k;                                  //循環(huán)變量
    int countt = 0;                             //缺頁(yè)次數(shù)
	int a = 0;                                  //最近訪問(wèn)標(biāo)志
	int c = 0;                                  //缺頁(yè)標(biāo)志
	printf ("您選擇了先進(jìn)先出（FIFO）算法！\n");
	printf ("請(qǐng)輸入物理塊的數(shù)目：");
	scanf ("%d",&p);
	printf ("請(qǐng)輸入頁(yè)面數(shù)：");
	scanf ("%d",&num);
	printf ("請(qǐng)輸入頁(yè)號(hào)（以空格隔開）：");
	for (i = 0 ; i < num ; i++)
		scanf("%d",&page[i]);
	for (k = 0 ; k < num ; k++)
	{///
	    for (i = 0 ; i < p ; i++)
		{//
		    if (physical[i] == page[k])
			{
				break;
			}
			else if (physical[i] == -1)       //物理塊有空位
			{
				physical[i] = page[k];
				countt ++;
				c += 1;
				break;
			}
			else if (physical[i] != -1 && i == p - 1)  //物理塊已滿
			{
                for (j = 0 ; j < p ; j++)
				{
                     if (page[k] != physical[j] && j == p - 1)   //該頁(yè)面不在當(dāng)前物理塊中
					{
						physical[a] = page[k];
				        a ++;
				        if (a == p)  a = 0 ;       //將最先進(jìn)的置換后 初始化其標(biāo)志
				        countt ++;
						c += 1;
					}
				}
			}
		}//
		printf ("置換過(guò)程第%d步：",k + 1);
		for (i = 0 ; i < p ; i++)
		{
			if (physical[i] == -1)
				printf ("  ");
			else
				printf ("%d ",physical[i]);
		}
		if (c == 1)
		{
			printf ("發(fā)生缺頁(yè)");
			c = 0;
		}
		printf ("\n");
	}///
	printf ("缺頁(yè)次數(shù)為：%d\n",countt);
	printf ("缺頁(yè)率為：%d%%\n\n",countt*100/num);
	//printf("Fifo\n");
}

void Lru()
{
	int p = 0;                                  //物理塊的數(shù)量
    int physical[7] = {-1,-1,-1,-1,-1,-1,-1};   //存入物理塊中的頁(yè)號(hào)
    int num = 0;                                //頁(yè)面數(shù)
    int page[20] = {0};                         //要運(yùn)行的進(jìn)程的頁(yè)號(hào)
    int i,j,k,t;                                //循環(huán)變量
    int countt = 0;                             //缺頁(yè)次數(shù)
	int c = 0;                                  //缺頁(yè)標(biāo)志
	int once[7] = {0};                          //最近訪問(wèn)標(biāo)志數(shù)組
	printf ("您選擇了最近最久未使用（LRU）算法！\n");
	printf ("請(qǐng)輸入物理塊的數(shù)目：");
	scanf ("%d",&p);
	printf ("請(qǐng)輸入頁(yè)面數(shù)：");
	scanf ("%d",&num);
	printf ("請(qǐng)輸入頁(yè)號(hào)（以空格隔開）：");
	for (i = 0 ; i < num ; i++)
		scanf("%d",&page[i]);
	for (k = 0 ; k < num ; k++)
	{
	    for (i = 0 ; i < p ; i++)
		{
		    if (physical[i] == page[k])
			{
				for (j = 0 ; j <= p ; j++)
				{
					if (once[j] != 0 && j != i && once[j] < once[i]) //??????     //不缺頁(yè)的 但相同頁(yè)號(hào) 算進(jìn)行了一次訪問(wèn)  其他未訪問(wèn)的+1		
					    once[j] += 1;
				}
				once[i] = 1;
				break;
			}
			else if (physical[i] == -1)       //物理塊有空位
			{
				physical[i] = page[k];
				countt ++;
				c += 1;
				once[i] = 1;
				for(j = 0 ; j < i ; j++)
				{
					if (once[j] != 0)
						once[j] += 1;
				}
				break;
			}
			else if(physical[i] != -1 && i == p - 1)    //物理塊已滿
			{
				for (j = 0 ; j < p ; j++)
				{
					if (once[j] == p)
					{
						physical[j] = page[k];
						once[j] = 1;                   //置換掉
						for (t = 0 ; t < p ; t++)
						{
							if(t != j)
								once[t] += 1;     //將其他未被訪問(wèn)的+1，達(dá)到三的就替掉
						
						}
						countt++;
						c += 1;
						break;
					}
				}
			}
		}
		printf ("置換過(guò)程第%d步：",k+1);
		for (i = 0 ; i < p ; i++)
		{
			if (physical[i] == -1)
				printf ("  ");
			else
				printf ("%d ",physical[i]);
		}
		if (c == 1)
		{
			printf ("發(fā)生缺頁(yè)");
			c = 0;
		}
		printf ("\n");
	}
	printf ("缺頁(yè)次數(shù)為：%d\n",countt);
	printf ("缺頁(yè)率為：%d%%\n\n",countt*100/num);
}

void Optimal()
{
	int p = 0;                                  //物理塊的數(shù)量
    int physical[7] = {-1,-1,-1,-1,-1,-1,-1};   //存入物理塊中的頁(yè)號(hào)
    int num = 0;                                //頁(yè)面數(shù)
    int page[20] = {0};                         //要運(yùn)行的進(jìn)程的頁(yè)號(hào)
    int i,j,k,t;                                //循環(huán)變量
    int countt = 0;                             //缺頁(yè)次數(shù)
	int a[7] = {0};                             //各物理塊中的頁(yè)面下一次的訪問(wèn)時(shí)間
	int b = 0;                                  //排序算法的中間變量
	int c = 0;                                  //缺頁(yè)標(biāo)志
	printf("您選擇了最佳（OPTIMAL）置換算法！\n");
    printf ("請(qǐng)輸入物理塊的數(shù)目：");
	scanf ("%d",&p);
	printf ("請(qǐng)輸入頁(yè)面數(shù)：");
	scanf ("%d",&num);
	printf ("請(qǐng)輸入頁(yè)號(hào)（以空格隔開）：");
	for (i = 0 ; i < num ; i++)
		scanf("%d",&page[i]);
	for (k = 0 ; k < num ; k++)
	{
	    for (i = 0 ; i < p ; i++)
		{
		    if (physical[i] == page[k])
			{
				break;
			}
			else if (physical[i] == -1)       //物理塊有空位
			{
                physical[i] = page[k];
				countt ++;
				c += 1;
				break;
			}
			else if(physical[i] != -1 && i == p - 1)    //物理塊已滿
			{
				//獲得各物理快中內(nèi)容下一次的訪問(wèn)時(shí)間
				for (j = 0 ; j < p ; j++)
				{
					for (t = k ; t < num ; t++)
					{
						if(physical[j] == page[t])      
						{
							a[j] = t - k;           //時(shí)間間隔
							break;
						}
						else if(physical[j] != page[t] && t == num - 1)
							a[j] = num;    //如果以后此頁(yè)面永遠(yuǎn)用不到，則設(shè)定為最大值
					}
				}
				//比較各時(shí)間的大小
				for (j = 1 ; j < p ; j++)
				{
                    if (a[j] > a[b])
					{
						b = j;
					}
				}
				physical[b] = page[k];
				b = 0;
				countt++;
				c += 1;
			}
		}
		printf ("置換過(guò)程第%d步：",k+1);
		for (i = 0 ; i < p ; i++)
		{
			if (physical[i] == -1)
				printf ("  ");
			else
				printf ("%d ",physical[i]);
		}
		if (c == 1)
		{
			printf ("發(fā)生缺頁(yè)");
			c = 0;
		}
		printf ("\n");
	}
	printf ("缺頁(yè)次數(shù)為：%d\n",countt);
	printf ("缺頁(yè)率為：%d%%\n\n",countt*100/num);
	//printf("Optimal\n");
}

int main()
{
	int n;
	do
	{
		printf ("請(qǐng)選擇要使用的置換算法:\n1.FIFO算法\n2.LRU算法\n3.OPTIMAL算法\n0.退出系統(tǒng)\n");
	    scanf ("%d",&n);
	    switch(n)
		{
	    case 1:
		    Fifo();
		    break;
	    case 2:
		    Lru();
		    break;
        case 3:
	    	Optimal();
		    break;
	    case 0:
		    return 0;
		default:
			printf ("輸入有誤，請(qǐng)重試！\n");
		}
	}
	while(n != 0);
	return 0;
}