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

先說明一下處理缺頁錯(cuò)誤的過程：

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

處理缺頁錯(cuò)誤：

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

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

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

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

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

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

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

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

頁面替換算法：

FIFO:算法

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

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

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

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

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

procedure t: {
  指針p：指向當(dāng)前的頁面
  p = 0;//指向初始位置
  boolean ：標(biāo)志位clock
  boolean : 修改位m
  進(jìn)程包含的所有頁面組成的循環(huán)鏈表：linklist//當(dāng)進(jìn)程在運(yùn)行時(shí)，鏈表存在，進(jìn)程結(jié)束時(shí)，鏈表也消失
  while(進(jìn)程運(yù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)保留一個(gè)空閑幀池。

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

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

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

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

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

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

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