一、实验目的
设计和实现最佳置换算法、随机置换算法、先进先出置换算法、最近最久未使用置 换算法、简单 Clock 置换算法及改进型 Clock 置换算法;通过支持页面访问序列随机发生实现有关算法的测试及性能比较。
二、实验原理
2.1、最佳置换算法
选择永不使用或是在最长时间内不再被访问(即距现在最长时间才会被访问)的页面淘汰出内存。
流程图如下:
2.2、随机值换算法
产生一个取值范围在 0 和 N‐1 之间的随机数,该随机数即可表示应被淘汰出内存的页面。
流程图如下:
2.3、先进先出置换算法
选择最先进入内存即在内存驻留时间最久的页面换出到外存,进程已调入内存的页面按进入先后次序链接成一个队列,并设置替换指针以指向最老页面。
流程图如下:
2.4、最近最久未使用置换算法
以“最近的过去”作为“最近的将来”的近似,选择最近一段时间最长时间未被访问的页面淘汰出内存。
流程图如下:
2.5、简单 Clock 置换算法
2.6、改进型 Clock 置换算法
1 从查寻指针当前位置起扫描内存分页循环队列,选择 A=0 且 M=0 的第一个页 面淘汰;若未找到,转2
2 开始第二轮扫描,选择 A=0 且 M=1 的第一个页面淘汰,同时将经过的所有页 面访问位置 0;若不能找到,转1
流程图如下:
三、实验结果
经过从网上查阅资料得知，较少块数的内存在测试时会影响各种算法的缺页率准确度，导致不好进行比较，所以将内存的块数设为6，然后用较多组数据测试，结果如下：
（表中缺页率均是由多组随机产生的页面进行测试后的平均数）
四、实验结果分析
根据对数据及图表的分析，可以得到以下几个结论：
（1）最佳置换算法在低页面数量下对其他算法有绝对的优势，但在页面数量达到一定数量级后，就会上升到和其他几种算法较接近的缺页率。
（2）随机置换算法效率受页面随机数影响较大，在多次重复实验中表现起伏较明显。
（3）最近最久未使用算法在除最佳置换算法外的几种算法中表现较好且比较稳定。
（4）在页面数量上升到较大数量级后，各种算法的缺页率较为接近且都稳定在38%左右，这个值取决于一开始规定的内存数量大小。
（5）在内存数量较小且页面数量足够多时，改进clock算法对简单clock算法有明显的优势。
五、实验总结
反思：
在处理实验数据时遇到很多问题，比如一开始，我用内存数量为3进行测试，导致各种算法缺页率差别较大，趋势也很不稳定，后来在各方面查阅资料后得知，修改内存大小可以有效解决这个问题，实验后果然趋势变得稳定。
测试不同的页面访问序列及不同的虚拟内存尺寸，并回答以下问题（同时请给出在给定页面访问序列的情况下，发生页面置换次数的平均值）
FIFO算法是否比随机置换算法优越？
答：是的，在多数情况下先进先出算法缺页率要小于随机置换算法，且更加稳定。平均值为：38.92（FIFO）39.73（随机）
LRU算法比FIFO 算法优越多少？
答：平均值为：37.45（LRU）和38.92（FIFO），优越四个百分点左右
LRU算法和Optimal算法有何差距？
答：LRU算法是通过最近最久未使用的页面来预估将来发生的页面，而Opt算法直接可以预见到未来，所以预测的缺页率要大于将来发生替换的实际缺页率。37.45（LRU）24.57（OPT）
Clock算法和LRU算法有何差距？
简单的 Clock 算法和 LRU 算法差距较大,比 LRU 算法的缺页率高出大约3个百分点，在较大页面数量后，改进型的clock算法可以接近LRU算法