JAVA 页面置换先进先出算法（FIFO）

电玩女神 2022-05-21 12:09 214阅读 0赞

设计四:页面置换

设计目的：

加深对请求页式存储管理实现原理的理解，掌握页面置换算法。

设计内容:

设计一个程序，有一个虚拟存储区和内存工作区，实现下述三种算法中的任意两种，计算访问命中率（命中率=1-页面失效次数/页地址流长度）。附加要求：能够显示页面置换过程。

算法包括：先进先出的算法（FIFO）、最少使用算法（LFU）、最近未使用算法（NUR）

该系统页地址流长度为320，页面失效次数为每次访问相应指令时，该指令对应的页不在内存的次数。

程序首先用srand()和rand()函数分别进行初始化、随机数定义和产生指令序列，然后将指令序列变换成相应的页地址流，并针对不同的算法计算出相应的命中率。

通过随机数产生一个指令序列。共320条指令，指令的地址按下述原则生成：

（1）50%的指令是顺序执行的。

（2）25%的指令是均匀分布在前地址部分。

（3）25%的指令是均匀分布在后地址部分。

具体的实施方法如下：

在【0，319】的指令地址之间随机选取一起点m。

顺序执行一条指令，即执行地址为m+1的指令。

在前地址【0,m+1】中随机选取一条指令并执行，该指令的地址为m’。

顺序执行一条指令，其地址为m’+1。

在后地址【m’+2,319】中随机选取一条指令并执行。

重复步骤（1）-（5），直到320次指令。

将指令序列变换为页地址流。

设：

页面大小为1KB。

用户内存容量4页到32页。

用户虚存容量为32KB。

在用户虚存中，按每K存放10条指令虚存地址，即320条指令在虚存中的存放方式为：

第0条～9条指令为第0页（对应虚存地址为【0，9】）。

第10条～19条指令为第1页（对应虚存地址为【10，19】）。

……

第310条～319条指令为第31页（对应虚拟地址为【310，319】）。

按以上方式，用户指令可组成32页。

计算每种算法在不同内存容量下的命中率。

import java.util.Random;
    public class Hello {  
        public static void main(String[] args){
        	int order=320;           //指令数
        	int [] c=new int[order];     //地址访问顺序
        	int [] b=new int[order];     //页面访问顺序
        	int memory=16;            //内存容量
        	int lose=0;         //页面失效次数
        	double hit_rate=0;  //命中率
        	int i,j,k;
        	int count1=0;
        	int count2=0;
        	int m1,m2,m3;
        	Random rand = new Random();  
    /
        	System.out.println("产生的随机数为：");
        	for(i=0;;i++){
        		m1=rand.nextInt(320);     //在0--319之间随机产生一个数
        		c[count1]=m1+1;
         		System.out.print(c[count1]+" ");
        		count1++;
        		count2++;
        		if(count1==order)
        			break;
        		if(count2==32){
        			System.out.print("\n");
        			count2=0;
        		}
        		m2=rand.nextInt(m1+1);    //在0--m1+1之间随机产生一个数
        		c[count1]=m2+1;
        		System.out.print(c[count1]+" ");
        		count1++;
        		count2++;
        		if(count1==order)
        			break;
        		if(count2==32){
        			System.out.print("\n");
        			count2=0;
        		}
        		m3=rand.nextInt(320-m2-2)+m2+2;    //在m2+2--319之间随机产生一个数
        		c[count1]=m3+1;
        		System.out.print(c[count1]+" ");
        		count1++; 	
        		count2++;
        		if(count1==order)
        			break;
        		if(count2==32){
        			System.out.print("\n");
        			count2=0;
        		}
        	}
        	System.out.print("\n");
    ///
        	System.out.println("访问页面的顺序为：");
        	count2=0;
        	for(i=0;i<order;i++){
        		b[i]=c[i]/10;
        		System.out.print(b[i]+" ");
        		count2++;
        		if(count2==32){
        			System.out.print("\n");
        			count2=0;
        		}
        	}
        	System.out.print("\n");
    ///
     //   	for(memory=4;memory<=32;memory++){
        		System.out.println("页面进入内存的步骤为：");
        		Queue queue=new Queue();  
        		for(i=0;i<order;i++){
        			if((queue.L-queue.F)==memory){    //如果内存满了,就淘汰最早进入内存的页面,否则直接进入内存
        				for(j=queue.F;j<queue.L;j++){
        					if(b[i]==queue.a[j])
        						break;
        				}
        				if(j==queue.L){          //如果没有命中，先进去的页面就先出来
        					lose++;
        					queue.out();
        					queue.come(b[i]);
        				}
        			}
        			else{
        				for(j=queue.F;j<queue.L;j++){
        					if(b[i]==queue.a[j])
        						break;
        				}
        				if(j==queue.L){          //如果没有命中，页面进入内存
        					lose++;
        					queue.come(b[i]);
        				}
        			}
        			for(k=queue.F;k<queue.L;k++)
        				System.out.print(queue.a[k]+"  ");
        			System.out.print("\n");
        		}
    /    	
        		System.out.println("页面失效次数为："+lose);
        		hit_rate=1-(lose/320.0);
        		System.out.println("命中率="+hit_rate);
        		lose=0;
        		hit_rate=0;
     //   	}
        }  
    }  
    class Queue{      //队列
    	int a[]=new int[10000];
    	int F=0;
    	int L=0;
    	void come(int num){
    		if(L>=999)
    			System.out.println("队满");
    		a[L]=num;
    		L++;	
    	}
    	void out(){
    		if(F>L)
    			System.out.println("队空");
    		F++;
    	}
    	int isexit() {
    		if(L>F)
    			return 1;
    		else
    			return 0;
    	}
    	void exchange(int i){
    		int t;
    		t=a[F];a[F]=a[i];a[i]=t;
    	}
    }

![70][]

![70 1][]

[70]: /images/20220521/2a8d80f7176e4440b1c61f876a49d20d.png
[70 1]: /images/20220521/702d49b78a5c4125a65605c70d629cb6.png