天天看點
傳回

計算機結構（Computer Architecture）----------- 虛拟記憶體（Virtual Memory）頁替換算法(Java實作OPT/ESC/FIFO)

當某個程序将記憶體中配置設定的空間全部使用了，這時需要使用一個新page的内容，這page不在記憶體中，是以就會發生page fault。此時就要在記憶體空間中挑選一個犧牲的page，将它換回Disk，把需要的新page引入記憶體中。如何挑選一個最适合的犧牲page（比如将來程序不再使用或最少或最久才會使用的page）這就是頁面替換算法要做的事情。

在介紹頁替換算法前，我們先來看一個公式：

  • Effective access time：EAT = (1-p) * memory access time + p * page fault time ; （p 為 page fault rate）

由上面的公式我們可以看出，一個系統的執行效率跟發生 page fault 的次數與機率息息相關，是以就需要一個好的頁面替換算法來提升系統存取資料的效率。下面我們就來聊一聊在Virtual Memory中存在的幾種頁面替換算法。

頁面替換算法：

  • FIFO algorithm:

FIFO的本質其實就是一個隊列，秉承着先進先出的原則。如圖：

計算機結構（Computer Architecture）----------- 虛拟記憶體（Virtual Memory）頁替換算法(Java實作OPT/ESC/FIFO)

 第4次引用的 page 為 2 ，記憶體中隻有 7/0/1，發生 page fault 則将最早進入記憶體的 7 替換。第5次 page 為0 ，在記憶體中命中，不發生page fault，第6次 page 為 3，将記憶體最早的0 替換...。以此類推。

Page Fault 次數：15；

優點：實作簡單。

缺點：效能不一定很高，而且會發生Belady‘s anomaly，即記憶體越大分越多的page frame反而會導緻page fault rate的上升。

  • Optimal algorithm：

OPT是最佳的頁面替換算法，沒有之一。

原理：預測未來，在未來記憶體中哪個page是最久才會被再次使用，就先将此 page 替換。如圖：

計算機結構（Computer Architecture）----------- 虛拟記憶體（Virtual Memory）頁替換算法(Java實作OPT/ESC/FIFO)

第4次引用的 page 為 2 ，發生page fault，OS開始預測未來，同樣page為7的是最久後才會被再次使用，将它替換。第6次 page 為 3，未來記憶體中page 為 1的是最久以後才會再次被使用，将它替換...。以此類推。

Page Fault 次數：9；

優點：最佳即page fault rate最低。而且不會發生 Belady's anomaly。

缺點：無法實作，因為人類無法預測未來。但仍然可以用此作為标杆來檢測其他算法的效能。

  • LRU algorithm：(Least recently used)

最接近OPT的算法。

 原理：最近記憶體中最久沒被使用或最少被使用的page，作為被替換者。其實就是假定認為一個page你最近一段時間沒用它，那麼将來一段時間也很可能不會用它。

計算機結構（Computer Architecture）----------- 虛拟記憶體（Virtual Memory）頁替換算法(Java實作OPT/ESC/FIFO)

Page Fault 次數：12；

主要實作方式有兩種：

  • Counter Implement

原理：為page table 中的每一個entry都添加一個“時間域” ， 然後CPU添加一個時鐘或者計數器。一個page每次被引用，時鐘或計數器的值就會被copy到此page所在entry的“時間域”内，發生page fault時就将時間最小或者計數值最小的被替換。

  • Stack Implement

采用棧的方式，棧的實作可以用指針連結清單。

原理：每當引用一個page，該page就從棧中删除，然後重新放到棧頂，這樣棧底部的 page 就是最久未使用的，将作為替換頁。

                   原棧長這樣 ==>

計算機結構（Computer Architecture）----------- 虛拟記憶體（Virtual Memory）頁替換算法(Java實作OPT/ESC/FIFO)

        當讀下一個為 7 的page，棧變成==>

計算機結構（Computer Architecture）----------- 虛拟記憶體（Virtual Memory）頁替換算法(Java實作OPT/ESC/FIFO)

優點：效能好，同樣不會發生Belady's anomaly。

缺點：實作的成本太高，而且不太實際，需要随時更新、記錄時鐘或者棧。

  • ESC algorithm：(Enhance second-change)

近似LRU的算法。

ESC算法采用了，reference bit 和 modify bit，用來輔助選擇替換的頁面。

Bits (ref , mod) 含義 優先級
（0，0） 近期既未被引用，也未被修改 最佳替換頁
（0，1） 被修改過，但近期未被引用 需要寫入Disk在被替換前
（1，0） 近期被引用過，但未被修改 可能再次被使用，給第二次機會
（1，1） 近期即被修改，也被引用 最糟替換頁

原理：OS第一次會搜尋記憶體中為(0,0)的page，若沒有，則會重新再搜(0,1) 的page，此時若遇到 ref 位為 1 的page 會将其 ref 位 清零等于給了第二次機會，若搜完連為(0,1)的page也沒有。就重新執行一次上面的搜尋動作，先(0,0)後(0,1)。因為上一次在搜(0,1）時已經對 ref 位清零過，是以這次一定能夠找到(0,0)或(0,1)的page。

  • ARB algorithm：(Additional-reference-bits)

ARB算法，在記憶體中為page table中的每一個 page 額外儲存一個 8 bits 移位寄存器，在規定間隔時間内(100ms)産生一個中斷，将控制權交給OS。然後OS會将此時刻每個page的 reference bit 值記錄到移位寄存器中的最高位，而移位寄存器中的其它位右移動1位。是以這8bits的移位寄存器記錄了某page 8個周期的使用情況，根據 8 bits 的值，最小的将作為替換頁。移位寄存器，不一定是8bits，如是1bit 就等于是單純使用reference bit，也就是SC algorithm。

如下圖：11000100值是比01110111大，是以01110111将作為替換頁。

計算機結構（Computer Architecture）----------- 虛拟記憶體（Virtual Memory）頁替換算法(Java實作OPT/ESC/FIFO)

其實還有SC，MFU，LFU等算法，不一一介紹了。

FIFO/OPT/ESC Java代碼模拟實作： 

import java.util.ArrayList;
import java.util.Queue;
import java.util.Random;
import java.util.concurrent.ArrayBlockingQueue;

public class Algorithm {
	// frame capacity
	private int CAPACITY;

	ArrayList<Integer> optIndex;
	int FifoPageFault;
	int OptPageFault;
	int EscPageFault;
	int EscWriteDisk;

	Queue<Integer> fifoFrame;
	ArrayList<Integer> optFrame;
	ArrayList<int[]> escFrame;

	public Algorithm(int capacity) {
		super();
		this.CAPACITY = capacity;
	}

	/*
	 * ESC算法
	 */
	public void ESC(ArrayList<Integer> arr) {
		escFrame = new ArrayList<int[]>();

		for (int i = 0; i < arr.size(); i++) {
			if (escFrame.size() < CAPACITY) {
				boolean indexHit = false;
				for (int j = 0; j < escFrame.size(); j++) {
					int[] eFrame = escFrame.get(j);
					if (eFrame != null && eFrame[2] == arr.get(i)) {
						indexHit = true;
						break;
					}
				}
				if (!indexHit) {
					int[] eFrame = createEachEscFrame();
					eFrame[2] = arr.get(i);
					escFrame.add(eFrame);
					EscPageFault++;
				}
			} else {
				boolean indexHit = false;
				for (int j = 0; j < escFrame.size(); j++) {
					int[] eFrame = escFrame.get(j);
					if (eFrame[2] == arr.get(i)) {
						// 再次被引用，Hit後記憶體中此frame reference bit set 1
						eFrame[0] = 1;
						indexHit = true;
						break;
					}
				}
				if (!indexHit) {
					EscPageFault++;
					boolean indexRep = false;
					for (int j = 0; j < escFrame.size(); j++) {
						int[] check00 = escFrame.get(j);
						if (check00[0] == 0 && check00[1] == 0) {
							int[] eFrame = createEachEscFrame();
							eFrame[2] = arr.get(i);
							escFrame.set(j, eFrame);
							indexRep = true;
							break;
						}
					}
					if (!indexRep) {
						for (int j = 0; j < escFrame.size(); j++) {
							int[] check01 = escFrame.get(j);
							if (check01[0] == 0 && check01[1] == 1) {
								int[] eFrame = createEachEscFrame();
								eFrame[2] = arr.get(i);
								escFrame.set(j, eFrame);
								EscWriteDisk++;
								indexRep = true;
								break;
							} else {
								check01[0] = 0;
							}
						}
					}
					if (!indexRep) {
						for (int j = 0; j < escFrame.size(); j++) {
							int[] checkAll = escFrame.get(j);
							if (checkAll[0] == 0 && checkAll[1] == 0) {
								int[] eFrame = createEachEscFrame();
								eFrame[2] = arr.get(i);
								escFrame.set(j, eFrame);
								break;
							} else if (checkAll[0] == 0 && checkAll[1] == 1) {
								int[] eFrame = createEachEscFrame();
								eFrame[2] = arr.get(i);
								escFrame.set(j, eFrame);
								EscWriteDisk++;
								break;
							}
						}
					}
				}
			}
		}
	}
	//建立page，模拟每一個frame中page的引用與修改
	public int[] createEachEscFrame() {
		int[] eFrame = new int[3];
		// page一旦被使用reference就置1， 随機獲得0或1,指派給 dirty bit
		int referenceBit = 1;
		int dirtyBit = (int) (Math.random() * 2);
		eFrame[0] = referenceBit;
		eFrame[1] = dirtyBit;
		return eFrame;
	}
	
	/*
	 * FIFO算法
	 */
	public void FIFO(ArrayList<Integer> arr) {
		fifoFrame = new ArrayBlockingQueue<Integer>(CAPACITY);
		for (int i = 0; i < arr.size(); i++) {
			if (fifoFrame.size() < CAPACITY) {
				if (fifoFrame.contains(arr.get(i))) {
					continue;
				} else {
					fifoFrame.add(arr.get(i));
					FifoPageFault++;
				}
			} else {
				if (fifoFrame.contains(arr.get(i))) {
					continue;
				} else {
					fifoFrame.poll();
					fifoFrame.add(arr.get(i));
					FifoPageFault++;
				}
			}
		}
	}

	/*
	 * OPT算法
	 */
	public void OPT(ArrayList<Integer> arr) {
		optFrame = new ArrayList<Integer>();
		for (int i = 0; i < arr.size(); i++) {
			if (optFrame.size() < CAPACITY) {// frame未滿
				if (optFrame.contains(arr.get(i))) {
					continue;
				} else {// 頁面不在記憶體,發生page fault
					optFrame.add(arr.get(i));
					OptPageFault++;
				}
			} else {// frame已滿
				if (optFrame.contains(arr.get(i))) {
					continue;
				} else {// 頁面不在記憶體,發生page fault
					OptPageFault++;
					optIndex = new ArrayList<Integer>();
					for (int j = i; j < arr.size(); j++) {
						if (optFrame.contains(arr.get(j)) && !optIndex.contains(optFrame.indexOf(arr.get(j)))) {
							optIndex.add(optFrame.indexOf(arr.get(j)));
							if (optIndex.size() == CAPACITY) {
								optFrame.set(optIndex.get(CAPACITY - 1), arr.get(i));
								break;
							}
						}
					}
					if (optIndex.size() < CAPACITY) {
						int[] useless = new int[CAPACITY - optIndex.size()];
						int a = 0;
						for (int z = 0; z < CAPACITY; z++) {
							if (!optIndex.contains(z)) {
								useless[a++] = z;
							}
						}
						Random rnd = new Random();
						int replace = rnd.nextInt(useless.length);
						optFrame.set(useless[replace], arr.get(i));
					}
				}

			}
		}

	}

僅為個人了解，如有不足，請指教。  https://blog.csdn.net/weixin_35811044

計算機結構 fifo LRU Optimal Esc
上一篇: S3C6410啟動模式介紹【轉載】目前的ARM處理器都支援多種啟動模式，S3C6410和以前的Samsung的ARM處理器一樣，通過外部管腳OM[4:0]的拉高拉低來決定是從哪個儲存設備上啟動。我認為S3C6410的User Manual并沒有說的很清楚，是以我在最開始使用的時候，也對其啟動模式有一些誤解，下面就我個人的了解，介紹一下S3C6410的啟動。
下一篇: UBOOT移植------smdk6410配置檔案分析

繼續閱讀