操作系統|| 虛擬內存頁置換算法

題目

寫一個程序來實現 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