关键词：
一、 实验目的
1、了解虚拟存储技术的特点，掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。
2、了解程序设计技术和内存泄露的原因
二、 实验环境
Windows操作系统、g++编译器
三、 实验内容
模拟实现请求页式存储管理的几种基本页面置换算法
（1）最佳淘汰算法（OPT）
（2）先进先出的算法（FIFO）
（3）最近最久未使用算法（LRU））
四、 实验要求
1、画出每个页面置换算法流程图；
2、对算法所用的数据结构进行说明；
3、测试数据随机产生。不可手工输入；
4、编写程序并调试；
5、多次测试程序，截屏输出实验结果；
6、根据实验结果与理论课讲述的原理进行实验分析。
五、 实验原理 实验中用到的系统调用函数（包括实验原理中介绍的和自己采用的），实验步骤
实验原理
1、虚拟存储系统
UNIX中，为了提高内存利用率，提供了内外存进程对换机制；内存空间的分配和回收均以页为单位进行；一个进程只需将其一部分（段或页）调入内存便可运行；还支持请求调页的存储管理方式。
当进程在运行中需要访问某部分程序和数据时，发现其所在页面不在内存，就立即提出请求（向CPU发出缺中断），由系统将其所需页面调入内存。这种页面调入方式叫请求调页。
为实现请求调页，核心配置了四种数据结构：页表、页框号、访问位、修改位、有效位、保护位等。
2、页面置换算法
当CPU接收到缺页中断信号，中断处理程序先保存现场，分析中断原因，转入缺页中断处理程序。该程序通过查找页表，得到该页所在外存的物理块号。如果此时内存未满，能容纳新页，则启动磁盘I/O将所缺之页调入内存，然后修改页表。如果内存已满，则须按某种置换算法从内存中选出一页准备换出，是否重新写盘由页表的修改位决定，然后将缺页调入，修改页表。利用修改后的页表，去形成所要访问数据的物理地址，再去访问内存数据。整个页面的调入过程对用户是透明的。
（1）最佳淘汰算法（OPT）：选择永不使用或在未来最长时间内不再被访问的页面予以替换。
（2）先进先出的算法（FIFO）：选择在内存中驻留时间最久的页面予以替换。
（3）最近最久未使用算法（LRU）：选择过去最长时间未被访问的页面予以替换。
3、首先用srand( )和rand( )函数定义和产生指令序列，然后将指令序列变换成相应的页地址流，并针对不同的算法计算出相应的命中率。
（1）通过随机数产生一个指令序列，共320条指令。指令的地址按下述原则生成：
A：50%的指令是顺序执行的
B：25%的指令是均匀分布在前地址部分
C：25%的指令是均匀分布在后地址部分
具体的实施方法是：
A：在[0，319]的指令地址之间随机选取一起点m
B：顺序执行一条指令，即执行地址为m+1的指令
C：在前地址[0,m+1]中随机选取一条指令并执行，该指令的地址为m’
D：顺序执行一条指令，其地址为m’+1
E：在后地址[m’+2，319]中随机选取一条指令并执行
F：重复步骤A-E，直到320次指令
（2）将指令序列变换为页地址流
设：页面大小为1K；
用户内存容量4页到32页；
用户虚存容量为32K。
在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：
第 0 条-第 9 条指令为第0页（对应虚存地址为[0，9]）
第10条-第19条指令为第1页（对应虚存地址为[10，19]）
………………………………
第310条-第319条指令为第31页（对应虚存地址为[310，319]）
按以上方式，用户指令可组成32页。
实验中用到的系统调用函数
因为是模拟程序，可以不使用系统调用函数。
实验步骤：
算法中所用的数据结构：
//指令的集合
int instructions[INSTRUCT_COUNT + 10];
//指令对应的页面
int pages[INSTRUCT_COUNT + 10];
//内存
int memory[MAX_PAGES + 10];
//记录数组（OPT中记录下一次使用将是什么时候，LRU中用来记录最近一次使用是什么时候，以便淘汰）
int record[MAX_PAGES + 10];
OPT算法程序流程图：
FIFO算法程序流程图：
LRU算法的程序流程图：
六、 实验结果分析（截屏的实验结果，与实验结果对应的实验分析）
1、实验结果与实验程序、实验步骤、实验原理、操作系统原理的对应分析；
2、不同条件下的实验结果反应的问题及原因；
3、实验结果的算法时间、效率、鲁棒性等性能分析。
随机生成的指令对应的页面：
OPT算法：
FIFO算法：
LRU算法:
将实验结果绘制成折线图，如图所示：
测试多几组数据：
从图中可以得出结论：
- 随着内存容量的增加，命中率也逐渐增加，整体呈上升的趋势。命中率最高接近90%
- FIFO和LRU算法整体上相差不大，LRU算法整体上会好一些，而FIFO算法在实现上只根据“先进先出”的规则进行置换，也没有像LRU算法那样根据“最长时间未使用”的规则进行置换，所以命中率在整体上略低于LRU。
- 由于指令序列是随机生成的，FIFO也比较受随机性的影响，所以FIFO和LRU算法的命中率有时候会相差较大（如图3）
- OPT算法的命中率在整体上远远领先其他两种算法，这是因为OPT算法具有预知未来的能力，实现上算法的时间复杂度也比另外两种算法的高
- OPT算法只是一种理想算法，实际上不可能实现，这是因为程序在运行过程中不可能对未来要使用到的页面进行精确地断言，这里也只是个模拟实验，已经提前把之后要使用的所有页面都存到pages数组里面了，所以可以模拟实现一下。
七、 实验数据及源代码（学生必须提交自己设计的程序源代码，并有注释，源代码电子版也一并提交），包括思考题的程序。
实验源代码：
#include <bits/stdc++.h>
using namespace std;
//生成的指令数量
#define INSTRUCT_COUNT 320
//内存最大的页面数
#define MAX_PAGES 32
//指令的集合
int instructions[INSTRUCT_COUNT + 10];
//指令对应的页面
int pages[INSTRUCT_COUNT + 10];
//内存
int memory[MAX_PAGES + 10];
//记录数组（OPT中记录下一次使用将是什么时候，LRU中用来记录最近一次使用是什么时候，以便淘汰）
int record[MAX_PAGES + 10];
//打开文件，用于把数据输出到文件，方便绘制折线图
FILE* opt;
FILE* fifo;
FILE* lru;
//初始化数据
void init()
srand((unsigned long)time(0)); //随机数种子
int i = 0;
int m,m1,m2;
//F：重复步骤A-E，直到320次指令
while(i < INSTRUCT_COUNT)
// A：在[0，319]的指令地址之间随机选取一起点m
m = rand() % 320;
instructions[i++] = m;
// B：顺序执行一条指令，即执行地址为m+1的指令
instructions[i++] = m + 1;
// C：在前地址[0,m+1]中随机选取一条指令并执行，该指令的地址为m’
m1 = rand() % (m + 2);
instructions[i++] = m1;
// D：顺序执行一条指令，其地址为m’+1
instructions[i++] = m1 + 1;
// E：在后地址[m’+2，319]中随机选取一条指令并执行
m2 = rand() % (320 - m1 - 2) + m1 + 2;
instructions[i++] = m2;
i = 0;
//计算指令对应的页面
while(i < INSTRUCT_COUNT)
pages[i] = instructions[i] / 10;
++i;
//输出：
printf("指令对应的页面如下：\\n");
i = 0;
while(i < INSTRUCT_COUNT)
printf("%d%c", pages[i++]," \\n"[i == INSTRUCT_COUNT - 1]);
//展开实验：不按照实验要求初始化数据，完全随机
void init1()
srand((unsigned long)time(0)); //随机数种子
int i = 0;
int m,m1,m2;
//F：重复步骤A-E，直到320次指令
while(i < INSTRUCT_COUNT)
m = rand() % 320;
instructions[i++] = m;
i = 0;
//计算指令对应的页面
while(i < INSTRUCT_COUNT)
pages[i] = instructions[i] / 10;
++i;
//输出：
printf("指令对应的页面如下：\\n");
i = 0;
while(i < INSTRUCT_COUNT)
printf("%d%c", pages[i++]," \\n"[i == INSTRUCT_COUNT - 1]);
//最佳淘汰算法（OPT）
void OPT(int capatity)
memset(memory,-1,sizeof(memory));
int right = 0;//命中次数
//扫描页面
for(int i = 0;i < INSTRUCT_COUNT;++i)
int p = pages[i]; //当前访问到的页面
//扫描memory，判断内存中是否已经有了这个页面
int j = 0;
while(j < capatity && memory[j] != -1 && memory[j] != p)
++j;
if(j == capatity)
//缺页中断，而且内存已满，需要执行页面置换算法
//初始化数组
memset(record,INSTRUCT_COUNT + 10,sizeof(record));
//两层for循环，记录一下下次使用是在什么时候
for(int k1 = 0;k1 < capatity;++k1)
for(int k2 = i;k2 < INSTRUCT_COUNT;++k2)
if(memory[k1] == pages[k2])
record[k1] = k2;
break;
//下面开始遍历record数组，看看距离下一次使用的时间最长是谁
int ma = 0;
int mi = 0;
for(int k = 0;k<capatity;++k)
if(record[k] > ma)
ma = record[k];
mi = k;
//找出最长时间的那个之后直接置换掉
memory[mi] = p;
else
if(memory[j] == p)
//页面在内存中，命中
++right;
else
//缺页中断，但是还有容量，直接插在后面
memory[j] = p;
//输出
double rate = right * 1.0 / INSTRUCT_COUNT;
printf("当内存容量为%2d页时，命中率为%lf\\n",capatity,rate);
fprintf(opt,"%lf\\n",rate);
//先进先出的算法（FIFO）
void FIFO(int capatity)
memset(memory,-1,sizeof(memory));
int right = 0;//命中次数
int pi = 0; //队列指针（指向memory中最后一个为-1的下标，如果没有为-1的就是指向最先进来的那个页面的下标）
//扫描页面
for(int i = 0;i < INSTRUCT_COUNT;++i)
int p = pages[i]; //当前访问到的页面
//扫描memory，判断内存中是否已经有了这个页面
int j = 0;
while(j < capatity && memory[j] != -1 && memory[j] != p)
++j;
if(j < capatity && memory[j] == p)
//页面在内存中，命中
++right;
continue;
//页面不在内存中，需要执行算法
//实现方式：队列
memory[pi++] = p;
pi %= capatity; //超过容量之后从0开始，会自动指向最先进来的那个页面的下标
//输出
double rate = right * 1.0 / INSTRUCT_COUNT;
printf("当内存容量为%2d页时，命中率为%lf\\n",capatity,rate);
fprintf(fifo,"%lf\\n",rate);
//最近最久未使用算法（LRU）
void LRU(int capatity)
//初始化数组
memset(memory,-1,sizeof(memory));
memset(record,-1,sizeof(record));
int right = 0;//命中次数
//扫描页面
for(int i = 0;i < INSTRUCT_COUNT;++i)
int p = pages[i]; //当前访问到的页面
//扫描memory，判断内存中是否已经有了这个页面
int j = 0;
while(j < capatity && memory[j] != -1 && memory[j] != p)
++j;
if(j == capatity)
//缺页中断，而且内存已满，需要执行页面置换算法
//下面开始遍历record数组，看看谁是最久未使用的
int mv = 0x3f3f3f3f;
int mi = 0;
for(int k = 0;k<capatity;++k)
if(record[k] < mv)
mv = record[k];
mi = k;
//找出最长时间的那个之后直接置换掉
memory[mi] = p;
//记录最近使用时间
record[mi] = i;
else
if(memory[j] == p)
//页面在内存中，命中
++right;
else
//缺页中断，但是还有容量，直接插在后面
memory[j] = p;
//记录最近使用时间
record[j] = i;
//输出
double rate = right * 1.0 / INSTRUCT_COUNT;
printf("当内存容量为%2d页时，命中率为%lf\\n",capatity,rate);
fprintf(lru,"%lf\\n",rate);
int main()
init();
opt = fopen("D:\\\\Documents\\\\opt.txt","w");
fifo = fopen("D:\\\\Documents\\\\fifo.txt","w");
lru = fopen("D:\\\\Documents\\\\lru.txt","w");
clock_t start, finish;
printf("--------------OPT--------------\\n");
start = clock();
//用户内存容量4页到32页
for(int i = 4;i <= MAX_PAGES;++i)
OPT(i);
finish = clock();
// printf("%f seconds\\n\\n",(finish - start) / CLOCKS_PER_SEC);
printf("--------------FIFO--------------\\n");
start = clock();
//用户内存容量4页到32页
for(int i = 4;i <= MAX_PAGES;++i)
FIFO(i);
finish = clock();
// printf("%f seconds\\n\\n",(finish - start) / CLOCKS_PER_SEC);
printf("--------------LRU--------------\\n");
start = clock();
//用户内存容量4页到32页
for(int i = 4;i <= MAX_PAGES;++i)
LRU(i);
finish = clock();
// printf("%f seconds\\n\\n",(finish - start) / CLOCKS_PER_SEC);
fclose(opt);
fclose(fifo);
fclose(lru);
return 0;
八、思考题：
1、从几种算法的命中率看，哪个算法最高？哪个算法最低？对每个页面的执行结果进行分析。
答：从上面的结果来看，OPT算法的命中率最高，FIFO的命中率相对较低。在前面的实验结果分析中已经简单总结过这3种算法的差别。
2、OPT算法在执行过程中可能会发生错误，为什么？
答：OPT算法本身就是一种理想算法，实际上不可能实现，因为操作系统是不可能对以后要使用到的页面进行精确地判断的，可能会存在一些差错，因此OPT算法在执行过程中可能会发生错误。
mit-6.828lab2实验报告(代码片段)
...agement实验报告tags:mit-6.828os概述本文主要介绍lab2，讲的是操作系统内存管理，从内容上分为三部分：第一部分讲的是物理内存管理，要进行内存管理首先需要知道哪些物理内存是空闲的，哪些是被使用的。还需要实现一些函数对... 查看详情
操作系统第5次实验报告：内存管理(代码片段)
李微微201821121001计算18111.记录内存空间使用情况 ①根据实验课上的PPT，记录进程使用了哪些内存空间，用链表实现。在结构体里声明进程ID、占用大小、起始地址、进程名和指向自己类型的指针，用于存放进程信息... 查看详情
操作系统存储管理实验课程设计报告(代码片段)
操作系统报告存储管理姓名： 郑兆涵 专业： 计算机科学与技术(嵌入式方向)一、设计目的、意义本次实验针对：(1)存储管理实验，(2)主存储器空间的分配和回收实验，... 查看详情
操作系统实验报告磁盘管理实验(代码片段)
...xff09;、电梯扫描算法（SCAN）。二、实验环境Windows操作系统、g++编译器三、实验内容1、模拟先来先服务法（First-Come,Firs 查看详情
实验2后篇——内存管理算法(代码片段)
实验2介绍了操作系统的基本内存管理，或者说是系统内存管理的软件接口实现。这对于我们实际上碰到的内存管理操作有一些差距，所以我们这一节补充一些内容，来详细介绍一些内存管理技术。 ... 查看详情
实验2正篇——内存管理(代码片段)
...的准备终于进入正题了。本实验主要介绍的是我们实现的操作系统中的内存管理。实验将以两部分内容进行讲解——内核与操作系统我们将互用，请根据实际情况理解： 第一部分是内核的物理内存分配器，内... 查看详情
操作系统实验报告进程管理与进程通信(代码片段)
一、实验目的1、掌握进程的概念，明确进程的含义。2、认识并了解进程并发执行的实质，进程的阻塞与唤醒，终止与退出的过程。3、熟悉进程的睡眠、同步、撤消等进程控制方法。4、分析进程竞争资源的现象，... 查看详情
python课设：作业统计管理系统，源码+实验报告+论文需要自取(代码片段)
作业管理统计系统ChapterOne【需求分析】ChapterTwo【总体设计】ChapterThree【详细设计】ChapterFour【课设总结】ChapterFive【课设感想】最后ChapterOne【需求分析】1、问题根据需求，该系统所应包含的信息有以下一些:学生提交作业情... 查看详情
实验2正篇——内存管理(代码片段)
...的准备终于进入正题了。本实验主要介绍的是我们实现的操作系统中的内存管理。实验将以两部分内容进行讲解——内核与操作系统我们将互用，请根据实际情况理解： 第一部分是内核的物理内存分配器，内... 查看详情
操作系统实验报告四
操作系统实验4题目1：编写页面内存的LRU替换算法在实验3基础上考虑，如果当前分配的内存或保存页面的数据项已经被用完，这时再有新的网页请求，需要对已在内存中的网页数据进行替换，本实验内容需要使用LRU算法来对内存... 查看详情
linux实验报告——磁盘存储管理——2021.5.22(代码片段)
Linux实验报告（2）——磁盘存储管理一丶配置要求：二丶实验目的三丶实验要求四丶上一篇：Linux实验报告（1）——文件权限与管理五丶下一篇：Linux实验报告（3）——计划任务管理一丶配置要... 查看详情
实验报告：实验九(代码片段)
实验内容：1.补全程序t1.asm，完成在屏幕上输出内存单元中的十进制两位数。 ;在屏幕上输出内存单元中的十进制两位数assumecs:code,ds:datadatasegmentdb12db?,?;前一个字节用于保存商，后一个字节用于保存余数dataendscodesegmentstart:movax... 查看详情
linux实验报告——计划任务管理——2021.5.22(代码片段)
Linux实验报告（3）——计划任务管理一丶配置要求：二丶实验目的三丶实验要求：(Root)四丶上一篇：Linux实验报告（2）——磁盘存储管理一丶配置要求：虚拟机VM15.0及以上版本centos7.0版本windows7或win... 查看详情
实验2前篇——x86内存管理(代码片段)
...富；但其实没有进入主题。然而它们却是实现与理解操作系统的必要步骤与开端。纯粹的操作系统的理论总是让人无法身临其境的去理解而且实用性不是很强 ，而且我觉得操作系统的相关理论都是经验的总结，而无... 查看详情
ucore实验(代码片段)
实验目的了解操作系统开发实验环境熟悉命令行方式的编译、调试工程掌握基于硬件模拟器的调试技术熟悉C语言编程和指针的概念了解X86汇编语言实验概述lab1：硬件层实现，中断等lab2：物理内存管理lab3：虚拟内... 查看详情
大数据hadoop实验报告(代码片段)
文章目录实验一熟悉常用的Linux操作和Hadoop操作1.实验目的2.实验平台3.实验内容和要求实验二熟悉常用的HDFS操作1.实验目的2.实验平台3.实验步骤实验三熟悉常用的HBase操作1.实验目的2.实验平台3.实验步骤实验四MapReduce/Spark编程初... 查看详情
大数据hadoop实验报告(代码片段)
文章目录实验一熟悉常用的Linux操作和Hadoop操作1.实验目的2.实验平台3.实验内容和要求实验二熟悉常用的HDFS操作1.实验目的2.实验平台3.实验步骤实验三熟悉常用的HBase操作1.实验目的2.实验平台3.实验步骤实验四MapReduce/Spark编程初... 查看详情
实验2后篇——内存管理算法(代码片段)
实验2介绍了操作系统的基本内存管理，或者说是系统内存管理的软件接口实现。这对于我们实际上碰到的内存管理操作有一些差距，所以我们这一节补充一些内容，来详细介绍一些内存管理技术。 ... 查看详情