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

先說(shuō)明一下處理缺頁(yè)錯(cuò)誤的過(guò)程：

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

處理缺頁(yè)錯(cuò)誤：

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

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

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

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

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

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

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

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

頁(yè)面替換算法：

FIFO:算法

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

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

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

procedure t: {
  指針p：指向當(dāng)前的頁(yè)面
  p = 0;//指向初始位置
  boolean ：標(biāo)志位clock
  進(jìn)程包含的所有頁(yè)面組成的循環(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指向的頁(yè)面并且在p處添加新的頁(yè)面；
      p.clock = 1;
      p++;
    }
  }
}

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

procedure t: {
  指針p：指向當(dāng)前的頁(yè)面
  p = 0;//指向初始位置
  boolean ：標(biāo)志位clock
  boolean : 修改位m
  進(jìn)程包含的所有頁(yè)面組成的循環(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指向的頁(yè)面并且在p處添加新的頁(yè)面；
      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(修改頁(yè)面){
      p.(clock,m) = (1,1);
      p++
    }
    if(讀頁(yè)面){
      p.(clock,m) = (1,0);
      p++;
    }
  }
}

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

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

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

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

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

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

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

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