# 页面置换实验文档
## 前言
#### 实验要求
本次页面置换竞争实验要求完成页面置换的模拟,并且会通过三项指标(时间,空间,缺页率)来判断页面置换操作的好坏,最终目的就是使三项指标都尽可能好(由于权值不同而有所侧重)。
回忆了一下,收获还是挺大的:
* 掌握了C++基本特性以及相比C多出的常用语法、常用STL的使用方法,了解了与java的不同
* 学会了CLION的基本使用,包括一些环境的配置,管道的配置,CMAKELIST的写法等等,最终用CLION实现了页面置换的评测机
* 复习了课堂上基本的页面置换算法,对于其优劣势有了更深的理解,同时上网查阅大量资料,学到了相应算法的改进算法
* 手动实现了一系列的容器,考虑了各种操作的时间、空间复杂度,将数据结构的知识进行了具体应用
* 掌握了优化相关技巧,包括register、inline等技巧
## 一、算法设计思想
### 整体策略
![](https://www.writebug.com/myres/static/uploads/2022/5/7/9ba2e22d9ee1cc8422f5e33a0c71bf26.writebug)
由rank标准可知,本次实验需要遵循以下原则:
* **页面命中率高于一切**,不能容忍优化其他指标所带来的缺页增加
* 对**时间成本优化的优先级**高于对**空间成本优化的优先级**
在实验开始之前,我坚信算法的好坏基本决定本次实验的成败,回顾课堂上讲过的具有可操作性的朴素页面置换算法,包括:`FIFO`,`LRU`,`CLOCK`,`LFU`等,发现所有的算法都有劣势,这里不再一一赘述,仔细权衡之后发现`LFU`、`LRU`是一个比较好的选择(可操作性,效果好坏)但是会有一个问题:
### 实例分析
页面访问序列:(4个页框)
1,2,3,4,1,2,5,6,1,2,7,8,1,2,9,10,**96,97,98,99**,1,2,3,4,1,2,5,6,1,2,3,4
* LRU:
冷数据替换热数据:
热数据:1,2(经常需要访问的页面不应该被换出)
冷数据:96,97,98,99(整个过程中只访问一次,不应该替换热数据)
偶尔的冷数据访问把热数据换出
* LFU:
则不会出现,因为历史上大量对热数据进行过访问,新的热数据建立之前,热数据永远不会被换出
页面访问序列:(4个页框)
1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,5,6,5,6,5,6,7,8,7,8,7,8,5,6,5,6,7,8,7,8
曾经的热数据:1,2
* LFU:
由于新的访问模式还没有建立,而之前的历史访问模式认定了1,2是热数据,在新的热数据建立之前,曾经的热数据永远不会被换出,白占了两个页框,即有两个页框被污染。
* LRU:
当访问模式突然改变时,不需要长时间建立“记忆”,不存在缓存污染的情况,曾经的热数据还是会换出,不会白占页框
综上:
* `LRU`较短视,他不是根据长期的访问行为而建立访问模式的,而是根据短期访问行为而建立访问模式,对于之前经常访问并且往后还会经常访问的页面,LRU可能会因为短期没有访问到而将其错误地换出。比如存在周期性、偶发性访问的话,`LRU`将会造成大量缺页
* `LFU`需要历史记录,适应需要时间,即需要一定的时间根据之前的大量访问记录来决定留下哪些页面(访问频率最高),这样导致对于新加入的页面会因为缺乏建立时间,即便之后会被经常访问,但是由于不能马上建立模式,会被错误地置换出去
之后以LRU为突破口我上网搜索发现了几种优化算法:
`LRU-K` `2Q` ` MQ` `LIRS` `ARC`等等,均对LRU做出了改进,经过一番尝试最终选择了`ARC`算法
因此主要介绍``ARC``算法:
从上面分析可知:LRU和LFU几乎是优势互补的,针对不同类型的数据分别有较好的表现,因此一个很自然的想法是:
**能不能把`LRU`和`LFU`结合一下呢?(虽然在某些情况下可能会损失各自原有优势,但总体上更优)**
`ARC`就是这样一个算法:
* 首先将给定的cache先平均分成两半,左边一部分对应LRU算法列表,右边对应LFU算法列表,列表中的每个元素都有对应的实际物理页号字段,这样就建立了映射
* 两个列表**长度可变**
* 为两个列表分别再准备一个**固定长度**的列表,称为``LRUGhost``,``LFUGhost``用来存储被置换出去的页面所对应的元素
* 首次访问的时候插入LRU列表头部
* LRU列表满了则将末尾元素插入``LRUGhost``头部,``LRUGhost``满了还进行插入,则末尾元素移出
* 若击中``LRULive``则将此元素放入`LFULive`,若击中`LFULive`则将此元素提到队首,另外`LFULive`与`LRULive`一样,若满则末尾元素移出,插入`LFUGhost`头部,若满再移出末尾元素
* 若击中`Ghost`则移到对应`Live`头部,若满则同前一样进行调整
整个过程中需要注意,`Ghost`长度是固定不变的,另外`Live`的长度是动态调整的,而这恰恰也是其自适应性的来源
### 图片说明
#### 对LRU
![](https://www.writebug.com/myres/static/uploads/2022/5/7/e0fdd2e9aeb7611ca350acc46097e41c.writebug)
![](https://www.writebug.com/myres/static/uploads/2022/5/7/122634dea2a8f424dff39021eeabbaf0.writebug)
![](https://www.writebug.com/myres/static/uploads/2022/5/7/837219be15428c746d01ca982b0b498e.writebug)
![](https://www.writebug.com/myres/static/uploads/2022/5/7/7bd8faf7517ae19db25855cc3a3f7c1e.writebug)
![](https://www.writebug.com/myres/static/uploads/2022/5/7/82ecb14a0d8cc1fac55e8350a2612c45.writebug)
![](https://www.writebug.com/myres/static/uploads/2022/5/7/1935dac08481c2f016973ef46e538c90.writebug)
![](https://www.writebug.com/myres/static/uploads/2022/5/7/7bc8766d61ec61aa5297ff29c7c3c314.writebug)
![](https://www.writebug.com/myres/static/uploads/2022/5/7/e3bc888d8c0511518e99ae50022abf90.writebug)
#### 对LFU
![](https://www.writebug.com/myres/static/uploads/2022/5/7/ba9412231f6f5ddac541f875cf5e47e7.writebug)
![](https://www.writebug.com/myres/static/uploads/2022/5/7/69fe6968cf60395595b7ccccf8837278.writebug)
![](https://www.writebug.com/myres/static/uploads/2022/5/7/e4f81409ce1c395d2ddeb685b28c1aa2.writebug)
综上,算法具有自适应性:
**能根据当前访问页面的行为动态调整队列长度,以适应当前访问行为,减少缺页**
## 二、算法实现技巧
### 1.建立相应的类
```C++
class Block {
public:
long vpage;
int ppage;
Block *pre;
Block *next;
Block();
};
Block::Block() {
vpage = 0;
ppage = 0;
pre = NULL;
next = NULL;
}
//Live 中对应的元素结构
class GBlock {
public:
long vpage;
GBlock *pre;
GBlock *next;
GBlock();
};
GBlock::GBlock() {
vpage = 0;
pre = NULL;
next = NULL;
}
//Ghost 中对应的元素结构
```
### 2.将具有高度相似性的操作内聚
`ARC`算法两侧几乎相同,可以提取共同的操作,再设不同的标志加以实现:
```C++
int changeCapacity(int choice) {
p += choice;
return 1;
}
//改变Live长度
int setEmptyPage(long *physic_memery,long vpage) {
for (register int i = 0; i < MAX_PHY_PAGE; ++i) {
if (EmptyPage[i] == 0) {
physic_memery[i] = vpage;
EmptyPage[i] = 1;
return i;
}
}
return -1;
}
void clearPhysic(int i) {
EmptyPage[i] = 0;
}
//填入、清空cache
void removeGListTail(int choice,GBlock *gb)
//Ghost 末尾元素出队
void removeListIn(int choice,Block *b)
//击中了Live里面的元素 需要移出
void removeGListIn(int choice,GBlock *gb)
//击中了Ghost里的元素 需要移出
void getFront(Block *b)
//击中了Live里的元素 需要提到最前面
void insertListHead(int choice,Block *b)
//头插Live
void insertGListHead(int choice,GBlock *gb)
//头插Ghost
void freeListTail(int choice,long *physic_memery)
//移除Live末尾元素
void freeGListTail(int choice)
//移除Ghost末尾
没有合适的资源?快使用搜索试试~ 我知道了~
资源推荐
资源详情
资源评论
收起资源包目录
100011904-基于C++进行页面置换实验.zip (57个子文件)
pagereplaceos
CMakeLists.txt 162B
cmake-build-debug
Testing
Temporary
LastTest.log 151B
LastTest-陈思翰的MacBook Pro.log 121B
CMakeFiles
Makefile2 4KB
3.19.2
CMakeRCCompiler.cmake 254B
CompilerIdC
CMakeCCompilerId.c 20KB
a.exe 53KB
CMakeDetermineCompilerABI_CXX.bin 53KB
CMakeCXXCompiler.cmake 6KB
CMakeSystem.cmake 380B
CMakeCCompiler.cmake 3KB
CMakeDetermineCompilerABI_C.bin 53KB
CompilerIdCXX
CMakeCXXCompilerId.cpp 20KB
a.exe 53KB
CMakeDirectoryInformation.cmake 677B
cmake.check_cache 85B
Makefile.cmake 12KB
progress.marks 2B
CMakeOutput.log 69KB
clion-log.txt 881B
ARCchain.dir
main.cpp.obj 43KB
CXX.includecache 276B
objects.a 44KB
link.txt 502B
depend.internal 277B
linklibs.rsp 99B
objects1.rsp 73B
depend.make 201B
flags.make 229B
DependInfo.cmake 767B
cmake_clean.cmake 340B
build.make 6KB
tmp.cpp.obj 553B
progress.make 64B
clion-environment.txt 79B
TargetDirectories.txt 259B
cmake_install.cmake 2KB
Makefile 6KB
ARCchain.cbp 7KB
ARCchain.exe 2.31MB
data500.txt 49.99MB
CMakeCache.txt 48KB
data1000.txt 99.97MB
tmp.cpp 10KB
LICENSE 1KB
main.cpp 10KB
.idea
workspace-陈思翰的MacBook Pro.xml 5KB
vcs.xml 180B
misc.xml 137B
ARCchain.iml 97B
modules.xml 268B
.gitignore 176B
说明文档.md 15KB
OS页面置换答辩.pptx 3.71MB
说明文档.pdf 631KB
README.md 15KB
ARC.pdf 366KB
共 57 条
- 1
资源评论
神仙别闹
- 粉丝: 2712
- 资源: 7668
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功