操作系统实验四：页面置换算法实验报告.pdf
67 浏览量
2022-12-22
20:51:33
上传
评论
收藏 631KB PDF 举报
操作系统实验四：页⾯置换算法实验报告
操作系统实验四：页⾯置换算法 实验报告
1、实验⽬的
设计和实现最佳置换算法、先进先出置换算法、最近最久未使⽤置换算法、页⾯缓冲置换算法；通过页⾯访问序列随机发⽣器实现对上述算
法的测试及性能⽐较。
2、页⾯置换算法背景知识
（1） 请求分页虚拟内存管理
请求分页虚拟内存管理是建⽴在基本分页基础上的，为了能⽀持虚拟存储器功能，⽽增加了请求调页功能和置换功能。
（2） ⼯作集
多数程序都显⽰出⾼度的局部性，也就是说，在⼀个时间段内，⼀组页⾯被反复引⽤。这组被反复引⽤的页⾯随着时间的推移，其成员也会
发⽣变化。有时这种变化是剧烈的，有时这种变化则是渐进的。我们把这组页⾯的集合称为⼯作集
（3） 缺页率
缺页中断次数/总的页⾯访问次数
3、实验假设
（1）模拟的虚拟内存的地址为16位，页⾯⼤⼩为1K，模拟的物理内存有32K。
（2）表⽤整数数组或结构数组来表⽰
（3） 页⾯访问序列串是⼀个整数序列，整数的取值范围为0到N - 1。页⾯访问序列串中的每个元素p表⽰对页⾯p的⼀次访问
（4） 符合局部访问特性的随机⽣成算法
确定虚拟内存的尺⼨N，⼯作集的起始位置p，⼯作集中包含的页数e，⼯作集移动率m（每处理m个页⾯访问则将起始位置p +1），以及⼀
个范围在0和1之间的值t
⽣成m个取值范围在p和p + e间的随机数，并记录到页⾯访问序列串中
⽣成⼀个随机数r，0 ≤ r ≤ 1
如果r < t，则为p⽣成⼀个新值，否则p = (p + 1) mod N
如果想继续加⼤页⾯访问序列串的长度，请返回第2步，否则结束
4、实验算法介绍
（1） 最佳置换算法
最佳置换算法的主要思想是，在发⽣页⾯替换时，被替换的对象应该满⾜，在以后的页⾯访问中，该对象不会再次被访问或者较晚被访问。
是⼀种理想化算法，具有最好性能（对于固定分配页⾯⽅式，本法可保证获得最低的缺页率），但实际上却难于实现，故主要⽤于算法评价
参照。
（2） 先进先出置换算法
先进先出置换算法的主要思想是，在发⽣页⾯替换时，被替换的对象应该是最早进⼊内存的。
（3） 最近最久未使⽤置换算法
最近最久未使⽤置换算法的主要思想是，在发⽣页⾯替换时，被替换的页⾯应该满⾜，在之前的访问队列中，该对象截⽌⽬前未被访问的时
间最长。
（4） 改进型Clock置换算法
改进型Clock置换算法的主要思想是，在每次页⾯替换时，总是尽可能地先替换掉既未被访问⼜未被修改的页⾯。
（5） 页⾯缓冲算法
设⽴空闲页⾯链表和已修改页⾯链表采⽤可变分配和基于先进先出的局部置换策略，并规定被淘汰页先不做物理移动，⽽是依据是否修改分
别挂到空闲页⾯链表或已修改页⾯链表的末尾,空闲页⾯链表同时⽤于物理块分配,当已修改页⾯链表达到⼀定长度如Z个页⾯时，⼀起将所有
已修改页⾯写回磁盘，故可显著减少磁盘I/O操作次数。
5、主要函数功能说明
（1） 全局共享函数
void InitMemo();//初始化存储空间，主要是设置分配空间的⼤⼩
void Generate();//⽣成访问序列
bool IsInMemo (int n); //指定页号是否已经在内存中
（2） 最佳置换算法
资源评论
