操作系统实验四：页面置换算法

代码地址点这里

1.生成随机访问序列

确定虚拟内存的尺寸N（初始设置为3，可修改），工作集的起始位置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步，否则结束。

实验截图如下

我们得到序列为 1 6 4 5 2 6 3 4 3 2 5 3 3 7 2，共15个，下面将其使用各种算法进行页面置换。

2.最佳置换算法

选择永不使用或是在最长时间内不再被访问（即距现在最长时间才会被访问）的页面淘汰出内存

理想化算法，具有最好性能（对于固定分配页面方式，本法可保证获得最低的缺页率），但实际上却难于实现，故主要用于算法评价参照

在实现上，因为序列是已知的，可以找到距现在最长时间不再被访问的页面替换掉，但实际情况中，我们对与后面的序列其实是未知的，所以这是理想化的算法

实验截图如下

3.先进先出置换算法

选择最先进入内存即在内存驻留时间最久的页面换出到外存

进程已调入内存的页面按进入先后次序链接成一个队列，并设置替换指针以指向最老页面

简单直观，但不符合进程实际运行规律，性能较差，故实际应用极少

这个算法在实现上较为简单，就是谁来得早谁走的早，故缺页率较大

实验截图如下

4.最近最久未使用置换算法

以“最近的过去”作为“最近的将来”的近似，选择最近一段时间最长时间未被访问的页面淘汰出内存

适用于各种类型的程序，性能较好，但需要较多的硬件支持

这个也不难理解，在序列中向前找到最长时间未使用的一位，将其替换即可。

实验截图如下

5.改进型clock置换算法

①从查寻指针当前位置起扫描内存分页循环队列，选择A=0且M=0的第一个页面淘汰；若未找到，转②

②开始第二轮扫描，选择A=0且M=1的第一个页面淘汰，同时将经过的所有页面访问位置0；若不能找到，转①

与简单Clock算法相比，可减少磁盘的I/O操作次数，但淘汰页的选择可能经历多次扫描，故实现算法自身的开销增大

实验截图如下

6.页面缓冲置换算法

设立空闲页面链表和已修改页面链表

采用可变分配和基于先进先出的局部置换策略，并规定被淘汰页先不做物理移动，而是依据是否修改分别挂到空闲页面链表或已修改页面链表的末尾

空闲页面链表同时用于物理块分配

当已修改页面链表达到一定长度如Z个页面时，一起将所有已修改页面写回磁盘，故可显著减少磁盘I/O操作次数

实验截图如下

7.实验总结

通过设置不同的访问序列、不同的虚拟内存尺寸可以发现，在这五种页面置换算法中，
opt最佳置换算法确实是最好的，在大多数情况下其缺页率都是最少的，但从时间开销上而言，opt的时间开销比较大
先进先出算法是时间开销最小的，但也因此，其缺页率也比较高
lru算法同opt差不多，一个是往前看，一个是往后看，因此lru也是缺页率低时间开销大。
对于改进clock置换算法，由于他要对内存页面进行多次扫描，因此开销比较大。
对于页面缓冲算法pab，由于其可以一起将所有已修改页面写回磁盘，因此显著减少了磁盘I./O操作次数，降低了开销。

在实验过程中，后两个算法过程较为麻烦。

通过这次实验，对页面置换的主要几种算法有了较明确的认识和了解，对理解操作系统的运行有了很大的帮助