操作系统 虚拟内存页面置换算法 java版

实验五 虚拟内存页面置换算法

1、 实验目的

通过这次实验，加深对虚拟内存页面置换概念的理解，进一步掌握先进先出FIFO、最佳置换OPI和最近最久未使用LRU页面置换算法的实现方法。 2、 试验内容 问题描述：

设计程序模拟先进先出FIFO、最佳置换OPI和最近最久未使用

LRU页面置换算法的工作过程。假设内存中分配给每个进程的最小物理块数为m，在进程运行过程中要访问的页面个数为n，页面访问序列为P1, … ,Pn，分别利用不同的页面置换算法调度进程的页面访问序列，给出页面访问序列的置换过程，计算每种算法缺页次数和缺页率。

3、 程序要求：

1）利用先进先出FIFO、最佳置换OPI和最近最久未使用LRU

三种页面置换算法模拟页面访问过程。

2）模拟三种算法的页面置换过程，给出每个页面访问时的内存

分配情况。

3）输入：最小物理块数m，页面个数n，页面访问序列P1, … ,Pn，

算法选择1-FIFO，2-OPI，3-LRU。 4）输出：每种算法的缺页次数和缺页率。 4、 需求分析

(1) 输入的形式和输入值的范围 算法选择 物理块数 页面个数

页面访问序列P1, … ,Pn (2) 输出的形式

每种算法的缺页次数和缺页率 (3) 测试用例

引用率701203042303212011701 777222444000777 00033322211100

1110003332221

页框引用率

70120304230321201701 77722222700004000 1133311

页框(物理块） 引用率 7012030423032120170 77722444011100000033300 1133222227

页框15、 调试分析

通过二次编程，又一次加深了对先进先出（FIFO）页面置换算法，最佳（OPI）置换算法，最近最久未使用（LRU）置换算法的理解。 同时，也掌握了一些使界面输出看起来更工整的办法。

还有，在平时做作业的时候，总是默认为物理块数是3，其实只是比较常用而已，并不是每次都是3.这个在编程中有体现，在今后做题中会更注意。 6、 测试结果

(1)先进先出FIFO页面置换算法 输入

输出

(2)最佳页面OPI置换算法 输入

输出

(3)最近最久未使用LRU置换算法 输入

输出

7、附录(java)

package experiment;

import java.io.BufferedInputStream; import java.io.FileInputStream;

import java.io.FileNotFoundException; import java.util.Scanner;

public class E_PageDisplace {

private static int MaxNumber = 100; // 页面序列P1, … ,Pn，

private static int PageOrder[] = new int[MaxNumber]; // 模拟页面置换过程

private static int Simulate[][] = new int[MaxNumber][MaxNumber];

//

private static int PageCount[] = new int[MaxNumber]; // 页面数

private static int PageNum; // 缺页数

private static int LackNum; // 缺页率

private static double LackPageRate; private static boolean found; // 物理块数量

private static int BlockNum; // NULL的int标记

private static int NULL=-1; // for循环用到变量 private static int i; private static int j; private static int k;

// 算法选择

// 1-先进先出FIFO页面置换算法 // 2-最佳页面OPI置换算法

// 3-最近最久未使用LRU置换算法 private static int option = 0;

private static Scanner stdin;

public static void main(String[] args) throws FileNotFoundException { // 输入数据 input();

// 算法选择

//算法选择\\n FIFO: 输入'1'\\n OPI: 输入'2'\\n LRU: 输入'3'\\n exit: 输入'4'\\n\

switch(option){ case 1:

System.out.println(\先进先出FIFO页面置换算法：\ FIFO(); output(); break; case 2:

System.out.println(\最佳页面OPI置换算法：\ OPI(); output(); break;

case 3:

System.out.println(\最近最久未使用LRU置换算法：\ LRU(); output(); break; default:

System.out.println(\你的输入有问题请重新输入！\ break; }

}

// 输入数据

public static void input() throws FileNotFoundException {

BufferedInputStream in = new BufferedInputStream(new FileInputStream( \ System.setIn(in);

stdin = new Scanner(System.in);

// 算法选择

// 1-先进先出FIFO页面置换算法 // 2-最佳页面OPI置换算法

// 3-最近最久未使用LRU置换算法 option = stdin.nextInt();

// 物理块数

BlockNum = stdin.nextInt(); // 页面个数

PageNum = stdin.nextInt(); // 页面访问序列P1, … ,Pn

for (i = 0; i < PageNum; i++) { PageOrder[i] = stdin.nextInt(); } }

//???????????????/

public static void original(){ for(i=0;i

for(j=0;j

LackNum=1; }

//先进先出:最早出现的置换算法，总是淘汰最先进入内存的页面。 public static void FIFO(){

original();

Simulate[0][0]=PageOrder[0]; int temp=0,flag=0; for(i=1;i

//判断该页面是否存在内存中 for(j=0;j

if(PageOrder[i]==Simulate[flag][j]) break; }

if(j==BlockNum) {//该页面不在内存中

for(k=0;k

if(Simulate[flag][k]==NULL) break; else

Simulate[i][k]=Simulate[flag][k]; }

//淘汰最先进入内存的页面 temp++;

temp=temp%BlockNum;

Simulate[i][temp]=PageOrder[i]; LackNum++; flag=i;

}//该页面在内存中 else

continue; } }

//最佳置换:选择的被淘汰的页面都是以后永不使用或者在最长（未来）时间内不被访问的页面。

public static void OPI(){

original();

Simulate[0][0]=PageOrder[0];

int temp,flag=0;//flag表示上一个模拟内存的下标

for(i=1;i

//判断该页面是否存在内存中 for(j=0;j

if(PageOrder[i]==Simulate[flag][j]) break; }

//j!=BlockNum表示该页面已经在内存中 if(j!=BlockNum) continue;

//模拟置换过程

for(k=0;k

if(Simulate[flag][k]==NULL) break; else

Simulate[i][k]=Simulate[flag][k]; }

//内存中页面进行选择

//两种情况：内存已满和内存未满 for(j=0;j

if(Simulate[i][j]==NULL) {

Simulate[i][j]=PageOrder[i]; LackNum++; flag=i; break; } }

if(j!=BlockNum)//内存未满 continue;

//内存已满

temp=0;//temp表示要置换的页面内存下标

for(j=0;j

{//选取要置换的页面内存下标

for(k=i+1;k

if(Simulate[i][j]==PageOrder[k]) {

PageCount[j]=k; break; } }

if(k==PageNum)//之后没有进行对该页面的访问 PageCount[j]=PageNum;

}

if(PageCount[temp]

temp=j; }

Simulate[i][temp]=PageOrder[i]; LackNum++; flag=i; } }

//最近最久未使用:LRU算法选择最近最久未使用的页面予以淘汰。 public static void LRU(){

original();

Simulate[0][0]=PageOrder[0];

int temp,flag=0;//flag表示上一个模拟内存的下标 PageCount[0]=0;//最近的页面下标

for(i=1;i

//判断该页面是否存在内存中 for(j=0;j

if(PageOrder[i]==Simulate[flag][j]) {

PageCount[j]=i; break; } }

//j!=BlockNum表示该页面已经在内存中 if(j!=BlockNum) continue;

//模拟置换过程

for(k=0;k

if(Simulate[flag][k]==NULL) break; else

Simulate[i][k]=Simulate[flag][k]; }

//内存中页面进行选择

//两种情况：内存已满和内存未满 for(j=0;j

if(Simulate[i][j]==NULL) {//内存未满

Simulate[i][j]=PageOrder[i]; PageCount[j]=i; LackNum++; flag=i; break; } }

if(j!=BlockNum) continue;

//内存已满

temp=0;//temp表示要置换的页面内存下标 for(j=0;j

{//最近最久时间内不被访问的页面 if(PageCount[temp]>PageCount[j]) temp=j; }

Simulate[i][temp]=PageOrder[i]; PageCount[temp]=i;

LackNum++; flag=i; }

}

//模拟三种算法的页面置换过程， //给出每个页面访问时的内存分配情况 //每种算法的缺页次数和缺页率。 public static void output(){

LackPageRate=(double)LackNum/PageNum; for(i=0;i

System.out.print(\ System.out.println(\ for(i=0;i

System.out.print(PageOrder[i]+\ System.out.println(\ for(i=0;i

System.out.print(\ System.out.println(\

for(j=0;j

//for(i=0;i

if(Simulate[i][j]==NULL)

System.out.print(' '+\ else

System.out.print(Simulate[i][j]+\ }

System.out.println(\ }

//cout<

System.out.println(\缺页次数:\率:\ } }

缺页

LackNum++; flag=i; }

}

//模拟三种算法的页面置换过程， //给出每个页面访问时的内存分配情况 //每种算法的缺页次数和缺页率。 public static void output(){

LackPageRate=(double)LackNum/PageNum; for(i=0;i

System.out.print(\ System.out.println(\ for(i=0;i

System.out.print(PageOrder[i]+\ System.out.println(\ for(i=0;i

System.out.print(\ System.out.println(\

for(j=0;j

//for(i=0;i

if(Simulate[i][j]==NULL)

System.out.print(' '+\ else

System.out.print(Simulate[i][j]+\ }

System.out.println(\ }

//cout<

System.out.println(\缺页次数:\率:\ } }

缺页

本文来源：https://www.bwwdw.com/article/xb2w.html