实验二存储器管理

实验目的：

理解各类置换算法的原理和虚拟存储器管理的方法。

实验内容：

编程实现LRU算法或CLOCK/改进算法等置换算法（二选一），模拟实现虚拟存储器的地址变换过程。

实验步骤：

1.改进型CLOCK算法

（1）改进型ClOCK算法描述：

在将一个页面换出时，如果该页已被修改过，便须将该页重新写回到磁盘上；但如果该页未被修改过，则不必将它拷回磁盘。在改进型CLOCK算法中，除须考虑页面的使用情况外，还须在增加一个因素，即置换代价，这样页面换出时，既要是未使用过的页面，又要是未被修改过的页面。把同时满足这两个条件的页面作为首选淘汰的页面。由访问位A和修改位M可以组合成下面四种类型的页面:

1类（A=0，M=0）：表示该页最近既未被访问，又未被修改，是最佳淘汰页。

2类（A=0，M=1）：表示该页最近未被访问，但已被修改，并不是很好的淘汰页。

3类（A=1，M=0）：表示该页最近已被访问，但未被修改，该页有可能在被访问。

4类（A=1，M=1）：表示该页最近已被访问且被修改，该页可能再被访问。

（2）改进型CLOCK页面置换算法的数据结构

1）内存块类和页面类

类名

属性

作用

Block

页面page

修改位modify

访问位access

用于表示一个内存块单元

Page

页号page

修改位modify

用于表示一个页面

注：Page的modify是预设置好的，也就是说页面访问串是预先生成的，生成的内容包括页面号和访问位，也就模拟了系统运行时要访问的页面号和要修改的页面。

（3）简单ClOCK算法流程图

图1 简单Clock的页面置换算法

（4）改进型Clock页面置换算法流程图。

图2 改进型Clock页面置换算法流程图

2.改进型Clock算法的代码实现

（1）代码目录结构如图3所示。从上到下依次为内存块类，改进型页面置换算法及其测试代码，页面类。

图3 改进型Clock页面置换算法代码目录结构

（2）Page页面类的代码如下。

public class Page{
	int page = -1;
	int modify = 0;
public Page(int page,int modify){
    this.page = page;
    this.modify = modify;
}


}

（3）Block页面块的代码如下。

public class Block {
	int page = -1;
	int access = 0;
	int modify = 0;
}

（4）Clock页面置换算法及其测试类的代码如下。测试数据通过三种方式实现，一种是随机生成，一种是自己输入+随机，最后一种是自己输入。

import java.util.Random;
import java.util.Scanner;
//改进型的页面置换算法
public class ClockTest {
		
		public static void main(String[] args) {
		    int size = 3;
		    int pagesize = 10;
		    Scanner in = new Scanner(System.in);
		    System.out.println("**************************************************************");
		    System.out.println("*************************改进型clock算法***************************");
		    System.out.println("*************注:预先生成页面访问序列再去调用页面置换算法,同时设置修改位***************");
		    System.out.println("**************************************");
		    System.out.println("请输入内存块的大小：");
		    size = in.nextInt();
		    Block[] arr = new Block[size];
		    for(int i = 0;i < size;i++){
		        arr[i] = new Block();
		    }
		    System.out.println("请输入访问页面的容量");
		    pagesize = in.nextInt();
		    Page[] pages = new Page[pagesize];

		    System.out.println("请选择操作(输入数字1或2或3)：");
		    System.out.println("1、随机生成页面访问序列和修改位");
		    System.out.println("2、动态指定访问序列，随机生成修改位");
		    System.out.println("3、动态指定访问序列和修改位");
		    int action = in.nextInt();

		    Random random = new Random();
		    if(action == 1){
		        for(int i = 0;i < pagesize;i++){
		            pages[i] = new Page(random.nextInt(8),Math.abs(random.nextInt(10)%2));
		        }
		    }else if(action == 2){

		        for(int i = 0;i < pagesize;i++){
		            System.out.println("请输入第" + i + "个页号");
		            pages[i] = new Page(in.nextInt(),Math.abs(random.nextInt(10)%2));
		        }
		    }else if(action ==3){
		        for(int i = 0;i < pagesize;i++){
		            System.out.println("请输入第" + i + "个页号和是否被会被修改(1为修改0为未修改)");
		            pages[i] = new Page(in.nextInt(),in.nextInt());//模拟页号为1的页面不会被修改
		        }
		    }
		    System.out.println("===要访问的页面串如下===");
		    System.out.println("页面号\t是否被修改");
		    for (Page page : pages) {
		        System.out.println(page.page+"\t"+page.modify);
		    }
		    clock(arr,pages);
		}
	
		public static void clock(Block[] block,Page[] page){
		    boolean flag = false; 
		    int count = 0;   //缺页数
		    for(int i = 0;i < page.length;i++){
		    	 System.out.println("页面置换前的内存块的使用情况");
		    	 System.out.println("页面号\t"+"访问位\t"+"修改位\t");
		        for (int m = 0;m < block.length;m++) {
		        	
		            System.out.println( block[m].page +"\t" + block[m].access + "\t"+block[m].modify);
		        }
		        System.out.println("将要访问的页面---"+page[i].page);
		        if(contain(block,page[i])){
		            System.out.println("命中！");
		            System.out.println("页面号\t"+"访问位\t"+"修改位\t");
			        for (int m = 0;m < block.length;m++) {
			        	
			            System.out.println( block[m].page +"\t" + block[m].access + "\t"+block[m].modify);
			        }
		            System.out.println("*****************************************");
		            continue;
		        }else{
		            System.out.println("缺页...");
		            count++;
		            flag = false;
		        }

		    
		        while(!flag){
		        	
		            for(int j = 0;j < block.length;j++){
		                if(block[j].access == 0 && block[j].modify == 0){
		                    block[j].page = page[i].page;
		                    block[j].access = 1;
		                    block[j].modify=page[i].modify;
		                    flag = true;
		                    break;
		                }
		            }
		           
		            if(flag){
		                break;
		            }

		            for(int j = 0;j < block.length;j++){

		                if(block[j].access == 0 && block[j].modify == 1){
		                    block[j].page = page[i].page;
		                    block[j].access = 1;
		                    flag = true;
		                    break;
		                }else{
		                    block[j].access = 0;
		                }
		            }
		        }
		        System.out.println("页面号\t"+"访问位\t"+"修改位\t");
		        for (int m = 0;m < block.length;m++) {
		        	
		            System.out.println( block[m].page +"\t" + block[m].access + "\t"+block[m].modify);
		        }		        System.out.println("*****************************************");
		    }

		    System.out.println("缺页次数：" + count);
		    System.out.println("缺页率：" + (count*1.0)/page.length);
		}

		public static boolean contain(Block[] block,Page page){
		    for(int i = 0;i < block.length;i++){
		        if(block[i].page == page.page){
		            block[i].page = page.page;
		            block[i].access = 1;
		            block[i].modify = page.modify;
		            return true;
		        }
		    }
		    return false;
		}
		}

（5）改进型Clcok页面置换算法的测试。

1）针对3个内存块，8个页面访问序列的情况的测试效果如图4-图6所示，图4采用的是随机生成的数据，图5页面置换的过程，图6显示的是缺页次数和缺页率。注：-1代表内存块未使用。

测试：输入内存块3，页面大小8，采用1随机的方式

暂无，详见文字描述

图4 页面数据初始化