changed 4 years ago  
Published Linked with GitHub

OS筆記-Chapter 9: Virtual Memory

tags: OS

目錄

背景

  • 虛擬記憶體(virtual memory)允許行程可以不必完全存在記憶體中就能執行
    • 程式不再被可用實體記憶體總量限制
    • 更多程式可一起執行
    • 載入或置換各個程式進記憶體所需會減少
    • 虛擬記憶體可以比實體記憶體大
    • 虛擬位址空間(virtual memory space)
    • 只有在堆積或堆疊成長時，虛擬位址空間才需要更多的實體分頁
    • 共用程式庫也被視為虛擬位址空間中的一部份(通常唯讀)

需求分頁(Demand Paging)

  • 程式一開始只載入它所需要的分頁到實體記憶體

  • 懶惰置換程式(lazy swapper):當需要某一頁時，將該頁置換進來

    • 為置換的輔助記憶體稱為置換空間(swap space)
    • 置換程式是處理整個行程，所以使用分頁程式這個詞比較適合

  • 分頁錯誤(page-fault)

    • 程式想使用一頁尚未被載入記憶體的資料
    • 使用有效-無效位元
    • 載入需要的頁
    • 純粹需求分頁(pure damand paging):直到需要某頁時才把它載入記憶體中

  • 參考之區域性(locality of reference):最近剛剛被引用過的一個內存位置容易再次被引用

    • 使需求分頁有不錯的效能

  • 有效存取時間(effective access time):(1-p)* ma+p*分頁錯誤的時間

    • p表示出現分頁錯誤比率(page-fault rate)
    • ma(memory acess)表示存取時間

  • 以磁碟輸入/輸出作為置換空間，通常要較以檔案系統處理快

    • 行程開始前，將全部檔案複製到置換空間
    • 分頁被替換時才被複製到置換空間

寫入時複製(Copy-on-Write)

  • 寫入時複製(Copy-on-Write):一般來說fork()讓父行程與子行程在一開始分享共同的分頁

    • 如果有行程想寫入共享的分頁才複製分頁
    • 因此許多作業系統對於這些要求提供一池(pool)的空白頁
    • 需求時填入零(zero-fill-on-demand):分頁在被配置前已經被填入零，因此清除了此分頁之前的內容

  • vfork():不使用寫入時複製，所以必須注意子行程會不會修改父行程的位址空間

分頁替換(Page Replacement)

  • 過度配置(over-allocating):當每個分頁本來需要10個欄，但有5個欄用不到，因此在40個欄的記憶體中，我們執行8個行程，但任何一個行程可能突然需要它原本的10個分頁，導致欄不足

  • 基本分頁替換

    • 找一個目前未使用的欄，把它空出來
    • 更改分頁表，該欄內容寫入置換空間中
    • 分頁錯誤將花兩倍的時間(分頁一出一進)

  • 修改位元/髒位元(modify bit/dirty bit)

    • 當某頁被改過時，以此位元指示此頁已被修改
    • 若某頁沒有修改過，則不需寫回置換空間

  • 欄的配置演算法(Frame-allocation algorithm)

    • 每個行程配置多少欄
    • 哪個欄應該被置換

  • 分頁替換演算法(Page-replacement algorithm)

    • 最低的分頁錯誤比率
    • 欄數越多，通常分頁錯誤越低

  • FIFO演算法

    • 參考串(Reference string):7,0,1,2,0,3,0,4,2,3,0,3,0,3,2,1,2,0,1,7,0,1
    • Belady's anomaly:配置的欄數增加，分頁錯誤比率卻增加
      • 參考串:1,2,3,4,1,2,5,1,2,3,4,5

  • 最佳分頁替換(otimal algorithm)

    • 把未來最常時間之內不會用到的那一頁替換掉
    • 保證在固定欄數，有最低的分頁錯誤比率
    • 難以預知參考串的內容
    • 參考串(Reference string):7,0,1,2,0,3,0,4,2,3,0,3,0,3,2,1,2,0,1,7,0,1

  • LRU分頁替換(Least Recently Used Algorithm)

    • 替換掉近來最少使用的分頁
    • 計數器:在CPU上加入邏輯時中或計數器，每當經過一次記憶體參考後就增加一次，對某頁參考時，就會複製該計數器的值到分頁表上，每次替換最小時間數值的分頁
    • 堆疊(stack):將被參考的分頁放到堆疊頂端，堆疊最下面則是近來最少使用的分頁
      • 參考串:4,7,0,7,1,0,1,2,1,2,7,1,2

  • LRU近似分頁替換法(LRU Approximation Algorithms)

    • 參考位元(reference bit):當某頁被參考時被設定，雖然不能知道次序，但能知道那些分頁被使用過
      • 額外參考位元:假設8-bit，每次右移一個位元，可代表近8個時間的使用狀況，比較數值大小，數值最小則是近來最少使用的分頁
    • 第二次機會演算法(second-chance page-replacement algorithm):以FIFO替換法為主，但當參考位元為1的分頁要被替換時，將參考位元改為0，並給予第二次的機會
    • 加強第二次機會演算法
      • 以參考位元與髒位元當作依據
        1. (0,0):最近沒被存取，也沒被修改
        2. (0,1):最近沒被存取，但曾被修改
        3. (1,0):最近被存取，但沒被修改
        4. (1,1):最近被存取，且曾被修改
      • 傾向選擇最近沒被修改的，以降低寫回置換空間所需的時間

  • 技術基礎分頁替換(Counting Algorithms)

    • 以計數器紀錄每一頁被參考過的次數
      • 最不經常使用(LFU,least frequently used):次數最少的被替換
      • 最常被使用(MFU,most frequently used):認為次數最少的剛載入不久，將要被使用

  • 頁緩衝演算法(Page-Buffering Algorithms)

    • 系統有空白欄作為庫存
    • 在犧牲欄被寫出之前，頁先被讀入庫存的欄，犧牲欄寫出後，犧牲欄加入庫存

欄的配置(Allocation of Frames)

  • 每個行程必須配置一個最少量的欄數

    • 欄數太低，分頁錯誤比率上升，影響效能

  • 配置演算法

    • 同等分配(equal allocation):m個欄分給n個行程，每個行程得m/n個欄
    • 比例分配(proportional allocation):每個行程得(該行程虛擬記憶體大小/總行程虛擬記憶體大小)* 欄數

  • 全體和區域配置

    • 全體替換法(global replacement):行程可以從所有欄選出一個替換的欄，包括其他行程使用中的欄
    • 區域替換法(local replaccement):行程只能從自己的欄選出一個替換的欄
    • 區域替換法可能因頁數不足而延遲行程，通常全體替換法有較好的效能

  • 不一致的記憶體存取(NUMA,non-uniform memory access)

    • 主記憶體上某些部分被CPU存取的時間比其他部分來的快，取決於CPU與記憶體如何連結
    • 必須改變原本視記憶體存取速度一致的演算法，盡可能最小延遲的配置記憶體欄到CPU上的行程
    • 地址群組(lgroup):聚集了接近的CPU和記憶體，利用地址群組來配置行程的所有記憶體

輾轉現象(Thrashing)

  • 輾轉現象

    • 若行程沒有足夠的欄，需要新的欄時，將其他行程正在使用的欄替換，等等又要替換回來，導致不斷的出現分頁錯誤
    • CPU排班程式發現CPU使用率降低，所以增加多元程式規劃程度，再度導致分頁錯誤增加(替換掉別的行程的欄)

  • 優先權替換演算法(priorty replacement algorithm)

    • 從自己的欄選出一個替換的欄
    • 先替換優先權低的欄
    • 不會引起其他行程的輾轉現象
    • 但本身會需要等待較長的分頁錯誤時間

  • 局部區域模式(locality model)

    • 一個局部區域就是一組同時被使用的頁
    • 一個程式由多個局部區域組成
    • 分配足夠的欄以滿足程式的局部區域，能避免輾轉現象

  • 工作組模式(working-set model)

    • 工作組欄框(working-set window):檢查最近Δ頁參考
    • 工作組(working set):這Δ頁中的頁
    • t₁時，工作組={1，2，5，6，7}
    • t₂時，工作組={3，4}
    • WSSᵢ (working set of Process Pᵢ)
    • D(對欄的需求) = Σ WSSᵢ
    • D > 可用欄數，發生輾轉現象
    • 避免輾轉現象，當D大於可用欄數，系統賄選出一個行程被擱置

  • 分頁錯誤頻率(Page-Fault Frequency)

    • 當錯誤頻率太高，需要更多欄
    • 當錯誤頻率太低，行程有太多欄
    • 藉由監測分頁錯誤頻率，以防止輾轉現象
      • 超過上限的行程，配置欄
      • 超過蝦線的行程，收回欄

  • 工作群組與分頁錯誤

    • 工作群組剛開始移動時，出現較高的分頁錯誤

記憶體對映檔案(Memory-Mapped Files)

  • 原本每次檔案被讀取時，需要一次系統呼叫和磁碟的存取，記憶體對映檔案將檔案I/O視為經常性的記憶體存取

  • 共用記憶體實際上以記憶體對映檔案來製作

  • 記憶體對映I/O(Memory-Mapped I/O):使用記憶體對映到裝置暫存器，適合快速回應的裝置(例如:螢幕)

核心記憶體配置(Allocating Kernel Memory)

  • 核心記憶體通常從可用記憶體池配置，與平常滿足使用者模式行程的串列不同

    • 核心為大小不同的資料結構要求大小不一的記憶體
    • 有時需要連續的記憶體

  • 夥伴系統(Buddy System)

    • 使用2的次方配置器(power-of-2 allocator)
    • 最初256KB的連續記憶體被分為兩個夥伴Aʟ，Aʀ
    • 合併(coalescing):可將相連的夥伴聯合形成更大的區段
    • 內部斷裂問題嚴重

  • 平板配置(Slab Allocator)

    • 平板:由一個或多個實體連續分頁組成
    • 快取(cache):由一個或多個平板組成
    • 物件(object)與快取一起存在
    • 不會有斷裂
    • 預先產生物件，因此能很快配置記憶體
      • 物件被標示為已使用、閒置

其他考慮的因素(Other Considerations)

  • 預先分頁(Prepaging)

    • 把所有需要的頁在同一時間都載入記憶體中
    • 避免行程剛開始執行時出現一大堆分頁錯誤

  • 分頁的大小

    • 較小的分頁
      • 能減少內部斷裂
      • 較佳的解析度(resolution)，能將實際需要的記憶體載入
    • 較大的分頁
      • 能減少I/O時間
        • 雖然分頁大小決定轉移時間，但潛伏與搜尋時間遠遠大於轉移時間
      • 能減少分頁錯誤的次數

  • TLB範圍(TLB Reach)

    • 指TLB能存取的記憶體數量
    • TLB範圍 = (TLB Size) X (Page Size)
    • 加大TLB範圍(加大分頁)，可能導致一些應用程式根本不需要如此大的分頁
    • 有些作業系統提供大小不一的分頁大小

  • 程式結構

    • 假設一頁128個字元組
    • 一欄為一頁，因此造成128* 128個分頁錯誤
    • 將程式碼改為如下，則可避免
    • 使用者對基本需求分頁有所了解的話，對系統性能有很大的幫助

  • I/O交互上鎖(I/O interlock)

    • 將分頁鎖在記憶體中，以免導致I/O要求被推進到佇列前端時，該分頁被置換，該欄已被其他行程使用
Select a repo