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

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

一、 需求分析 ................................................................................................................. 1

1.输入的形式和输入值的范围 .................................................................................... 2 2.输出的形式 ............................................................................................................ 2 3.程序所能达到的功能 .............................................................................................. 3 4.测试数据 ................................................................................................................ 4 二、 概要设计 ................................................................................................................. 5

1.抽象数据类型的定义 .............................................................................................. 5 2.主程序的流程 ......................................................................................................... 6 3.程序各模块之间的层次(调用)关系 .......................................................................... 7 三、 详细设计 ................................................................................................................. 7

1.void FIFO() ............................................................................................................. 7 2.void OPI() ............................................................................................................... 8 3.void LRU().............................................................................................................10 四、 调试分析 ................................................................................................................ 11

1.发现的问题 ........................................................................................................... 11

2.算法的性能分析(包括基本操作和其它算法的时间复杂度和空间复杂度的分析)及其改进设想；.................................................................................................................. 11 3.解决方法 ............................................................................................................... 11 4.经验和体会 ...........................................................................................................12 五、用户使用说明...........................................................................................................12 六、测试结果..................................................................................................................12 七．附录.........................................................................................................................14

一、 需求分析

? 需求

在进程运行过程中，若其所访问的页面不在内存而需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存调出一页程序或数据送磁盘的对换区中。但应将哪个页面调出，需根据一定的算法来确定。通常，把选择换出页面的算法称为页面置换算法。置换算法的好坏，将直接影响到系统的性能。一个好的页面置换算法，应具有较低的更好频率。从理论上讲，应将那些以后不再访问的页面换出，或把那些在较长时间内不再访问的页面调出。

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

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

1）利用先进先出FIFO、最佳置换OPI和最近最久未使用LRU三种页面置换算法模拟页面访问过程。

2）模拟三种算法的页面置换过程，给出每个页面访问时的内存分配情况。 3）输入：最小物理块数m，页面个数n，页面访问序列P1, … ,Pn，算法选择1-FIFO，2-OPI，3-LRU。

4）输出：每种算法的缺页次数和缺页率。

1.输入的形式和输入值的范围

从dos控制台界面按照输入提示输入数据（红色的数字即为输入的内容）： 物理块(LackNum)：3 页号数（PageNum）：20

页面序列(PageOrder)：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2

0 1 7 0 1

进程的最大页号数为100，物理块、页面序列的值为int类型的范围。

2.输出的形式

输入数据后，按ENTER键就可在dos控制台界面得到结果。按照实验要求分别

输出程序模拟先进先出FIFO、最佳置换OPI和最近最久未使用LRU页面置换算法的工作过程。结果如下：

首行是算法的名称，第二行是页号序列，接下来的3行数字是模仿物理块的情况，竖着看才是正确的结果，此图显示的是3块物理块时内存占用情况。之后显示缺页次数和缺页率。

3.程序所能达到的功能

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

4.测试数据

二、 概要设计

1.抽象数据类型的定义

程序中进程调度时间变量描述如下：

const int MaxNumber=100; int PageOrder[MaxNumber];

int Simulate[MaxNumber][MaxNumber];

int PageCount[MaxNumber]; int PageNum,LackNum; double LackPageRate; bool found; 主要函数： void print(); void init(); void original(); void FIFO(); void OPI(); void LRU();

2.主程序的流程

初始化全局变量：最小物理块数，页面个数，页面访问序列Init()输入a输出缺页次数和缺页率及模拟过程a=1否是FIFO()a=2否否是OPI()a=3否是LRU()a=4是结束

3.程序各模块之间的层次(调用)关系

FIFO()1Print()main()调用Init()2OPI()Print()3LRU()

Print()三、 详细设计

1.void FIFO()

original();

Simulate[0][0]=PageOrder[0]; int temp=0,flag=0;

for(i=1;i

}

Simulate[i][k]=Simulate[flag][k]; } //淘汰最先进入内存的页面 temp++; temp=temp%BlockNum; Simulate[i][temp]=PageOrder[i]; LackNum++; flag=i;

}//该页面在内存中 else continue;

2.void OPI()

original();

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

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

for(i=1;i

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

3.void LRU()

original();

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

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

for(i=1;i

break; } } if(j!=BlockNum) continue; //内存已满 temp=0;//temp表示要置换的页面内存下标 for(j=0;jPageCount[j]) temp=j; } Simulate[i][temp]=PageOrder[i]; PageCount[temp]=i; LackNum++; flag=i; } }

四、 调试分析

1.发现的问题

在编写程序的最初，界面不是很好，看着很乱。最后求的缺页率也不是用百分数表示。

2.算法的性能分析(包括基本操作和其它算法的时间复杂度和空间复杂度的分析)及其改进设想；

该程序的的时间复杂度还算理想，是O(m*n),空间复杂度也是一样，复杂度为O(m*n),均不需要再改进了。

3.解决方法

界面使用空格填充，使各行各列对齐。

对于输出百分数，将缺页率乘以100，后加%输出。

4.经验和体会

通过二次编程，又一次加深了对先进先出（FIFO）页面置换算法，最佳（OPI）置换算法，最近最久未使用（LRU）置换算法的理解。

同时，也掌握了一些使界面输出看起来更工整的办法。

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

五、用户使用说明

(1)用户根据提示输入物理块数

(2)输入页面个数

(3)依次输入页面访问个数

(4)根据提示选择算法，输入对应的数字。

六、测试结果

列出测试结果，包括输入和输出。

七．附录

#include #include using namespace std;

const int MaxNumber=100;

int PageOrder[MaxNumber];//页面序列P1, … ,Pn，

int Simulate[MaxNumber][MaxNumber];//模拟页面置换过程 int PageCount[MaxNumber];//

int PageNum,LackNum;//页面数，缺页数 double LackPageRate;//缺页率 bool found;

int BlockNum; int i,j,k;

void print(); void init();

void original(); void FIFO(); void OPI(); void LRU();

void main(){

//cout<

bool d=true; while(d) {

cout<<\算法选择\\n FIFO: 输入'1'\\n OPI: 输入'2'\\n LRU: 输入'3'\\n exit: 输入'4'\\n\ int c; cin>>c; switch(c){ case 1:

cout<

cout<

cout<

d=false; break; default:

cout<<\你的输入有问题请重新输入！\\n\ break; } } }

void init(){

cout<<\物理块数m: \ cin>>BlockNum;

cout<<\页面个数n: \ cin>>PageNum;

cout<<\页面访问序列P1, … ,Pn\\n\ for(i=0;i>PageOrder[i]; }

void original(){

for(i=0;i

for(j=0;j

LackNum=1; }

void print(){

//模拟三种算法的页面置换过程，

//给出每个页面访问时的内存分配情况 //每种算法的缺页次数和缺页率。

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

cout<

for(j=0;j

//for(i=0;i

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

cout<

//cout<

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; } }

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; } }

void LRU(){

//最近最久未使用: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; } }

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