一、设计目的及意义
- 存储管理的主要功能之一是合理的分配空间，请求页式存储管理是一种常用的虚拟存储管理技术。在地址映射过程中，若在页表中发现所要访问的页面不在内存，则产生中断，当发生中断时，系统必须在内存选择一个页面移出内存，调用页面置换算法，以便为调入新的页面让出空间。
- 本次设计，使用JAVA语言对于置换算法进行模拟实现，通过对请求页式存储管理中页面置换算法的模拟设计 ，掌握请求页式存储管理页面置换算法，并进一步理解虚拟存储技术的原理及特点。
二、需求分析
（一）实现的功能
设计一个虚拟存储及内存工作区，使用先进先出算法（FIFO），最近最久未使用算法（LRU），理想型淘汰算法（OPT），计算不同内存容量下的缺页率，以图表的形式模拟表示出不同算法内存中页面的变化情况，并对不同内存容量下不同算法的缺页率进行比较分析。
1.虚拟内存初始化
根据用户的输入的“物理块数”和“序列数”，确定虚拟内存的大小为，随机生成随机数求余计算得到其所在的页数，并记录到页面访问序列串中；
2.页面置换算法实现
用户选择三种不同的算法进行模拟实现，根据不同的算法规则，以表格的形式表示出内存中页面的变化情况，（其中横坐标表示步数，纵坐标表示物理块数）。每一步，将进入内存的页面进行标记，便于用户观察页面的变化情况，同时计算出缺页次数。
3.缺页率的分析比较
根据缺页次数得到缺页率，从缺页率的角度对各个算法进行比较，得到不同的页面访问序列及不同的虚拟内存大小下的最优算法。
（二）算法分析
1.先进先出算法（FIFO）
优先淘汰最早进入内存的页面，亦即总是选择在内存中驻留时间最久的页面将其淘汰：使用replacepos对于最先进入的页面进行标记，初始化为0，当需要进行置换时，选择Memory[replacepos]，即第一次页面置换替换Memory[0]，然后replacepos = (replacepos + 1) % block，依次执行下去，保证每次都能替换出最先进入内存的页面。
2.最近最久未使用算法（LRU）
选择最近最长时间未访问过的页面予以淘汰：赋予每个页面对应的页表项中，用访问字段记录该页面自上次被访问以来所经历的时间use。当需要淘汰一个页面时，选择现有页面中use值最大的进行置换，置换后对应的页面置为0。
3.理想型淘汰算法（OPT）
被淘汰页面将是以后永不使用的，或者是在最长时间内不再被访问的页面：依次遍历后续所有的页面序列，将已经存在于内存中的序列号进行标记，不同页面出现的位置保存在数组use中，最后，替换use为0的页面，倘若，每个页面在后续页面中都调用，则选择use最大的页面进行替换。
三、详细设计与实现
（一）虚拟内存初始化
进入初始化界面，要求用户输入内存块数以及序列数，便于构造虚拟内存以及随机生成序列
随机生成序列如下，同时将其记录到页面访问序列串中：
关键代码实现如下：
int[] randomSeq = new int[128]; // 随机序列
int[] pageSeq = new int[128];// 页地址流
String[] bcolumnNames = { "编号", "页地址流" }; // 列名
Object[][] btableVales = new Object[128][2]; // 数据
int count = 0;
// 随机生成1到seq区间中的整数
Random r = new Random();
for (count = 0; count < seqNum; count++) {
for (int i = 0; i < seqNum; i++) {// 给tab中的行列赋值
btableVales[i][0] = i;
randomSeq[i] = r.nextInt(100) + 1;
btableVales[i][1] = randomSeq[i] /10;
pageSeq[i] = randomSeq[i] / 10;// 求余，计算所在页数
}
}
HitRate HitFrame = new HitRate(pageSeq, block,seqNum); // 将所在页数和物理块数传值
（二）页面置换模拟
1.FIFO
关键代码实现如下：
boolean flag;
int pos = -1;// 标记指令序列数组
int memorynum = 0;
int[] Memory = new int[block];// 内存物理块所含页面数组
int[][] changecolor = new int[block][seqNum+1];
int replacepos = 0;// 被替换页面所在的物理块
// FIFO算法
if (comboBox.getSelectedItem().equals("FIFO")) {
for (int a = 0; a < block; a++)
Memory[a] = -1; // 初始化为-1
for (int q = 0; q < seqNum; q++) {
flag = false;
pos++;
int temp = seq[pos];// 中间变量暂时存放当前指令所在页地址
// 查看是否已经存在内存中
for (int i = 0; i < block; i++) {
if (Memory[i] == temp) {// 如果命中，命中数+1，跳出循环
flag = true;
break;
}
// 如果未命中，考虑是否要替换
if (!flag) {
FIFOhit++;
if (memorynum < block) {// 如果内存没满，则不用替换
Memory[memorynum] = temp;
changecolor[memorynum][pos + 1] = 1;
memorynum++;
} else {// 如果内存已满，选择最早调入的页面进行替换
Memory[replacepos] = temp;// Memory[replacepos]为被替换的元素，第一次满即替换memory[0]
changecolor[replacepos][pos + 1] = 1;// 标记待变颜色的表格框
replacepos = (replacepos + 1) % block;// 按照block大小来循环替换
}
}
for (int i = 0; i < block; i++)
data1[i][pos + 1] = Memory[i];
2.LRU
关键代码实现如下：
// 如果内存已满，选择最近最久未使用的页面进行替换
for (int i = 1; count < block; i++) {
for (int j = 0; j < block; j++) {
if (Memory[j] == seq[pos - i]) {// 在块中找到了指令序列所在页面
if (use[j] == 0) {
// System.out.println("第"+q+"次use["+j+"]为0，将变为"+i);
count++;
use[j] = i;
}
break;
}
}
int max = 0;
// use最大的即为待替换的页面
for (int i = 0; i < block; i++) {
if (max < use[i]) {
max = use[i];
replacepos = i;
}
}
Memory[replacepos] = temp;// Memory[replacepos]为被替换的元素
changecolor[replacepos][pos + 1] = 1;// 标记待变颜色的表格框
}
3.OPT
关键代码如下：文章来源：https://www.toymoban.com/news/detail-471911.html
for (int x = pos; x < seqNum; x++) {
for (int j = 0; j < block; j++) {
if (Memory[j] == seq[x]) {// 在块中找到了指令序列所在页面
if (use[j] == 0) {
// System.out.println("第"+q+"次use["+j+"]为0，将变为"+i);
count++;
use[j] = x;
}
break;
}
}
if (count == block)// 若块中页面在后续执行指令都调用了
break;
}
boolean flag1 = false;
for (int i = 0; i < block; i++) {
if (use[i] == 0) {
replacepos = i;
flag1 = true;
break;
}
}
if (!flag1) {// 如果每个块中页面在后续指令中都调用了
int max = 0;
// use最大的即为待替换的页面
for (int i = 0; i < block; i++) {
if (max < use[i]) {
max = use[i];
replacepos = i;
}
Memory[replacepos] = temp;// Memory[replacepos]为被替换的元素
（三）缺页率的分析比较
通过计算三种置换算法的缺页率得到最优算法：
文章来源地址https://www.toymoban.com/news/detail-471911.html
实现代码如下：
int min = 128;
String str = null;
if (FIFOhit < min) {
min = FIFOhit; str = "FIFO";
}
if (LRUhit < min) {
min = LRUhit; str = "LRU";
}
if (OPThit < min) {
min = OPThit; str = "OPT";
}
textbest.setText(str);
四、设计总结
- 通过这次课程设计巩固了我平时在课堂上所学的知识，掌握请求页式存储管理页面置换算法，并进一步理解虚拟存储技术的原理，对于不同算法的具体实现也有了更加深刻的认识。
- 在多次的测试运行过程中，可以得到，对同一种算法，对于不同的访问序列，其缺页率是不同，会有所变化，总的来看，最佳置换算法的缺页率是最低的；同时对比不同内存块数下的程序运行结果能够看出，算法的缺页率与分配的内存块数有关系，分配的内存块数越多，缺页率越低。
到了这里，关于页面置换算法模拟实现-操作系统课程设计基于Java的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
