操作系统实验之存储管理第二版

import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;
import java.util.Scanner;

public class 存储管理 {
	public static int []num;
	public static node []node1;
	public static List<node>list=new ArrayList<node>();
	public static DecimalFormat df=new DecimalFormat("0.00");
	public static int findMax(int []num)//找出存在时间最长的未被使用的标志位
	{
		int max=num[0];
		int flag=0;
		for(int i=1;i<num.length;i++)
		{
			if(num[i]>max)
			{
				flag=i;
				max=num[i];
			}
		}
		return flag;
	}
	public static int findlist(List<Integer>list1,int address)
	{
		int flag=0;
		for(int i=0;i<list1.size();i++)
		{
			if(list1.get(i)==address)
			{
				flag=i;
				break;
			}
		}
		return flag;
	}
	public static int figure(int j,int i)//i是最大值，j是最小值
	{
		Random ran=new Random();
		int k=ran.nextInt(i-j+1)+j;//范围是[j,i]
		return k;
	}

	public static void LRU(int i)//最近最久未使用
	{
		List<Integer>list1=new ArrayList<Integer>();
		int flag=0;
		double count=0;
		int []num=new int [i];
		for(int j=0;j<list.size();j++)//这一步是先将整个地址能够填充满
		{
			if(list1.size()==i)//如果填充满了整个list1那么就跳出循环
			{
				flag=j;
				break;
			}
			else if(list1.contains(list.get(j).address))//如果list1中存在该页号，那么就只需要将该页号的最近使用时间置为0，其他位的时间+1就行了
			{
				int flag1=findlist(list1, list.get(j).address);
				for(int k=0;k<list1.size();k++)
				{
					if(k!=flag1)
						num[k]+=1;
					else
						num[k]=0;
				}
			}
			else if(!list1.contains(list.get(j).address))//这里面与下面的操作有一个不同的就是，因为list1没有填充满，所以不需要将不存在的那个页号与某个页号进行置换，
				                                         //只需要压入就够了，这时候不用就将所有的时间+1就行了
			{
				count++;
				list1.add(list.get(j).address);
				for(int k=0;k<list1.size();k++)
					num[k]+=1;
			}
		}
		for(int j=flag;j<list.size();j++)
		{
			if(list1.contains(list.get(j).address))//将存在的位置置为0，其他位置+1
			{
				int flag1=findlist(list1, list.get(j).address);
				for(int k=0;k<num.length;k++)
				{
					if(k!=flag1)
						num[k]+=1;
					else
						num[k]=0;
				}
				/*for(int k=0;k<num.length-1;k++)
					System.out.print(num[k]+" ");
				System.out.println(num[num.length-1]);*/
			}
			else//如果不存在就需要先找到最久未使用的标志，然后将其位置置为0，其他位置+1,之后将list1相应位置的值重新赋值成更改后的值 
			{
				count++;
				int flag1=findMax(num);
				for(int k=0;k<num.length;k++)
				{
					if(k!=flag1)
						num[k]+=1;
					else
						num[k]=0;
				}
				for(int k=0;k<list1.size();k++)
				{
					if(k==flag1)
						list1.set(flag1,list.get(j).address);
				}
				/*System.out.println("置换出第"+flag1);
				for(int k=0;k<num.length-1;k++)
					System.out.print(num[k]+" ");
				System.out.println(num[num.length-1]);*/
			}
		}
		count/=320;
		count=1-count;
		System.out.println(df.format(count));
		list1.clear();
		Arrays.fill(num, 0);
	}
	public static void FIFO(int i)//先进先出算法
	{
		List<Integer>list1=new ArrayList<Integer>();
		int flag=0;
		double count=0;
		for(int j=0;j<list.size();j++)//还是先将整个list1压满再说
		{
			if(list1.size()==i)
			{
				flag=j;
				break;
			}
			else if(!list1.contains(list.get(j).address))
			{
				list1.add(list.get(j).address);
				count++;
			}
		}
		for(int j=flag;j<list.size();j++)//因为是先进先出，那么这个理念就特别满足队列的使用范围，因为队列中最先进去的元素最后会在哪里呢，
			                             //想想就知道是在对头元素呀，最晚进入的元素就是队尾刚刚被压入的队尾元素
		{
			if(!list1.contains(list.get(j).address))
			{
				count++;
				list1.remove(0);
				list1.add(list.get(j).address);
			}
		}
		count/=320;
		count=1-count;
		System.out.println(df.format(count));
		list1.clear();
	}
	public static void LFU(int i)//最少使用算法
	{
		List<Integer>list1=new ArrayList<Integer>();
		int []num1=new int [32];//这里一开始设置的数组长度为i,但是之后发现不方便，就设置长度为32，设置为32后可以计数每个页号出现的次数，这样可以方便比较
		int flag=0;
		double count=0;
		for(int j=0;j<list.size();j++)//还是之前的操作，就只是压满队列而已
		{
			if(list1.size()==i)
			{
				flag=j;
				break;
			}
			else if(!list1.contains(list.get(j).address))//计数每个页号出现的次数
			{
				count++;
				list1.add(list.get(j).address);
				for(int k=0;k<32;k++)
				{
					if(k==list.get(j).address)
						num1[k]+=1;
				}
			}
			else 
			{
				for(int k=0;k<32;k++)//计数每个页号出现的次数
				{
					if(k==list.get(j).address)
						num1[k]+=1;
				}
			}
		}
		for(int j=flag;j<list.size();j++)
		{
			if(!list1.contains(list.get(j).address))
			{
				count++;
				int min=num1[list1.get(0)];
				int flag1=0;
				for(int k=1;k<list1.size();k++)//这里是最少使用算法的关键，就是查找出那个是使用最少的
					                           //我们通过置换的次数来判断list1中那个使用次数最少，这时候我们创建的数组长度的好处就体现出来了
					                           //这里我们只要比较list1中所有的出现过的页号的使用次数，然后找出其中使用次数最少的即可
				{
					if(num1[list1.get(k)]<min)
					{
						flag=k;
						min=num1[k];
					}
				}
				list1.set(flag1, list.get(j).address);
				for(int k=0;k<32;k++)
				{
					if(k==list.get(j).address)
						num1[k]+=1;
				}
			}
			else 
			{
				for(int k=0;k<32;k++)
				{
					if(k==list.get(j).address)
						num1[k]+=1;
				}
			}
		}
		count/=320;
		count=1-count;
		System.out.println(df.format(count));
		list1.clear();
		Arrays.fill(num1, 0);
		
	}
	public static void optimal(int i)//最佳置换算法
	{
		List<Integer>list1=new ArrayList<Integer>();
		int []num1=new int [i];//记录每个已经压入的页号在之后最近出现的时间
		int flag=0;
		double count=0;
		for(int j=0;j<list.size();j++)//还是先将整个队列压满再说
		{
			if(list1.size()==i)
			{
				flag=j;
				break;
			}
			else if(!list1.contains(list.get(j).address))
			{
				list1.add(list.get(j).address);
				count++;
			}	
		}
		for(int j=flag;j<list.size();j++)
		{
			if(!list1.contains(list.get(j).address))//如果碰到不存在的就开始查找list1中所有元素，在之后的队列顺序中最先出现的位置，
				                                    //然后查找出出现位置最大的那个，也就是最晚使用的页号，然后将他所对应的页号的位置上的页号重新赋值成现在即将插入的页号
			{
				count++;
				for(int k=0;k<i;k++)
				{
					a:for(int k1=j+1;k1<list.size();k1++)
					{
						if(list1.get(k)==list.get(k1).address)
						{
							num1[k]=k1;
							break a;
						}
						num1[k]=Integer.MAX_VALUE;
					}
				}
				int flag1=findMax(num1);
				list1.set(flag1, list.get(j).address);
				/*System.out.println("置换出第"+flag1);
				for(int k=0;k<num1.length-1;k++)
					System.out.print(num1[k]+" ");
				System.out.println(num1[num1.length-1]);*/
			}
		}
		count/=320;
		count=1-count;
		System.out.println(df.format(count));
		list1.clear();
		Arrays.fill(num1, 0);
	}
	public static void xunhuan()
	{
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		while(n>4||n<1)
		{
			System.out.println("输入的算法号码不存在！！！");
			n=sc.nextInt();
		}
		if(n==1)//最佳置换算法
		{
			for(int i=2;i<33;i++)
			{
				 System.out.print("地址块为"+i+"时的命中率:");
				 //System.out.println("地址块为"+10+"时的命中率:");
				 optimal(i);
				 //optimal(10);
			}
		}
		else if(n==2)//最久未使用
		{
			for(int i=2;i<33;i++)
			{
				System.out.print("地址块为"+i+"时的命中率:");
			    //System.out.print("地址块为"+10+"时的命中率:");
				LRU(i);
				//LRU(10);
			}
		}
		else if(n==3)//先进先出
		{
			for(int i=2;i<33;i++)
			{
				System.out.print("地址块为"+i+"时的命中率:");  
				FIFO(i);
			}
		}
		else 
		{
			for(int i=2;i<33;i++)
			{
				System.out.print("地址块为"+i+"时的命中率:");  
				LFU(i);
			}
		}
	}
	public static void main(String[] args)
	{
		System.out.println("开始存储管理");
		System.out.println("地址流正在产生，请稍等:");
		int count=0;
		num=new int [320];
		node1=new node[320];
		while(count!=320)//按照要求开始产生相应的地址流
		{
			int i=figure(0, 319);
			num[count]=i;
			count++;
			int j=figure(0, i+1);
			num[count]=j;
			count++;
			num[count]=j+1;
			count++;
			num[count]=figure(j+2, 319);
			count++;
		}
		System.out.println("地址流产生:");//打印地址流
		for(int i=0;i<320;i++)
		{
			if((i-9)%10==0)
				System.out.println(num[i]);
			else
				System.out.print(num[i]+" ");
		}
		for(int i=0;i<320;i++)
		{
			node1[i]=new node();
			node1[i].zhiling=num[i];
			node1[i].address=num[i]/10;
			list.add(node1[i]);
		}
		/*for(int i=0;i<320;i++)
		{
			System.out.println(list.get(i).zhiling+" "+list.get(i).address);
		}*/
		/*System.out.println("地址页号产生:");
		for(int i=0;i<32;i++)
		{
			System.out.println("第"+i+"页号内容如下");
			for(int j=0;j<9;j++)
				System.out.print(num[10*i+j]+" ");
			System.out.println(num[10*i+9]);
		}*/
		System.out.println("1.Optimization algorithm(最佳置换算法)");
		System.out.println("2.Least recently used algorithm(最近最久未使用算法)");
		System.out.println("3.First in first out algorithm(先进先出页面置换算法)");
		System.out.println("4.Least frequently used algorithm(最少未使用算法)");
		System.out.println("请选择以下的淘汰算法的号码:");
		Scanner sc=new Scanner(System.in);
		xunhuan();
		System.out.println("是否继续选择其他的页面置换算法");
		System.out.println("输入Y或者N");
		String str=sc.next();
		while(str.equals("Y"))
		{
			System.out.println("1.Optimization algorithm(最佳置换算法)");
			System.out.println("2.Least recently used algorithm(最近最久未使用算法)");
			System.out.println("3.First in first out algorithm(先进先出页面置换算法)");
			System.out.println("4.Least frequently used algorithm(最少未使用算法)");
			System.out.println("请选择以下的淘汰算法的号码:");
			xunhuan();
			System.out.println("是否继续选择其他的页面置换算法");
			System.out.println("输入Y或者N");
			str=sc.next();
		}	
	}
	static class node
	{
		int zhiling;
		int address;
		public node() {
			// TODO Auto-generated constructor stub
		}
	}
}