操作系统|| 虚拟内存页置换算法

题目

写一个程序来实现 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 faultsprotected int pageFaultCount;// the number of physical page frameprotected 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;}@Overridepublic void insert(int pageNumber) {boolean pageFault = true;//check pages whether in pageFramesfor(int i =0;i<pageFrameCount;i++){if(pageFrames[i]==pageNumber){pageFault = false;break;}}//if pages not in pagesFrames,it happens faultsif(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];}@Overridepublic void insert(int pageNumber) {boolean pageFault = true;int oldestTimestampIndex = 0;int oldestTimestamp = timestamps[0];//check pages whether in pagesFramesfor(int i =0;i<pageFrameCount;i++){if(pageFrames[i]==pageNumber){pageFault = false;//upgrade pageTimestapstimestamps[i] = getPageFaultCount();break;}if(timestamps[i]<oldestTimestamp){oldestTimestamp = timestamps[i];oldestTimestampIndex = i;}}//if not in pagesFrame,happen faultsif(pageFault){pageFaultCount++;pageFrames[oldestTimestampIndex]=pageNumber;timestamps[oldestTimestampIndex]=getCurrentTimestamp();}}//acquire current timestampprivate  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 pagefor (int i = 0; i < referenceString.length; i++) {//System.out.println("inserting " + referenceString[i]);lru.insert(referenceString[i]);}// output a message when inserting a pagefor (int i = 0; i < referenceString.length; i++) {//System.out.println("inserting " + referenceString[i]);fifo.insert(referenceString[i]);}// report the total number of page faultsSystem.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