题目
写一个程序来实现 FIFO 和 LRU 页置换算法。首先，产生一个随机的页面引用序列，页面数从 0~9。将这个序列应用到每个算法并记录发生的页错误的次数。实现这个算法时要将页帧的数量设为可变。假设使用请求调页。可以参考所示的抽象类。
抽象类：
public abstract class ReplacementAlgorithm
{
protected int pageFaultCount; // the number of page faults
protected int pageFrameCount; // the number of physical page frame
// pageFrameCount the number of physical page frames
public ReplacementAlgorithm(int pageFrameCount) {
if (pageFrameCount <0)
throw new IllegalArgumentException();
this.pageFrameCount = pageFrameCount;
pageFaultCount= 0;
}
// return - the number of page faults that occurred
public int getPageFaultCount() {
return pageFaultCount;
}
// int pageNumber - the page number to be inserted
public abstract void insert (int pageNumber);
}
采用 LRU 页置换算法，另一个采用 FIFO 算法。
有两个类可以在线测试你的算法。
（1）PageGenerator——该类生成页面引用序列，页面数从 0~9。引用序列
的大小可作为 PageGenerateor 构造函数的参数。在创建 PageGenerator 对象后，
可用方法 getReferenceString0 方法返回作为引用序列的整数数组。
（2）Test-用来测试你的基于 ReplacementAlgorithm 的两个类 FIFO 与 LRU。
Test 可按如下方法调用：
Java Test <reference string #> <# of page frames> 算法介绍
先进先出算法（FIFO）：缺页中断发生时，系统选择在内存中驻留时间最长的页面淘汰。通常采用链表记录进入物理内存中的逻辑页面，链首时间最长。
该算法实现简单，但性能较差，调出的页面可能是经常访问的页面，而且进程分配物理页面数增加时，缺页并不一定减少(Belady 现象)。
优点 ：实现简单，只需要维护一个先进先出队列，每次淘汰时直接操作队列头部即可。
缺点 ：性能较差，因为被调出的页面可能是经常访问的页面。会发生 Belady 现象（颠簸现象），当进程分配的物理页面数增加时，缺页次数反而可能增加。
Java伪代码：
public class FIFO {
private Queue<Integer> queue = new LinkedList<>();
private Set<Integer> pageSet = new HashSet<>();
private int capacity;
public FIFO(int capacity) {
this.capacity = capacity;
}
public void accessPage(int page) {
if (pageSet.contains(page)) {
// 页面已在内存中，不需要处理
return;
}
if (pageSet.size() < capacity) {
// 内存未满，将页面加入队列和集合
queue.offer(page);
pageSet.add(page);
System.out.println("页面 " + page + " 调入内存");
} else {
// 内存已满，淘汰队首页面
int evictPage = queue.poll();
pageSet.remove(evictPage);
System.out.println("页面 " + evictPage + " 被淘汰");
// 将新页面加入队列和集合
queue.offer(page);
pageSet.add(page);
System.out.println("页面 " + page + " 调入内存");
}
}
public static void main(String[] args) {
FIFO fifo = new FIFO(3);
int[] pages = {1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5};
for (int page : pages) {
System.out.print("访问页面 " + page + "：");
fifo.accessPage(page);
System.out.println("当前内存中的页面：" + fifo.pageSet);
System.out.println();
}
}
}
最近最久未使用算法（LRU）：算法思想是缺页发生时，选择最长时间没有被引用的页面进行置换，如某些页面长时间未被访问，则它们在将来还可能会长时间不会访问。该算法的开销较大。
优点 ：具有较好的性能，能够较好地预测页面的使用频率。
缺点 ：实现相对复杂，需要记录每个页面的访问时间，并且每次访问都需要更新访问时间。
Java伪代码：
public class LRU {
private Map<Integer, Integer> pageMap = new HashMap<>();
private List<Integer> pageList = new ArrayList<>();
private int capacity;
public LRU(int capacity) {
this.capacity = capacity;
}
public void accessPage(int page) {
if (pageMap.containsKey(page)) {
// 页面已在内存中，更新其位置
pageList.remove(Integer.valueOf(page));
pageList.add(page);
System.out.println("页面 " + page + " 已在内存中，更新其位置");
} else {
if (pageList.size() < capacity) {
// 内存未满，将页面加入列表和映射
pageList.add(page);
pageMap.put(page, pageList.size() - 1);
System.out.println("页面 " + page + " 调入内存");
} else {
// 内存已满，淘汰最久未使用的页面（列表开头的页面）
int evictPage = pageList.remove(0);
pageMap.remove(evictPage);
System.out.println("页面 " + evictPage + " 被淘汰");
// 将新页面加入列表和映射
pageList.add(page);
pageMap.put(page, pageList.size() - 1);
System.out.println("页面 " + page + " 调入内存");
}
}
}
public static void main(String[] args) {
LRU lru = new LRU(3);
int[] pages = {1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5};
for (int page : pages) {
System.out.print("访问页面 " + page + "：");
lru.accessPage(page);
System.out.println("当前内存中的页面：" + lru.pageList);
System.out.println();
}
}
}关键步骤
(1)在PageGenerator类中，构造函数PageGenerator(int count)中生成随机的页面引用序列。
public PageGenerator(int count) {
if (count < 0)
throw new IllegalArgumentException();
java.util.Random generator = new java.util.Random();
referenceString = new int[count];
for (int i = 0; i < count; i++)
referenceString[i] = generator.nextInt(RANGE + 1);
}(2)在ReplacementAlgorithm抽象类的子类FIFO和LRU中，实现页面置换算法。
FIFO类：实现FIFO算法（First-In, First-Out）：将最早插入的页面替换出去。
@Override
public void insert(int pageNumber) {
boolean pageFault = true;
// 检查页面是否已经在物理页面帧中
for (int i = 0; i < pageFrameCount; i++) {
if (pageFrames[i] == pageNumber) {
pageFault = false;
break;
}
}
// 如果页面不在物理页面帧中，则发生页面错误
if (pageFault) {
pageFaultCount++;
pageFrames[currentIndex] = pageNumber;
currentIndex = (currentIndex + 1) % pageFrameCount;
}
}LRU类：实现LRU算法（Least Recently Used）：将最长时间未被使用的页面替换出去
@Override
public void insert(int pageNumber) {
boolean pageFault = true;
int oldestTimestampIndex = 0;
int oldestTimestamp = timestamps[0];
// 检查页面是否已经在物理页面帧中
for (int i = 0; i < pageFrameCount; i++) {
if (pageFrames[i] == pageNumber) {
pageFault = false;
// 更新页面的时间戳
timestamps[i] = getCurrentTimestamp();
break;
}
// 找到最老的时间戳和对应的页面帧索引
if (timestamps[i] < oldestTimestamp) {
oldestTimestamp = timestamps[i];
oldestTimestampIndex = i;
}
}
// 如果页面不在物理页面帧中，则发生页面错误
if (pageFault) {
pageFaultCount++;
pageFrames[oldestTimestampIndex] = pageNumber;
timestamps[oldestTimestampIndex] = getCurrentTimestamp();
}
}
(3)在Test类中，使用FIFO和LRU算法计算页面错误次数。
PageGenerator ref = new PageGenerator(new Integer(args[0]).intValue());
int[] referenceString = ref.getReferenceString();
/** Use either the FIFO or LRU algorithms */
ReplacementAlgorithm fifo = new FIFO(new Integer(args[1]).intValue());
ReplacementAlgorithm lru = new LRU(new Integer(args[1]).intValue());
// 插入页面时输出消息
for (int i = 0; i < referenceString.length; i++) {
// System.out.println("inserting " + referenceString[i]);
lru.insert(referenceString[i]);
}
// 插入页面时输出消息
for (int i = 0; i < referenceString.length; i++) {
// System.out.println("inserting " + referenceString[i]);
fifo.insert(referenceString[i]);
}
// 报告页面错误总数
System.out.println("LRU faults = " + lru.getPageFaultCount());
System.out.println("FIFO faults = " + fifo.getPageFaultCount());源码
/**
* This class generates page references ranging from 0 .. 9
*
* Usage:
* PageGenerator gen = new PageGenerator()
* int[] ref = gen.getReferenceString();
*/
public class PageGenerator
{
private static final int DEFAULT_SIZE = 100;
private static final int RANGE = 9;
int[] referenceString;
public PageGenerator() {
this(DEFAULT_SIZE);
}
public PageGenerator(int count) {
if (count < 0)
throw new IllegalArgumentException();
java.util.Random generator = new java.util.Random();
referenceString = new int[count];
for (int i = 0; i < count; i++)
referenceString[i] = generator.nextInt(RANGE + 1);
}
public int[] getReferenceString() {
/**
* comment out the following two lines to
* generate random reference strings
*/
int[] str = {7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1};
//int[] str = {1,2,3,4,1,2,5,1,2,3,4,5};
return str;
/**
* and uncomment the following line
*/
//return referenceString;
}
}
/**
* ReplacementAlgorithm.java
*
*/
public abstract class ReplacementAlgorithm
{
// the number of page faults
protected int pageFaultCount;
// the number of physical page frame
protected int pageFrameCount;
/**
* @param pageFrameCount - the number of physical page frames
*/
public ReplacementAlgorithm(int pageFrameCount) {
if (pageFrameCount < 0)
throw new IllegalArgumentException();
this.pageFrameCount = pageFrameCount;
pageFaultCount = 0;
}
/**
* @return - the number of page faults that occurred.
*/
public int getPageFaultCount() {
return pageFaultCount;
}
/**
* @param pageNumber - the page number to be inserted
*/
public abstract void insert(int pageNumber);
}
public class FIFO extends ReplacementAlgorithm{
private int[] pageFrames;
private int currentIndex;
public FIFO(int pageFrameCount){
super(pageFrameCount);
pageFrames = new int[pageFrameCount];
currentIndex = 0;
}
@Override
public void insert(int pageNumber) {
boolean pageFault = true;
//check pages whether in pageFrames
for(int i =0;i<pageFrameCount;i++){
if(pageFrames[i]==pageNumber){
pageFault = false;
break;
}
}
//if pages not in pagesFrames,it happens faults
if(pageFault){
pageFaultCount++;
pageFrames[currentIndex] = pageNumber;
currentIndex = (currentIndex+1)%pageFrameCount;
}
}
}
public class LRU extends ReplacementAlgorithm{
private int[] pageFrames;
private int[] timestamps;
/**
* @param pageFrameCount - the number of physical page frames
*/
public LRU(int pageFrameCount) {
super(pageFrameCount);
pageFrames = new int[pageFrameCount];
timestamps = new int[pageFrameCount];
}
@Override
public void insert(int pageNumber) {
boolean pageFault = true;
int oldestTimestampIndex = 0;
int oldestTimestamp = timestamps[0];
//check pages whether in pagesFrames
for(int i =0;i<pageFrameCount;i++){
if(pageFrames[i]==pageNumber){
pageFault = false;
//upgrade pageTimestaps
timestamps[i] = getPageFaultCount();
break;
}
if(timestamps[i]<oldestTimestamp){
oldestTimestamp = timestamps[i];
oldestTimestampIndex = i;
}
}
//if not in pagesFrame,happen faults
if(pageFault){
pageFaultCount++;
pageFrames[oldestTimestampIndex]=pageNumber;
timestamps[oldestTimestampIndex]=getCurrentTimestamp();
}
}
//acquire current timestamp
private int getCurrentTimestamp(){
return pageFaultCount+1;
}
}
/**
* Test harness for LRU and FIFO page replacement algorithms
*
*/
public class Test
{
public static void main(String[] args) {
if (args.length != 2) {
System.err.println("Usage: java Test <reference string size> <number of page frames>");
System.exit(-1);
}
PageGenerator ref = new PageGenerator(Integer.valueOf(args[0]).intValue());
int[] referenceString = ref.getReferenceString();
/** Use either the FIFO or LRU algorithms */
ReplacementAlgorithm fifo = new FIFO(Integer.valueOf(args[1]).intValue());
ReplacementAlgorithm lru = new LRU(Integer.valueOf(args[1]).intValue());
// output a message when inserting a page
for (int i = 0; i < referenceString.length; i++) {
//System.out.println("inserting " + referenceString[i]);
lru.insert(referenceString[i]);
}
// output a message when inserting a page
for (int i = 0; i < referenceString.length; i++) {
//System.out.println("inserting " + referenceString[i]);
fifo.insert(referenceString[i]);
}
// report the total number of page faults
System.out.println("LRU faults = " + lru.getPageFaultCount());
System.out.println("FIFO faults = " + fifo.getPageFaultCount());
}
}运行结果
参数设置 20-3
参数设置 20-4
思考
在实现了 FIFO 与 LRU 算法后，给定引用序列，试验不同页帧的数量所产
生的缺页次数。并分析：一个算法比另一好么？对给定引用序列，页帧的最佳数
量是多少？假设给定引用序列 1，2，3，4，1，2，5，1，2，3，4，5，当页帧
数分别为 3 和 4 时，用 FIFO 置换算法时缺页中断分别为多少？
根据代码，可以通过修改 Test 类的 main 方法中的 args 数组来改变页面帧的数量和引用序列的大小。以下是分别使用 FIFO 和 LRU 置换算法对给定引用序列进行测试的结果：
（1）当页帧数为 3 时：
使用 FIFO 置换算法，缺页次数为 9
使用 LRU 置换算法，缺页次数为 9
