页面置换算法

1. 实验目的

设计和实现最佳置换算法、先进先出置换算法、最近最久未使用置换算法、页面缓冲置换算法；通过页面访问序列随机发生器实现对上述算法的测试及性能比较。

2. 实验题目

1、课题假设前提说明：

1）页表用整数数组或结构数组来表示。

2）页面访问序列串是一个整数序列，整数的取值范围为0到N - 1。页面访问序列串中的每个元素p表示对页面p的一次访问。

2、页面访问序列随机生成说明：

符合局部访问特性的随机生成算法

1）确定虚拟内存的尺寸N，工作集的起始位置p，工作集中包含的页数e，工作集移动率m（每处理m个页面访问则将起始位置p +1），以及一个范围在0和1之间的值t；

2）生成m个取值范围在p和p + e间的随机数，并记录到页面访问序列串中；

3）生成一个随机数r，0 ≤ r ≤ 1；

4）如果r < t，则为p生成一个新值，否则p = (p + 1) mod N；

5）如果想继续加大页面访问序列串的长度，请返回第2步，否则结束。

3、性能测评及问题说明：

1）测试不同的页面访问序列及不同的虚拟内存尺寸，并从缺页率、算法开销等方面对各个算法进行比较。

（同时请给出在给定页面访问序列的情况下，发生页面置换次数的平均值）