通過代碼實例了解頁面置換算法原理

頁面置換算法：本質(zhì)是為了讓有限內(nèi)存能滿足無線進(jìn)程。

先說明一下處理缺頁錯誤的過程：

分頁硬件在通過頁表轉(zhuǎn)換地址時會注意到無效位被設(shè)置，從而陷入操作系統(tǒng)，這種陷阱是因為操作系統(tǒng)未能將所需要的頁面調(diào)入內(nèi)存引起的。

處理缺頁錯誤：

1、檢查這個進(jìn)程的內(nèi)部表，確定該引用是否為有效的內(nèi)存訪問（可以理解為這個內(nèi)存能被當(dāng)前進(jìn)程使用），如果無效那么直接終止進(jìn)程；如果有效但是尚未調(diào)入頁面，就將該頁面調(diào)入內(nèi)存。

2、然后從空閑幀鏈表上找到一個空閑幀。

3、調(diào)度磁盤將進(jìn)程所需要的內(nèi)存讀入頁幀中，

4、磁盤讀取完成，修改頁表，使空閑幀對應(yīng)到該頁號上。并且修改頁表有效-無效位 為有效。

注意頁表中的一些標(biāo)志位：

修改位：如果有效為位1，表明被修改，那么替換頁面時需要將內(nèi)存寫入磁盤中；如果為0，表明未被修改，那么使用頁面替換算法直接釋放

保護(hù)位：可以標(biāo)記為只讀，寫。

有效-無效位：i：表示邏輯頁號不對應(yīng)物理頁幀，為V表示有對應(yīng)的物理頁幀

頁面替換算法：

FIFO:算法

操作系統(tǒng)總時替換出在內(nèi)存中停留時間最久的頁面，可以用一個指針來指向這個位置（開銷很小，可以使用一個隊列來實現(xiàn)，每次缺頁時移出末尾的頁面，再隊列頭添加新的頁面，未發(fā)生缺頁錯誤就不需要對隊列進(jìn)行操作）

LRU算法：操作系統(tǒng)總時替換在內(nèi)存中最久沒有使用的頁面：我么可以使用鏈表來實現(xiàn)這個算法，表頭表示的是最近被使用的頁面，表尾表示最久沒被使用的頁面，每一次不管是否發(fā)生缺頁，都需要對這個鏈表進(jìn)行從新增刪改查，來保證每一次的鏈表都是我們需要的（開銷太大）

近似LRU算法：我們在頁表中添加一個引用位clock，當(dāng)clock為1時，不能移出，當(dāng)clock為0時，表明可以移除

procedure t: {
  指針p：指向當(dāng)前的頁面
  p = 0;//指向初始位置
  boolean ：標(biāo)志位clock
  進(jìn)程包含的所有頁面組成的循環(huán)鏈表：linklist//當(dāng)進(jìn)程在運行時，鏈表存在，進(jìn)程結(jié)束時，鏈表也消失
  while(進(jìn)程運行){
    
    if(p.clock == 1){
      p.clock = 0;
      p++;//指針指向下一個
    }
    if(p.clock == 0){
      刪除p指向的頁面并且在p處添加新的頁面；
      p.clock = 1;
      p++;
    }
  }
}

近似LRU增強算法：將修改位和引用位合起來作為是否替換條件：當(dāng)（修改位，引用位） = （0，0）時表明可以替換

procedure t: {
  指針p：指向當(dāng)前的頁面
  p = 0;//指向初始位置
  boolean ：標(biāo)志位clock
  boolean : 修改位m
  進(jìn)程包含的所有頁面組成的循環(huán)鏈表：linklist//當(dāng)進(jìn)程在運行時，鏈表存在，進(jìn)程結(jié)束時，鏈表也消失
  while(進(jìn)程運行){
    
  
    if(p.(clock,m) == (0,0)){
      
      刪除p指向的頁面并且在p處添加新的頁面；
      p.(clock,m) = (1,0);
      p++;
    }
    if(p.(clock,m) == (0,1)){
      
      
      p.(clock,m) = (0,0);
      p++;
    }
    if(p.(clock,m) == (1,0)){
      
      
      p.(clock,m) = (0,0);
      p++;
    }
    if(p.(clock,m) == (1,1)){
      
      p.(clock,m) = (0,1);
      p++;
    }
    if(修改頁面){
      p.(clock,m) = (1,1);
      p++
    }
    if(讀頁面){
      p.(clock,m) = (1,0);
      p++;
    }
  }
}

頁面緩沖算法：操作做系統(tǒng)保留一個空閑幀池。

當(dāng)發(fā)生缺頁錯誤時，所需要的頁面就讀取空閑幀，并且將替換的犧牲幀放入緩沖池，在調(diào)頁空閑時期將緩沖池中的犧牲幀中的內(nèi)容寫入（如果頁表上的修改位為1）磁盤中（減少了操作系統(tǒng)的調(diào)頁時直接訪問磁盤的過程，提高了調(diào)頁效率）.

第二種方法：將犧牲幀中的內(nèi)容寫入磁盤，但是不釋放幀中的內(nèi)容，因為進(jìn)程有可能調(diào)用之前的頁，這樣就將緩沖池中的幀直接寫入內(nèi)存，減少了（從磁盤讀取數(shù)據(jù)的操作）。

以上均為局部頁面置換算法，都是在單個進(jìn)程內(nèi)部進(jìn)行的頁面替換操作，但是操作系統(tǒng)在運行過程中不同的進(jìn)程可以并行并發(fā)執(zhí)行，這樣對頁面的替換就不會僅僅局限于單個進(jìn)程中

下面我們學(xué)習(xí)全局置換算法：我們規(guī)定一個工作集和一個常駐集。工作集表明當(dāng)前程序需要訪問的Δ個頁面，常駐集表明操作系統(tǒng)正在使用的頁面。

工作集：WS(Δ，t) = {}　　工作集不斷移動，操作系統(tǒng)替換出不在工作集中的頁面

動態(tài)工作集頁面替換算法：如下圖，我們規(guī)定一個閾值windows size = 2，我們使用兩次缺頁中斷的差值（表明兩次中斷之間有多少次沒有中斷）和閾值比較，如果比閾值大，那么將不再當(dāng)前工作集的頁面換出，并且重置工作集的大小，如果比閾值小，那么將缺的頁換入工作集并且重置工作集的大小。

以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。