页面置换算法模拟

第一篇：页面置换算法模拟

“计算机操作系统”课程设计大作业

一、题目: 页面置换算法模拟实验

二、目的

分别采用最佳(Optimal)置换算法、先进先出(FIFO)页面置换算法和最近最少使用(LRU)置换算法对用户输入的页面号请求序列进行淘汰和置换，从而加深对页面置换算法的理解。

三、内容和要求

请用C/C++语言编一个页面置换算法模拟程序。用户通过键盘输入分配的物理内存总块数，再输入用户逻辑页面号请求序列，然后分别采用最佳(Optimal)置换算法、先进先出(FIFO)页面置换算法和最近最少使用(LRU)置换算法三种算法对页面请求序列进行转换，最后按照课本P150页图4-26的置换图格式输出每次页面请求后各物理块内存放的虚页号，并算出每种算法的缺页次数。最后评价三种页面置换算法的优缺点。

三种页面置换算法的思想可参考教材P149-P152页。

假设页面号请求序列为4、3、2、1、4、3、5、4、3、2、1、5，当分配给某进程的物理块数分别为3块和4块时，试用自己编写的模拟程序进行页面转换并输出置换图和缺页次数。

四、提交内容 本大作业每个人必须单独完成，大作业以WORD附件形式提交。最后需提交的内容包括：算法算法思路及流程图、数据结构说明、源程序（关键代码需要注释说明）、运行结果截图、心得体会及总结。

大作业严禁抄袭。发现抄袭一律以不及格论。

请大家严格按照大作业题目来编写程序，不要上交以前布置的大作业。如果提交的大作业题目与本文档要求不符，成绩一律为不及格。

请大家按时在网院网上系统里提交大作业，过了规定时间将无法再补交大作业。

页面置换算法模拟实验

算法算法思路

模拟FIFOOPTLRU这3种页面置换算法，先分配所需的内存空间，在根据已知的序列，分别根据不同的页面算法去访问已知序列，得出不同内存空间的置换算法的缺页数量。总体流程图

开始输入内存数执行页面置换FIFOLRUOPT显示结果结束

数据结构说明

源程序（关键代码需要注释说明）FIFO关键源码

LRU关键源码

OPT关键源码

程序源码

#include using namespace std;#define N 12 //默认序列12 #define M 4 // 默认开辟4 内存空间 struct page{ int pno;// 定义页号

int bno;//定义块号

int time;// 定义最近使用

int status;//定义命中状态

int order;//定义优先级 };

int list[12]={4,3,2,1,4,2,5,2,3,2,1,5};// 已知序列

// 输出方法

void output(int *a ,int n){ for(int i=0;i

cout<<*a<<'t';

a++;} cout<<'n';}

void fifo(int *list,int mem_num){

page p[N];// 定义记录数组

int flag;int mem[M];// 定义内存

int index =0;// 默认下标

int lack=0;// 初始化内存

for(int i=0;i

mem[i]=0;} // 遍历序列

for(i=0;i

flag=0;// 设置默认命中 0

for(int j=0;j

if(list[i]==mem[j]){ // 检测序列与已知内存值，命中返回flag

flag=1;

break;

}

}

if(flag==1){ // 判断是否命中，则对 p 赋值

p[i].bno = j+1;

p[i].pno = list[i];

p[i].status =1;

}else{

p[i].pno = list[i];

p[i].status = 0;

mem[index] = list[i];

p[i].bno = index+1;// 赋予 页号

index =(index+1)%mem_num;// 每次取余

lack++;

} }

cout<<“FIFO算法：n”;cout<<“---**n”;cout<<“缺页次数：”<<'t'<

cout<<“-----**n”;cout<<“序列号n”;

cout<<“-----**n”;for(i=0;i

cout<<“-----**n”;} for(i=mem_num;icout<<“-----**n”;}

}

struct mem{ int order;//内存优先级 主要用于识别是否不常用

int pno;// 内存页号

int time;// 记录是否最近使用 };

void lru(int *list,int mem_num){ page p[N];// 定义记录数组

int flag;mem m[M];// 定义内存

int index =0;// 默认下标

int lack=0;int temp;int max=0;// 内存赋值

for(int i=0;i

m[i].pno=0;

//默认初始优先级 0

m[i].order = 0;} for(i=0;i

flag=0;

for(int j=0;j

if(list[i]==m[j].pno){

flag=1;

index=j;

//m[j].order++;

p[i].order =m[j].order;

break;

}

}

if(flag==1){ //命中后，p[i].bno = index+1;

p[i].pno = list[i];

p[i].status = 1;

p[i].order--;

temp = p[i].order;

for(j=0;j

if(p[j].order

temp=p[j].order;

index = p[j].bno;

}

}

}else{

p[i].status=0;

p[i].pno = list[i];

m[index].pno = list[i];

m[index].order = p[i].order;

p[i].bno = index+1;

for(j=0;j

if(m[j].order>max){

index = j;

}

}

index =(index+1)%mem_num;// 每次取余有效的下标

//max++;

lack++;

} } cout<<“LRU算法：n”;cout<<“---**n”;cout<<“缺页次数：”<<'t'<

cout<<“-----**n”;cout<<“序列号n”;

cout<<“-----**n”;for(i=0;i

cout<<“-----**n”;} for(i=mem_num;ivoid opt(int *list,int mem_num){ page p[N];//定义页面

mem m[M];int flag=0;int index = 0;//下标

int max = N;int lack=0;for(int i=0;i

m[i].pno=0;

m[i].time = 0;//设置内存使用频率

}

for(i=0;i

flag=0;

for(int j=0;j

if(list[i]==m[j].pno){

flag=1;

index = j;

break;

}

}

if(flag==1){

p[i].status =1;

p[i].bno = index+1;

p[i].pno = list[i];

for(j=0;j

for(int g=i;g

if(m[j].pno==list[g]){

m[j].time = N-g;//获取到 最近使用

p[i].time = m[j].time;

index = j;

}

}

}

}else{

p[i].status =0;

p[i].pno = list[i];

m[index].pno = list[i];

m[index].time = N;//设置默认不使用

p[i].bno =index+1;

for(j=0;j

if(m[j].time>max){

index = j;

}

}

index =(index+1)%mem_num;

lack++;

}

} cout<<“OPT算法：n”;cout<<“---**n”;cout<<“缺页次数：”<<'t'<

cout<<“-----**n”;cout<<“序列号n”;

cout<<“-----**n”;for(i=0;i

cout<<“-----**n”;} for(i=mem_num;icout<<“-----**n”;} }

void main(){ int m;cout << “===========================n”;cout << “请输入内存大小（3/4）n”;cin >> m;cout << “===========================n”;opt(list,m);fifo(list,m);lru(list,m);

}

运行结果截图

FIFO、LRU、OPT运行截图（开辟3个内存空间）：

FIFO、LRU、OPT运行截图（开辟4个内存空间）：

心得体会及总结：

在开始做题目的时候，需要了解什么是FIOFOLRUOPT这3个页面置换的知识点，同时参考了网络上许多实现过程技巧，并在在纸上面简单画出页面如何记录如何与内存置换，这样子比较方便写出算法。由于这次设计的时间比较仓促，其中不免会有些纰漏，比如在程序的实现上还不够严谨，出错处理不够完善等多方面问题，这些都有进一步改善。同时，在这次编写3个页面算法的过程中，我学到了很多东西，无论在理论上还是实践中，都得到不少的提高，这对以后的工作中会有一定的帮助。

第二篇：页面置换算法实验报告（精选）

《操作系统--页面置换算法》

实验报告

姓

名： 范学升

学

号：1001050903

班

级：电科10-1班

专

业：电子信息科学与技术

一、实验目的

1．通过模拟实现几种基本页面置换的算法，了解虚拟存储技术的特点。

2．掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想，并至少用三种算法来模拟实现。

3．通过对几种置换算法页面的比较，来对比他们的优缺点，并通过比较更换频率来对比它们的效率。

二、实验内容：

设计一个虚拟存储区和内存工作区，并使用下述算法来模拟实现页面的置换： 1.先进先出的算法（FIFO）2.最近最久未使用算法（LRU）3.最佳置换算法（OPT）

三、实验分析

在进程运行过程中，若其所访问的页面不存在内存而需要把它们调入内存，但内存已无空闲时，为了保证该进程能够正常运行，系统必须从内存中调出一页程序或数据送磁盘的对换区中。但应调出哪个页面，需根据一定的算法来确定，算法的好坏，直接影响到系统的性能。

一个好的页面置换算法，应该有较低的页面更换频率。

假设分给一作业的物理块数为3，页面数为20个。页面号为(20个)：

7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1

1．先进先出(FIFO)置换算法的思路

该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单，只需把一个进程已调入内存的页面，按照先后次序连接成一个队列，并设置一个替换指针，使它总指向最老的页面。

2．最近久未使用(LRU)置换算法的思路

最近久未使用置换算法的替换规则，是根据页面调入内存后的使用情况来进行决策的。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间，当需淘汰一个页面的时候选择现有页面中其时间值最大的进 行淘汰。

3.最佳（OPT）置换算法的思路

其所选择的被淘汰的页面，奖是以后不使用的，或者是在未来时间内不再被访问的页面，采用最佳算法，通常可保证获得最低的缺页率。

4．数据结构

struct pageInfor { int content;//页面号 int timer;//被访问标记 };

class PRA { public:

PRA(void);int findSpace(void);//查找是否有空闲内存

int findExist(int curpage);//查找内存中是否有该页面 int findReplace(void);//查找应予置换的页面 void display(void);//显示 void FIFO(void);//FIFO算法 void LRU(void);//LRU算法

void BlockClear(void);//BLOCK清空，以便用另一种方法重新演示 pageInfor * block;//物理块 pageInfor * page;//页面号串 private: };

5．FIFO页面置换算法

当需要访问一个新的页面时，首先调用findExist(i)函数来查看物理块中是否就有这个页面，若要查看的页面物理块中就有，则调用display函数直接显示，不需要替换页面；如果要查看的页面物理块中没有，就需要寻找空闲物理块放入，若存在有空闲物理块，则将页面放入；若没有空闲物理块，则调用findReplace函数替换页面。并将物理块中所有页面timer++。

6．LRU页面置换算法

当需要访问一个新的页面，首先调用findExist(i)函数查看物理块中是否就有这个页面。

7.OPT页面置换算法

当需要访问一个新的页面，首先调用findExist(i)函数来查看物理块中是否有这个页面。

8．寻找置换页面函数findReplace比较三个物理块中的时间标记timer，找到时间最久的。

四、源程序结构分析

1． 程序结构

程序共有以下九个部分：

int findSpace(void);//查找是否有空闲内存

int findExist(int curpage);//查找内存中是否有该页面 int findReplace(void);//查找应予置换的页面 void display(void);//显示 void FIFO(void);//FIFO算法 void LRU(void);//LRU算法 void OPT(void);//OPT算法；

void BlockClear(void);//BLOCK清空，以便用另一种方法重新演示 int main()

//主程序

五、实验结果

1运行后的初始界面 opt算法

3.FIFO算法

4LRU算法

第三篇：页面置换算法模拟,实验报告

中北大学软件学院 实 验 报 告

专

业

软件工程

课程名称

计算机操作系统

学

号

姓

名

辅导教师

张

静

成绩

实验日期 2015、１1、20 实验时间实验名称 :实验四

页面置换算法模拟 ２、实验目得(１）了解内存分页管理策略（2）掌握调页策略(3）掌握一般常用得调度算法（4）学会各种存储分配算法得实现方法。

（5）了解页面大小与内存实际容量对命中率得影响。

3、实验要求 编程实现页面置换算法，最少实现两种算法，比较算法得优劣,并将调试结果显示在计算机屏幕上，并检测机算与笔算得一致性。

（1）采用页式分配存储方案，通过分别计算不同算法得命中率来比较算法得优劣，同时也考虑页面大小及内存实际容量对命中率得影响;（2）实现 OＰT 算法(最优置换算法)、ＬRU 算法(Lｅast Recｅｎtly）、FIFO 算法（Fｉrst IN Firｓｔ Out）得模拟;（3)使用某种编程语言模拟页面置换算法.4、实验算法描述 （1）ＦIFO（先进先出）

Y

Ｎ

N

Y

开始 页面走向存入数组 p[]中,内存块用page[]表示初始化为 0 当前p[]中第i个元素就是否已在内Page[]就是否有空把 page[]中最先装入得页面置换出去、i++ 把 p[i]得内容直接装入最上面一个空内存块,i++ 输出当前内存块状态 i++

图 4－1FIFＯ算法流程图

结束

(2）

LＲU（最近最久未使用）

Y

N

Y

Ｎ

图 4—2

LＲU 算法流程图

开始 页面走向存入数组 p[]中,内存块用 page[]表示初始化为 0 当前 p[]中第 i 个元素就是否已在内存 Page[]就是否有空把 page[]中最近最久未使用得页面置换出去、i++ 把 p[i]得内容直接装入最上面一个空内存块,i++ 输出当前内存块状态

结束 i++

(3）OＰＴ（最佳置换算法）

Y

N

Y

Ｎ

图４－3 ＯPT 流程图

开始 页面走向存入数组 p[]中,内存块用 page[]表示初始化为 0 当前 p[]中第 i 个元素就是否已在内存 Page[]就是否有空把 page[]中以后一段时间都不使用或就是使用时间离现在最远得换出、i++ 把 p[i]得内容直接装入最上面一个空内存块,i++ 输出当前内存块状态

结束 i++

6、实验代码 ＃iｎcｌuｄe ＜iostreａm〉 usiｎｇ ｎａmespace sｔｄ;#defiｎe Bｓｉzｅ ３ #dｅfine Psｉｚe 20 ｓｔruct ｐaｇｅInｆor ｛

号面页//

;ｔneｔｎoc tniﻩ int tｉmer;

//被访问标记 ｝;ｃlasｓ ＰＲA{ ｐuｂｌiｃ：

PRA(ｖoid）；

存内闲空有否是就找查/／

;)diov（eｃaｐSdnif tniﻩ iｎt ｆindExist（int curpage）;

／／查找内存中就是否有该页面

int findReplacｅ（vｏid）;

//查找应予置换得页面

void ｄisplay(void）;

//显示

法算 OＦIF//;）dioｖ（OFIＦ ｄiovﻩ 法算 UＲL／/；)dｉov(URL diovﻩ vｏid Ｏptimａl(ｖoid);／／ＯPTIＭAL 算法

ｖoｉd BlockＣlear（voiｄ)；/／ＢLOCK 恢复

pageＩｎfor ＊ ｂlｏck；//物理块

pageInfoｒ ＊ page；／／页面号串 privaｔe: };PＲA：：PＲＡ(vｏid）{

ｉnt QStriｎg［２0］=｛7，0，1，２,0，3,0，4,２，3,0,3,２,1，2，0，1,7,0,１};

block = ｎew paｇeIｎfor[Bｓizｅ］;)++i;ｅzisB＜ｉ;0＝i ｔnｉ(rofﻩ {

;1— = tnｅtnｏc、］ｉ［ｋcolbﻩ ；0 ＝ remｉt、]ｉ［kcolbﻩﻩ }

page = ｎew pageInfｏｒ［Psｉze];）＋+ｉ;eｚiｓP〈i ；０=i（ｒofﻩ {

；]i[gｎiｒtSQ = tｎetnoｃ、］i[egａpﻩ;0 = rｅmit、]i[eｇａｐﻩﻩ }ﻩ} iｎt ＰRA：：fｉndSpace（voiｄ）

{

for（iｎt i=0； i

if(bｌocｋ[i]、cｏntent =＝ －1）

置位中 KＣOLＢ回返，存内闲空到找//;i nrutｅｒﻩ;1— ｎruteｒﻩ｝ inｔ ＰRA：：fiｎｄExisｔ（iｎt cｕrpage）

{

ｆor（int i=0;ｉ<Ｂsizｅ； i++））tｎetnｏc、]egapruc［ｅgａp =＝ tneｔｎoc、］ｉ［kｃoｌb(fiﻩﻩ

置位中 KCOＬB 回返,面页该有中存内到找//;i nrｕterﻩ ；1— nruterﻩ｝ iｎt PRA：：findReplａce(void）

{

;0 ＝ sop tｎiﻩ foｒ（iｎt i=0;i<Ｂsｉzｅ； ｉ+＋）)rｅmit、］soｐ[ｋcｏlb =＞ rｅmit、］i［kcｏlb（fiﻩﻩ

ﻩ pos = i;//找到应予置换页面,返回 BLOCＫ中位置

ｒeturn pos； } voｉd ＰRＡ：:display（voiｄ）

{

for（inｔ i=0;i＜Ｂsiｚe； ｉ++）

ｉｆ(bｌock［ｉ］、coｎteｎｔ!＝-１）

ﻩ；” ”<〈ｔnetnoc、］i[kcｏlb〈〈tuocﻩ ；ldｎe＜＜tuocﻩ｝ void PRA：：Optimａｌ（ｖoid)｛

； noｉtisop,ecapｓ，tsiｘe tｎiﻩ fｏr（ｉnt i=0； i

｛ﻩ;)i（tsixEdｎif = tｓｉxeﻩﻩ）1-=！

ｔsixe（fｉﻩ

{ﻩ

;ｌdnｅ〈〈”页缺不“<<ｔｕoｃﻩ ｝ﻩﻩ

esｌｅﻩ

{ﻩﻩ ﻩﻩ spａｃe = findSpacｅ（）；

ﻩ）1— ＝！

eｃaｐs（fiﻩ ﻩ

{ﻩ ﻩ

；]i［egaｐ = ］eｃapｓ［kcolｂﻩ

ﻩ

;）（yalpsidﻩﻩ

ﻩ }

ﻩ

ｅslｅﻩ

{ﻩﻩ ﻩ)+＋k ；ezisB<ｋ ；0＝k tｎｉ（roｆﻩ

ﻩ for（iｎｔ j＝i； j＜Psize； ｊ+＋)

ﻩ

{ﻩﻩﻩ

ﻩﻩ)ｔnetnoc、]ｊ［ｅgaｐ =!ｔnｅtnoc、］k[ｋcolb（ｆiﻩ

｛ 为 RＥMＩT 置设，用会不来将//};00０1 = ｒemiｔ、］k［kcoｌbﻩﻩ一个很大数

ﻩﻩ

esleﻩ

ﻩﻩ

｛

ﻩﻩ

ﻩ

ﻩ bloｃk［k]、ｔｉmeｒ = j;

ﻩ

ﻩﻩ ｂreaｋ；

｝ ﻩﻩﻩ }ﻩﻩﻩﻩﻩ

ﻩ ｐoｓition ＝ fiｎdReｐｌａce（）；

ﻩ

；］i［ｅｇap ＝ ]ｎｏiｔｉｓｏｐ[ｋcolｂﻩ

；）(yalｐsｉｄﻩﻩ

｝ﻩﻩ ﻩ }

}ﻩ｝ voiｄ PRA:：LRU（ｖoid){

int ｅxｉsｔ,ｓpace，ｐositioｎ ；

for(int ｉ ＝ 0； i < Psizｅ;ｉ++）

｛ﻩ ﻩ ｅxist = fｉndEｘｉst(i);)1－ =！

tsｉxｅ(ｆiﻩ

{

ﻩﻩ cout＜<”不缺页”＜

ﻩ

blｏck［eｘisｔ］、tiｍｅｒ = —1；//恢复存在得并刚访问过得ＢLOCK 中页面 TＩMＥR 为－1

ﻩ }

ﻩ else

｛ﻩ ﻩﻩ sｐace = fｉｎdSpace();ﻩ）１-=!ecaｐs（fiﻩ ﻩ

{ﻩ;]i[ｅgａp = ］ecaｐs［ｋｃolｂﻩﻩ ﻩ

；)（ｙalpｓidﻩ ﻩﻩ ｝

ﻩ

eｓleﻩ

｛ﻩﻩ

；）（eｃａｌｐeRｄｎif = noｉtiｓopﻩﻩ

ﻩ

bｌoｃk[positiｏn］ = ｐagｅ［i］；

ﻩ

;）(yａlｐsidﻩ

｝ﻩﻩ

｝ﻩ

for(int ｊ=0;j〈Ｂsizｅ;j++)

;+＋rｅmit、］j[kcolbﻩﻩ ｝ﻩ｝ ｖoｉd PRA:：ＦIFO（ｖoid）

{

int exｉｓt,ｓpace,position ；

for（iｎt i=0;i

｛ﻩ

exｉｓt ＝ findExist(ｉ）；

ﻩ ｉf（eｘist!＝-１）

{cout＜<＂不缺页＂＜

esleﻩ

｛

sｐａce = findSｐａｃe（）；

ﻩ)1-=！

ecaｐs（ｆiﻩ ﻩﻩ ｛

ﻩ

block［spaｃｅ］ = paｇe[ｉ]；

ﻩ

ﻩ displaｙ();

｝ﻩﻩ

ｅsｌeﻩﻩ ﻩ

｛

ﻩﻩ

pｏsition = findReplaｃe（）；

ﻩﻩ

block［pｏsitioｎ] ＝ paｇe[i］；

;)（yａlｐsｉdﻩﻩ ﻩﻩ ｝

}ﻩ）＋+j;ezｉsB

ｂlock[j］、tｉmｅr+＋；//BLOCK 中所有页面ＴIMER+＋

｝ﻩ｝ void ＰＲA：：BlockＣleａr（vｏiｄ)｛

for(inｔ ｉ=０;i

{ﻩ

blocｋ[i］、contｅnt =-1；

ﻩ ｂｌｏcｋ[i]、timeｒ = ０;

｝

} ｖoid mａｉn(vｏiｄ)｛

;lｄne<〈”:法 算 换 置 面 页“＜＜tuｏcﻩ ｃｏｕｔ〈〈”页面号引用串：7,０,1,2，0,3,0，4,2，３，0，３,2,1,2，0，1，7，０,1＂<〈ｅndｌ；

cout〈〈”选择<１＞应用 LＲU 算法”〈＜eｎdl；

coｕt<＜”选择<２〉应用 FIFO 算法”〈

ｃout<<”选择＜3>应用 Optｉmａl 算法“<〈ｅndl;

；ldne<<＂出退>0〈择选”〈＜ｔuocﻩ int select；

ＰRA tesｔ;ﻩ whｉle(seleｃｔ)

｛

ﻩ cｉｎ〉>select;）tcｅｌｅs（ｈctｉwsﻩ

｛ﻩ

:0 esacﻩﻩ;ｋaerbﻩ :1 esａcﻩﻩﻩ;ｌdnｅ＜<“：下如果结法算ＵRL”＜〈tuocﻩ

;）（URL、tsetﻩﻩ

；)(raelCkｃｏｌB、tｓeｔﻩﻩ;ldne＜<”－－-—-—－-—-—--—-—－—－———“<

ﻩ break；

：2 esacﻩ

cｏut<〈”FIFO 算法结果如下:“<＜endl；

tesｔ、FIFO();ﻩ；）（raelCｋcoｌＢ、ｔsetﻩ

ﻩ cｏuｔ<〈”-——-－－－－－-—－—－－---－—－-”＜〈eｎdl;

ﻩ

ｂreak；

caｓe 3:

；ｌdnｅ〈＜”：下如果结法算 lａmiｔｐＯ”<

test、Optimal（）;

ﻩ

；)（rａeｌCkｃolB、tｓetﻩﻩ；ldｎe＜<＂－-－-—－－--－-——-－————－－－＂〈〈tuocﻩﻩ;ｋaeｒbﻩ

defaulｔ：

ﻩ

；ldｎe〈＜”号能功确正入输请“＜＜tuoｃﻩ

;ｋaerbﻩﻩ }ﻩﻩ } ｝

6、实验结果

7、实验心得 加深了对操作系统得认识,了解了操作系统中各种资源分配算法得实现，特别就是对虚拟存储，页面置换有了深入得了解，并能够用高级语言进行模拟演示。在这短短得两周时间里，通过浏览、阅读有关得资料，学到了很多东西,同时也发现仅仅书本得知识就是远远不够得,需要把知识运用到实践中去,能力才能得到提高。

使用 MFＣ可视化编程极大得减少了编写得代码量，直观得界面设计，不但便于修改，而且简化了界面程序代码得编写 两种页面置换算法 FIＦO 与ＬRＵ理解起来相当容易，但在实际编程实现得时候需要注意各种细节,需要耐心细致,实际编程中遇到一些细节上得小问题确实需要仔细考虑才行.

第四篇：页面置换算法实验报告

计算机体系结构

实验报告

班级：计科姓名：张华敏学号：

0902班

0909090814

FIFU算法

一，实验内容：

编写一段程序来模拟页面置换算法中的FIFU算法的实现 二，算法设计：

设置一个产生随机数的函数rand()产生随机数来模拟程序所需访问的页面的标号，如果页面需要被访问则把页面中的一个标志位设为in表示他已经被调入内存，如果再次需要访问此页面是只需检查此页面的标志位是否为in就可判断它是否已经存在在内存中了，如果已经存在则可直接使用，如果不存在则需调入，在调入新页面是先检查内存空间是否已满，如果未满则直接调入，如果已经满了则需选择一个页面将其调出，调出时就把页面的标志位设为out。选择页面的规则是：将进入内存时间最久的页面调出去，为了达到这一目的，在页面中设置一个计数器，每当有新页面调入内存时则将内存中已经存在的页面计数器自动加一，调出页面时就选择那个计数器最大值的页面，调出后重新将计数器设为零。三，遇到的问题及解决方案：

在做此实验时遇到了一些小问题,如在C语言中函数名定义为export()则会报错。在调用有返回值的函数是如果直接int s=use(pag)则会运行出错,要先分开写如：int s,s=use(pag).四，源代码 头文件.cpp #include #include

int t;//全局变量，用来盛放rand()函数产生的随机数

enum boolean{in,out};//定义一个枚举类型 /////////如果把in，out换成 true,false则会处错误

typedef struct { int num;//页面编号 char content;//页面内容

enum boolean flog;//判断此页面是否页调入，调入为true,否则为false;int count;//页面计数器

int usebit;//使用位，被使用过值为1，否则为0 }page;

FIFU.cpp #include #include #include #include“头文件.cpp”

int capacity=3;//设置内存最多可以容纳的页面数

void initialize(page p[])//初始化页面函数 { for(int i=0;i<5;i++)//初始化页面，页面内容分别为小写字母 abcde,计数器全部为0 {p[i].num=i;p[i].content=i+97;p[i].flog=out;p[i].count=0;} }

int use(page p[]){ t=rand()%5;//产生一个0-5的随机数，if(p[t].flog==in){ printf(“tt%d页面命中n”,t);//for(int i=0;i<5;i++)//调入此页面后其他以在内存中存在的页面计数器加1 // { // if(p[i].flog==in)// p[i].count++;// } return(1);} else return(0);}

void import(page p[])//调入页面的函数 { /* int t=rand()%5;//产生一个0-5的随机数，if(p[t].flog==in)printf(“tt%d页面命中n”,t);*/ // if(p[t].flog==out)//如果此页面未被调入内存则立即调入 p[t].flog=in;capacity--;//调入后内存空间减少一叶

for(int i=0;i<5;i++)//调入此页面后其他以在内存中存在的页面计数器加1 { if(p[i].flog==in&&p[i].num!=t)p[i].count++;} printf(“页面%d被调入内存n”,t);}

void port(page p[])//调出页面的函数，，，，，，，，，，，如果函数名定义为export则处错误 { int x=0,y;//x用来暂时存放计数器 中的最大值，y存放此页面的页面号 for(int i=0;i<5;i++)//寻找计数器值最大的 页面 { if(p[i].count>x){ x=p[i].count;y=i;} }

p[y].flog=out;//修改调入符号 p[y].count=0;capacity++;//调入后内存空间增加一叶 printf(“ttt页面%d被调出内存n”,y);}

main(){ int s;long t3,t1,t2;page pag[5];//定义五个页面，，，，，，，，，，，如果这个定义在子函数之前那么不用通过参数 子函数便可以直接访问 t3=time(NULL);initialize(pag);do { t1=time(NULL);s=use(pag);//，，，，，，，，，，，，，，如果这里写成int s=use(pag)则会运行出错

//printf(“s=%d capacity=%dn”,s,capacity);if(capacity>0&&s==0)import(pag);else { if(capacity==0&&s==0){ port(pag);import(pag);} } t2=time(NULL);while(t2-t1<1){ t2=time(NULL);} }while(t2-t3<20);system(“pause”);}

五，测试结果：

LFU算法

一,实验内容：

编写一段程序来模拟页面置换算法中的LFU算法的实现 二,算法设计：

设置一个产生随机数的函数rand()产生随机数来模拟程序所需访问的页面的标号，如果页面需要被访问则把页面中的一个标志位设为in表示他已经被调入内存，如果再次需要访问此页面是只需检查此页面的标志位是否为in就可判断它是否已经存在在内存中了，如果已经存在则可直接使用，如果不存在则需调入，在调入新页面是先检查内存空间是否已满，如果未满则直接调入，如果已经满了则需选择一个页面将其调出，调出时就把页面的标志位设为out。选择页面的规则是：将最近一段时间未被访问过的页面调出。为了达到这一目的在页面中设置一个标志位，如果页面在近期只要被访问过则将该标志位设置为1（默认为0），在选择调出页面时只需将标志位为0的页面调出即可。三,遇到的问题及解决方案： 未遇到什么问题

四,实验感悟：

遇到问题后上网查资料和有效,及时查不到自己想要的但是也可从相关结果中获得启发给自己灵感来想到解决问题的方法.四，源代码

FLU.cpp #include #include #include #include“头文件.cpp”

int capacity=3;

//设置内存最多可以容纳的页面数

void initialize(page p[])

//初始化页面函数

{

for(int i=0;i<5;i++)

//初始化页面，页面内容分别为小写字母 abcde,计数器全部为0

{p[i].num=i;

p[i].content=i+97;

p[i].flog=out;

p[i].count=0;

p[i].usebit=0;

}

}

int use(page p[]){

t=rand()%5;

//产生一个0-5的随机数，if(p[t].flog==in)

{

printf(“tt%d页面命中n”,t);

p[t].usebit=1;

//for(int i=0;i<5;i++)//调入此页面后其他以在内存中存在的页面计数器加1

//

{

//

if(p[i].flog==in)

//

p[i].count++;

//

}

return(1);

}

else

return(0);

}

void import(page p[])//调入页面的函数

{

int t=rand()%5;

//产生一个0-5的随机数，//if(p[t].flog==in)

// {

//

printf(“tt%d页面命中n”,t);

//

p[t].usebit=1;

// }

// if(p[t].flog==out)

//如果此页面未被调入内存则立即调入

p[t].flog=in;

capacity--;

//调入后内存空间减少一叶

for(int i=0;i<5;i++)//调入此页面后其他以在内存中存在的页面计数器加1

{

if(p[i].flog==in&&p[i].num!=t)

p[i].count++;

}

printf(“页面%d被调入内存n”,t);

}

void port(page p[])

//调出页面的函数

////////////////////////////////如果函数名定义为export则处错误

{

int x=0,y;//x用来暂时存放计数器 中的最大值，y存放此页面的页面号

int z=-1;

//用来判断近期是否有未被访问过的页面

int g=0;

for(int i=0;i<5;i++)//寻找计数器值最大的 页面

{

if(p[i].count>x)

{

x=p[i].count;

y=i;

}

}

for(int i=0;i<5;i++)

{

if(p[i].flog==in&&p[i].usebit==0)

{

z=i;

g++;

}

}

if(z==-1||g==3)//如果所有页面均为1则按照FIFO算法置换页面 //如果g=3则表明页面使用位全为零，此时也按照FIFO算法置换页面

{

p[y].flog=out;//修改调入符号

p[y].count=0;

capacity++;

//调入后内存空间增加一叶

p[y].usebit=0;

for(int i=0;i<5;i++)//将所有页面置0

p[i].usebit=0;

printf(“ttt页面%d被调出内存n”,y);

}

else

//如果有页面为0则将此页面置换出来

{

p[z].flog=out;//修改调入符号

p[z].count=0;

capacity++;

//调入后内存空间增加一叶

printf(“ttt页面%d被调出内存n”,z);

}

}

main(){

int s;

long t3,t1,t2;

page pag[5];//定义五个页面

///////////////////如果这个定义在子函数之前那么不用通过参数 子函数便可以直接访问

t3=time(NULL);

initialize(pag);

do

{

t1=time(NULL);

s=use(pag);

if(capacity>0&&s==0)

import(pag);

else

{

if(capacity==0&&s==0)

{

port(pag);

import(pag);

}

}

t2=time(NULL);

while(t2-t1<1)

{

t2=time(NULL);

}

}while(t2-t3<20);

system(“pause”);}

六,实验结果

总结

通过本次试验我对各种页面置换算法有了更深入的了解,也使得自己认识到平常学习到某些东西觉得懂了会了可是一旦实际动手操作起来就会发现总会存在这样或者那样的错误，只有多动手实际操作才会发现不足发现错误并且改正。查漏补缺提高自己的实际动手能力。

第五篇：实验5 页面置换算法

实验5

页面置换算法

一、实验题目：页面置换算法（请求分页）

二、实验目的：

进一步理解父子进程之间的关系。

1）理解内存页面调度的机理。2）掌握页面置换算法的实现方法。3）通过实验比较不同调度算法的优劣。4）培养综合运用所学知识的能力。

页面置换算法是虚拟存储管理实现的关键，通过本次试验理解内存页面调度的机制，在模拟实现FIFO、LRU等经典页面置换算法的基础上，比较各种置换算法的效率及优缺点，从而了解虚拟存储实现的过程。将不同的置换算法放在不同的子进程中加以模拟，培养综合运用所学知识的能力。

三、实验内容及要求

这是一个综合型实验，要求在掌握父子进程并发执行机制和内存页面置换算法的基础上，能综合运用这两方面的知识，自行编制程序。

程序涉及一个父进程和两个子进程。父进程使用rand()函数随机产生若干随机数，经过处理后，存于一数组Acess_Series[]中，作为内存页面访问的序列。两个子进程根据这个访问序列，分别采用FIFO和LRU两种不同的页面置换算法对内存页面进行调度。要求：

1）每个子进程应能反映出页面置换的过程，并统计页面置换算法的命中或缺页情况。

设缺页的次数为diseffect。总的页面访问次数为total_instruction。缺页率 = disaffect/total_instruction 命中率 = 1-disaffect/total_instruction 2）将为进程分配的内存页面数mframe 作为程序的参数，通过多次运行程序，说明FIFO算法存在的Belady现象。

四、程序流程图

开始创建子进程1创建子进程2

结束 子进程1逻辑页面读完？N命中？N内存页面满？Y命中次数+1YY最先进入的进程退出内存页面N当前调入页面进入内存页面退出 2逻辑页面读完？N命中？N内存页面满？N当前调入页面进入内存页面Y被访问次数最少的进程退出内存页面Y命中次数+1，命中页面访问数+1Y退出

五、运行结果及其说明

FIFO:

LRU:

：

六、回答以下问题： ① 父进程、子进程之间的并发执行的过程

父进程与子进程之间的并发执行宏观并行，微观串行。从宏观来说，父进程创建子进程1，子进程1和父进程同时执行，直到父进程创建子进程2遇到wait()函数挂机为止，当子进程1结束父进程和子进程2并发执行到再次遇见wait()函数是挂起等待子进程2结束，到子进程2结束返回父进程父进程继续执行至结束。从微观来说，父进程先执行至创建子进程1，接下来父进程挂起执行子进程1知道子进程1结束回到父进程；父进程继续执行到创建子进程2再次挂起，执行子进程2，直到子进程2结束回到父进程继续执行至结束。

② 通过完成实验，根据你的体会，阐述虚拟存储器的原理。虚拟存储器实际上是用来解决作业大而内存小的问题，他通过页面置换算法来提供远大于内存地址空间的地址范围，针对不同的程序将不同的数据页面读取到虚拟存储器中用来实现。

③ 写出FIFO算法中出现Belady现象的内存页面访问序列。

4个内存页面数：

序列2 2 5 3 3 1 3 1 2 5 5 2 3个内存页面数：

序列2 1 3 2 1 4 3 1 3 1 5 5

7次命中，命中率为0.58 6次命中，命中率为0.5

七、程序源代码、文档注释及文字说明

#include #include #include #include #include #include #include #include #define max_Frame 12 #define Frame 2

main(){ srand(time(0));int pid1, pid2, fd[2], Acess_Series[12], temp;float effect, rate = 0;char str1[100], str2[100];struct M_Frame {

int page_no;

char flag;};struct M_Frame one_frame[4];one_frame[0].page_no = 0;one_frame[1].page_no = 0;one_frame[2].page_no = 0;one_frame[3].page_no = 0;effect = 0;int i = 0;printf(“内存访问页面序列:”);for(;i<12;i++){

Acess_Series[i] = rand()% 5 + 1;

printf(“%d ”, Acess_Series[i]);} while((pid1 = fork())==-1);if(pid1 == 0){

int no = 0;

int pno = 0;

printf(“FIFO页面置换算法:n”);

for(;no<12;no++)

{

printf(“调入的页面号是%d ”, Acess_Series[no]);

int k = 0;

for(;k <= Frame;k++)

{

if(one_frame[k].page_no == Acess_Series[no]){ effect++;printf(“命中n”);break;}

if(one_frame[k].page_no == 0)

{

one_frame[k].page_no = Acess_Series[no];

printf(“未命中n”);

break;

}

if(k == Frame)

{

int j = 1;

for(;j <= Frame;j++)

{

one_frame[j1].page_no;one_frame[t1].page_no = one_frame[j].page_no;

}

one_frame[Frame].page_no = Acess_Series[no];

printf(“未命中n”);

}

}

printf(“内存情况为:%d |%d |%d |%dn”, one_frame[0].page_no, one_frame[1].page_no, one_frame[2].page_no, one_frame[3].page_no);

}

rate = effect / 12;

printf(“命中次数：%fn”, effect);

printf(“命中率：%fn”, rate);

}

wait(0);

exit(0);} }