页面置换算法是指在需要调入页面且内存已满时，确定将要换出页面的算法。置换算法的好坏将直接影响系统的性能。不适当的算法可能会导致进程发生”抖动”。即刚被换出的页很快又被访问，需重新调入，为此，有需要再选一页调出，而此刚被换出的页，很快又要被访问，因而又需要将他调入，为此频繁的更换页面，以致一个进程在运行中，将大部分时间花在完成页面置换的工作上。
实验目的
通过模拟实现实现请求页式存储管理的基本几种页面置换算法，了解虚拟存储技术的特点，掌握虚拟存储请求页式存储管理中的基本页面置换算法的基本思想和实现过程，并比较他们的效率。
实验内容
设计一个虚拟存储区和内存工作区，并使用下述算法访问命中率
-
最佳淘汰算法（OPT）。
-
先进先出算法（FIFO）。
-
最近最久未使用算法（LRU）。
实验指导
-
假设分给一作业的内存块数为4，每条指令占一个存储单元，每个页面中可存放10条指令。
-
设计一个程序，模拟一作业的执行过程。设改作业共有160条指令，即他们的地址空间为16页，最初作业的所有页面都还未调入内存。在模拟过程中，如果所访问的指令都已经在内存，则显示其物理地址，并转吓一条指令。如果所访问的指令都未装入内存，则发生缺页，此时需要记录缺页的次数，并将相应页调入内存。如果4个内存块中均已装入该作业的虚页面，则需进行页面置换；在所有200条指令执行完毕后，请计算并显示作业运行过程中发生的缺页率。
-
作业中指令的访问次序要按如下原则生成。
具体实施的办法是：
- 在[0,159]之间随机选举一条起始执行指令，其序号为 m ;
- 顺序执行两条指令，即序号为 m+1 、m+2 的指令;
- 通过随机数，跳转到前地址部分[0,m-1]中的某条指令处，其序号为 m1;
- 顺序执行两条指令，即序号为 m1+1 、m1+2的指令;
- 通过随机数，跳转到后地址部分[m1+3,159]中的某条指令处，其序号为 m2;
- 顺序执行两条指令，即序号为 m2+1、m2+2 的指令;若 m2+2>159 只执行一条指令;
- 重复 “跳转到前地址部分、顺序执行、跳转到后地址部分、顺序执行” 的过程，直至执行完全部200条指令。
实验过程
代码目录结构
先按要求生成随机条指令
代码
package com.yb.test4;
import org.junit.Test;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
/**
* 随机生成指令
* Created by 杨波 on 2016/11/23.
*/
public class RandList {
private int m0,m1,m2,m3;
@Test
public void randList(){
Random random = new Random();
List<Integer> integerList = new ArrayList<Integer>();
//生成0-159之间的随机数nextint(int n)表示区间[0,n)取随机整数
m0 = random.nextInt(160);
for (int i=0;i<20;i++) {
integerList.add(m0);
integerList.add(m0 + 1);
integerList.add(m0 + 2);
if(m0==0) {
m1=m0;
}else {
//向前取
m1 = random.nextInt(m0);
}
integerList.add(m1);
integerList.add(m1 + 1);
integerList.add(m1 + 2);
//向后取
m2 = random.nextInt(160 - m1 - 3) + m1+3;
integerList.add(m2);
integerList.add(m2 + 1);
integerList.add(m2 + 2);
if(m2==0) {
m3=m2;
}else {
//向前取
m3 = random.nextInt(m2);
}
integerList.add(m3);
integerList.add(m3+1);
integerList.add(m3+2);
m0 = random.nextInt(160 - m3 - 3) + m3+3;
}
//讲大于159的数remove
for (int i=0;i<integerList.size();){
if (integerList.get(i)>159){
integerList.remove(i);
} else {
//integerList.set(i,integerList.get(i)/10);
i++;
}
}
/*List<Integer> lists =new ArrayList<Integer>();
for (int i=0;i<200;i++){
lists.add(i,integerList.get(1));
*//*if ((i+1)%20==0){
System.out.println();
}*//*
}*/
System.out.println("生成的指令,总共有"+integerList.size()+"个指令");
for (Integer integer:integerList){
System.out.print(integer+" ");
}
System.out.println();
//System.out.println(lists.size());
//return integerList;
}
}
使用Random.nextInt(int n)取随机数,根据要求生成大于200个的指令，在截取前200个指令
测试输出生成的指令
85 86 87 4 5 6 89 90 91 44 45 46 129 130 131 126 127 128 158 159 51 52 53 123 124 125 11 12 13 25 26 27 12 13 14 59 60 61 54 55 56 83 84 85 9 10 11 94 95 96 39 40 41 55 56 57 47 48 49 86 87 88 63 64 65 92 93 94 41 42 43 133 134 135 64 65 66 158 159 43 44 45 85 86 87 28 29 30 120 121 122 0 1 2 66 67 68 64 65 66 81 82 83 29 30 31 46 47 48 8 9 10 24 25 26 23 24 25 58 59 60 19 20 21 121 122 123 87 88 89 111 112 113 103 104 105 151 152 153 48 49 50 117 118 119 94 95 96 151 152 153 43 44 45 146 147 148 33 34 35 129 130 131 50 51 52 128 129 130 80 81 82 142 143 144 48 49 50 55 56 57 2 3 4 67 68 69 63 64 65 92 93 94 79 80 81 136 137 138 62 63 64 150 151 152 52 53 54 125 126 127 116 117 118 158 159 15 16 17 120 121 122 23 24 25 81 82 83 37 38 39 109 110 111 103 104 105
重复测试了多次，指令满足要求，因为每个页面可存放10个指令，只需讲指令 /10 操作即可
创建一个Page类，生成get set方法
package com.yb.test4;
/**
* Created by 杨波 on 2016/11/23.
*/
public class Page {
private int id = -1;
private int count;
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public int getCount() {
return count;
}
public void inc() {
count ++;
}
public void setCount(int count) {
this.count = count;
}
}
实现FIFO算法（先进先出）
代码
package com.yb.test4;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
/**
* 先进先出算法
* Created by 杨波 on 2016/11/23.
*/
public class FIFO {
private static final int PRO_MEMORY = 4;//系统分配的内存块数
private static Page[] pages = new Page[PRO_MEMORY];
private static int countOldPoint ;//纪录最久的页面下标
private static int count ;//纪录当前在使用的总页面数
private static int lackTime;//缺页次数
private List<Integer> usePageNumList = new ArrayList<Integer>();//页面使用列表
/**初始化*/
public void init(){
for(int i=0;i<pages.length;i++){
pages[i] = new Page();
}
}
/**接受传过来的list集合*/
public void input(List<Integer> lists){
/*System.out.println("传进去的list");
for (Integer integer:lists){
System.out.print(integer+" ");
}
System.out.println();*/
for(int i=0;i<200;i++){
usePageNumList.add(i,lists.get(i));
}
//System.out.println("接受到的指令,总共"+usePageNumList.size()+"个指令");
for (Integer integer:usePageNumList){
System.out.print(integer+" ");
}
System.out.println();
}
/**系统运行*/
public void running(){
Iterator<Integer> it = usePageNumList.iterator();
//列表置入替换
while(it.hasNext()){
countOldPoint = countOldPoint % PRO_MEMORY;
int inPageId = it.next();
//查找内存中是否有该页面
if(search(inPageId)){
System.out.println("内存中有"+inPageId+" ,不置换");
}
else if(count<PRO_MEMORY){//有空闲内存页
pages[count].setId( (Integer)inPageId);
System.out.println("页面"+pages[count].getId()+" 进入内存");
count ++;
}
else{//替换
replace(inPageId);
lackTime ++;
countOldPoint ++;
}
display();
}
System.out.println("缺页次数为:"+lackTime+",缺页率是:"+(float)lackTime/usePageNumList.size());
}
/**查找内存中是否有该页面*/
public boolean search(int pageId){
for(int i=0;i<pages.length;i++){
if(pages[i].getId() == pageId){
return true;
}
}
return false;
}
/**置换算法*/
public void replace(int pageId){
//置换最久的页面
int outPageId = -1;
outPageId = pages[countOldPoint].getId();
pages[countOldPoint].setId(pageId);
System.out.println("页面"+pageId+" 进入内存, "+outPageId+"被置换出去");
}
/**显示当前内存页*/
public void display(){
System.out.print("当前内存的页面:");
for(Page page : pages){
System.out.print(page.getId()+" ");
}
System.out.println();
}
}
测试FIFO
/**测试FIFO算法*/
@Test
public void testFIFO(){
System.out.println();
System.out.println();
System.out.println("**FIFO，先进先出置换算法**");
FIFO fifo = new FIFO();
fifo.init();
fifo.input(lists);
fifo.running();
}
多次测试结果之一如下
FIFO，先进先出置换算法 接受到的指令,总共200个指令 6 6 6 3 3 3 11 11 11 6 7 7 8 8 8 0 1 1 2 2 2 2 2 2 9 9 9 8 8 8 15 15 15 1 1 1 14 14 14 2 2 2 14 14 14 1 1 1 15 9 9 9 14 14 14 3 3 3 7 7 7 5 5 5 13 13 13 2 2 2 15 15 15 1 1 1 11 11 11 8 8 8 12 12 12 3 3 3 9 9 9 3 3 4 7 7 7 5 5 5 8 8 8 2 2 2 5 5 5 3 3 4 12 12 12 7 7 7 13 14 14 6 6 6 13 13 13 8 8 8 11 11 11 0 0 0 8 8 8 6 6 6 11 11 11 7 7 7 12 12 12 6 6 7 11 11 11 5 5 5 8 8 8 1 1 2 4 4 4 2 2 2 10 10 10 6 6 6 9 9 9 1 1 1 15 15 15 11 11 11 15 15 15 1 2 2 15 15 15 10 页面6 进入内存 当前内存的页面:6 -1 -1 -1 内存中有6 ,不置换 当前内存的页面:6 -1 -1 -1 内存中有6 ,不置换 当前内存的页面:6 -1 -1 -1 页面3 进入内存 当前内存的页面:6 3 -1 -1 内存中有3 ,不置换 当前内存的页面:6 3 -1 -1 内存中有3 ,不置换 当前内存的页面:6 3 -1 -1 页面11 进入内存 当前内存的页面:6 3 11 -1 内存中有11 ,不置换 当前内存的页面:6 3 11 -1 内存中有11 ,不置换 当前内存的页面:6 3 11 -1 内存中有6 ,不置换 当前内存的页面:6 3 11 -1 页面7 进入内存 当前内存的页面:6 3 11 7 内存中有7 ,不置换 当前内存的页面:6 3 11 7 页面8 进入内存, 6被置换出去 当前内存的页面:8 3 11 7 内存中有8 ,不置换 当前内存的页面:8 3 11 7 内存中有8 ,不置换 当前内存的页面:8 3 11 7 页面0 进入内存, 3被置换出去 当前内存的页面:8 0 11 7 页面1 进入内存, 11被置换出去 当前内存的页面:8 0 1 7 内存中有1 ,不置换 当前内存的页面:8 0 1 7 页面2 进入内存, 7被置换出去 当前内存的页面:8 0 1 2 内存中有2 ,不置换 当前内存的页面:8 0 1 2 内存中有2 ,不置换 当前内存的页面:8 0 1 2 内存中有2 ,不置换 当前内存的页面:8 0 1 2 内存中有2 ,不置换 当前内存的页面:8 0 1 2 内存中有2 ,不置换 当前内存的页面:8 0 1 2 页面9 进入内存, 8被置换出去 当前内存的页面:9 0 1 2 内存中有9 ,不置换 当前内存的页面:9 0 1 2 内存中有9 ,不置换 当前内存的页面:9 0 1 2 页面8 进入内存, 0被置换出去 当前内存的页面:9 8 1 2 内存中有8 ,不置换 当前内存的页面:9 8 1 2 内存中有8 ,不置换 当前内存的页面:9 8 1 2 页面15 进入内存, 1被置换出去 当前内存的页面:9 8 15 2 内存中有15 ,不置换 当前内存的页面:9 8 15 2 内存中有15 ,不置换 当前内存的页面:9 8 15 2 页面1 进入内存, 2被置换出去 当前内存的页面:9 8 15 1 内存中有1 ,不置换 当前内存的页面:9 8 15 1 内存中有1 ,不置换 当前内存的页面:9 8 15 1 页面14 进入内存, 9被置换出去 当前内存的页面:14 8 15 1 内存中有14 ,不置换 当前内存的页面:14 8 15 1 内存中有14 ,不置换 当前内存的页面:14 8 15 1 页面2 进入内存, 8被置换出去 当前内存的页面:14 2 15 1 内存中有2 ,不置换 当前内存的页面:14 2 15 1 内存中有2 ,不置换 当前内存的页面:14 2 15 1 内存中有14 ,不置换 当前内存的页面:14 2 15 1 内存中有14 ,不置换 当前内存的页面:14 2 15 1 内存中有14 ,不置换 当前内存的页面:14 2 15 1 内存中有1 ,不置换 当前内存的页面:14 2 15 1 内存中有1 ,不置换 当前内存的页面:14 2 15 1 内存中有1 ,不置换 当前内存的页面:14 2 15 1 内存中有15 ,不置换 当前内存的页面:14 2 15 1 页面9 进入内存, 15被置换出去 当前内存的页面:14 2 9 1 内存中有9 ,不置换 当前内存的页面:14 2 9 1 内存中有9 ,不置换 当前内存的页面:14 2 9 1 内存中有14 ,不置换 当前内存的页面:14 2 9 1 内存中有14 ,不置换 当前内存的页面:14 2 9 1 内存中有14 ,不置换 当前内存的页面:14 2 9 1 页面3 进入内存, 1被置换出去 当前内存的页面:14 2 9 3 内存中有3 ,不置换 当前内存的页面:14 2 9 3 内存中有3 ,不置换 当前内存的页面:14 2 9 3 页面7 进入内存, 14被置换出去 当前内存的页面:7 2 9 3 内存中有7 ,不置换 当前内存的页面:7 2 9 3 内存中有7 ,不置换 当前内存的页面:7 2 9 3 页面5 进入内存, 2被置换出去 当前内存的页面:7 5 9 3 内存中有5 ,不置换 当前内存的页面:7 5 9 3 内存中有5 ,不置换 当前内存的页面:7 5 9 3 页面13 进入内存, 9被置换出去 当前内存的页面:7 5 13 3 内存中有13 ,不置换 当前内存的页面:7 5 13 3 内存中有13 ,不置换 当前内存的页面:7 5 13 3 页面2 进入内存, 3被置换出去 当前内存的页面:7 5 13 2 内存中有2 ,不置换 当前内存的页面:7 5 13 2 内存中有2 ,不置换 当前内存的页面:7 5 13 2 页面15 进入内存, 7被置换出去 当前内存的页面:15 5 13 2 内存中有15 ,不置换 当前内存的页面:15 5 13 2 内存中有15 ,不置换 当前内存的页面:15 5 13 2 页面1 进入内存, 5被置换出去 当前内存的页面:15 1 13 2 内存中有1 ,不置换 当前内存的页面:15 1 13 2 内存中有1 ,不置换 当前内存的页面:15 1 13 2 页面11 进入内存, 13被置换出去 当前内存的页面:15 1 11 2 内存中有11 ,不置换 当前内存的页面:15 1 11 2 内存中有11 ,不置换 当前内存的页面:15 1 11 2 页面8 进入内存, 2被置换出去 当前内存的页面:15 1 11 8 内存中有8 ,不置换 当前内存的页面:15 1 11 8 内存中有8 ,不置换 当前内存的页面:15 1 11 8 页面12 进入内存, 15被置换出去 当前内存的页面:12 1 11 8 内存中有12 ,不置换 当前内存的页面:12 1 11 8 内存中有12 ,不置换 当前内存的页面:12 1 11 8 页面3 进入内存, 1被置换出去 当前内存的页面:12 3 11 8 内存中有3 ,不置换 当前内存的页面:12 3 11 8 内存中有3 ,不置换 当前内存的页面:12 3 11 8 页面9 进入内存, 11被置换出去 当前内存的页面:12 3 9 8 内存中有9 ,不置换 当前内存的页面:12 3 9 8 内存中有9 ,不置换 当前内存的页面:12 3 9 8 内存中有3 ,不置换 当前内存的页面:12 3 9 8 内存中有3 ,不置换 当前内存的页面:12 3 9 8 页面4 进入内存, 8被置换出去 当前内存的页面:12 3 9 4 页面7 进入内存, 12被置换出去 当前内存的页面:7 3 9 4 内存中有7 ,不置换 当前内存的页面:7 3 9 4 内存中有7 ,不置换 当前内存的页面:7 3 9 4 页面5 进入内存, 3被置换出去 当前内存的页面:7 5 9 4 内存中有5 ,不置换 当前内存的页面:7 5 9 4 内存中有5 ,不置换 当前内存的页面:7 5 9 4 页面8 进入内存, 9被置换出去 当前内存的页面:7 5 8 4 内存中有8 ,不置换 当前内存的页面:7 5 8 4 内存中有8 ,不置换 当前内存的页面:7 5 8 4 页面2 进入内存, 4被置换出去 当前内存的页面:7 5 8 2 内存中有2 ,不置换 当前内存的页面:7 5 8 2 内存中有2 ,不置换 当前内存的页面:7 5 8 2 内存中有5 ,不置换 当前内存的页面:7 5 8 2 内存中有5 ,不置换 当前内存的页面:7 5 8 2 内存中有5 ,不置换 当前内存的页面:7 5 8 2 页面3 进入内存, 7被置换出去 当前内存的页面:3 5 8 2 内存中有3 ,不置换 当前内存的页面:3 5 8 2 页面4 进入内存, 5被置换出去 当前内存的页面:3 4 8 2 页面12 进入内存, 8被置换出去 当前内存的页面:3 4 12 2 内存中有12 ,不置换 当前内存的页面:3 4 12 2 内存中有12 ,不置换 当前内存的页面:3 4 12 2 页面7 进入内存, 2被置换出去 当前内存的页面:3 4 12 7 内存中有7 ,不置换 当前内存的页面:3 4 12 7 内存中有7 ,不置换 当前内存的页面:3 4 12 7 页面13 进入内存, 3被置换出去 当前内存的页面:13 4 12 7 页面14 进入内存, 4被置换出去 当前内存的页面:13 14 12 7 内存中有14 ,不置换 当前内存的页面:13 14 12 7 页面6 进入内存, 12被置换出去 当前内存的页面:13 14 6 7 内存中有6 ,不置换 当前内存的页面:13 14 6 7 内存中有6 ,不置换 当前内存的页面:13 14 6 7 内存中有13 ,不置换 当前内存的页面:13 14 6 7 内存中有13 ,不置换 当前内存的页面:13 14 6 7 内存中有13 ,不置换 当前内存的页面:13 14 6 7 页面8 进入内存, 7被置换出去 当前内存的页面:13 14 6 8 内存中有8 ,不置换 当前内存的页面:13 14 6 8 内存中有8 ,不置换 当前内存的页面:13 14 6 8 页面11 进入内存, 13被置换出去 当前内存的页面:11 14 6 8 内存中有11 ,不置换 当前内存的页面:11 14 6 8 内存中有11 ,不置换 当前内存的页面:11 14 6 8 页面0 进入内存, 14被置换出去 当前内存的页面:11 0 6 8 内存中有0 ,不置换 当前内存的页面:11 0 6 8 内存中有0 ,不置换 当前内存的页面:11 0 6 8 内存中有8 ,不置换 当前内存的页面:11 0 6 8 内存中有8 ,不置换 当前内存的页面:11 0 6 8 内存中有8 ,不置换 当前内存的页面:11 0 6 8 内存中有6 ,不置换 当前内存的页面:11 0 6 8 内存中有6 ,不置换 当前内存的页面:11 0 6 8 内存中有6 ,不置换 当前内存的页面:11 0 6 8 内存中有11 ,不置换 当前内存的页面:11 0 6 8 内存中有11 ,不置换 当前内存的页面:11 0 6 8 内存中有11 ,不置换 当前内存的页面:11 0 6 8 页面7 进入内存, 6被置换出去 当前内存的页面:11 0 7 8 内存中有7 ,不置换 当前内存的页面:11 0 7 8 内存中有7 ,不置换 当前内存的页面:11 0 7 8 页面12 进入内存, 8被置换出去 当前内存的页面:11 0 7 12 内存中有12 ,不置换 当前内存的页面:11 0 7 12 内存中有12 ,不置换 当前内存的页面:11 0 7 12 页面6 进入内存, 11被置换出去 当前内存的页面:6 0 7 12 内存中有6 ,不置换 当前内存的页面:6 0 7 12 内存中有7 ,不置换 当前内存的页面:6 0 7 12 页面11 进入内存, 0被置换出去 当前内存的页面:6 11 7 12 内存中有11 ,不置换 当前内存的页面:6 11 7 12 内存中有11 ,不置换 当前内存的页面:6 11 7 12 页面5 进入内存, 7被置换出去 当前内存的页面:6 11 5 12 内存中有5 ,不置换 当前内存的页面:6 11 5 12 内存中有5 ,不置换 当前内存的页面:6 11 5 12 页面8 进入内存, 12被置换出去 当前内存的页面:6 11 5 8 内存中有8 ,不置换 当前内存的页面:6 11 5 8 内存中有8 ,不置换 当前内存的页面:6 11 5 8 页面1 进入内存, 6被置换出去 当前内存的页面:1 11 5 8 内存中有1 ,不置换 当前内存的页面:1 11 5 8 页面2 进入内存, 11被置换出去 当前内存的页面:1 2 5 8 页面4 进入内存, 5被置换出去 当前内存的页面:1 2 4 8 内存中有4 ,不置换 当前内存的页面:1 2 4 8 内存中有4 ,不置换 当前内存的页面:1 2 4 8 内存中有2 ,不置换 当前内存的页面:1 2 4 8 内存中有2 ,不置换 当前内存的页面:1 2 4 8 内存中有2 ,不置换 当前内存的页面:1 2 4 8 页面10 进入内存, 8被置换出去 当前内存的页面:1 2 4 10 内存中有10 ,不置换 当前内存的页面:1 2 4 10 内存中有10 ,不置换 当前内存的页面:1 2 4 10 页面6 进入内存, 1被置换出去 当前内存的页面:6 2 4 10 内存中有6 ,不置换 当前内存的页面:6 2 4 10 内存中有6 ,不置换 当前内存的页面:6 2 4 10 页面9 进入内存, 2被置换出去 当前内存的页面:6 9 4 10 内存中有9 ,不置换 当前内存的页面:6 9 4 10 内存中有9 ,不置换 当前内存的页面:6 9 4 10 页面1 进入内存, 4被置换出去 当前内存的页面:6 9 1 10 内存中有1 ,不置换 当前内存的页面:6 9 1 10 内存中有1 ,不置换 当前内存的页面:6 9 1 10 页面15 进入内存, 10被置换出去 当前内存的页面:6 9 1 15 内存中有15 ,不置换 当前内存的页面:6 9 1 15 内存中有15 ,不置换 当前内存的页面:6 9 1 15 页面11 进入内存, 6被置换出去 当前内存的页面:11 9 1 15 内存中有11 ,不置换 当前内存的页面:11 9 1 15 内存中有11 ,不置换 当前内存的页面:11 9 1 15 内存中有15 ,不置换 当前内存的页面:11 9 1 15 内存中有15 ,不置换 当前内存的页面:11 9 1 15 内存中有15 ,不置换 当前内存的页面:11 9 1 15 内存中有1 ,不置换 当前内存的页面:11 9 1 15 页面2 进入内存, 9被置换出去 当前内存的页面:11 2 1 15 内存中有2 ,不置换 当前内存的页面:11 2 1 15 内存中有15 ,不置换 当前内存的页面:11 2 1 15 内存中有15 ,不置换 当前内存的页面:11 2 1 15 内存中有15 ,不置换 当前内存的页面:11 2 1 15 页面10 进入内存, 1被置换出去 当前内存的页面:11 2 10 15 缺页次数为:55,缺页率是:0.275
缺页率在0.275左右
实现LRU算法（最近最久未使用）
代码
package com.yb.test4;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
/**
* 最近最久未使用算法
* Created by 杨波 on 2016/11/23.
*/
public class LRU {
private static final int PRO_MEMORY = 4;//系统分配的内存块数
private static Page[] pages = new Page[PRO_MEMORY];
private static int count ;//纪录当前在使用的总页面数
private static int lackTime;//缺页次数
private List<Integer> usePageNumList = new ArrayList<Integer>();//页面使用列表
/**初始化*/
public void init(){
for(int i=0;i<pages.length;i++){
pages[i] = new Page();
}
}
/**接受传过来的list集合*/
public void input(List<Integer> lists){
for(int i=0;i<200;i++){
usePageNumList.add(i,lists.get(i));
}
System.out.println("接受到的指令,总共"+usePageNumList.size()+"个指令");
for (Integer integer:usePageNumList){
System.out.print(integer+" ");
}
System.out.println();
}
/**系统运行*/
public void running(){
Iterator<Integer> it = usePageNumList.iterator();
//列表置入替换
while(it.hasNext()){
int inPageId = it.next();
//查找内存中是否有该页面
if(search(inPageId)){
System.out.println("内存中有"+inPageId+" ,不置换");
}
else if(count<PRO_MEMORY){//有空闲内存页
pages[count].setId( (Integer)inPageId);
System.out.println("页面"+pages[count].getId()+" 进入内存");
reSet(count);
count ++;
timeRefresh();
}
else{//替换
replace(inPageId);
timeRefresh();
lackTime ++;
}
display();
}
System.out.println("缺页次数为:"+lackTime+",缺页率是:"+(float)lackTime/usePageNumList.size());
}
/**查找内存中是否有该页面*/
public boolean search(int pageId){
for(int i=0;i<pages.length;i++){
if(pages[i].getId() == pageId){
timeRefresh();
reSet(i);
return true;
}
}
return false;
}
/**访问后置0*/
public void reSet(int cur){
pages[cur].setCount(0);
}
/**刷新*/
public void timeRefresh(){
for(Page page : pages){
page.inc();
}
}
/**置换算法*/
public void replace(int pageId){
//寻找时间数最大的页面
int max = 0,perCount,outPageId = -1,cur = 0;//cur为下标
for(int i=0;i<pages.length;i++){
perCount = pages[i].getCount();
if(max<perCount){
max = perCount;
outPageId = pages[i].getId();//换出去的页号
cur = i;
}
}
reSet(cur);
pages[cur].setId(pageId);
System.out.println("页面"+pageId+" 进入内存, "+outPageId+"被置换出去");
}
/**显示当前内存页*/
public void display(){
System.out.print("当前内存的页面:");
for(Page page : pages){
System.out.print(page.getId()+" ");
}
System.out.println();
}
}
测试LRU
/**测试LRU算法*/
@Test
public void testLRU(){
System.out.println();
System.out.println();
System.out.println("**LRU，最近最久未使用置换算法**");
LRU lru = new LRU();
lru.init();
lru.input(lists);
lru.running();
}
结果
LRU，最近最久未使用置换算法 接受到的指令,总共200个指令 1 1 1 1 1 1 12 12 12 1 1 1 5 5 5 1 1 2 8 8 8 5 5 5 6 6 6 5 5 5 7 7 7 0 1 1 4 4 4 1 2 2 11 11 11 1 1 1 13 13 13 12 13 13 14 14 14 1 2 2 14 14 14 6 6 6 14 14 14 7 7 7 15 14 14 14 15 15 15 8 8 8 12 12 12 3 3 3 5 6 6 3 3 3 14 14 14 2 2 2 8 8 8 3 4 4 11 11 11 5 5 5 6 6 6 3 3 3 11 11 11 7 7 7 10 10 10 3 3 3 12 12 13 1 1 1 8 8 8 6 6 6 15 15 15 5 5 5 15 15 15 11 11 11 13 13 13 9 9 9 14 14 14 0 0 0 4 4 4 0 0 0 10 10 10 3 3 3 15 14 14 14 15 15 15 11 11 11 13 13 14 5 5 5 15 15 15 0 0 0 页面1 进入内存 当前内存的页面:1 -1 -1 -1 内存中有1 ,不置换 当前内存的页面:1 -1 -1 -1 内存中有1 ,不置换 当前内存的页面:1 -1 -1 -1 内存中有1 ,不置换 当前内存的页面:1 -1 -1 -1 内存中有1 ,不置换 当前内存的页面:1 -1 -1 -1 内存中有1 ,不置换 当前内存的页面:1 -1 -1 -1 页面12 进入内存 当前内存的页面:1 12 -1 -1 内存中有12 ,不置换 当前内存的页面:1 12 -1 -1 内存中有12 ,不置换 当前内存的页面:1 12 -1 -1 内存中有1 ,不置换 当前内存的页面:1 12 -1 -1 内存中有1 ,不置换 当前内存的页面:1 12 -1 -1 内存中有1 ,不置换 当前内存的页面:1 12 -1 -1 ……
中间结果省略
……
内存中有15 ,不置换 当前内存的页面:14 5 13 15 页面0 进入内存, 13被置换出去 当前内存的页面:14 5 0 15 内存中有0 ,不置换 当前内存的页面:14 5 0 15 内存中有0 ,不置换 当前内存的页面:14 5 0 15 缺页次数为:52,缺页率是:0.26
缺页率在0.26左右
实现OPT算法（最佳）
代码
package com.yb.test4;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
/**
* 最佳置换算法
* Created by 杨波 on 2016/11/23.
*/
public class OPT {
private static final int PRO_MEMORY = 4;//系统分配的内存块数
private static Page[] pages = new Page[PRO_MEMORY];
private static int count ;//纪录当前在使用的总页面数
private static int lackTime;//缺页次数
private List<Integer> usePageNumList = new ArrayList<Integer>();//页面使用列表
/**初始化*/
public void init(){
for(int i=0;i<pages.length;i++){
pages[i] = new Page();
}
}
/**接受传过来的list集合*/
public void input(List<Integer> lists){
for(int i=0;i<200;i++){
usePageNumList.add(i,lists.get(i));
}
System.out.println("接受到的指令,总共"+usePageNumList.size()+"个指令");
for (Integer integer:usePageNumList){
System.out.print(integer+" ");
}
System.out.println();
}
/**系统运行*/
public void running(){
Iterator<Integer> it = usePageNumList.iterator();
int currentPoint = 0;//当前读取输入列表的下标
//列表置入替换
while(it.hasNext()){
int inPageId = it.next();
//查找内存中是否有该页面
if(search(inPageId)){
System.out.println("内存中有"+inPageId+" ,不置换");
}
else if(count<PRO_MEMORY){//有空闲内存页
pages[count].setId( (Integer)inPageId);
System.out.println(pages[count].getId()+" 进入内存");
count ++;
timeRefresh();
}
else{//替换
replace(inPageId,currentPoint);//传入当前下标确定需要遍历的未来输入列表
timeRefresh();
lackTime ++;
}
currentPoint ++;
display();
}
System.out.println("缺页次数为:"+lackTime+",缺页率是:"+(float)lackTime/usePageNumList.size());
}
/**查找内存中是否有该页面*/
public boolean search(int pageId){
for(int i=0;i<pages.length;i++){
if(pages[i].getId() == pageId){
timeRefresh();
return true;
}
}
return false;
}
/**刷新*/
public void timeRefresh(){
for(Page page : pages){
page.inc();
}
}
/**置换算法*/
public void replace(int pageId,int currentPoint){
//寻找最长时间不使用的页面,count最大的内存块
int max = 0,perCount,outPageId = -1,cur = 0,searchCounter=0;//cur为内存块下标,searchCounter纪录是否内存块搜索完毕
//循环爆出最长为使用的页面
for(int i=currentPoint+1;i<usePageNumList.size();i++){
for(Page page : pages){
if(page.getId() == usePageNumList.get(i)){
searchCounter ++;
}
else{
page.inc();//未找到则增长值
}
}
if(searchCounter == pages.length){
break;
}
}
//进行搜索,查找替换目标
for(int i=0;i<pages.length;i++){
perCount = pages[i].getCount();
if(max<perCount){
max = perCount;
cur = i;
outPageId = pages[i].getId();
}
// System.out.println("--------当前-页号count------->"+perCount);
}
pages[cur].setId(pageId);
System.out.println(pageId+" 进入内存, "+outPageId+"被置换出去");
reSet();
}
/**搜索完毕进行重置*/
public void reSet(){
for(Page page : pages){
page.setCount(0);
}
}
/**显示当前内存页*/
public void display(){
System.out.print("当前内存的页面:");
for(Page page : pages){
System.out.print(page.getId()+" ");
}
System.out.println();
}
}
测试OPT
/**测试OPT算法*/
@Test
public void testOPT(){
System.out.println();
System.out.println();
System.out.println("**OPT：最佳置换算法**");
OPT opt = new OPT();
opt.init();
opt.input(lists);
opt.running();
}
结果
OPT：最佳置换算法 接受到的指令,总共200个指令 4 4 4 1 1 1 14 14 14 9 9 9 10 10 10 3 3 3 14 14 14 4 4 4 7 7 7 7 7 7 13 13 14 3 3 3 9 10 10 0 0 0 15 15 15 9 9 9 11 11 11 0 0 0 4 4 4 1 1 1 15 15 15 5 5 5 10 10 11 5 5 5 7 7 7 0 0 0 4 5 5 1 1 1 15 15 15 2 2 2 11 11 11 10 10 10 14 14 14 7 7 7 7 7 7 0 0 0 1 1 1 0 0 0 13 13 13 9 9 9 11 11 11 1 1 1 5 5 5 0 0 0 3 3 3 2 2 2 3 3 3 0 0 0 3 3 3 2 2 3 6 6 6 6 6 6 10 10 10 2 2 2 13 13 13 12 12 12 15 5 5 5 9 9 9 7 8 8 10 10 10 9 9 9 13 13 13 13 13 13 15 15 15 10 10 10 11 11 11 2 页面4 进入内存 当前内存的页面:4 -1 -1 -1 内存中有4 ,不置换 当前内存的页面:4 -1 -1 -1 内存中有4 ,不置换 当前内存的页面:4 -1 -1 -1 页面1 进入内存 当前内存的页面:4 1 -1 -1 内存中有1 ,不置换 当前内存的页面:4 1 -1 -1 内存中有1 ,不置换 当前内存的页面:4 1 -1 -1 页面14 进入内存 当前内存的页面:4 1 14 -1
……
中间结果省略
……
页面11 进入内存, 15被置换出去 当前内存的页面:11 10 3 9 内存中有11 ,不置换 当前内存的页面:11 10 3 9 内存中有11 ,不置换 当前内存的页面:11 10 3 9 页面2 进入内存, 11被置换出去 当前内存的页面:2 10 3 9 缺页次数为:39,缺页率是:0.195
缺页率在0.195左右
将三种算法放在一起测试
/**三个一起测试*/
@Test
public void testAll(){
System.out.println();
System.out.println();
System.out.println("**三种算法一起测试比较**");
testOPT();
testFIFO();
testLRU();
}
结果
三种算法一起测试比较 OPT：最佳置换算法
缺页次数为:43,缺页率是:0.215 FIFO，先进先出置换算法
缺页次数为:54,缺页率是:0.27 LRU，最近最久未使用置换算法
缺页次数为:54,缺页率是:0.27
OPT>LRU≈FIFO