package myprojects.os;
//	LRU最近最久未使用置換算法實現及其命中率計算
class LRU{
	public LRU(){}		//缺省構造方法
	public float getLru(int p){	//有參getLru(int p)方法由測試類傳入內存頁面數，并用此
		int[] Lpage = new int[p]; //參數計算其對應的LRU的命中率及返回該命中率；
		int[] old = new int[p];  //old[]數組，用于記錄對應當前內存頁面上一次訪問此頁面至今的時間間隔
		int[] page= new int[400];
		GetRandom random = new GetRandom();
		page=random.getPage();	//定義一數組，用以接收頁面數組的內容
		int s,a,t,n=0;
		int i,j;
		float sum=0,Opercent;	//設置兩個float型變量，其中Opercent用于存放命中率,sum則用于記錄命中次數
		for(i=0;i<400;i++){
			if(n==0){	//內存為空
				Lpage[0]=page[i];// 把當前頁面值存入內存
				n++;		//記錄當前內存空間
				old[0]=0;	//	時間清零；
			}
			else{
				if(n<p-1){	//內存不為空且內存未滿
					s=0;
					for(j=0;j<n;j++) //與內存存放的內容比較，相等則讀入下一條指令
						if(Lpage[j]==page[i]){
							sum++;	//命中次數加1
							//a=j;
							s=1;	//標記比較結果，有相等則s=1
							for(t=0;t<n;t++)
								old[t]=old[t]+1;//所有頁面時間數加1
							old[j]=0;			//剛訪問的頁面時間數置0
							break;
						}
					if(s==0){	//當前指令所對應的頁面值與內存所有內容比較不相等
						Lpage[n]=page[i];	//則將當前頁面值添加入內存	
						for(t=0;t<n;t++)
							old[t]=old[t]+1;//所有頁面時間數加1
						old[n]=0;		//剛添加入的頁面時間數置0
						n++;
					}
				}
				else{	//內存已滿
					s=0;
					for(j=0;j<p;j++){	//與內存存放的內容比較，相等則讀入下一條
						if(Lpage[j]==page[i]){//指令
							sum++;		//命中次數加1
							s=1;		//標記比較結果，有相等則s=1
							for(t=0;t<n;t++)
								old[t]=old[t]+1;//所有頁面時間數加1
							old[j]=0;	//剛訪問的頁面時間數置0
							break;
						}
					}
					if(s==0){	//當前指令所對應的頁面值與內存所有內容比較不相等
						a=0;
						for(t=0;t<p-1;t++)
							if(old[t]>old[t+1])	//比較內存內所有頁面所標記的訪問時間
								old[t+1]=old[t];	//找出最大時間間隔的頁面
							else 
								a=t+1;
						Lpage[a]=page[i];	//用當前讀入頁面替換最大時間間隔的頁面
						for(t=0;t<n;t++)
							old[t]=old[t]+1;//所有頁面時間數加1
						old[a]=0;	//剛添加入的頁面時間數置0
					}
				}
			}
		}
		Opercent=sum/400;	//計算命中率
		return Opercent;	//返回該值
	}
}