页面置换算法
- 实验目的
设计和实现最佳置换算法、先进先出置换算法、最近最久未使用置换算法、页面缓冲置换算法;通过页面访问序列随机发生器实现对上述算法的测试及性能比较。
- 实验题目
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)测试不同的页面访问序列及不同的虚拟内存尺寸,并从缺页率、算法开销等方面对各个算法进行比较。
(同时请给出在给定页面访问序列的情况下,发生页面置换次数的平均值)