virtualmemory.java

虚拟内存中四种置换算法: OPT/LRU/FIFO/时钟算法

import javax.swing.JOptionPane;
public class Virtualmemory {
	public static void main(String args[])
	{
		int jincheng_num=Integer.parseInt(JOptionPane.showInputDialog("Input the amount of the thread:"));
		int page_num=Integer.parseInt(JOptionPane.showInputDialog("Input the amount of the page:"));
		int jincheng[]=new int[jincheng_num];//{2,3,2,1,5,2,4,5,3,2,5,2};
		//int jincheng_num=jincheng.length;
		int memo_num=3;
		int FOPT,FLRU,FFIFO,FClock;
		for(int i=0;i<jincheng_num;i++)
		{
			jincheng[i]=(int)((Math.random()*page_num)+1);
		}
		outPut(jincheng);
		System.out.println();
		int memo[]=new int[]{0,0,0};
		System.out.println("OPT:");
		FOPT=OPT(memo,memo_num,jincheng,jincheng_num);
		System.out.println("****************************************************");
		System.out.println("LRU:");
		FLRU=LRU(memo,memo_num,jincheng,jincheng_num);
		System.out.println("****************************************************");
		System.out.println("FIFO:");
		FFIFO=FIFO(memo,memo_num,jincheng,jincheng_num);
		System.out.println("****************************************************");
		System.out.println("Clock:");
		FClock=Clock(memo,memo_num,jincheng,jincheng_num);
		System.out.println("****************************************************");
	}
	static int OPT(int memo[],int memo_num,int jincheng[],int jincheng_num)						//OPT 算法
	{
		int change_num[]=new int[memo_num];
		int flag=0,F=0;
		for(int n=0;n<change_num.length;n++)
		{
			change_num[n]=jincheng_num+1;
		}
		for(int k=0;k<jincheng.length;k++)
		{
			for(int j=0;j<memo.length && flag==0;j++)
			{
				if(memo[j]==0)
				{
					memo[j]=jincheng[k];
					flag=1;
					F++;
			//		System.out.println("insert memo" + j);

				}
				else if(memo[j] == jincheng[k])
				{
					flag=1;

					//System.out.println("insert memo" + j);
					break;
				}
			}
			if(flag==0)
			{
				int changenum=0;
				int temp=0;
				for(int p=0;p<memo.length;p++)
				{
					for(int i=k+1;i<jincheng.length;i++)
					{
						if(memo[p]==jincheng[i])
						{
							change_num[p]=i;
							break;
						}
					}
				}
			//	System.out.print("change_num array:");
			//	outPut(change_num);
				for(int l=0;l<change_num.length;l++)
				{
					if(temp<change_num[l])
					{
						temp=change_num[l];
						changenum=l;
					}
						//System.out.println("changenum:"+changenum);
				}

				memo[changenum]=jincheng[k];
				F++;
			}

			outPut(memo);
			System.out.println();
			flag=0;
		}
		System.out.println("F="+F);
		return F;
	}
		static int LRU(int memo[],int memo_num,int jincheng[],int jincheng_num)						//LRU 算法
		{
			int change_num[]=new int[memo_num];
			int flag=0,F=0;
			for(int n=0;n<change_num.length;n++)
			{
				change_num[n]=-1;
			}
			for(int k=0;k<jincheng.length;k++)
			{
				for(int j=0;j<memo.length && flag==0;j++)
				{
					if(memo[j]==0)
					{
						memo[j]=jincheng[k];
						flag=1;
						F++;
				//		System.out.println("insert memo" + j);

					}
					else if(memo[j] == jincheng[k])
					{
						flag=1;

						//System.out.println("insert memo" + j);
						break;
					}
				}
				if(flag==0)
				{
					int changenum=0;
					int temp=k;
					for(int p=0;p<memo.length;p++)
					{
						for(int i=k-1;i>=0;i--)
						{
							if(memo[p]==jincheng[i])
							{
								change_num[p]=i;
								break;
							}
						}
					}
				//	System.out.print("change_num array:");
				//	outPut(change_num);
					for(int l=0;l<change_num.length;l++)
					{
						if(temp>change_num[l])
						{
							temp=change_num[l];
							changenum=l;
						}
							//System.out.println("changenum:"+changenum);
					}

					memo[changenum]=jincheng[k];
					F++;
				}

				outPut(memo);
				System.out.println();
				flag=0;
			}
			System.out.println("F="+F);
			return F;
		}
	static int FIFO(int memo[],int memo_num,int jincheng[],int jincheng_num)									//FIFO算法
	{
		int flag=0,F=0;
		int i=0;
		/*for(int n=0;n<change_num.length;n++)
		{
			change_num[n]=jincheng_num+1;
		}*/
		for(int k=0;k<jincheng.length;k++)
		{
			for(int j=0;j<memo.length && flag==0;j++)
			{
				if(memo[j]==0)
				{
					memo[j]=jincheng[k];
					flag=1;
					F++;
			//		System.out.println("insert memo" + j);

				}
				else if(memo[j] == jincheng[k])
				{
					flag=1;

					//System.out.println("insert memo" + j);
					break;
				}
			}
			if(flag==0)
			{
				memo[i]=jincheng[k];
				F++;
				i=(i+1)%3;
				flag=1;
			}

			outPut(memo);
			System.out.println();
			flag=0;
		}
		System.out.println("F="+F);
		return F;
	}
		static int Clock(int memo[],int memo_num,int jincheng[],int jincheng_num)//Clock 算法
		{
			int change_num[]=new int[memo_num];
			int flag=0,F=0,count=0,changenum=0;
			for(int n=0;n<change_num.length;n++)
			{
				change_num[n]=0;
			}
			for(int k=0;k<jincheng.length;k++)
			{

				for(int j=0;j<memo.length;j++)
				{
					if(memo[j] == jincheng[k]&&change_num[j]==1)
					{
						//change_num[j]=0;
						flag=1;
						//System.out.println("insert memo" + j);
						break;
					}
				}
				if(flag==0)
				{
					while(true)
					{
						if(change_num[count]==0)
						{
							if(memo[count]==jincheng[k])
							{
								F--;
							}
							memo[count]=jincheng[k];
					//		System.out.println("change memo"+count);
							flag=1;
							F++;
							change_num[count]=1;
							count=(count+1)%3;
					//		System.out.println(F);
							break;
						}
						else
						{
							change_num[count]=0;
						}
						count=(count+1)%3;
					//	System.out.println(count);
					}
				}

				outPut(memo);
				System.out.println();
				flag=0;
			}
			System.out.println("F="+F);
			return F;
		}

	static void outPut(int p[])																		//输出数组
		{
			for(int i=0;i<p.length;i++)
			{
				System.out.print(p[i]+";");
			}
	}

}